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

From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2007-09-20 10:37:41

Right on! :-)

Larry Evans wrote:
> 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.
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>