A hack of Bitmap Marking GC for CRuby 2.0

Prerequisite knowledge

• "What is Ruby Enterprise Edition?" - Frequently Asked Questions — Ruby Enterprise Edition
• InfoQ: Bitmap Marking GC for Ruby Improves Memory Usage

How to find for the bitmap corresponding to the object

Find processing of the bitmap is important to GC, since it's frequently used when mark phase. So, if the find processing is slow, GC will become slow as well.
The structure of the heap is as follows.

How do you find the bitmap corresponding to the object?
In REE's GC, they adopted the liner search approach to find the heap slot which has target object (I don't know detail of implementation now. I'm sorry if I'm wrong). This approach is good for CRuby 1.8. However, it's not good for CRuby 1.9 or later, because the structure of the heap was changed. Therefore, in CRuby after 1.9, it was not committed.

A hack by the alignment approach

I aligned a heap block at 16KB (1<<14) in CRuby2.0. So, we can calculate the top address of the heap block which has the target object as follows.

(object addr) & (~((1<<14)-1)) = top addr of the heap block

As fllows, if the top of heap block has the bitmap address, we can find it so quickly from the object address.

I used posix_memalign() or some functions for alignment. You can refer to aligned_malloc() in gc.c if you are interested: https://github.com/ruby/ruby/blob/trunk/gc.c#L1089