[PATCH] nano malloc allocator algorithm improvement

[Maarten van der Schrieck | Things Connected]

The current nano malloc implementation has two issues reducing the amount of memory available and increasing fragmentation.

The first issue is that sbrk() will be called to allocate a space with the size of the entire requested alloc_size, even if the last free chunk borders the edge of currently allocated memory. This means that in a system with 20 kb of RAM, you will get ENOMEM when performing this:

tmpbuf = malloc(10*1024);
free(tmpbuf);
tmpbuf2 = malloc(11*1024); // will fail on a 20 kb RAM system

It would be better if malloc would detect if the last free chunk can be simply grown to alloc_size instead. (Or if free() would return the memory to the system by sbrk(-10kb), which is currently impossible.)

The second issue is that a free chunk that is oversized will be cut up in two pieces, where the *second* piece is used for allocation and the first one is kept as a free chunk. Although this is easier/shorter in code (because the free list remains unaffected apart from the size of the free chunk) it leads to an inefficient pattern of memory allocation, and ultimately in fragmentation and slower malloc/free calls.

As an example, again in a system with 20kb, if the above issue would be patched, you will still get ENOMEN when performing this:

tmpbuf = malloc(10*1024);
free(tmpbuf);
tmpbuf2 = malloc(1); // this will end up in the middle of RAM space
tmpbuf3 = malloc(15*1024); // will fail on a 20 kb RAM system

Total impact on binary size (on ARM Thumb) is ~100 bytes.
---
  newlib/libc/stdlib/nano-mallocr.c | 41 ++++++++++++++++++++++++++++---
  1 file changed, 38 insertions(+), 3 deletions(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 6ba0eb74b..9d3462861 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -258,15 +258,50 @@ void * nano_malloc(RARG malloc_size_t s)
      while (r)
      {
          int rem = r->size - alloc_size;
+
+        /* To prevent a trailing but small chunk to be left unused, grow
+         * the available memory and the chunk instead of allocating
+         * alloc_size */
+        if (rem < 0 && r->next == NULL)
+        {
+            /* This is the last chunk, check if there is any allocated
+             * memory after it. */
+            chunk *heap_end = sbrk_aligned(RCALL 0);
+            if ((char *)r + r->size == heap_end)
+            {
+                /* Attempt to allocate the additional memory needed and
+                 * go on as usual */
+                if (sbrk_aligned(RCALL -rem) == (void*)-1)
+                {
+                    RERRNO = ENOMEM;
+                    MALLOC_UNLOCK;
+                    return NULL;
+                }
+                rem = 0;
+                r->size = alloc_size;
+                /* Fall through to regular logic below */
+            }
+        }
          if (rem >= 0)
          {
              if (rem >= MALLOC_MINCHUNK)
              {
                  /* Find a chunk that much larger than required size, break
-                * it into two chunks and return the second one */
-                r->size = rem;
-                r = (chunk *)((char *)r + rem);
+                 * it into two chunks and return the first one.
+                 * Returning the second part would be a bit easier, because
+                 * the chunk list stays intact, but doing that leads to
+                 * memory fragmentation quickly.
+                 */
+                chunk *part2 = (chunk *)((char *)r + alloc_size);
+                part2->size = rem;
+                part2->next = r->next;
                  r->size = alloc_size;
+                if ( p == r )
+                {
+                    free_list = part2;
+                } else {
+                    p->next = part2;
+                }
              }
              /* Find a chunk that is exactly the size or slightly bigger
               * than requested size, just return this chunk */
-- 
2.23.0