3 p.m.
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