Garbage Collection and Swap

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've been researching garbage collection.

Let me first get it out in the open that I *despise* the concept of garbage collection. I worried when I first heard of a magical automatic free()/delete[] that it would do one or more of two things:

~ - Create excessive overhead
~ - Free up ram I'm still using

I've learned that the first may or may not be true. This means that they've won on some accounts with that one.

The second may or may not occur as well. It worries me that it may in certain cases, due to the way GC works. Most garbage collectors will look in the heap, maybe the stack, maybe other places, for what looks like pointers to allocated ram. If they don't find any, they free the ram.

So, the first extremely obvious thing you'll notice is that GC may at times miss things, especially if you use the XOR linked list trick or use your own makeshift swap file (write pointers to disk, read back in).

After a while, a big one hit me.

THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO YOUR ALLOCATED DATA.

Read that. It's in all caps, so you should read it. It has meaning.

How about, everything is using Bohem GC. Bohem wanders around in the heap concurrently. So all of your applications are wandering around through their vm space everywhere, continuously.

You get low on ram. Let's say an app is using 500M of ram (Mozilla). What's going to happen? Obvious. It's going to yank shit out of swap.

If we all linked against a GC, what kinds of swap hell do you think we'd encounter?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA7zvMhDd4aOud5P8RAh8zAJ9zTAH2D+aJOpK60Gz2FiWfKE/iYQCfShG1 GuXdbh0ZRJuwCX2fLleOBbw=
=Glt1
-----END PGP SIGNATURE-----

Ones almost as bad as the Hell of trolls going nuts over hypothetical problems no one is stupid enough to cause in practice anyway.

-- wli

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

William Lee Irwin III wrote:

| On Fri, Jul 09, 2004 at 08:43:57PM -0400, John Richard Moser wrote:
|
|>Read that.  It's in all caps, so you should read it.  It has meaning.
|>How about, everything is using Bohem GC.  Bohem wanders around in the
|>heap concurrently.  So all of your applications are wandering around
|>through their vm space everywhere, continuously.
|>You get low on ram.  Let's say an app is using 500M of ram (Mozilla).
|>What's going to happen?  Obvious.  It's going to yank shit out of swap.
|>If we all linked against a GC, what kinds of swap hell do you think we'd
|>encounter?
|
|
| Ones almost as bad as the Hell of trolls going nuts over hypothetical
| problems no one is stupid enough to cause in practice anyway.
|
|

I'm actually trying to get the boehm one up, but it keeps setting PaX off for some odd reason. I'd intended to have some test data right about now. . . . >/ Firefox, gimp, hell vim can't run with boehm LD_PRELOAD to redirect malloc(). Nano can. A simple tester can. fortune can't. BASH doesn't seem to like it.

It's only hypothetical until I prove or disprove it; and I'm not afraid to do either.

| -- wli
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA7145hDd4aOud5P8RAkTCAJ9onJMZS5bFzu8ppfvyWg8vOE5SzQCeL5SR NZPBU5gMs/ZSl0iXuJmvnYQ=
=UVWv
-----END PGP SIGNATURE-----

Look up "generational garbage collection".

I suspect that, when tuned right, generational garbage collection could actually be quite VM friendly...

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

... and of course the guy has one of those broken
challenge-response authentication protocol (CRAP)
systems in front of his mailbox.

Last time I'll ever help him out...

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Rik van Riel wrote:

| On Sat, 10 Jul 2004, Rik van Riel wrote:
|
|
|
| ... and of course the guy has one of those broken
| challenge-response authentication protocol (CRAP)

hum?

| systems in front of his mailbox.
|
| Last time I'll ever help him out...
|

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA8KGnhDd4aOud5P8RAkCuAJ9mM8UfpgZ73pMoJzMDIW/aWvU/hACgjA0c 4fTJmFghiE7QMd7riRRQX/I=
=9cfV
-----END PGP SIGNATURE-----

Whose GC does this?

I get the impression that the Java VM, for instance, knows what variables are pointers (well, references) and only considers those. It also knows every object that has even been allocated. It scans over every pointer it knows about (the "mark" phase), and then it scans over every dynamically allocated memory block (the "sweep" phase) and removes all that have no references.

There is anecdotal evidence that this approach sometimes can improve performance over "manual" freeing because freeing can be done in bulk.

Java GC works very well, and it's a huge improvement over the "manual" method, because it almost completely eliminates memory leaks (if you really want a memory leak, you can find a way to make it happen).

Now, if you're talking about trying to apply GC to C code, it's an entirely different matter. C wasn't designed with GC in mind. The very fact that you can do MATH on pointers in C makes reliable GC nearly impossible, although any reasonable attempt would certainly be better than your assumption that something would "go scanning through memory looking for things that look like pointers." That would be horribly stupid. Better would be to have the compiler emit code that registers pointers with something that keeps track of them, but that's still a huge can of worms when you consider someone malloc'ing N bytes, storing a (void *), and then later assigning that value to a struct pointer.

