homepage

# Bug
# ---
# 
# static PyObject *
# combinations_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
# {
# ...
# 
# 1 indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
# ...
# 
# for (i=0 ; i<r ; i++)
# 2 indices[i] = i;
# 
# 1. if r=2^30, then r*sizeof(Py_ssize_t)=2^30*2^2=0 (modulo 2^32), so malloc
# allocates a 0 byte buffer
# 2. r=2^30>0, so we write well beyond the buffer's end
# 
# Crash
# -----
# 
# Breakpoint 1, combinations_new (type=0x83390c0 <combinations_type>, args=('AA', 1073741824), kwds=0x0)
# at ./Modules/itertoolsmodule.c:2343
# 2343 PyObject *pool = NULL;
# ...
# (gdb) n
# 2362 indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
# (gdb) print r
# 1ドル = 1073741824
# (gdb) print r*4
# 2ドル = 0
# (gdb) c
# Continuing.
# 
# Program received signal SIGSEGV, Segmentation fault.
# 0x0822f359 in combinations_new (type=0x83390c0 <combinations_type>, args=('AA', 1073741824), kwds=0x0)
# at ./Modules/itertoolsmodule.c:2369
# 2369 indices[i] = i;
# OS info
# -------
# 
# % ./python -V
# Python 3.4.1
# 
# % uname -a
# Linux ubuntu 3.8.0-29-generic #42~precise1-Ubuntu SMP Wed Aug 14 15:31:16 UTC 2013 i686 i686 i386 GNU/Linux
# 
 
import itertools as it
it.combinations("AA", 2**30)

New changeset 014886dae5c4 by Benjamin Peterson in branch '3.3':
detect overflow in combinations (closes #23366)
https://hg.python.org/cpython/rev/014886dae5c4
New changeset 2f73de7ffcf5 by Benjamin Peterson in branch '3.4':
merge 3.3 (#23366)
https://hg.python.org/cpython/rev/2f73de7ffcf5
New changeset 886559229911 by Benjamin Peterson in branch 'default':
merge 3.4 (#23366)
https://hg.python.org/cpython/rev/886559229911
New changeset fe203370c049 by Benjamin Peterson in branch '2.7':
detect overflow in combinations (closes #23366)
https://hg.python.org/cpython/rev/fe203370c049 

This commit (and three other) causes compiler warnings:
./Modules/itertoolsmodule.c: In function ‘product_new’:
./Modules/itertoolsmodule.c:2025:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (repeat > PY_SSIZE_T_MAX/sizeof(Py_ssize_t) ||
 ^
./Modules/itertoolsmodule.c:2026:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 nargs > PY_SSIZE_T_MAX/(repeat * sizeof(Py_ssize_t))) {
 ^
./Modules/itertoolsmodule.c: In function ‘combinations_new’:
./Modules/itertoolsmodule.c:2371:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
 ^
./Modules/itertoolsmodule.c: In function ‘cwr_new’:
./Modules/itertoolsmodule.c:2716:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
 ^
./Modules/itertoolsmodule.c: In function ‘permutations_new’:
./Modules/itertoolsmodule.c:3061:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if (n > PY_SSIZE_T_MAX/sizeof(Py_ssize_t) ||
 ^
./Modules/itertoolsmodule.c:3062:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
 ^
May be use PyMem_New instead of PyMem_Malloc?

And with this patch an OverflowError in tests should be replaced with (OverflowError, MemoryError). Updated patch also fixes other bugs in itertools tests.

lgtm

New changeset 356ed025dbae by Serhiy Storchaka in branch '3.3':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/356ed025dbae
New changeset 98c720c3e061 by Serhiy Storchaka in branch '3.4':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/98c720c3e061
New changeset 4cb316fe6bf2 by Serhiy Storchaka in branch 'default':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/4cb316fe6bf2 

New changeset 887526ebb013 by Serhiy Storchaka in branch '2.7':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/887526ebb013