rewrite bump allocator to fix corner cases, decouple from expand_heap
authorRich Felker <dalias@aerifal.cx>
Wed, 3 Jun 2020 22:13:18 +0000 (18:13 -0400)
committerRich Felker <dalias@aerifal.cx>
Wed, 3 Jun 2020 22:13:18 +0000 (18:13 -0400)
commitc4694f4061aa393e82cf3b587a56a86c1311f438
tree68ec00f1cf02e794cf59eec9557920bd131e3141
parent135c94f097c8a82ba29cc184b1ee6a9a69da04ed
rewrite bump allocator to fix corner cases, decouple from expand_heap

this affects the bump allocator used when static linking in programs
that don't need allocation metadata due to not using realloc, free,
etc.

commit e3bc22f1eff87b8f029a6ab31f1a269d69e4b053 refactored the bump
allocator to share code with __expand_heap, used by malloc, for the
purpose of fixing the case (mainly nommu) where brk doesn't work.
however, the geometric growth behavior of __expand_heap is not
actually well-suited to the bump allocator, and can produce
significant excessive memory usage. in particular, by repeatedly
requesting just over the remaining free space in the current
mmap-allocated area, the total mapped memory will be roughly double
the nominal usage. and since the main user of the no-brk mmap fallback
in the bump allocator is nommu, this excessive usage is not just
virtual address space but physical memory.

in addition, even on systems with brk, having a unified size request
to __expand_heap without knowing whether the brk or mmap backend would
get used made it so the brk could be expanded twice as far as needed.
for example, with malloc(n) and n-1 bytes available before the current
brk, the brk would be expanded by n bytes rounded up to page size,
when expansion by just one page would have sufficed.

the new implementation computes request size separately for the cases
where brk expansion is being attempted vs using mmap, and also
performs individual mmap of large allocations without moving to a new
bump area and throwing away the rest of the old one. this greatly
reduces the need for geometric area size growth and limits the extent
to which free space at the end of one bump area might be unusable for
future allocations.

as a bonus, the resulting code size is somewhat smaller than the
combined old version plus __expand_heap.
src/malloc/lite_malloc.c