[rucksack-devel] Rucksack error

[Edi Weitz]

On Thu, 20 Jul 2006 02:15:38 +0200, Edi Weitz <edi at agharta.de> wrote:

> After some testing today I'm pretty sure there's a race condition in
> the garbage collector.

OK, here's my analysis of what I think is happening:

Suppose you're writing a big aggregate object (like a btree) to the
heap.  A, B, and C are parts of this object where A is a Rucksack
root.  A points to B and B points to C, i.e. the garbage collector in
its marking phase reaches C through B.

Now suppose that A and C have been created pretty early while B has
been created much later, i.e. it's far behind in the dirty queue of
the transaction.  This is not unusual, especially for btrees.

When the transaction is committed, A and C get written to disk.
HANDLE-WRITTEN-OBJECT adds C to the roots of the heap (A is there
anyway) if necessary so it will be marked live.

However, this only applies to the /current/ garbage collection.  It is
not impossible (and this is what happens in the TEST-BTREE-INSERT
case) that another GC will be started while B is still not written to
disk.  This time C will simply be marked dead in the
:MARKING-OBJECT-TABLE phase and it won't be marked live in the
:SCANNING phase because (B still not being there) it can't be reached
from the root A.

This will eventually result in C being deallocated and overwritten by
other objects in the same transaction commit.  That's it... :(

Now, what to do about this?

The only idea I could come up with is the following: In the
:MARKING-OBJECT-TABLE phase never mark objects dead that belong to the
current transaction.  This assumes that a) we're always within a
transaction and b) transactions can't be nested, but I think this is
what Rucksack currently does anyway.

Still, it looks like a kludge to me as now the garbage collector has
to be aware of transactions.  There goes the modular design.  Any
better ideas?

Even worse, the idea above won't work with Rucksack in its current
form because if you close and then re-open a rucksack, transactions
will again be numbered beginning from 1.  This makes me wonder why
transaction IDs are stored at all because they seem pretty useless.
Am I missing something?  (I should probably re-read the mailing list
archives from May, maybe this was already discussed.)

Anyway, I'll try to come up with a solution as outlined above but I'll
first change the way transactions are identified.  Stay tuned...

Cheers,
Edi.