filters/cache/reclaim.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 #include <config.h>
  34
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <stdint.h>
  38 #include <stdbool.h>
  39 #include <inttypes.h>
  40 #include <string.h>
  41 #include <unistd.h>
  42 #include <fcntl.h>
  43 #include <sys/types.h>
  44 #include <sys/stat.h>
  45
  46 #include <nbdkit-filter.h>
  47
  48 #include "bitmap.h"
  49
  50 #include "cache.h"
  51 #include "reclaim.h"
  52 #include "lru.h"
  53
  54 #ifndef HAVE_CACHE_RECLAIM
  55
  56 void
  57 reclaim (int fd, struct bitmap *bm)
  58 {
  59   /* nothing */
  60 }
  61
  62 #else /* HAVE_CACHE_RECLAIM */
  63
  64 /* If we are currently reclaiming blocks from the cache.
  65  *
  66  * The state machine starts in the NOT_RECLAIMING state.  When the
  67  * size of the cache exceeds the high threshold, we move to
  68  * RECLAIMING_LRU.  Once we have exhausted all LRU blocks, we move to
  69  * RECLAIMING_ANY (reclaiming any blocks).
  70  *
  71  * If at any time the size of the cache goes below the low threshold
  72  * we move back to the NOT_RECLAIMING state.
  73  *
  74  * A possible future enhancement is to add an extra state between LRU
  75  * and ANY which reclaims blocks from lru.c:bm[1].
  76  *
  77  * reclaim_blk is the last block that we looked at.
  78  */
  79 enum reclaim_state {
  80   NOT_RECLAIMING = 0,
  81   RECLAIMING_LRU = 1,
  82   RECLAIMING_ANY = 2,
  83 };
  84
  85 static enum reclaim_state reclaiming = NOT_RECLAIMING;
  86 static int64_t reclaim_blk;
  87
  88 static void reclaim_one (int fd, struct bitmap *bm);
  89 static void reclaim_lru (int fd, struct bitmap *bm);
  90 static void reclaim_any (int fd, struct bitmap *bm);
  91 static void reclaim_block (int fd, struct bitmap *bm);
  92
  93 void
  94 reclaim (int fd, struct bitmap *bm)
  95 {
  96   struct stat statbuf;
  97   uint64_t cache_allocated;
  98
  99   /* If the user didn't set cache-max-size, do nothing. */
 100   if (max_size == -1) return;
 101
 102   /* Check the allocated size of the cache. */
 103   if (fstat (fd, &statbuf) == -1) {
 104     nbdkit_debug ("cache: fstat: %m");
 105     return;
 106   }
 107   cache_allocated = statbuf.st_blocks * UINT64_C (512);
 108
 109   if (reclaiming) {
 110     /* Keep reclaiming until the cache size drops below the low threshold. */
 111     if (cache_allocated < max_size * lo_thresh / 100) {
 112       nbdkit_debug ("cache: stop reclaiming");
 113       reclaiming = NOT_RECLAIMING;
 114       return;
 115     }
 116   }
 117   else {
 118     if (cache_allocated < max_size * hi_thresh / 100)
 119       return;
 120
 121     /* Start reclaiming if the cache size goes over the high threshold. */
 122     nbdkit_debug ("cache: start reclaiming");
 123     reclaiming = RECLAIMING_LRU;
 124   }
 125
 126   /* Reclaim up to 2 cache blocks. */
 127   reclaim_one (fd, bm);
 128   reclaim_one (fd, bm);
 129 }
 130
 131 /* Reclaim a single cache block. */
 132 static void
 133 reclaim_one (int fd, struct bitmap *bm)
 134 {
 135   assert (reclaiming);
 136
 137   if (reclaiming == RECLAIMING_LRU)
 138     reclaim_lru (fd, bm);
 139   else
 140     reclaim_any (fd, bm);
 141 }
 142
 143 static void
 144 reclaim_lru (int fd, struct bitmap *bm)
 145 {
 146   int64_t old_reclaim_blk;
 147
 148   /* Find the next block in the cache. */
 149   reclaim_blk = bitmap_next (bm, reclaim_blk+1);
 150   old_reclaim_blk = reclaim_blk;
 151
 152   /* Search for an LRU block after this one. */
 153   do {
 154     if (! lru_has_been_recently_accessed (reclaim_blk)) {
 155       reclaim_block (fd, bm);
 156       return;
 157     }
 158
 159     reclaim_blk = bitmap_next (bm, reclaim_blk+1);
 160     if (reclaim_blk == -1)    /* wrap around */
 161       reclaim_blk = bitmap_next (bm, 0);
 162   } while (reclaim_blk >= 0 && old_reclaim_blk != reclaim_blk);
 163
 164   if (old_reclaim_blk == reclaim_blk) {
 165     /* Run out of LRU blocks, so start reclaiming any block in the cache. */
 166     nbdkit_debug ("cache: reclaiming any blocks");
 167     reclaiming = RECLAIMING_ANY;
 168     reclaim_any (fd, bm);
 169   }
 170 }
 171
 172 static void
 173 reclaim_any (int fd, struct bitmap *bm)
 174 {
 175   /* Find the next block in the cache. */
 176   reclaim_blk = bitmap_next (bm, reclaim_blk+1);
 177   if (reclaim_blk == -1)        /* wrap around */
 178     reclaim_blk = bitmap_next (bm, 0);
 179
 180   reclaim_block (fd, bm);
 181 }
 182
 183 static void
 184 reclaim_block (int fd, struct bitmap *bm)
 185 {
 186   if (reclaim_blk == -1) {
 187     nbdkit_debug ("cache: run out of blocks to reclaim!");
 188     return;
 189   }
 190
 191   nbdkit_debug ("cache: reclaiming block %" PRIu64, reclaim_blk);
 192 #ifdef FALLOC_FL_PUNCH_HOLE
 193   if (fallocate (fd, FALLOC_FL_PUNCH_HOLE|FALLOC_FL_KEEP_SIZE,
 194                  reclaim_blk * blksize, blksize) == -1) {
 195     nbdkit_error ("cache: reclaiming cache blocks: "
 196                   "fallocate: FALLOC_FL_PUNCH_HOLE: %m");
 197     return;
 198   }
 199 #else
 200 #error "no implementation for punching holes"
 201 #endif
 202
 203   bitmap_set_blk (bm, reclaim_blk, 0);
 204 }
 205
 206 #endif /* HAVE_CACHE_RECLAIM */