[rucksack-devel] Rucksack error

[Arthur Lemmens]

Edi Weitz wrote:

> 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... :(

I agree with your analysis.  We already discussed this privately, but
just for the record:

At the moment I think that the best solution for this problem is to
make sure that dirty objects (like B in your example) are serialized
to disk when the GC sees them during the scanning phase.  Sooner or
later they must be written to disk anyway, so we might as well do it
when the GC needs them to be on disk.

The only potential problem I see is that this could recursively
trigger another GC step (when we're already within a GC step).  But I
suppose we could use some kind of flag to indicate that the GC is
active, so we know that we shouldn't call the GC when that flag is
true.

Unless someone has a better idea, I think I'll try to implement this.

Arthur