[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:

Thank you very much to the task force who worked on this issues which can be 
seen as boring and useless, but are very important nowadays with C compilers 
which are more and more agressive to optimize everything (I'm looking at you 
clang!).

This bug is open for 11 years and dozens and dozens of undefined behaviours 
have been fixed in the meanwhile.

This bug is a giant beast with many patches and many pull requests. I dislike 
such bug, it's very hard to follow them. I suggest to open new bugs for 
undefined behaviour on specific functions, rather than a very vague "let's open 
a single bug to track everything".

It's now time to close the issue.

--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:


New changeset 6665802549006eb50c1a68c3489ee3aaf81d0c8e by Victor Stinner (Miss 
Islington (bot)) in branch '3.7':
bpo-1621: Avoid signed integer overflow in set_table_resize() (GH-9059) 
(GH-9198)
https://github.com/python/cpython/commit/6665802549006eb50c1a68c3489ee3aaf81d0c8e


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:


New changeset a9274f7b3f69519f0746c50f85a68abd926ebe7b by Victor Stinner (Miss 
Islington (bot)) in branch '3.6':
bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059) 
(GH-9199)
https://github.com/python/cpython/commit/a9274f7b3f69519f0746c50f85a68abd926ebe7b


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:

Benjamin: what do you think of adding an explicit check after the "new_size <<= 
1;" loop?

if (new_size > (size_t)PY_SSIZE_T_MAX) {
PyErr_NoMemory();
return -1;
}

Technically, PyMem_Malloc() already implements the check, so it's not really 
needed. So I'm not sure if it's needed :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Benjamin Peterson]

Change by Benjamin Peterson :


--
pull_requests: +8692, 8693

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Benjamin Peterson]

Change by Benjamin Peterson :


--
pull_requests: +8692

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:

I asked if there is an issue. In fact, all Python memory allocators start by 
checking if the size is larger than PY_SSIZE_T_MAX. Example:

void *
PyMem_RawMalloc(size_t size)
{
/*
 * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes.
 * Most python internals blindly use a signed Py_ssize_t to track
 * things without checking for overflows or negatives.
 * As size_t is unsigned, checking for size < 0 is not required.
 */
if (size > (size_t)PY_SSIZE_T_MAX)
return NULL;
return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);
}

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Sergey Fedoseev]

Sergey Fedoseev  added the comment:

> Now you rely on PyMem_Malloc() to detect the overflow.

Now overflow is not possible or am I missing something?

--
nosy: +sir-sigurd

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Jeffrey Walton]

Jeffrey Walton  added the comment:

On Tue, Sep 11, 2018 at 8:26 PM, STINNER Victor  wrote:
>
> STINNER Victor  added the comment:
>
>> newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1.
>
> Previously, there was a explicitly check for error raising  PyErr_NoMemory() 
> on overflow. Now you rely on PyMem_Malloc() to detect the overflow. I'm not 
> sure that it's a good idea.

+1. It will probably work as expected on Solaris and other OSes that
don't oversubscribe memory. It will probably fail in unexpected ways
on Linux when the allocation succeeds but then the OOM killer hits a
random process.

Jeff

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[STINNER Victor]

STINNER Victor  added the comment:

> newsize <<= 1; // The largest possible value is PY_SSIZE_T_MAX + 1. 

Previously, there was a explicitly check for error raising  PyErr_NoMemory() on 
overflow. Now you rely on PyMem_Malloc() to detect the overflow. I'm not sure 
that it's a good idea.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[miss-islington]

Change by miss-islington :


--
pull_requests: +8633

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[miss-islington]

Change by miss-islington :


--
pull_requests: +8634

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[miss-islington]

miss-islington  added the comment:


New changeset 6c7d67ce83a62b5f0fe5c53a6df602827451bf7f by Miss Islington (bot) 
(Sergey Fedoseev) in branch 'master':
bpo-1621: Avoid signed integer overflow in set_table_resize(). (GH-9059)
https://github.com/python/cpython/commit/6c7d67ce83a62b5f0fe5c53a6df602827451bf7f


