strange malloc behavior with Doug Lea allocator

I have an very small system with only 16kb of heap, no mmap, no swap. I'm using the latest version 2.8.5 of Doug Lea allocator ftp://g.oswego.edu/pub/misc/malloc-2.8.5.c

UPDATE I made a smaller test case that is easier to understand and see what is my problem

If I allocate 8kb, free it, allocate 12kb, it's working (i != NULL), I can allocate the 12 kb:

char *i;
dlstats();
i = dlmalloc(8192);
printf("DEBUG: %p\n", i);
dlstats();
dlfree(i);
dlstats();
i = dlmalloc(12288);
printf("DEBUG: %p\n", i);
dlstats();
dlfree(i);
dlstats();

displays:

heap 0xa00003f0 sbrk 0xa00003f0 arena 0 ordblks 0 usmblks 0 uordblks 0 fordblks 0 keepcost 0
DEBUG: 0xa00003f8
heap 0xa00003f0 sbrk 0xa0002440 arena 8272 ordblks 1 usmblks 8272 uordblks 8200 fordblks 72 keepcost 32
heap 0xa00003f0 sbrk 0xa0002440 arena 8272 ordblks 1 usmblks 8272 uordblks 0 fordblks 8272 keepcost 8232
DEBUG: 0xa00003f8
heap 0xa00003f0 sbrk 0xa0003460 arena 12400 ordblks 1 usmblks 12400 uordblks 12296 fordblks 104 keepcost 64
heap 0xa00003f0 sbrk 0xa0003460 arena 12400 ordblks 1 usmblks 12400 uordblks 0 fordblks 12400 keepcost 12360

If I first allocate a too big buffer (30kb) and then I allocate 8kb, free it, allocate 12kb, it's working (i == NULL), i cannot allocate the 12 kb:

char *i;
dlstats();
i = dlmalloc(30000);
printf("DEBUG: %p\n", i);
dlstats();
i = dlmalloc(8192);
printf("DEBUG: %p\n", i);
dlstats()开发者_运维百科;
dlfree(i);
dlstats();
i = dlmalloc(12288);
printf("DEBUG: %p\n", i);
dlstats();
dlfree(i);
dlstats();

displays:

heap 0xa00003f0 sbrk 0xa00003f0 arena 0 ordblks 0 usmblks 0 uordblks 0 fordblks 0 keepcost 0
DEBUG: 0x0
heap 0xa00003f0 sbrk 0xa00003f0 arena 0 ordblks 0 usmblks 0 uordblks 0 fordblks 0 keepcost 0
DEBUG: 0xa00003f8
heap 0xa00003f0 sbrk 0xa0002430 arena 8256 ordblks 1 usmblks 8256 uordblks 8200 fordblks 56 keepcost 16
heap 0xa00003f0 sbrk 0xa0002430 arena 8256 ordblks 1 usmblks 8256 uordblks 0 fordblks 8256 keepcost 8216
DEBUG: 0x0
heap 0xa00003f0 sbrk 0xa0002430 arena 8256 ordblks 1 usmblks 8256 uordblks 0 fordblks 8256 keepcost 8216
heap 0xa00003f0 sbrk 0xa0002430 arena 8256 ordblks 1 usmblks 8256 uordblks 0 fordblks 8256 keepcost 8216

At every moment, only one allocation is made and freed before allocation another block so the memory should never be fragmented.

---

I had the answer from Doug Lea:

If an attempt to extend (or initialize) contiguous sbrk's segment fails, sysalloc marks the space as non-contiguous, to avoid continual re-failures which would otherwise disrupt transitions from MORECORE to MMAP when availble.

This causes subsequent segments to not be mergeable. There is currently no way to override this behavior. But you should be able to work around it by removing lines 4113-4

  else
    disable_contiguous(m); /* Don't try contiguous path in the future */

In the future, I'll consider adding a way to control this in the course of some other planned support for page-protection

---

I think this paragraph (from wikipedia, so no guarantees) explains why you are seeing this behaviour:

dlmalloc has a fairly weak free space segment coalescer algorithm, mainly because free space coalescing tends to be extremely slow due to causing TLB cache exhaustion. It is called every (by default) 4096 free() operations and it works by iterating each of the segments previously requested from the system which were not contiguously returned by the system. It tries to identify large ranges of memory which contain no allocated blocks and breaking its segment into two with the free memory being returned to the system. This algorithm works well if dlmalloc is the sole user of the VM system, however if dlmalloc is used simultaneously with another allocator then dlmalloc's free space coalescer can fail to correctly identify opportunities for free memory release.

http://en.wikipedia.org/wiki/Malloc#dlmalloc_and_its_derivatives