thr3ads.net - Libguestfs - [Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library. [Dec 2018]

If this information is useful, please help other people find it:
Share via:

Richard W.M. Jones

2018-Dec-03 22:13 UTC

[Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

v2:
https://www.redhat.com/archives/libguestfs/2018-December/msg00039.html

v2 -> v3:

 - Fix all the issues raised in Eric's review.

 - Precompute some numbers to make the calculations easier.

 - Calculations now use bitshifts and masks in preference to division
   and modulo.

 - Clear existing bits before setting (which fixes a bug in the cache
   filter).

Rich.

Richard W.M. Jones

2018-Dec-03 22:13 UTC

head link

[Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

The cow and cache filters both use a bitmap mapping virtual disk
blocks to status stored in the bitmap.  The implementation of the
bitmaps is very similar because one was derived from the other when
the filters were implemented.

The main difference is the cow filter uses a simple bitmap (one bit
per block), whereas the cache filter uses two bits per block.

This commit abstracts the bitmap structure into a common library.  The
block size and bits per block are configurable.

This commit is refactoring, except:

- it cures a memory leak (bitmap was not being freed),

- in the cache filter we now mask out existing bits when updating the
  bitmap.
---
 configure.ac              |   1 +
 Makefile.am               |   1 +
 common/bitmap/bitmap.h    | 166 ++++++++++++++++++++++++++++++++++++++
 common/bitmap/bitmap.c    |  75 +++++++++++++++++
 filters/cache/cache.c     | 122 +++++++---------------------
 filters/cow/cow.c         |  59 +++-----------
 common/bitmap/Makefile.am |  44 ++++++++++
 filters/cache/Makefile.am |   3 +
 filters/cow/Makefile.am   |   3 +
 9 files changed, 335 insertions(+), 139 deletions(-)

diff --git a/configure.ac b/configure.ac
index 91b5f5b..cf931cd 100644
--- a/configure.ac
+++ b/configure.ac
@@ -779,6 +779,7 @@ AC_CONFIG_FILES([podwrapper.pl],
                 [chmod +x,-w podwrapper.pl])
 AC_CONFIG_FILES([Makefile
                  bash/Makefile
+                 common/bitmap/Makefile
                  common/include/Makefile
                  common/regions/Makefile
                  common/sparse/Makefile
diff --git a/Makefile.am b/Makefile.am
index 28d5723..cc56d61 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -67,6 +67,7 @@ SUBDIRS = \
 
 if HAVE_PLUGINS
 SUBDIRS += \
+	common/bitmap \
 	common/regions \
 	common/sparse \
 	plugins \
diff --git a/common/bitmap/bitmap.h b/common/bitmap/bitmap.h
new file mode 100644
index 0000000..2330249
--- /dev/null
+++ b/common/bitmap/bitmap.h
@@ -0,0 +1,166 @@
+/* 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.
+ */
+
+/* This is a very simple structure for creating a bitmap associated
+ * with a virtual disk.  1, 2, 4 or 8 bits can be associated with each
+ * block of the disk.  You can choose the number of bits and block
+ * size when creating the bitmap.  Entries in the bitmap are
+ * initialized to 0.
+ */
+
+#ifndef NBDKIT_BITMAP_H
+#define NBDKIT_BITMAP_H
+
+#include <stdint.h>
+#include <assert.h>
+
+#include "ispowerof2.h"
+
+/* This is the bitmap structure. */
+struct bitmap {
+  unsigned blksize;             /* Block size. */
+  unsigned bpb;                 /* Bits per block (1, 2, 4, 8 only). */
+  /* bpb = 1 << bitshift   ibpb = 8/bpb
+     1          0          8
+     2          1          4
+     4          2          2
+     8          3          1
+  */
+  unsigned bitshift, ibpb;
+
+  uint8_t *bitmap;              /* The bitmap. */
+  size_t size;                  /* Size of bitmap in bytes. */
+};
+
+static inline void
+bitmap_init (struct bitmap *bm, unsigned blksize, unsigned bpb)
+{
+  assert (is_power_of_2 (blksize));
+  bm->blksize = blksize;
+
+  /* bpb can be 1, 2, 4 or 8 only. */
+  bm->bpb = bpb;
+  bm->ibpb = 8/bpb;
+  switch (bpb) {
+  case 1: bm->bitshift = 0; break;
+  case 2: bm->bitshift = 1; break;
+  case 4: bm->bitshift = 2; break;
+  case 8: bm->bitshift = 3; break;
+  default: abort ();
+  }
+
+  bm->bitmap = NULL;
+  bm->size = 0;
+}
+
+/* Only frees the bitmap itself, since it is assumed that the struct
+ * bitmap is statically allocated.
+ */
+static inline void
+bitmap_free (struct bitmap *bm)
+{
+  if (bm)
+    free (bm->bitmap);
+}
+
+/* Resize the bitmap to the virtual disk size in bytes.
+ * Returns -1 on error, setting nbdkit_error.
+ */
+extern int bitmap_resize (struct bitmap *bm, uint64_t new_size);
+
+/* This macro calculates the byte offset in the bitmap and which
+ * bit/mask we are addressing within that byte.
+ *
+ * bpb     blk_offset         blk_bit          mask
+ * 1       blk >> 3           0,1,2,...,7      any single bit
+ * 2       blk >> 2           0, 2, 4 or 6     0x3, 0xc, 0x30 or 0xc0
+ * 4       blk >> 1           0 or 4           0xf, 0xf0
+ * 8       blk >> 0           always 0         always 0xff
+ */
+#define BITMAP_OFFSET_BIT_MASK(bm, blk)                         \
+  uint64_t blk_offset = (blk) >> (3 - (bm)->bitshift);          \
+  unsigned blk_bit = (bm)->bpb * ((blk) & ((bm)->ibpb - 1));    \
+  unsigned mask = ((1 << (bm)->bpb) - 1) << blk_bit
+
+/* Return the bit(s) associated with the given block.
+ * If the request is out of range, returns the default value.
+ */
+static inline unsigned
+bitmap_get_blk (const struct bitmap *bm, uint64_t blk, unsigned default_)
+{
+  BITMAP_OFFSET_BIT_MASK (bm, blk);
+
+  if (blk_offset >= bm->size) {
+    nbdkit_debug ("bitmap_get: block number is out of range");
+    return default_;
+  }
+
+  return (bm->bitmap[blk_offset] & mask) >> blk_bit;
+}
+
+/* As above but works with virtual disk offset in bytes. */
+static inline unsigned
+bitmap_get (const struct bitmap *bm, uint64_t offset, unsigned default_)
+{
+  return bitmap_get_blk (bm, offset / bm->blksize, default_);
+}
+
+/* Set the bit(s) associated with the given block.
+ * If out of range, it is ignored.
+ */
+static inline void
+bitmap_set_blk (const struct bitmap *bm, uint64_t blk, unsigned v)
+{
+  BITMAP_OFFSET_BIT_MASK (bm, blk);
+
+  if (blk_offset >= bm->size) {
+    nbdkit_debug ("bitmap_set: block number is out of range");
+    return;
+  }
+
+  bm->bitmap[blk_offset] &= ~mask;
+  bm->bitmap[blk_offset] |= v << blk_bit;
+}
+
+/* As above bit works with virtual disk offset in bytes. */
+static inline void
+bitmap_set (const struct bitmap *bm, uint64_t offset, unsigned v)
+{
+  return bitmap_set_blk (bm, offset / bm->blksize, v);
+}
+
+/* Iterate over blocks represented in the bitmap. */
+#define bitmap_for(bm, /* uint64_t */ blknum)                           \
+  for ((blknum) = 0; (blknum) < (bm)->size * (8 / (bm)->bpb);
++(blknum))
+
+#endif /* NBDKIT_BITMAP_H */
diff --git a/common/bitmap/bitmap.c b/common/bitmap/bitmap.c
new file mode 100644
index 0000000..fb5dbe7
--- /dev/null
+++ b/common/bitmap/bitmap.c
@@ -0,0 +1,75 @@
+/* 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.
+ */
+
+#include <config.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+
+#include <nbdkit-plugin.h>
+
+#include "bitmap.h"
+#include "rounding.h"
+
+int
+bitmap_resize (struct bitmap *bm, uint64_t new_size)
+{
+  uint8_t *new_bitmap;
+  const size_t old_bm_size = bm->size;
+  uint64_t new_bm_size_u64;
+  size_t new_bm_size;
+
+  new_bm_size_u64 = DIV_ROUND_UP (new_size,
+                                  bm->blksize * UINT64_C(8) / bm->bpb);
+  if (new_bm_size_u64 > SIZE_MAX) {
+    nbdkit_error ("bitmap too large for this architecture");
+    return -1;
+  }
+  new_bm_size = (size_t) new_bm_size_u64;
+
+  new_bitmap = realloc (bm->bitmap, new_bm_size);
+  if (new_bitmap == NULL) {
+    nbdkit_error ("realloc: %m");
+    return -1;
+  }
+  bm->bitmap = new_bitmap;
+  bm->size = new_bm_size;
+  if (old_bm_size < new_bm_size)
+    memset (&bm->bitmap[old_bm_size], 0, new_bm_size-old_bm_size);
+
+  nbdkit_debug ("bitmap resized to %zu bytes", new_bm_size);
+
+  return 0;
+}
diff --git a/filters/cache/cache.c b/filters/cache/cache.c
index b9de92a..e9a5c38 100644
--- a/filters/cache/cache.c
+++ b/filters/cache/cache.c
@@ -52,7 +52,7 @@
 
 #include <nbdkit-filter.h>
 
-#include "rounding.h"
+#include "bitmap.h"
 
 /* XXX See design comment in filters/cow/cow.c. */
 #define THREAD_MODEL NBDKIT_THREAD_MODEL_SERIALIZE_ALL_REQUESTS
@@ -75,10 +75,7 @@ static int fd = -1;
  * 10 = <unused>
  * 11 = block cached and dirty
  */
-static uint8_t *bitmap;
-
-/* Size of the bitmap in bytes. */
-static size_t bm_size;
+static struct bitmap bm;
 
 enum bm_entry {
   BLOCK_NOT_CACHED = 0,
@@ -93,9 +90,7 @@ static enum cache_mode {
   CACHE_MODE_UNSAFE,
 } cache_mode = CACHE_MODE_WRITEBACK;
 
-static int
-cache_flush (struct nbdkit_next_ops *next_ops, void *nxdata, void *handle,
-             uint32_t flags, int *err);
+static int cache_flush (struct nbdkit_next_ops *next_ops, void *nxdata, void
*handle, uint32_t flags, int *err);
 
 static void
 cache_load (void)
@@ -104,6 +99,8 @@ cache_load (void)
   size_t len;
   char *template;
 
+  bitmap_init (&bm, BLKSIZE, 2 /* bits per block */);
+
   tmpdir = getenv ("TMPDIR");
   if (!tmpdir)
     tmpdir = LARGE_TMPDIR;
@@ -133,6 +130,8 @@ cache_unload (void)
 {
   if (fd >= 0)
     close (fd);
+
+  bitmap_free (&bm);
 }
 
 static int
@@ -180,28 +179,8 @@ cache_open (nbdkit_next_open *next, void *nxdata, int
readonly)
 static int
 blk_set_size (uint64_t new_size)
 {
-  uint8_t *new_bm;
-  const size_t old_bm_size = bm_size;
-  uint64_t new_bm_size_u64 = DIV_ROUND_UP (new_size, BLKSIZE*8/2);
-  size_t new_bm_size;
-
-  if (new_bm_size_u64 > SIZE_MAX) {
-    nbdkit_error ("bitmap too large for this architecture");
+  if (bitmap_resize (&bm, new_size) == -1)
     return -1;
-  }
-  new_bm_size = (size_t) new_bm_size_u64;
-
-  new_bm = realloc (bitmap, new_bm_size);
-  if (new_bm == NULL) {
-    nbdkit_error ("realloc: %m");
-    return -1;
-  }
-  bitmap = new_bm;
-  bm_size = new_bm_size;
-  if (old_bm_size < new_bm_size)
-    memset (&bitmap[old_bm_size], 0, new_bm_size-old_bm_size);
-
-  nbdkit_debug ("cache: bitmap resized to %zu bytes", new_bm_size);
 
   if (ftruncate (fd, new_size) == -1) {
     nbdkit_error ("ftruncate: %m");
@@ -246,36 +225,6 @@ cache_prepare (struct nbdkit_next_ops *next_ops, void
*nxdata,
   return 0;
 }
 
-/* Return true if the block is allocated.  Consults the bitmap. */
-static enum bm_entry
-blk_get_bitmap_entry (uint64_t blknum)
-{
-  uint64_t bm_offset = blknum / 4;
-  uint64_t bm_bit = 2 * (blknum % 4);
-
-  if (bm_offset >= bm_size) {
-    nbdkit_debug ("blk_get_bitmap_entry: block number is out of
range");
-    return BLOCK_NOT_CACHED;
-  }
-
-  return (bitmap[bm_offset] & (3 << bm_bit)) >> bm_bit;
-}
-
-/* Update cache state of a block. */
-static void
-blk_set_bitmap_entry (uint64_t blknum, enum bm_entry state)
-{
-  uint64_t bm_offset = blknum / 4;
-  uint64_t bm_bit = 2 * (blknum % 4);
-
-  if (bm_offset >= bm_size) {
-    nbdkit_debug ("blk_set_bitmap_entry: block number is out of
range");
-    return;
-  }
-
-  bitmap[bm_offset] |= (unsigned) state << bm_bit;
-}
-
 /* These are the block operations.  They always read or write a single
  * whole block of size ‘blksize’.
  */
@@ -284,7 +233,7 @@ blk_read (struct nbdkit_next_ops *next_ops, void *nxdata,
           uint64_t blknum, uint8_t *block, int *err)
 {
   off_t offset = blknum * BLKSIZE;
-  enum bm_entry state = blk_get_bitmap_entry (blknum);
+  enum bm_entry state = bitmap_get_blk (&bm, blknum, BLOCK_NOT_CACHED);
 
   nbdkit_debug ("cache: blk_read block %" PRIu64 " (offset
%" PRIu64 ") is %s",
                 blknum, (uint64_t) offset,
@@ -326,7 +275,7 @@ blk_writethrough (struct nbdkit_next_ops *next_ops, void
*nxdata,
   if (next_ops->pwrite (nxdata, block, BLKSIZE, offset, flags, err) == -1)
     return -1;
 
-  blk_set_bitmap_entry (blknum, BLOCK_CLEAN);
+  bitmap_set_blk (&bm, blknum, BLOCK_CLEAN);
 
   return 0;
 }
@@ -354,7 +303,7 @@ blk_writeback (struct nbdkit_next_ops *next_ops, void
*nxdata,
     nbdkit_error ("pwrite: %m");
     return -1;
   }
-  blk_set_bitmap_entry (blknum, BLOCK_DIRTY);
+  bitmap_set_blk (&bm, blknum, BLOCK_DIRTY);
 
   return 0;
 }
@@ -509,7 +458,6 @@ cache_flush (struct nbdkit_next_ops *next_ops, void *nxdata,
void *handle,
              uint32_t flags, int *err)
 {
   uint8_t *block = NULL;
-  uint64_t i, j;
   uint64_t blknum;
   enum bm_entry state;
   unsigned errors = 0;
@@ -524,36 +472,28 @@ cache_flush (struct nbdkit_next_ops *next_ops, void
*nxdata, void *handle,
    * underlying storage.
    */
   assert (!flags);
-  for (i = 0; i < bm_size; ++i) {
-    if (bitmap[i] != 0) {
-      /* The bitmap stores information about 4 blocks per byte,
-       * therefore ...
-       */
-      for (j = 0; j < 4; ++j) {
-        blknum = i*4+j;
-        state = blk_get_bitmap_entry (blknum);
-        if (state == BLOCK_DIRTY) {
-          /* Lazily allocate the bounce buffer. */
-          if (!block) {
-            block = malloc (BLKSIZE);
-            if (block == NULL) {
-              *err = errno;
-              nbdkit_error ("malloc: %m");
-              return -1;
-            }
-          }
-          /* Perform a read + writethrough which will read from the
-           * cache and write it through to the underlying storage.
-           */
-          if (blk_read (next_ops, nxdata, blknum, block,
-                        errors ? &tmp : err) == -1 ||
-              blk_writethrough (next_ops, nxdata, blknum, block, 0,
-                                errors ? &tmp : err) == -1) {
-            nbdkit_error ("cache: flush of block %" PRIu64 "
failed", blknum);
-            errors++;
-          }
+  bitmap_for (&bm, blknum) {
+    state = bitmap_get_blk (&bm, blknum, BLOCK_NOT_CACHED);
+    if (state == BLOCK_DIRTY) {
+      /* Lazily allocate the bounce buffer. */
+      if (!block) {
+        block = malloc (BLKSIZE);
+        if (block == NULL) {
+          *err = errno;
+          nbdkit_error ("malloc: %m");
+          return -1;
         }
       }
+      /* Perform a read + writethrough which will read from the
+       * cache and write it through to the underlying storage.
+       */
+      if (blk_read (next_ops, nxdata, blknum, block,
+                    errors ? &tmp : err) == -1 ||
+          blk_writethrough (next_ops, nxdata, blknum, block, 0,
+                            errors ? &tmp : err) == -1) {
+        nbdkit_error ("cache: flush of block %" PRIu64 "
failed", blknum);
+        errors++;
+      }
     }
   }
 
diff --git a/filters/cow/cow.c b/filters/cow/cow.c
index c3833e1..ba98b4f 100644
--- a/filters/cow/cow.c
+++ b/filters/cow/cow.c
@@ -89,7 +89,7 @@
 
 #include <nbdkit-filter.h>
 
-#include "rounding.h"
+#include "bitmap.h"
 
 #ifndef HAVE_FDATASYNC
 #define fdatasync fsync
@@ -106,11 +106,8 @@
 /* The temporary overlay. */
 static int fd = -1;
 
-/* Bitmap.  Bit 1 = allocated, 0 = hole. */
-static uint8_t *bitmap;
-
-/* Size of the bitmap in bytes. */
-static size_t bm_size;
+/* Bitmap.  Bit = 1 => allocated, 0 => hole. */
+static struct bitmap bm;
 
 static void
 cow_load (void)
@@ -119,6 +116,8 @@ cow_load (void)
   size_t len;
   char *template;
 
+  bitmap_init (&bm, BLKSIZE, 1 /* bits per block */);
+
   tmpdir = getenv ("TMPDIR");
   if (!tmpdir)
     tmpdir = LARGE_TMPDIR;
@@ -148,6 +147,8 @@ cow_unload (void)
 {
   if (fd >= 0)
     close (fd);
+
+  bitmap_free (&bm);
 }
 
 static void *
@@ -169,28 +170,8 @@ cow_open (nbdkit_next_open *next, void *nxdata, int
readonly)
 static int
 blk_set_size (uint64_t new_size)
 {
-  uint8_t *new_bm;
-  const size_t old_bm_size = bm_size;
-  uint64_t new_bm_size_u64 = DIV_ROUND_UP (new_size, BLKSIZE*8);
-  size_t new_bm_size;
-
-  if (new_bm_size_u64 > SIZE_MAX) {
-    nbdkit_error ("bitmap too large for this architecture");
+  if (bitmap_resize (&bm, new_size) == -1)
     return -1;
-  }
-  new_bm_size = (size_t) new_bm_size_u64;
-
-  new_bm = realloc (bitmap, new_bm_size);
-  if (new_bm == NULL) {
-    nbdkit_error ("realloc: %m");
-    return -1;
-  }
-  bitmap = new_bm;
-  bm_size = new_bm_size;
-  if (old_bm_size < new_bm_size)
-    memset (&bitmap[old_bm_size], 0, new_bm_size-old_bm_size);
-
-  nbdkit_debug ("cow: bitmap resized to %zu bytes", new_bm_size);
 
   if (ftruncate (fd, new_size) == -1) {
     nbdkit_error ("ftruncate: %m");
@@ -263,30 +244,14 @@ cow_can_fua (struct nbdkit_next_ops *next_ops, void
*nxdata, void *handle)
 static bool
 blk_is_allocated (uint64_t blknum)
 {
-  uint64_t bm_offset = blknum / 8;
-  uint64_t bm_bit = blknum % 8;
-
-  if (bm_offset >= bm_size) {
-    nbdkit_debug ("blk_is_allocated: block number is out of range");
-    return false;
-  }
-
-  return bitmap[bm_offset] & (1 << bm_bit);
+  return bitmap_get_blk (&bm, blknum, false);
 }
 
 /* Mark a block as allocated. */
 static void
 blk_set_allocated (uint64_t blknum)
 {
-  uint64_t bm_offset = blknum / 8;
-  uint64_t bm_bit = blknum % 8;
-
-  if (bm_offset >= bm_size) {
-    nbdkit_debug ("blk_set_allocated: block number is out of range");
-    return;
-  }
-
-  bitmap[bm_offset] |= 1 << bm_bit;
+  bitmap_set_blk (&bm, blknum, true);
 }
 
 /* These are the block operations.  They always read or write a single
@@ -333,9 +298,7 @@ blk_write (uint64_t blknum, const uint8_t *block, int *err)
   return 0;
 }
 
-static int
-cow_flush (struct nbdkit_next_ops *next_ops, void *nxdata, void *handle,
-           uint32_t flags, int *err);
+static int cow_flush (struct nbdkit_next_ops *next_ops, void *nxdata, void
*handle, uint32_t flags, int *err);
 
 /* Read data. */
 static int
diff --git a/common/bitmap/Makefile.am b/common/bitmap/Makefile.am
new file mode 100644
index 0000000..cbd82bd
--- /dev/null
+++ b/common/bitmap/Makefile.am
@@ -0,0 +1,44 @@
+# 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.
+
+include $(top_srcdir)/common-rules.mk
+
+noinst_LTLIBRARIES = libbitmap.la
+
+libbitmap_la_SOURCES = \
+        bitmap.c \
+        bitmap.h
+libbitmap_la_CPPFLAGS = \
+	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/common/include
+libbitmap_la_CFLAGS = \
+        $(WARNINGS_CFLAGS)
diff --git a/filters/cache/Makefile.am b/filters/cache/Makefile.am
index 827ff17..89f4396 100644
--- a/filters/cache/Makefile.am
+++ b/filters/cache/Makefile.am
@@ -42,11 +42,14 @@ nbdkit_cache_filter_la_SOURCES = \
 
 nbdkit_cache_filter_la_CPPFLAGS = \
 	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/common/bitmap \
 	-I$(top_srcdir)/common/include
 nbdkit_cache_filter_la_CFLAGS = \
 	$(WARNINGS_CFLAGS)
 nbdkit_cache_filter_la_LDFLAGS = \
 	-module -avoid-version -shared
+nbdkit_cache_filter_la_LIBADD = \
+	$(top_builddir)/common/bitmap/libbitmap.la
 
 if HAVE_POD
 
diff --git a/filters/cow/Makefile.am b/filters/cow/Makefile.am
index c81b41c..5c3ae2e 100644
--- a/filters/cow/Makefile.am
+++ b/filters/cow/Makefile.am
@@ -42,11 +42,14 @@ nbdkit_cow_filter_la_SOURCES = \
 
 nbdkit_cow_filter_la_CPPFLAGS = \
 	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/common/bitmap \
 	-I$(top_srcdir)/common/include
 nbdkit_cow_filter_la_CFLAGS = \
 	$(WARNINGS_CFLAGS)
 nbdkit_cow_filter_la_LDFLAGS = \
 	-module -avoid-version -shared
+nbdkit_cow_filter_la_LIBADD = \
+	$(top_builddir)/common/bitmap/libbitmap.la
 
 if HAVE_POD
 
-- 
2.19.0.rc0

Eric Blake

2018-Dec-03 22:41 UTC

head link

Re: [Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

On 12/3/18 4:13 PM, Richard W.M. Jones wrote:> The cow and cache filters both use a bitmap mapping virtual disk
> blocks to status stored in the bitmap.  The implementation of the
> bitmaps is very similar because one was derived from the other when
> the filters were implemented.
> 
> The main difference is the cow filter uses a simple bitmap (one bit
> per block), whereas the cache filter uses two bits per block.
> 
> This commit abstracts the bitmap structure into a common library.  The
> block size and bits per block are configurable.
> 
> This commit is refactoring, except:
> 
> - it cures a memory leak (bitmap was not being freed),
> 
> - in the cache filter we now mask out existing bits when updating the
>    bitmap.
> ---
> +
> +/* This is the bitmap structure. */
> +struct bitmap {
> +  unsigned blksize;             /* Block size. */
> +  unsigned bpb;                 /* Bits per block (1, 2, 4, 8 only). */
> +  /* bpb = 1 << bitshift   ibpb = 8/bpb
> +     1          0          8
> +     2          1          4
> +     4          2          2
> +     8          3          1
> +  */
> +  unsigned bitshift, ibpb;
As written, you've consumed 16 bytes in the struct by this point.  If 
cache line pressure is a concern, you could make these three values 
unsigned char, and only consume 8 bytes (1 padding) before the next 
field member.
> +
> +  uint8_t *bitmap;              /* The bitmap. */
> +  size_t size;                  /* Size of bitmap in bytes. */
> +};
But even without that compression, a 64-bit architecture should fit the 
struct in 32 bytes, which means cache line pressure may not be a concern.
> +/* This macro calculates the byte offset in the bitmap and which
> + * bit/mask we are addressing within that byte.
> + *
> + * bpb     blk_offset         blk_bit          mask
> + * 1       blk >> 3           0,1,2,...,7      any single bit
> + * 2       blk >> 2           0, 2, 4 or 6     0x3, 0xc, 0x30 or
0xc0
> + * 4       blk >> 1           0 or 4           0xf, 0xf0
> + * 8       blk >> 0           always 0         always 0xff
> + */
> +#define BITMAP_OFFSET_BIT_MASK(bm, blk)                         \
> +  uint64_t blk_offset = (blk) >> (3 - (bm)->bitshift);          \
> +  unsigned blk_bit = (bm)->bpb * ((blk) & ((bm)->ibpb - 1));   
\
> +  unsigned mask = ((1 << (bm)->bpb) - 1) << blk_bit
Nice.  Maybe not the easiest indirection when reading a given function 
in isolation (macros don't very often declare variables), but does 
reduce the duplication and chance for errors.

ACK

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Richard W.M. Jones

2018-Dec-03 22:42 UTC

head link

Re: [Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

On Mon, Dec 03, 2018 at 10:13:28PM +0000, Richard W.M. Jones
wrote:> +/* Iterate over blocks represented in the bitmap. */
> +#define bitmap_for(bm, /* uint64_t */ blknum)                           \
> +  for ((blknum) = 0; (blknum) < (bm)->size * (8 / (bm)->bpb);
++(blknum))                                                ^^^^^^^^^^^^^^^

should be (bm)->ibpb.  I've made the change locally.

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

Possibly Parallel Threads

Search for more possibly parallel threads

Libguestfs - Dec 2018 - [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

[Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

[Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

Re: [Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

Re: [Libguestfs] [PATCH nbdkit v3] common: Move shared bitmap code to a common library.

Possibly Parallel Threads