[Libguestfs] [PATCH nbdkit v2 1/4] common/bitmap: Add bitmap_next function and tests.

It's useful to be able to search for the next non-zero entry in a bitmap. This commit adds a ‘bitmap_next’ function to do that. Because the bitmap is just a uint8_t buffer, using fast string functions we should be able to do this quickly even if the bitmap is sparse. (However the actual implementation is not optimized since that is quite complicated - see to-do comments in common/include/nextnonzero.h). I wasn't confident about the correctness of the code and so this commit also adds some unit tests covering all of the bitmap code. --- common/bitmap/bitmap.h | 6 ++ common/include/iszero.h | 3 + common/include/nextnonzero.h | 59 +++++++++++++ common/bitmap/bitmap.c | 35 ++++++++ common/bitmap/test-bitmap.c | 162 +++++++++++++++++++++++++++++++++++ .gitignore | 1 + common/bitmap/Makefile.am | 12 +++ common/include/Makefile.am | 1 + 8 files changed, 279 insertions(+) diff --git a/common/bitmap/bitmap.h b/common/bitmap/bitmap.h index f943933..80fd5e4 100644 --- a/common/bitmap/bitmap.h +++ b/common/bitmap/bitmap.h @@ -165,4 +165,10 @@ bitmap_set (const struct bitmap *bm, uint64_t offset, unsigned v) #define bitmap_for(bm, /* uint64_t */ blknum) \ for ((blknum) = 0; (blknum) < (bm)->size * (bm)->ibpb; ++(blknum)) +/* Find the next non-zero block in the bitmap, starting at ‘blk’. + * Returns -1 if the bitmap is all zeroes from blk to the end of the + * bitmap. + */ +extern int64_t bitmap_next (const struct bitmap *bm, uint64_t blk); + #endif /* NBDKIT_BITMAP_H */ diff --git a/common/include/iszero.h b/common/include/iszero.h index 1079f3e..7a54f0a 100644 --- a/common/include/iszero.h +++ b/common/include/iszero.h @@ -42,6 +42,9 @@ * The clever approach here was suggested by Eric Blake. See: * https://www.redhat.com/archives/libguestfs/2017-April/msg00171.html * https://rusty.ozlabs.org/?p=560 + * + * See also: + * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69908 */ static inline bool is_zero (const char *buffer, size_t size) diff --git a/common/include/nextnonzero.h b/common/include/nextnonzero.h new file mode 100644 index 0000000..3f96e85 --- /dev/null +++ b/common/include/nextnonzero.h @@ -0,0 +1,59 @@ +/* nbdkit + * Copyright (C) 2018 Red Hat Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of Red Hat nor the names of its contributors may be + * used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef NBDKIT_NEXTNONZERO_H +#define NBDKIT_NEXTNONZERO_H + +/* Given a byte buffer, return a pointer to the first non-zero byte, + * or return NULL if we reach the end of the buffer. + * + * XXX: Even with -O3 -mavx2, gcc 8.2.1 makes a terrible job with this + * loop, compiling it completely naively. QEMU has an AVX2 + * implementation of a similar loop. + * + * See also: + * https://sourceware.org/bugzilla/show_bug.cgi?id=19920 + * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69908 + */ +static inline const char * +next_non_zero (const char *buffer, size_t size) +{ + size_t i; + + for (i = 0; i < size; ++i) + if (buffer[i] != 0) + return &buffer[i]; + return NULL; +} + +#endif /* NBDKIT_NEXTNONZERO_H */ diff --git a/common/bitmap/bitmap.c b/common/bitmap/bitmap.c index fb5dbe7..9690a2e 100644 --- a/common/bitmap/bitmap.c +++ b/common/bitmap/bitmap.c @@ -42,6 +42,7 @@ #include "bitmap.h" #include "rounding.h" +#include "nextnonzero.h" int bitmap_resize (struct bitmap *bm, uint64_t new_size) @@ -73,3 +74,37 @@ bitmap_resize (struct bitmap *bm, uint64_t new_size) return 0; } + +int64_t +bitmap_next (const struct bitmap *bm, uint64_t blk) +{ + uint64_t limit = bm->size * bm->ibpb; + const uint8_t *p; + + /* Align to the next byte boundary. */ + for (; blk < limit && (blk & (bm->ibpb-1)) != 0; ++blk) { + if (bitmap_get_blk (bm, blk, 0) != 0) + return blk; + } + if (blk == limit) + return -1; + + /* Now we're at a byte boundary we can use a fast string function to + * find the next non-zero byte. + */ + p = &bm->bitmap[blk >> (3 - bm->bitshift)]; + p = (const uint8_t *) next_non_zero ((const char *) p, + &bm->bitmap[bm->size] - p); + if (p == NULL) + return -1; + + /* Now check the non-zero byte to find out which bit (ie. block) is set. */ + blk = (p - bm->bitmap) << (3 - bm->bitshift); + for (; blk < limit; ++blk) { + if (bitmap_get_blk (bm, blk, 0) != 0) + return blk; + } + + /* Should never be reached. */ + abort (); +} diff --git a/common/bitmap/test-bitmap.c b/common/bitmap/test-bitmap.c new file mode 100644 index 0000000..6bf4574 --- /dev/null +++ b/common/bitmap/test-bitmap.c @@ -0,0 +1,162 @@ +/* nbdkit + * Copyright (C) 2018 Red Hat Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the name of Red Hat nor the names of its contributors may be + * used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, + * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF + * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* Unit tests of the bitmap code. */ + +#include <config.h> + +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <stdarg.h> +#include <string.h> +#include <errno.h> +#include <assert.h> + +#include <nbdkit-plugin.h> + +#include "bitmap.h" + +static void +test (int bpb, int blksize) +{ + struct bitmap bm; + const int nr_blocks = 1000; + int blks[] = + { + 1, 2, 3, 10, 12, + 90, 91, 92, 93, 94, 99, + 800, 801, 802, 803, + 902, 903, 905, 907, 911, 913, 917, 919, 923, 929, + 999 + }; + unsigned v, vexp; + size_t i, j; + + printf ("bpb = %d, blksize = %d\n", bpb, blksize); + fflush (stdout); + + bitmap_init (&bm, blksize, bpb); + if (bitmap_resize (&bm, nr_blocks * blksize) == -1) + exit (EXIT_FAILURE); + + /* Set some bits at known block numbers. */ + for (j = 0; j < sizeof blks / sizeof blks[0]; ++j) { + v = (j & 1) == 0 ? 1 : (1<<bpb) - 1; + bitmap_set_blk (&bm, blks[j], v); + } + + /* Check the values of all bits. */ + for (i = j = 0; i < nr_blocks; ++i) { + if (i == blks[j]) { /* previously set bit */ + vexp = (j & 1) == 0 ? 1 : (1<<bpb) - 1; + v = bitmap_get_blk (&bm, blks[j], 0); + assert (v == vexp); + ++j; + } + else { /* unset bit, except it to be zero */ + v = bitmap_get_blk (&bm, i, 0); + assert (v == 0); + } + } + + /* Same as above, but using bitmap_for macro. */ + j = 0; + bitmap_for (&bm, i) { + if (i == blks[j]) { /* previously set bit */ + vexp = (j & 1) == 0 ? 1 : (1<<bpb) - 1; + v = bitmap_get_blk (&bm, blks[j], 0); + assert (v == vexp); + ++j; + } + else { /* unset bit, except it to be zero */ + v = bitmap_get_blk (&bm, i, 0); + assert (v == 0); + } + } + + /* Use bitmap_next to iterate over the non-zero entries in the bitmap. */ + i = bitmap_next (&bm, 0); + j = 0; + while (i != -1) { + assert (i == blks[j]); + vexp = (j & 1) == 0 ? 1 : (1<<bpb) - 1; + v = bitmap_get_blk (&bm, i, 0); + assert (v == vexp); + i = bitmap_next (&bm, i+1); + ++j; + } + + bitmap_free (&bm); +} + +int +main (void) +{ + int bpb; + size_t i; + int blksizes[] = { 1, 2, 4, 1024, 2048, 4096, 16384 }; + + /* Try the tests at each bpb setting and at a range of block sizes. */ + for (bpb = 1; bpb <= 8; bpb <<= 1) + for (i = 0; i < sizeof blksizes / sizeof blksizes[0]; ++i) + test (bpb, blksizes[i]); + + exit (EXIT_SUCCESS); +} + +/* The bitmap code uses nbdkit_debug, normally provided by the main + * server program. So we have to provide it here. + */ +void +nbdkit_debug (const char *fs, ...) +{ + /* do nothing */ +} + +/* Same for nbdkit_error. */ +void +nbdkit_error (const char *fs, ...) +{ + int err = errno; + va_list args; + + va_start (args, fs); + fprintf (stderr, "error: "); + errno = err; /* Must restore in case fs contains %m */ + vfprintf (stderr, fs, args); + fprintf (stderr, "\n"); + va_end (args); + + errno = err; +} diff --git a/.gitignore b/.gitignore index e5b5d82..fc019e9 100644 --- a/.gitignore +++ b/.gitignore @@ -24,6 +24,7 @@ Makefile.in /aclocal.m4 /autom4te.cache +/common/bitmap/test-bitmap /common/include/test-byte-swapping /common/include/test-current-dir-name /common/include/test-isaligned diff --git a/common/bitmap/Makefile.am b/common/bitmap/Makefile.am index cbd82bd..dade5ec 100644 --- a/common/bitmap/Makefile.am +++ b/common/bitmap/Makefile.am @@ -42,3 +42,15 @@ libbitmap_la_CPPFLAGS = \ -I$(top_srcdir)/common/include libbitmap_la_CFLAGS = \ $(WARNINGS_CFLAGS) + +# Unit tests. + +TESTS = test-bitmap +check_PROGRAMS = test-bitmap + +test_bitmap_SOURCES = test-bitmap.c bitmap.c bitmap.h +test_bitmap_CPPFLAGS = \ + -I$(top_srcdir)/include \ + -I$(top_srcdir)/common/include +test_bitmap_CFLAGS = \ + $(WARNINGS_CFLAGS) diff --git a/common/include/Makefile.am b/common/include/Makefile.am index 506fe2c..3e7f056 100644 --- a/common/include/Makefile.am +++ b/common/include/Makefile.am @@ -41,6 +41,7 @@ EXTRA_DIST = \ isaligned.h \ ispowerof2.h \ iszero.h \ + nextnonzero.h \ random.h \ rounding.h -- 2.19.2