Re: Good strategy for determining root set in C++

Our collector uses a variety of mostly system-dependent techniques to
identify bounds of the root segments.  This is often not as nice as we
would like, since the OS/linker interfaces are often not completely
adequate.  That's one reason we're trying to get some GC support into
the C++ standard, which would make this more of a vendor issue.  (See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1943.pdf )

For main program static data, many linkers define symbols at the bounds.
(Or, for system V variants, there tend to be obscure rules for finding
the start of the data segment from the value of the etext segment.) If
not, you can often start at the address of a global, and probe addresses
until you get a SIGSEGV or equivalent.  (This is undesirable, since it
tends to confuse programmers using debuggers; we thus use it as a last
resort.)

Finding dynamic library data areas is also very system-dependent.  Glibc
provides the dl_iterate_phdr call, which can also be used to find the
main program data area.  Under linux, you can also look at
/proc/self/maps, but that can result in scanning mapped files (or frame
buffers, or weird special hardware) that you really didn't mean to scan.
Under Windows, we do use VirtualQuery, and try to deal with some of the
resulting problems.

We have a variety of possible rules for finding the base of the main
stack.  As Eliot points out, the stack pointer serves as the other
bound.  Note that you have to be careful to make sure that you are
scanning all callee-save register slots, even if they end up inside GC
frames

For other thread stacks, we generally intercept thread creation calls,
and hence can know the stack base.  For pthread-like systems, we usually
stop threads by sending them a signal, which gives us the stack
pointers.  (That has the disadvantage that it's only 95% transparent to
client code, in that a few nonrestartable system calls may need to be
wrapped, and that we need some mechanism for intercepting pthread_create
or equivalent.)

We've generally discovered that this way of handling thread stacks isn't
completely adequate.  You also need a way to "attach" preexisting
threads to the GC after the fact.  Version 7 of our GC has a fairly
elaborate interface which tries to reconcile that with the fact that
finding thread stack bounds after the fact can be hard.  (Glibc does
have an easy way to do it, I believe.)

We don't currently deal with some of the more obscure sources of roots
in C++, particularly thread local storage and in-flight exceptions.  If
you really care, I can say more about that, or you can read more about
in the [email protected] archive.  Currently the rule is that anything
accessible through those has to be accessible through other means as
well.

Hans

> -----Original Message-----
> From: [email protected] 
> [mailto:[email protected]] On Behalf Of Eliot Moss
> Sent: Friday, April 14, 2006 4:08 AM
> To: Campbell, Matt
> Cc: [email protected]; [email protected]
> Subject: Re: [gclist] Good strategy for determining root set in C++
> 
> Others would be more qualified than I to describe the Boehm 
> collector in detail. The stack pointer is the obvious clue as 
> to where to start scanning the stack. In single threaded 
> programs, one would run from there upwards to the end of the 
> stack region. In multithreaded programs, one must enumerate 
> the threads and from them their stacks. Static areas come 
> from linker information to begin with. And the 
> allocation/collection system knows how it parcels out 
> dynamically allocated memory.
> 
> What complicates things a bit is that the collector will 
> avoid using certain regions of virtual memory precisely 
> because it would cause non-poiner values in the 
> stack(s)/statics to be considered (ambiguously) roots.
> 
> But if you want to understand that collector, there are 
> papers about its original design, and I expect you can find 
> experts through this list with whom you can correspond more 
> directly, etc.
> 
> Best wishes -- Eliot Moss
>