crash appending list and namedtuple

[benrg]

BPO	8847
Nosy	@loewis, @birkenfeld, @rhettinger, @terryjreedy, @jcea, @atsuoishimoto, @amauryfa, @ncoghlan, @pitrou, @vstinner, @jackdied, @tjguk, @merwok, @alex, @bitdancer, @briancurtin, @skrah, @meadori
Files	issue8847.diff issue8847-3.2.diff issue8847-3.3.diff

^{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 = None
closed_at = <Date 2012-08-01.09:13:02.819>
created_at = <Date 2010-05-28.22:53:45.970>
labels = ['interpreter-core', 'deferred-blocker', 'library', 'OS-windows', 'type-crash']
title = 'crash appending list and namedtuple'
updated_at = <Date 2012-08-01.13:32:32.136>
user = 'https://bugs.python.org/benrg'

bugs.python.org fields:

activity = <Date 2012-08-01.13:32:32.136>
actor = 'loewis'
assignee = 'none'
closed = True
closed_date = <Date 2012-08-01.09:13:02.819>
closer = 'loewis'
components = ['Interpreter Core', 'Library (Lib)', 'Windows']
creation = <Date 2010-05-28.22:53:45.970>
creator = 'benrg'
dependencies = []
files = ['26623', '26633', '26634']
hgrepos = []
issue_num = 8847
keywords = ['patch']
message_count = 42.0
messages = ['106695', '106720', '107103', '107108', '107111', '107112', '107115', '107116', '107117', '107119', '107120', '107124', '107147', '130233', '166907', '166908', '166909', '166929', '166935', '166936', '166942', '166943', '166946', '166954', '166964', '166969', '166971', '167009', '167026', '167033', '167036', '167037', '167057', '167062', '167063', '167098', '167100', '167101', '167106', '167111', '167120', '167127']
nosy_count = 21.0
nosy_names = ['loewis', 'georg.brandl', 'rhettinger', 'terry.reedy', 'jcea', 'ishimoto', 'amaury.forgeotdarc', 'ncoghlan', 'pitrou', 'vstinner', 'jackdied', 'tim.golden', 'eric.araujo', 'mrabarnett', 'alex', 'r.david.murray', 'brian.curtin', 'skrah', 'meador.inge', 'benrg', 'python-dev']
pr_nums = []
priority = 'deferred blocker'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue8847'
versions = ['Python 3.2', 'Python 3.3']

[benrg]

c:\>python
  Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on win32
  Type "help", "copyright", "credits" or "license" for more information.
  >>> from collections import namedtuple
  >>> foo = namedtuple('foo', '')
  >>> [1] + foo()

At this point the interpreter crashes. Also happens when foo has named arguments, and in batch scripts. foo() + [1] throws a TypeError as expected. [] + foo() returns (). The immediate cause of the crash is the CALL instruction at 1E031D5A in python31.dll jumping into uninitialized memory.

[bitdancer]

I can't reproduce this on either 3.1.2 or py3k trunk.

[terryjreedy]

Running the exact same binary on winxp with an amd athlon processor,
I *did* get a crash after about 5 seconds. "python.exe has encountered a problem and needs to close. We are sorry for the inconvenience."
Trying again with IDLE instead of the command window, I get the same message (for pythonw instead of python) and the shell restarts when I close the message.

Even though foo()+[1] correctly raises a TypeError, the reverse [1] + foo() very bizarrely produces a length 1 tuple whose bizarre member is supposedly an instance of a empty list [] with length 1

from collections import namedtuple
foo = namedtuple('foo', '')
a = [1] + foo()
b=a[0]
print (type(a), len(a), type(b), len(type(b)), type(type(b)))

# <class 'tuple'> 1 [] 1 <class 'list'>

([2]+foo() produces same output)

Other than the above, any attempt to do anything with b or type(b) that I tried crashes. I presume that this is due to attribute lookups on the invalid type(b) (or something like that), which type(b) must bypass. In particular, the OP's crash is due to trying to print the tuple which tries to print its member which looks for type(b).__str__ which crashes.

To anyone: investigating crashers like this is a lot easier with IDLE and an edit window than with the interactive command window.

[terryjreedy]

More experiments

from collections import namedtuple
foo = namedtuple('foo', '')
a = [] + foo()
print (a, type(a), len(a))
# () <class 'tuple'> 0

ie, a standard empty tuple, whereas
a = [1,1] + foo()
crashes immediately. So the behavior of list()+namedtuple depends on the length of the list.

There are also some funny interactions. Adding
try:
a = foo()+[]
except TypeError:
print("correct TypeError")

after the 'foo = ' line in my original 5 line example causes the final print to crash, whereas adding the same 4 lines to the 4 line example at the beginning of this message does not obviously change anything.

David, since you omitted all details, I wonder if you tested in batch mode, as I did, and hence never tried to print the malformed object, or used different OS or hardware.

[jackdied]

I can't reproduce on 3k trunk with Ubuntu 10.04, gcc 4.4.3

namedtuples are just a subclass of tuple with only two dunder methods defined (a plain __new__ with empty __slots__). Can you provoke the same behavior with plain tuples, or a subclass of tuple that looks like one of these?

class Crasher(tuple): pass

class Crasher(tuple):
  __slots__ = ()

class Crasher(tuple):
  def __new__(cls,): return tuple.__new__(cls,)
  __slots__ = ()

[terryjreedy]

Substituting
foo = tuple()
TypeError: can only concatenate list (not "tuple") to list

class Crasher(tuple): pass
foo = Crasher()
a = [1] + foo
b=a[0]
print (type(a), len(a), type(b), len(type(b)), type(type(b)))

<class 'tuple'> 1 [] 1 <class 'list'>

as before, so namedtuple is not, in particular, the culprit.
Other two Crasher versions do the same. I also get a delayed pythonw error message after the print that does not cause the shell to restart. This may partly be an IDLE artifact.

[jackdied]

Two more probes:

1. does it also have the same strange/crashy behavior when you subclass list and concat that to a tuple?

2. does dropping the optimization level down to -O help? This has "compiler quirk" written all over it. The C-code for list and tuple concat are almost identical, and both start with a type check.

[terryjreedy]

"can't reproduce" does not inform as to what *did* happen with which code.

More experiments:
foo = str()
TypeError: can only concatenate list (not "str") to list

class s(str): pass
foo = s()
TypeError: Can't convert 'list' object to str implicitly

Why is it trying to do that? Of course, the interpreter can (implicitly) convert list to tuple, which must be what happens in OP example.

The subclasses of tuple and str do not gain an __radd__ method. If we add one

class s(str):
    def __radd__(s,o): print('in radd, type(o)')
foo = s()
a = [1] + foo
# prints "in radd <class 'list'>"

no implicit conversion is done.

Reversing tuple and list

class Crasher(list): pass
a = () + Crasher() # or Crasher([1])
print(a, type(a), len(a))
#[] <class 'list'> 0 # or [1] <class 'list'> 1

whereas
a = (1,) + Crasher()
crashes, so not completely symmetrical

[terryjreedy]

1. answered before you asked (yes, similar)
2. (same thought) I am using PSF windows installer, however that was prepared. Martin?

[jackdied]

if the id() of the left operand is identical to the id() of the first element in the result it would strongly support compiler skulldugerry.

class Crasher(tuple): pass
foo = Crasher()
x = [1]
a = x + foo
b=a[0]

if id(b) == id(x):
  raise Exception("It's the C compiler what did it!")

The only way I can think of this coming about is the right_op getting new'd and then .extend'ing(left_op). That extend() must be going batsh*t and inserting the left_op instead of it's contained items. The C-code for extend is more fiddly than the code for concatenation so there is more room for the compiler to generate bad code.

[terryjreedy]

Good try, but for one run, the ids of foo, x, a, and b are
>>> 
15719440 15717880 15273104 12266976

[loewis]

The binaries get compiled with the PGInstrument/PGUpdate configurations.

[mrabarnett]

I've just found that:

[1] + foo()

crashes, but:

[1].__add__(foo())

gives:

    Traceback (most recent call last):
      File "<pyshell#25>", line 1, in <module>
        [1].__add__(foo())
    TypeError: can only concatenate list (not "foo") to list

(IDLE on Windows XP)

[benrg]

The bug is still present in 3.2.

[pitrou]

For some reasons I was able to reproduce under 64-bit Windows with the 3.3b1 official build, but neither with my own VS9.0-compiled build, nor with the 3.2 official build.

To reproduce:

>>> class T(tuple): pass
...
>>> t = T((1,2))
>>> [] + t
(1, 2)
>>> [3,] + t
# crash

I tried to use the debugging symbols but it doesn't help a lot. The primary issue seems to be that the concatenation doesn't raise TypeError, and instead constructs an invalid object which then makes PyObject_Repr() crash.

Also, it is not the Python compiler, the same thing happens with constructor calls:

>>> list() + T([1,2])
(1, 2)
>>> list((3,)) + T([1,2])
# crash

And no it doesn't happen with list subclasses:

>>> class L(list): pass
...
>>> class T(tuple): pass
...
>>> L([]) + T([1,2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate list (not "T") to list
>>> [] + T([1,2])
(1, 2)

Also, directly calling the __add__ method doesn't trigger the issue, but operator.add does:

>>> l + T([1,2])
(1, 2)
>>> operator.add(list(), T([1,2]))
(1, 2)
>>> list().__add__(T([1,2]))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate list (not "T") to list

[pitrou]

The exact same issue happens when concatenating a list subclass to a tuple:

>>> () + L([1,2])
[1, 2]
>>> (3,) + L([1,2])
# crash

Also, note that in this case a list is returned, not a tuple despite the first operand being a tuple. Conversely:

>>> [] + T((1,2))
(1, 2)

A tuple is returned, not a list. Which is exactly what happens when calling T.__add__:

>>> T.__add__((), T((1,2)))
(1, 2)

My intuition is that the issue is somewhere in binary_op1() (called by PyNumber_Add) in abstract.c. I can't go much further since my own builds don't exhibit the issue.

(in the end, chances are it's a MSVC compiler bug)

[birkenfeld]

Raising priority. This should be investigated properly before 3.3 final.

[skrah]

I can reproduce this exclusively with the pgupdate build:

msbuild PCbuild\pcbuild.sln /p:Configuration=PGInstrument /p:Platform=win32
msbuild PCbuild\pcbuild.sln /p:Configuration=PGUpdate /p:Platform=win32

PCbuild\Win32-pgo\python.exe
Python 3.3.0b1 (default, Jul 30 2012, 23:45:42) [MSC v.1600 32 bit (Intel)] on win32                          
Type "help", "copyright", "credits" or "license" for more information.                                        
>>> from collections import namedtuple                                                                        
>>> foo = namedtuple('foo', '')                                                                               
>>> [1] + foo()                                                                                               
                                  

Interpreter exits silently here. So it could be either an optimizer
bug or it's a Python bug exposed by the optimizer making draconian
assumptions at the highest level (c.f. clang exposing overflows).

[vstinner]

When Python is compiled by Visual Studio 10 in PGUpdate mode, duplicated functions are merged to become the same unique function. The C code of wrap_binaryfunc() and wrap_binaryfunc_l() functions is the same and so both functions get the same address.

For "class List(list): pass", type_new() fills type->tp_as_number->nb_add to list_concat() because "d->d_base->wrapper == p->wrapper" is True whereas it should be False (wrap_binaryfunc vs wrap_binaryfunc_l).

A workaround is to use a different code for wrap_binaryfunc() and wrap_binaryfunc_l(). A real fix is to use something else than the address of the wrapper to check the type of the operator (left, right, or the 3rd type).

[ncoghlan]

Nice detective work, Victor.

Can we turn that particular optimisation off? We use function addresses for identification purposes in many more places than just this one. Having the compiler merge different pointers just because the functions happen to have the same implementation is simply *not cool* from the point of view of the CPython code base.

[meadori]

Nice work Victor.

Can we turn that particular optimisation off?

/OPT:NOICF is probably what we are looking for [1]:

"""
/OPT:ICF can result in the same address being assigned to different functions or read only data members (const variables compiled with /Gy). So, /OPT:ICF can break a program that depends on the address of functions or read-only data members being different. See /Gy (Enable Function-Level Linking) for more information.
"""

Now it makes sense that this only crops up with the PGO builds -- those are the only ones where we link with /OPT:ICF.

Can someone try out this option? I would, but I don't have a Windows box handy.

[1] http://msdn.microsoft.com/en-us/library/bxwfs976.aspx

[loewis]

Having the compiler merge different pointers just because the functions
happen to have the same implementation is simply *not cool* from the
point of view of the CPython code base.

I believe the compiler is completely entitled to do so according to the C language definition. There is no guarantee that two different functions have two different addresses as long as calling the function pointer does the same thing according to the as-if rule.

So we really need to fix Python, not work-around in the compiler. There may be many more compilers which use the same optimisation. Python relying on undefined behavior is simply *not cool*.

[loewis]

OTOH, 6.5.9p6 says

"Two pointers compare equal if and only if both are null pointers, both
are pointers to the same object (including a pointer to an object and a
subobject at its beginning) or function [...]"

This is probably meant to imply that pointers to different functions must not compare equal.

So if this is determined to be a compiler bug, the most natural conclusion is to stop using PGI/PGO entirely.

[meadori]

This is probably meant to imply that pointers to different functions must
not compare equal.

I think so. Also, in our case the functions have different names, therefore
they can't be the "same" function.

So if this is determined to be a compiler bug, the most natural conclusion
is to stop using PGI/PGO entirely.

I think it is non-conformant behavior. Microsoft warns about it in their
documentation, but they don't go as far to say it is non-conformant.

Also, this isn't really a problem with PGO. AFAICT, it is the COMDAT folding
optimization in the linker. That optimization just happens to be enabled on
our PGO configurations.

Do we even use PGO to the fullest extent? Does someone actually build an
instrumented Python, run training inputs on it, and then rebuild with the
training data to take advantage of the profile-guided optimizations? If not,
then I doubt PGO is buying us anything anyway.

Also, PGO is only available on the Premium and Ultimate versions of VC++ [1].
I noticed when building with VC++ 2010 Express on the PGI/PGO builds that it
warns about PGO not being available. I don't know what version we build our
Python release bits with.

[1] http://msdn.microsoft.com/en-us/library/hs24szh9.aspx

[vstinner]

I noticed when building with VC++ 2010 Express on the PGI/PGO
builds that it warns about PGO not being available.

Even if PGO is not available, wrap_binaryfunc() and wrap_binaryfunc_l() functions get the same address when Python is compiled in "PGUpdate" mode. (I tried Visual C++ 2010 Express).

The issue was seen at least with the following versions:

Python 3.1.2 (r312:79149, Mar 21 2010, 00:41:52) [MSC v.1500 32 bit (Intel)] on win32
Python 3.2 (which version exactly?)
Python 3.3b.01, MSVC v16.00 64 bits (AMD 64) on win32

So the issue was also reproduced with old Python versions compiled with Visual C++ 2008, and I'm not sure that the "ICF" optimization is only enabled in "Profile-Guided" (PG*) modes.

If we choose to change Visual Studio options instead of changing the mode, we may also try /Gy- option:
http://msdn.microsoft.com/en-us/library/xsa71f43.aspx

[loewis]

Do we even use PGO to the fullest extent? Does someone actually build an
instrumented Python, run training inputs on it, and then rebuild with the
training data to take advantage of the profile-guided optimizations?

Yes, I do, on every release of Python. The test set includes at the minimum
"Tools\pybench\pybench.py -n1 -C1 --with-gc". I used to also include
"Lib\test\regrtest.py". Now, some recently added tests have slowed this down
so much that this is not feasible anymore in PGI mode.

This issue wouldn't have been reported in the first place if this
feature wasn't
used; see also msg107124.

I don't mind just not doing it anymore; it speeds up the release process.

If not, then I doubt PGO is buying us anything anyway.

It was originally added because people reported measurable speedups when
profile-guided optimization is used, for VS 2008.

I noticed when building with VC++ 2010 Express on the PGI/PGO builds that it
warns about PGO not being available. I don't know what version we build our
Python release bits with.

I do, of course, have at least a professional edition of Visual Studio to make
the Python releases available from www.python.org. More specifically,
my VS 2008
installation is "Professional"; my VS 2010 installation is "Ultimate".

[skrah]

Martin v. L??wis <report@bugs.python.org> wrote:

> If not, then I doubt PGO is buying us anything anyway.

It was originally added because people reported measurable speedups when
profile-guided optimization is used, for VS 2008.

For libmpdec/64-bit I've measured huge speedups in the order of 50% (with
training data). This led me to believe that the main optimizations for
x64 are only available with PGO, perhaps as a distinguishing feature from
the Express versions.

[skrah]

Here's a patch based on the analysis. All test cases given here
now raise TypeError.

[terryjreedy]

I presume the previously crashing test cases should be added to the test suite, to detect reversion. Is there a method (faulthandler?) to keep tests going, or stop gracefully, when adding a once-crasher that could revert?

[pitrou]

Here's a patch based on the analysis. All test cases given here
now raise TypeError.

I think we want to add those tests to the test suite as well.

[skrah]

Antoine Pitrou <report@bugs.python.org> wrote:

I think we want to add those tests to the test suite as well.

What's a good place? Shall we just add one of the tests to test_tuple?

Also, the only person to run the tests with the PGO build will probably
be Martin just before the releases. :)

[pitrou]

Antoine Pitrou <report@bugs.python.org> wrote:
> I think we want to add those tests to the test suite as well.

What's a good place? Shall we just add one of the tests to test_tuple?

Sounds good. And another of them to test_list perhaps as well :)

Also, the only person to run the tests with the PGO build will probably
be Martin just before the releases. :)

