malloc() in newlib : does it waste memory after one big failure allocation?

Question

I am writing an embedded software for STM32F7 and my libc is newlib-2.4.0.20160527.

I have implemented _sbrk() as follows:

extern intptr_t g_bss_end; /* value after the last byte in .bss */
extern intptr_t g_msp_lim; /* stack buffer starts at this address */

intptr_t _sbrk(ptrdiff_t heap_incr)
{
    static intptr_t heap_end = 0;

    intptr_t prev_heap_end;
    intptr_t new_heap_end;

    if(heap_end == 0) {
        heap_end = (intptr_t)&g_bss_end;
    }

    prev_heap_end = heap_end;
    new_heap_end = prev_heap_end + heap_incr;

    if(new_heap_end >= g_msp_lim) {
        errno = ENOMEM;

        return -1;
    }

    heap_end = new_heap_end;

    return prev_heap_end;
}

Then, when I do the following:

/* total capacity of my heap is 0x40000 */
void * mem = malloc(0x40000);
free(mem); mem = 0;
mem = malloc(0x40000);

everything works fine (i.e., malloc returns non-zero twice).

But when I do the following (for testing purposes):

for(int32_t sz = 0x50000; sz >= 0; sz--) {
    void * mem = malloc(sz);

    if(mem != 0) {
        __BKPT();
        free(mem);

        break;
    }
}

every malloc() fails, even malloc(0) (i.e., __BKPT() is never reached). So, there is no allocated memory on heap in fact (I did not get any mem != 0 so I can not even free() something) and there is also no available memory.

I expected malloc() to fail for every sz > 0x40000 and succeed for every sz <= 0x40000 (assuming free() works fine after each malloc()).

Have I missed something, or this is either a bug or intended behavior in newlib?

Answer 1

The newlib's malloc() does not work properly when allocating whole heap memory due to bad malloc_extend_top() routine in newlib/libc/stdlib/mallocr.c:2137. After a successful call to _sbrk()

  brk = (char*)(MORECORE (sbrk_size)); /* MORECORE = _sbrk */

  /* Fail if sbrk failed or if a foreign sbrk call killed our space */
  if (brk == (char*)(MORECORE_FAILURE) || 
      (brk < old_end && old_top != initial_top))
    return;

it tries to calculate the correction to fit the page alignment:

/* Guarantee alignment of first new chunk made from this space */
front_misalign = (POINTER_UINT)chunk2mem(brk) & MALLOC_ALIGN_MASK;
if (front_misalign > 0) 
{
  correction = (MALLOC_ALIGNMENT) - front_misalign;
  brk += correction;
}
else
  correction = 0;

/* Guarantee the next brk will be at a page boundary */
correction += pagesz - ((POINTER_UINT)(brk + sbrk_size) & (pagesz - 1));

The correction is always positive, because even if the allocation fits perfectly it tries to allocate the next whole page. E.g., if page size is 4096 and the brk + sbrk_size = 4096*n, expression 4096 - ((brk + sbrk_size) & 4095) will give 4096, so the next empty page is required, but there is no space for it.

The routine is handling this situation not properly and leaves just allocated data (brk value), resulting in permanent "unfreeable" whole heap allocation. Such a waste :-)

Answer 2

Tested, works OK.

From 1473e08d2a16ad448afedb7036a476231a785643 Mon Sep 17 00:00:00 2001
From: Jeff Johnston <[email protected]>
Date: Thu, 24 May 2018 23:53:15 -0400
Subject: [PATCH] Fix issue with malloc_extend_top

- when calculating a correction to align next brk to page boundary,
  ensure that the correction is less than a page size
- if allocating the correction fails, ensure that the top size is
  set to brk + sbrk_size (minus any front alignment made)

Signed-off-by: Jeff Johnston <[email protected]>
---
 newlib/libc/stdlib/mallocr.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/newlib/libc/stdlib/mallocr.c b/newlib/libc/stdlib/mallocr.c
index ecc445f..26d1c89 100644
--- a/newlib/libc/stdlib/mallocr.c
+++ b/newlib/libc/stdlib/mallocr.c
@@ -2198,13 +2198,18 @@ static void malloc_extend_top(RARG nb) RDECL INTERNAL_SIZE_T nb;
     /* Guarantee the next brk will be at a page boundary */
     correction += pagesz - ((POINTER_UINT)(brk + sbrk_size) & (pagesz - 1));

+    /* To guarantee page boundary, correction should be less than pagesz */
+    correction &= (pagesz - 1);
+
     /* Allocate correction */
     new_brk = (char*)(MORECORE (correction));
     if (new_brk == (char*)(MORECORE_FAILURE))
       {
    correction = 0;
    correction_failed = 1;
-   new_brk = brk;
+   new_brk = brk + sbrk_size;
+   if (front_misalign > 0)
+     new_brk -= (MALLOC_ALIGNMENT) - front_misalign;
       }

     sbrked_mem += correction;
-- 
1.8.3.1