#13 kjbuckets apparently corrupts memory

closed-invalid
nobody
None
5
2002-07-10
2002-06-29
Anonymous
No

I have some proprietary code which I wanted to convert
to use kjbuckets (rather than sorted Python lists with
slow pure-Python union and intersection operations).
The code appeared to work fine very briefly, but then
the program started hanging when trying to take the
repr() of a short list of strings. gdb revealed that
it was spending a lot of time trying to append a
366779-character string beginning with a '[' and a nul,
as if the length field of that string object had been
overwritten by a wild pointer.

More detail if I can post this.

- kragen@pobox.com

Discussion

  • Logged In: NO

    The promised additional detail: the application has very
    limited interaction with kjbuckets. It is building several
    thousand kjSets, each starting with a list of a single
    integer, and then adding more integers to them with the .add
    method; all the integers are in the range 0 to 60000. The
    kjSets vary in final size from one element to several tens
    of thousands of elements.

    The problem happens even if construction of all these kjSets
    is the *only* kjbuckets interaction we have.

    This is with Python 2.1.1 on Linux.
    The application also uses NumPy and a very small C extension
    I wrote, either of which could actually be the culprit;
    however, I haven't seen any problems like this before adding
    kjbuckets to the mix, and NumPy is very widely used and, I
    hope, debugged, while my C extension is very simple and not
    likely to be buggy in this fashion.
    My guess on the 366779-character string is that it is
    actually the "[" string that list_repr uses to produce
    representations of lists; because PyString_FromString keeps
    a table of all the one-character strings that have been
    created, this string has been sitting around for a long
    time, so there is a large time window during which it could
    have been corrupted.
    The application runs under Zope, so I'm not really sure how
    to run the actual application under gdb, and unsurprisingly,
    if I import and run the same application code in an
    interactive Python shell, it doesn't manifest the same
    problem. Perhaps the same memory corruption is happening
    but affecting something else.

    So, anyway, I don't expect anybody to investigate this right
    now --- it's not specific enough to be reproducible, and
    it's not even certain that it's in kjbuckets. But if
    someone runs into this problem in the future, perhaps this
    will be helpful.

     
  • Logged In: NO

    This was all a big mistake. I'm so embarrassed. Resolve
    this bug! It wasn't kjbuckets at all.

    For those curious about how I could possibly be SO DUMB, the
    statements where the program would begin to hang were
    actually raising exceptions; Zope was handling them by
    generating a traceback in HTML, and rather than the standard
    traceback, it was using cgitb to produce a traceback. cgitb
    includes abbreviated versions of the repr's of variables
    mentioned on any line in the traceback; some of these
    variables were NumPy arrays, which have O(N^2) repr
    functions. And gdb was showing me only the first character
    of the strings --- they weren't the "[" string after all,
    but representations of Numeric arrays being built up item by
    item.
    Hope this is good for a laugh or two. Sorry to have wasted
    the time of the Gadfly developers with this bogus bug report.

     
  • Richard Jones
    Richard Jones
    2002-07-10

    • status: open --> closed-invalid