Re: [Libguestfs] [PATCH nbdkit v2 3/4] cache: Implement LRU structure.

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

+/* 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.

+ * + * 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;

+ +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); +}