--
nosy: +miss-islington

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Sergey Fedoseev]

Change by Sergey Fedoseev :


--
pull_requests: +8519

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Gregory P. Smith]

Change by Gregory P. Smith :


--
versions: +Python 3.7, Python 3.8 -Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter  added the comment:

Sorry I haven’t made a PR for ctypes_v2.patch, but I don’t mind if someone else 
takes over. I understand the HAVE_LONG_LONG check may no longer necessary for 
newer Python versions.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Martin, do you mind to create a PR for your ctypes_v2.patch?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot added the comment:

New changeset dd2c7d497878 by Martin Panter in branch '3.5':
Issues #1621, #29145: Test for str.join() overflow
https://hg.python.org/cpython/rev/dd2c7d497878

New changeset eb6eafafdb44 by Martin Panter in branch 'default':
Issue #1621: Overflow should not be possible in listextend()
https://hg.python.org/cpython/rev/eb6eafafdb44

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Changes by Martin Panter :


--
dependencies: +failing overflow checks in replace_*

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

It's good Martin. Just commit it.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Xiang: regarding your overflow_fix_in_listextend.patch, what do you think about 
adding a comment or debugging assertion instead, something like:

/* It should not be possible to allocate a list large enough to cause an 
overflow on any relevant platform */
assert(m < PY_SSIZE_T_MAX - n);

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Christian Heimes]

Changes by Christian Heimes :


--
nosy:  -christian.heimes

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

I agree. For multibytecode, how about switching the positions of the two 
checks? If npendings + ctx->pendingsize overflows, the result can be anything, 
larger, smaller than or equal to MAXDECPENDING. For ast, although a SystemError 
may be raised but the message seems not obvious to the reason.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Looking over r60793, the overflow check at 
Modules/cjkcodecs/multibytecodec.c:836 looks vulnerable to being optimized 
away, because it can only detect the overflow if the line above has already 
overflowed. Perhaps change PY_SSIZE_T_MAX to MAXDECPENDING. I wonder if any of 
the GCC optimization and warning modes can detect this case?

Also, Python/ast.c:3988 checks using PY_SIZE_MAX, but then passes the value to 
PyBytes_FromStringAndSize(), which expects ssize_t and in the best case would 
raise SystemError.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Antti Haapala]

Antti Haapala added the comment:

I don't believe Python would really ever work on a platform with 
non-8-bit-bytes, I believe there are way too much assumptions *everywhere*. You 
can program in C on such a platform, yes, but not that sure about Python.

And on 8-bit-byte platfomrs, there is no large model with 16-bit pointers 
anywhere. There just are not enough bits that you could have multiple 64k 
byte-addressable segments that are addressed with 16-bit pointers. 

It might be that some obscure platform in the past would have had 128k memory, 
with large pointers, 2 allocatable 64k segments, >16 bit char pointer and 
16-bit object pointers pointing to even bytes, but I doubt you'd be really 
porting *Python 3* to such a platform, basically we're talking about something 
like Commodore 128 here.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

So these checks are superfluous? Do we need to remove them?

Hmm, I still doubt such checks should consider platform characteristics first. 
In theory List can be PY_SSIZE_T_MAX length. Do we have to put the PY_SIZE_MAX 
// sizeof(PyObject *) limit on it?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

The check in ins1() was originally added in revision b9002da46f69. I presume it 
references the Python-dev thread “can this overflow (list insertion)?” 
<2812145155.a7...@activestate.com>, 
. At that time, ob_size was 
an int, so overflow checking was definitely needed. Later, revision 
7fdc639bc5b4 changed ob_size to Py_ssize_t, and then revision 606818c33e50 
updated the overflow check from INT_MAX to PY_SSIZE_T_MAX.

BTW I made a small mistake in my previous message. The worst case would be 
extending a list with itself. But I think the conclusion is still the same.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Gregory P. Smith]

Changes by Gregory P. Smith :


--
nosy:  -gregory.p.smith

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

