[gclist] boehm-gc and the STL

[Boehm, Hans]

[ Copied to gc@linux.hpl.hp.com, which may be more appropriate for this sort of detailed discussion.  For subscription/archive info see the bottom of http://www.hpl.hp.com/personal/Hans_Boehm/gc ]

Some more partial answers:

1) Recent versions of the GC distribution include a file gc_allocator.h.  This defines two standard-conforming allocator templates.  One allocates collectable memory; the other allocates uncollectable but traced memory.  The second is intended for containers that are explicitly deallocated but point to collectable memory.  These should work with any reasonably standard-conforming implementation.  (The distribution also contains older versions that were designed to work with STL implementations derived from the SGI one.)  I'm not sure this code has been terribly well tested, but bug reports are welcome.  It does contains some optimizations for pointer-free data.

2) I'm a bit surprised by the leakage problems.  This could happen if objects are deallocated explicitly but references to them are retained, or if the objects have a very high probability of containing false pointers.  It would be nice to track this down.  If this still occurs with the above allocator, and you have a small test program, I will be happy to take a look.

3) Re: finalization cycles.  My preferred solution is generally to break objects needing cleanup into two pieces:  One piece (A) contains only pointers that actually need to be followed during cleanup.  The other (A') contains all other data and a reference to A.  Only A is actually enabled for cleanup.  (In simple cases A' may not be needed.)  Any remaining cycles between objects needing cleanup in this scheme are at least suggestive of a real logic error, in that there is no acceptable order in which the finalizers/cleanup actions can safely be run.  (In theory they could be resolved by further splitting of objects, but I don't think I've ever seen a case where that was necessary.)

If this turns out to be too expensive, the "disappearing link" facility in the collector can be used to do basically the same thing without adding the second object.

This has the advantage over the unordered/Java solution in that ordering dependencies between finalizers are usually handled correctly automagically.  And when things do go wrong (due to an unexpected cycle), you got a leak with a collector warning that you generated a finalization cycle, instead of a crash (when you forgot to deal explicitly with an ordering constraint in the unordered case).

Hans

