Re: [Libguestfs] [PATCH nbdkit 1/9] server: Implement extents/can_extents calls for plugins and filters.

This pair of calls allows plugins to describe which extents in the virtual disk are allocated, holes or zeroes. ---

+ void nbdkit_extents_free (struct nbdkit_extents_map *); + +Frees an existing extents map.

+ +=head3 Iterating over nbdkit_extents_map + +One function is provided to filters only to iterate over the extents +map: + + typedef int (*nbdkit_extents_callback) (uint64_t offset, uint64_t length, + uint32_t type, void *opaque); + + int nbdkit_extents_foreach ( + const struct nbdkit_extents_map *extents_map, + nbdkit_extents_callback fn, void *opaque, + uint32_t flags, + uint64_t range_offset, uint64_t range_length); +

+=item C<NBDKIT_EXTENTS_FOREACH_FLAG_RANGE> + +If this flag is included then the C<range_offset> and C<range_length> +parameters are used, so only extents overlapping +C<[range_offset...range_offset+range_length-1]> are returned.

+++ b/docs/nbdkit-plugin.pod

+The callback should detect and return the list of extents overlapping +the range C<[offset...offset+count-1]>. The C<extents_map> parameter +points to an opaque object which the callback should fill in by +calling C<nbdkit_extent_add> etc. See L</Extents map> below. + +The C<flags> parameter may contain the flag C<NBDKIT_FLAG_REQ_ONE> +which means that the client is only requesting information about the +extent overlapping C<offset>. The plugin may ignore this flag, or as +an optimization it may return just a single extent for C<offset>. +(Note that implementing this optimization correctly is difficult and +subtle. You must ensure that the upper limit of the single extent +returned is correct. If unsure then the safest option is to ignore +this flag.)

+ +If there is an error, C<.extents> should call C<nbdkit_error> with an +error message, and C<nbdkit_set_error> to record an appropriate error +(unless C<errno> is sufficient), then return C<-1>. + +=head3 Extents map + +The plugin C<extents> callback is passed an opaque pointer C<struct +nbdkit_extents_map *extents_map>. This structure represents a list of +L<filesystem extents|https://en.wikipedia.org/wiki/Extent_(file_systems)> +describing which areas of the disk are allocated, which are sparse +(“holes”), and, if supported, which are zeroes. Initially the map +describes a single allocated data extent covering the entire virtual +disk. + +The C<extents> callback has to fill in any holes or zeroes areas by +calling C<nbdkit_extent*> functions, to describe all extents +overlapping the range C<[offset...offset+count-1]>. (nbdkit will +ignore extents outside this range so plugins may, if it is easier to +implement, return all extent information for the whole disk.)

+++ b/server/extents.c