Hmm, I don't tend to infer platform characteristics. IMHO, it's a simple 
problem: sum up two lists' length which may overflow in logic.

With your argument, does it means it seems somewhat meaningless to have a List 
a Py_ssize_t length since it can never reach it? Checks against PY_SSIZE_T_MAX 
have already existed (for example, in ins1).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

overflow_fix_in_listextend.patch: I doubt Python supports the kinds of platform 
where this overflow would be possible. It may require pointers smaller than 32 
bits, or char objects larger than 8 bits. Perhaps we could just add a comment 
explaining we assume the overflow cannot happen.

It seems list objects will hold one pointer for each element, but the overflow 
involves the number of elements. Python defines PY_SSIZE_T_MAX as PY_SIZE_MAX 
// 2. For the overflow to happen we would need

m + n > PY_SSIZE_T_MAX

Assuming a “flat” address space that can allocate up to PY_SIZE_MAX bytes _in 
total_, the total number of elements cannot exceed

m + n == PY_SIZE_MAX // sizeof (PyObject *)

So in this scenario, the overflow cannot happen unless sizeof (PyObject *) == 1.

Considering things like the 16-bit segmented Intel “large” memory model (which 
I doubt Python is compatible with), each list could _independently_ be up to 
PY_SIZE_MAX bytes. Therefore the total number of elements may reach

m + n == PY_SIZE_MAX // sizeof (PyObject *) * 2

So even in this case, sizeof (PyObject *) == 4 (large model) is fine, but 
anything less (e.g. 16-bit char, or 1-byte segment + 2-byte offset) might 
overflow.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

Martin, I upload a patch to fix another possible overflow in listextend.

--
Added file: http://bugs.python.org/file43956/overflow_fix_in_listextend.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot added the comment:

New changeset db93af6080e7 by Martin Panter in branch 'default':
Issue #1621: Avoid signed overflow in list and tuple operations
https://hg.python.org/cpython/rev/db93af6080e7

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

It turns out you just want to see the output. That is easy. Patch v3 adding the 
test.

--
Added file: http://bugs.python.org/file43862/tuple_and_list_v3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

unicode.patch avoids an overflow in PyUnicode_Join():

>>> size = int(sys.maxsize**0.5) + 1
>>> "".join(("A" * size,) * size)
Objects/unicodeobject.c:9927:12: runtime error: signed integer overflow: 46341 
+ 2147441940 cannot be represented in type 'int'
OverflowError: join() result is too long for a Python string

--
Added file: http://bugs.python.org/file43856/unicode.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Xiang: I don’t think we need to make the tests do anything special. Just make 
sure they exercise the code that handles overflows. I have been running the 
test suite without any -j0 option, and I can look over the output and see the 
error messages. Or if we get to a stage where all the errors are eliminated, 
you could run with UBSAN_OPTIONS=halt_on_error=1. E.g. in this patch, I add two 
simple tests to cover parts of the code that weren’t covered before (and if I 
hadn’t fixed the overflows, the tests would trigger extra UBSAN errors).

ctypes_v2.patch is an update of array-size.patch. I improved the test case, and 
added a new fix for overflows like the following:

>>> class S(ctypes.Structure):
... _fields_ = (("field", ctypes.c_longlong, 64),)
... 
>>> s = S()
>>> s.field = 3
Modules/_ctypes/cfield.c:900:9: runtime error: signed integer overflow: 
-9223372036854775808 - 1 cannot be represented in type 'long long int'

--
Added file: http://bugs.python.org/file43855/ctypes_v2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

It's cool, but I get one problem when writing tests. support.captured_stderr 
cannot capture the runtime error message. So we have nothing to do with the 
assertion and the test will always succeed even when overflow does happen (the 
message will be output). To solve this problem, we have to do io redirect in 
file descriptor level, I wonder does this deserve that?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

The error message comes from Undefined Behaviour Sanitizer, which was added to 
newer versions of GCC and Clang. Currently I am compiling with

./configure --with-pydebug CC="gcc -fsanitize=undefined -fno-sanitize=alignment 
-fno-sanitize=shift"