> -----Original Message-----
> From: Marcin.Skubiszewski@inria.fr 
> [mailto:Marcin.Skubiszewski@inria.fr]
> Sent: Wednesday, May 07, 2003 1:24 AM
> To: gclist@lists.iecc.com
> Subject: Re: [gclist] boehm-gc and the STL
> 
> 
> On Tue, May 06, 2003 at 12:19:01PM -0400, David Jones wrote:
> > I have just started playing with the Boehm collector under 
> C++ and have run
> > into a problem with STL objects.
> 
> I have been using STL with Boehm GC for more than a year now. This is
> difficult and delicate.
> 
> Pointers found in malloc'd objects are ignored by the
> GC. An stl::set that points to collectable objects needs to be
> collectable, not malloc'd.
> 
> > 1. Write an allocator for STL objects that uses GC_malloc.  
> Drawback: since
> >    C++ doesn't have "template typedefs", you need to write 
> an ugly template
> >    instantiation each time you want to use a container, e.g.:
> 
> This is what I do. And it is ugly, indeed, but the ugliness is not
> where you think.
> 
> This is my allocator:
> 
> class gcalloc : public __malloc_alloc_template<0> {
>  public:
>   static void* allocate(size_t __n) {
>     void* __result = GC_malloc(__n);
>     if (__result == 0) {
>       throw std::bad_alloc();
>     }
>     //cerr << "did GC_malloc" << endl;
>     return __result;
>   }
> 
>   static void deallocate(void* __p, size_t __n)
>   {
>     //cerr << "TRYING free" << endl;
>   }
> 
>   static void* reallocate(void* __p, size_t /* old_sz */, 
> size_t __new_sz)
>   {
>     void* __result = GC_realloc(__p, __new_sz);
>     if (0 == __result) {
>       throw std::bad_alloc();
>     }
>     //cerr << "did *** GC_realloc" << endl;
>     return __result;
>   }
> };
> 
> template <class _Tp>
> struct _Alloc_traits<_Tp, gcalloc >
> {
>   static const bool _S_instanceless = true;
> #if ((__GNUG__==3) && (__GNUC_MINOR__ < 2))
>   typedef simple_alloc<_Tp, gcalloc> _Alloc_type;
> #else
>   typedef __simple_alloc<_Tp, gcalloc> _Alloc_type;
> #endif
>   typedef __allocator<_Tp, gcalloc> allocator_type;
> };
> 
> 
> 
> Some examples of use of this allocator:
> 
> std::list <WLocker *, gcalloc> l; /* local variable declaration */
> 
> struct AlarmDescList : std::list<AlarmDesc, gcalloc>, gc {};
> 
> typedef std::basic_string<char, std::char_traits<char>,
> 			  std::__allocator<char, gcalloc> > 
> AuxMTKstring;
> struct MTKstring : AuxMTKstring, gc {
>   MTKstring(const char *a) : AuxMTKstring(a) {}
>   MTKstring() {}
> }; /* Here, MTKstring is a fully collectable string */
> 
> 
> 
> Now, where is the ugliness ?
> 
> Small ugliness: I do not understand why certain STL templates need the
> parameter gcalloc, and others (like basic_string) need
> std::__allocator<char, gcalloc> instead. I always try out both of
> them.
> 
> Middle-sized ugliness: my definition of gcalloc depends on the
> internals of STL. Therefore, I needed to rewrite it while
> migrating from gcc 2.95.3 to gcc 3.0 (no rewrite for migrating to gcc
> 3.2.2, which I use now).
> 
> Big ugliness: the whole thing only half-works: with STL, the GC seems
> to leave behind lots of leaks.
> 
> I got very big, ever increasing leaks with collectable std::set and
> basic_string. I do not really know what caused these leaks.
> 
> For std::set, I took the hypothesis that internal nodes of the tree
> somehow retain pointers to dead nodes (I don't know why, I did not
> analyze the operation of std::set). As a result, if one dead node
> leaks (is falsely considered by the GC as being alive), many other
> nodes, that are (recursively) referenced by it, will leak along with
> it.
> 
> To fix this, I wrote a version of the gcalloc allocator that clears
> objects that are explicitly deleted. This way, whenever some dead
> (explicitly deleted) node leaks, it will contain no pointers, and will
> not cause other nodes to leak. This solved the problem with std::set
> and other similar structures.
> 
> Here comes the modified version of gcalloc:
> 
> class eraseGcalloc : public gcalloc {
>  public:
>   static void deallocate(void* __p, size_t __n)
>   {
>     bzero (__p, __n);
>     //cerr << "TRYING free" << endl;
>   }
> };
> 
> _Alloc_traits<_Tp, eraseGcalloc > is defined similarly to
> _Alloc_traits<_Tp, gcalloc >.
> 
> Here is an example of use of eraseGcalloc:
> 
> typedef multiset < Measure *, OrderingByDesiredDate, eraseGcalloc >
> MultisetSortedByDesiredDate;
> 
> Concerning basic_string, I chose a much simpler solution: I quit using
> the collectable version. This is possible because a basic_string never
> points to outside objects.
> 
> The use of malloc'd strings induces another problem: we need to
> somehow trigger the destruction of these strings. I use the following
> solution: every string is embedded in a collectable object, and the
> collectable object is set up so that its collection will trigger the
> destructor; recursively, the destructor will cause the embedded string
> to be properly and completely freed.
> 
> To cause the destructor to be called, it would suffice to have the
> object inherit from gc_cleanup. But this is not quite the solution I
> retain, because gc_cleanup has a problem with cycles of garbage: if A
> and B are garbage objects, and A points to B, and B points to A, then
> A and B will never be collected. This has to do with having a
> perfectly clean semantics of finalization/destruction (ask Hans Boehm,
> not me, about this issue).
> 
> Instead of using gc_cleanup, I declare gc_destruct, which is very
> similar to gc_cleanup, but ignores cycles: a dead object will be
> destructed ASAP, regardless of who references it and/or who is
> referenced by it. Unlike gc_cleanup, gc_destruct does not guarantee
> correct operation of fancy destructors, but is perfectly OK with
> simple destructors that only destroy things.
> 
> gc_destruct is defined as follows:
> 
> class gc_destruct: virtual public gc {
>  public:
>   inline gc_destruct();
>   inline virtual ~gc_destruct();
>  private:
>   inline static void GC_cdecl cleanup( void* obj, void* clientData );
> };
> /*
>   Instances of classes derived from "gc_destruct" will be allocated
>   in the collected heap by default.  When the collector discovers an
>   inaccessible object derived from "gc_destruct" or containing a
>   member derived from "gc_destruct", its destructors will be
>   invoked. */
> 
> inline gc_destruct::~gc_destruct() {
>   GC_REGISTER_FINALIZER_IGNORE_SELF(GC_base(this), 0, 0, 0, 0 );
> }
> 
> inline void gc_destruct::cleanup( void* obj, void* displ ) {
>   ((gc_destruct*) ((char*) obj + (ptrdiff_t) displ))->~gc_destruct();
> }
> 
> inline gc_destruct::gc_destruct() {
>   GC_finalization_proc oldProc;
>   void* oldData;
>   void* base = GC_base( (void *) this );
>   if (0 != base)  {
>     // Don't call the debug version, since this is a real 
> base address.
>     GC_register_finalizer_no_order
>       (base, (GC_finalization_proc)cleanup,
>        (void*) ((char*) this - (char*) base), 
>        &oldProc, &oldData );
>     if (0 != oldProc) {
>       GC_register_finalizer_no_order(base, oldProc, oldData, 0, 0 );
>     }
>   }
> }
> 
> 
> Examples of use of gc_destruct (this is really trivial):
> 
> struct PathList: std::list <Pathname *, gcalloc>, gc_destruct {};
> 
> class WebAdministrable : public gc_destruct {
> /* ... */
> };
> 
> 
> Good luck !
> 
> 					Marcin.
> 
> 
> ----- End forwarded message -----
>