Richard W.M. Jones
2020-Apr-19 21:14 UTC
[Libguestfs] [PATCH nbdkit 1/2] vddk: Use new vector library to allocate the argv list.
--- plugins/vddk/vddk.c | 41 +++++++++++++++++++++++++---------------- TODO | 1 - 2 files changed, 25 insertions(+), 17 deletions(-) diff --git a/plugins/vddk/vddk.c b/plugins/vddk/vddk.c index 87c0d146..d1a3015f 100644 --- a/plugins/vddk/vddk.c +++ b/plugins/vddk/vddk.c @@ -51,6 +51,7 @@ #include "isaligned.h" #include "minmax.h" #include "rounding.h" +#include "vector.h" #include "vddk-structs.h" @@ -256,12 +257,23 @@ vddk_config (const char *key, const char *value) * the caller prefers to proceed as if this had not been attempted. * Thus, no return value is needed. */ +DEFINE_VECTOR_TYPE(string_vector, char *); + +#define CLEANUP_FREE_STRING_VECTOR \ + __attribute__((cleanup (cleanup_free_string_vector))) + +static void +cleanup_free_string_vector (string_vector *v) +{ + string_vector_iter (v, (void *) free); + free (v->ptr); +} + static void perform_reexec (const char *env, const char *prepend) { CLEANUP_FREE char *library = NULL; - int argc = 0; - CLEANUP_FREE char **argv = NULL; + CLEANUP_FREE_STRING_VECTOR string_vector argv = empty_vector; int fd; size_t len = 0, buflen = 512; CLEANUP_FREE char *buf = NULL; @@ -301,25 +313,22 @@ perform_reexec (const char *env, const char *prepend) buflen = len; len = 0; while (len < buflen) { - char **tmp = realloc (argv, sizeof *argv * (argc + 3)); - - if (!tmp) { - nbdkit_debug ("failure to parse original argv: %m"); + if (string_vector_append (&argv, buf + len) == -1) { + argv_realloc_fail: + nbdkit_debug ("argv: realloc: %m"); return; } - argv = tmp; - argv[argc++] = buf + len; len += strlen (buf + len) + 1; } if (!env) env = ""; - nbdkit_debug ("original argc == %d, adding reexeced_=%s", argc, env); - if (asprintf (&reexeced, "reexeced_=%s", env) == -1) { - nbdkit_debug ("failure to re-exec: %m"); - return; - } - argv[argc++] = reexeced; - argv[argc] = NULL; + nbdkit_debug ("adding reexeced_=%s", env); + if (asprintf (&reexeced, "reexeced_=%s", env) == -1) + goto argv_realloc_fail; + if (string_vector_append (&argv, reexeced) == -1) + goto argv_realloc_fail; + if (string_vector_append (&argv, NULL) == -1) + goto argv_realloc_fail; if (env[0]) { if (asprintf (&library, "%s:%s", prepend, env) == -1) @@ -334,7 +343,7 @@ perform_reexec (const char *env, const char *prepend) nbdkit_debug ("re-executing with updated LD_LIBRARY_PATH=%s", library); fflush (NULL); - execvp ("/proc/self/exe", argv); + execvp ("/proc/self/exe", argv.ptr); nbdkit_debug ("failure to execvp: %m"); } diff --git a/TODO b/TODO index 0c06b968..967c58f3 100644 --- a/TODO +++ b/TODO @@ -101,7 +101,6 @@ General ideas for improvements * common/utils/vector.h could be extended and used in other places: - there are some more possible places in the server (anywhere using realloc is suspect) - - nbdkit-vddk-plugin, where it builds the new argv - allow insertion, and use it in nbdkit-extentlist-filter - allow insertion and keep sorted, use it in nbdkit-eval-plugin - same, and use it in common/sparse/sparse.c -- 2.25.0
Richard W.M. Jones
2020-Apr-19 21:14 UTC
[Libguestfs] [PATCH nbdkit 2/2] Add insert function and use the new vector library in several places.
This extends the vector library with an insert function. It is more expensive than appending, but this does not affect existing code using vector and can be used in new places without making those uses more expensive. We use this function in nbdkit-extentlist-filter, nbdkit-eval-plugin and the sparse library. This is refactoring, so should not affect functionality at all. However during the rewrite of eval it revealed a fencepost error in the loop iterating over method_scripts which is fixed here. --- common/sparse/Makefile.am | 1 + common/utils/vector.h | 24 +++++-- common/sparse/sparse.c | 50 +++++++------- plugins/eval/eval.c | 49 ++++++-------- filters/extentlist/extentlist.c | 113 ++++++++++++++++---------------- TODO | 5 +- 6 files changed, 119 insertions(+), 123 deletions(-) diff --git a/common/sparse/Makefile.am b/common/sparse/Makefile.am index d11d3098..f0ca16ff 100644 --- a/common/sparse/Makefile.am +++ b/common/sparse/Makefile.am @@ -40,5 +40,6 @@ libsparse_la_SOURCES = \ libsparse_la_CPPFLAGS = \ -I$(top_srcdir)/include \ -I$(top_srcdir)/common/include \ + -I$(top_srcdir)/common/utils \ $(NULL) libsparse_la_CFLAGS = $(WARNINGS_CFLAGS) diff --git a/common/utils/vector.h b/common/utils/vector.h index dbf9ea07..ee12c3ae 100644 --- a/common/utils/vector.h +++ b/common/utils/vector.h @@ -30,17 +30,19 @@ * SUCH DAMAGE. */ -/* Simple implementation of appendable vector. There are two main - * use-cases we consider: lists of strings (either with a defined - * length, or NULL-terminated), and lists of numbers. It is generic - * so could be used for lists of anything (eg. structs) where being - * able to append easily is important. +/* Simple implementation of a vector. It can be cheaply appended, and + * more expensively inserted. There are two main use-cases we + * consider: lists of strings (either with a defined length, or + * NULL-terminated), and lists of numbers. It is generic so could be + * used for lists of anything (eg. structs) where being able to append + * easily is important. */ #ifndef NBDKIT_VECTOR_H #define NBDKIT_VECTOR_H #include <assert.h> +#include <string.h> #define DEFINE_VECTOR_TYPE(name, type) \ struct name { \ @@ -55,15 +57,23 @@ return generic_vector_extend ((struct generic_vector *)v, n, \ sizeof (type)); \ } \ + /* Insert at i'th element. i=0 => beginning i=size => append */ \ static inline int \ - name##_append (name *v, type elem) \ + name##_insert (name *v, type elem, size_t i) \ { \ if (v->size >= v->alloc) { \ if (name##_extend (v, 1) == -1) return -1; \ } \ - v->ptr[v->size++] = elem; \ + memmove (&v->ptr[i+1], &v->ptr[i], (v->size-i) * sizeof (elem)); \ + v->ptr[i] = elem; \ + v->size++; \ return 0; \ } \ + static inline int \ + name##_append (name *v, type elem) \ + { \ + return name##_insert (v, elem, v->size); \ + } \ static inline void \ name##_iter (name *v, void (*f) (type elem)) \ { \ diff --git a/common/sparse/sparse.c b/common/sparse/sparse.c index c479c3a4..7cfbd33d 100644 --- a/common/sparse/sparse.c +++ b/common/sparse/sparse.c @@ -45,6 +45,7 @@ #include "iszero.h" #include "sparse.h" +#include "vector.h" /* Two level directory for the sparse array. * @@ -100,9 +101,10 @@ struct l1_entry { void **l2_dir; /* Pointer to L2 directory. */ }; +DEFINE_VECTOR_TYPE(l1_dir, struct l1_entry); + struct sparse_array { - struct l1_entry *l1_dir; /* L1 directory. */ - size_t l1_size; /* Number of entries in L1 directory. */ + l1_dir l1_dir; /* L1 directory. */ bool debug; }; @@ -123,9 +125,9 @@ free_sparse_array (struct sparse_array *sa) size_t i; if (sa) { - for (i = 0; i < sa->l1_size; ++i) - free_l2_dir (sa->l1_dir[i].l2_dir); - free (sa->l1_dir); + for (i = 0; i < sa->l1_dir.size; ++i) + free_l2_dir (sa->l1_dir.ptr[i].l2_dir); + free (sa->l1_dir.ptr); free (sa); } } @@ -141,11 +143,9 @@ alloc_sparse_array (bool debug) { struct sparse_array *sa; - sa = malloc (sizeof *sa); + sa = calloc (1, sizeof *sa); if (sa == NULL) return NULL; - sa->l1_dir = NULL; - sa->l1_size = 0; sa->debug = debug; return sa; } @@ -169,26 +169,17 @@ static int insert_l1_entry (struct sparse_array *sa, const struct l1_entry *entry) { size_t i; - struct l1_entry *old_l1_dir = sa->l1_dir; - /* The l1_dir always ends up one bigger, so reallocate it first. */ - sa->l1_dir = realloc (sa->l1_dir, (sa->l1_size+1) * sizeof (struct l1_entry)); - if (sa->l1_dir == NULL) { - sa->l1_dir = old_l1_dir; - nbdkit_error ("realloc"); - return -1; - } - - for (i = 0; i < sa->l1_size; ++i) { - if (entry->offset < sa->l1_dir[i].offset) { + for (i = 0; i < sa->l1_dir.size; ++i) { + if (entry->offset < sa->l1_dir.ptr[i].offset) { /* Insert new entry before i'th directory entry. */ - memmove (&sa->l1_dir[i+1], &sa->l1_dir[i], - (sa->l1_size-i) * sizeof (struct l1_entry)); - sa->l1_dir[i] = *entry; - sa->l1_size++; + if (l1_dir_insert (&sa->l1_dir, *entry, i) == -1) { + nbdkit_error ("realloc: %m"); + return -1; + } if (sa->debug) nbdkit_debug ("%s: inserted new L1 entry for %" PRIu64 - " at l1_dir[%zu]", + " at l1_dir.ptr[%zu]", __func__, entry->offset, i); return 0; } @@ -196,12 +187,14 @@ insert_l1_entry (struct sparse_array *sa, const struct l1_entry *entry) /* This should never happens since each entry in the the L1 * directory is supposed to be unique. */ - assert (entry->offset != sa->l1_dir[i].offset); + assert (entry->offset != sa->l1_dir.ptr[i].offset); } /* Insert new entry at the end. */ - sa->l1_dir[sa->l1_size] = *entry; - sa->l1_size++; + if (l1_dir_append (&sa->l1_dir, *entry) == -1) { + nbdkit_error ("realloc: %m"); + return -1; + } if (sa->debug) nbdkit_debug ("%s: inserted new L1 entry for %" PRIu64 " at end of l1_dir", __func__, entry->offset); @@ -233,7 +226,8 @@ lookup (struct sparse_array *sa, uint64_t offset, bool create, again: /* Search the L1 directory. */ - entry = bsearch (&offset, sa->l1_dir, sa->l1_size, sizeof (struct l1_entry), + entry = bsearch (&offset, sa->l1_dir.ptr, + sa->l1_dir.size, sizeof (struct l1_entry), compare_l1_offsets); if (sa->debug) { diff --git a/plugins/eval/eval.c b/plugins/eval/eval.c index a733a3c5..547ca701 100644 --- a/plugins/eval/eval.c +++ b/plugins/eval/eval.c @@ -46,6 +46,7 @@ #include <nbdkit-plugin.h> #include "cleanup.h" +#include "vector.h" #include "call.h" #include "methods.h" @@ -87,11 +88,12 @@ static const char *known_methods[] = { /* List of method scripts that we have saved. This is stored in * sorted order of method name. */ -static size_t nr_method_scripts; -static struct method_script { +struct method_script { const char *method; char *script; -} *method_scripts; +}; +DEFINE_VECTOR_TYPE(method_script_list, struct method_script); +static method_script_list method_scripts; static int compare_script (const void *methodvp, const void *entryvp) @@ -104,21 +106,12 @@ compare_script (const void *methodvp, const void *entryvp) static int insert_method_script (const char *method, char *script) { - struct method_script *newp; - size_t i; int r; + size_t i; + struct method_script new_entry = { .method = method, .script = script }; - newp = realloc (method_scripts, - sizeof (struct method_script) * (nr_method_scripts + 1)); - if (newp == NULL) { - nbdkit_error ("insert_method_script: realloc: %m"); - return -1; - } - nr_method_scripts++; - method_scripts = newp; - - for (i = 0; i < nr_method_scripts-1; ++i) { - r = compare_script (method, &method_scripts[i]); + for (i = 0; i < method_scripts.size; ++i) { + r = compare_script (method, &method_scripts.ptr[i]); /* This shouldn't happen. insert_method_script() must not be * called if the method has already been added. Call get_script() * first to check. @@ -126,17 +119,19 @@ insert_method_script (const char *method, char *script) assert (r != 0); if (r < 0) { /* Insert before this element. */ - memmove (&method_scripts[i+1], &method_scripts[i], - sizeof (struct method_script) * (nr_method_scripts-i-1)); - method_scripts[i].method = method; - method_scripts[i].script = script; + if (method_script_list_insert (&method_scripts, new_entry, i) == -1) { + nbdkit_error ("realloc: %m"); + return -1; + } return 0; } } /* Insert at end of list. */ - method_scripts[i].method = method; - method_scripts[i].script = script; + if (method_script_list_append (&method_scripts, new_entry) == -1) { + nbdkit_error ("realloc: %m"); + return -1; + } return 0; } @@ -147,8 +142,8 @@ get_script (const char *method) struct method_script *p; p = bsearch (method, - method_scripts, - nr_method_scripts, sizeof (struct method_script), + method_scripts.ptr, + method_scripts.size, sizeof (struct method_script), compare_script); if (p) return p->script; @@ -229,7 +224,6 @@ eval_unload (void) const char *method = "unload"; const char *script = get_script (method); CLEANUP_FREE char *cmd = NULL; - size_t i; /* Run the unload method. Ignore all errors. */ if (script) { @@ -239,9 +233,8 @@ eval_unload (void) } call_unload (); - for (i = 0; i < nr_method_scripts; ++i) - free (method_scripts[i].script); - free (method_scripts); + method_script_list_iter (&method_scripts, (void *) free); + free (method_scripts.ptr); free (missing); } diff --git a/filters/extentlist/extentlist.c b/filters/extentlist/extentlist.c index 2dc6623d..afabd6cd 100644 --- a/filters/extentlist/extentlist.c +++ b/filters/extentlist/extentlist.c @@ -44,6 +44,7 @@ #include "cleanup.h" #include "minmax.h" +#include "vector.h" #define HOLE (NBDKIT_EXTENT_HOLE|NBDKIT_EXTENT_ZERO) @@ -56,31 +57,13 @@ struct extent { uint64_t offset, length; uint32_t type; }; -static struct extent *extents; -static size_t nr_extents, allocated; - -/* Insert an extent before i. If i = nr_extents, inserts at the end. */ -static void -insert_extent (size_t i, struct extent new_extent) -{ - if (nr_extents >= allocated) { - allocated = allocated == 0 ? 1 : allocated * 2; - extents = realloc (extents, (sizeof (struct extent) * allocated)); - if (extents == NULL) { - nbdkit_error ("realloc: %m"); - exit (EXIT_FAILURE); - } - } - memmove (&extents[i+1], &extents[i], - sizeof (struct extent) * (nr_extents-i)); - extents[i] = new_extent; - nr_extents++; -} +DEFINE_VECTOR_TYPE(extent_list, struct extent); +static extent_list extents; static void extentlist_unload (void) { - free (extents); + free (extents.ptr); } /* Called for each key=value passed on the command line. */ @@ -152,8 +135,8 @@ parse_extentlist (void) uint64_t end; assert (extentlist != NULL); - assert (extents == NULL); - assert (nr_extents == 0); + assert (extents.ptr == NULL); + assert (extents.size == 0); fp = fopen (extentlist, "r"); if (!fp) { @@ -204,61 +187,79 @@ parse_extentlist (void) type |= NBDKIT_EXTENT_ZERO; } - insert_extent (nr_extents, - (struct extent){.offset = offset, .length=length, - .type=type}); + if (extent_list_append (&extents, + (struct extent){.offset = offset, .length=length, + .type=type}) == -1) { + nbdkit_error ("realloc: %m"); + exit (EXIT_FAILURE); + } } fclose (fp); /* Sort the extents by offset. */ - qsort (extents, nr_extents, sizeof (struct extent), compare_offsets); + qsort (extents.ptr, extents.size, sizeof (struct extent), compare_offsets); /* There must not be overlaps at this point. */ end = 0; - for (i = 0; i < nr_extents; ++i) { - if (extents[i].offset < end || - extents[i].offset + extents[i].length < extents[i].offset) { + for (i = 0; i < extents.size; ++i) { + if (extents.ptr[i].offset < end || + extents.ptr[i].offset + extents.ptr[i].length < extents.ptr[i].offset) { nbdkit_error ("extents in the extent list are overlapping"); exit (EXIT_FAILURE); } - end = extents[i].offset + extents[i].length; + end = extents.ptr[i].offset + extents.ptr[i].length; } /* If there's a gap at the beginning, insert a hole|zero extent. */ - if (nr_extents == 0 || extents[0].offset > 0) { - end = nr_extents == 0 ? UINT64_MAX : extents[0].offset; - insert_extent (0, (struct extent){.offset = 0, .length = end, - .type = HOLE}); + if (extents.size == 0 || extents.ptr[0].offset > 0) { + end = extents.size == 0 ? UINT64_MAX : extents.ptr[0].offset; + if (extent_list_insert (&extents, + (struct extent){.offset = 0, .length = end, + .type = HOLE}, + 0) == -1) { + nbdkit_error ("realloc: %m"); + exit (EXIT_FAILURE); + } } /* Now insert hole|zero extents after every extent where there * is a gap between that extent and the next one. */ - for (i = 0; i < nr_extents-1; ++i) { - end = extents[i].offset + extents[i].length; - if (end < extents[i+1].offset) - insert_extent (i+1, (struct extent){.offset = end, - .length = extents[i+1].offset - end, - .type = HOLE}); + for (i = 0; i < extents.size-1; ++i) { + end = extents.ptr[i].offset + extents.ptr[i].length; + if (end < extents.ptr[i+1].offset) + if (extent_list_insert (&extents, + (struct extent){.offset = end, + .length = extents.ptr[i+1].offset - end, + .type = HOLE}, + i+1) == -1) { + nbdkit_error ("realloc: %m"); + exit (EXIT_FAILURE); + } } /* If there's a gap at the end, insert a hole|zero extent. */ - end = extents[nr_extents-1].offset + extents[nr_extents-1].length; - if (end < UINT64_MAX) - insert_extent (nr_extents, (struct extent){.offset = end, - .length = UINT64_MAX-end, - .type = HOLE}); + end = extents.ptr[extents.size-1].offset + extents.ptr[extents.size-1].length; + if (end < UINT64_MAX) { + if (extent_list_append (&extents, + (struct extent){.offset = end, + .length = UINT64_MAX-end, + .type = HOLE}) == -1) { + nbdkit_error ("realloc: %m"); + exit (EXIT_FAILURE); + } + } /* Debug the final list. */ - for (i = 0; i < nr_extents; ++i) { + for (i = 0; i < extents.size; ++i) { nbdkit_debug ("extentlist: " "extent[%zu] = %" PRIu64 "-%" PRIu64 " (length %" PRIu64 ")" " type %" PRIu32, - i, extents[i].offset, - extents[i].offset + extents[i].length - 1, - extents[i].length, - extents[i].type); + i, extents.ptr[i].offset, + extents.ptr[i].offset + extents.ptr[i].length - 1, + extents.ptr[i].length, + extents.ptr[i].type); } } @@ -294,10 +295,10 @@ extentlist_extents (struct nbdkit_next_ops *next_ops, void *nxdata, uint64_t end; /* Find the starting point in the extents list. */ - p = bsearch (&eoffset, extents, - nr_extents, sizeof (struct extent), compare_ranges); + p = bsearch (&eoffset, extents.ptr, + extents.size, sizeof (struct extent), compare_ranges); assert (p != NULL); - i = p - extents; + i = p - extents.ptr; /* Add extents to the output. */ while (count > 0) { @@ -306,9 +307,9 @@ extentlist_extents (struct nbdkit_next_ops *next_ops, void *nxdata, "loop i=%zd count=%" PRIu32 " offset=%" PRIu64, i, count, offset); - end = extents[i].offset + extents[i].length; + end = extents.ptr[i].offset + extents.ptr[i].length; if (nbdkit_add_extent (ret_extents, offset, end - offset, - extents[i].type) == -1) + extents.ptr[i].type) == -1) return -1; count -= MIN (count, end-offset); diff --git a/TODO b/TODO index 967c58f3..02627069 100644 --- a/TODO +++ b/TODO @@ -101,10 +101,7 @@ General ideas for improvements * common/utils/vector.h could be extended and used in other places: - there are some more possible places in the server (anywhere using realloc is suspect) - - allow insertion, and use it in nbdkit-extentlist-filter - - allow insertion and keep sorted, use it in nbdkit-eval-plugin - - same, and use it in common/sparse/sparse.c - Also add more iterators, map function, etc, as required. + - add more iterators, map function, etc, as required. Suggestions for plugins ----------------------- -- 2.25.0
Eric Blake
2020-Apr-20 14:24 UTC
Re: [Libguestfs] [PATCH nbdkit 2/2] Add insert function and use the new vector library in several places.
On 4/19/20 4:14 PM, Richard W.M. Jones wrote:> This extends the vector library with an insert function. It is more > expensive than appending, but this does not affect existing code using > vector and can be used in new places without making those uses more > expensive. > > We use this function in nbdkit-extentlist-filter, nbdkit-eval-plugin > and the sparse library. > > This is refactoring, so should not affect functionality at all. > However during the rewrite of eval it revealed a fencepost error in > the loop iterating over method_scripts which is fixed here. > --- > common/sparse/Makefile.am | 1 + > common/utils/vector.h | 24 +++++-- > common/sparse/sparse.c | 50 +++++++------- > plugins/eval/eval.c | 49 ++++++-------- > filters/extentlist/extentlist.c | 113 ++++++++++++++++---------------- > TODO | 5 +- > 6 files changed, 119 insertions(+), 123 deletions(-)> +++ b/plugins/eval/eval.c> @@ -104,21 +106,12 @@ compare_script (const void *methodvp, const void *entryvp) > static int > insert_method_script (const char *method, char *script) > { > - struct method_script *newp; > - size_t i; > int r; > + size_t i; > + struct method_script new_entry = { .method = method, .script = script }; > > - newp = realloc (method_scripts, > - sizeof (struct method_script) * (nr_method_scripts + 1)); > - if (newp == NULL) { > - nbdkit_error ("insert_method_script: realloc: %m"); > - return -1; > - } > - nr_method_scripts++; > - method_scripts = newp;The old code appended the new element first, then> - > - for (i = 0; i < nr_method_scripts-1; ++i) { > - r = compare_script (method, &method_scripts[i]);iterated on the previously-existing elements to see if re-sorting was needed.> + for (i = 0; i < method_scripts.size; ++i) { > + r = compare_script (method, &method_scripts.ptr[i]);The new code does not increase the list size until first finding where to insert. I see why you called this a fencepost error, as comparing just the pre-/post-patch 'for' lines looks like you fixed an off-by-one error, but with the additional context of when the list counter was incremented, I don't think it is actually a bug fix, so the commit message had me hunting for something not there. At any rate, the series looks good. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3226 Virtualization: qemu.org | libvirt.org
Possibly Parallel Threads
- Re: [PATCH nbdkit 2/2] Add insert function and use the new vector library in several places.
- [PATCH nbdkit 2/2] Add insert function and use the new vector library in several places.
- [PATCH nbdkit] include: Annotate function parameters with attribute((nonnull)).
- Cross-project NBD extension proposal: NBD_INFO_INIT_STATE
- [PATCH nbdkit v2 0/2] Use of attribute(()).