Understanding the current GC, part II
by Leandro Lucarella on 2009- 04- 06 00:00 (updated on 2009- 04- 15 04:10)- with 0 comment(s)
Back to the analysis of the current GC implementation, in this post I will focus on the Gcx object structure and methods.
Gcx attributes
- Root set
- roots (nroots, rootdim)
- An array of root pointers.
- ranges (nranges, rangedim)
- An array of root ranges (a range of memory that should be scanned for root pointers).
- Beginning of the stack (stackBottom)
- A pointer to the stack bottom (assuming it grows up).
- Pool table (pooltable, npools)
- An array of pointers to Pool objects (the heap itself).
- Free list (bucket)
- A free list for each Bins size.
- Internal state
- anychanges
- Set if the marking of a range has actually marked anything (and then using in the full collection.
- inited
- Set if the GC has been initialized.
- Behaviour changing attributes
- noStack
- Don't scan the stack if activated.
- log
- Turn on logging if activated.
- disabled
- Don't run the collector if activated.
- Cache (for optimizations and such)
- p_cache, size_cache
- Querying the size of a heap object is an expensive task. This caches the last query as an optimization.
- minAddr, maxAddr
- All the heap is in this range. It's used as an optimization when looking if a pointer can be pointing into the heap (if the pointer is not in this range it can be safely discarded, but if it's in the range, a full search in the pooltable should be done).
Gcx main methods
- initialize()
- Initialization, set the Gcx object attributes to 0, except for the stackBottom (which is set to the address of a dummy local variable, this works because this function is one of the first functions called by the runtime) and the inited flag, that is set to 1. The log is initialized too.
- Dtor()
- Destruction, free all the memory.
- Root set manipulation
- addRoot(p), removeRoot(p), rootIter(dg)
- Add, remove and iterate over single root pointers.
- addRange(pbot, ptop), remove range(pbot), rangeIter(dg)
- Add, remove and iterate over root pointer ranges. This methods are almost the same as the previous ones, so the code duplication here can be improved here.
- Flags manipulation
Each Bin has some flags associated (as explained before). With this functions the user can manipulate some of them:
- FINALIZE: this pool has destructors to be called (final flag)
- NO_SCAN: this pool should not be scanned for pointers (noscan flag)
- NO_MOVE: this pool shouldn't be moved (not implemented)
- getBits(pool, biti)
- Get which of the flags specified by biti are set for the pool Pool.
- setBits(pool, mask)
- Set the flags specified by mask for the pool Pool.
- clrBits(pool, mask)
- Clear the flags specified by mask for the pool Pool.
- Searching
- findPool(p)
- Find the Pool object that pointer p is in.
- findBase(p)
- Find the base address of block containing pointer p.
- findSize(p)
- Find the size of the block pointed by p.
- getInfo(p)
- Get information on the pointer p. The information is composed of: base (the base address of the block), size (the size of the block) and attr (the flags associated to the block, as shown in Flag manipulation). This information is returned as a structure called the BlkInfo.
- findBin(size)
- Compute Bins (bin size) for an object of size size.
- Heap (pagetable) manipulation
The pooltable is kept sorted always.
- reserve(size)
- Allocate a new Pool of at least size bytes.
- minimize()
- Minimizes physical memory usage by returning free pools to the OS.
- bigAlloc(size)
- Allocate a chunk of memory that is larger than a page.
- newPool(npages)
- Allocate a new Pool with at least npages pages in it.
- allocPage(bin)
- Allocate a page of bin size.
- Collection
- mark(pbot, ptop)
This is the mark phase. It search a range of memory values and mark any pointers into the GC heap. The mark bit is set, and if the noscan bit is unset, the scan bit is activated (indicating that the block should be scanned for pointers, equivalent to coloring the cell grey in the tri-colour abstraction).
The mark phase is not recursive (nor a mark stack is used). Only the passed range is marked, pointers are not followed here.
That's why the anychanges flag is used, if anything has got marked, anychanges is set to true. The marking phase is done iteratively until no more blocks are marked, in which case we can safely assume that we marked all the live blocks.
- fullcollectshell()
- The purpose of the shell is to ensure all the registers get put on the stack so they'll be scanned.
- fullcollect(stackTop)
Collect memory that is not referenced by the program. The algorithm is something like this:
- Stop the world (all other threads)
- Clear all the mark/scan bits in the pools
- Manually mark each free list entry (bucket), so it doesn't get scanned
- mark() the static data
- mark() stacks and registers for each paused thread
- mark() the root set (both roots and ranges)
- mark() the heap iteratively until no more changes are detected (anychanges is false)
- Start the world (all other threads)
- Sweep (free up everything not marked)
- Free complete pages, rebuild free list
Note
This is a very summarized version of the algorithm, what I could understand from a quick look into the code, which is pretty much undocumented. A deeper analysis should be done in a following post.