On Tue, 30 Nov 2004, Keith Packard wrote:

...

I've been using a garbage collector in C for about twenty years which is different from the Boehm system.

It looks really interesting to me. I'm not sure it would address the general problems we've had with garbage collection[1], nor that it offers everything we need for C++.

...

advantages:

1. Completely portable -- no machine dependent code at all

I have to say I find the use of a "reference stack" in avoiding the need to examine the stack or registers to be very elegant.

...

2. Integrates with malloc/free using code

Hmm. We haven't really had many integration problems with the boehm collector. About 1/4 of our codebase uses the collector, and the remainder uses the system allocator (generally via glib).

The one issue that does come to mind is the problem of storing references to collector-managed objects in malloc-managed memory.

In Inkscape's case we have some collector-managed classes which have supplementary refcounts. Objects of these hybrid classes are pinned while they have a nonzero refcount, and can safely be referenced from untraced memory if refcounts are managed appropriately.

Of course, refcounts used in this fashion can create some interesting issues with cycles if they're used redundantly with references the collector knows about -- for example, leaks from incompletely removing internal refcounting from refcounted classes when they were rewritten to be such hybrids.

The only other major issue has been pre-existing refcount leaks whose effects were magnified when the collector was introduced, since the collector knows about a lot of references naive refcounting could not.

Is there any alternate way the nickle collector could assist us in marrying the collected and uncollected worlds?

...

3. Precise pointer knowledge - the set of referenced objects is known,

not discovered.

That would be exceptionally nice to have, especially as large RGBA image buffers have a decent chance of looking a lot like arrays of valid pointers in places.

Right now we have to expose a distinction between "atomic" and "traced" classes to deal with that sort of thing; it would be nicer if classes intrinsically knew to mark themselves appropriately, but things are certainly managable as-is.

...

disadvantages:

1. Requires stylized function call/return macros both where the

allocator is used as well as in at least one place above all allocation calls in the call graph.

For Inkscape that needn't be as ugly as it might be in C, since in C++ you could do things like this[2]:

class Thing : public Managed { ... };

void fleem() { MemStackFrame frame; ... Thing *blah = new Thing(); ... }

