[libvirt] [PATCHv3 01/17] util: add VIR_(APPEND|INSERT|DELETE)_ELEMENT

[Eric Blake]

On 12/07/2012 11:16 AM, Laine Stump wrote:
> I noticed when writing the backend functions for virNetworkUpdate that
> I was repeating the same sequence of memmove, VIR_REALLOC, nXXX-- (and
> messed up the args to memmove at least once), and had seen the same
> sequence in a lot of other places, so I decided to write a few
> utility functions/macros - see the .h file for full documentation.

> 
> [*] One initial problem with the INSERT and APPEND macros was that,
> due to both the array pointer and newelem pointer being cast to void*
> when passin to virInsertElementsN(), any chance of type-checking was

s/passin/passing/

> 
> But thanks to Eric Blake's clever thinking, I was able to modify the
> INSERT and APPEND macros so that they *do* check for both assignment
> and size compatibility of *ptr (an element in the array) and newelem
> (the element being copied into the new position of the array). This is
> done via clever use of the POSIX-guaranteed fact that the sizeof()

Actually guaranteed by C89, which is even more fundamental than POSIX
(Microsoft obeys the C standard but not POSIX).

> operator is must have *no* side effects (so an assignment inside
> sizeof() is checked for validity, but not actually evaluated), and the
> fact that virInsertElementsN has a "# of new elements" argument that we want
> to always be 1.

It looks like you also set things up for a future patch to add
VIR_INSERT_N_ELEMENTS (or some such name) where you can splice in an
array rather than just one element at a time; there, we could use the
identity property that '1 * N' is still N for the user request of how
many elements to insert at once.

> 
> What we do is replace the "1" in that argument with a call to
> VIR_TYPEMATCH(ptr, newelem), which returns 1 on success, and generates
> a compile error on failure. VIR_TYPEMATCH does three things:

It might be nice to (additionally?) mention these three things as a
comment in the source code, so that someone reading it later knows why
the macro is even present, without having to look at git history.

> 
>    * sizeof(*(a) = *(b)) assures that *a and *b are
>      assignment-compatible (they may still have a different size
>      though! e.g. longVar = intVar) (If not, there is a compile-time
>      error. If so, the result of that subexpression is sizeof(*(a)),
>      i.e. one element of the array)
> 
>    * sizeof(*(a) = *(b)) == sizeof(*(b)) checks if *a and *b are also
>      of the same size (so that, e.g. you don't accidentally copy an
>      int plus the random bytes following it into an array of long). It
>      evaluates to 1 if they are the same, and 0 otherwise.
> 
>    * sizeof(char[2 * (result of previous step) - 1]) evaluates to 1 if
>      the previous step was successful (char [(2*1) - 1] ==> char[1]),
>      of generates a compile error if it wasn't successful
>      (char[2*0) -1] ==> char[-1], which isn't legal).
> 
> So we end up sending "1" to the caller, and in the meantime check that we've
> actually added the correct &'s and/or *'s to the arguments. (Whew!)

Yep, I take full responsibility for that black magic :)

> 
> The result is that we've been relieved of the burden of getting the
> math right for the arguments to memmove when expanding/contracting the
> array, and haven't lost the type checking of ptr and newelem.

