[Libguestfs] [PATCH nbdkit v2 3/4] cache: Implement LRU structure.
Eric Blake
eblake at redhat.com
Thu Jan 3 03:04:43 UTC 2019
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libguestfs/attachments/20190102/0c5584e9/attachment.sig>
More information about the Libguestfs
mailing list