filters/cache/lru.c

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /* These are the block operations.  They always read or write a single
  34  * whole block of size ‘blksize’.
  35  */
  36
  37 #include <config.h>
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <stdint.h>
  42 #include <stdbool.h>
  43 #include <inttypes.h>
  44
  45 #include <nbdkit-filter.h>
  46
  47 #include "bitmap.h"
  48 #include "minmax.h"
  49
  50 #include "cache.h"
  51 #include "blk.h"
  52 #include "lru.h"
  53
  54 /* LRU bitmaps.  These bitmaps implement a simple, fast LRU structure.
  55  *
  56  *    bm[0]
  57  * ┌───────────────────────┐
  58  * │  X    XX   X   XXX    │ c0 bits set
  59  * └───────────────────────┘
  60  *    bm[1]
  61  * ┌───────────────────────┐
  62  * │   X    XX  X   X      │ c1 bits set
  63  * └───────────────────────┘
  64  *
  65  * The LRU structure keeps track of the [approx] last N distinct
  66  * blocks which have been most recently accessed.  It can answer in
  67  * O(1) time the question: “Is a particular block in or not in the N
  68  * distinct blocks most recently accessed?”
  69  *
  70  * To do this we keep two bitmaps.
  71  *
  72  * When a new block is accessed, we set the corresponding bit in bm[0]
  73  * and increment c0 (c0 counts the number of bits set in bm[0]).  If
  74  * c0 == N/2 then we move bm[1] <- bm[0], clear bm[0] and set c0 <- 0.
  75  *
  76  * To check if a block has been accessed within the previous N
  77  * distinct accesses, we simply have to check both bitmaps.  If it is
  78  * not in either bitmap, then it's old and a candidate to be
  79  * reclaimed.
  80  *
  81  * You'll note that in fact we only keep track of between N/2 and N
  82  * recently accessed blocks because the same block can appear in both
  83  * bitmaps.  bm[1] is a last chance to hold on to blocks which are
  84  * soon to be reclaimed.  We could make the estimate more accurate by
  85  * having more bitmaps, but as this is only a heuristic we choose to
  86  * keep the implementation simple and memory usage low instead.
  87  */
  88 static struct bitmap bm[2];
  89 static unsigned c0 = 0, c1 = 0;
  90 static unsigned N = 100;
  91
  92 void
  93 lru_init (void)
  94 {
  95   bitmap_init (&bm[0], blksize, 1 /* bits per block */);
  96   bitmap_init (&bm[1], blksize, 1 /* bits per block */);
  97 }
  98
  99 void
 100 lru_free (void)
 101 {
 102   bitmap_free (&bm[0]);
 103   bitmap_free (&bm[1]);
 104 }
 105
 106 int
 107 lru_set_size (uint64_t new_size)
 108 {
 109   if (bitmap_resize (&bm[0], new_size) == -1)
 110     return -1;
 111   if (bitmap_resize (&bm[1], new_size) == -1)
 112     return -1;
 113
 114   if (max_size != -1)
 115     /* Make the threshold about 1/4 the maximum size of the cache. */
 116     N = MAX (max_size / blksize / 4, 100);
 117   else
 118     N = MAX (new_size / blksize / 4, 100);
 119
 120   return 0;
 121 }
 122
 123 void
 124 lru_set_recently_accessed (uint64_t blknum)
 125 {
 126   /* If the block is already set in the first bitmap, don't need to do
 127    * anything.
 128    */
 129   if (bitmap_get_blk (&bm[0], blknum, false))
 130     return;
 131
 132   bitmap_set_blk (&bm[0], blknum, true);
 133   c0++;
 134
 135   /* If we've reached N/2 then we need to swap over the bitmaps.  Note
 136    * the purpose of swapping here is to ensure that we do not have to
 137    * copy the dynamically allocated bm->bitmap field (the pointers are
 138    * swapped instead).  The bm[0].bitmap field is immediately zeroed
 139    * after the swap.
 140    */
 141   if (c0 >= N/2) {
 142     struct bitmap tmp;
 143
 144     tmp = bm[0];
 145     bm[0] = bm[1];
 146     bm[1] = tmp;
 147     c1 = c0;
 148
 149     bitmap_clear (&bm[0]);
 150     c0 = 0;
 151   }
 152 }
 153
 154 bool
 155 lru_has_been_recently_accessed (uint64_t blknum)
 156 {
 157   return
 158     bitmap_get_blk (&bm[0], blknum, false) ||
 159     bitmap_get_blk (&bm[1], blknum, false);
 160 }