[Gc] Dangling disappearing link

Ludovic Courtès ludo at gnu.org
Sun Nov 1 07:45:47 PST 2009


Hello,

GNU Guile 1.9 has weak hash tables implemented in terms of disappearing
links: buckets are lists of weak pairs, where either the first element,
the second one, or both (depending on whether it’s a weak-key,
weak-value, or doubly-weak hash table), are disappearing links.

It is sometimes possible to get an invalid key from such a doubly-weak
hash table.  To reproduce the problem, we run two threads: one that
calls ‘GC_gcollect ()’ continuously, and the other keeps inserting and
fetching an element in the hash table, always under the same key.
Eventually, fetching from the hash table would return an object that’s
not the one that was inserted in the hash table, and that’s not even a
valid Scheme object.

IOW, the disappearing link to the value has /not/ been nullified, but it
points to some invalid object.  That invalid object, however, passes
‘GC_is_visible ()’.  (In case it helps, it looks like this:

                            ,----------.  ,------------.
                            |          |  |            |
  .-----  . . .  ------+----v-+------+----v-+------+---+--+------.
  |                    | back | NULL | back | NULL | back | NULL |
  |                    | ptr  |      | ptr  |      | ptr  |      |
  `-----  . . .  ------+------+------+------+------+--^---+------'
                                                      |
                                                      |
                                               dangling pointer

It looks like a 2-word element free-list.  It is mistaken by Guile as a
list of Scheme pairs, but NULL is not a valid Scheme object.)

The weak hash table implementation fetches elements from
‘GC_call_with_alloc_lock ()’, which supposedly avoid such race
conditions.

I haven’t been able to reproduce the problem with a simple C program, so
I’d be glad if you could provide me with some advice.

Thanks,
Ludo’.



More information about the Gc mailing list