The resolution to http://bugs.python.org/issue1608 looks like it'll add
a -fwrapv gcc flag when building python.  This works around the issue
nicely on one compiler (gcc) but doesn't fix our fundamentally broken code.

We should fix all dependencies on integer overflow behavior, starting by
making everything compile properly with gcc's -Wstrict-overflow and
-Werror flags.

My gcc 4.1 doesn't have the -Wstrict-overflow option.

gcc-Version 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)

Should we use -ansi (C90 aka C89 standard) option, too? Python core
compiles fine with -ansi but together with -Werror it breaks several
extensions:

_bsddb            _codecs_iso2022   _ctypes
_socket           _ssl              linuxaudiodev

Socket and SSL are using bluetooth.h which defines some functionas as
inline. Inline isn't part of C89. Linuxaudiodev depends on the 'linux'
macro which is not defined in  C89.

The Python core can be compiled with -ansi but the extension modules
require -std=gnu89.

Using ansi is out of scope of this issue, and should not be mixed with
it. -ansi is about disabling certain GCC extensions. This report is
about C code in Python which has undefined behavior.

I think there is disagreement on whether Python should stop relying on
this particular undefined behavior (namely, whether the sum of two large
positive numbers is negative). GvR (apparently) believes that the
compiler should guarantee that the twos-complement semantic is available
throughout the C language.

Whatever you change regarding the compiler options for Python, please
make sure that this doesn't effect the default settings used by
distutils to compile external modules (it normally takes the options
straight from the Makefile used for compiling Python).

Otherwise, you're likely going to break lots and lots of extensions. Thanks.

I compiled Python using gcc 4.3.0 with the -Wstrict-overflow, and that's
the only warning I got:  

Objects/doubledigits.c: In function ‘_PyFloat_Digits’:
Objects/doubledigits.c:313: error: assuming signed overflow does not
occur when assuming that (X + c) < X is always false

I am sure yet how to interpret it, though. It says that the overflow
check is in _PyFloat_Digits(), line 313 is in the function add_big(). It
probably means that add_big() gets inlined. I tried to set
-finline-limit=0, but strangely the overflow warning disappears...

I will try to investigate this further, when I will have a bit more time
in my hands.

heh if thats the only warning gcc -Wstrict-overflow gives then I've
mistitled the bug.  Fixed.  It'll take some manual code review. 

Anyone know if the commercial analysis tools we've run the code base
through in the past can find these for us?

Alexandre, which Python version did you compile with -Wstrict-overflow?
 It would behoove us to check 2.5.2 thoroughly before it goes out the door.

I will contact Coverity to ask if they check for this kind of thing. 
(They just upgraded us to "Rung 2", whatever that may mean. :-)

MvL: I don't want 2s complement throughout the language, I just want the
overflow checks to be reliable.  Since I'd forgotten about the
difference between unsigned and signed overflow, I have no idea how many
overflow checks have been submitted that are relying on signed overflow;
though apparently (if the -Wstrict-overflow results can be trusted)
we're okay.

FWIW, I've heard that some commercial compilers (e.g. XLC) assume that
even *unsigned* overflow is undefined, violating the C standard.  This
would suggest that buffer overflow checks should be coded without
relying on arithmetic overflow at all.  This is possible, just a bit hairy.

Marc-Andre: what do you mean by breaking lots and lots of extensions? 
Extensions also contain buffer overflow checks (at least I hope they do
:-) and those should also be guaranteed safe by using -fwrapv or
-fno-strict-overflow (GCC 4.2 and higher) until we're sure there aren't any.

-Wstrict-overflow=3 with gcc 4.3 trunk here shows :

Modules/cPickle.c: In function 'Unpickler_noload':
Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false

Modules/cPickle.c:194: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false
Modules/cPickle.c: In function 'load':
Modules/cPickle.c:4232: warning: assuming signed overflow does not occur
when assuming that (X - c) > X is always false

But also note that -fno-strict-aliasing is also just another workaround
and its more serious than -fwrapv.

> But also note that -fno-strict-aliasing is also just another workaround
> and its more serious than -fwrapv.

Sure - however, that is fixed in Python 3 (and unrelated to this issue)

Hm. I don't get any warning, related to the overflow issue, neither with
-Wstrict-overflow=3, nor -Wstrict-overflow=5. Are the cPickle warnings
already fixed?

Make sure you use gcc 4.3 trunk and at least -O2 is enabled. I tested
revision 59895 from release25-maint branch.

FWIW gcc hacker Ian Lance Taylor has a nice article about signed
overflow optimizations in gcc, see http://www.airs.com/blog/archives/120
. Reading that it might be better to use -fno-strict-overflow instead of
-fwrapv.

Regards,
ismail

