Integer multiplication overflow

[8c52cf18-3922-45e4-ba86-c360b31a3394]

BPO	215919
Nosy	@tim-one, @loewis

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = None closed_at = created_at = labels = ['interpreter-core'] title = 'Integer multiplication overflow' updated_at = user = 'https://bugs.python.org/lo-lan-do' ``` bugs.python.org fields: ```python activity = actor = 'jhylton' assignee = 'jhylton' closed = True closed_date = None closer = None components = ['Interpreter Core'] creation = creator = 'lo-lan-do' dependencies = [] files = [] hgrepos = [] issue_num = 215919 keywords = [] message_count = 18.0 messages = ['1794', '1795', '1796', '1797', '1798', '1799', '1800', '1801', '1802', '1803', '1804', '1805', '1806', '1807', '1808', '1809', '1810', '1811'] nosy_count = 4.0 nosy_names = ['tim.peters', 'loewis', 'jhylton', 'lo-lan-do'] pr_nums = [] priority = 'high' resolution = 'fixed' stage = None status = 'closed' superseder = None type = None url = 'https://bugs.python.org/issue215919' versions = [] ```

[8c52cf18-3922-45e4-ba86-c360b31a3394]

roland@cachemir ~ $ python2.0 
Python 2.0b2 (#3, Oct  3 2000, 16:30:25) 
[GCC 2.95.2 20000220 (Debian GNU/Linux)] on linux2
Type "copyright", "credits" or "license" for more information.
>>> 1+1
2
>>> 1*1
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
OverflowError: integer multiplication
>>> 

Last CVS update 2000-10-03 around 14:00 UTC. Last before that was some weeks ago, sorry for not being precise. Compiled with ./configure --prefix=/usr/local/ && make, su and make install. Only personal change is the use of readline in Modules/Setup.local. Did I do something wrong?

[03bde425-37ce-4291-88bd-d6cecc46a30e]

What happens when you run "make test"? It looks like there is something fundamentally broken, but I can't tell what it is. If 1*1 fails, I expect the rest of the test suite to also report errors.

[8c52cf18-3922-45e4-ba86-c360b31a3394]

make test shows me plenty of lines looking like this one (except the name of the test changes):

test_grammar test test_grammar crashed -- exceptions.OverflowError: integer multiplication

I also get messages along the lines of 'test test_dbm skipped -- No module named dbm', but I guess these ones are OK.

[03bde425-37ce-4291-88bd-d6cecc46a30e]

Can you include the complete output?

[8c52cf18-3922-45e4-ba86-c360b31a3394]

[In case the bug would be caused by a recent upgrade to a beta glibc, I tried the '1*1' test with Python 1.5.2. No bug visible there.]

$ make distclean && ./configure --prefix=/usr/local/ && make
$ make test &> test.log

It seems that 'make test' somehow hangs when testing threads, so I cut at that point. I hope the relevant info is shown before that point. Here goes...

PYTHONPATH= ./python -tt ./Lib/test/regrtest.py -l
Unhandled exception in thread:
test_grammar
test test_grammar crashed -- exceptions.OverflowError: integer multiplication
test_opcodes
test_operations
test_builtin
test test_builtin crashed -- exceptions.OverflowError: integer multiplication
test_exceptions
test_types
test test_types crashed -- exceptions.OverflowError: integer multiplication
test_MimeWriter
test_StringIO
test_al
test test_al skipped --  No module named al
test_array
test test_array crashed -- exceptions.OverflowError: integer multiplication
test_atexit
test_audioop
test test_audioop skipped --  No module named audioop
test_augassign
test test_augassign crashed -- exceptions.OverflowError: integer multiplication
test_binascii
test_binhex
test test_binhex crashed -- exceptions.OverflowError: integer multiplication
test_bsddb
test_cd
test test_cd skipped --  No module named cd
test_cfgparser
test test_cfgparser crashed -- exceptions.OverflowError: integer multiplication
test_cgi
test test_cgi crashed -- exceptions.OverflowError: integer multiplication
test_cl
test test_cl skipped --  No module named cl
test_class
test_cmath
test_compile
test_contains
test_cookie
test test_cookie crashed -- exceptions.OverflowError: integer multiplication
test_cpickle
test_crypt
test test_crypt skipped --  No module named crypt
test_dbm
test test_dbm skipped --  No module named dbm
test_dl
test test_dl skipped --  No module named dl
test_dospath
test_errno
test_extcall
test_fcntl
test_file
test_fork1
test_format
test_gc
test_gdbm
test test_gdbm skipped --  No module named gdbm
test_getopt
test_gettext
test test_gettext crashed -- exceptions.OverflowError: integer multiplication
test_gl
test test_gl skipped --  No module named gl
test_grp
test_gzip
test test_gzip skipped --  No module named zlib
test_hash
test_imageop
test test_imageop skipped --  No module named imageop
test_imgfile
test test_imgfile skipped --  No module named imgfile
test_largefile
test test_largefile skipped --  platform does not have largefile support
test_linuxaudiodev
test test_linuxaudiodev skipped --  No module named linuxaudiodev
test_long
test test_long crashed -- exceptions.OverflowError: integer multiplication
test_longexp
test_math
test_md5
test_mimetools
test test_mimetools crashed -- exceptions.AttributeError: encode
test_minidom
test test_minidom skipped --  No module named pyexpat
test_mmap
test test_mmap crashed -- exceptions.OverflowError: integer multiplication
test_new
test_nis
test test_nis skipped --  No module named nis
test_ntpath
test_openpty
test_operator
test test_operator failed -- Writing: 'mul(5, 2) = <class exceptions.OverflowError at 0x818f41c>: 10 expected', expected: 'testing:
 neg\012testing: or_\012testing: pos\012testing: repeat\012testing: rshift'
test_parser
test_pickle
test_pkg
test_poll
test test_poll crashed -- exceptions.OverflowError: integer multiplication
test_popen2
test_posixpath
test_pow
test test_pow crashed -- exceptions.OverflowError: integer multiplication
test_pty
test test_pty skipped --  No module named termios
test_pwd
test_pyexpat
test test_pyexpat skipped --  cannot import name expat
test_re
test test_re crashed -- exceptions.OverflowError: integer multiplication
test_regex
test_rfc822
test test_rfc822 crashed -- exceptions.OverflowError: integer multiplication
test_rgbimg
test test_rgbimg skipped --  No module named rgbimg
test_rotor
test_sax
test test_sax skipped --  cannot import name expat
test_select
test_sha
test_signal
test_socket
test_sre
test test_sre failed -- Writing: "sre.match(r'(a)|(b)', 'b').start(1)", expected: ''
test_strftime
test test_strftime crashed -- exceptions.OverflowError: integer multiplication
test_string
test_strop
test_struct
test test_struct crashed -- exceptions.OverflowError: integer multiplication
test_sunaudiodev
test test_sunaudiodev skipped --  No module named sunaudiodev
test_thread
Traceback (most recent call last):
  File "./Lib/test/test_thread.py", line 21, in task
    delay = random.random() * numtasks
  File "/home/roland/perso/src/sourceforge/python/dist/src/Lib/whrandom.py", line 71, in random
    x = (171 * x) % 30269
OverflowError: integer multiplication

[03bde425-37ce-4291-88bd-d6cecc46a30e]

Two more questions: 1) What platform? Is this a 64-bit machine? A regular x86? 2) Could you run this under gdb and report where exactly the error is being generated? The exception is raised in Objects/intobject.c. I would set a breakpoint at the top of int_mul() and step through the function.

[8c52cf18-3922-45e4-ba86-c360b31a3394]

1) Regular i686 (sez uname). 2) It seems that ah and bh are 1 and not 0 like they should. A bit of printf-debugging shows me that LONG_BIT/2 is 32, so somehow 1 >> 32 != 0, which seems most strange and bizarre to me. On the other hand, gcc tells me the following when I compile:

intobject.c: In function `int_mul': intobject.c:327: warning: right shift count >= width of type

