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

Richard W.M. Jones rjones at redhat.com
Fri Jan 4 09:48:04 UTC 2019


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




More information about the Libguestfs mailing list