Finding Garbage Collection Roots in C

Question

I am trying to implement a simple label and collect the garbage collector in C. The first step of the algorithm is to find the roots. So my question is: how can I find the roots in a C program?

In programs using malloc, I will use a custom allocator. This custom allocator is all that is called from a C program, and can be custom init ().

How does the garbage collector know that all pointers (roots) are in the program? Also, given a custom type pointer, how does it get all the pointers inside that?

For example, if there is a pointer p pointing to a list of classes that has another pointer inside it, say q. How does the garbage collector know about this so that he can tag it?

Update: how about sending all the names and types of pointers to the GC when it is initialized? Similarly, a structure of various types can also be sent so that the GC can cross the tree. Is that even a reasonable idea, or am I just losing my mind?

Answer 1

First, C garbage collectors, without extensive compiler and OS support, should be conservative because you cannot distinguish between a legal pointer and an integer that has a value similar to a pointer. And even conservative garbage collectors are hard to implement. Like, very hard. And often you need to limit the language in order to get something acceptable: for example, it would be impossible to correctly collect the memory if the pointers are hidden or confused. If you allocate 100 bytes and keep the pointer to the tenth byte of the allocation, your GC is unlikely to understand that you still need a block, since it will not see a link to the beginning. Another very important limitation to control is memory alignment: if the pointers can be in unchanged memory, your collector can slow down 10 times or worse.

To find the roots, you need to know where your stacks begin and where your stacks end. Pay attention to the plural form: each thread has its own stack, and you may need to consider this, depending on your goals. To find out where the stack starts without going into platform-specific details (which I probably couldn't have provided anyway), you can use the build code inside the main function of the current thread (just main ( esp on x86, rsp on x86_64 to name only these two.) Gcc and clang support a language extension that allows you to constantly assign a variable to a register, which will make it easier for you:

 register void* stack asm("esp"); // replace esp with the name of your stack reg 

( register is a standard language keyword, which in most cases is ignored by compilers today, but in combination with asm("register_name") it allows you to do some unpleasant things.)

So that you do not forget the important roots, you must defer the actual operation of the main function to another. (On x86 platforms, you can also request ebp / rbp base stack frame pointers and still do your actual work in the main function.)

 int main(int argc, const char** argv, const char** envp) { register void* stack asm("esp"); // put stack somewhere return do_main(argc, argv, envp); } 

Once you enter your GC for collection, you need to request the current stack pointer for the thread that you interrupted. To do this, you will need special requirements for the development and / or platform (although if you get something to be executed in one thread, the technique will work above).

Now begins the real hunt for the roots. The good news: most ABIs will require alignment of the stack frames on the border larger than the size of the pointer, which means that if you trust every pointer in the aligned memory, you can treat your entire stack as intptr_t* and check if any template inside looks like any of your managed pointers.

Obviously, there are other roots. Global variables can (theoretically) be roots, and fields within structures can also be roots. Registers can also have pointers to objects. You need to take into account global variables that can be rooted separately (or disallow it at all, which, in my opinion, is not a bad idea), because automatic detection of these will be difficult (at least I don’t know how to do this on any platform )

These roots can lead to links to a bunch where things can go awry if you don't care.

Since not all platforms provide introspection of malloc (as far as I know), you need to implement the concept of scanned memory, that is, memory that your GC knows about. He must know at least the address and size of each such distribution. When you get a link to one of them, you just look at them for pointers, as well as for the stack. (This means that you must ensure that your pointers are aligned. This is usually the case if you let your compiler do the work, but you still need to be careful when using third-party APIs).

It also means that you cannot put references to collective memory in places where the GC cannot reach it. And this is where it hurts the most and where you need to be too careful. Otherwise, if your platform supports malloc introspection, you can easily specify the size of each distribution that you get a pointer to, and make sure that you do not overfill it.

It just scratches the surface of the theme. Garbage collectors are extremely complex, even if single-threaded. When you add streams to the mix, you are introducing a whole new world.

Apple introduced such a conservative GC for the Objective-C language and named it libauto. They discovered it, along with a good piece of low-level Mac OS X technology, and you can find the source here .

I can only quote Hot Licks here: good luck!

---

Well, before I go any further, I forgot something very important: optimizing the compiler can break the GC. If your compiler does not know about your GC, it can very well never put certain roots on the stack (only dealing with them in the registries), and you are going to skip them. This is not too problematic for single-threaded programs if you can check registers, but again, there is a huge mess for multi-threaded programs.

Also, be very careful about interrupting distributions: you have to make sure that your GC cannot hit while you are returning a new pointer, because it can collect it right before it is assigned to the root file, and when your program resumes it is assigned would a new dangling pointer to your program.

And here is the update for editing:

Update: how about sending all the names and types of pointers to the GC when I start it? Similarly, a structure of various types can also be sent so that the GC can cross the tree. Is that even a reasonable idea or am I just losing my mind?

I assume that you could allocate our memory and then register it in the GC to say that it should be a managed resource. This will solve the interrupt problem. But then be careful what you send to third-party libraries, because if they link to it, your GC may not be able to detect it, because they will not register their data structures with your GC.

And you probably cannot do this with the roots in the stack.

Answer 2

Roots are mostly static and automatic object pointers. Static pointers will be linked inside load modules. Auto pointers should be found when scanning stack frames. Of course, you don’t know where in the frames of the stack there are automatic pointers.

Once you have the roots, you need to scan the objects and find all the pointers inside them. (This will include pointer arrays.) To do this, you need to identify the class object and somehow extract information about the places of the pointers from it. Of course, in C, many objects are not virtual and do not have a class pointer inside them.

Good luck

Added: One way that can vaguely make your quest possible is a "conservative" garbage collection. Since you intend to have your own dispenser, you can (somehow) track the sizes and locations of the location so that you can select any piece of the size of the pointer from the repository and ask: “Could this be a pointer to one of my objects?” Of course, you may not know exactly, since random data may look like a pointer to one of your objects, but you can scan a piece of storage through this mechanism (for example, a frame in the call stack, or a separate object) and identify all possible objects which he can decide.

With a conservative collector, you cannot safely move objects / compaction (where you change the pointers to objects when moving them), because you can accidentally change “random” data that looks like a pointer to an object, but actually represents meaningful data for some expression . But you can identify unused objects and free up the space that they occupy for reuse. With the right design, it can have a very effective non-sealing GC.

(However, if your version of C allows you to scan for ambiguous pointers, this can be very slow since you will have to try all the byte alignment options.)