[Gc] False pointers and (long) linked lists?

Jan Wielemaker J.Wielemaker at vu.nl
Tue Jan 24 06:10:23 PST 2012


Hi,

Before considering wild plans, I'd check with the gc users to see
whether this problem is already solved. I'm deleting cells from a (long)
single-linked list by making the pointer of the previous cell point to
the next, hoping GC will do the rest. That works nice in theory :-) In
fact, it works great for short lists.

However, some of the cells are referenced by `false pointers' (i.e.,
misinterpreted integers). As a consequence, all cells that are
(indirectly) reachable from this false referenced garbage cell stay
reachable as well :-(

An obvious solution is to eliminate false pointers. It wasn't very hard
to find the main cause using GC_generate_random_backtrace().
Unfortunately, one cannot use this after introducing
GC_MALLOC_EXPLICITLY_TYPED():

<gc_typed.h>:
...
#ifdef GC_DEBUG
# define GC_MALLOC_EXPLICITLY_TYPED(bytes, d) GC_MALLOC(bytes)
...

I.e., under GC_DEBUG, typed allocation is disabled.  But, without GC_DEBUG,
we cannot use GC_generate_random_backtrace():

****Chosen address 0x1c1378fe in object
start: 0x1c137870, appr. length: 144
No debug info in object: Can't find reference
(gdb)

This makes it very hard to find the less frequent sources of false
pointers :-(

One (dirty) way around I can see is to use my own marking procedure for
the cells. Now, if I mark a cell marked as deleted, I follow the chain
of deleted cells to the first non-deleted (or NULL) and make the next of
all cells found point to the end. This will turn all intermediate cells
into disconnected cells and GC will take care of (most of) them.

This sounds overly complicated.  Any other suggestions?

	Thanks --- Jan

P.s.	I read a lot about the vulnerability of large objects wrt. conservative
	GC.  It appears this more generally applies to large interlinked networks
	where a small part is referenced from a false pointer.


More information about the Gc mailing list