Problems with mpz_set_str and huge strings

[Stefan Krah]

Hi,

I'm having memory corruption problems when using mpz_set_str for some huge
strings. Valgrind tracks down the problem to an invalid write in __gmpn_sub_n.


Perhaps I'm not using gmp in an intended way, so here are the steps:


System and versions:
=====================

System: Ubuntu 8.10, 64 bit
Version: gmp-4.3.1
Compilers: gcc 4.3.2, gcc 4.1, icc 11.0


Build 32 bit libraries:
========================

export CC=/usr/bin/gcc-4.1    # reproduced with all three compilers above
export CFLAGS="-O0 -g -m32"
./configure ABI=32 --disable-shared --enable-assert --enable-alloca=debug
make
make check                    # no errors
make install


A small test program, convert.c:
=================================

#include <stdio.h>
#include <stdlib.h>
#include "/usr/local/include/gmp.h"

int
main(void)
{
        mpz_t x;
        char *s;
        size_t len, k;

        len = 677741241;

        s = malloc(len+1);
        for (k = 0; k < len; k++) {
                s[k] = '9';
        }
        s[k] = '\0';

        mpz_init(x);
        mpz_set_str(x, s, 10);

        return 0;
}


Compile convert.c:
==================

gcc -Wall -m32 -W -O0 -g -o convert convert.c /usr/local/lib/libgmp.a


Valgrind output:
================

valgrind --tool=memcheck --leak-check=full --leak-resolution=high --db-attach=yes --show-reachable=yes ./convert
==28944== Memcheck, a memory error detector.
==28944== Copyright (C) 2002-2007, and GNU GPL'd, by Julian Seward et al.
==28944== Using LibVEX rev 1854, a library for dynamic binary translation.
==28944== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==28944== Using valgrind-3.3.1-Debian, a dynamic binary instrumentation framework.
==28944== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==28944== For more details, rerun with: -v
==28944== 
==28944== Warning: set address range perms: large range 677741242 (undefined)
==28944== Warning: set address range perms: large range 677741242 (undefined)
==28944== Warning: set address range perms: large range 301218460 (undefined)
==28944== Warning: set address range perms: large range 134348800 (undefined)
==28944== Warning: set address range perms: large range 134348832 (noaccess)
==28944== Warning: set address range perms: large range 268566528 (undefined)
==28944== Warning: set address range perms: large range 268566560 (noaccess)
==28944== Warning: set address range perms: large range 201457664 (undefined)
==28944== Warning: set address range perms: large range 201457696 (noaccess)
==28944== Warning: set address range perms: large range 301218460 (undefined)
==28944== Invalid write of size 4
==28944==    at 0x8056E3A: __gmpn_sub_n (tmp-sub_n.s:143)
==28944==    by 0x8051B74: __gmpn_toom22_mul (toom22_mul.c:114)
==28944==    by 0x804AE68: __gmpn_mul (mul.c:215)
==28944==    by 0x8049110: __gmpn_dc_set_str (set_str.c:247)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==    by 0x8049057: __gmpn_dc_set_str (set_str.c:236)
==28944==  Address 0x30eb433c is not stack'd, malloc'd or (recently) free'd
==28944== 
==28944== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ---- 

(gdb) bt
#0  __gmpn_sub_n () at tmp-sub_n.s:143
#1  0x00000019 in ?? ()
#2  0x08051b75 in __gmpn_toom22_mul (pp=0x30eb433c, ap=0x6cf050b8, an=25, bp=0xa5ba9028, bn=23, scratch=0xb7aecaf8) at toom22_mul.c:114
#3  0x0804ae69 in __gmpn_mul (prodp=0x30eb433c, up=0x6cf050b8, un=25, vp=0xa5ba9028, vn=23) at mul.c:215
#4  0x08049111 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=543, powtab=0xfec4e420, tp=0xa5ba9028)
    at set_str.c:247
#5  0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=1191, powtab=0xfec4e40c, tp=0x30eb4318)
    at set_str.c:236
#6  0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=2487, powtab=0xfec4e3f8, tp=0xa5ba9028)
    at set_str.c:236
#7  0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=5079, powtab=0xfec4e3e4, tp=0x30eb4318)
    at set_str.c:236
#8  0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=10254, powtab=0xfec4e3d0, tp=0xa5ba9028)
    at set_str.c:236
#9  0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=20604, powtab=0xfec4e3bc, tp=0x30eb4318)
    at set_str.c:236
#10 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=41295, powtab=0xfec4e3a8, tp=0xa5ba9028)
    at set_str.c:236
#11 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=82668, powtab=0xfec4e394, tp=0x30eb4318)
    at set_str.c:236
#12 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=165405, powtab=0xfec4e380, tp=0xa5ba9028)
    at set_str.c:236
#13 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=330870, powtab=0xfec4e36c, tp=0x30eb4318)
    at set_str.c:236
#14 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=661800, powtab=0xfec4e358, tp=0xa5ba9028)
    at set_str.c:236
#15 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=1323660, powtab=0xfec4e344, tp=0x30eb4318)
    at set_str.c:236
#16 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=2647380, powtab=0xfec4e330, tp=0xa5ba9028)
    at set_str.c:236
#17 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=5294811, powtab=0xfec4e31c, tp=0x30eb4318)
    at set_str.c:236
#18 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=10589673, powtab=0xfec4e308, tp=0xa5ba9028)
    at set_str.c:236
#19 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=21179388, powtab=0xfec4e2f4, tp=0x30eb4318)
    at set_str.c:236
#20 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=42358809, powtab=0xfec4e2e0, tp=0xa5ba9028)
    at set_str.c:236
#21 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=84717642, powtab=0xfec4e2cc, tp=0x30eb4318)
    at set_str.c:236
#22 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=169435299, powtab=0xfec4e2b8, tp=0xa5ba9028)
    at set_str.c:236
#23 0x08049058 in __gmpn_dc_set_str (rp=0xa5ba9028, str=0x3a714028 '\t' <repeats 200 times>..., str_len=338870613, powtab=0xfec4e2a4, tp=0x30eb4318)
    at set_str.c:236
#24 0x08049058 in __gmpn_dc_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=677741241, powtab=0xfec4e290, tp=0xa5ba9028)
    at set_str.c:236
#25 0x08048c1b in __gmpn_set_str (rp=0x30eb4318, str=0x3a714028 '\t' <repeats 200 times>..., str_len=677741241, base=10) at set_str.c:120
#26 0x08048977 in __gmpz_set_str (x=0xfec4e5fc, str=0x30eb42e2 "", base=10) at set_str.c:130
#27 0x080485b9 in main () at convert.c:22