Segfault in gc with cyclic trash

[inglesp]

BPO	21435
Nosy	@gvanrossum, @tim-one, @pitrou, @vstinner, @larryhastings, @tjguk, @asvetlov, @gvanrossum
Files	problemreport.txt finalize.patch: Redo iteration logic in finalize_garbage(). finalize2.patch: Cleaner patch, but same idea. finalize3.patch: Restore incref/decref pair. finalize4.patch: Typo repair and minor improvements xxx.py: Self-contained (no imports) crasher finalize42.patch: Code changes + new test_gc.py test.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/tim-one'
closed_at = <Date 2014-05-08.22:46:10.935>
created_at = <Date 2014-05-05.11:59:58.233>
labels = ['type-crash']
title = 'Segfault in gc with cyclic trash'
updated_at = <Date 2014-05-10.08:55:38.890>
user = 'https://bugs.python.org/inglesp'

bugs.python.org fields:

activity = <Date 2014-05-10.08:55:38.890>
actor = 'asvetlov'
assignee = 'tim.peters'
closed = True
closed_date = <Date 2014-05-08.22:46:10.935>
closer = 'tim.peters'
components = []
creation = <Date 2014-05-05.11:59:58.233>
creator = 'inglesp'
dependencies = []
files = ['35152', '35165', '35166', '35167', '35180', '35182', '35187']
hgrepos = []
issue_num = 21435
keywords = ['patch']
message_count = 32.0
messages = ['217918', '217931', '217936', '217956', '217959', '217960', '217961', '217962', '217963', '217964', '217968', '217971', '218028', '218035', '218036', '218037', '218038', '218041', '218042', '218043', '218072', '218089', '218091', '218094', '218115', '218116', '218125', '218134', '218138', '218194', '218205', '218214']
nosy_count = 10.0
nosy_names = ['gvanrossum', 'tim.peters', 'pitrou', 'vstinner', 'larry', 'tim.golden', 'asvetlov', 'python-dev', 'inglesp', 'Guido.van.Rossum']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue21435'
versions = ['Python 3.4', 'Python 3.5']

[inglesp]

The following code causes a segfault when run under Python3.4+ on OSX10.9.

# segfaulter.py
import asyncio
 
class A:
    pass
 
class B:
    def __init__(self, future):
        self.future = future
 
    def __del__(self):
        self.a = None
 
@asyncio.coroutine
def do_work(future):
    a = A()
    b = B(asyncio.Future())
 
    a.b = b
    b.a = a
 
    future.set_result(None)
 
future = asyncio.Future()
asyncio.Task(do_work(future))
loop = asyncio.get_event_loop()
loop.run_until_complete(future)

It does matter that the Future is passed to b's __init__ method.

It doesn't matter whether the Future has been resolved.

Attached is the problem report generated by OSX on the crash.

[tjguk]

I can confirm that this crashes on Windows as well. Failure actually occurs in gcmodule.c:finalize_garbage. Adding Guido as it looks as it's tied to asyncio.

[gvanrossum]

