large alloc problems (possible int overflow)

[GoogleCodeExporter]

What steps will reproduce the problem?

1.

compile this and link with tcmalloc from the 2.0 release (compiled from source 
with the compiler below):

#include <stdlib.h>
#include <stdio.h>

main()
{
    void *p;
    size_t t = 2600000000;

    p = malloc(1);
    printf("%p\n", p);
    p = realloc(p, t);
    if (!p) { fprintf(stderr, "realloc error"); }
    p = realloc(p, t+100000000);
    if (!p) { fprintf(stderr, "realloc 2 error"); }
}

I used gcc version 4.4.5 (Debian 4.4.5-8)
Target: x86_64-linux-gnu

Configured with: ../src/configure -v --with-pkgversion='Debian 4.4.5-8' 
--with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs 
--enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr 
--program-suffix=-4.4 --enable-shared --enable-multiarch 
--enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib 
--without-included-gettext --enable-threads=posix 
--with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls 
--enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc 
--with-arch-32=i586 --with-tune=generic --enable-checking=release 
--build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix

2. ./a.out shows

14508064
tcmalloc: large alloc 2600001536 bytes == 0xee2000 @  0x7ff92ed1593d 
0x7ff92ed363e7 0x400784 0x7ff92e9b9c8d 0x400679
tcmalloc: large alloc 18446744072664588288 bytes == (nil) @  0x7ff92ed1593d 
0x7ff92ed3685d 0x4007cd 0x7ff92e9b9c8d 0x400679
tcmalloc: large alloc 2700001280 bytes == 0x9c0dc000 @  0x7ff92ed1593d 
0x7ff92ed363e7 0x4007cd 0x7ff92e9b9c8d 0x400679

The second message is obviously problematic. 

Original issue reported on code.google.com by myanni...@gmail.com on 20 Jan 2013 at 12:12

[GoogleCodeExporter]

oops the output is from an earlier version using %lu instead of %p in the 
printf - in case anyone is wondering (no relevant change)

Original comment by myanni...@gmail.com on 20 Jan 2013 at 12:14

[GoogleCodeExporter]

Interesting. Here is the output on a 32-bit machine. It seems to exhibit a 
similar oddity with the second log message:

david@hatch:~/gperftools/patch-test$ ./main 
0x978c018
tcmalloc: large alloc 2600001536 bytes == 0x1c7d8000 @  0x4e493c 0x80485ad 
0x129113
tcmalloc: large alloc 3250003968 bytes == (nil) @  0x4e4f3f 0x80485f6 0x129113
tcmalloc: large alloc 2700001280 bytes == (nil) @  0x4e493c 0x80485f6 0x129113

I made a couple of quick logging modifications and got this:

david@hatch:~/gperftools/patch-test$ g++ main.cpp -g -O0 -ltcmalloc -o main
david@hatch:~/gperftools/patch-test$ ./main 
0x9f10018
tcmalloc: large alloc num_pages=317383 kPageShift=13 2600001536 bytes == 
0x1c7c4000 @  0x63795c 0x80485ad 0x320113
tcmalloc: large alloc num_pages=396729 kPageShift=13 3250003968 bytes == (nil) 
@  0x637f5f 0x80485f6 0x320113
tcmalloc: large alloc num_pages=329590 kPageShift=13 2700001280 bytes == (nil) 
@  0x63795c 0x80485f6 0x320113

Which seems to show a significant jump in the number of pages on the second log 
line.

Original comment by chapp...@gmail.com on 10 Mar 2013 at 8:58

• Changed state: Started

[GoogleCodeExporter]

Seems that the second realloc ends up calling into 
src/tcmalloc.cc:do_malloc_pages twice. The first seems to be for pulling a 

david@hatch:~/gperftools/patch-test$ ./main 
0x960a018
tcmalloc: large alloc size=2600001536 num_pages=317383 kPageShift=13 2600001536 
bytes == 0x1c854000 @  0xe41888 0x80485ad 0xc34113
0x1c854000
tcmalloc: large alloc size=3250003968 num_pages=396729 kPageShift=13 3250003968 
bytes == (nil) @  0xe41eab 0x804860a 0xc34113
tcmalloc: large alloc size=2700001280 num_pages=329590 kPageShift=13 2700001280 
bytes == (nil) @  0xe41888 0x804860a 0xc34113
(nil)

Original comment by chapp...@gmail.com on 10 Mar 2013 at 9:15

[GoogleCodeExporter]

I think that the backtrace here explains it. Seems to be a natural growth 
algorithm built in to tcmalloc. Refer to 
src/tcmalloc.cc:do_realloc_with_callback:

