[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