Status Report for GC through Self-Introspection through DWARF

DWARF makes finding the functions executing based on the given program counter fairly painless. I was able to get a call stack, and figure out the variables inside the function and the associated types.

Actually getting the value of the pointers requires running a simple state machine. There are a few locations that a variable could be in, and all of the relevant ones require a degree of stack walking.

 The first location is in the function call frame. In this case, the DWARF opcode DW_OP_fbreg is used with the first argument being the offset from the top of the call stack that the variable is placed in. After trying to use the stack values retrieved from the backtrace call, I realized that a bit of refactoring was necessary to get this information.

Alternatively, the variable can be in a register. These values can be found without significant pain because the C calling convention stipulates that they'll be placed on the stack before a function call.

Other possible locations refer almost entirely to types of static values, which are not relevant to us because values handed back by our malloc will be determined at runtime and thus will never be inserted into the binary.

Where that leaves me is that after I write the requisite stack walking helper functions, I'll be able to read the values stored in the roots and know their types.

Moving forward, I plan to recursively type the heap. All of the necessary type information is easily accessible in the DWARF symbols. This would allow an infrequent mark-compact phase for the collector.

In all reality, the act of collecting type information is probably slower than simply doing a linear sweep of the stack and comparing ranges. Where I believe that this change can have a strong performance benefit is that the type information can stick around in the heap cells. This prevents needless traversal and also allows for compacting subsets or the entirety of the heap.
 After the root scanning is working, I will definitely seek a way to memoize the offset/type finding for a given function.

Without definite knowledge that a value is a pointer, it is not safe to overwrite the value. This prevents moving and dictates the mark-sweep/freelist style of collector. Accurate heap information could possibly allow for an alternative collector for C with a less naive strategy than freelist allocation with mark-sweep. Freelist allocation is much too slow for a rapidly allocating language.

Furthermore, segmentation in mark-sweep allocators in very frequently allocating programs can be unacceptable in many cases. I was recently told the tale of a student project to write a game engine in the D language. It was selected specifically because collection was hoped to speed development time. The very frequent allocation of short-lived and variably-sized objects led to quick memory exhaustion and death by the OOM daemon. This project was abandoned.

Because the BDW collector breaks a page into fixed-size chunks, and has a different freelist for each chunk size, a program allocating very variable sizes of memory could easily take dramatically more memory than needed. I believe that this might be worth addressing separately.
While the generational paradigm is desirable, the relative costs of typing could complicate things. With infrequent use of the precise root-typing walking, we'll know the types of the older generation, but not of the younger. On the other hand, the recording of inter-generational pointers could include information about the type of the object pointed to. Combined with a smaller region into which false roots could point and the stipulation that major collections will always type the roots, a generational/bump-pointer scheme might fit partially-conservative collection well.

This is a stretch goal, but one that I will definitely take up after the end of the semester if not accomplished before then. Creation of a generic garbage collector would allow for the early stages of language prototyping to avoid having to hand-write a collector in order to reach an alpha milestone. The LLVM is frequently used for backend output for new languages, and support for DWARF die creation in llvm appears fairly well polished. Writing debugging support and getting memory management "for free" would be great for prototyping.