This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Segmentation fault with tuple + gc.collect()
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.1, Python 3.2, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: pitrou Nosy List: LambertDW, flox, pitrou, skrah
Priority: high Keywords: patch

Created on 2009-12-10 02:21 by LambertDW, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
issue7466.diff flox, 2009-12-10 17:38 Patch, apply to trunk and py3k
Messages (11)
msg96190 - (view) Author: David W. Lambert (LambertDW) Date: 2009-12-10 02:21
'''
    This brute [possibly a] solution to

    http://projecteuler.net/index.php?section=problems&id=159

    causes segmentation fault.


    $ p3 # an AMD 64 bit build.
    Python 3.1.1 (r311:74480, Oct  2 2009, 12:29:57) 
    [GCC 4.3.3] on linux2
    Type "help", "copyright", "credits" or "license" for more 
information.
    >>>


    The block between "load_primes" and "print(result)" can be written
    as a single statement using various comprehensions.  sum(max(...))
    The program does not seg-fault this way, but the result was wrong.
    I unrolled the code to fix my algorithm, disclosing the segmentation 
fault.
'''

import functools
import operator
import itertools
import array

PrimeQ = Primes = 'use load_primes(n) function'

def load_primes(n):
    global PrimeQ,Primes
    PrimeQ = sieve(1+n)
    Primes = array.array('L',(i for (i,Q,) in enumerate(PrimeQ) if Q))

def sieve(n):
    a = array.array('b',(True,))*n
    a[0] = a[1] = False
    for (i,j) in enumerate(a):
        if j:
            for k in range(i**2,n,i):
                a[k] = False
    return a

def PrimeRange(a):
    '''
        see "load_primes"
    '''
    n = 1+int(a**(1/2))
    for p in Primes:
        if n < p:
            raise StopIteration
        yield p

def PrimeFactor(a):
    '''
        see "load_primes"

        >>> load_primes(30)
        >>> print([PrimeFactor(x)for x in (6,7,)])
        [[2, 3], [7]]
    '''
    if (a < len(PrimeQ)) and PrimeQ[a]:
        return [a]
    for p in PrimeRange(a):
        (q,r,) = divmod(a,p)
        if not r:
            return [p]+PrimeFactor(q)
    return [a]

def product(a):
    return functools.reduce(operator.mul,a,1)

def digital_root(n):
    while 9 < n:
        n = sum(map(int,str(n)))
    return n

def partition(L, chain=itertools.chain):
    '''
        python recipe by Ray Hettinger
    '''
    s = L
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    return [[L[a:b] for (a,b) in zip(chain(first, div), chain(div, 
last))]
            for i in range(n) for div in itertools.combinations(middle, 
i)]





load_primes(1000)

s = 0
for n in range(2,10**6):
    factorizations = [
        [product(p)for p in group]for group in 
partition(PrimeFactor(n))]
    mx = 0
    for factorization in factorizations:
        digital_roots = tuple(map(digital_root,factorization))
        sdr = sum(digital_roots)
        mx = max(mx,sdr)
    s += mx

print('result!',s)
msg96191 - (view) Author: David W. Lambert (LambertDW) Date: 2009-12-10 02:40
Further isolation, following change removes segmentation fault: 

        digital_roots = tuple(map(digital_root,factorization))

becomes

        digital_roots = [digital_root(factor) for factor in 
factorization]
msg96197 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2009-12-10 11:17
Segfault confirmed on 64 bit Ubuntu, Python 3.2a0:

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7f5074dea6e0 (LWP 11665)]
0x000000000042111b in _PyTuple_Resize (pv=0x7fff7ce03b10, newsize=25) at
Objects/tupleobject.c:853
853             _PyObject_GC_UNTRACK(v);
msg96199 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-10 11:28
Yes, confirmed too. Both 3.1 and 3.2 are broken.

Minimal sequence to trigger the bug:

"""
~ $ ./python 
Python 3.2a0 (py3k:76743M, Dec 10 2009, 12:19:41) 
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.

"""
def m(i):
    if i == 10:
        return next(i for i in '0')

MAX_LOOP = 1<<10
t = range(11)
for i in range(MAX_LOOP):
  d = map(m, t)
  tup = tuple(d)

## python: Objects/tupleobject.c:853: _PyTuple_Resize:
## Assertion `g->gc.gc_refs != (-2)' failed.
msg96207 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-10 16:32
Fix is coming soon...

## Sample code:

import gc
tuple(gc.collect() for i in range(11))

## python: Objects/tupleobject.c:853: _PyTuple_Resize:
## Assertion `g->gc.gc_refs != (-2)' failed.


And Trunk is affected
msg96208 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-12-10 16:35
An even simpler way to reproduce:

>>> import gc
>>> def g(it):
...   for x in it:
...     gc.collect()
...     yield x
... 
>>> t = tuple(g(range(100)))
Erreur de segmentation


This is probably caused by the GC optimizations I introduced in trunk
and 3.1.
msg96209 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-12-10 16:35
Ok, you've been faster than me, flox :-)
msg96210 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-10 17:17
Well... here comes the patch.
msg96262 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-12-11 15:55
IMO it would be better to call _PyObject_GC_IS_TRACKED() explicitly
rather than rely on a subtle difference between the two APIs as in the
current patch.
msg96263 - (view) Author: Florent Xicluna (flox) * (Python committer) Date: 2009-12-11 16:45
Ok. It is here:
  http://bugs.python.org/file15520/issue7466.diff
msg96302 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-12-12 19:27
Committed, thanks!
History
Date User Action Args
2022-04-11 14:56:55adminsetgithub: 51715
2009-12-12 19:27:32pitrousetstatus: open -> closed
resolution: fixed
messages: + msg96302

stage: needs patch -> resolved
2009-12-11 19:21:09Arfreversettitle: Segmentation fault after about 20 seconds on lenovo T500 -> Segmentation fault with tuple + gc.collect()
2009-12-11 16:45:14floxsetmessages: + msg96263
2009-12-11 15:55:58pitrousetmessages: + msg96262
2009-12-10 17:39:00floxsetfiles: + issue7466.diff
2009-12-10 17:38:21floxsetfiles: - issue7466.diff
2009-12-10 17:17:52floxsetfiles: + issue7466.diff
keywords: + patch
messages: + msg96210
2009-12-10 16:35:35pitrousetmessages: + msg96209
2009-12-10 16:35:11pitrousetassignee: pitrou
messages: + msg96208
2009-12-10 16:32:31floxsetmessages: + msg96207
versions: + Python 2.7
2009-12-10 16:22:47pitrousetpriority: high
nosy: + pitrou

stage: needs patch
2009-12-10 11:28:03floxsetversions: + Python 3.2
nosy: + flox

messages: + msg96199

components: + Interpreter Core
2009-12-10 11:17:18skrahsetnosy: + skrah
messages: + msg96197
2009-12-10 02:40:58LambertDWsetmessages: + msg96191
2009-12-10 02:21:08LambertDWcreate