4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
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.
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.
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
33 /* These are the block operations. They always read or write a single
34 * whole block of size ‘blksize’.
45 #include <nbdkit-filter.h>
54 /* LRU bitmaps. These bitmaps implement a simple, fast LRU structure.
57 * ┌───────────────────────┐
58 * │ X XX X XXX │ c0 bits set
59 * └───────────────────────┘
61 * ┌───────────────────────┐
62 * │ X XX X X │ c1 bits set
63 * └───────────────────────┘
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?”
70 * To do this we keep two bitmaps.
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.
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
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.
88 static struct bitmap bm
[2];
89 static unsigned c0
= 0, c1
= 0;
90 static unsigned N
= 100;
95 bitmap_init (&bm
[0], blksize
, 1 /* bits per block */);
96 bitmap_init (&bm
[1], blksize
, 1 /* bits per block */);
102 bitmap_free (&bm
[0]);
103 bitmap_free (&bm
[1]);
107 lru_set_size (uint64_t new_size
)
109 if (bitmap_resize (&bm
[0], new_size
) == -1)
111 if (bitmap_resize (&bm
[1], new_size
) == -1)
115 /* Make the threshold about 1/4 the maximum size of the cache. */
116 N
= MAX (max_size
/ blksize
/ 4, 100);
118 N
= MAX (new_size
/ blksize
/ 4, 100);
124 lru_set_recently_accessed (uint64_t blknum
)
126 /* If the block is already set in the first bitmap, don't need to do
129 if (bitmap_get_blk (&bm
[0], blknum
, false))
132 bitmap_set_blk (&bm
[0], blknum
, true);
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
149 bitmap_clear (&bm
[0]);
155 lru_has_been_recently_accessed (uint64_t blknum
)
158 bitmap_get_blk (&bm
[0], blknum
, false) ||
159 bitmap_get_blk (&bm
[1], blknum
, false);