> FWIW gcc hacker Ian Lance Taylor has a nice article about signed
> overflow optimizations in gcc, see http://www.airs.com/blog/archives/120
> . Reading that it might be better to use -fno-strict-overflow instead of
> -fwrapv.

Please be specific. I read it, and I don't think it's better to use
-fno-strict-overflow.

Ian says -fno-strict-overflow still allows some optimizations, and his
example code shows less assembly is produced with -fno-strict-overflow.
But of course your opinion matters on this one, not mine.

Regards,
ismail

I think the -Wstrict-overflow option may not be enough for the audit we
need.

The overflow issue in expandtabs() still exists (in 2.5 as well as in
the trunk):

            if (*p == '\n' || *p == '\r') {
                i += j;
                old_j = j = 0;
                if (i < 0) {
                    PyErr_SetString(PyExc_OverflowError,
                                    "new string is too long");
                    return NULL;
                }
            }

Here i and j are signed ints (Py_ssize_t) initially know to be >= 0; i
can only become < 0 through overflow.  This is the place where Ismail
(cartman) found a crash because the test was optimized away by GCC 4.3
before we added -fwrap.

If we ever hope to clean up the code to the point where -fwrapv is no
longer needed, the audit should find this spot!  (Good thing we at least
had a unittest for the overflow check.  This should be standard practice
for all overflow checks, as long it doesn't require allocating a GB or
more of memory.)

FWIW I reported this to GCC bugzilla as a missing diagnostic @
http://gcc.gnu.org/PR34843

Problem was that -Wall at the end was resetting -Wstrict-overflow, so
here is the current results for signed overflow warnings (python 2.5
branch SVN), a lot of them :

Parser/acceler.c: In function 'fixstate':
Parser/acceler.c:90: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2

Parser/node.c: In function 'PyNode_AddChild':
Parser/node.c:90: warning: assuming signed overflow does not occur when
changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/node.c:90: warning: assuming signed overflow does not occur when
changing X +- C1 cmp C2 to X cmp C1 +- C2

Parser/firstsets.c: In function 'calcfirstset':
Parser/firstsets.c:71: warning: assuming signed overflow does not occur
when simplifying conditional to constant

Parser/pgen.c: In function 'compile_item':
Parser/pgen.c:268: warning: assuming signed overflow does not occur when
changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/pgen.c: In function '_Py_pgen':
Parser/pgen.c:454: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Parser/pgen.c:556: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Parser/pgen.c:604: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Parser/pgen.c:611: warning: assuming signed overflow does not occur when
simplifying conditional to constant

Parser/tokenizer.c: In function 'new_string':
Parser/tokenizer.c:175: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c: In function 'tok_get':
Parser/tokenizer.c:1163: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c: In function 'PyTokenizer_Get':
Parser/tokenizer.c:1443: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c:1443: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c: In function 'PyTokenizer_FromString':
Parser/tokenizer.c:607: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2

Objects/abstract.c: In function 'PyObject_CallMethodObjArgs':
Objects/abstract.c:2038: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/abstract.c:2038: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/abstract.c: In function 'PyObject_CallFunctionObjArgs':
Objects/abstract.c:2038: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/abstract.c:2038: warning: assuming signed overflow does not
occur when simplifying conditional to constant

Objects/intobject.c: In function 'PyInt_FromUnicode':
Objects/intobject.c:394: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Objects/listobject.c: In function 'merge_at':
Objects/listobject.c:1595: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/listobject.c:1459: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/listobject.c:1459: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/listobject.c:1595: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Objects/longobject.c: In function 'PyLong_FromUnicode':
Objects/longobject.c:1701: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/longobject.c: In function '_PyLong_AsScaledDouble':
Objects/longobject.c:703: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/longobject.c:703: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/longobject.c: In function 'long_sub':
Objects/longobject.c:1978: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/longobject.c: In function 'l_divmod':
Objects/longobject.c:1802: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/longobject.c:1802: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Objects/stringobject.c: In function 'string_expandtabs':
Objects/stringobject.c:3331: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c:3339: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c: In function 'string_replace':
Objects/stringobject.c:2509: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c:2509: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c:2509: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c:2509: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c:2672: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringobject.c: In function 'string_count':
Objects/stringlib/count.h:24: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/stringlib/count.h:24: warning: assuming signed overflow does not
occur when simplifying conditional to constant

Objects/unicodeobject.c: In function 'unicode_expandtabs':
Objects/unicodeobject.c:5719: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/unicodeobject.c:5727: warning: assuming signed overflow does not
occur when simplifying conditional to constant
Objects/unicodeobject.c: In function 'PyUnicodeUCS4_Compare':
Objects/unicodeobject.c:5376: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/unicodeobject.c:5376: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Objects/unicodeobject.c: In function 'PyUnicodeUCS4_Join':
Objects/unicodeobject.c:4659: warning: assuming signed overflow does not
occur when simplifying conditional to constant