No, I don't think GC in C is feasible.

A garbage collector for C and C++
http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Well, most VM implementations use an generative aproach, where fresh objects are kept in a smaller hot pool and aged out (nursery), expecting less traversal. It is not enough to keep the marks in a central location with pointers, since you have actually follow those pointers into the object and travers the graphs.

http://java.sun.com/products/hotspot/whitepaper.html#5d

Greetings
Bernd

eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Timothy Miller wrote:

|
|
| John Richard Moser wrote:
|
|>
|> THE GARBAGE COLLECTOR WANDERS AROUND IN THE ENTIRE HEAP, AND IN SOME
|> CASES IN OTHER PARTS OF RAM, LOOKING FOR WHAT LOOKS LIKE POINTERS TO
|> YOUR ALLOCATED DATA.
|>
|
| Whose GC does this?
|

http://www.iecc.com/gclist/GC-faq.html

## C-compatible garbage collectors know where pointers may generally be ## found (e.g., "bss", "data", and stack), and maintain heap data ## structures that allow them to quickly determine what bit patterns ## might be pointers. Pointers, of course, look like pointers, so this ## heuristic traces out all memory reachable through pointers. What ## isn't reached, is reclaimed.

This just sticks out in my face
| I get the impression that the Java VM, for instance, knows what [...]

blah blah java blah blah

Yeah Java was built around garbage collection, let's not talk about this; I was talking about C.

|
| There is anecdotal evidence that this approach sometimes can improve
| performance over "manual" freeing because freeing can be done in bulk.
|

Dude.

if (check_for_tons_of_crap_that_says_I_am_not_used(p)) free(p);

Yeah. It's a pain in the ass to check every time you turn around for conditions that indicate that p is unused. In some cases, it's a best effort; you can't always tell. I can believe that GC would be more passive; hell, if it's not, just slow the GC down a bit. Garbage collection doesn't make sure there's no allocated ram that's not in use; it only frees things it can determine as such.

| Java GC works very well, and it's a huge improvement over the "manual"

[...]

blah blah java blah blah

Everything is an improvement over manual mm.

|
| Now, if you're talking about trying to apply GC to C code, it's an
| entirely different matter.  C wasn't designed with GC in mind.  The very

[...huge paragraph that makes sense...]

Yeah my thoughts exactly.

|
| No, I don't think GC in C is feasible.

See above.

|

Incidently, I've compiled a list of pros/cons from legacy/refct/mm.

I'm going to point something out here though, about comparing these.

When you compare manual mm and reference counting, you're in the same
field: Both of these set up deterministic points in program flow where allocated blocks will be freed if it is determined that they are no longer in use. Both of these occur immediately when a specific body of code is finished with a block of memory.

With garbage collection, it's different. The garbage collector finds out on its own at some undefined point after the block is no longer needed that it can free it, and does so. The GC is in no way obligated to free the block as soon as it is no longer in use; it only does this when it discovers this. As such, a GC is not the same class of operation as the other two. You can show me a GC that imposes less overhead than the other two methods; and I can retune that same GC to use 99% of your CPU.

That being said, don't argue about the overhead of a GC, because it's completely managable.

Attached is my list of pros/cons of each system. It's just some scrap for data I'm collecting, not presentation material. -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFA9HX5hDd4aOud5P8RAjyjAJ9bOxGUoRzGg66dgLHSEC7z5yUScgCfdc6+ cPaxYGWDN4Tx5IFA3bJgFIA=
=n2yk
-----END PGP SIGNATURE-----

Manual
malloc() your ram manually
free() your memory manually

Pros:
High level of control
Autofreeing of temporary data is possible: Dump pointers to temporary data into a pool that is deallocated later, and is destructed immediately before deallocation by deallocating all held pointers; then destruct and deallocate the pool before leaving the code body

Cons:
Have to determine when not using something before free()ing it Can free stuff you're not done with easily
Can lose track of stuff without free()ing it easily

Con Caveats:
None

Reference Counting
Create objects holding your data
Retain those objects when using them
Release those objects when not using them

Pros:
Maintain high level of control over memory management
References are held within immediate code bodies such as companion functions, single functions, or objects; thus, when the end of the object's usefulness for that code is reached, it may be released.
Increased chance of properly freeing data: Companion function to that which allocated it releases it; atomic functions retain/release in their own right
Lower chances of freeing in-use data: Once all references to an object are gone, via releasing it, nobody can access it anymore anyway, and it is thus deallocated; threaded environments retain before splitting off into new thread to avoid race conditions of create-create_thread-release-retain-release, instead using create-retain-create_thread-release-release. Autoreleasing temporary data is possible: Add retained objects to the autorelease pool, which releases them for each time they're entered into it as it is destructed.

