On 1/1/19 8:33 AM, Richard W.M. Jones wrote:
--- filters/cache/lru.h | 54 ++++++++++++++ filters/cache/blk.c | 12 +++ filters/cache/lru.c | 150 ++++++++++++++++++++++++++++++++++++++ filters/cache/Makefile.am | 2 + 4 files changed, 218 insertions(+)
+++ b/filters/cache/lru.c @@ -0,0 +1,150 @@ +/* nbdkit + * Copyright (C) 2018 Red Hat Inc.
Always fun to see new files added near a new year boundary. Up to you if you want to add 2019.
+/* 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 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.
Are you incrementing c0 on every access, or just on accesses that flip a bit from 0 to 1? That is, if I access sector 0 repeatedly and nothing else (say 100 times), is c0 set to 100 or to just 1?
+ * + * 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.
Depending on how c0 is incremented, this is either the last previous N accesses (even if they were repeats of an already LRU block), or the last previously used N blocks (even if there were many more than N accesses). Both methods have their advantages (the former can be used to reduce memory usage to only the hot blocks, rather than always carrying a full N blocks in memory; the latter reduces the times the cache has to be repopulated).
+ * + * 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.
Seems reasonable enough.
+ */ +static struct bitmap bm[2]; +static unsigned c0 = 0, c1 = 0;
Static variables already start life zero-initialized.
+ +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;
And this implements the latter (the most recent N blocks accessed, not the most recent N accesses).
+ + 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); +}
Code matches the documented algorithm, and looks sane. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3226 Virtualization: qemu.org | libvirt.org