+/* Trivial implementation as an ordered list of extents. We will + * probably have to change this to a more efficient data structure if + * we have plugins with lots of extents. + * + * Invariants: + * - extents are stored in ascending order + * - extents must not overlap + * - adjacent extents must not have the same type + *

+ +/* Find the extent before or containing offset. If offset is inside + * the extent, the extent index is returned. If offset is not in any + * extent, but there is an extent with a lower offset, then the index + * of the nearest lower extent is returned. If offset is before the + * zeroth extent then -1 is returned.

+int +nbdkit_extent_add (struct nbdkit_extents_map *map, + uint64_t offset, uint64_t length, uint32_t type) +{ + ssize_t lo, hi; + bool coalesce_below, coalesce_above; + struct extent new_extent; + + /* This might be considered an error, but be flexible for badly + * written plugins. + */ + if (length == 0) + return 0; + + /* Don't allow extents to exceeed the _signed_ 64 bit limit that is

+ * used in the rest of nbdkit. + */ + if (offset > INT64_MAX || + offset + length < offset || + offset + length > INT64_MAX) { + nbdkit_error ("nbdkit_extent_add: " + "extent cannot exceed signed 64 bit limit: " + "offset=%" PRIu64 " length=%" PRIu64, + offset, length); + return -1; + } + + again: + lo = find_extent (map, offset); + hi = find_extent (map, offset + length - 1); + + /* "lo" and "hi" are -1 or they point to the extent + * overlapping-or-below the corresponding endpoints of the new + * extent. + * + * The algorithm here has two parts: Firstly we remove any + * overlapping extents (this may involve erasing extents completely + * or shrinking them). Secondly we insert the new extent at the + * right place in the array, if necessary allowing it to coalesce + * with the extent above or below. + * + * To remove overlapping extents we consider 7 cases: + * + * A.0 lo == -1 (there is no old extent before the new extent) + * => do nothing + * + * A.1 ┌─────┐ offset of new extent exactly at + * │ lo │ beginning of lo and lo smaller/equal + * └─────┘ to new extent + * ↑ + * ▐▓▓▓▓▓▓▓▓▓ + * => erase lo + * => creates situation A.0 or A.5 + * + * A.2 ┌──────────┐ offset of new extent exactly at + * │ lo │ beginning of lo and lo bigger than + * └──────────┘ new extent + * ↑ + * ▐▓▓▓▓▓▓▓▓▓ + * => shrink lo “upwards” + * => creates situation A.0 or A.5 + * + * A.3 ┌──────────────┐ new extent in the middle + * │ lo │ of lo + * └──────────────┘ + * ↑ + * ▓▓▓▓▓▓▓▓▓ + * => split lo + * => creates situation A.5 + * + * A.4 ┌─────┐ offset of new extent in the middle + * │ lo │ of lo + * └─────┘ + * ↑ + * ▓▓▓▓▓▓▓▓▓ + * => shrink lo + * => creates situation A.5 + * + * A.5 ┌─────┐ offset of new extent after lo + * │ lo │ + * └─────┘ + * ↑ + * ▓▓▓▓▓▓▓▓▓ + * => do nothing + * + * B.0 lo == hi or hi == -1 (there is no higher extent) + * => do nothing + * + * B.1 ┌─────┐ extent hi is fully covered + * │ hi │ by new extent + * └─────┘ + * ↑ + * ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ + * => erase hi + * => creates situation B.0 + * + * B.2 ┌─────┐ extent hi is partly overlapped + * │ hi │ by new extent + * └─────┘ + * ↑ + * ▓▓▓▓▓▓▓▓▓▓▓ + * => shrink hi + * => creates situation B.0 + * + * In addition extents [lo+1...hi-1] (if they exist) are erased + * since they must be fully covered by the new extent. + * + * At the end we're in situation A.0/A.5 and B.0, and so no old + * extents overlap the new extent. + * + * The insertion can then be done with optional coalescing (see code + * below for details - this is a lot simpler). + */ + + /* A.0 */ + if (lo == -1) + goto erase_middle_extents; + /* A.5 */ + if (offset >= map->extents[lo].offset + map->extents[lo].length) + goto erase_middle_extents; + + /* A.1 or A.2 */ + if (offset == map->extents[lo].offset) { + if (map->extents[lo].offset + map->extents[lo].length <= offset + length) { + /* A.1 */ + erase_extents (map, lo, 1); + } + else { + /* A.2 */ + uint64_t end = map->extents[lo].offset + map->extents[lo].length; + map->extents[lo].offset = offset + length; + map->extents[lo].length = end - map->extents[lo].offset; + } + goto again; + } + + /* A.3 */ + if (map->extents[lo].offset < offset && + map->extents[lo].offset + map->extents[lo].length > offset + length) { + new_extent.offset = offset + length; + new_extent.length = + map->extents[lo].offset + map->extents[lo].length - new_extent.offset; + new_extent.type = map->extents[lo].type; + map->extents[lo].length = offset - map->extents[lo].offset; + if (insert_extent (map, new_extent, lo+1) == -1) + return -1; + goto again; + } + + /* We must be in situation A.4 assuming analysis above is exhaustive. */ + assert (offset > map->extents[lo].offset); + assert (offset < map->extents[lo].offset + map->extents[lo].length); + assert (map->extents[lo].offset + map->extents[lo].length <= offset + length); + + map->extents[lo].length = offset - map->extents[lo].offset; + + erase_middle_extents: + /* Erase extents [lo+1..hi-1] if they exist as they must be + * completely covered by the new extent. + */ + if (hi >= 0 && lo+1 < hi) { + erase_extents (map, lo+1, hi-lo-1); + goto again; + } + + /* B.0 */ + if (lo == hi || hi == -1) + goto insert; + + /* B.1 */ + if (map->extents[hi].offset + map->extents[hi].length <= offset + length) { + erase_extents (map, hi, 1);

+ goto again; + } + + /* We must be in situation B.2 if the analysis above is exhaustive. */ + assert (map->extents[hi].offset < offset + length); + + uint64_t end = map->extents[hi].offset + map->extents[hi].length; + map->extents[hi].offset = offset + length; + map->extents[hi].length = end - map->extents[hi].offset; + + insert: + /* Now we know there is no extent which overlaps with the new + * extent, and the new extent must be inserted after lo. + */ + + /* However we have to deal with possibly coalescing the new extent + * with lo and/or lo+1. + */

