Re: [PATCH] nano malloc allocator algorithm improvement

Keith Packard via Newlib <[email protected]> Sat, 22 Aug 2020 15:57:54 -0700

Newsgroups	gmane.comp.lib.newlib
Message-ID	<[email protected]>

Maarten van der Schrieck | Things Connected <[email protected]>
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

signature.asc (application/pgp-signature, 832 B)