[gclist] Comments on a gc approach

[Chris Smith]

This may not be (and probably isn't) new, but I'm wondering if anyone has
comments and/or pointers to previously written critique of this approach to
garbage collection.  As some background, I am trying my hand at writing a
Java VM with gc (just for self-educational purposes, at least for now).  I
am thinking of implementing an incremental, generational copy collector.  I
know incrementalism probably isn't required for most Java apps and that
incrementalism and generationalism don't belong together in most cases, but
it seems like so much more fun to write an incremental, generational 
collector.

In order to make it easier to update references after copying an object, I
have a list of ref objects that contain a pointer to an actual object. 
Objects access the internal object by locking the reference.  To implement
this locking, I have a read-write style lock.  The mutator grabs read locks
on references, and the GC grabs a write lock.

My reasoning behind this locking mechanism was that I didn't want to create
the overhead of grabbing a mutex before every reference to an object, and I
figured that while I'm at it, I can implement the write-barrier for the
incremental algorithm by scanning for references from black to white as I
unlock the object.  Hopefully this will provide enough of an efficiency
boost to avoid the need for something like using page dirty bits for the
write barrier, which would decrease the portability of the collector.

Finally, is there a well-accepted way to design a read-write style lock for
synchronizing the mutator and the gc?  This is what I came up with, but I
am not really experienced with this kind of thing, and this may not work in
all cases, or may be comparatively inefficient.  It is optimized as best 
am able for the uncontested case, because I'm guessing that will be the
most common by far.

The WaitableObject class encapsulates OS-specific synchronization
primitives...

class WaitableObject {
	...
public:
	...
	void wait();
	void notifyAll();
	...
};

I also have several functions to encapsulate platform-specific atomic
memory operations that are needed by the lock implementation.

void atomicIncrement(int *pval);
void atomicDecrement(int *pval);
int atomicReadAndSet(int *pval, int newval);

And here's the actual read-write lock class.

class ReadWriteLock
{
protected:
	int readCount;
	int writeCount;
	WaitableObject waitable;

public:
	ReadWriteLock() {
		readCount = 0;
		writeCount = 0;
	}

	void aquireRead() {
		while (1) {
			atomicIncrement(&readCount);
			// Loop exit point is here.
			if (writeCount == 0) break;
			atomicDecrement(&readCount);

			do {
				waitable.wait();
			} while (writeCount == 1);
		}
	}

	void aquireWrite() {
		while (atomicReadAndSet(&writeCount, 1) == 1) {
			waitable.wait();
		}

		while (readCount > 0) {
			waitable.wait();
		}
	}

	void releaseRead() {
		atomicDecrement(&readCount);
		waitable.notifyAll();
	}

	void releaseWrite() {
		atomicDecrement(&writeCount);
		waitable.notifyAll();
	}

	bool testRead() {
		return writeCount == 0;
	}

	bool testWrite() {
		return (readCount == 0) && (writeCount == 0);
	}
};

Is that a normal way to implement a read-write lock for garbage collection?

Thanks for your comments,

Chris Smith
Computer Science Major
University of Oklahoma