Cons:
Requires some level of object orientation, at least by encapsulating data into a structure with a reference count Minor overhead from the retain counting and locking around retain counts
True, permenant circular references between objects retaining a reference to eachother causes orphanage

Con Caveats:
It's not that much more complex to code with this
Overhead is arguable versus the other two methods' needed checks
Good coding will avoid circular references where one object won't normally be aware of and tell the other to let go of it, thus causing the mutual deallocation of both

Garbage Collection
malloc() your ram manually
The garbage collector determines when you aren't using it anymore

Pros:
Recovers from memory leaks, where data is unreachable and thus freeing it is harmless anyway Takes the job of freeing up ram off the programmer
Conservative garbage collectors usually don't free in-use data

Pro Caveats:
Freeing up memory when leaking doesn't make that memory any less important; if you lose critical data that you just can't get back (I.e. by clobbering a pointer), you simply lose it.
Taking the job of freing up ram off the programmer is significant versus manual memory management; however, it's a trivial task with reference counting, as even bugs caused by mistakes here are easily tracked down and fixed
Certain programming techniques like the XOR Linked LIst tirck or those which write pointers to files will have problems with the garbage collector; similar things may happen with object oriented programming in which a class member gets a thread and then references to the class are lost, depending on how the language implements things. Objects may even have a permenant reference to self, which makes them never free.

Cons:
Takes most control away from the programmer
Even conservative garbage collectors free up things still in use, especially in strange situations such as where the pointers to the data aren't where the GC expects them to be; or when they're mangled or encoded Minor overhead in the form of a second thread, or periodic pauses, depending on implementation
Collector may lag behind, allowing large numbers of small, temporary allocations to build into large amounts of used but unfreed memory
Not sane for Object Oriented Programming, unless it specifically can identify the language in use and its constructs

Con Caveats:
Control over memory management is usually a security blanket, although this is not always true
Conservative garbage collectors usually make the grade, although they do miss in many useful situations
Overhead is usually comparable to reference counting or explicite malloc()/free(), but grows with vm size (especially heap size)
Ram is usually cheap, unless you're wasting hundreds of megabytes from being in a long-running (3-4 seconds even) tight loop that allocates and frees ram repetedly Garbage collectors exist for C and C++, but they don't work for Objective-C for example; similarly, there are garbage-collected Objective-C objects using a specially made collector

Hi,
What does an array of size 1 mean? or maybe I might be putting it wrong, so here's the declaration -

struct option_state {
    int refcnt;
    int universe_count;
    int site_universe;
    int site_code_min;
    VOIDPTR universes[1];
};

(code from ISC DHCP sources includes/dhcpd.h)

What does universes[1] mean here?

Thanks.
-Anshu

Hi Anshuman,

Em Tue, 20 Jul 2004 12:47:27 -0400 "Anshuman S. Rawat" <[email protected]> screveu:

| Hi,
| What does an array of size 1 mean? or maybe I might be putting it wrong, so
| here's the declaration -
| 
| struct option_state {
|     int refcnt;
|     int universe_count;
|     int site_universe;
|     int site_code_min;
|     VOIDPTR universes[1];
| };
| 
| (code from ISC DHCP sources includes/dhcpd.h)
| 
| What does universes[1] mean here?

I think is best to ask for the author, seems to me it is not usual.

Luiz Fernando

It means an array of size one.

However, an array of size one at the end of a structure is often a clue that the structure is intended to be a "header" for a larger block of data, where the rest of the block is an array whose size isn't fixed at compile time.

Given the names of the fields, I would guess that the universe_count field holds the actual number of elements in the array.

C doesn't support variable-sized arrays directly (actually, C99 supports variable-sized arrays, but C89 doesn't). However, you can do something like:

	struct option_state *p;
	int i;

	p = malloc(sizeof(struct option_state) + (count-1) * sizeof(VOIDPTR));
	...
	p->universe_count = count;
	...
	for (i = 0; i < count; i++)
		p->universes[i] = ...;

Also, gcc supports zero-length arrays for exactly this purpose. The "Zero Length" node in the gcc Info file (under "C Extensions") says:

	Zero-length arrays are allowed in GNU C.  They are very useful as the
	last element of a structure which is really a header for a
	variable-length object:

	     struct line {
	       int length;
	       char contents[0];
	     };

	     struct line *thisline = (struct line *)
	       malloc (sizeof (struct line) + this_length);
	     thisline->length = this_length;

In practice, it's probably better to just use an array of length one (which will work with all compilers) and just subtract one when computing the size.

Glynn Clements <[email protected]>

Am Di, 2004-07-20 um 18.47 schrieb Anshuman S. Rawat:

Came across this:
http://www.eskimo.com/~scs/C-faq/q2.6.html