34 ms·

Nice article. What I didn't understand: How does a conservative GC without type information know where the references are in an object? E.g. given this object:

Nice article. What I didn't understand: How does a conservative GC without type information know where the references are in an object? E.g. given this object: struct { double a; // 64 bit short b // 16 bit int c, d; // 32+32 bit FooPtr e; // 64 bit int f; // 32 bit BarPtr g; // 64 bit } Does it assume that all fields are aligned to 64 bit boundaries? Does it potentially consider a double to be a pointer? And how does it know where to stop looking for references without knowing the size of the object?

alexrp 14y ago
I'll start with your last question: It does know the size of objects - this size is passed to the GC when you allocate memory from it. Root ranges (such as the stack, global variables, TLS areas, etc) also all have a static size. (Not strictly true - some runtimes have dynamically growing stacks, but the GC knows the size regardless.) Most garbage collectors assume pointers to be aligned on a word boundary; that is on a 4-byte boundary on 32-bit machines and an 8-byte boundary on 64-bit machines. This is a reasonable assumption because accessing pointers that are not word-aligned is extremely slow on most architectures. It does not care how fields that don't contain pointers are aligned because their contents are irrelevant (so this translates to the compiler being able to pack some fields together without worrying about breaking the GC). So, a conservative GC will simply scan over every word in an object and interpret it as a potential pointer, regardless of what it actually is. So yes - even a double will be considered a pointer.
- mseepgood 14y ago
  Thanks alexrp and digitalinfinity for your replies!
digitalinfinity 14y ago
It can't make that assumption- in a conservative GC, any pointer sized field in an object could be a pointer. So assuming you're on a 32 bit machine, in the above example, the double would look like 2 pointers to the GC. One way of dealing with this is, the GC keeps a set of all the address ranges that belong to its objects (these are the only objects that could be garbage collected). Then, when it sees what could be a pointer, it'll first look up whether this "maybe pointer" actually belongs to it's address range, and only if it does will it add it to the mark stack for further scanning. In terms of how does it know when to stop looking for references, actually, the GC will know the object size for any objects that it has allocated, so it knows when to stop scanning it's own object. For objects that it hasn't given out, it doesn't matter since it won't scan those. And for the stack, it'll just scan the entire stack looking for pointers to it's own objects.
rayiner 14y ago
A conservative GC requires the application to obey certain "typical" behaviors. One of those behaviors is "natural" alignment of structures. Most C compilers will align pointers in structures to the word size of the architecture, inserting padding if necessary. In your example, padding would be inserted between "b" and "c" to align "c" to 32-bits and between "f" and "g" to align "g" to 64-bits (assuming this is a 64-bit machine). So the GC can scan an object a word at a time and be sure it'll hit all pointers. Note that using compiler directives that pack structures as tightly as possible, ignoring natural alignments, can break this assumption. As for your other questions, remember that a conservative GC manages objects allocated through it, not just random objects in the system. It can use allocator metadata to keep track of where objects start and how long they are.* It aligns objects to some multiple of the word size, and can ignore any bit pattern that doesn't point to some multiple of 4 or 8 bytes. It also knows the extents of its own heap. As its scanning pointers, it does some checks to see if a particular bit-pattern points outside of the heap or does not point to the beginning of an object. If a possible pointer passes all of these tests, it definitely points to an object. It might not actually be a real pointer, but the target is actually an object managed by the GC. On a 64-bit machine, it's actually fairly rare for a random "int" or "double" to be mistaken for a pointer. Most "ints" are small integers, and on a 64-bit machine the heap is almost always allocated above 4GB. Similarly, the odds of a 64-bit double bit pattern pointing inside the heap out of all those exabytes of heap is unlikely. *) This is similar to how a malloc implementation might use allocator metadata to know how big a chunk is for a free() call.

alexrp 14y ago

I'll start with your last question: It does know the size of objects - this size is passed to the GC when you allocate memory from it. Root ranges (such as the stack, global variables, TLS areas, etc) also all have a static size. (Not strictly true - some runtimes have dynamically growing stacks, but the GC knows the size regardless.) Most garbage collectors assume pointers to be aligned on a word boundary; that is on a 4-byte boundary on 32-bit machines and an 8-byte boundary on 64-bit machines. This is a reasonable assumption because accessing pointers that are not word-aligned is extremely slow on most architectures. It does not care how fields that don't contain pointers are aligned because their contents are irrelevant (so this translates to the compiler being able to pack some fields together without worrying about breaking the GC). So, a conservative GC will simply scan over every word in an object and interpret it as a potential pointer, regardless of what it actually is. So yes - even a double will be considered a pointer.

mseepgood 14y ago
Thanks alexrp and digitalinfinity for your replies!

digitalinfinity 14y ago

It can't make that assumption- in a conservative GC, any pointer sized field in an object could be a pointer. So assuming you're on a 32 bit machine, in the above example, the double would look like 2 pointers to the GC. One way of dealing with this is, the GC keeps a set of all the address ranges that belong to its objects (these are the only objects that could be garbage collected). Then, when it sees what could be a pointer, it'll first look up whether this "maybe pointer" actually belongs to it's address range, and only if it does will it add it to the mark stack for further scanning. In terms of how does it know when to stop looking for references, actually, the GC will know the object size for any objects that it has allocated, so it knows when to stop scanning it's own object. For objects that it hasn't given out, it doesn't matter since it won't scan those. And for the stack, it'll just scan the entire stack looking for pointers to it's own objects.

rayiner 14y ago

A conservative GC requires the application to obey certain "typical" behaviors. One of those behaviors is "natural" alignment of structures. Most C compilers will align pointers in structures to the word size of the architecture, inserting padding if necessary. In your example, padding would be inserted between "b" and "c" to align "c" to 32-bits and between "f" and "g" to align "g" to 64-bits (assuming this is a 64-bit machine). So the GC can scan an object a word at a time and be sure it'll hit all pointers. Note that using compiler directives that pack structures as tightly as possible, ignoring natural alignments, can break this assumption. As for your other questions, remember that a conservative GC manages objects allocated through it, not just random objects in the system. It can use allocator metadata to keep track of where objects start and how long they are.* It aligns objects to some multiple of the word size, and can ignore any bit pattern that doesn't point to some multiple of 4 or 8 bytes. It also knows the extents of its own heap. As its scanning pointers, it does some checks to see if a particular bit-pattern points outside of the heap or does not point to the beginning of an object. If a possible pointer passes all of these tests, it definitely points to an object. It might not actually be a real pointer, but the target is actually an object managed by the GC. On a 64-bit machine, it's actually fairly rare for a random "int" or "double" to be mistaken for a pointer. Most "ints" are small integers, and on a 64-bit machine the heap is almost always allocated above 4GB. Similarly, the odds of a 64-bit double bit pattern pointing inside the heap out of all those exabytes of heap is unlikely. *) This is similar to how a malloc implementation might use allocator metadata to know how big a chunk is for a free() call.