https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html#index-fsanitize_003dundefined-962

I thought it is worth adding a test for the impossible __length_hint__() value. 
Since the test iterator returns no elements, there will not be a MemoryError, 
but if overflow detection is enabled (such as UB Sanitizer or -ftrapv), it is 
guaranteed to exercise the overflow path and would be detected.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

Change tuple_and_list.patch with empty curly braces. I don't add the test for 
__length_hint__. According to the comment, when overflow happens, it is either 
ignored or a MemoryError will finally be raised. I am not willing to test a 
MemoryError in this case.

BTW, how do you get the error?

--
Added file: http://bugs.python.org/file43842/tuple_and_list_v2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Changes by Martin Panter :


Added file: http://bugs.python.org/file43839/array-size.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Perhaps we should add a test for the __length_hint__() overflow to 
tuple_and_list.patch:

>>> a = [1,2,3,4]
>>> import sys
>>> class B:
...  def __iter__(s): return s
...  def __next__(s): raise StopIteration()
...  def __length_hint__(s): return sys.maxsize
... 
>>> a.extend(B())
Objects/listobject.c:844:8: runtime error: signed integer overflow: 4 + 
2147483647 cannot be represented in type 'int'

array-size.patch fixes the ctypes array size overflow (including a test).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Apart from the empty “if” statement style (see review), tuple_and_list.patch 
looks good to me.

I understand the patches from 2011 and earlier have all been committed (correct 
me if I missed something).

Here is another patch fixing a 64-bit overflow in _thread, detected by the 
test_timeout() method in test_threading:
Modules/_threadmodule.c:59:17: runtime error: signed integer overflow: 
6236628528058 + 92233720360 cannot be represented in type 'long int'

--
Added file: http://bugs.python.org/file43838/thread.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Xiang Zhang]

Xiang Zhang added the comment:

@Martin, attach a patch to fix the overflow check you mentioned in tuple and 
list objects.

--
nosy: +xiang.zhang
Added file: http://bugs.python.org/file43827/tuple_and_list.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Guido van Rossum]

Changes by Guido van Rossum :


--
nosy:  -gvanrossum

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Serhiy: slice-step.patch seems to be fine with negative slice steps. The actual 
indexes are still positive, and “unsigned” arithmetic is really modular 
arithmetic, so when you add the negative “unsigned” step value, it decrements 
the index properly.

Antti: if you use the sanitizer, (almost?) all the shift errors are for left 
shifts, either of a positive signed overflow, or a negative value. There is a 
bit more discussion of bit shift errors in Issue 20932. Examples:

Modules/audioop.c:1527:43: runtime error: left shift of negative value -24
Objects/unicodeobject.c:5152:29: runtime error: left shift of 255 by 24 places 
cannot be represented in type 'int'

I didn’t see any sanitizer reports about right shifts; perhaps it doesn’t 
report those (being implemenation-defined, rather than undefined, behaviour). 
And the only report about an excessive shift size is due to a known bug in 
ctypes, Issue 15119.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Antti Haapala]

Antti Haapala added the comment:

About shifts, according to C standard, right shifts >> of negative numbers are 
implementation-defined:

   "[in E1 >> E2], If E1 has a signed type and a negative value, the
   resulting value is implementation-defined."

In K this meant that the number can be either zero-extended or sign-extended. 
In any case it cannot lead to undefined behaviour, but the implementation must 
document what is happening there. Now, GCC says that >> is always 
arithmetic/sign-extended. This is the implementation-defined behaviour, now GCC 
has defined what its implementation will do, but some implementation can choose 
zero-extension. (unlikely)

As for the other part as it says "GCC does not use the latitude given in C99 
only to treat certain aspects of signed ‘<<’ as undefined". But GCC6 will 
diagnose that now with -Wextra, and thus it changed already, as with -Werror 
-Wextra the code doesn't necessarily compile any longer, which is fine. Note 
that this "certain -- only" refers to that section where the C99 and C11 
explicitly say that the behaviour is undefined and C89 doesn't say anything. It 
could as well be argued that in C89 it is undefined by omission.

