classification
Title: interpreter crash when multiplying large lists
Type: Stage:
Components: Interpreter Core Versions: Python 2.5
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: nnorwitz Nosy List: agthorr, christian.heimes, gvanrossum, jorend, nnorwitz
Priority: high Keywords: patch

Created on 2007-04-20 22:17 by agthorr, last changed 2007-11-12 20:07 by gvanrossum. This issue is now closed.

Files
File name Uploaded Description Edit
list_repeat.patch agthorr, 2007-04-20 22:17 patch to fix overflows in list_repeat and list_inplace_repeat
list_repeat.patch agthorr, 2007-04-21 03:55 revised patch to fix overflows in list_repeat and list_inplace_repeat
list_repeat.patch agthorr, 2007-05-16 14:47 revised patch that includes test case
Messages (13)
msg52496 - (view) Author: Daniel Stutzbach (agthorr) Date: 2007-04-20 22:17
Here's a succinct summary of the problem:

>>> x = [0] * 2**20
>>> x *= 2**20
Segmentation fault (core dumped)

>>> x = [0] * 2**20
>>> x * 2**20
[]
>>>

The problem is that list_repeat()'s check for an overflow is flawed, and list_inplace_repeat() doesn't check at all.  Attached is a patch that adds a correct check to both functions.  With the patch, both variations throw a MemoryError exception.  The patch is against Python 2.5, but should also fix 2.5.1/2.6/3.0.
msg52497 - (view) Author: Jason Orendorff (jorend) Date: 2007-04-20 22:41
Yes, I see it.  Patch looks good.  I haven't tested it.
msg52498 - (view) Author: Neal Norwitz (nnorwitz) * (Python committer) Date: 2007-04-21 03:04
Thanks for the patch!

Can you add a test case for both conditions?
msg52499 - (view) Author: Daniel Stutzbach (agthorr) Date: 2007-04-21 03:55
Sort of.  Below is a test for 32-bit architectures.  Unfortunately, on architectures where Py_ssize_t is a 64-bit integer, the multiplication won't overflow and the test really will try to build a list with 2**32 items (which most likely will eventually raise a MemoryError, but it will take a LONG time!).  This is probably undesirable.  Is there a way to skip this test for non-32-bit architectures?

One way would be to only perform the test if sys.maxint <= 2**31.

Below is a test that can be added to seq_tests.py:

    def test_bigrepeat(self):
        x = self.type2test([0])
        x *= 2**16
        self.assertRaises(MemoryError, x.__mul__, 2**16)
        self.assertRaises(MemoryError, x.__imul__, 2**16)

While writing the test I found a bug in my patch for the case where the list is already size 0.  New patch attached.
File Added: list_repeat.patch
msg52500 - (view) Author: Neal Norwitz (nnorwitz) * (Python committer) Date: 2007-04-21 04:14
You could always check the value of sys.maxint.  The test_bigrepeat below fails quickly on a 64-bit box if you don't have enough memory. :-)  If you calculated 16 in the __mul__ calls based on sys.maxint, wouldn't that do what you want?

Perhaps something like:

reasonable_exp = 16
x *= 2 ** reasonable_exp
overflow_exp = int(math.log(sys.maxint, 2)) + 1 - reasonable_exp
self.assertRaises(MemoryError, x.__mul__, 2**overflow_exp)
msg52501 - (view) Author: Daniel Stutzbach (agthorr) Date: 2007-04-21 13:29
Yes, I realized the same thing while staring off into space before getting out of bed this morning. :-)

Here's a simpler version:

x = [0,0,0,0]
self.assertRaises(MemoryError, x.__mul__, sys.maxint/2+1)
self.assertRaises(MemoryError, x.__imul__, sys.maxint/2+1)
msg52502 - (view) Author: Daniel Stutzbach (agthorr) Date: 2007-05-15 19:25
I just noticed that my last suggestion makes test_tuple fail because tuple's don't support __imul__.  Here's a revised suggestion:

    def test_bigrepeat(self):
        x = self.type2test([0])
        x *= 2**16
        self.assertRaises(MemoryError, x.__mul__, 2**16)
        if hasattr(x, '__imul__'):
            self.assertRaises(MemoryError, x.__imul__, 2**16)

msg52503 - (view) Author: Neal Norwitz (nnorwitz) * (Python committer) Date: 2007-05-16 06:34
Daniel, could you incorporate the tests and the fix to listobject.c into a single patch file?  I can then apply that.  Thanks!
msg52504 - (view) Author: Daniel Stutzbach (agthorr) Date: 2007-05-16 14:47
New patch with test case attached.
File Added: list_repeat.patch
msg57216 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2007-11-07 18:52
Shouldn't this be fixed before 2.5.2 goes out?
msg57337 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2007-11-09 22:08
Python 2.5 still seg faults.

Python 2.6 and 3.0 are raising a memory error. However I'm unsure if the
memory error is also raised in a plain build. I've just Py_DEBUG builds
of 2.6 and 3.0 around.
msg57421 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2007-11-12 19:28
Python 2.6 (trunk) is raising a MemoryError in a non-debug build, too.
The problem is fixed in 2.6 and 3.0.
msg57424 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2007-11-12 20:07
Fixed in 2.5 branch (to be released with 2.5.2). Unit test added to 2.6
(trunk).
History
Date User Action Args
2007-11-12 20:07:10gvanrossumsetstatus: open -> closed
resolution: accepted
messages: + msg57424
2007-11-12 19:28:53christian.heimessetmessages: + msg57421
versions: - Python 2.6, Python 3.0
2007-11-09 22:08:52christian.heimessetnosy: + christian.heimes
messages: + msg57337
versions: + Python 2.6, Python 2.5, Python 3.0
2007-11-07 18:52:59gvanrossumsetpriority: normal -> high
assignee: nnorwitz
messages: + msg57216
nosy: + gvanrossum
2007-04-20 22:17:46agthorrcreate