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
_______________________________________________
Libguestfs mailing list
Libguestfs@redhat.com
https://www.redhat.com/mailman/listinfo/libguestfs
