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.