Python/ast.c: In function 'ast_for_genexp':
Python/ast.c:1195: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Python/ast.c:1160: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Python/ast.c: In function 'ast_for_atom':
Python/ast.c:1040: warning: assuming signed overflow does not occur when
simplifying conditional to constant
Python/ast.c:1005: warning: assuming signed overflow does not occur when
simplifying conditional to constant

Python/bltinmodule.c: In function 'builtin_map':
Python/bltinmodule.c:907: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Python/bltinmodule.c:847: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Python/bltinmodule.c:847: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Parser/tokenizer.c:1163: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c: In function 'PyTokenizer_Get':
Parser/tokenizer.c:1443: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
Parser/tokenizer.c:1443: warning: assuming signed overflow does not
occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Python/getargs.c:994: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2
Python/getargs.c:1040: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2
Python/getargs.c: In function 'seterror':
Python/getargs.c:357: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2

Python/import.c: In function 'PyImport_ExtendInittab':
Python/import.c:3129: warning: assuming signed overflow does not occur
when simplifying conditional to constant

Python/modsupport.c: In function 'va_build_value':
Python/modsupport.c:529: warning: assuming signed overflow does not
occur when simplifying conditional to constant

Python/sysmodule.c: In function 'sys_getframe':
Python/sysmodule.c:650: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2

Modules/gcmodule.c: In function 'collect':
Modules/gcmodule.c:767: warning: assuming signed overflow does not occur
when changing X +- C1 cmp C2 to X cmp C1 +- C2

./Modules/_sre.c: In function 'sre_match':
./Modules/_sre.c:1002: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1069: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1086: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1143: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1185: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1214: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1238: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1251: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1277: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1291: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1308: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1395: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1408: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c: In function 'sre_umatch':
./Modules/_sre.c:1002: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1069: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1086: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1143: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1185: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1214: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1238: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1251: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1277: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1291: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1308: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1395: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1408: warning: assuming signed overflow does not occur
when simplifying conditional to constant

/packages/python-2.5/Modules/stropmodule.c: In function 'strop_replace':
/packages/python-2.5/Modules/stropmodule.c:1102: warning: assuming
signed overflow does not occur when changing X +- C1 cmp C2 to X cmp C1
+- C2

/packages/python-2.5/Modules/_heapqmodule.c: In function 'heappop':
/packages/python-2.5/Modules/_heapqmodule.c:146: warning: assuming
signed overflow does not occur when changing X +- C1 cmp C2 to X cmp C1
+- C2

/packages/python-2.5/Modules/_hotshot.c: In function 'pack_line_times':
/packages/python-2.5/Modules/_hotshot.c:693: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
/packages/python-2.5/Modules/_hotshot.c: In function 'pack_frame_times':
/packages/python-2.5/Modules/_hotshot.c:706: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

/packages/python-2.5/Modules/binascii.c: In function 'binascii_a2b_base64':
/packages/python-2.5/Modules/binascii.c:320: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2
/packages/python-2.5/Modules/binascii.c: In function 'binascii_b2a_uu':
/packages/python-2.5/Modules/binascii.c:287: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

/packages/python-2.5/Modules/parsermodule.c: In function
'validate_subscript':
/packages/python-2.5/Modules/parsermodule.c:2811: warning: assuming
signed overflow does not occur when changing X +- C1 cmp C2 to X cmp C1
+- C2

/packages/python-2.5/Modules/cPickle.c: In function 'Unpickler_noload':
/packages/python-2.5/Modules/cPickle.c:193: warning: assuming signed
overflow does not occur when simplifying conditional to constant
/packages/python-2.5/Modules/cPickle.c:194: warning: assuming signed
overflow does not occur when reducing constant in comparison
/packages/python-2.5/Modules/cPickle.c:4232: warning: assuming signed
overflow does not occur when assuming that (X - c) > X is always false
/packages/python-2.5/Modules/cPickle.c:194: warning: assuming signed
overflow does not occur when assuming that (X - c) > X is always false
/packages/python-2.5/Modules/cPickle.c: In function 'load':
/packages/python-2.5/Modules/cPickle.c:4232: warning: assuming signed
overflow does not occur when assuming that (X - c) > X is always false

/packages/python-2.5/Modules/audioop.c: In function 'audioop_ratecv':
/packages/python-2.5/Modules/audioop.c:1150: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

/packages/python-2.5/Modules/imageop.c: In function 'imageop_dither2grey2':
/packages/python-2.5/Modules/imageop.c:430: warning: assuming signed
overflow does not occur when simplifying conditional to constant

/packages/python-2.5/Modules/_csv.c: In function 'join_append_data':
/packages/python-2.5/Modules/_csv.c:969: warning: assuming signed
overflow does not occur when simplifying conditional to constant

