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

On Mon, Apr 20, 2020 at 09:24:43AM -0500, Eric Blake wrote: OK, I'll remove the comment from the commit message. I was wondering why it didn't obviously crash :-) Thanks, 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