1257   // Reallocate if the new size is larger than the old size,
1258   // or if the new size is significantly smaller than the old size.
1259   // We do hysteresis to avoid resizing ping-pongs:
1260   //    . If we need to grow, grow to max(new_size, old_size * 1.X)
1261   //    . Don't shrink unless new_size < old_size * 0.Y
1262   // X and Y trade-off time for wasted space.  For now we do 1.25 and 0.5.
1263   const size_t lower_bound_to_grow = old_size + old_size / 4ul;
1264   const size_t upper_bound_to_shrink = old_size / 2ul;
1265   if ((new_size > old_size) || (new_size < upper_bound_to_shrink)) {
1266     // Need to reallocate.
1267     void* new_ptr = NULL;
1268 
1269     if (new_size > old_size && new_size < lower_bound_to_grow) {
1270       new_ptr = do_malloc_no_errno_or_cpp_alloc(lower_bound_to_grow);
1271     }
1272     if (new_ptr == NULL) {
1273       // Either new_size is not a tiny increment, or last do_malloc failed.
1274       new_ptr = do_malloc_or_cpp_alloc(new_size);
1275     }

Breakpoint 2, do_malloc_pages (size=2600000000, heap=0x80cc900)
    at src/tcmalloc.cc:1060
1060      size = num_pages << kPageShift;
(gdb) bt
#0  do_malloc_pages (size=2600000000, heap=0x80cc900) at src/tcmalloc.cc:1060
#1  do_malloc_no_errno (size=2600000000) at src/tcmalloc.cc:1102
#2  do_malloc (size=2600000000) at src/tcmalloc.cc:1107
#3  do_malloc_or_cpp_alloc (size=2600000000) at src/tcmalloc.cc:1027
#4  do_realloc_with_callback (
    invalid_get_size_fn=0x144420 <(anonymous namespace)::InvalidGetSizeForRealloc(void const*)>, 
    invalid_free_fn=0x144360 <(anonymous namespace)::InvalidFree(void*)>, 
    new_size=2600000000, old_ptr=0x80ee018) at src/tcmalloc.cc:1274
#5  do_realloc (new_size=2600000000, old_ptr=0x80ee018) at src/tcmalloc.cc:1297
#6  tc_realloc (old_ptr=0x80ee018, new_size=2600000000) at src/tcmalloc.cc:1600
#7  0x080485ad in main () at main.cpp:11
(gdb) c
Continuing.
tcmalloc: large alloc size=2600001536 num_pages=317383 kPageShift=13 2600001536 
bytes == 0x1d056000 @  0x168888 0x80485ad 0x1af113
0x1d056000

Breakpoint 2, do_malloc_pages (size=3250001920, heap=0x80cc900)
    at src/tcmalloc.cc:1060
1060      size = num_pages << kPageShift;
(gdb) bt
#0  do_malloc_pages (size=3250001920, heap=0x80cc900) at src/tcmalloc.cc:1060
#1  do_malloc_no_errno (size=3250001920) at src/tcmalloc.cc:1102
#2  do_malloc_no_errno_or_cpp_alloc (size=3250001920) at src/tcmalloc.cc:1031
#3  do_realloc_with_callback (
    invalid_get_size_fn=0x144420 <(anonymous namespace)::InvalidGetSizeForRealloc(void const*)>, 
    invalid_free_fn=0x144360 <(anonymous namespace)::InvalidFree(void*)>, 
    new_size=2700000000, old_ptr=0x1d056000) at src/tcmalloc.cc:1270
#4  do_realloc (new_size=2700000000, old_ptr=0x1d056000)
    at src/tcmalloc.cc:1297
#5  tc_realloc (old_ptr=0x1d056000, new_size=2700000000)
    at src/tcmalloc.cc:1600
#6  0x0804860a in main () at main.cpp:14
(gdb) c
Continuing.
tcmalloc: large alloc size=3250003968 num_pages=396729 kPageShift=13 3250003968 
bytes == (nil) @  0x168eab 0x804860a 0x1af113

Breakpoint 2, do_malloc_pages (size=2700000000, heap=0x80cc900)
    at src/tcmalloc.cc:1060
1060      size = num_pages << kPageShift;
(gdb) bt
#0  do_malloc_pages (size=2700000000, heap=0x80cc900) at src/tcmalloc.cc:1060
#1  do_malloc_no_errno (size=2700000000) at src/tcmalloc.cc:1102
#2  do_malloc (size=2700000000) at src/tcmalloc.cc:1107
#3  do_malloc_or_cpp_alloc (size=2700000000) at src/tcmalloc.cc:1027
#4  do_realloc_with_callback (
    invalid_get_size_fn=0x144420 <(anonymous namespace)::InvalidGetSizeForRealloc(void const*)>, 
    invalid_free_fn=0x144360 <(anonymous namespace)::InvalidFree(void*)>, 
    new_size=2700000000, old_ptr=0x1d056000) at src/tcmalloc.cc:1274
#5  do_realloc (new_size=2700000000, old_ptr=0x1d056000)
    at src/tcmalloc.cc:1297
#6  tc_realloc (old_ptr=0x1d056000, new_size=2700000000)
    at src/tcmalloc.cc:1600
#7  0x0804860a in main () at main.cpp:14
(gdb) c

Original comment by chapp...@gmail.com on 10 Mar 2013 at 9:20

[GoogleCodeExporter]

Ok so got a bit side tracked there :). Looking back on this with a fresh set of 
eyes I get the following. In the 332-bit case:

    3250003968 = C1B72000

In the 64-bit case:

    18446744072664588288 = FFFFFFFFC1B72000

So as you can see, in the 64-bit case the upper 32-bits are all set to 1 for 
some reason. Will have to dig a bit deeper once I get a 64-bit VM up and 
running.

Original comment by chapp...@gmail.com on 12 Mar 2013 at 4:43