True, but other people may still run them *after* the release.

[skrah]

New patches with tests for 3.2 and 3.3. For 3.2 I determined empirically
that EnableCOMDATFolding="1" (and not "0") turns on NOICF.

If anyone can confirm that this is the case or has a pointer to
the relevant vcproj docs, I'd be thrilled.

[loewis]

Also, the only person to run the tests with the PGO build will probably
be Martin just before the releases. :)

We could set up a buildbot slave which does PGO builds, provided somebody
volunteered an installation (including VS Pro), and somebody contributed
a build script that deviates from the regular build (perhaps including some
training on the PGI). This is a separate issue, of course.

[loewis]

If anyone can confirm that this is the case or has a pointer to
the relevant vcproj docs, I'd be thrilled.

http://msdn.microsoft.com/de-de/library/microsoft.visualstudio.vcprojectengine.vclinkertool.enablecomdatfolding(v=vs.90).aspx

http://msdn.microsoft.com/de-de/library/microsoft.visualstudio.vcprojectengine.optfoldingtype(v=vs.90).aspx

While the actual values for the XML schema aren't documented, I expect that
they have the numeric values that they have in C++ (i.e. optFoldingDefault=0,
optNoFolding=1, optFolding=2)

To confirm, just look up the setting in the UI.

[python-dev]