> @@ -253,6 +253,106 @@ void virShrinkN(void *ptrptr, size_t size, size_t *countptr, size_t toremove)
>      }
>  }
>  
> +/**
> + * virInsertElementsN:
> + * @ptrptr: pointer to hold address of allocated memory

Missing:
@size: size of one element of @ptrptr or @newelem

> + * @at: index within array where new elements should be added
> + * @countptr: variable tracking number of elements currently allocated
> + * @add: number of elements to add

All of your existing macros pass '1' to this, but I think it is nice to
leave this in so that we can add future macros that pass in multiple
elements at once.

> + * @newelem: pointer to array of one or more new elements to move into place
> + * (the originals will be zeroed out if successful and if clearOriginal is true)

Indentation is not consistent - here you are flush...

> + * @clearOriginal: false if the new item in the array should be copied from
> + *                 the original, and the original left intact.
> + *                 true if the original should be 0'd out on success.

...but here, you offset second lines.  Either one works, but it looks
nicer to be consistent (I think the offset looks slightly nicer, to
quickly pick out the @name: entries)

> + * @inPlace: false if we should expand the allocated memory before moving,
> + *           true if we should assume someone else *has already* done that.
> + *
> + * Re-allocate an array of 'count' elements, each sizeof(*ptr) bytes
> + * long, to be 'count' + 'add' elements long, then appropriately move
> + * the elements starting at ptr[at] up by 'count' elements, copy the
> + * items from 'newelem' into ptr[at], then store the address of
> + * allocated memory in 'ptr' and the new size in 'count'.  If
> + * 'newelem' is NULL, the new elements at ptr[at] are instead filled
> + * with zero.
> + *
> + * Returns -1 on failure, 0 on success
> + */
> +int
> +virInsertElementsN(void *ptrptr, size_t size, size_t at,
> +                   size_t *countptr,
> +                   size_t add, void *newelem,
> +                   bool clearOriginal, bool inPlace)
> +{
> +    if (at > *countptr)
> +       return -1;
> +
> +    if (inPlace) {
> +        (*countptr)++;

Oops.  Should be:

*countptr += add;

(it worked only because you always pass add==1 for now)

> +    } else if (virExpandN(ptrptr, size, countptr, add) < 0) {
> +        return -1;
> +    }

Hmm, this can fail both for invalid usage (at > *countptr) and for OOM
(virExpandN failed), but we don't issue the error message.  On the other
hand, callers should debug things to avoid invalid usage, so it should
be okay if they blindly call virReportOOMError() on failure.

> +
> +    /* memory was successfully re-allocated. Move up all elements from
> +     * ptrptr[at] to the end (if we're not "inserting" at the end
> +     * already), memcpy in the new elements, and clear the elements
> +     * from their original location. Remember that *countptr has
> +     * already been updated with new element count!
> +     */
> +    if (at < *countptr - add) {
> +        memmove(*(char**)ptrptr + (size * (at + add)),
> +                *(char**)ptrptr + (size * at),
> +                size * (*countptr - add - at));
> +    }
> +
> +    if (newelem) {
> +        memmove(*(char**)ptrptr + (size * at), newelem, size * add);

This could technically be memcpy, as ptrptr and newlem should not
overlap, for a potential minor speedup.

> +        if (clearOriginal)
> +           memset((char*)newelem, 0, size * add);
> +    } else if (inPlace || (at < *countptr - add)) {
> +        /* NB: if inPlace, even memory at the end wasn't initialized */
> +        memset(*(char**)ptrptr + (size * at), 0, size * add);
> +    }
> +
> +    return 0;
> +}
> +
> +/**
> + * virDeleteElementsN:
> + * @ptr: pointer to hold address of allocated memory

Again, document @size.

> + * @at: index within array where new elements should be deleted
> + * @count: variable tracking number of elements currently allocated
> + * @remove: number of elements to remove
> + * @inPlace: false if we should shrink the allocated memory when done,
> + *           true if we should assume someone else will do that.
> + *
> + * Re-allocate an array of 'count' elements, each sizeof(*ptr)
> + * bytes long, to be 'count' - 'remove' elements long, then store the
> + * address of allocated memory in 'ptr' and the new size in 'count'.
> + * If 'count' <= 'remove', the entire array is freed.
> + *
> + * Returns -1 on failure, 0 on success
> + */
> +int
> +virDeleteElementsN(void *ptrptr, size_t size, size_t at,
> +                   size_t *countptr, size_t remove,
> +                   bool inPlace)
> +{
> +    if (at + remove > *countptr)
> +        return -1;
> +
> +    /* First move down the elements at the end that won't be deleted,
> +     * then realloc. We assume that the items being deleted have
> +     * already been cleared.
> +    */
> +    memmove(*(char**)ptrptr + (size * at),
> +            *(char**)ptrptr + (size * (at + remove)),
> +            size * (*countptr - remove - at));
> +    if (inPlace)
> +        (*countptr)--;

Oops, same bug again where you got lucky that remove==1; should be:

*countptr -= remove

> +    else
> +        virShrinkN(ptrptr, size, countptr, remove);
> +    return 0;
> +}
>  
>  /**
>   * Vir_Alloc_Var:
> diff --git a/src/util/memory.h b/src/util/memory.h
> index ad8ee64..8388de5 100644
> --- a/src/util/memory.h
> +++ b/src/util/memory.h
> @@ -1,7 +1,7 @@
>  /*
>   * memory.c: safer memory allocation
>   *
> - * Copyright (C) 2010-2011 Red Hat, Inc.
> + * Copyright (C) 2010-2012 Red Hat, Inc.
>   * Copyright (C) 2008 Daniel P. Berrange
>   *
>   * This library is free software; you can redistribute it and/or
> @@ -59,6 +59,13 @@ int virResizeN(void *ptrptr, size_t size, size_t *alloc, size_t count,
>      ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
>  void virShrinkN(void *ptrptr, size_t size, size_t *count, size_t toremove)
>      ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
> +int virInsertElementsN(void *ptrptr, size_t size, size_t at, size_t *countptr,
> +                       size_t add, void *newelem,
> +                       bool clearOriginal, bool inPlace)
> +    ATTRIBUTE_RETURN_CHECK ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(4);
> +int virDeleteElementsN(void *ptrptr, size_t size, size_t at, size_t *countptr,
> +                       size_t remove, bool inPlace)
> +    ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(4);
>  int virAllocVar(void *ptrptr,
>                  size_t struct_size,
>                  size_t element_size,
> @@ -158,6 +165,115 @@ void virFree(void *ptrptr) ATTRIBUTE_NONNULL(1);
>  # define VIR_SHRINK_N(ptr, count, remove) \
>      virShrinkN(&(ptr), sizeof(*(ptr)), &(count), remove)
>  

spot [1]

> +/**
> + * VIR_INSERT_ELEMENT:
> + * @ptr: pointer to array of objects (*not* ptr to ptr)
> + * @at: index within array where new elements should be added
> + * @count: variable tracking number of elements currently allocated
> + * @newelem: ptr to new element to move into place  (*not* element itself)
> + * (the original will be zeroed out if successful)
> + *
> + * Re-allocate an array of 'count' elements, each sizeof(*ptr) bytes
> + * long, to be 'count' + 1 elements long, then appropriately move
> + * the elements starting at ptr[at] up by 1 element, copy the
> + * item from 'newelem' into ptr[at], then store the address of
> + * allocated memory in 'ptr' and the new size in 'count'.  If
> + * 'newelem' is NULL, the new element at ptr[at] is instead filled
> + * with zero.
> + *
> + * VIR_INSERT_ELEMENT_COPY is identical, but doesn't clear out the
> + *   original element to 0 on success, so there are two copies of the
> + *   element. This is useful if the "element" is actually just a
> + *   pointer to the real data, and you want to maintain a reference to
> + *   it for use after the insert is completed; but if the "element" is
> + *   an object that points to other allocated memory, having multiple
> + *   copies can cause problems (e.g. double free).
> + *
> + * VIR_INSERT_ELEMENT_*INPLACE are identical, but assume any necessary
> + *   memory re-allocation has already been done.
> + *
> + * Returns -1 on failure, 0 on success
> + *
> + *
> + */
> +# define VIR_TYPEMATCH(a, b) \
> +    sizeof(char[2 * (sizeof(*(a) = *(b)) == sizeof(*(b))) - 1])

