Nitro's Garbage Collector

The remaining piece in Apple's Nitro (Formerly SquirrelFish) is the garbage collector. Within the past month or two, I think the SquirrelFish team moved from a reference counting to a conservative mark-and-sweep GC with free lists . Prior to every allocation of an object, Nitro checks to see if there is enough space for a new object. If there is no longer any space, it begins to mark then sweep the heap. There are two heaps: the primary and number heap. The primary heap is for JavaScript objects. The number heap looks like its for numbers. The mark phase touches both heaps while the sweeping is done independently for each heap.

The primary and number heap are instances of the CollectorHeap. The CollectorHeap contains a list of memory blocks currently being used in addition to some metadata such as the number of blocks used, where the next free block is, and how many objects are currently live. The list of blocks are of type CollectorBlock. The CollectorBlock points a CollectorCell which finally stores JsCell objects. JsCells wrap around all objects and values. One thing to note is that for the number heap, the amount of memory each cell has is halved.

Collector.h
struct CollectorHeap {
CollectorBlock** blocks;
};

class CollectorBlock {
public:
CollectorCell cells[CELLS_PER_BLOCK]; // CELLS_PER_BLOCK = 2031
CollectorCell* freeList;
Heap* heap;
};

struct CollectorCell {
union {
double memory[CELL_ARRAY_LENGTH]; // CELL_ARRAY_LENGTH = 4
struct {
ptrdiff_t next;
} freeCell;
} u;
};


The overall algorithm to mark/sweep seems pretty standard. When Nitro enters the sweep phase, it recursively scans and marks all live objects starting from the root set. The marking includes objects in both the primary and number heaps. Sweeping occurs first on the primary, then number heap. Nitro iterates over each CollectorBlock, looking at all the cells in each block. When the object in a CollectorCell is considered garbage, that cell is added to the list of free cells. Thus the GC does not copy or compact anything. Everything is maintained in a free list. Finally, allocating space for a new object is done by following a pointer to the next free space.

Collector.cpp
// find a free spot in the block and detach it from the free list
Cell* newCell = targetBlock->freeList;

// "next" field is a cell offset -- 0 means next cell, so a zeroed block is already initialized
targetBlock->freeList = (newCell + 1) + newCell->u.freeCell.next;

// Allocation for the new object
return newCell;