[gclist] boehm-gc and the STL

[Marcin.Skubiszewski@inria.fr]

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