[libnbd PATCH] common/utils/vector: Better overflow handling
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t. Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) --- Unless you see problems in this, I'll push this and also port it to nbdkit. common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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; - if (newcap < reqcap) + if (newcap * itemsize < reqcap * itemsize) newcap = reqcap; newptr = realloc (v->ptr, newcap * itemsize); -- 2.33.1
On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake@redhat.com> wrote:
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t.
Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) ---
Unless you see problems in this, I'll push this and also port it to nbdkit.
common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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) {
Just to make sure I understand this correctly: v->cap * itemsize must be valid value since this is the current allocation, computed in a previous call to generic_vector_reserve...
+ errno = ENOMEM; return -1; /* overflow */ + }
newcap = (v->cap * 3 + 1) / 2;
- if (newcap < reqcap) + if (newcap * itemsize < reqcap * itemsize)
So reqcap * itemsize is valid because we passed the check above.
newcap = reqcap;
newptr = realloc (v->ptr, newcap * itemsize);
Looks right to me. Nir
On Mon, Nov 08, 2021 at 10:08:59PM +0200, Nir Soffer wrote:
On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake@redhat.com> wrote:
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t.
Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) ---
Unless you see problems in this, I'll push this and also port it to nbdkit.
common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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) {
Just to make sure I understand this correctly: v->cap * itemsize must be valid value since this is the current allocation, computed in a previous call to generic_vector_reserve...
+ errno = ENOMEM; return -1; /* overflow */ + }
newcap = (v->cap * 3 + 1) / 2;
- if (newcap < reqcap) + if (newcap * itemsize < reqcap * itemsize)
So reqcap * itemsize is valid because we passed the check above.
newcap = reqcap;
newptr = realloc (v->ptr, newcap * itemsize);
Looks right to me.
I agree too, it seems right here. Guess it's one case where a proof checker could actually help :-) Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-top is 'top' for virtual machines. Tiny program with many powerful monitoring features, net stats, disk stats, logging, etc. http://people.redhat.com/~rjones/virt-top
On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake@redhat.com> wrote:
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t.
Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) ---
Unless you see problems in this, I'll push this and also port it to nbdkit.
common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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? 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.
- 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. Nir
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
On 11/08/21 20:56, Eric Blake wrote:
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t.
Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) ---
Unless you see problems in this, I'll push this and also port it to nbdkit.
common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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) {
In my opinion, this is not good enough. Example (assuming uint64_t for size_t): itemsize = 2; v->cap = 1; n = 0x8000_0000_0000_0001; therefore reqcap = 0x8000_0000_0000_0002; The product on the LHS will overflow, to 4. The product on the RHS will be 2. So the controlling expression will evaluate to false.
+ errno = ENOMEM; return -1; /* overflow */ + }
newcap = (v->cap * 3 + 1) / 2;
This is another unchecked multiplication. What guarantees (v->cap * 3) cannot overflow? I strongly dislike attempts to catch overflows after the fact. I think it's much better to ensure in advance that the addition or multiplication cannot overflow. That usually involces subtraction, division, and comparison. I assume generic_vector_reserve() is not on any "hot path". size_t reqcap, maxcap, newcap; if (itemsize == 0) { errno = EINVAL; return -1; } if (n > (size_t)-1 - v->cap) { errno = ENOMEM; return -1; /* overflow */ } reqcap = v->cap + n; /* can never overflow */ maxcap = (size_t)-1 / itemsize; /* never divides by zero */ if (reqcap > maxcap) { errno = ENOMEM; return -1; /* overflow */ } if (v->cap > (size_t)-1 / 3 || v->cap * 3 > (size_t)-1 - 1) { /* we cannot compute the next auto-increment; stick with the * requested capacity */ newcap = reqcap; } else { newcap = v->cap * 3 + 1; /* cannot overflow */ newcap /= 2; /* if the auto-increment is smaller than requested, or the * auto-increment is too large as a number of plain bytes, then * stick with the requested capacity */ if (newcap < reqcap || newcap > maxcap) newcap = reqcap; } assert (newcap <= maxcap); newptr = realloc (v->ptr, newcap * itemsize); /* cannot overflow */ /* ... */ Thanks Laszlo
- if (newcap < reqcap) + if (newcap * itemsize < reqcap * itemsize) newcap = reqcap;
newptr = realloc (v->ptr, newcap * itemsize);
On Tue, Nov 09, 2021 at 02:15:03PM +0100, Laszlo Ersek wrote:
On 11/08/21 20:56, Eric Blake wrote:
Check newcap * itemsize for overflow prior to calling realloc, so that we don't accidentally truncate an existing array. Set errno to ENOMEM on all failure paths, rather than leaving it indeterminate on overflow. The patch works by assuming a prerequisite that v->cap*itemsize is always smaller than size_t.
Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append) ---
Unless you see problems in this, I'll push this and also port it to nbdkit.
common/utils/vector.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
diff --git a/common/utils/vector.c b/common/utils/vector.c index a4b43ce..c37f0c3 100644 --- a/common/utils/vector.c +++ b/common/utils/vector.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2018-2020 Red Hat Inc. + * Copyright (C) 2018-2021 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -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) {
In my opinion, this is not good enough. Example (assuming uint64_t for size_t):
itemsize = 2; v->cap = 1; n = 0x8000_0000_0000_0001;
therefore
reqcap = 0x8000_0000_0000_0002;
The product on the LHS will overflow, to 4. The product on the RHS will be 2. So the controlling expression will evaluate to false.
+ errno = ENOMEM; return -1; /* overflow */ + }
newcap = (v->cap * 3 + 1) / 2;
This is another unchecked multiplication. What guarantees (v->cap * 3) cannot overflow?
I strongly dislike attempts to catch overflows after the fact. I think it's much better to ensure in advance that the addition or multiplication cannot overflow. That usually involces subtraction, division, and comparison. I assume generic_vector_reserve() is not on any "hot path".
size_t reqcap, maxcap, newcap;
if (itemsize == 0) { errno = EINVAL; return -1; }
if (n > (size_t)-1 - v->cap) { errno = ENOMEM; return -1; /* overflow */ } reqcap = v->cap + n; /* can never overflow */
maxcap = (size_t)-1 / itemsize; /* never divides by zero */
if (reqcap > maxcap) { errno = ENOMEM; return -1; /* overflow */ }
if (v->cap > (size_t)-1 / 3 || v->cap * 3 > (size_t)-1 - 1) { /* we cannot compute the next auto-increment; stick with the * requested capacity */ newcap = reqcap; } else { newcap = v->cap * 3 + 1; /* cannot overflow */ newcap /= 2;
/* if the auto-increment is smaller than requested, or the * auto-increment is too large as a number of plain bytes, then * stick with the requested capacity */ if (newcap < reqcap || newcap > maxcap) newcap = reqcap; }
assert (newcap <= maxcap); newptr = realloc (v->ptr, newcap * itemsize); /* cannot overflow */ /* ... */
Want to point out that gcc has a set of functions to check for overflow, and they're quite nice to use too. One definite advantage here is that these should map to particular hardware instructions, eg. seto on x86. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html libnbd already uses __builtin_bswap* and __builtin_expect, although defended with some is-gcc macros. clang also implements these, but from what I'm reading online it seems they were buggy in at least earlier versions. Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com Fedora Windows cross-compiler. Compile Windows programs, test, and build Windows installers. Over 100 libraries supported. http://fedoraproject.org/wiki/MinGW
On Tue, Nov 09, 2021 at 02:39:38PM +0000, Richard W.M. Jones wrote:
clang also implements these, but from what I'm reading online it seems they were buggy in at least earlier versions.
Actually the clang bug doesn't look that bad, it seems like an obscure corner case that we're unlikely to hit: https://bugs.llvm.org/show_bug.cgi?id=16404 Since GCC and Clang are the only two compilers we support we might as well use these functions IMHO. Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com libguestfs lets you edit virtual machines. Supports shell scripting, bindings from many languages. http://libguestfs.org
On 11/09/21 15:42, Richard W.M. Jones wrote:
On Tue, Nov 09, 2021 at 02:39:38PM +0000, Richard W.M. Jones wrote:
clang also implements these, but from what I'm reading online it seems they were buggy in at least earlier versions.
Actually the clang bug doesn't look that bad, it seems like an obscure corner case that we're unlikely to hit:
https://bugs.llvm.org/show_bug.cgi?id=16404
Since GCC and Clang are the only two compilers we support we might as well use these functions IMHO.
I agree. (This is the first time I've heard of GCC's integer overflow builtins!) (One data point: in edk2, at long last, a library called SafeIntLib had been introduced, for the same purpose. The initial implementation needed some fixes, but that doesn't diminish the value of hiding these tricky overflow checks behind a well-defined API.) Thanks, Laszlo
participants (4)
-
Eric Blake -
Laszlo Ersek -
Nir Soffer -
Richard W.M. Jones