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.

Yes, I see it.  Patch looks good.  I haven't tested it.

Thanks for the patch!

Can you add a test case for both conditions?

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

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)

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)

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)

Daniel, could you incorporate the tests and the fix to listobject.c into a single patch file?  I can then apply that.  Thanks!

New patch with test case attached.
File Added: list_repeat.patch

Shouldn't this be fixed before 2.5.2 goes out?

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.

Python 2.6 (trunk) is raising a MemoryError in a non-debug build, too.
The problem is fixed in 2.6 and 3.0.

Fixed in 2.5 branch (to be released with 2.5.2). Unit test added to 2.6
(trunk).