[boost] more detail on root_ptr method (was Re: portable precise garbage collector for C++

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-09-20 10:23:19

On 09/18/07 09:22, Achilleas Margaritis wrote:
 > Larry Evans wrote:
[snip]
 >> 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.

At first I thought, "make perfect sense", then I thought "if a page is
on the heap, it remains there; so, why not use a bitflag instead of
refcount?". Then I thought about the stack and heap growing to meet
each other in the middle so I thought "a page could be on the heap at
one point, but then, after all objects on that page were deleted, it
could, after more functions calls, be on the stack" so I guess the
refcount is used to detect when "all objects on that page were
deleted" in which case, it would be put back into the gc::_page_pool.
Is that the reason refcount (actually `size_t _page::_heap_ref`) is used
instead of a `bool _page::_on_heap;` ?  Since other people trying to
understand the method will probably have the same question, it would
be nice to have such an explanation as detailed (or more detailed)
than the one above.

 >
 > 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.

By pointer, you actually mean the smart-pointer, _pgr, from cppgc.hpp:

//base class for gc_ptr
struct _ptr {
     //the actual pointer value
     void *_value;

     //constructor from value; registers the pointer in the gc by 
setting the relevant bit
     inline _ptr(void *v) : _value(v) {
         gc::_init();
         gc::_set_ptr(this);
     }
     ...
     //destructor; unregisters the pointer in the gc by resetting the 
relevant bit
     inline ~_ptr() {
         gc::_reset_ptr(this);
     }
     ...
};

where the gc::_{set,reset}_ptr(this) does the registration and
deregistration in "bitmap of pointers", implemented, at least partly,
in gc::_pages[_MAX_PAGES].  BTW, couldn't 1048576 in:

     //number of 4K pages that fit inside the 32-bit address space
     enum { _MAX_PAGES = 1048576 };

be calculated as some function of values in <limits> rather than
hard-coded. This would make the code more portable, IIUC.

 >
 > 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.
 >

This *sounds* like it works; however, it also sounds so simple
(although I couldn't think of it :( ) I'm surprised it hasn't been
tried before.  Maybe you should post this method to some gc newsgroup:

http://dir.gmane.org/index.php?prefix=gmane.comp.programming.garbage-collection

and ask for feedback.