On Tue, Nov 09, 2021 at 08:53:28PM +0200, Nir Soffer wrote:
> On Tue, Nov 9, 2021 at 7:49 PM Richard W.M. Jones <[email protected]> wrote:
> >
> > ---
> > common/include/Makefile.am | 1 +
> > common/utils/Makefile.am | 3 +-
> > common/include/checked-overflow.h | 61 +++++++++++++++++++++++++++++++
> > common/utils/vector.c | 26 +++++++++----
> > 4 files changed, 82 insertions(+), 9 deletions(-)
> >
> > diff --git a/common/include/Makefile.am b/common/include/Makefile.am
> > index a7d0d026..52d97216 100644
> > --- a/common/include/Makefile.am
> > +++ b/common/include/Makefile.am
> > @@ -37,6 +37,7 @@ EXTRA_DIST = \
> > ascii-ctype.h \
> > ascii-string.h \
> > byte-swapping.h \
> > + checked-overflow.h \
> > exit-with-parent.h \
> > isaligned.h \
> > ispowerof2.h \
> > diff --git a/common/utils/Makefile.am b/common/utils/Makefile.am
> > index 55415535..012a5c25 100644
> > --- a/common/utils/Makefile.am
> > +++ b/common/utils/Makefile.am
> > @@ -52,6 +52,7 @@ libutils_la_SOURCES = \
> > $(NULL)
> > libutils_la_CPPFLAGS = \
> > -I$(top_srcdir)/include \
> > + -I$(top_srcdir)/common/include \
> > $(NULL)
> > libutils_la_CFLAGS = \
> > $(WARNINGS_CFLAGS) \
> > @@ -101,7 +102,7 @@ test_quotes_CPPFLAGS = -I$(srcdir)
> > test_quotes_CFLAGS = $(WARNINGS_CFLAGS)
> >
> > test_vector_SOURCES = test-vector.c vector.c vector.h bench.h
> > -test_vector_CPPFLAGS = -I$(srcdir)
> > +test_vector_CPPFLAGS = -I$(srcdir) -I$(top_srcdir)/common/include
> > test_vector_CFLAGS = $(WARNINGS_CFLAGS)
> >
> > bench: test-vector
> > diff --git a/common/include/checked-overflow.h
> > b/common/include/checked-overflow.h
> > new file mode 100644
> > index 00000000..b571e2c6
> > --- /dev/null
> > +++ b/common/include/checked-overflow.h
> > @@ -0,0 +1,61 @@
> > +/* nbdkit
> > + * Copyright (C) 2013-2021 Red Hat Inc.
> > + *
> > + * Redistribution and use in source and binary forms, with or without
> > + * modification, are permitted provided that the following conditions are
> > + * met:
> > + *
> > + * * Redistributions of source code must retain the above copyright
> > + * notice, this list of conditions and the following disclaimer.
> > + *
> > + * * Redistributions in binary form must reproduce the above copyright
> > + * notice, this list of conditions and the following disclaimer in the
> > + * documentation and/or other materials provided with the distribution.
> > + *
> > + * * Neither the name of Red Hat nor the names of its contributors may be
> > + * used to endorse or promote products derived from this software without
> > + * specific prior written permission.
> > + *
> > + * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
> > + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
> > + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
> > + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
> > + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
> > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
> > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
> > + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
> > + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
> > + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
> > + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> > + * SUCH DAMAGE.
> > + */
> > +
> > +/* This header file defines functions for checking overflow in common
> > + * integer arithmetic operations.
> > + *
> > + * It uses GCC/Clang built-ins: a possible future enhancement is to
> > + * provide fallbacks in plain C or for other compilers. The only
> > + * purpose of having a header file for this is to have a single place
> > + * where we would extend this in future.
> > + */
> > +
> > +#ifndef NBDKIT_CHECKED_OVERFLOW_H
> > +#define NBDKIT_CHECKED_OVERFLOW_H
> > +
> > +#if !defined(__GNUC__) && !defined(__clang__)
> > +#error "this file may need to be ported to your compiler"
> > +#endif
> > +
> > +/* Add two uint64_t values. Returns true if overflow happened. */
> > +#define ADD_UINT64_T_OVERFLOW(a, b, r) __builtin_add_overflow((a), (b),
> > (r))
> > +
> > +/* Multiply two uint64_t values. Returns true if overflow happened. */
> > +#define MUL_UINT64_T_OVERFLOW(a, b, r) __builtin_mul_overflow((a), (b),
> > (r))
> > +
> > +/* Add two size_t values. Returns true if overflow happened. */
> > +#define ADD_SIZE_T_OVERFLOW(a, b, r) __builtin_add_overflow((a), (b), (r))
> > +
> > +/* Multiple two size_t values. Returns true if overflow happened. */
> > +#define MUL_SIZE_T_OVERFLOW(a, b, r) __builtin_mul_overflow((a), (b), (r))
> > +
> > +#endif /* NBDKIT_CHECKED_OVERFLOW_H */
> > diff --git a/common/utils/vector.c b/common/utils/vector.c
> > index dff051e9..e4ea7f3f 100644
> > --- a/common/utils/vector.c
> > +++ b/common/utils/vector.c
> > @@ -36,6 +36,7 @@
> > #include <stdlib.h>
> > #include <errno.h>
> >
> > +#include "checked-overflow.h"
> > #include "vector.h"
> >
> > int
> > @@ -44,21 +45,30 @@ generic_vector_reserve (struct generic_vector *v,
> > size_t n, size_t itemsize)
> > void *newptr;
> > size_t reqcap, reqbytes, newcap, newbytes;
> >
> > - /* New capacity requested. We must allocate this minimum (or fail). */
> > - reqcap = v->cap + n;
> > - reqbytes = reqcap * itemsize;
> > - if (reqbytes < v->cap * itemsize) {
> > + /* New capacity requested. We must allocate this minimum (or fail).
> > + * reqcap = v->cap + n
> > + * reqbytes = reqcap * itemsize
> > + */
>
> This should explain the next lines? I'm not sure about it, it makes
> the code more complicated and the commented code can get out
> of sync with the actual code.
I really do think it makes it clearer. I agree that it makes it
possible for the code to get out of step though.
> > + if (ADD_SIZE_T_OVERFLOW (v->cap, n, &reqcap) ||
> > + MUL_SIZE_T_OVERFLOW (reqcap, itemsize, &reqbytes)) {
>
> Is order guaranteed?
>
> I think it will be more clear as separate if blocks, even if we need
> to have 2 blocks for returning ENOMEM.
Order is definitely guaranteed since || is a sequence point
https://en.wikipedia.org/wiki/Sequence_point#Sequence_points_in_C_and_C++
(point 1). (It could also short-circuit, but we don't care). I could
add an overflow: label, split the two statements, and jump here I
suppose?
> > errno = ENOMEM;
> > - return -1; /* overflow */
> > + return -1;
> > }
> >
> > /* However for the sake of optimization, scale buffer by 3/2 so that
> > * repeated reservations don't call realloc often.
> > + * newcap = v->cap + (v->cap + 1) / 2
> > + * newbytes = newcap * itemsize
> > */
> > - newcap = v->cap + (v->cap + 1) / 2;
> > - newbytes = newcap * itemsize;
> > -
> > + if (ADD_SIZE_T_OVERFLOW (v->cap, 1, &newcap))
> > + goto fallback;
> > + newcap /= 2;
> > + if (ADD_SIZE_T_OVERFLOW (v->cap, newcap, &newcap))
> > + goto fallback;
>
> This probably works but adding v->cap and newcap and storing
> back in newcap is pretty confusing. I would use a temporary:
Agreed.
> if (ADD_SIZE_T_OVERFLOW (v->cap, 1, &extracap))
> goto fallback;
>
> extracap /= 2;
> if (ADD_SIZE_T_OVERFLOW (v->cap, extracap, &newcap))
> goto fallback;
>
> > + if (MUL_SIZE_T_OVERFLOW (newcap, itemsize, &newbytes))
> > + goto fallback;
> > if (newbytes < reqbytes) {
> > + fallback:
>
> Jumping inside an if block is evil.
?!
> I would try to extract the code to compute the new capacity into a helper
> function:
>
> if (next_capacity(v-cap, n, itemsize, &newcap))
> return -1;
>
> This function can return early instead of jumping around or fail
> if we cannot reserve n items. In the worst case this function will
> only hide the overflow macros.
OK
Rich.
--
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-p2v converts physical machines to virtual machines. Boot with a
live CD or over the network (PXE) and turn machines into KVM guests.
http://libguestfs.org/virt-v2v
_______________________________________________
Libguestfs mailing list
[email protected]
https://listman.redhat.com/mailman/listinfo/libguestfs
