RE: Conservative GC and glibc data structures

["Boehm, Hans" <hans dot boehm at hp dot com>]

Roland -

Thanks very much for the detailed reply and offer.  The information
mostly confirms my (uncertain) impressions, which is good.  I think a
big part of the problem for me is to understand exactly what's currently
available.

It's worth distinguishing between two different GC usage models, which
have somewhat different requirements:

Model 1: The GC implements a separate function GC_malloc() (and
friends), while malloc continues to refer to the libc malloc (macro
games excepted). I think this is by far the most commonly used today.
It's used by gcj and Mono.

Model 2: The GC library overrides malloc.  This is currently hard to get
to work for multithreaded apps, in part due to tls issues.  This may
become more important and is, in many cases, cleaner.  It would be a
major, but tempting, change to always intercept malloc.  Currently it's
not feasible, since we can't do it well on some platforms.

There are clearly three kinds of regions of interest here:

A: Tls "roots" allocated either at the base of thread stacks other than
the main one.

B: Anything allocated before main starts.  This includes tls for the
main stack.  (I gather that some of these are allocated through a
malloc() defined in the dynamic loader that can't be intercepted, but is
not used after main starts?)

C: Further regions referenced by A and allocated through malloc().

Based on what you say, it sounds like all type A regions can currently
be found with the aid of pthread_getattr_np()?  Currently we intercept
thread creation and just use the stack pointer at that point.  We can
possibly also get the actual stack base by expanding to the next
unmapped page, but that's ugly, and has some debugging issues.  (We
could conceivably also get thread stack bases through the thread
pointer, as you point out.  But if we didn't intercept thread creation,
they would be much harder to enumerate reliably, so I'm not sure this
buys us much.)

We currently don't try to track type B regions (regions allocated before
main, but not found through dl_iterate_phdr) under Linux.  And it's
unclear whether we want to do that in general.  As you suggest there may
be junk there.  On some platforms, we do trace from all writable
mappings that we don't otherwise recognize.  That tends to be dangerous,
e.g. if someone decides to map a large amount of graphics memory during
startup or, even worse, if someone sets up user-space mappings to
special synchronization hardware that traps if you read it in the wrong
way.  (I know Irix can do that.  I don't know about Linux on SGI Altix.)

That's known to be inadequate for model 2, at least in the multithreaded
case.  I believe some dynamic loader data structures get collected.

Regions in C are not an issue, as you point out, if we're operating in
model 2.  These will be in the collected heap, and we can just scan
them.  However in model 1, they are a real issue, and we really need
some way to enumerate the malloc'ed regions along with their length.

My impression is that type C regions are used to hold __thread tls data
that's introduced by dlopen'ed libraries, and pthread_getspecific data
if a top-level buffer overflows?  Thus we could at least guarantee to
scan __thread data introduced by the main executable even if we miss
those?  That would be better than nothing, but not ideal.

If I understood all of this correctly, I think my requests in order of
importance are:

1) A way to identify the main thread tls region in B,

2) Reliable symbol interception (see below, though this may be the wrong
mailing list for that, and I may have misunderstood the issue),

3) A way to iterate over the malloc'ed tls regions C.

Since you asked about other requests, here's a concern that came up
recently and makes me nervous (see
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13212):

