[Libguestfs] [PATCH nbdkit v5 1/3] cache: Implement LRU structure.

Implement a simple LRU structure for the cache filter using bitmaps. --- filters/cache/lru.h | 54 ++++++++++++++ filters/cache/blk.c | 12 +++ filters/cache/lru.c | 151 ++++++++++++++++++++++++++++++++++++++ filters/cache/Makefile.am | 2 + 4 files changed, 219 insertions(+) diff --git a/filters/cache/lru.h b/filters/cache/lru.h new file mode 100644 index 0000000..4faefcd --- /dev/null +++ b/filters/cache/lru.h @@ -0,0 +1,54 @@ +/* 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_LRU_H +#define NBDKIT_LRU_H + +#include <stdbool.h> + +/* Initialize LRU. */ +extern void lru_init (void); + +/* Free the LRU. */ +extern void lru_free (void); + +/* Notify LRU that the virtual size has changed. */ +extern int lru_set_size (uint64_t new_size); + +/* Mark a block as recently accessed in the LRU structure. */ +extern void lru_set_recently_accessed (uint64_t blknum); + +/* Check if a block has been recently accessed. */ +extern bool lru_has_been_recently_accessed (uint64_t blknum); + +#endif /* NBDKIT_LRU_H */ diff --git a/filters/cache/blk.c b/filters/cache/blk.c index 4000276..b256446 100644 --- a/filters/cache/blk.c +++ b/filters/cache/blk.c @@ -53,6 +53,7 @@ #include "cache.h" #include "blk.h" +#include "lru.h" /* The cache. */ static int fd = -1; @@ -80,6 +81,8 @@ blk_init (void) size_t len; char *template; + lru_init (); + bitmap_init (&bm, BLKSIZE, 2 /* bits per block */); tmpdir = getenv ("TMPDIR"); @@ -115,6 +118,8 @@ blk_free (void) close (fd); bitmap_free (&bm); + + lru_free (); } int @@ -128,6 +133,9 @@ blk_set_size (uint64_t new_size) return -1; } + if (lru_set_size (new_size) == -1) + return -1; + return 0; } @@ -163,6 +171,7 @@ blk_read (struct nbdkit_next_ops *next_ops, void *nxdata, return -1; } bitmap_set_blk (&bm, blknum, BLOCK_CLEAN); + lru_set_recently_accessed (blknum); } return 0; } @@ -172,6 +181,7 @@ blk_read (struct nbdkit_next_ops *next_ops, void *nxdata, nbdkit_error ("pread: %m"); return -1; } + lru_set_recently_accessed (blknum); return 0; } } @@ -196,6 +206,7 @@ blk_writethrough (struct nbdkit_next_ops *next_ops, void *nxdata, return -1; bitmap_set_blk (&bm, blknum, BLOCK_CLEAN); + lru_set_recently_accessed (blknum); return 0; } @@ -222,6 +233,7 @@ blk_write (struct nbdkit_next_ops *next_ops, void *nxdata, return -1; } bitmap_set_blk (&bm, blknum, BLOCK_DIRTY); + lru_set_recently_accessed (blknum); return 0; } diff --git a/filters/cache/lru.c b/filters/cache/lru.c new file mode 100644 index 0000000..c828968 --- /dev/null +++ b/filters/cache/lru.c @@ -0,0 +1,151 @@ +/* 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. + */ + +/* These are the block operations. They always read or write a single + * whole block of size ‘blksize’. + */ + +#include <config.h> + +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <stdbool.h> +#include <inttypes.h> + +#include <nbdkit-filter.h> + +#include "bitmap.h" + +#include "cache.h" +#include "blk.h" +#include "lru.h" + +#define MAX(a, b) ((a) > (b) ? (a) : (b)) + +/* LRU bitmaps. These bitmaps implement a simple, fast LRU structure. + * + * bm[0] bm[1] blocks not in either bitmap + * ┌─────────┬──────────────────┬─────────────────────────────┐ + * │ │ │ │ + * └─────────┴──────────────────┴─────────────────────────────┘ + * ↑ c1 bits set + * c0 bits set + * + * The LRU structure keeps track of the [approx] last N distinct + * blocks which have been most recently accessed. It can answer in + * O(1) time the question: “Is a particular block in or not in the N + * distinct blocks most recently accessed?” + * + * To do this we keep two bitmaps. + * + * When a new block is accessed, we set the corresponding bit in bm[0] + * and increment c0 (c0 counts the number of bits set in bm[0]). If + * c0 == N/2 then we swap the two bitmaps, clear bm[0], and reset c0 + * to 0. + * + * To check if a block has been accessed within the previous N + * distinct accesses, we simply have to check both bitmaps. If it is + * not in either bitmap, then it's old and a candidate to be + * reclaimed. + * + * You'll note that in fact we only keep track of between N/2 and N + * recently accessed blocks. We could make the estimate more accurate + * by having more bitmaps, but as this is only a heuristic we choose + * to keep the implementation simple and memory usage low instead. + */ +static struct bitmap bm[2]; +static unsigned c0 = 0, c1 = 0; +static unsigned N = 100; + +void +lru_init (void) +{ + bitmap_init (&bm[0], BLKSIZE, 1 /* bits per block */); + bitmap_init (&bm[1], BLKSIZE, 1 /* bits per block */); +} + +void +lru_free (void) +{ + bitmap_free (&bm[0]); + bitmap_free (&bm[1]); +} + +int +lru_set_size (uint64_t new_size) +{ + if (bitmap_resize (&bm[0], new_size) == -1) + return -1; + if (bitmap_resize (&bm[1], new_size) == -1) + return -1; + + /* XXX Choose this better. */ + N = MAX (new_size / BLKSIZE / 4, 100); + + return 0; +} + +void +lru_set_recently_accessed (uint64_t blknum) +{ + /* If the block is already set in the first bitmap, don't need to do + * anything. + */ + if (bitmap_get_blk (&bm[0], blknum, false)) + return; + + bitmap_set_blk (&bm[0], blknum, true); + c0++; + + /* If we've reached N/2 then we need to swap over the bitmaps. */ + if (c0 >= N/2) { + struct bitmap tmp; + + tmp = bm[0]; + bm[0] = bm[1]; + bm[1] = tmp; + c1 = c0; + + bitmap_clear (&bm[0]); + c0 = 0; + } +} + +bool +lru_has_been_recently_accessed (uint64_t blknum) +{ + return + bitmap_get_blk (&bm[0], blknum, false) || + bitmap_get_blk (&bm[1], blknum, false); +} diff --git a/filters/cache/Makefile.am b/filters/cache/Makefile.am index 3a542af..1620fa1 100644 --- a/filters/cache/Makefile.am +++ b/filters/cache/Makefile.am @@ -41,6 +41,8 @@ nbdkit_cache_filter_la_SOURCES = \ blk.h \ cache.c \ cache.h \ + lru.c \ + lru.h \ $(top_srcdir)/include/nbdkit-filter.h nbdkit_cache_filter_la_CPPFLAGS = \ -- 2.19.2