+ coalesce_below = + lo >= 0 && + map->extents[lo].type == type && + map->extents[lo].offset + map->extents[lo].length == offset; + coalesce_above = + lo+1 < map->nr_extents && + map->extents[lo+1].type == type && + map->extents[lo+1].offset == offset + length; + + if (coalesce_below && coalesce_above) { + /* Coalesce lo + new extent + lo+1 + * => Extend lo to cover the whole range and remove lo+1. + */ + map->extents[lo].length = + map->extents[lo+1].offset + map->extents[lo+1].length + - map->extents[lo].offset; + erase_extents (map, lo+1, 1); + } + else if (coalesce_below) { + /* Coalesce lo + new extent. + * => Extend lo to cover new extent. + */ + map->extents[lo].length = offset + length - map->extents[lo].offset; + } + else if (coalesce_above) { + /* Coalesce new extent + lo+1 + * => Extend lo+1 to cover new extent. + */ + map->extents[lo+1].length = + map->extents[lo+1].offset + map->extents[lo+1].length - offset; + map->extents[lo+1].offset = offset; + } + else { + /* Normal case: Allocate a new extent and insert it after lo. */ + new_extent.offset = offset; + new_extent.length = length; + new_extent.type = type; + if (insert_extent (map, new_extent, lo+1) == -1) + return -1; + } + + return 0;

+} + +int +nbdkit_extents_foreach (const struct nbdkit_extents_map *map, + nbdkit_extents_callback fn, void *opaque, + uint32_t flags, + uint64_t range_offset, uint64_t range_length) +{ + const bool flag_range = flags & NBDKIT_EXTENTS_FOREACH_FLAG_RANGE; + const bool flag_one = flags & NBDKIT_EXTENTS_FOREACH_FLAG_ONE; + uint64_t offset, next; + size_t i; + + if (flag_range) { + if (range_offset + range_length < range_offset) { + nbdkit_error ("nbdkit_extents_foreach: invalid range: " + "offset=%" PRIu64 " length=%" PRIu64, + range_offset, range_length); + return -1; + }

+ } + else { + range_offset = 0; + range_length = INT64_MAX + UINT64_C(1); + } + + for (i = 0, offset = range_offset; + offset < range_offset + range_length; + offset = next) { + next = offset; + + if (i >= map->nr_extents) { + /* Beyond last extent => Type 0 to end of range. */ + next = range_offset + range_length; + if (fn (offset, next - offset, 0, opaque) == -1) + return -1; + if (flag_one) + return 0; + continue; + } + + if (offset < map->extents[i].offset) { + /* In a gap before the i'th extent => Type 0 to next offset. */

+ next = MIN (map->extents[i].offset, range_offset + range_length); + if (fn (offset, next - offset, 0, opaque) == -1) + return -1; + if (flag_one) + return 0; + continue; + } + + if (offset < map->extents[i].offset + map->extents[i].length) { + /* In an extent. */ + next = MIN (map->extents[i].offset + map->extents[i].length, + range_offset + range_length); + if (fn (offset, next - offset, map->extents[i].type, opaque) == -1) + return -1; + if (flag_one) + return 0; + continue; + } + + /* After an extent, increment i and iterate. */ + i++; + } + + return 0; +} + +#ifdef IN_TEST_EXTENTS