classification
Title: int_pow() implementation is incorrect
Type: behavior Stage: commit review
Components: Versions: Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder: [PATCH] Configure should enable -fwrapv for clang
View: 11149
Assigned To: mark.dickinson Nosy List: adam@NetBSD.org, haypo, loewis, mark.dickinson, python-dev, skrah
Priority: normal Keywords: patch

Created on 2011-09-13 19:46 by adam@NetBSD.org, last changed 2011-09-24 08:04 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
issue12975.diff mark.dickinson, 2011-09-14 18:31 review
listobject_overflow.diff skrah, 2011-09-15 18:01 review
itertools_overflow.diff skrah, 2011-09-15 18:01 review
Messages (23)
msg143985 - (view) Author: Adam (adam@NetBSD.org) Date: 2011-09-13 19:46
int_pow() (from Objects/intobject.c) shows incorrect results when Python is compiled with Clang (llvm.org); long story short: int_pow() function should use 'unsigned long' type instead of 'long' or some code gets optimised out.

Please, refer to this bug report to find out the details:
http://llvm.org/bugs/show_bug.cgi?id=10923
msg143986 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-09-13 19:59
I think this is related to issue #11149. Can you try compiling with
-fwrapv?
msg143990 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-09-13 22:46
I can reproduce your results with a recent clang. gcc has similar
optimization behavior, but for gcc ./configure automatically adds
-fwrapv, which prevents the incorrect results.

I'm closing this as a duplicate of #11149.
msg144013 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-14 07:36
Reopening and assigning to me;  it would be good to fix this in intobject.c as well as adding the Clang-specific -fwrapv fix.
msg144017 - (view) Author: Martin v. Löwis (loewis) * (Python committer) Date: 2011-09-14 09:23
Notice that this "signed overflow" issue is also tracked as #1621. I don't mind keeping this issue open, though - it's unlikely that #1621 will be fixed within this decade. unless somebody does some heroic effort.
msg144034 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-14 18:31
Here's a simple patch.  Is anyone in a good position to see if this fixes the tests failures for Clang (without the fwrapv flag)?
msg144038 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2011-09-14 18:56
I removed -fwrapv from configure and Makefile, but I'm unable to reproduce the issue with clang 2.8 on x86_64 (Fedora 15).
msg144040 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-14 19:06
Thanks Victor; I just managed to install Clang, and it looks I can reproduce the failures.  I'm testing right now to see if the patch fixes them all...
msg144041 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2011-09-14 19:08
> Thanks Victor; I just managed to install Clang,
> and it looks I can reproduce the failures.

What is your clang version? I ran ./python -m test -v test_long to check the issue.
msg144042 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-14 19:17
I've got Clang from MacPorts, on OS X 10.6.8.

iwasawa:cpython mdickinson$ clang --version
clang version 2.9 (tags/RELEASE_29/final)
Target: x86_64-apple-darwin10
Thread model: posix

Without the patch (and before the -fwrapv inclusion), I get the following failures:

20 tests failed:
    test_array test_builtin test_bytes test_ctypes test_float
    test_fractions test_getargs2 test_index test_int test_itertools
    test_list test_long test_long_future test_math test_random test_re
    test_strtod test_tokenize test_types test_xrange

... and also test_decimal, which I had to delete because the failure caused the test run to hang.

With the patch, only test_ctypes is failing, for reasons that I presume are unrelated to int_pow.
msg144044 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2011-09-14 19:34
Aaaah, int_pow. I was testing Python 3.3.

I tested Python 2.7 with clang 2.8, optimization level at -03 and without -fwrapv... I'm still unable to reproduce the issue. It's maybe an optimization introduced by clang 2.9.

--

This issue remembers me the great "What Every C Programmer Should Know About Undefined Behavior" article serie (3 parts).

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html

See also this tool to detect such bug:
http://blog.regehr.org/archives/508
msg144058 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-09-14 22:33
== CPython 2.7.2+ (2.7:a698ad2741da+, Sep 15 2011, 00:17:28) [GCC 4.2.1 Compatible Clang 3.0 (trunk 139637)]
==   FreeBSD-8.0-RELEASE-amd64-64bit-ELF little-endian
==   /usr/home/stefan/pydev/cpython/build/test_python_71451