Additionally all shifts that shift by more than or equal to the width *still* 
have undefined behaviour (as do shifts by negative amount). IIRC they work 
differently on ARM vs x86: in x86 the shift can be mod 32 on 386, and in ARM, 
mod 256.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Does this work with negative steps?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

I committed the fix for negation in audioop.

slice-step.patch includes a better fix for the remaining part of trapv.patch, 
with Element Tree slicing. I think this fix is much less intrusive, and I have 
copied it to other places that handle slicing, and added corresponding test 
cases.

The undefined behaviour sanitizer produces lots of errors about bit shifting 
signed integers in low-level modules like ctypes, struct, audioop. Typically 
this is for code converting signed integers to and from bytes, and 
big/little-endian conversions. This is technically undefined behaviour, but I 
think it may be less serious than the other overflows with traditional 
arithmetic like addition and multiplication. E.g. GCC explicitly documents 
 that this is 
handled as expected with twos-complement, so with GCC there should be no nasty 
surprises with optimizing out undefined behaviour. My set-overflow.patch would 
also be in this boat.

--
versions: +Python 3.6
Added file: http://bugs.python.org/file43785/slice-step.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot added the comment:

New changeset d6a86018ab33 by Martin Panter in branch 'default':
Issue #1621: Avoid signed int negation overflow in audioop
https://hg.python.org/cpython/rev/d6a86018ab33

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Antti Haapala]

Antti Haapala added the comment:

Gnulib portability library has 
https://www.gnu.org/software/gnulib/manual/html_node/Integer-Range-Overflow.html
 and 
https://www.gnu.org/softwarhe/gnulib/manual/html_node/Integer-Type-Overflow.html
 and even macros for producing well-defined integer wraparound for signed 
integers: 
https://www.gnu.org/software/gnulib/manual/html_node/Wraparound-Arithmetic.html

That code is under GPL but I believe there is no problem if someone just looks 
into that for ideas on how to write similar macros.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Jeffrey Walton]

Jeffrey Walton added the comment:

>  Has this sort of thing been done in other projects?

Yes.

If you are using C, you can use safe_iop. Android uses it for safer
integer operations. If you are using C++, you can use David LeBlanc's
SafeInt class. Microsoft uses it for safer inter operations.

Jeff

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

I tried the newer -fsanitize=undefined mode, and it is better than -ftrapv. It 
adds instrumentation that by default nicely reports the errors and continues 
running.

My problem with the large slice step is not restricted to Element Tree; it 
affects list objects too:

>>> "abcdef"[3::sys.maxsize]
Objects/unicodeobject.c:13794:55: runtime error: signed integer overflow: 3 + 
9223372036854775807 cannot be represented in type 'long int'
'd'

Regarding Antti’s overflow macros, I noticed there is already a macro 
_PyTime_check_mul_overflow() in Python/pytime.c which does that kind of thing. 
Maybe it could help, though I am not sure. Has this sort of thing been done in 
other projects? We might need to be careful about the sign, e.g. clarify the 
macro is only for positive values, add an assertion, or handle both positive 
and negative.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

The audioop part LGTM. If this case was found with the help of -ftrapv, I'm for 
adding this option in a debug build.

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

I added Issue 13312 as a dependency, there is currently a test for a negative 
year that relies on overflow handling.

Here is a patch where I tried to fix overflow detection for huge set objects.

--
Added file: http://bugs.python.org/file43729/set-overflow.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Martin Panter added the comment:

Inspired by Issue 27473, I did a quick and dirty scan for obvious places that 
expect overflow to wrap, and found the following, which I think should be fixed:

Modules/_ctypes/_ctypes.c:1388, in PyCArrayType_new()
Objects/listobject.c:492, in list_concat()
Objects/tupleobject.c:457, in tupleconcat()
Objects/listobject.c:845, in listextend()

Also I played with enabling GCC’s -ftrapv option. Attached is a patch with 
three changes:

1. configure --with-pydebug enables -ftrapv (experimental, not sure everyone 
would want this)