I hope he [gcc] still does the rshift, but I'm no gcc guru. Hope this helps...

[03bde425-37ce-4291-88bd-d6cecc46a30e]

This does help. The compiler warning is a bad sign. I notice that you're using a more recent version of gcc than I have installed. I'll try building with a newer gcc, but in the interim it may help if you compile the following test program:

#include <stdio.h>
#include <ctype.h>

#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif

#ifndef LONG_BIT
#define LONG_BIT (CHAR_BIT * sizeof(long))
#endif

int main()
{
    int a, b;
    a = 1;
    b = a;
    a = a >> (LONG_BIT / 2);
    printf("CHAR_BIT = %d, LONG_BIT = %d\n", CHAR_BIT, LONG_BIT);
    printf("%d >> %d == %d\n", b, LONG_BIT/2, a);
    return 0;
}

On my system it compiles without warning using gcc -Wall and produces the following output:

CHAR_BIT = 8, LONG_BIT = 32
1 >> 16 == 0

What output do you get? What is sizeof(long) on your platform? Does ctype.h define CHAR_BIT or LONG_BIT?

[8c52cf18-3922-45e4-ba86-c360b31a3394]

Your test program compiles without warning and gives the same results as yours here. sizeof(long) is 4, limits.h defines CHAR_BIT to be 8. LONG_BIT is defined in bits/xopen_lim.h to be 32.

