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

This is exactly the same as v1:

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

except that it now frees the bitmap on unload (which the old code did
not - there was always a memory leak).

Rich.

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.  However it also cures a memory leak
(bitmap was not being freed).
---
 Makefile.am               |   1 +
 common/bitmap/Makefile.am |  44 ++++++++++++
 common/bitmap/bitmap.c    |  74 ++++++++++++++++++++
 common/bitmap/bitmap.h    | 141 ++++++++++++++++++++++++++++++++++++++
 configure.ac              |   1 +
 filters/cache/Makefile.am |   3 +
 filters/cache/cache.c     | 122 +++++++++------------------------
 filters/cow/Makefile.am   |   3 +
 filters/cow/cow.c         |  59 +++-------------
 9 files changed, 309 insertions(+), 139 deletions(-)

diff --git a/Makefile.am b/Makefile.am
index 40ef0bd..2b5d80d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -66,6 +66,7 @@ SUBDIRS = \
 
 if HAVE_PLUGINS
 SUBDIRS += \
+	common/bitmap \
 	common/regions \
 	common/sparse \
 	plugins \
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/common/bitmap/bitmap.c b/common/bitmap/bitmap.c
new file mode 100644
index 0000000..35d584d
--- /dev/null
+++ b/common/bitmap/bitmap.c
@@ -0,0 +1,74 @@
+/* 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 * 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/common/bitmap/bitmap.h b/common/bitmap/bitmap.h
new file mode 100644
index 0000000..2e1dd19
--- /dev/null
+++ b/common/bitmap/bitmap.h
@@ -0,0 +1,141 @@
+/* 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). */
+
+  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));
+  assert (bpb >= 1);
+  assert (bpb <= 8);
+  assert (is_power_of_2 (bpb)); /* Only 1, 2, 4, 8 allowed. */
+
+  bm->blksize = blksize;
+  bm->bpb = bpb;
+
+  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);
+
+/* 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_)
+{
+  uint64_t blk_offset = blk / (8 / bm->bpb);
+  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));
+  unsigned mask = (1 << bm->bpb) - 1;
+
+  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)) >>
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)
+{
+  uint64_t blk_offset = blk / (8 / bm->bpb);
+  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));
+
+  if (blk_offset >= bm->size) {
+    nbdkit_debug ("bitmap_set: block number is out of range");
+    return;
+  }
+
+  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/configure.ac b/configure.ac
index 39a7e6d..a3e4457 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/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/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/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
 
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
-- 
2.19.0.rc0

On 12/2/18 10:33 AM, 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.  However it also cures a memory leak
> (bitmap was not being freed).
> ---
>   Makefile.am               |   1 +
>   common/bitmap/Makefile.am |  44 ++++++++++++
>   common/bitmap/bitmap.c    |  74 ++++++++++++++++++++
>   common/bitmap/bitmap.h    | 141 ++++++++++++++++++++++++++++++++++++++
With git's orderfile directive, you can arrange to have all Makefile.am 
appear before all .h before all .c, to make patches a little easier to 
follow logically (what gets built, what interfaces does it need, and how 
is it implemented).  'git config diff.orderFile /path/to/file'; see 
qemu's scripts/git.orderfile for an example.

> +
> +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 * 8 /
bm->bpb);
Can the computation of bm->blksize * 8 overflow? (blksize is 32-bit 
unsigned; did initialization clamp block size to less than 512M?). But 
appears to be unchanged in the refactor, and at most a pre-existing 
issue.  If so, write bm->blksize * UINT64_C(8) / bm->bpb or similar.

> diff --git a/common/bitmap/bitmap.h b/common/bitmap/bitmap.h
> new file mode 100644
> index 0000000..2e1dd19
> --- /dev/null
> +++ b/common/bitmap/bitmap.h
> +
> +/* This is the bitmap structure. */
> +struct bitmap {
> +  unsigned blksize;             /* Block size. */
> +  unsigned bpb;                 /* Bits per block (1, 2, 4, 8 only). */
> +
> +  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));
> +  assert (bpb >= 1);
> +  assert (bpb <= 8);
> +  assert (is_power_of_2 (bpb)); /* Only 1, 2, 4, 8 allowed. */
> +
> +  bm->blksize = blksize;
No validation that blksize is not too big for multiplying by 8 (for bpb 
of 1).
> +  bm->bpb = bpb;
> +
> +  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);
> +
> +/* 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_)
> +{
> +  uint64_t blk_offset = blk / (8 / bm->bpb);
> +  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));
Would using << and >> instead of / and % aid the compiler, since we
know
we have powers of 2 based on initialization, but the compiler might not 
see it locally?
> +/* 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)
> +{
> +  uint64_t blk_offset = blk / (8 / bm->bpb);
> +  unsigned blk_bit = bm->bpb * (blk % (8 / bm->bpb));
> +
> +  if (blk_offset >= bm->size) {
> +    nbdkit_debug ("bitmap_set: block number is out of range");
> +    return;
> +  }
> +
> +  bm->bitmap[blk_offset] |= v << blk_bit;
Do you want to mask out the existing bits first, or is this 
intentionally only a saturating set (where you can turn bits on but not 
off)?  Should there be a counterpart for clearing bits?
> +}
> +
> +/* 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)
For safety, you should probably:

for ((blknum) = 0; (blknum) < (bm)->size * (8 / (bm->bpb); ++(blknum))



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