The collector currently needs to intercept symbols like pthread_create,
and then later call the underlying pthread facility.  It currently often
does that with preprocessor hacks.  But that's not very satisfactory,
and I would like to mostly do this using the linker.  My impression from
an earlier discussion is that this is no longer reliable with RTLD_NEXT,
due to versioned symbols.  We may end up getting the wrong version of a
symbol with dlsym(RTLD_NEXT, ...).  And dlvsym doesn't really seem to do
the trick, since we have no way of asking what the requested version was
for a particular existing symbol, such as the GC's version of
pthread_create.  (Tom Tromey just proposed a workaround for the above
bug that I think determines the version at configure time.  But I don't
see an argument that that's correct in general.

If I understand the situation here correctly, it would be really nice to
find a way around this.  There are all sorts of tools that would really
like to intercept library calls.  And my impression is that this
actually worked before versioned symbols.

Thanks.

Hans

> -----Original Message-----
> From: Roland McGrath [mailto:roland@redhat.com] 
> Sent: Sunday, February 05, 2006 7:21 PM
> To: Boehm, Hans
> Cc: libc-alpha@sourceware.org; Filip Pizlo
> Subject: Re: Conservative GC and glibc data structures
> 
> 
> We are certainly open to making things work better and more 
> cleanly with things like your collector.  I can only speak 
> for libc issues here.  For issues in libstdc++ or other 
> things provided by GCC, you need to talk to the GCC folks.  
> For glibc, it is almost a good time to be asking.  We are 
> getting close to making a 2.4 release, and we have supposedly 
> frozen the ABI.  If we can agree very soon on worthwhile 
> additions that we're sure are adequate and going to remain 
> satisfactory, then we can still add them now for the 2.4 ABI. 
>  If it's not done now, then it will wait for the next glibc 
> ABI release cycle some months away, and it will likely be 
> many more months before you can expect to see it available on 
> a lot of users' systems.  If there are any other issues 
> besides TLS data structures where glibc changes might be 
> worthwhile to improve things for your collector, please bring 
> those up now.
> 
> For your purposes, you don't really need to know about the 
> structure of TLS data or to enumerate it per se.  You just 
> need to find all of it from some roots, right?  The TLS data 
> structures are allocated space containing pointers.  Some of 
> that space is allocated normally with malloc, and some is 
> part of the thread data structures.  For threads created by 
> pthread_create, the thread data structures sit at the base of 
> the stack, which is either user-provided or is allocated with 
> mmap.  For the initial thread, the thread data structures are 
> allocated by the dynamic linker early in startup and reside 
> in startup dynamic linker heap space, which means either the 
> partial page after the dynamic linker's own .bss, or pages 
> allocated with mmap.  I don't know if you already examine the 
> process's mappings to consider heap roots set up before your 
> initialization.  If so, that should be able to find the 
> initial thread's data structures.  If you can find these 
> thread data structures and take them as roots, then that 
> should cover (indirectly) all the TLS data.  (Depending on 
> the kinds of TLS access used, some modules' TLS data will be 
> in separately malloc'd space and some will be directly in the 
> thread data structures at the base of thread stacks.)
> 
> These same thread structures point to all the thread-specific 
> data that the pthread_getspecific et al functions access.  
> Since there isn't a POSIX interface to enumerate 
> pthread_key_t's created so as to take each pointer from 
> pthread_getspecific as a root for that thread, I don't know 
> if you already try to track these.
> 
> You didn't propose any specific interface additions, but you 
> mentioned enumerating memory containing TLS values.  I am 
> glad to consider any specific proposal on its particular 
> merits.  My instinct is to focus on the fundamental 
> requirements of what you need in your context, and see if we 
> can avoid too much detail about the problem case you've 
> cited. TLS data is C data structures living in the heap, or 
> in part of the thread stack.  These are kinds of things you 
> already track as roots, though I don't know the details of 
> how you enumerate heap roots.  If you take each thread's 
> whole stack from base page boundary to the current SP, you 
> will come across TLS segments or pointers to malloc'd TLS 
> segments for that thread.
> 
> The initial thread's TLS data is perhaps a special beast in 
> that it's allocated in the dynamic linker startup heap, and 
> perhaps there aren't any other kinds of roots you care about 
> in there (just dynamic linker data structures) and so you 
> don't track that.  I'd like to understand better how you do 
> go about tracking heap data and how you decide to enumerate 
> it, before suggesting specific solutions.
> 
> If you do already know about the memory regions that are 
> potentially heap (from looking at the memory mappings) and 
> want a pointer into the right region, that is available 
> already just given the ELF TLS ABI for each machine.  On most 
> machines, a particular register is either zero (no TLS 
> support) or is a pointer with an ABI-specified bias (zero for 
> some machines) to the thread data structures.  On x86, if %gs 
> matches %ds then no TLS support is in use, and if not then 
> loading %gs:0 in the thread itself gets the pointer.  On 
> x86-64, I guess there isn't any generic way to check whether 
> %fs is set up or not; loading %fs:0 gets you the pointer, but 
> will fault on an older system that is not using %fs for thread data.
> 
> 
> Thanks,
> Roland
>