With clang 3.0 from trunk, the pow() failures are fixed. I still get:

test test_itertools failed -- Traceback (most recent call last):
  File "/usr/home/stefan/pydev/cpython/Lib/test/test_itertools.py", line 788, in test_islice
    self.assertEqual(len(list(islice(count(), 1, 10, maxsize))), 1)
AssertionError: 3 != 1


test test_list failed -- Traceback (most recent call last):
  File "/usr/home/stefan/pydev/cpython/Lib/test/test_list.py", line 59, in test_overflow
    self.assertRaises((MemoryError, OverflowError), mul, lst, n)
AssertionError: (<type 'exceptions.MemoryError'>, <type 'exceptions.OverflowError'>) not raised



But these are exactly the failures from 3.x. so they are probably
unrelated to this issue (and they are "fixed" by -fwrapv).
msg144089 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-09-15 18:08
With issue12975.diff, listobject_overflow.diff and itertools_overflow.diff
I don't get any more failures.


Also, of course issue12975.diff looks correct to me if we assume:

http://mail.python.org/pipermail/python-dev/2009-December/094392.html
http://yarchive.net/comp/linux/signed_unsigned_casts.html


Mark, did you write those rules down somewhere? I had to think
a bit about the unsigned -> signed casts.
msg144092 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-15 19:32
Gah;  did I really misnumber that issue patch?  Sorry.

> Mark, did you write those rules down somewhere?

Well, they're all in the standard, which is publicly available.  (Or at least, a draft of the standard that's pretty much interchangeable with the real thing is publicly available;  Google for n1256.pdf, or see hyperlink [1] below.)

The correctness of the patch depends on:

(1) the 'usual arithmetic conversions', C99 6.3.1.8, paragraph 1.
     This implies that the other (uncast) long argument will be
     converted to unsigned long before the operation is performed.
    This part is safe.  When reading the rules, note that the 'long'
    and 'unsigned long' types have the same rank. (C99 6.3.1.1, 4th
    listed point.)

(2) an assumption that the C implementation will never raise an
    'implementation-defined' signal (C99 6.3.1.3p3).  This seems
    reasonable:  I'm fairly sure that this provision is there mainly
    for systems using ones' complement or sign-magnitude
    representations for signed integers, and it's safe to assume
    that Python won't meet such systems.

(3) an assumption that integer division for negative arguments
    follows C99 semantics, namely that the quotient is rounded
    towards zero.  C99 requires this (C99 6.5.5p6);  the older
    1989 standard allows quotients to be truncated either towards
    zero (like C99), or towards -infinity (like Python does).  In
    the presence of rounding towards -infinity, the style of
    overflow check used in int_pow can fail.  Even on C89 systems,
    truncation is much more common than flooring for this, so I
    think we're safe again here:  I don't know of any existing
    compilers with issues;  new/future compilers are likely to follow
    the C99 standard here.

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
msg144093 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-15 19:33
> an assumption that the C implementation will never raise an
> 'implementation-defined' signal (C99 6.3.1.3p3).

Sorry, this should have been more explicit: "will never raise ... when converting long to unsigned long"
msg144095 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-15 19:44
Those two patches (for listobject and itertools) look fine to me.
msg144098 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-09-15 19:57
Mark Dickinson <report@bugs.python.org> wrote:
> Well, they're all in the standard, which is publicly available. 

I have the real thing. :)

> The correctness of the patch depends on:
> (2) an assumption that the C implementation will never raise an
>     'implementation-defined' signal (C99 6.3.1.3p3).  This seems
>     reasonable:  I'm fairly sure that this provision is there mainly
>     for systems using ones' complement or sign-magnitude
>     representations for signed integers, and it's safe to assume
>     that Python won't meet such systems.