/packages/python-2.5/Modules/expat/xmlparse.c: In function 'getAttributeId':
/packages/python-2.5/Modules/expat/xmlparse.c:5337: warning: assuming
signed overflow does not occur when simplifying conditional to constant

/packages/python-2.5/Modules/dlmodule.c: In function 'dl_call':
/packages/python-2.5/Modules/dlmodule.c:103: warning: assuming signed
overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

Thanks! Good catch about -Wall. I think I am now able to reproduce these
results with gcc 4.2. These results, while much more disturbing
regarding the state of our code base, at least restore my faith in GCC. :-)

I still don't get additional error messages on the trunk. I've altered
the configure.in file to include -Wstrict-overflow=5 after -Wall:

gcc -pthread -c -fno-strict-aliasing -g -Wall -Wstrict-prototypes
-Wstrict-overflow=5  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o
Objects/listobject.o Objects/listobject.c

Either all problems are already solved or I'm doing something wrong here.

$ LC_ALL=C gcc-4.2 -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v
--enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr
--enable-shared --with-system-zlib --libexecdir=/usr/lib
--without-included-gettext --enable-threads=posix --enable-nls
--with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2
--enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr
--enable-targets=all --enable-checking=release --build=i486-linux-gnu
--host=i486-linux-gnu --target=i486-linux-gnu
Thread model: posix
gcc version 4.2.1 (Ubuntu 4.2.1-5ubuntu4)

-Wstrict-overflow=5 is not valid afaik its 1-3, 3 for most verbose also
you need a recent gcc 4.3 snapshot for best results, check your
distribution for gcc-snapshot package.

About the -Wall thing it seems to be a gcc bug, but for now workaround
is easy :-)

Regards,
ismail

Btw I think we need an unsigned version of Py_ssize_t to fix this
problem cleanly. I am not sure if you would agree with me though.

I don't think we can make Py_ssize_t unsigned. On several occasions
Python uses -1 as error flag or default flag.

No I mean we need a new unsigned variant. Else we will have to cast it
to unsigned for many overflow cases which is ugly.

The proper thing to do here is to add

-Werror=strict-overflow

to the CFLAGS (*before* -Wall -- we should fix the position of -Wall!);
this will turn all those spots into errors, forcing us to fix them, and
alerting users who might be using a newer compiler than we tested with.

This should be done in favor of -fwrapv, but only if strict-overflow is
supported (which we can find out in the same way as we found out whether
-fwrapv is supported).  I think in practice this means GCC 4.2 or newer.

Can someone come up with a patch?

An unsigned variant of Py_ssize_t would just be size_t -- that's a much
older type than ssize_t.  I don't think we need to invent a Py_ name for it.

Replace -fwrapv with -Wstrict-overflow=3 -Werror=strict-overflow when
supported. Guido, does this do what you wanted?

Regards,
ismail

Close, I'd like to keep the -fwrapv if -Wstrict-overflow isn't supported.

Also, would checking this in mean we can't build with GCC 4.3 until
those issues are all fixed?

Yes it breaks compilation with gcc 4.3. Fixing these bugs are mostly
s/int/unsigned int. But some parts of code need Python wisdom :/ 

New patch attached adressing your comment.

Would you mind also adding patches for the places you think you can fix,
and providing us with a list of places you need help with?

O'm hoping that Greg or Christian can help reviewing these and
committing them.  Thanks much for your help BTW!

The -fwrapv doesn't look right. You aren't testing for -fwrapv at all ;)

First stub at fixing overflows, regresses following tests :

test_doctests.py
test_locale.py
test_long.py
test_long_future.py
test_optparse.py
test_pickle.py
test_str.py (crash)
test_string.py (crash)
test_unicode.py (crash)
test_userstring.py (crash)
test_xpickle.py

Not great, but a start.

> Btw I think we need an unsigned version of Py_ssize_t to fix this
> problem cleanly. I am not sure if you would agree with me though.

There is an unsigned version, it's called "size_t".

Crashes ain't good ;)

I suggest that you chance only a small portion of files at a time, then
make && ./python Lib/test/regrtest.py. Start with the Parser, then move
over to AST and the rest of Python/.

You may have to remove all pyc and pyo files if you change code related
to the Parser, AST and byte code marshaling. I'm not sure if it's
required but it's worth a shot. Bytecode mismatches can lead to strange
errors.

I created a git repo for my fixes over
http://repo.or.cz/w/pytest.git?a=shortlog;h=overflow-fix .

Now as tiran suggested I fix one file and make sure nothing regressed.
But! Feel free to beat me to it and fix this. I am all new to this and
progress might be and possibly be slow.

With second patch now python builds without any overflow warnings, no
new regressions. Please test and/or review.

Only thing left is fixing Modules subdirectory.

Thanks.