New changeset 5a8c5631463f by Martin v. Löwis in branch '2.7':
Issue bpo-8847: Disable COMDAT folding in Windows PGO builds.
http://hg.python.org/cpython/rev/5a8c5631463f

[python-dev]

New changeset 2638ce032151 by Martin v. Löwis in branch '3.2':
Issue bpo-8847: Disable COMDAT folding in Windows PGO builds.
http://hg.python.org/cpython/rev/2638ce032151

New changeset 029cde4e58c5 by Martin v. Löwis in branch 'default':
Issue bpo-8847: Disable COMDAT folding in Windows PGO builds.
http://hg.python.org/cpython/rev/029cde4e58c5

New changeset d3afe5d8a4da by Martin v. Löwis in branch 'default':
Issue bpo-8847: Merge with 3.2
http://hg.python.org/cpython/rev/d3afe5d8a4da

[loewis]

Thanks for the research and the fix!

[vstinner]

You didn't add any test for non regression??

[loewis]

You didn't add any test for non regression??

Please rephrase your question: what tests did I not add?
I did add the tests that Stefan proposed.

[vstinner]

Please rephrase your question: what tests did I not add?
I did add the tests that Stefan proposed.

Ah yes, you added new tests to Python 3.2 and 3.3, but no to Python
2.7. Why not adding these new tests to Python 2.7?

[loewis]

Ah yes, you added new tests to Python 3.2 and 3.3, but no to Python
2.7. Why not adding these new tests to Python 2.7?

The tests don't crash Python 2.7. So they are not useful as a test whether
the bug has been worked-around. I actually don't know how to test this
compiler
bug in Python 2.7 (except for writing specific C code that tries to trigger
the bug).