Libguestfs - Nov 2021 - [PATCH nbdkit 2/2] common: Add checked-overflow macros and use for safe vector extension

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 <rjones at
redhat.com> 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

On Tue, Nov 9, 2021 at 9:27 PM Richard W.M. Jones <rjones at redhat.com>
wrote:
>
> 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 <rjones at
redhat.com> 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?
overflow label can be nice.
>
> > >      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.
>
> ?!
Maybe evil is not the right word :-)
> > 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
>

On Tue, Nov 09, 2021 at 07:27:12PM +0000, Richard W.M. Jones
wrote:
> On Tue, Nov 09, 2021 at 08:53:28PM +0200, Nir Soffer wrote:
> > 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
While I think this is a good idea, when I tried to make it work the
function wasn't very elegant.  The problem is trying to make the
output "atomic", ie. only updating *newcap once.

What was worse, reading the disassembly Clang managed to produce
something that was less efficient, even though it inlined the function.

Rich.

-- 
Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones
Read my programming and virtualization blog: http://rwmj.wordpress.com
virt-builder quickly builds VMs from scratch
http://libguestfs.org/virt-builder.1.html