2. Easy fix for negation overflow in audioop (I am happy to apply this part)

3. Avoid dumb overflows at end of for loop in Element Tree code when handling 
slices with step=sys.maxsize. Technically the overflow is undefined behaviour, 
but the change is annoying, because ignoring the overflow at the end of the 
loop is much simpler than adding special cases. Not sure what I think about 
this part.

--
dependencies: +test_time fails: strftime('%Y', y) for negative year
nosy: +martin.panter
Added file: http://bugs.python.org/file43728/trapv.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Antti Haapala]

Antti Haapala added the comment:

One common case where signed integer overflow has been assumed has been the 
wraparound/overflow checks like in http://bugs.python.org/issue27473 

I propose that such commonly erroneous tasks such as overflow checks be 
implemented as common macros in CPython as getting them right is not quite easy 
(http://c-faq.com/misc/sd26.html); it would also make the C code more 
self-documenting.

Thus instead of writing

 if (va.len > PY_SSIZE_T_MAX - vb.len) {
  
one would write something like

if (PY_SSIZE_T_SUM_OVERFLOWS(va.len, vb.len)) {

and the mere fact that such a macro *wasn't* used there would signal about 
possible problems with the comparison.

--
nosy: +ztane

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin Panter]

Changes by Martin Panter :


--
dependencies: +bytes_concat seems to check overflow using undefined behaviour

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Stefan Krah]

Changes by Stefan Krah stefan-use...@bytereef.org:


--
nosy:  -skrah

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Jakub Wilk]

Changes by Jakub Wilk jw...@jwilk.net:


--
nosy: +jwilk

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Jeffrey Walton]

Jeffrey Walton added the comment:

Also see http://bugs.python.org/issue20944 for suggestions to identify the 
offending code.

--
nosy: +Jeffrey.Walton

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Florian Weimer]

Changes by Florian Weimer fwei...@redhat.com:


--
nosy: +fweimer

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

See also issue #9530.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot devn...@psf.upfronthosting.co.za added the comment:

New changeset 3fb9464f9b02 by Mark Dickinson in branch 'default':
Issue #1621: Fix undefined behaviour from signed overflow in datetime module 
hashes, array and list iterations, and get_integer (stringlib/string_format.h)
http://hg.python.org/cpython/rev/3fb9464f9b02

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

Resetting versions.

--
versions: +Python 3.3 -Python 2.6, Python 3.1

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

Clang has an -ftrapv option that seems to be less buggy and more complete than 
gcc's.  Compiling and running the test suite with that option enabled looks 
like a good way to catch a lot of these signed overflows.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin v . Löwis]

Martin v. Löwis mar...@v.loewis.de added the comment:

Do we consider these overflows as bugs in Python, or do we declare that we 
expect compilers to do the right thing for the bug fix releases (i.e. care 
only about the default branch). I'd personally vote for the latter - i.e. don't 
apply any of the resulting changes to the maintenance releases, and target the 
issue only for 3.3.

Realistically, a compiler that invokes truly undefined behavior for signed 
overflow has no chance of getting 3.2 compiled correctly, and we have no chance 
of finding all these issues within the lifetime of 3.2.

If that is agreed, I would start committing changes that fix the issues Mark 
already discussed in 2009 (unless he wants to commit them himself).

--
priority: high - normal

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

 don't apply any of the resulting changes to the maintenance releases,
 and target the issue only for 3.3.

That sounds fine to me, though if we find more instances of signed overflow 
that actually trigger test failures in the maintenance branches (like the 
int_pow one) on mainstream compilers, we might want to fix those there too, on 
a case-by-case basis.

To get started, here's a patch that fixes occurrences of signed overflow in the 
bytes, str and tuple hash methods, and also in set lookups.  It also fixes a 
related and minor casting inconsistency in dictobject.c  (which was using 
(size_t)hash  mask in some places, and just 'hash  mask' in others).  These 
are the minimal changes required to get Python to build completely using Clang 
with '-ftrapv' turned on and --with-pydebug enabled.

