Tcl Source Code

testing a references support for Tcl I'm developing
(that will be
the subject of another comunication), I discovered a
bug that
is very common in languages implementations using
reference counts.

The problem is that when a reference of an object drops
to zero,
the Tcl_DecrRefCount() calls Tcl_FreeObj() in order to
free the
object internal representation, string, and storage
allocation.
If that object is able to take references to other
objects, before
to free the object, all the referenced objects gets
RefDecremented(),
and this can result in a new (recursive) invocation of
Tcl_FreeObj().

That's how it should be in theory, but with deeply
nested data
structures, for example lists containing lists
containing lists (...)
the result is a deep recursion of Tcl_FreeObj(), and
once the C
stack is terminated, a segmentation fault.

The following code will crash Tcl on many operating systems
and many archs:

set x foobar
time {lset x 0 [list $x 2]} 20000
set x {}

If this is not able to crash your box, try with a value
a bit
bigger than 20000.

Another way to crash Tcl is to substitute the "set x
{}" final
command with "string length $x". Because the list -> string
conversion also is a recursive call.

Of course the 'free' problem is much severe than the string
conversion one, but fortunatelly the fix is general and
quite
simple.

To fix this problem Tcl should "lazy free" objects.
Instead to really
free the object, Tcl_FreeObj() should just put the
object's pointer
in a ToFree list, then free that list only when
Tcl_FreeObj() is
not called recursively (an alternative is to call a
Tcl_FreeCycle()
when there is some allocation action, and on low memory).

I did a simple implementation for Tcl HEAD (attached to
this email).
Seems to work well but should be modified to support
threads
and the Tcl coding style.

Regards,
Salvatore Sanfilippo

Logged In: YES 
user_id=79902

Fixed in HEAD and added tests.

File Deleted - 90857:

File Added - 90859: freeobj.diff

File Added - 90857: freeobj.diff

Logged In: YES 
user_id=79902

Here's the changes I had in mind.  The patch should be
neatly thread-safe (make test in threaded Tcl works) and
appears to deal with the freeing problem firmly (or at least
when I have a go with an object tree ten times deeper than
the fault was reported for, nothing goes wrong. :^)

Assigning to area maintainer for review.

Logged In: YES 
user_id=79902

I have a prototype fix for this in the works.  A few
comments on Miguel's notes:
1. Queues are more complex to maintain than stacks, and
library code tidying up the guts of a type should
categorically not rely on the order of deletion of objects.
The core does not document what this order is BTW.
2. The behaviour (whether or not to use per-thread
collecting) depends purely on TCL_THREADS and not which
allocator. It turns out that this can be done really neatly
with virtually the same code in the threaded and
non-threaded case. :^)
3. Being very lazy is probably not a good idea, especially
as it will significantly increase the overall memory
consumption of Tcl unless a strategy of "reuse the most
recently released object" is used, which negates a lot of
the benefit of laziness.  Keeping a reasonable degree of
openness is best.

I'll upload the patch once I've got a version which compiles
cleanly in both threaded and non-threaded builds. ;^)

Logged In: YES 
user_id=148712

Some notes:

1. It is probably necessary to arrange that the objs are
really freed in the same order of the requests. This is no
guarantee that things will work, but is more robust than
inverting the order wrt assumptions by extensions. IOW, we
need a queueToFree (FIFO) - not a stackToFree

2. Each object should be freed from its own thread. This
implies that each thread has to maintain its own queue, even
if using the non-threaded allocator with a unified
tclFreeObjList.

3. The "laziest" approach (free the object when it is about
to be reused) could be dangerous: an extension may be
keeping a reference to the obj that is not accounted in the
refCount, relying on the freeIntRepProc to remove it. If we
delay calling fIRP while the obj is in fact dead for tcl,
the extension is not notified of this death and could reuse
it - not good.

Logged In: YES 
user_id=79902

Just wondering if it would be possible to build a queue
using the bytes field to hold the links between objects
being freed?

Logged In: YES 
user_id=79902

The supplied patch is not even close to thread-safe.  :^/

Logged In: YES 
user_id=79902

I looked and saw that it was indeed a problem.  :^)

The fix is to be careful about nested calls to TclFreeObj()
but I'd need to check whether antirez's patch adds
additional overhead in terms of locking in threaded builds
(ideally, single level frees will happen immediately, but
multi-level frees will be queued; current behaviour is to
process them using the stack, which unsurprisingly blows up.)

If I don't review and fix this by the next release, moan at me.

Logged In: YES 
user_id=72656

IIRC dkf was looking into this at one point.

File Added - 74990: lazyfree.patch