Possibly last one before final patch, only Modules/_sre.c left to fix, I
appreciate help on that. Please ignore tab problems, I think that can be
fixed later on.

Thanks.

Final patch should be complete. Used a trick in _sre.c, instead of i < 0
, I used 
i + i < i to trick gcc.

Ismail Donmez wrote:
> Ismail Donmez added the comment:
> 
> Final patch should be complete. Used a trick in _sre.c, instead of i < 0
> , I used 
> i + i < i to trick gcc.

I'm going to review your patch later.

Christian

Ismail Donmez wrote:
> Final patch should be complete. Used a trick in _sre.c, instead of i < 0
> , I used 
> i + i < i to trick gcc.
> 
> Added file: http://bugs.python.org/file9242/fix-overflows-final.patch

Does the C89 standard allow this code?

int q = 1;
int p = (unsigned)q;

I've never seen an unsigned cast without a type. Does the code compile
with gcc -std=C89?

Christian

> Does the C89 standard allow this code?
> 
> int q = 1;
> int p = (unsigned)q;
> I've never seen an unsigned cast without a type.

Yes, that's fine; it's a different spelling of "unsigned int".
In C99, 6.7.2p1 defines the following groups as equivalent:
- short, signed short, short int, or signed short int
- unsigned short, or unsigned short int
- int, signed, or signed int
- unsigned, or unsigned int
- long, signed long, long int, or signed long int
- unsigned long, or unsigned long int
- long long, signed long long, long long int, or
            signed long long int
- unsigned long long, or unsigned long long int

Specifiers may occur in any order, so you may also write
"int short unsigned".

Hi Christian,

unsigned cast is actually suggested by GCC developers to force correct
wrapping for signed types. And thanks to Martin, it makes sense :-)

I'm just starting to look at the patch.  The first one changes i to
unsigned in Modules/_csv.c.  Hopefully most of them are like this.  The
code is fine as it is.  There is no reliance on overflow AFAICT.  It's
just that the breaking condition from the loop is not in the for (...).
 I think this change is fine to avoid a warning.  Just pointing out that
in this one case, it's not a real problem.

Change to heapq doesn't seem needed.  I looked at the warning generated
from this and it's if (!n).  This seems to indicate the compiler thinks
that n could be negative.  That should not be possible.  It came from
PyList_GET_SIZE.  We had verified the object was already a list.  So
this value should be between 0 and PY_SSIZE_T_MAX.  We check for 0, so
it might be > 0.  After decrementing n, it should be between 0 and
PY_SSIZE_T_MAX-1.  Of course, the compiler can't know the value can't be
negative (or PY_SSIZE_T_MIN) which would cause an underflow.

Change to hotshot should avoid a cast, so it's slightly better with this
approach.  Although with the change to size_t, the cast in flush_data
can be removed (just after the fwrite).

I don't see the reason to need for the change in sre.c, but I'm pretty
sure there are other overflows.

audioop definitely looks needed.
cPickle looks necessary.
expat/xmlparse.c is interesting--not sure if it's really necessary.  In
practice this probably can't be reached.
gc can't really overflow given that NUM_GENERATIONS is 3 and not likely
to grow much more. :-)