--
versions:  -Python 2.7, Python 3.2
Added file: http://bugs.python.org/file23237/issue1621_hashes_and_sets.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot devn...@psf.upfronthosting.co.za added the comment:

New changeset 698fa089ce70 by Mark Dickinson in branch 'default':
Issue #1621: Fix undefined behaviour in bytes.__hash__, str.__hash__, 
tuple.__hash__, frozenset.__hash__ and set indexing operations.
http://hg.python.org/cpython/rev/698fa089ce70

--
nosy: +python-dev

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Roundup Robot]

Roundup Robot devn...@psf.upfronthosting.co.za added the comment:

New changeset 5e456e1a9e8c by Mark Dickinson in branch 'default':
Issue #1621: Fix undefined behaviour from signed overflow in get_integer 
(stringlib/formatter.h)
http://hg.python.org/cpython/rev/5e456e1a9e8c

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Jesús Cea Avión]

Changes by Jesús Cea Avión j...@jcea.es:


--
nosy: +jcea

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Alex Gaynor]

Changes by Alex Gaynor alex.gay...@gmail.com:


--
nosy: +alex

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[deadshort]

deadshort cploo...@gmail.com added the comment:

Since this is still dribbling along I'll point out intobject.c:int_pow() and:

prev = ix;  /* Save value for overflow check */
if (iw  1) {
ix = ix*temp;
if (temp == 0)
break; /* Avoid ix / 0 */
if (ix / temp != prev) {
return PyLong_Type.tp_as_number-nb_power(
(PyObject *)v,
(PyObject *)w,
(PyObject *)z);
}
}

which I misclassified in http://bugs.python.org/issue12701

--
nosy: +deadshort

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Terry J. Reedy]

Changes by Terry J. Reedy tjre...@udel.edu:


--
versions:  -Python 2.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Stefan Krah]

Changes by Stefan Krah stefan-use...@bytereef.org:


--
nosy: +skrah

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Dave Malcolm]

Changes by Dave Malcolm dmalc...@redhat.com:


--
nosy: +dmalcolm

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Terry J. Reedy]

Changes by Terry J. Reedy tjre...@udel.edu:


--
versions: +Python 2.7, Python 3.2 -Python 2.5, Python 3.0

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Terry J. Reedy]

Changes by Terry J. Reedy tjre...@udel.edu:


--
versions: +Python 2.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin v. Löwis]

Martin v. Löwis mar...@v.loewis.de added the comment:

 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;

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin v. Löwis]

Martin v. Löwis mar...@v.loewis.de added the comment:

   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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin v. Löwis]

Martin v. Löwis mar...@v.loewis.de added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

Aargh!

s/Wsigned-overflow/Wstrict-overflow/g

Sorry.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

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.

--
nosy: +marketdickinson

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Gregory P. Smith]

Gregory P. Smith g...@krypto.org added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez ism...@namtrac.org added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Mark Dickinson]

Mark Dickinson dicki...@gmail.com added the comment:

 [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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Daniel Diniz]

Changes by Daniel Diniz aja...@gmail.com:


--
nosy: +haypo
stage:  - patch review
versions: +Python 3.1

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Antoine Pitrou]

Changes by Antoine Pitrou pit...@free.fr:


--
nosy: +pitrou

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue1621
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[jan matejek]

Changes by jan matejek [EMAIL PROTECTED]:


--
nosy: +matejcik

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

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

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Martin v. Löwis]

Martin v. Löwis added the comment:

 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.

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Guido van Rossum]

Guido van Rossum added the comment:

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

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

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

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

 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.

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

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

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

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;
}

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Ismail Donmez]

Ismail Donmez added the comment:

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.

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Neal Norwitz]

Neal Norwitz added the comment:

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?

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue1621] Do not assume signed integer overflow behavior

[Guido van Rossum]

Guido van Rossum added the comment:

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...

__
Tracker [EMAIL PROTECTED]
http://bugs.python.org/issue1621
__
___
Python-bugs-list mailing list 
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com