• Global block manager talks to the OS
• Thread-local block manager talks to the global
• Allocation bump-allocates from the next block that can easily accomodate; or buys a new block to handle overflow
• Blocks are divided in to "lines"
• When marking and sweeping: only the entire line is marked or swept. Small objects within all mark the same line.
• Blocks might be "evacuated": copy any live lines to a new bucket and return the old bucket to storage.
• Blocks might be "recycled": move the cursor back to the start, but beware not to allocate atop lines in use.

Allocation relies on a basic policy: only ever move the cursor forward (except when recycling), do not move over a line that is live, and do not skip over *too many* bytes. There is a threshold how much you can waste before just going to the next bucket and trying there.

I previously thought allocations always got an entire line to themselves. This does not seem to be the case? The cursor hands out memory which might cross multiple lines.

Optimization

An exact collector checks every single object for a size and ensures all objects are marked precisely.

A conservative collector requires objects be marked as small or medium. A small object is one which is less than one line's size (so it may span at most two lines) while a medium object has another size. Small objects cause the line and next line to be marked. Medium objects must be checked precisely.

definitions and stuff

Block: a large unit of measure, defaults to 32kb but is a tunable. Blocks are also the minimum shareable unit; threads share a whole block or none of the block.

Line: a subunit of measure for a block, defaults to 128 bytes but is a tunable.

Pinned: mark a line such that it cannot be moved.

Forwarded: mark a line with a pointer to its new location. This line has been evacuated from its original block and a second mark pass must replace all references to a forwarded object with its new location.

Evacuation: when a line is moved to a new block during collection.

Bump allocation: a cursor exists in a block and is moved forward to fulfill allocation requests. The cursor may skip over a line if it is already occupied (as happens if a block is recycled.)

Medium object: allocation larger than a line.

Large object: allocation larger than a block.

Conservative marking: use one bit for a line header to mark the entire line as occupied. Used for smol objects.

Exact marking: store the number of lines used somewhere, to quickly mark medium and larger objects.

Overflow allocation: a secondary allocator handles objects when they are larger than the bump allocator can provide. Overflow allocates from a secondary block reserved for larger objects which already failed the first allocation attempt. It will pull a new global block if needed.

Recycled block: a block that has been mark&swept and for some reason objects remain within it. These leave "holes" which have to be worked around, such as by falling back to an overflow block to allocate bigger items.

Blocks

A global block manager claims and returns full sized blocks from the OS' memory services. This is a synchronized, global service.

Thread-local block managers claim and return blocks from the global block manager.

Thread-local blocks belong to those threads and so there is no contention with these.

Line and Block tuning

Line/block sizes are for space and performance tradeoffs.