[PATCH] nano malloc allocator algorithm improvement

[Keith Packard]

Maarten van der Schrieck | Things Connected <maarten@thingsconnected.nl>
writes:

> 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:

Oh, that's a great idea. I did the same for realloc when the block was
at the end of the heap; doing the same for malloc is a nice
addition.

> 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.

I re-worked the list management to use a different pattern that makes
this change much less invasive.

https://github.com/picolibc/picolibc/commit/fd2d18bb5ab442f16789c243648d07b4ec8e2b29

-- 
-keith
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/newlib/attachments/20200822/35de7090/attachment.sig>