Thing *blah() { MemStackFrame frame; ... Thing *foo = new Thing(); Thing *bar = new Thing(); ... return frame.retain(something_p() ? foo : bar); // only one kept }

and would have the advantage of being exception-safe, obeying C++ scoping rules, and so forth.

There would be some issues with this that I'm not immediately sure how to solve, though:

* implementing other allocation interfaces: - array new/delete - an STL allocator - use in automatic variables

* finalization (required e.g. when collector-managed objects reference purely refcounted objects)

* situations where 'Managed' isn't the root of a class hierarchy (e.g. as a result of multiple inheritance) -- we'd basically need a facility to get the base address of a collector-managed object, given an interior pointer like boehm's GC_base()

Admittedly I'm not sure how necessary some of these are.

-mental

[1] As far as I can tell there's only one problem we've had that's specific to the Boehm collector (the allocation hangs), and that one appears likely to be a bug in the particular version of the collector rather than an issue with conservative collection.

[2] The implementation, so far as the example goes, could probably be something like the following...

class MemStackFrame;

class Managed { public: void *operator new(size_t size) throw(std::bad_alloc) { void *header=MemAllocateRef(datatype_(), size); if (header) { return object_(mem); } else { throw std::bad_alloc(); } } void operator delete(void *) { /* do something? */ }

protected: virtual void mark_() {}

private: Managed *object_(void *object) { return (Managed *)((char *)object + sizeof(struct bfree)); } void *header_(Managed *object) { return (char *)object - sizeof(struct bfree); } static void invoke_mark_(void *object) { object_(object)->mark_(); } static DataType *datatype_() { static DataType type = { &Managed::invoke_mark_, NULL, "C++" }; return &type; }

friend class MemStackFrame; };

class MemStackFrame { public: MemStackFrame() : stack_pointer_(STACK_TOP(MemStack)), retained_(NULL) {}

~MemStackFrame() { if (retained_) { STACK_RETURN(MemStack, stack_pointer_, retained_); } else { STACK_RESET(MemStack, stack_pointer_); } }

template <typename T> T *retain(T *object) { retained_ = Managed::header_(object); return object; }

private: StackPointer stack_pointer_; StackElement retained_; };

On Wed, 2004-12-01 at 01:07, Keith Packard wrote:

...

I have to say I find the use of a "reference stack" in avoiding the need to examine the stack or registers to be very elegant.

I was much more interested in portability than transparent use, and with some practice, it's not that hard to use the macros. One nice thing is that forgettin to use the macros causes no harm, it just delays the collection of garbage collected below the function failing to invoke the macros.

That's part of the beauty of it -- I am very fond of intrinsically fail-safe designs. Sadly they're rather rare in the software world ("defensive programming" doesn't count).

...

The one issue that does come to mind is the problem of storing references to collector-managed objects in malloc-managed memory.

And this is easy enough with the nickle collector -- you create a synthetic object and add it as another root in the system. The 'mark' function then walks the malloced memory to reference the gc'able objects. The malloc'ed storage need never know that it's being used in this fashion.

That wouldn't always be possible; in our case the referencing malloc()ed memory is often abstracted away in e.g. a glib or sigc++ closure. In those instances there is generally no way for such a 'mark' function to get at it.

The only general solution I've found so far is to create synthetic "anchor" objects which are attached to a root and contain a refcount and a pointer to the managed memory. Usually the interfaces provided by the closures or whatever are sufficient to manage a refcount.

...

That would be exceptionally nice to have, especially as large RGBA image buffers have a decent chance of looking a lot like arrays of valid pointers in places.

heh. One wonders how much of the GC time is spent wandering through non-pointer data. Think of the cache thrashing when you hit something like this which isn't explicitly marked as non-pointer data...

Supposedly it isn't a big deal in practice, but I still avoided using it as a wholesale malloc replacement for that reason.

As things stand right now, GTK and other libraries still use the system allocator for everything. In our own code we use either the system allocator or GC_malloc_atomic() for strings and image data (the latter function marks the allocated memory as containing non-pointer data).

The boehm collector does also provide a facility for typed allocation, but with this approach we've never needed to resort to it. It does some clever things like blacklisting unallocated ranges while bogus pointers or pointer-like values

...

• implementing other allocation interfaces:
  • array new/delete
  • an STL allocator

The fundamental problem in these two cases is that no type information is provided to the allocator -- the only information available is the raw size of the memory requested. Figuring out what's actually been put in the memory and how to mark it gets painful.

For example, if I use the new[] operator to allocate an array of 32 objects of some type (which happens to have a size of 4 bytes), all the function implementing the operator will be told is that 128 bytes were requested. For all it knows, the requested memory might get used for e.g. 16 8-byte objects.

In the case of an STL allocator, I don't think it's even guaranteed that the objects placed in the requested memory will be homogenously typed or sized. I know it's certainly possible that they will not be homogenously spaced nor the memory block fully used.

The simple new/delete case isn't really different, but there we could at least assume that the memory would only contain one object and that its address would lie at the start of the allocated block, which would let us find a pointer to its 'mark' function easily enough.

In a nutshell, C++ is really unkind to typed allocators.

...

• use in automatic variables

Whether stack-allocated objects are a problem depends on the approach taken in marrying the C++ type system to the allocator's.

Some approaches, like the sketch in my last email (which has some bugs, so don't read too much into it), place the struct bfree (at least the type pointer; I am assuming the 'next' pointer was safe to reuse when it wasn't in a free list) before the start of the object. In those cases, a stack-allocated object will be missing the bfree "header".

Thanks much for taking time to look at the code; the prototype C++ code looks a lot easier to use than the C macros. Note that you'll still want to use the macros in places like:

a () { return new a_type; } b () { return new b_type; } c () { return new c_type; } bar () { operate (a (), b(), c()); } foo () { for (i = 0; i < 100; i++) bar (); }

Failing to use the macros in bar will result in a large pile of uncollectable garbage until foo returns to some higher level function which does use the macros. This is probably the most annoying part of the whole system.

Hmm. One of the reasons I adopted a garbage collector was to facilitate writing in a functional style which would unfortunately be susceptible to this sort of problem.

Also in some cases the equivalent of bar() may be a generic function written by someone else (e.g. an STL generic algorithm). In those cases it might not always be appropriate to set up a reference stack frame, and we couldn't anyway if we wanted to.

In this specific example, though, I don't believe the macros are necessary. I would expect this to work:

void bar() { MemStackFrame frame; operate(a(), b(), c()); }

(MemStack would be reset by MemStackFrame::~MemStackFrame() when 'frame' goes out of scope)

Oh, one thing I used to do was erase newly allocated memory. This was a huge simplification as it meant you didn't need to be particularily careful about allocation and initialization order. As it is, any potential pointer values in newly allocated data must be initialized before the next allocation call is made. This turned out to be a non-trivial source of bugs when I stopped calling memset. I'm not sure it's worth the modest performance improvements myself.

At least it's more portable. As you probably know, at least on paper memset() isn't a portable way to initialize pointers.

[ For those following along at home: the compiler will maintain the invariant NULL == (void *)0 mandated by the C and C++ languages, but on some (rare) architectures the NULL pointer is not the zero address, requring gymnastics on the compiler's part which would be defeated by the use of memset(). ]

In my experience another problem with the allocator zeroing memory is social: bugs tend to creep in if folks are relying on the allocator for implicit initialization. I think this is partly because explicit initialization forces people to think through the initial state of the object, and serves something of a documentation role as well.

In Inkscape I actually fill memory allocated for some classes with garbage before their constructor is called. It's helped shake out some subtle bugs that were previously flying below the radar because zero was close to a sensible value (and pages claimed from the OS are often initally zero-filled).

Er, forgive my curmudgeonly ranting. ^^; I still wonder whether there might be another good conservative solution to the initialization/allocation ordering problem...

-mental