This is what I was concerned about, but the assumption seems safe.
msg144290 - (view) Author: Roundup Robot (python-dev) Date: 2011-09-19 15:38
New changeset 07efe83795b0 by Mark Dickinson in branch '2.7':
Issue #12973: Fix int.__pow__ overflow checks that invoked undefined behaviour, thereby producing incorrect results on Clang.
http://hg.python.org/cpython/rev/07efe83795b0
msg144306 - (view) Author: Roundup Robot (python-dev) Date: 2011-09-19 18:20
New changeset 99b808c94834 by Mark Dickinson in branch '3.2':
Issue #12973: Fix undefined-behaviour-inducing overflow check in list_repeat.
http://hg.python.org/cpython/rev/99b808c94834

New changeset 2dbd5870de0b by Mark Dickinson in branch 'default':
Merge issue #12973 list_repeat fix.
http://hg.python.org/cpython/rev/2dbd5870de0b
msg144308 - (view) Author: Roundup Robot (python-dev) Date: 2011-09-19 18:24
New changeset f8280cf63d9e by Mark Dickinson in branch '2.7':
Backport issue #12973 list_repeat fix from 3.x.
http://hg.python.org/cpython/rev/f8280cf63d9e
msg144485 - (view) Author: Roundup Robot (python-dev) Date: 2011-09-24 08:00
New changeset b378864d8ff3 by Mark Dickinson in branch '3.2':
Issue #12973: Fix itertools bug caused by signed integer overflow.  Thanks Stefan Krah.
http://hg.python.org/cpython/rev/b378864d8ff3

New changeset 18eec56bcf29 by Mark Dickinson in branch 'default':
Merge #12973 itertools fix.
http://hg.python.org/cpython/rev/18eec56bcf29
msg144486 - (view) Author: Roundup Robot (python-dev) Date: 2011-09-24 08:02
New changeset 5a1cb8506cea by Mark Dickinson in branch '2.7':
Backport issue #12973 itertools fix from 3.x.
http://hg.python.org/cpython/rev/5a1cb8506cea
msg144487 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-09-24 08:04
Okay, all fixed here.  Let's add any further signed overflow issues to the issue #1621 discussion.
History
Date User Action Args
2013-01-25 20:09:25mark.dickinsonlinkissue12701 superseder
2011-09-24 08:04:08mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg144487
2011-09-24 08:02:35python-devsetmessages: + msg144486
2011-09-24 08:00:35python-devsetmessages: + msg144485
2011-09-19 18:24:38python-devsetmessages: + msg144308
2011-09-19 18:20:34python-devsetmessages: + msg144306
2011-09-19 15:38:18python-devsetnosy: + python-dev
messages: + msg144290
2011-09-16 19:05:57terry.reedysetresolution: duplicate -> (no value)
stage: resolved -> commit review
2011-09-15 19:57:28skrahsetmessages: + msg144098
2011-09-15 19:44:36mark.dickinsonsetmessages: + msg144095
2011-09-15 19:33:51mark.dickinsonsetmessages: + msg144093
2011-09-15 19:32:06mark.dickinsonsetmessages: + msg144092
2011-09-15 18:08:04skrahsetmessages: + msg144089
2011-09-15 18:01:50skrahsetfiles: + itertools_overflow.diff
2011-09-15 18:01:31skrahsetfiles: + listobject_overflow.diff
2011-09-14 22:33:13skrahsetmessages: + msg144058
2011-09-14 19:34:12hayposetmessages: + msg144044
2011-09-14 19:17:54mark.dickinsonsetmessages: + msg144042
2011-09-14 19:08:59hayposetmessages: + msg144041
2011-09-14 19:06:39mark.dickinsonsetmessages: + msg144040
2011-09-14 18:56:19hayposetnosy: + haypo
messages: + msg144038
2011-09-14 18:31:46mark.dickinsonsetfiles: + issue12975.diff
keywords: + patch
messages: + msg144034
2011-09-14 09:23:20loewissetnosy: + loewis
messages: + msg144017
2011-09-14 07:36:41mark.dickinsonsetstatus: closed -> open

nosy: + mark.dickinson
messages: + msg144013

assignee: mark.dickinson
2011-09-13 22:46:53skrahsetstatus: open -> closed
resolution: duplicate
messages: + msg143990

superseder: [PATCH] Configure should enable -fwrapv for clang
stage: resolved
2011-09-13 19:59:49skrahsetnosy: + skrah
messages: + msg143986
2011-09-13 19:46:49adam@NetBSD.orgcreate