[rucksack-devel] GC problems

[Edi Weitz]

On Sun, 23 Jul 2006 22:00:09 +0200, Edi Weitz <edi at agharta.de> wrote:

> Anyway, I currently think there are more substantial problems with
> the garbage collector.  I'm trying to build a simple test case which
> demonstrates them.  More later.

OK, here is one:

  (in-package :test-rs)

  (defun check-gc (n)
    (with-rucksack (rucksack *test-suite* :if-exists :supersede)
      (with-transaction ()
        ;; after this, INNER can be reached directly from the root
        (let* ((inner (p-cons "Waldorf" "Statler"))
               (root (p-cons 42 inner)))
          (add-rucksack-root root rucksack)))
      (with-transaction ()
        (let* ((root (first (rucksack-roots rucksack)))
               (inner (p-cdr root))
               (array (p-make-array n)))
          ;; after this, INNER can't be reached from the root anymore
          (setf (p-cdr root) 43)
          ;; now let the GC do some work
          (dotimes (i n)
            (let ((string (format nil "~R" i)))
              (setf (p-aref array i) (p-cons string string))))
          ;; hook INNER back to the root again before we finish the
          ;; transaction
          (setf (p-car root) array
                (p-cdr root) (p-cons 'bar (p-cons 'foo inner))))) ; [***]
      (with-transaction ()
        (let* ((root (first (rucksack-roots rucksack)))
               (inner (p-cdr (p-cdr (p-cdr root)))))
          ;; we expect the list ("Waldorf" "Statler") here
          (list (p-car inner) (p-cdr inner))))))

If I try to execute CHECK-GC with a high enough value for N (on my
machine, 10,000 will suffice), I reproducibly get an "Object-id
mismatch" error from Rucksack.

What happens is similar to what I described on July 20, but not the
same: In the second transaction, the GC has to do a lot of work if N
is large enough, one pass won't suffice.  But then on the first pass
already, INNER can't be reached from the one and only root anymore
because it can only be reached through the P-CONS objects created in
the [***] line, and these are at the end of the dirty queue and
haven't been written to disc when the GC scans the heap for the first
time.

So, the GC marks INNER dead and frees its space.  INNER's block will
then be re-allocated for some other object from the dirty queue.
Bang...

The important difference between the July 20 case and this one is that
INNER was not written in the current transaction - it's an "old"
object.  Still, the GC is wrong when it frees its space.

I /think/ there were discussion about similar cases on this mailing
list two months ago or so, but IIRC they were about more "esoteric"
scenarios where you hold references to persistent objects while you're
not within a transaction or somesuch.  IMHO, the example above is a
completely legitimate usage of Rucksack, though.

Cheers,
Edi.