Garbage collector

Overview

Ruruby has a simple mark-and-sweep, precise, non-moving garbage collector. Currently, the GC only handles RValue structs which represent objects in Ruby world. A RValue struct is stored in a 64-byte slot, and a single heap page (256KB) consists of 64 * 63 slots and a bitmap area (64bit * 63) for marking living objects.
The GC consists of two components: allocator and collector.

Allocator

The allocator is a mixed type of a so-called bump allocator and a free list allocator, which allocates RValue according to the VM's request. If there are some free slots in the free list, it passes them on, and if there are no free slot, the allocator simply advances the pointer on the current page for allocation.

Collector

When the collector is invoked by VM, at first, it marks all the objects that can be traced from the root. The root actually means constants(in most cases, bound to Class objects), global variables, local variables in each execution contexts. Next, it searches unmarked (=dead) objects by scanning marking bitmap, and connects them to the free list. Since the current GC is non-moving, fragmentation of heap pages occurs as the program executes, but if all objects in a certain page were 'dead', the entire page is retrieved and prepared for later allocation.

Development

As Ruby has, ruruby has a builtin class, named 'GC' which provides some methods to control GC and collect information.

irb:0> GC.count
=> 0
irb:0> GC.stat
=> {:total_allocated_objects=>38, :count=>0, :heap_allocated_pages=>1, :heap_free_slots=>0, :heap_live_slots=>0}
irb:0> a = []; 100000.times do |x| a << x.to_s end
=> 100000
irb:0> GC.stat
=> {:total_allocated_objects=>100040, :count=>24, :heap_allocated_pages=>25, :heap_free_slots=>0, :heap_live_slots=>96705}
irb:0> a = nil
=> nil
irb:0> GC.start
=> nil
irb:0> GC.stat
=> {:total_allocated_objects=>100041, :count=>25, :heap_allocated_pages=>2, :heap_free_slots=>7266, :heap_live_slots=>39}
irb:0> GC.print_mark
fffffffffe000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 

0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 

GC Info----------------------------------------------------------------------------
active pages: 2 free pages:23
free list:7265 allocated:100042  used in current page:3273
=> nil