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.