Confirmed too (OSX 10.9 again, CPython 3.4 or 3.5; but it doesn't crash with CPython 3.3). There is no C code in asyncio, so I'm not sure how asyncio can be directly responsible for this crash. Probably some of the GC improvements have an edge case that is triggered by the example program. Adding Antoine and Victor, they probably understand that code better.

[pitrou]

Here is the gdb backtrace. The gc variable is equal to NULL.

0x000000000043d254 in finalize_garbage (collectable=0x7fffffffdc40, old=0x8fdae0 <generations+64>)
at Modules/gcmodule.c:788
788 if (!_PyGCHead_FINALIZED(gc) &&
(gdb) bt
#0 0x000000000043d254 in finalize_garbage (collectable=0x7fffffffdc40, old=0x8fdae0 <generations+64>)
at Modules/gcmodule.c:788
#1 0x000000000043dac0 in collect (generation=2, n_collected=0x7fffffffdca8, n_uncollectable=0x7fffffffdcb0, nofail=0)
at Modules/gcmodule.c:1009
#2 0x000000000043dffc in collect_with_callback (generation=2) at Modules/gcmodule.c:1128
#3 0x000000000043eda0 in PyGC_Collect () at Modules/gcmodule.c:1604
#4 0x000000000041f332 in Py_Finalize () at Python/pythonrun.c:607
#5 0x000000000043c401 in Py_Main (argc=2, argv=0x980020) at Modules/main.c:788
#6 0x000000000041af96 in main (argc=2, argv=0x7fffffffdfc8) at ./Modules/python.c:69

(gdb) p gc
$1 = (PyGC_Head *) 0x0

[gvanrossum]

So should we just add

if (!gc)
    break;

at the top of the for-loop body? That prevents the crash for me. But why is it needed?

[tim-one]

Guido, that's no good. The outer loop is traversing a doubly-linked circular list, and it should be flatly impossible for gc to ever be NULL - the list structure is insanely damaged if any gc_next or gc_prev field reachable from it is NULL (gc always comes from a gc_next or gc_prev field)

I'd wonder whether the collectable argument passed in was NULL to begin with, but Antoine's traceback shows that it's not.

So, like most crashes in gc, we're just seeing the end symptom of something that went wrong long before. Guarding against gc != NULL is just hiding this particular symptom.

[tim-one]

Thought question: suppose finalize_garbage() is called with a collectable list all of whose members are in fact going to be destroyed?

I don't see how the loop iteration logic could reliably work then. For concreteness, suppose there's only object - A - in the list. It's a circular list so gc starts as A. A is finalized, we see it's refcount is 1, gc = gc->gc.gc_prev sets gc to A again, and A is destroyed by the Py_DECREF. We go back to the top of the loop, and then gc = gc->gc.gc_next reads up trash (free'd) memory.

Or so it seems to me ;-)

[tim-one]

Noting that in a Windows debug build, at death gc is 0xdbdbdbdb, so we are in reading up free'd memory (0xdb is pymalloc's "dead byte" marker).

[tim-one]

Also noting that the loop "looks funny" because it appears never to process the first element in the input list (unless the input list contains only one element). That is, the loop starts by processing the second element in the list, and exits as soon as gc makes it back to the first element in the list.

[tim-one]

Ah, fudge - I think I forgot that these circular lists also have dummy heads, in which case it's A Good Thing "the first element" is skipped, and it should be impossible for one to become physically empty (the dummy header should always survive intact). Never mind ;-)

[tim-one]

Sorry for the earlier noise. I'm fighting a flu and my head is mush :-(

Anyway, this doesn't look obvious. We get to this point:

            if (Py_REFCNT(op) == 1) {
                /* op will be destroyed */
                gc = gc->gc.gc_prev;
            }

and op is the type object for class B. gc gets set to the previous object, a list. Everything looks fine at this point. But when we get back from:

            Py_DECREF(op);

the list's gc.gc_next field has been overwritten with NULL. That's why gc gets set to NULL on the next trip through the loop.

I spaced out stepping through all the type deallocation code, and didn't find exactly when the list's gc_next is overwritten. The list's gc_prev is still fine. Perhaps some code called _PyObject_GC_UNTRACK on the list object (which NULLs out the gc_next pointer but not the gc_prev pointer).

[vstinner]

Similar(?) issue bpo-20526:
Modules/gcmodule.c:379: visit_decref: Assertion `((gc)->gc.gc_refs >> (1)) != 0' failed.

[tim-one]

A bit more info: recall that, when deleting a type object (for class B), the previous (list) object's gc_next got overwritten with NULL. The new info: its (the list object's) gc_refs also changed from GC_TENTATIVELY_UNREACHABLE to GC_UNTRACKED, That the object became untracked is wholly consistent with that its gc_next became NULL but not its gc_prev.

I haven't tracked it down all the way to the offending code, but I wonder whether that's worth the bother. What reason do we have to believe that

            Py_DECREF(op);

CANNOT cause other objects in the collectable list to become recognized as trash too? We're in cyclic trash, and one decref can trigger an arbitrary number of other objects to become trash.

So I'll attach a patch that doesn't assume the Py_DECREF is harmless, by moving collectable objects one at a time to a temporary list, and then - at the end - moves all survivors back to collectable. That makes the error go away, but I can't be certain it's address the real problem (since I stopped looking for the code that messed with the list as a side effect of doing a decref on the type object for class B).

[tim-one]

Attaching a marginally cleaner version of the patch, with comments.

I think it's clear this addresses _some_ real fatal problems, but they're rare: for a problem to show up, it has to be the case that finalize() reduces the refcount of the current object to 0, and that this also causes "the immediately previous" object in the gc list to become free'd, or at least untracked from gc. Then the next "current object" will be taken from an insane gc_next member, and all bets are off.