search for: bitmap_next

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...

...aiming); > + > + if (reclaiming == RECLAIMING_LRU) > + reclaim_lru (); > + else > + reclaim_any (); > +} > + > +static void > +reclaim_lru (void) > +{ > + uint64_t old_reclaim_blk; > + > + /* Find the next block in the cache. */ > + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); > + old_reclaim_blk = reclaim_blk; > + > + /* Search for an LRU block after this one. */ > + do { > + if (! lru_has_been_recently_accessed (reclaim_blk)) { > + reclaim_block (); > + return; > + } > + > + reclaim_blk = bit...

...iming == RECLAIMING_LRU) > + reclaim_lru (fd, bm); > + else > + reclaim_any (fd, bm); > +} > + > +static void > +reclaim_lru (int fd, struct bitmap *bm) > +{ > + uint64_t old_reclaim_blk; > + > + /* Find the next block in the cache. */ > + reclaim_blk = bitmap_next (bm, reclaim_blk+1); > + old_reclaim_blk = reclaim_blk; > + > + /* Search for an LRU block after this one. */ > + do { > + if (! lru_has_been_recently_accessed (reclaim_blk)) { > + reclaim_block (fd, bm); > + return; > + } > + > + reclaim_blk = bi...

These are essentially identical to what was previously posted as patches 6/9 through 9/9 here: https://www.redhat.com/archives/libguestfs/2018-December/msg00145.html except that it has been rebased onto the current git master and retested thoroughly. Rich.

v3 was broken by a bad rebase, so let's forget about that one. Compared to v2: - Patch 1 is the same except for a minor comment change. - Patch 2 splits the reclaim code into a separate file (filters/cache/reclaim.c) - Addressed Eric's comments from his review of v2. - Retested on Linux and FreeBSD.

...le cache block. */ +static void +reclaim_one (void) +{ + assert (reclaiming); + + if (reclaiming == RECLAIMING_LRU) + reclaim_lru (); + else + reclaim_any (); +} + +static void +reclaim_lru (void) +{ + uint64_t old_reclaim_blk; + + /* Find the next block in the cache. */ + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + old_reclaim_blk = reclaim_blk; + + /* Search for an LRU block after this one. */ + do { + if (! lru_has_been_recently_accessed (reclaim_blk)) { + reclaim_block (); + return; + } + + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + if (reclai...

...le cache block. */ +static void +reclaim_one (void) +{ + assert (reclaiming); + + if (reclaiming == RECLAIMING_LRU) + reclaim_lru (); + else + reclaim_any (); +} + +static void +reclaim_lru (void) +{ + uint64_t old_reclaim_blk; + + /* Find the next block in the cache. */ + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + old_reclaim_blk = reclaim_blk; + + /* Search for an LRU block after this one. */ + do { + if (! lru_has_been_recently_accessed (reclaim_blk)) { + reclaim_block (); + return; + } + + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + if (reclai...

...le cache block. */ +static void +reclaim_one (void) +{ + assert (reclaiming); + + if (reclaiming == RECLAIMING_LRU) + reclaim_lru (); + else + reclaim_any (); +} + +static void +reclaim_lru (void) +{ + uint64_t old_reclaim_blk; + + /* Find the next block in the cache. */ + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + old_reclaim_blk = reclaim_blk; + + /* Search for an LRU block after this one. */ + do { + if (! lru_has_been_recently_accessed (reclaim_blk)) { + reclaim_block (); + return; + } + + reclaim_blk = bitmap_next (&bm, reclaim_blk+1); + if (reclai...

...struct bitmap *bm) +{ + assert (reclaiming); + + if (reclaiming == RECLAIMING_LRU) + reclaim_lru (fd, bm); + else + reclaim_any (fd, bm); +} + +static void +reclaim_lru (int fd, struct bitmap *bm) +{ + uint64_t old_reclaim_blk; + + /* Find the next block in the cache. */ + reclaim_blk = bitmap_next (bm, reclaim_blk+1); + old_reclaim_blk = reclaim_blk; + + /* Search for an LRU block after this one. */ + do { + if (! lru_has_been_recently_accessed (reclaim_blk)) { + reclaim_block (fd, bm); + return; + } + + reclaim_blk = bitmap_next (bm, reclaim_blk+1); + if (reclaim_bl...

...dkit-plugin.h>. [4/9] cache: Split out the block/bitmap code into - All of the above patches are pretty uncontroversial and ready for review and upstreaming. [5/9] cache: Allow this filter to serve requests in - Probably needs more testing, but should be OK too. [6/9] common/bitmap: Add bitmap_next function and tests. [7/9] common/bitmap: Add bitmap_clear function. [8/9] cache: Implement LRU structure. [9/9] cache: Implement cache-max-size and method of - Needs much better testing, and maybe even review of the design. Rich.

Patch 1 is the same as last time, except for a minor comment fix. Patch 2 should address everything that Eric mentioned in his review, and has been retested. Rich.

...struct bitmap *bm) +{ + assert (reclaiming); + + if (reclaiming == RECLAIMING_LRU) + reclaim_lru (fd, bm); + else + reclaim_any (fd, bm); +} + +static void +reclaim_lru (int fd, struct bitmap *bm) +{ + uint64_t old_reclaim_blk; + + /* Find the next block in the cache. */ + reclaim_blk = bitmap_next (bm, reclaim_blk+1); + old_reclaim_blk = reclaim_blk; + + /* Search for an LRU block after this one. */ + do { + if (! lru_has_been_recently_accessed (reclaim_blk)) { + reclaim_block (fd, bm); + return; + } + + reclaim_blk = bitmap_next (bm, reclaim_blk+1); + if (reclaim_bl...

Should we use attribute((nonnull)) at all? There's a very interesting history of this in libvirt -- try looking at commit eefb881 plus the commits referencing eefb881 -- but it does seem to work for me using recent GCC and Clang. I only did a few functions because annotating them gets old quickly... Rich.

v4: https://www.redhat.com/archives/libguestfs/2019-January/msg00032.html v5: - Now we set the block size at run time. I'd like to say that I was able to test this change, but unfortunately I couldn't find any easy way to create a filesystem on x86-64 with a block size > 4K. Ext4 doesn't support it at all, and XFS doesn't support block size > page size (and I

...struct bitmap *bm, uint64_t offset, unsigned v) { return bitmap_set_blk (bm, offset / bm->blksize, v); @@ -177,6 +178,7 @@ bitmap_set (const struct bitmap *bm, uint64_t offset, unsigned v) * 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); +extern int64_t bitmap_next (const struct bitmap *bm, uint64_t blk) + __attribute__((__nonnull__ (1))); #endif /* NBDKIT_BITMAP_H */ diff --git a/common/include/iszero.h b/common/include/iszero.h index 7a54f0a..efe0762 100644 --- a/common/include/iszero....

v1 was here: https://www.redhat.com/archives/libguestfs/2019-January/msg00008.html In v2 I have provided two patches: The first patch extends attribute((nonnull)) to most internal functions, but not to the external API. The second patch uses a macro so that attribute((format)) is only used in the public API on GCC or Clang. At least in theory these headers could be used by a C compiler which