[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <2760191.lGaqSPkdTl@tjmaciei-mobl5>
Date: Sun, 02 Nov 2025 16:41:46 -0800
From: Thiago Macieira <thiago@...ieira.org>
To: Alejandro Colomar <alx@...nel.org>
Cc: Florian Weimer <fw@...eb.enyo.de>, libc-alpha@...rceware.org,
musl@...ts.openwall.com, Arthur O'Dwyer <arthur.j.odwyer@...il.com>,
Jonathan Wakely <jwakely@...hat.com>
Subject: Re: realloci(): A realloc() variant that works in-place
On Sunday, 2 November 2025 15:58:39 Pacific Standard Time Alejandro Colomar
wrote:
> realloci() would still give a few more. The difference is that if you
> speculate from std::vector, you're speculating, while realloci() gives
> you more without speculation.
Clearly we need to avoid the double speculation. I don't think that will be
prescribed in the C Standard, so speculation would be implementation-defined
behaviour. That leaves room for us to to fine-tune with prototype
implementations, then make a recommendation for implementors.
> > So it's unlikely to return 40 kB,
> > aside of some special circumstances (e.g., an mmap()-backed allocation).
>
> Now that I checked, it seems musl's mmap(2) threshold is in the hundreds
> of kiB. I was expecting it to be lower.
mmap() is more expensive than manipulating bits in memory you already own. And
unless you've dealt with low-level page tables, you may not realise that
munmap() is actually more expensive, because it needs to perform a TLB flush
(or equivalent) in every thread of the process that is currently running. That
explains the mmap threshold.
> How about two consecutive calls?
>
> size = realloci(p, speculative_size);
> if (size != -1)
> goto done;
>
> size = realloci(p, needed_size);
> if (size != -1)
> goto done;
>
> do_actual_realloc();
That works, but I'd prefer if the first call returned to me the maximum that it
could satisfy. And locked it in place, because multi-threading is a thing.
> The problem is that this is asking the implementation to speculate.
>
> Consider the case that a realloci() implementation knows that the
> requested size fails. Let's put some arbitrary numbers:
>
> old_size = 10000;
> requested_size = 30000;
>
> It knows the block can grow to somewhere between 10000 (which it
> currently has) and 30000 (the system reported ENOMEM), but now it has
> the task of allocating as much as it can get. Should it do a binary
> search of the size? Try 20000, then if it fails try 15000, etc.?
> That's speculation, and it would make this function too slow.
That's a good question. To be verified later, but my guess is that the
implementation could return the available limit in this heap. For systems that
use a brk() call like Linux, that's simply the amount of memory to the brk.
For an mmap()-backed arena, that's the available memory to the end of the
arena.
In fact, an mmap()-backed arena usually cannot grow. On Linux, it is possible
to attempt to allocate more pages at the next virtual address using
MAP_FIXED_NOREPLACE, which will fail if either there's no memory or if it
would overlap with an existing mapping. This means the ENOMEM scenario is
indistinguishable from the one where there's something already using the next
address.
This does mean we could have a situation where
realloci(ptr, 30000) = 10240
but maybe
realloci(ptr, 20000) = 20480
> Hmmmmm, if people are going to do this every time they need realloci(),
> then I guess it makes sense to have it more compact. Also, you can have
> a constant EXTRA_GROWTH that you use all the time, so you don't need to
> calculate the speculative size unnecessarily (wasting another line of
> code, plus one for the declaration of the variable).
I don't know if it will be. Again to test with fine-tuning, but my initial idea
is to round up to the next power of two elements or 4 kB, whichever is
smaller.
MIN(ROUND_POWER2(count) * sizeof(T), count * sizeof(T) + 4096)
> I'm starting to like the interface of xallocx(). Prior art often has
> reasons. :)
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Principal Engineer - Intel Data Center - Platform & Sys. Eng.
Download attachment "signature.asc" of type "application/pgp-signature" (871 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
