Bug#260767: double-free on small allocations causes infinite loop or SIGSEGV in malloc

[Jeff Licquia <licquia@progeny.com>]

Package: libc6
Version: 2.3.2.ds1-13
Severity: serious
Tags: sarge sid

Small allocations via malloc() and friends uses the "fastbin" facility
to optimize situations where lots of small allocations and deallocations
of memory are needed.  Basically, small allocations are not freed right
away; instead, they are kept in an array of null-terminated
singly-linked lists (where the array indexes act as hashes of the
allocation sizes), and are handed back out on the next allocation.

Unfortunately, the fastbin facility does not do adequate error checking
in the case of a double free.  When free() is called and a fastbin is
considered appropriate, the memory in question is tacked on to the front
of the list, with its "fd" pointer ("forward") pointing to the old first
node of the list:

   Before free(A): B -> C -> NULL
   After free(A):  A -> B -> C -> NULL

Allocations simply pull off the first node, making each fastbin a LIFO
queue.

If A is freed twice in a row, A gets tacked to the front of the list on
the first free.  On the second free, the first node (A) is saved, the
new node (also A) is set to the first node, and the new first node's
pointer to the next node (A's "fd" pointer) is set to the old first node
(A).  This creates an infinite loop when the fastbin must be traversed
for bookkeeping (malloc_consolidate), which happens (among other
occasions) with larger allocations.

Here is some code that reproduces this:

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

int main(int argc, char *argv[])
{
    char *one, *two, *three;

    printf("doing small allocations\n");

    one = (char *) malloc(2);
    two = (char *) malloc(2);
    three = (char *) malloc(2);

    printf("freeing the last allocation twice\n");

    free(three);
    free(three);

    printf("allocating a lot of memory\n");

    three = (char *) malloc(1048576);

    printf("done\n");
    return 0;
}

On my i386 system, this segfaults fairly quickly in the middle of the
last malloc():

----------
(gdb) break main
Breakpoint 1 at 0x80483d4: file test.c, line 8.
(gdb) run
Starting program: /home/jeff/tmp/libc-malloc-test/test

Breakpoint 1, main (argc=1, argv=0xbffffbd4) at test.c:8
8           printf("doing small allocations\n");
(gdb) n
doing small allocations
10          one = (char *) malloc(2);
(gdb) n
11          two = (char *) malloc(2);
(gdb) n
12          three = (char *) malloc(2);
(gdb) n
14          printf("freeing the last allocation twice\n");
(gdb) n
freeing the last allocation twice
16          free(three);
(gdb) n
17          free(three);
(gdb) n
19          printf("allocating a lot of memory\n");
(gdb) n
allocating a lot of memory
21          three = (char *) malloc(1048576);
(gdb) n

Program received signal SIGSEGV, Segmentation fault.
malloc_consolidate (av=0x40147fc0) at malloc.c:4368
4368    malloc.c: No such file or directory.
        in malloc.c
(gdb) bt
#0  malloc_consolidate (av=0x40147fc0) at malloc.c:4368
#1  0x40089ce8 in _int_malloc (av=0x40147fc0, bytes=135065) at
malloc.c:3797
#2  0x40088ed3 in __libc_malloc (bytes=1048576) at malloc.c:3296
#3  0x08048447 in main (argc=1, argv=0xbffffbd4) at test.c:21
(gdb)
----------

In researching this bug, I learned that malloc was reimplemented in
glibc 2.3, so I cannot say if this bug affects glibc 2.2 or earlier.

The severity deserves an explanation.  I found this bug as part of my
work on getting Debian in shape for LSB 2.0.  It appears that test
/tset/LSB.os/genuts/glob/T.glob 29 does a double-free which tweaks this
bug.  That test ends up succeeding, but the next test (test 30) hangs at
the very first attempt to allocate memory through no fault of its own. 
This causes bogus test failures, which will have an impact on Debian's
ability to certify under at least LSB 2.0.  I suspect that the LSB 1.3
version of this test will experience similar problems.

One might argue that the LSB's double-free is the real problem, and I
will indeed be working with the LSB people to get this problem solved. 
Unfortunately, it's very possible that the LSB will not be in a position
to fix this bug in a timely manner, and thus it would be better to fix
the underlying incorrect behavior in glibc.

I won't argue with a severity adjustment, though.

I will have to write a workaround patch to fix this problem, and will
attach it to this bug report when it is ready.