The general plan is to have the compiler identify the data structures that are static roots, and then have the linker use that information to generate a global table of all roots. The address of this table is then passed to the garbage collector at initialization time. At the beginning of each collection, the garbage collector will trace all of the static roots, so that any object referred to will be considered live.
Each static root contains two pieces of information: A pointer to the static data structure to be traced, and a pointer to the trace table for that data structure. The reason we need the trace table is that not all data types in Tart have embedded type information, for some data types the information about pointer offsets has to be supplied externally.
Tart's code generator has a getTraceTable(Type * type) function which takes a type, and returns the trace table for that type - or NULL if that type has no traceable references embedded in it. Thus, each time the compiler emits a static data structure, it gets the trace table, and if non-NULL, adds it to the list of roots for that module.
Actually, there's an additional optimization that can be applied: If a static data structure is immutable, then there's no need to trace it, since the only thing it can point to are other static data structures, which will themselves be static roots.
The next question is how to communicate the information about static roots from the compiler to the linker. The simple solution would be to simply create an array of pointers to those roots, however this solution has a problem: By referring to global variables directly, you prevent the linker from removing dead globals. I asked about this problem on the llvm-dev mailing list, and the suggestion I got was to instead create a list containing the names of the global variables. The idea is that you would run the dead global elimination pass, and then use the list of names to see which roots remained.
Of course, for this to work, every static root has to have a name, and that name has to be globally unique after the modules have all been combined into one large module. Normally LLVM deals with name collisions either by merging or renaming the symbol, depending on what that symbol's linkage type is, but we can't allow these particular symbols to be renamed, since the name would no longer match the string. So much of the work that I did over the weekend was making sure that each static root had a proper name.
One issue that I haven't quite worked out yet: How to deal with the linker's dead global elimination pass eliminating trace tables. We only want to keep the trace tables for the globals that didn't get eliminated during the dead global elimination pass. Since the globals themselves don't point to their trace tables, we need a way to prevent the trace tables from being prematurely removed, but afterwards we only want to keep the tables for globals that didn't get eliminated.
One other thing I need to figure out is how to handle roots that are in read-only memory. In LLVM, when you create a global variable, there's a boolean parameter that you can pass in that specifies whether this global is a constant. If set to true, it puts the global in read-only memory, so that any attempt to mutate it will generate a fault. I normally set this flag to true for any static global that has no mutable fields.
However, each object has a hidden integer field called __gcstate which is intended for use by the garbage collector. The meaning of this field is unspecified, it's up to the various garbage collector implementations to decide what data they need to store on a per-object basis. A typical example might be a "marked" bit to indicate that the object has been traced. However, garbage collectors will need some way to detect objects in read-only memory and refrain from writing to the __gcstate field of those objects. Probably the simplest solution is to assume that all objects whose address is outside of the collector's memory pool should not be modified. That means that we'll need to keep a record of which objects have been traced in some sort of auxiliary data structure.
(This makes me wonder if it's even worth having a __gcstate field, since the collector can easily create any auxiliary data fields it wants by prefix them to the beginning of the object -- although there are some alignment benefits to having the field be within the object, especially on 32-bit architectures.)
Another possibility is to have the __gcstate of all readonly objects always be zero, and the __gcstate of any objects allocated by the garbage collector be non-zero.
No comments:
Post a Comment