[8c52cf18-3922-45e4-ba86-c360b31a3394]

Now if I replace LONG_BIT/2 by LONG_BIT in your test program: roland@cachemir /tmp $ gcc -Wall test.c && ./a.out test.c: In function `main': test.c:20: warning: right shift count >= width of type CHAR_BIT = 8, LONG_BIT = 32 1 >> 32 == 1 roland@cachemir /tmp $

So I guess it's really something to do with gcc. Drat.

[03bde425-37ce-4291-88bd-d6cecc46a30e]

I'll see if I can reproduce the problem with GCC 2.95.2

[03bde425-37ce-4291-88bd-d6cecc46a30e]

I can't reproduce this on my system with gcc-2.95.2

I'm puzzled by your last comment about replacing LONG_BIT/2 with LONG_BIT and getting the warning. I really don't understand why the code is generating a warning at compile time.

line 327 of Object/intobject.c is this right: ah = a >> (LONG_BIT/2); And on your platform LONG_BIT == 32? And it generates the warning? Can you print the value of LONG_BIT/2 at just the time it is used in int_mul?

[61337411-43fc-4a9c-b8d5-4060aede66d0]

Instead of printing the value of LONG_BIT, I recommend to compile intobject with --save-temps. When invoking make, catch the line that compiles intobject.c, copy it and add --save-temps. Then report the fragment of intobject.i that corresponds to int_mul.

Please also report the exact version of glibc you are using. 2.1.93 sometimes gets the order of includes wrong, so that LONG_BIT ends up being defined as 64.

[8c52cf18-3922-45e4-ba86-c360b31a3394]

You're [Martin v. Löwis] probably right about the libc stuff. I'm using 2.1.94 (as installed by the Debian unstable distribution). After inserting

printf ("ah: %d, LONG_BIT: %d, LONG_BIT/2: %d\n", ah, LONG_BIT, LONG_BIT/2);

I can clearly see that LONG_BIT is 64. The appropriate intobject.i section reads:

int_mul(PyIntObject *v, PyIntObject *w)
{
        long a, b, ah, bh, x, y;
        int s = 1;

        a = v->ob_ival;
        b = w->ob_ival;
        ah = a >> (64 /2);
        bh = b >> (64 /2);
        printf ("ah: %d, LONG_BIT: %d, LONG_BIT/2: %d\n", ah, 64 , 64 /2);

Does this give enough confirmation for me to submit a Debian bug on the libc6 package?

[8c52cf18-3922-45e4-ba86-c360b31a3394]

After a bit of investigation (thanks to the Debian maintainer of libc6) it appears that #define'ing _GNU_SOURCE causes some include file or other to do Not The Right Thing. Namely,

define'ing LONG_BIT to 64 while LONG_MAX is correct

(0x7FFFFFFFL).

I'll continue investigating (though maybe not as intensively, I'm getting a bit flummoxed...)

[tim-one]

Note that I just checked in changes to intobject.c and pyport.h to do a compile-time #error if LONG_BIT appears to be insanely defined by the platform.

[8c52cf18-3922-45e4-ba86-c360b31a3394]

True. And I confirm that this breaks compilation on my system :-)

I'll try to get in touch with the Debian libc maintainer to see if that's Debian-specific or not. I trust him to forward the bug report upstream if need be. Stay tuned.

[03bde425-37ce-4291-88bd-d6cecc46a30e]

The fix is to raise an error at compile time if LONG_BITS is assigned an unreasonable value by the compiler/C library headers.

This is fix in revision 2.21 of Include/pyport.h and rev 2.51 of Object/intobject.h