I stopped looking at this point.  It looks like some of these are really
needed.  Others are not possible given other invariants (the compiler
can't know about).  I like the idea of silencing compiler warnings. 
However, I fear this may generate a different problem.  Namely
signed/unsigned mismatches.

What happens if you add this warning:  -Wsign-compare
I think we got rid of most of those before (probably not true as much
for Modules/*.c).  I think this introduces many more.  Would it be
possible to come up with a patch that doesn't introduce more warnings
w/-Wsign-compare?

One potential issue with this patch is that while the additions might
have guaranteed semantics, we might have other problems when doing:

   size_t value = PyXXX_Size();
   if (value < 0) ...

I'm hoping that if we can use both -Wstrict-overflow and
-Wsign-conversion, eliminate all warnings, resulting in better code. 
(You could also try building with g++.  The core used to work without
warnings.  The modules still had a ways to go.)

Also what is the current state?  What has been implemented and what else
needs to be done?  Perhaps we should make other bug report(s) to address
other tangents that were discussed in this thread.

Thanks for the through review! I will add -Wsign-compare and fix new
warnings.
Btw current state is with the patch -fwrapv is not needed and no
regressions.

I just added -Wstrict-overflow to the code in sysmodule.c
(sys_getframe) and tried with gcc 4.2.1.  It doesn't warn.  I wonder
if 4.3 is more picky or warns when it shouldn't?

Unless if I changed the code so it doesn't work:

typedef struct {int ref;} PyObject;
typedef struct { PyObject* f_back; } PyFrameObject;
int PyArg_ParseTuple(PyObject*, const char*, int*);

PyObject *
sys_getframe(PyFrameObject *f, PyObject *self, PyObject *args)
{
        int depth = -1;

        if (!PyArg_ParseTuple(args, "|i:_getframe", &depth))
                return 0;

        while (depth > 0 && f != 0) {
                f = (PyFrameObject*)f->f_back;
                --depth;
        }
        return (PyObject*)f;
}

Compiled with:
gcc-4.2.1-glibc-2.3.2/x86_64-unknown-linux-gnu/bin/x86_64-unknown-linux-gnu-gcc
-Wstrict-overflow -c xx.c

produced no warnings.  This is not a stock gcc 4.2.1, so that could
also be an issue.  Did I run it correctly.  Is there anything else I
need to do?  If you run the code above with gcc 4.3, does it produce a
warning?

Unfortunately I have no time to work on this myself, but in order to
make progress I recommend checking in things piecemeal so that the same
changes don't get reviewed over and over again.  I propose that each
submit reference this bug ("Partial fix for issue #1621" I'd suggest)
and that the submits are recorded here (e.g. "fixed <filename> in rXXX
(2.5.2), rYYY (2.6)").  Then hopefully only a few hard cases will remain.

With Neal, I don't see what the warning in _csv is about. What condition
is being turned into a constant? Is the compiler perhaps rearranging the
code so as to insert "if (field[0] == '\0') goto XXX;" in front of the
for-loop where XXX jumps into the middle of the condition in the
if-statement immediately following the for-loop, and skipping that
if-block when breaking of the loop later? That would be clever, and
correct, and I'm not sure if making i unsigned is going to help -- in
fact it might make the compiler decide it can't use that optimization...

To Neal,

Can you try with -Wstrict-overflow=3 , but yes I am using gcc 4.3 trunk.

To Guido,

I'll check _csv.c issue closely. Shall I create the new bug reports or
will reviewers will do so and CC me maybe?

On Jan 27, 2008 6:45 PM, Ismail Donmez <report@bugs.python.org> wrote:
>
> Can you try with -Wstrict-overflow=3 , but yes I am using gcc 4.3 trunk.

I just tried with =1, =2, =3, and no =.  All the same result:  no warning.

Ismail, thanks for going through all this effort.  It's very helpful.

Don't create new bug reports!

Neal,

I'll try to answer your questions one by one, first with _csv.c compiler
issues :

Modules/_csv.c:969: warning: assuming signed overflow does not occur
when simplifying conditional to constant

There is a check inside loop like this:

               if (c == '\0')
                       break;

Instead of this if we do the check in the for :

+       for (i = 0; i < strlen(field) ; i++) {

and remove the if check compiler no longer issues a warning also csv
test passes with this. Attached patch implements this optimization.

Guido, you don't have to shout, you know noone pays me per python
bugreport I create :)

_sre.c case is the most interesting one , compiler says :

./Modules/_sre.c:1002: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1069: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1086: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1143: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1185: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1214: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1238: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1251: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1277: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1291: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1308: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1395: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1408: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c: In function 'sre_umatch':
./Modules/_sre.c:1002: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1069: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1086: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1143: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1185: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1214: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1238: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1251: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1277: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1291: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1308: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1395: warning: assuming signed overflow does not occur
when simplifying conditional to constant
./Modules/_sre.c:1408: warning: assuming signed overflow does not occur
when simplifying conditional to constant

all lines refer to : RETURN_ON_ERROR(ret);

My investigation :

On line 1002 we got RETURN_ON_ERROR(ret); but ret is already 0 and not
set to anything this if will always be false.

Same for line 1069, ret is still zero there. Maybe I am missing
something here?

For xmlparse.c compiler says :

Modules/expat/xmlparse.c:5337: warning: assuming signed overflow does
not occur when simplifying conditional to constant

Its impossible for j to overflow here due to name[i] check but I am not
sure what gcc is optimizing here.

> for (i = 0; i < strlen(field) ; i++) {

This looks inefficient.  Why not

 for (i = 0; field[i] != '\0'; i++) {

???

Hah strlen in a loop, a nice beginner mistake but its 5.30 AM here so
please excuse me, Guido your version of course is way better. But with
that version compiler issues 

Modules/_csv.c:969: warning: assuming signed overflow does not occur when 
simplifying conditional to constant

again, strlen() just fooled that optimization it seems. So there should
be another way to optimize this loop.

> With Neal, I don't see what the warning in _csv is about. What condition
> is being turned into a constant? Is the compiler perhaps rearranging the
> code so as to insert "if (field[0] == '\0') goto XXX;" in front of the
> for-loop where XXX jumps into the middle of the condition in the
> if-statement immediately following the for-loop, and skipping that
> if-block when breaking of the loop later?

Indeed that's what happens. In the case of breaking the loop later,
the compiler can skip the if-block only if signed ints never overflow,
hence the warning.

Another way of silencing the warning is to test field[0]=='\0' in the
if-statement. This might also somewhat pessimize the code, but allows
the compiler to eliminate i altogether.

I wonder if it would help making i a Py_ssize_t instead of an int?

Neal,

You could btw check
http://repo.or.cz/w/pytest.git?a=shortlog;h=overflow-fix which have each
fix seperate so that reviewing is easy. Just ignore configure changes
thats for later.

Thanks,
ismail

> Guido van Rossum added the comment:
>
> I wonder if it would help making i a Py_ssize_t instead of an int?

gcc still issues the same warning with that.

gcc is optimizing the second if check , for specifically i == 0 seems to
redundant according to gcc.

        if (i == 0 && quote_empty) {
                if (dialect->quoting == QUOTE_NONE) {
                        PyErr_Format(error_obj,
                                     "single empty field record must be
quoted");
                        return -1;
                }
                else
                        *quoted = 1;
        }

Moving the empty check before the loop will fix this and possibly
optimize empty string handling.

Any news on this? Also gcc 4.3 & gcc 4.2.3 fixed the -Wall clobbering -
Wstrict-overflow problem, which is good news.

A few comments:

(1) I agree that signed overflows should be avoided
where possible.

(2) I think some of the changes in the latest patch
(fix-overflows-final.patch) are unnecessary, and
decrease readability a bit. An example is the following
chunk for the x_divrem function in Objects/longobject.c.

@@ -1799,7 +1799,7 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
 	k = size_v - size_w;
 	a = _PyLong_New(k + 1);
 
-	for (j = size_v; a != NULL && k >= 0; --j, --k) {
+	for (j = size_v; a != NULL && k >= 0; j = (unsigned)j - 1 , k = (unsigned)k - 1) {
 		digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
 		twodigits q;
 		stwodigits carry = 0;

In this case it's easy to see from the code that j and k
will always be nonnegative, so replacing --j with j =
(unsigned)j - 1 is unnecessary.  (This chunk no longer
applies for 2.7 and 3.1, btw, since x_divrem got
rewritten recently.)  Similar comments apply to the
change:

-			min_gallop -= min_gallop > 1;
+			if (min_gallop > 1) min_gallop = (unsigned)min_gallop - 1;

in Objects/listobject.c.  Here it's even clearer that
the cast is unnecessary.

I assume these changes were made to silence warnings from
-Wstrict-overflow, but I don't think that should be a goal:
I'd suggest only making changes where there's a genuine
possibility of overflow (even if it's a remote one), and
leaving the code unchanged if it's reasonably easy to
see that overflow is impossible.


(3) unicode_hash also needs fixing, as do the lookup
algorithms for set and dict.  Both use overflowing
arithmetic on signed types as a matter of course.
Probably a good few of the hash algorithms for the
various object types in Objects/ are suspect.

"""I assume these changes were made to silence warnings from
-Wstrict-overflow, but I don't think that should be a goal:
I'd suggest only making changes where there's a genuine
possibility of overflow (even if it's a remote one), and
leaving the code unchanged if it's reasonably easy to
see that overflow is impossible."""

There is a lot of value in being able to compile with -Wstrict-overflow 
and know that every warning omitted is something to be looked at.  I 
think it is advantageous to make all code pass this.  Having any 
"expected" warnings during compilation tends to lead people to ignore 
all warnings.

That said, I agree those particular examples of unnecessary casts are 
ugly and should be written differently if they are actually done to 
prevent a warning.

> There is a lot of value in being able to compile with -Wstrict-overflow 
> and know that every warning omitted is something to be looked at.

I agree in principle; this certainly applies to -Wall.  But -Wstrict-
overflow doesn't do a particularly good job of finding signed overflow
cases:  there are a good few false positives, and it doesn't pick up
the many cases of actual everyday signed overflow e.g., in unicode_hash, 
byteshash, set_lookkey, etc.), so it doesn't seem a particular good basis 
for code rewriting.

You should be using gcc 4.4 to get the best warning behaviour.

Thanks Ismail.  I'm currently using gcc-4.4 with the -ftrapv (not 
-fwrapv!) option to see how much breaks.  (Answer: quite a lot. :-[ )

I'm finding many overflow checks that look like:

	size = Py_SIZE(a) * n;
	if (n && size / n != Py_SIZE(a)) {
		PyErr_SetString(PyExc_OverflowError,
			"repeated bytes are too long");
		return NULL;
	}

where size and n have type Py_ssize_t.  That particular one comes
from bytesobject.c (in py3k), but this style of check occurs
frequently throughout the source.

Do people think that all these should be fixed?  

The fix itself s reasonably straightforward:  instead of multiplying
and then checking for an overflow that's already happened (and hence
has already invoked undefined behaviour according to the standards),
get an upper bound for n *first* by dividing PY_SSIZE_T_MAX
by Py_SIZE(a) and use that to do the overflow check *before*
the multiplication.  It shouldn't be less efficient:  either way
involves an integer division, a comparison, and a multiplication.

The hard part is finding all the places that need to be fixed.

> I'm finding many overflow checks that look like:
> 
> 	size = Py_SIZE(a) * n;
> 	if (n && size / n != Py_SIZE(a)) {
> 		PyErr_SetString(PyExc_OverflowError,
> 			"repeated bytes are too long");
> 		return NULL;
> 	}
> 
> where size and n have type Py_ssize_t.  That particular one comes
> from bytesobject.c (in py3k), but this style of check occurs
> frequently throughout the source.
> 
> Do people think that all these should be fixed?  

If this really invokes undefined behavior already (i.e. a compiler
could set "size" to -1, and have the test fail - ie. not give
an exception, and still be conforming) - then absolutely yes.

> The fix itself s reasonably straightforward:  instead of multiplying
> and then checking for an overflow that's already happened (and hence
> has already invoked undefined behaviour according to the standards),
> get an upper bound for n *first* by dividing PY_SSIZE_T_MAX
> by Py_SIZE(a) and use that to do the overflow check *before*
> the multiplication.  It shouldn't be less efficient:  either way
> involves an integer division, a comparison, and a multiplication.

[and then perform the multiplication unsigned, to silence the
warning - right?]

I think there is a second solution: perform the multiplication
unsigned in the first place. For unsigned multiplication, IIUC,
overflow behavior is guaranteed in standard C (i.e. it's modulo
2**N, where N is the number of value bits for the unsigned value).

So the code would change to

nbytes = (size_t)Py_SIZE(a)*n;
if (n && (nbytes > Py_SSIZE_T_MAX || nbytes/n != Py_SIZE(a))...
size = (Py_ssize_t)nbytes;

> [and then perform the multiplication unsigned, to silence the
> warning - right?]

That wasn't actually what I was thinking:  I was proposing to rewrite it 
as:

	if (Py_SIZE(a) > 0 && n > PY_SSIZE_T_MAX/Py_SIZE(a)) {
		PyErr_SetString(PyExc_OverflowError,
			"repeated bytes are too long");
		return NULL;
	}
	size = Py_SIZE(a) * n;

The multiplication should be safe from overflow, and I don't get
any warning at all either with this rewrite (using -O3 -Wall -Wextra -
Wsigned-overflow=5) or from the original code, so there's nothing to 
silence.

> I think there is a second solution: perform the multiplication
> unsigned in the first place.

That would work too.  I find the above code clearer, though.  It's not 
immediately obvious to me that the current overflow condition actually 
works, even assuming wraparound on overflow; I find myself having to 
think about the mathematics every time.

In general, it seems to me that the set of places reported by -Wsigned-
overflow is a poor match for the set of places that need to be fixed.  -
Wsigned-overflow only gives a warning when that particular version of 
gcc, with those particular flags, happens to make use of the no-overflow 
assumption for some particular optimization.  Certainly each of the 
places reported by -Wsigned-overflow should be investigated, but I don't 
believe it's worth 'fixing' correct code just to get rid of warnings 
from this particular warning option.

> 	size = Py_SIZE(a) * n;
> 
> The multiplication should be safe from overflow, and I don't get
> any warning at all either with this rewrite (using -O3 -Wall -Wextra -
> Wsigned-overflow=5) or from the original code, so there's nothing to 
> silence.

This is puzzling, isn't it? It *could* overflow, could it not?

>> I think there is a second solution: perform the multiplication
>> unsigned in the first place.
> 
> That would work too.  I find the above code clearer, though.

I agree in this case. In general, I'm not convinced that it
is always possible to rewrite the code in that way conveniently.

> This is puzzling, isn't it?

I don't see why.  There's nothing in -Wall -Wextra -Wsigned-overflow
that asks for warnings for code that might overflow. Indeed, I don't
see how any compiler could reasonably provide such warnings without
flagging (almost) every occurrence of arithmetic on signed integers
as suspect.[*] 

The -ftrapv option is useful for catching genuine signed-integer
overflows at runtime, but it can still only catch those cases
that actually get exercised (e.g., by the Python test suite).


[*] Even some operations on unsigned integers would have to be
flagged: the C expression "(unsigned short)x * (unsigned short)y"
also has the potential to invoke undefined behaviour, thanks to
C's integer promotion rules.

Aargh!

s/Wsigned-overflow/Wstrict-overflow/g

Sorry.

> I don't see why.  There's nothing in -Wall -Wextra -Wsigned-overflow
> that asks for warnings for code that might overflow.

Ah, right. I misunderstood (rather, didn't bother checking) what
-Wsigned-overflow really does.