extend dl-minimal malloc implementation

From: DJ Delorie <dj@delorie.com>

  Florian Weimer <fweimer@redhat.com> writes:
> It will allow us to use dynarrays and scratch buffers in the dynamic
> linker because we get a working realloc.

Yup, but you still won't be able to migrate those buffers across the
minimal/complete switchover once libc.so's malloc is loaded.

> You can use _Static_assert for that.

Done.

>> +static free_chunk free_list = { 0, 0, NULL };
>
> Can we turn this into a single pointer, to save .bss space?

Done, with suitable fixes throughout.

>> +static free_chunk *
>> +find_on_free_list (void *old_pointer, size_t n, int zero_it)
>
> zero_it should be bool (also in other places).

Fixed.

>> +      /* Shrinking - just reuse the old chunk.  */
>> +      if (old_chunk->size >= n)
>> +	return old_pointer;
>
> Can we put the tail on the free list?

We *can* but unless there's a compelling need to, remember that the
design goals here are (1) keep the code simple and easy to review, and
(2) see #1.

What we *don't* want is for the minimal malloc to grow in complexity
until it rivals the full malloc ;-)

>> +  /* If we're realloc'ing the last block, we either extend it (by
>> +     re-allocating it over the old block) or we copy it (because a new
>> +     noncontiguous mapping was needed).  */
>
> What does “last” mean here?

Reworded.  It's the highest addressed block in the current mmap'd area.

>> +  /* else if it's really big we can't store it on the free list.  */
>> +  if (ch->size == TOOBIG)
>> +    return;
>
> I think we should just fail TOOBIG allocations.

Carlos and I talked briefly about this a while back.  The idea here is
that in the RARE case that we need to allocate more than 2G at a time,
at least my patch won't break that.  And hopefully you won't be free'ing
or realloc'ing that memory.

Alternately (i.e. in the future, if it matters ;) we can divert all
TOOBIG allocations to mmap/munmap directly.

> Would it make sense to keep the free list order by increasing addresses
> and attempt to coalesce neighboring chunks?  The free list should be
> really short, and this should help us to reduce fragmentation.

Only if we care about fragmentation that much, and see it happen during
loading.  Likewise, we don't try to unmap anything.  We assume a small
amount of memory might be wasted by un-reused free'd blocks when we
switch to the full malloc, but I don't see any way to guarantee that
amount is zero anyway.

> Another thing that might be worth considering is to keep the free list
> pointer in a parameter.

It wouldn't match the full malloc API at that point, though.  We would
need to be careful to stop calling those functions before libc.so is
linked in.

We'd still need to async-protect the top-of-heap data, I don't think
we'd be buying much.  If we need to, we can make this malloc async-safe
throughout, but that still only "solves" the problem before libc.so is
linked in.

From 3028f66942b68723a2151ca013d4f9d646fbd697 Mon Sep 17 00:00:00 2001
From: DJ Delorie <dj@delorie.com>
Date: Tue, 20 Jun 2017 12:56:30 -0400
Subject: Extend dl-minimal's malloc() implementation

* elf/dl-minimal.c: Upgrade minimal malloc to allow for reusing
free'd memory.  Migrate malloc/calloc/realloc to morecore(),
add free list, optimize calloc zeroing.
* elf/tst-dl-minimal-malloc.c: New.
* elf/Makefile: Run it.

extend dl-minimal malloc implementation

Commit Message

Comments

Patch