[gclist] Multi threaded reference counting

[James McCartney]

At 3:41 PM -0800 1/18/97, Henry G. Baker wrote:
>> I am trying to figure out how to do multi threaded reference counting
>> and have only one problem. When an object's ref count drops to zero
>> you can't free it immediately because it is not possible to atomically
>> dereference the object and decrement its count, another object
>> might have incremented it while you were decrementing it.
>
>Huh?  If the reference count is _really_ the reference count, then
>refcount=0 means that _you_ are the only one who can reference it, and
>there can't possibly be any contention.
>There has been a lot of work done on this problem under the guise
>of 'distributed GC'.  Perhaps a web search will turn up something....

In the distributed GCs I've seen only one thread owns an object.
I need a shared memory GC where every thread can access the
contents of every object. In that environment you can have a race
condition where one thread is decrementing the reference to an object
while another is incrementing it :

say array X[0] contains the only reference to object Y and thread A
stores  NIL into X[0] while thread B pushes X[0] onto its stack.
It is possible for Y's refcount to become zero due to thread A
as thread B tries to increment it.

Say the code executes in the following sequence:

thread B:
	/* load contents of X[0] to a register. */
	obj = X[0];

thread A :

	/* store NIL in object get previous contents */
	prevobj = fetch_and_store(&X[0], NIL);
	/* decrement refcount of previous contents */
	decrement prevobj->refcount
	/* free it */
	if (refcount <= 0)
		free(prevobj);

thread B interrupts:

	obj->refcount++; /* crash! object has been freed by thread A. */



>Of course, this finesses the whole issue of how you get a _real_
>reference count in a multi-threaded system in the first place.

  Well that is exactly the issue I need to solve. The system I've proposed
is a non-blocking non-copying incremental shared memory multi threaded GC
which is exactly the sort of thing that I need.
   I haven't found any literature that describes such a thing. If you know of
one please advise. Web searches have not turned up anything and I've
printed out dozens of papers.

  By deferring the freeing of the object as I proposed in my previous post
I prevent the race condition and crash above.



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