[gclist] multiple mutator thread GC, ref counting in particular.

[James McCartney]

<Sorry about the repost, forgot the Subject line and had a code typo.
Getting off on the right foot here..>

Hi, I just joined this list. As introduction, I've written an audio
synthesis language which uses an adaptation of Paul Wilson's real
time GC algorithm (noncopying incremental update write barrier with a
treadmill for each power of 2 size class.. whew!). Now that I have a
BeBox I'd like to have a multi mutator thread safe version of this, but
I've been unable to figure out how to do it. So I thought I'd bail
and try out doing just a multithreaded reference counting gc, but even that
has me vexed. It seems like it should be simple.
Consider an object format like :

typedef struct obj {
	long refcnt;
	long numslots;
	struct obj *slot[1]; /* extend as long as needed */
} Obj;

Now I want to be able to have the operations :

void fetch_and_push_slot(Obj** stackptr, Obj *obj, int index)
{
	/* get a slot, increase its content's refcount, and put it on the
stack */
	Obj **slotptr;
	slotptr = obj->slot + index;
	atomic_fetch_and_add(&(*slotptr)->refcnt, 1); /* increase refcnt */
	*stackptr = *slotptr;
	stackptr++;
}

void pop_and_store_slot(Obj** stackptr, Obj *obj, int index)
{
	/* pop the stack and store in a slot, decrease refcount of slot's
		previous contents */
	Obj *newval, *prevval;
	long oldcnt;
	--stackptr;
	newval = *stackptr;
	prevval = atomic_fetch_and_store(obj->slot + index, newval);
	prevcnt = atomic_fetch_and_add(&prevval->refcnt, -1); /* decrease
refcnt */
	if (prevcnt <= 1) {
		dealloc(prevval);
	}
}

pop_and_store_slot() seems OK to me. Other pop_and_store_slot() calls can
interrupt it and they will execute OK. However fetch_and_push_slot()
can get messed up because in the time between the first dereference of slotptr
and the and the second one to get at the refcnt field, it could get interrupted
by a pop_and_store_slot() which deletes the object pointed to, making the
access to refcnt be via a dangling pointer. Is there a way to implement these
functions using the usual primitives?

(note the stackptr needs no protection because it is only changed by its own
thread)



   --- james mccartney     james@clyde.as.utexas.edu   james@lcsaudio.com
If you have a PowerMac check out SuperCollider, a real time synth program:
ftp://mirror.apple.com//mirrors/Info-Mac.Archive/gst/snd/super-collider-demo.hqx