Garbage collection scheme

Hello,
I would like to receive opinions on a garbage collection scheme.

It has three parameters:

* Free space ratio - basically controls how much memory the program should be able to allocate at any time
* Release memory ratio - allows to release memory when the free space is very large
* Min allowed GC interval - how often is the GC allowed to do a collection

Data structures -

* A bitmap for allocated slots
* A "counts" array for old generation inbound references (4bit/object?)

Old generation and new generation are stored at opposite ends of the heap.

The reference counts saturate, which means that when they reach a certain value (e.g. 15) they can no longer increase or decrease.

# Initialisation

Request some memory from the memory manager (e.g. MMU), preferably enough to satisfy the free memory ratio after storing the GC roots.

Set the bitmap and counts to zero.

Store the GC roots in old generation (presumably lowest addresses). Mark the corresponding slots as allocated in the bitmap and set the corresponding reference counts to 1.

# Short GC

If the distance between the closest allocation in old generation and in new generation is more than the free space ratio, do nothing.

Else:

* Starting from the GC roots, look for references to new generation objects and move them to old generation
 Housekeeping: mark the moved objects as unallocated in new generation and set a redirection to the new location, mark as allocated in old generation and increase the reference count of the object + all its direct references which are already in old generation.

* Clear the remaining allocation bits in new generation area

* If free memory in the heap is more than the memory release ratio, release memory until it no longer is

# Long GC

Starting from the GC roots, recalculate the reference counts for old generation objects (don’t count new generation references).

* If a reference count reaches 0, move the object to new generation
 Housekeeping: mark the moved object as unallocated in old generation and set a redirection to the new location, decrease the reference count of all its direct references which are in old generation.

Compact the heap (old generation only).

Perform a short GC.

# Memory allocation

Try to find a suitable free block in the new generation area.

If there is no space, request some memory from the memory manager to hold the object, preferably enough to satisfy the free space ratio after the next short GC. Allocate the object in the new area.

Optional, heuristic may not work:
If an allocation is possible but will cause the free space ratio to be breached, then allocate at the threshold of old generation area so the object will not need to be moved if it is still live at next collection.

# Errors

If the memory manager fails to provide enough allocation memory for the object we are in trouble. The allocation cannot go ahead until something is done.

The following will be performed:

* Long GC

* Try allocating again, fail if it doesn’t work

* Enable low memory mode

# Low memory mode

* If the distance between generations is less than the free space ratio then run a long GC

* Otherwise run a short GC (which means collection happens at the min allowed interval)

* If the free memory after GC is more than the memory release ratio, exit low memory mode

—

My only concern is the memory required to store the bitmaps and the reference counts. The rest looks straightforward (the scheme probably has already a name?)

Thank you for reading,

— Denis.

Received on Tuesday, 22 November 2022 08:03:59 UTC