On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake(a)redhat.com&gt; 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.

> @@ -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.

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 */ /* ... */