Re: [Libguestfs] [libnbd PATCH] common/utils/vector: Better overflow handling
On Tue, Nov 09, 2021 at 02:14:38PM +0200, Nir Soffer wrote:
> @@ -44,12 +44,14 @@ generic_vector_reserve (struct
generic_vector *v, size_t n, size_t itemsize)
> size_t reqcap, newcap;
>
> reqcap = v->cap + n;
> - if (reqcap < v->cap)
> + if (reqcap * itemsize < v->cap * itemsize) {
> + errno = ENOMEM;
> return -1; /* overflow */
> + }
>
> newcap = (v->cap * 3 + 1) / 2;
Should we use:
newcap = v->cap + (v->cap + 1) / 2
so we don't overflow too early?
Sure, nice improvement. On a 32-bit platform, if v->cap is
2,000,000,000, this changes that particular calculation from
852,516,352 to 3,000,000,000. But then again, on a 32-bit platform,
it is unlikely that you have enough address space to hold that many
items in memory in the first place.
And if we overflow - meaning that we cannot grow by factor of 1.5,
grow to maximum size:
if (newcap * itemsize < v->cap * itemsize)
newcap = SIZE_MAX / itemsize;
This makes a difference when itemsize is 1 or 2. The current
code will stop growing efficiently when allocation is 1.45g, and
then go back to realloc() on every call.
Also an interesting idea, but I don't think it's necessary. After
all, this only matters on a 32-bit platform; but attempting to realloc
nearly 4G of memory in one call WILL fail (with a 32-bit address
space, you're lucky if you can address more than 3G, because the OS
reserved another 1G for itself; not to mention that it is not just
this one array that you are trying to resize, but everything else
already in memory that is competing for usage) - you've probably hit
ENOMEM long before getting to even the 2.7G cutoff point where we
degrade back to linear realloc.
> - if (newcap < reqcap)
> + if (newcap * itemsize < reqcap * itemsize)
> newcap = reqcap;
If we handle overflow before, we can keep the old check
comparing caps.
I can post a patch with this changes if you like.
I hadn't pushed just yet, so I incorporated your suggestion, and the
result is now commit 884052e054 in libnbd, and 0c342208d5 in nbdkit.
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3266
Virtualization: qemu.org | libvirt.org