I would move this helper array up to spot [1] above, along with
documenting that it is either the compile-time constant '1' or a compile
error due to improper code (that is, the summary of how the three
sizeof() work, as mentioned in the commit message, might be worth
listing here).

Ouch - we have a problem with your stated goal of allowing newelem to be
passed as NULL instead of &var when it is just desirable to leave space
but not actually populate it.  sizeof(*(NULL)), aka sizeof(*((void*)0)),
is a compilation error.

That implies that none of the rest of your series ever directly passed
NULL, but always passed &orig.  I'm not sure whether the goal of
allowing us to pass NULL makes sense if we don't have a client for it;
if it does make sense, then we need to enhance VIR_TYPEMATCH (perhaps by
using gcc-specific magic in order to ensure we don't ever evaluate
*NULL); if it doesn't make sense, it might be simpler to pass 'orig'
instead of '&orig' (but that means touching all callers in your series).

> +
> +# define VIR_INSERT_ELEMENT(ptr, at, count, newelem) \
> +    virInsertElementsN(&(ptr), sizeof(*(ptr)), at, &(count), \
> +                       VIR_TYPEMATCH(ptr, newelem), newelem, true, false)
> +# define VIR_INSERT_ELEMENT_COPY(ptr, at, count, newelem) \
> +    virInsertElementsN(&(ptr), sizeof(*(ptr)), at, &(count), \
> +                       VIR_TYPEMATCH(ptr, newelem), newelem, false, false)
> +# define VIR_INSERT_ELEMENT_INPLACE(ptr, at, count, newelem) \
> +    virInsertElementsN(&(ptr), sizeof(*(ptr)), at, &(count), \
> +                       VIR_TYPEMATCH(ptr, newelem), newelem, true, true)
> +# define VIR_INSERT_ELEMENT_COPY_INPLACE(ptr, at, count, newelem) \
> +    virInsertElementsN(&(ptr), sizeof(*(ptr)), at, &(count), \
> +                       VIR_TYPEMATCH(ptr, newelem), newelem, false, true)

These look okay, unless my concern about NULL newelem forces us to
rewrite slightly.

> +
> +/**
> + * VIR_APPEND_ELEMENT:
...
Looks okay, as nice shorthand for the common insert-at-end case.

> +/**
> + * VIR_DELETE_ELEMENT:
> + * @ptr: pointer to array of objects (*not* ptr to ptr)
> + * @at: index within array where new elements should be deleted
> + * @count: variable tracking number of elements currently allocated
> + *
> + * Re-allocate an array of 'count' elements, each sizeof(*ptr)
> + * bytes long, to be 'count' - 1 elements long, then store the
> + * address of allocated memory in 'ptr' and the new size in 'count'.
> + * If 'count' <= 1, the entire array is freed.
> + *
> + * VIR_DELETE_ELEMENT_INPLACE is identical, but assumes any
> + *   necessary memory re-allocation will be done later.
> + *
> + * Returns -1 on failure, 0 on success
> + */
> +# define VIR_DELETE_ELEMENT(ptr, at, count) \
> +    virDeleteElementsN(&(ptr), sizeof(*(ptr)), at, &(count), 1, false)
> +# define VIR_DELETE_ELEMENT_INPLACE(ptr, at, count) \
> +    virDeleteElementsN(&(ptr), sizeof(*(ptr)), at, &(count), 1, true)

Looks good.  And here, we don't have to worry about type-matching.

I think I found enough logic flaws, plus my concern about NULL newelem,
to need a v4.  But I'll still need some time to figure out how to rework
the type-checking macro to work with a NULL newelem.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 619 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20121207/b876fd17/attachment-0001.sig>