Ultimately, both the blocksize and swab filters want to return aligned extents to the client. I'm posting this as a snapshot of my work in progress on how I plan to get there (it's not quite working yet, but I'm done for today and wanted to at least document my ideas). I might also add a convenience function for nbdkit_extents_offset, since we have a number of filters that repeat the same code for translating all extents from the plugin by an offset. Eric Blake (3): vector: Add VECT_remove extents: Add nbdkit_extents_aligned() RFC swab: Re-enable .extents docs/nbdkit-filter.pod | 18 +++++++++ include/nbdkit-filter.h | 5 +++ common/utils/vector.h | 10 +++++ server/extents.c | 80 +++++++++++++++++++++++++++++++++++++- server/nbdkit.syms | 1 + common/utils/test-vector.c | 26 ++++++++++++- filters/swab/swab.c | 16 ++++---- 7 files changed, 146 insertions(+), 10 deletions(-) -- 2.27.0
An upcoming patch wants to remove an arbitrary element from a vector. Also, add testsuite coverage for other functions added since the original unit test was written. It's a bit awkward that the compare for VECT_search and VECT_sort differ in type, but such is life (we indeed have search code where typing the key differently is useful). Signed-off-by: Eric Blake <eblake@redhat.com> --- common/utils/vector.h | 10 ++++++++++ common/utils/test-vector.c | 26 +++++++++++++++++++++++++- 2 files changed, 35 insertions(+), 1 deletion(-) diff --git a/common/utils/vector.h b/common/utils/vector.h index c14644a7..880fd308 100644 --- a/common/utils/vector.h +++ b/common/utils/vector.h @@ -125,6 +125,16 @@ f (v->ptr[i]); \ } \ \ + /* Remove i'th element. i=0 => beginning i=size-1 => end */ \ + static inline int \ + name##_remove (name *v, size_t i) \ + { \ + if (i >= v->size) return -1; \ + memmove (&v->ptr[i], &v->ptr[i+1], (v->size-i) * sizeof (type)); \ + v->size--; \ + return 0; \ + } \ + \ /* Sort the elements of the vector. */ \ static inline void \ name##_sort (name *v, \ diff --git a/common/utils/test-vector.c b/common/utils/test-vector.c index 7b0a7424..a87f89ec 100644 --- a/common/utils/test-vector.c +++ b/common/utils/test-vector.c @@ -43,19 +43,43 @@ DEFINE_VECTOR_TYPE(int64_vector, int64_t); DEFINE_VECTOR_TYPE(string_vector, char *); +static int +compare (const int64_t *a, const int64_t *b) +{ + return (*a > *b) - (*a < *b); +} + static void test_int64_vector (void) { int64_vector v = empty_vector; size_t i; int r; + int64_t tmp, *p; for (i = 0; i < 10; ++i) { - r = int64_vector_append (&v, i); + r = int64_vector_insert (&v, i, 0); assert (r == 0); } + + for (i = 0; i < 10; ++i) + assert (v.ptr[i] == 9 - i); + int64_vector_sort (&v, compare); for (i = 0; i < 10; ++i) assert (v.ptr[i] == i); + + r = int64_vector_remove (&v, 1); + assert (r == 0); + assert (v.size == 9); + assert (v.ptr[1] == 2); + + tmp = 10; + p = int64_vector_search (&v, &tmp, (void*) compare); + assert (p == NULL); + tmp = 8; + p = int64_vector_search (&v, &tmp, (void*) compare); + assert (p == &v.ptr[7]); + free (v.ptr); } -- 2.27.0
Eric Blake
2020-Jul-07 22:22 UTC
[Libguestfs] [nbdkit PATCH 2/3] extents: Add nbdkit_extents_aligned()
We have several filters that would benefit from reporting extents to the client that are always aligned to boundaries chosen by the filter, regardless of whether the plugin reports extents at a finer granularity. Add a new helper function to make the work easier, without having to duplicate code in each filter. Any alignment block that straddles more than one plugin extent is reported as a single extent to the client, with a type determined by the intersection of the underlying extents. Signed-off-by: Eric Blake <eblake@redhat.com> --- docs/nbdkit-filter.pod | 18 ++++++++++ include/nbdkit-filter.h | 5 +++ server/extents.c | 80 ++++++++++++++++++++++++++++++++++++++++- server/nbdkit.syms | 1 + 4 files changed, 103 insertions(+), 1 deletion(-) diff --git a/docs/nbdkit-filter.pod b/docs/nbdkit-filter.pod index 510781e1..066ca1c7 100644 --- a/docs/nbdkit-filter.pod +++ b/docs/nbdkit-filter.pod @@ -719,6 +719,24 @@ Returns the number of extents in the list. Returns a copy of the C<i>'th extent. +=head3 Enforcing alignment of an nbdkit_extents list + +A convenience function is provided to filters only which makes it +easier to ensure that the client only encounters aligned extents. + + int nbdkit_extents_aligned (struct nbdkit_next_ops *next_ops, + nbdkit_backend *nxdata, + uint32_t count, uint64_t offset, + uint32_t flags, uint32_t align, + struct nbdkit_extents *extents, int *err); + +Calls next_ops->extents as needed until at least C<align> bytes are +obtained. Anywhere the underlying plugin returns differing extents +within C<align> bytes, this function treats that portion of the disk +as a single extent with zero and sparse status bits determined by the +intersection of all underlying extents. It is an error to call this +function with C<count> or C<offset> that is not already aligned. + =head2 C<.cache> int (*cache) (struct nbdkit_next_ops *next_ops, void *nxdata, diff --git a/include/nbdkit-filter.h b/include/nbdkit-filter.h index d81186f5..229a54b4 100644 --- a/include/nbdkit-filter.h +++ b/include/nbdkit-filter.h @@ -116,6 +116,11 @@ extern void nbdkit_extents_free (struct nbdkit_extents *); extern size_t nbdkit_extents_count (const struct nbdkit_extents *); extern struct nbdkit_extent nbdkit_get_extent (const struct nbdkit_extents *, size_t); +extern int nbdkit_extents_aligned (struct nbdkit_next_ops *next_ops, + nbdkit_backend *nxdata, + uint32_t count, uint64_t offset, + uint32_t flags, uint32_t align, + struct nbdkit_extents *extents, int *err); /* Filter struct. */ struct nbdkit_filter { diff --git a/server/extents.c b/server/extents.c index 4ab5946c..035497b5 100644 --- a/server/extents.c +++ b/server/extents.c @@ -1,5 +1,5 @@ /* nbdkit - * Copyright (C) 2019 Red Hat Inc. + * Copyright (C) 2019-2020 Red Hat Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are @@ -41,7 +41,10 @@ #include <errno.h> #include <assert.h> +#include "cleanup.h" +#include "isaligned.h" #include "minmax.h" +#include "rounding.h" #include "vector.h" #include "internal.h" @@ -206,3 +209,78 @@ nbdkit_add_extent (struct nbdkit_extents *exts, return append_extent (exts, &e); } } + +/* Compute aligned extents on behalf of a filter. */ +int +nbdkit_extents_aligned (struct nbdkit_next_ops *next_ops, + nbdkit_backend *nxdata, + uint32_t count, uint64_t offset, + uint32_t flags, uint32_t align, + struct nbdkit_extents *exts, int *err) +{ + size_t i; + struct nbdkit_extent e, e2; + + if (!IS_ALIGNED(count | offset, align)) { + nbdkit_error ("nbdkit_extents_aligned: unaligned request"); + *err = EINVAL; + return -1; + } + + /* Perform an initial query, then scan for the first unaligned extent. */ + if (next_ops->extents (nxdata, count, offset, flags, exts, err) == -1) + return -1; + for (i = 0; i < exts->extents.size; ++i) { + e = exts->extents.ptr[i]; + if (!IS_ALIGNED(e.length, align)) { + /* If the unalignment is past align, just truncate and return early */ + if (e.offset + e.length > offset + align) { + e.length = ROUND_DOWN (e.length, align); + exts->extents.size = i + !!e.length; + exts->next = e.offset + e.length; + break; + } + + /* Otherwise, coalesce until we have at least align bytes, which + * may require further queries. + */ + assert (i == 0); + while (e.length < align) { + if (exts->extents.size > 1) { + e.length += exts->extents.ptr[1].length; + e.type &= exts->extents.ptr[1].type; + extents_remove (&exts->extents, 1); + } + else { + /* The plugin needs a fresh extents object each time, but + * with care, we can merge it into the callers' extents. + */ + extents tmp; + CLEANUP_EXTENTS_FREE struct nbdkit_extents *extents2 = NULL; + + extents2 = nbdkit_extents_new (e.offset + e.length, offset + align); + if (next_ops->extents (nxdata, offset + align - e.length, + e.offset + e.length, + flags & ~NBDKIT_FLAG_REQ_ONE, + extents2, err) == -1) + return -1; + e2 = extents2->extents.ptr[0]; + assert (e2.offset == e.offset + e.length); + e2.offset = e.offset; + e2.length += e.length; + e2.type &= e.type; + e = e2; + tmp = exts->extents; + exts->extents = extents2->extents; + extents2->extents = tmp; + } + } + e.length = align; + exts->extents.size = 1; + exts->next = e.offset + e.length; + break; + } + } + /* Once we get here, all extents are aligned. */ + return 0; +} diff --git a/server/nbdkit.syms b/server/nbdkit.syms index 20c390a9..d62ad484 100644 --- a/server/nbdkit.syms +++ b/server/nbdkit.syms @@ -43,6 +43,7 @@ nbdkit_debug; nbdkit_error; nbdkit_export_name; + nbdkit_extents_aligned; nbdkit_extents_count; nbdkit_extents_free; nbdkit_extents_new; -- 2.27.0
Eric Blake
2020-Jul-07 22:22 UTC
[Libguestfs] [nbdkit PATCH 3/3] RFC swab: Re-enable .extents
This reverts commit 2c5aec42cf04c567639bd885cf12a57192229215. Now that we have an easy way to generate aligned extents from the plugin, where the client will never see an unaligned extent transition, it's time to put it to use. Signed-off-by: Eric Blake <eblake@redhat.com> --- Here's what I used on the command line; I need to turn it into a formal test: $ ./nbdkit -U - eval pread='exit 1' get_size='echo 8' can_extents='exit 0' \ extents='printf "0 3\n3 4 hole,zero\n7 1\n"' --run \ 'qemu-img map -f raw --output=json $uri' $ ./nbdkit -U - --filter=swab eval pread='exit 1' get_size='echo 8' can_extents='exit 0' extents='printf "0 3\n3 4 hole,zero\n7 1\n"' --run 'qemu-img map -f raw --output=json $uri' except it's currently failing: nbdkit: eval[1]: error: swab: requests to this filter must be aligned nbdkit: backend.c:621: backend_extents: Assertion `*err' failed. qemu-img: Could not read file metadata: Input/output error --- filters/swab/swab.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/filters/swab/swab.c b/filters/swab/swab.c index 57a51aee..2e423bbf 100644 --- a/filters/swab/swab.c +++ b/filters/swab/swab.c @@ -191,15 +191,15 @@ swab_zero (struct nbdkit_next_ops *next_ops, void *nxdata, return next_ops->zero (nxdata, count, offset, flags, err); } -/* FIXME: Extents could be useful, but if the underlying plugin ever reports - * values not aligned to 2 bytes, it is complicated to adjust that correctly. - * In the short term, we punt by disabling extents. - */ +/* Extents. */ static int -swab_can_extents (struct nbdkit_next_ops *next_ops, void *nxdata, - void *handle) +swab_extents (struct nbdkit_next_ops *next_ops, void *nxdata, + void *handle, uint32_t count, uint64_t offset, uint32_t flags, + struct nbdkit_extents *extents, int *err) { - return 0; + if (!is_aligned (count, offset)) return -1; + return nbdkit_extents_aligned (next_ops, nxdata, count, offset, flags, + bits/8, extents, err); } /* Cache. */ @@ -223,7 +223,7 @@ static struct nbdkit_filter filter = { .pwrite = swab_pwrite, .trim = swab_trim, .zero = swab_zero, - .can_extents = swab_can_extents, + .extents = swab_extents, .cache = swab_cache, }; -- 2.27.0
Richard W.M. Jones
2020-Jul-08 11:22 UTC
Re: [Libguestfs] [nbdkit PATCH 1/3] vector: Add VECT_remove
On Tue, Jul 07, 2020 at 05:22:45PM -0500, Eric Blake wrote:> An upcoming patch wants to remove an arbitrary element from a vector. > > Also, add testsuite coverage for other functions added since the > original unit test was written. It's a bit awkward that the compare > for VECT_search and VECT_sort differ in type, but such is life (we > indeed have search code where typing the key differently is useful).I think you should just push this kind of patch, but I have one comment below:> Signed-off-by: Eric Blake <eblake@redhat.com> > --- > common/utils/vector.h | 10 ++++++++++ > common/utils/test-vector.c | 26 +++++++++++++++++++++++++- > 2 files changed, 35 insertions(+), 1 deletion(-) > > diff --git a/common/utils/vector.h b/common/utils/vector.h > index c14644a7..880fd308 100644 > --- a/common/utils/vector.h > +++ b/common/utils/vector.h > @@ -125,6 +125,16 @@ > f (v->ptr[i]); \ > } \ > \ > + /* Remove i'th element. i=0 => beginning i=size-1 => end */ \ > + static inline int \ > + name##_remove (name *v, size_t i) \ > + { \ > + if (i >= v->size) return -1; \ > + memmove (&v->ptr[i], &v->ptr[i+1], (v->size-i) * sizeof (type)); \ > + v->size--; \ > + return 0; \ > + } \Do we need to have this function return an error indication? I would think that the check should be replaced with an assert. If it happens it's an internal error. 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
Richard W.M. Jones
2020-Jul-08 11:28 UTC
Re: [Libguestfs] [nbdkit PATCH 2/3] extents: Add nbdkit_extents_aligned()
On Tue, Jul 07, 2020 at 05:22:46PM -0500, Eric Blake wrote: [...]> +/* Compute aligned extents on behalf of a filter. */ > +int > +nbdkit_extents_aligned (struct nbdkit_next_ops *next_ops, > + nbdkit_backend *nxdata, > + uint32_t count, uint64_t offset, > + uint32_t flags, uint32_t align, > + struct nbdkit_extents *exts, int *err) > +{ > + size_t i; > + struct nbdkit_extent e, e2; > + > + if (!IS_ALIGNED(count | offset, align)) { > + nbdkit_error ("nbdkit_extents_aligned: unaligned request"); > + *err = EINVAL; > + return -1; > + }I wonder if this also should be an assert? This is less clear to me than the vector case however.> + /* Perform an initial query, then scan for the first unaligned extent. */ > + if (next_ops->extents (nxdata, count, offset, flags, exts, err) == -1) > + return -1; > + for (i = 0; i < exts->extents.size; ++i) { > + e = exts->extents.ptr[i]; > + if (!IS_ALIGNED(e.length, align)) { > + /* If the unalignment is past align, just truncate and return early */ > + if (e.offset + e.length > offset + align) { > + e.length = ROUND_DOWN (e.length, align); > + exts->extents.size = i + !!e.length; > + exts->next = e.offset + e.length; > + break; > + } > + > + /* Otherwise, coalesce until we have at least align bytes, which > + * may require further queries. > + */ > + assert (i == 0); > + while (e.length < align) { > + if (exts->extents.size > 1) { > + e.length += exts->extents.ptr[1].length; > + e.type &= exts->extents.ptr[1].type; > + extents_remove (&exts->extents, 1); > + } > + else { > + /* The plugin needs a fresh extents object each time, but > + * with care, we can merge it into the callers' extents. > + */ > + extents tmp; > + CLEANUP_EXTENTS_FREE struct nbdkit_extents *extents2 = NULL; > + > + extents2 = nbdkit_extents_new (e.offset + e.length, offset + align); > + if (next_ops->extents (nxdata, offset + align - e.length, > + e.offset + e.length, > + flags & ~NBDKIT_FLAG_REQ_ONE, > + extents2, err) == -1) > + return -1; > + e2 = extents2->extents.ptr[0]; > + assert (e2.offset == e.offset + e.length); > + e2.offset = e.offset; > + e2.length += e.length; > + e2.type &= e.type;So we're intersecting (&) the types defined as: #define NBDKIT_EXTENT_HOLE (1<<0) /* Same as NBD_STATE_HOLE */ #define NBDKIT_EXTENT_ZERO (1<<1) /* Same as NBD_STATE_ZERO */ If all extents are holes, then it's a hole. If all extents are zero, then it's a zero. Otherwise it's non-zero data. This seems correct. All looks good to me, so ACK. 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
Richard W.M. Jones
2020-Jul-08 11:32 UTC
Re: [Libguestfs] [nbdkit PATCH 3/3] RFC swab: Re-enable .extents
On Tue, Jul 07, 2020 at 05:22:47PM -0500, Eric Blake wrote:> This reverts commit 2c5aec42cf04c567639bd885cf12a57192229215. > > Now that we have an easy way to generate aligned extents from the > plugin, where the client will never see an unaligned extent > transition, it's time to put it to use. > > Signed-off-by: Eric Blake <eblake@redhat.com> > > --- > Here's what I used on the command line; I need to turn it into a formal test: > > $ ./nbdkit -U - eval pread='exit 1' get_size='echo 8' can_extents='exit 0' \ > extents='printf "0 3\n3 4 hole,zero\n7 1\n"' --run \ > 'qemu-img map -f raw --output=json $uri' > $ ./nbdkit -U - --filter=swab eval pread='exit 1' get_size='echo 8' can_extents='exit 0' extents='printf "0 3\n3 4 hole,zero\n7 1\n"' --run 'qemu-img map -f raw --output=json $uri' > > except it's currently failing: > nbdkit: eval[1]: error: swab: requests to this filter must be aligned > nbdkit: backend.c:621: backend_extents: Assertion `*err' failed. > qemu-img: Could not read file metadata: Input/output errorI would add -v to the command line, as it will show you exactly what requests qemu-img is making. The assert failure seems to be a separate and worrying problem. Rich.> filters/swab/swab.c | 16 ++++++++-------- > 1 file changed, 8 insertions(+), 8 deletions(-) > > diff --git a/filters/swab/swab.c b/filters/swab/swab.c > index 57a51aee..2e423bbf 100644 > --- a/filters/swab/swab.c > +++ b/filters/swab/swab.c > @@ -191,15 +191,15 @@ swab_zero (struct nbdkit_next_ops *next_ops, void *nxdata, > return next_ops->zero (nxdata, count, offset, flags, err); > } > > -/* FIXME: Extents could be useful, but if the underlying plugin ever reports > - * values not aligned to 2 bytes, it is complicated to adjust that correctly. > - * In the short term, we punt by disabling extents. > - */ > +/* Extents. */ > static int > -swab_can_extents (struct nbdkit_next_ops *next_ops, void *nxdata, > - void *handle) > +swab_extents (struct nbdkit_next_ops *next_ops, void *nxdata, > + void *handle, uint32_t count, uint64_t offset, uint32_t flags, > + struct nbdkit_extents *extents, int *err) > { > - return 0; > + if (!is_aligned (count, offset)) return -1; > + return nbdkit_extents_aligned (next_ops, nxdata, count, offset, flags, > + bits/8, extents, err); > } > > /* Cache. */ > @@ -223,7 +223,7 @@ static struct nbdkit_filter filter = { > .pwrite = swab_pwrite, > .trim = swab_trim, > .zero = swab_zero, > - .can_extents = swab_can_extents, > + .extents = swab_extents, > .cache = swab_cache, > }; > > -- > 2.27.0 > > _______________________________________________ > Libguestfs mailing list > Libguestfs@redhat.com > https://www.redhat.com/mailman/listinfo/libguestfs-- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-df lists disk usage of guests without needing to install any software inside the virtual machine. Supports Linux and Windows. http://people.redhat.com/~rjones/virt-df/
Apparently Analagous Threads
- [PATCH nbdkit v5 FINAL 00/19] Implement extents.
- Re: [nbdkit PATCH 2/3] extents: Add nbdkit_extents_aligned()
- [PATCH nbdkit v4 00/15] Implement Block Status.
- [PATCH nbdkit 0/8] Implement extents using a simpler array.
- [PATCH nbdkit 2/2] filters: Be careful to set *err if nbdkit_add_extent or nbdkit_extents_new fail.