Re: [boost] portable precise garbage collector for C++

From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2007-09-18 10:22:19

Larry Evans wrote:
> On 09/17/07 13:31, Achilleas Margaritis wrote:
>> O/H Larry Evans έγραψε:
>>> On 09/17/07 03:30, Achilleas Margaritis wrote:
>>>> Larry Evans wrote:
>>>>> On 09/16/07 16:56, Achilleas Margaritis wrote:
>>> [snip]
>>>>> How does this collector determine the location of pointers on the stack
>>>>> and within the heap?
>>>> An internal bit map is used as a pointer database. Each bit represents 
>>>> one pointer location in memory.
> [snip]
> I'm still fuzzy about how this collector works.  On:
> 
>    http://www.hpl.hp.com/personal/Hans_Boehm/gc/complexity.html
> 
> there's:
> 
> A mark-sweep garbage collector traverses all reachable objects in the 
> heap by following pointers beginning with the "roots", i.e. pointers 
> stored in statically allocated or stack allocated program variables. All 
> such reachable objects are marked. A sweep over the entire heap is the 
> performed to restore unmarked objects to a free list, so they can be 
> reallocated.
> 
> How does this collector determine whether a pointer in the database
> is a root pointer?  Wouldn't that method have to be non-portable
> or at least dispatch on the OS type to the appropriate method?
> 

The collector keeps internally a map of memory page information 
structure allocated on demand from the heap. Each page information 
structure contains:

1) a bit map of pointers.
2) a heap reference count.

When a heap block is allocated on a page, the page's reference count is 
increased. When a heap block is freed, the page's reference count is 
decreased.

When a pointer is created, the bit that corresponds to the pointer's 
address is set. When a pointer is destroyed, the same bit is reset.

When we scan for root pointers, we look at the heap reference count of 
the page: if it is greater than 0, the page contains heap data, and 
therefore we do not check if the page has any pointers, because even if 
it does, it is not a root page.

The whole mechanism is based on the fact that heap, global data and 
thread data can not be on the same page.