classification
Title: Qsort function misuse in typeobject.c
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.1, Python 3.2, Python 3.3, Python 2.7, Python 2.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: benjamin.peterson, python-dev, zhalas
Priority: normal Keywords: patch

Created on 2013-04-01 12:49 by zhalas, last changed 2013-04-07 13:53 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
python_2.7_fix_slot_sorting_v1.patch zhalas, 2013-04-07 01:43 review
Messages (5)
msg185738 - (view) Author: Zbigniew Halas (zhalas) Date: 2013-04-01 12:49
Comparison function slotdef_cmp in  Objects/typeobject.c is based on the assumption that qsort may be stabilised by taking memory addresses of compared objects into consideration. This assumption is not guaranteed by the C standard and may not always be true, like for example in the case of qsort implemented as a typical quicksort.
Sometimes it may be even more harmful, as some implementations may be unhappy about comparison function changing its value just because an element was moved to another memory location (I discovered this problem while porting Python to HelenOS, where this comparison function caused qsort to enter infinite recursion).

The actual function:

/* Comparison function for qsort() to compare slotdefs by their offset, and
   for equal offset by their address (to force a stable sort). */
static int
slotdef_cmp(const void *aa, const void *bb)
{
    const slotdef *a = (const slotdef *)aa, *b = (const slotdef *)bb;
    int c = a->offset - b->offset;
    if (c != 0)
        return c;
    else
        /* Cannot use a-b, as this gives off_t,
           which may lose precision when converted to int. */
        return (a > b) ? 1 : (a < b) ? -1 : 0;
}
msg185773 - (view) Author: Roundup Robot (python-dev) Date: 2013-04-01 21:43
New changeset 9431a092b708 by Benjamin Peterson in branch '3.3':
list slotdefs in offset order rather than sorting them (closes #17610)
http://hg.python.org/cpython/rev/9431a092b708

New changeset 96c0efe93774 by Benjamin Peterson in branch 'default':
merge 3.3 (#17610)
http://hg.python.org/cpython/rev/96c0efe93774
msg185774 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2013-04-01 21:46
Thanks for the report. I fixed the 3.3 and 3.4 branches. If you felt motivated to do the associated shuffling around in 2.7, I would accept a patch.
msg186175 - (view) Author: Zbigniew Halas (zhalas) Date: 2013-04-07 01:43
Thank you for the fix, attaching a patch for 2.7.
msg186209 - (view) Author: Roundup Robot (python-dev) Date: 2013-04-07 13:53
New changeset eaff15532b3c by Benjamin Peterson in branch '2.7':
list slotdefs in offset order rather than sorting them (closes #17610)
http://hg.python.org/cpython/rev/eaff15532b3c
History
Date User Action Args
2013-04-07 13:53:57python-devsetstatus: open -> closed

messages: + msg186209
2013-04-07 11:04:00georg.brandlsetstatus: closed -> open
2013-04-07 01:43:02zhalassetfiles: + python_2.7_fix_slot_sorting_v1.patch
keywords: + patch
messages: + msg186175
2013-04-01 21:46:10benjamin.petersonsetnosy: + benjamin.peterson
messages: + msg185774
2013-04-01 21:43:44python-devsetstatus: open -> closed

nosy: + python-dev
messages: + msg185773

resolution: fixed
stage: resolved
2013-04-01 12:49:02zhalascreate