2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * 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.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup lwext4
34 * @brief Block cache allocator.
37 #include "ext4_config.h"
38 #include "ext4_bcache.h"
39 #include "ext4_blockdev.h"
40 #include "ext4_debug.h"
41 #include "ext4_errno.h"
46 static int ext4_bcache_lba_compare(struct ext4_buf *a, struct ext4_buf *b)
50 else if (a->lba < b->lba)
55 static int ext4_bcache_lru_compare(struct ext4_buf *a, struct ext4_buf *b)
57 if (a->lru_id > b->lru_id)
59 else if (a->lru_id < b->lru_id)
64 RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
65 ext4_bcache_lba_compare, static inline)
66 RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
67 ext4_bcache_lru_compare, static inline)
69 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
72 ext4_assert(bc && cnt && itemsize);
74 memset(bc, 0, sizeof(struct ext4_bcache));
77 bc->itemsize = itemsize;
79 bc->max_ref_blocks = 0;
84 void ext4_bcache_cleanup(struct ext4_bcache *bc)
86 struct ext4_buf *buf, *tmp;
87 RB_FOREACH_SAFE(buf, ext4_buf_lba, &bc->lba_root, tmp) {
88 ext4_block_flush_buf(bc->bdev, buf);
89 ext4_bcache_drop_buf(bc, buf);
93 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
95 memset(bc, 0, sizeof(struct ext4_bcache));
101 * This is ext4_bcache, the module handling basic buffer-cache stuff.
103 * Buffers in a bcache are sorted by their LBA and stored in a
106 * Bcache also maintains another RB-Tree(lru_root) right now, where
107 * buffers are sorted by their LRU id.
109 * A singly-linked list is used to track those dirty buffers which are
110 * ready to be flushed. (Those buffers which are dirty but also referenced
111 * are not considered ready to be flushed.)
113 * When a buffer is not referenced, it will be stored in both lba_root
114 * and lru_root, while it will only be stored in lba_root when it is
118 static struct ext4_buf *
119 ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
122 struct ext4_buf *buf;
123 data = malloc(bc->itemsize);
127 buf = calloc(1, sizeof(struct ext4_buf));
139 static void ext4_buf_free(struct ext4_buf *buf)
145 static struct ext4_buf *
146 ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
148 struct ext4_buf tmp = {
152 return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
155 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
157 return RB_MIN(ext4_buf_lru, &bc->lru_root);
160 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
162 /* Warn on dropping any referenced buffers.*/
164 ext4_dbg(DEBUG_BCACHE, DBG_WARN "Buffer is still referenced. "
165 "lba: %" PRIu64 ", refctr: %" PRIu32 "\n",
166 buf->lba, buf->refctr);
168 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
170 RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
172 /*Forcibly drop dirty buffer.*/
173 if (ext4_bcache_test_flag(buf, BC_DIRTY))
174 ext4_bcache_remove_dirty_node(bc, buf);
180 void ext4_bcache_invalidate_buf(struct ext4_bcache *bc,
181 struct ext4_buf *buf)
183 buf->end_write = NULL;
184 buf->end_write_arg = NULL;
186 /* Clear both dirty and up-to-date flags. */
187 if (ext4_bcache_test_flag(buf, BC_DIRTY))
188 ext4_bcache_remove_dirty_node(bc, buf);
190 ext4_bcache_clear_dirty(buf);
193 void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
197 uint64_t end = from + cnt - 1;
198 struct ext4_buf *tmp = ext4_buf_lookup(bc, from), *buf;
199 RB_FOREACH_FROM(buf, ext4_buf_lba, tmp) {
203 ext4_bcache_invalidate_buf(bc, buf);
208 ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
211 struct ext4_buf *buf = ext4_buf_lookup(bc, lba);
213 /* If buffer is not referenced. */
215 /* Assign new value to LRU id and increment LRU counter
217 buf->lru_id = ++bc->lru_ctr;
218 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
219 if (ext4_bcache_test_flag(buf, BC_DIRTY))
220 ext4_bcache_remove_dirty_node(bc, buf);
224 ext4_bcache_inc_ref(buf);
233 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
236 /* Try to search the buffer with exaxt LBA. */
237 struct ext4_buf *buf = ext4_bcache_find_get(bc, b, b->lb_id);
243 /* We need to allocate one buffer.*/
244 buf = ext4_buf_alloc(bc, b->lb_id);
248 RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
249 /* One more buffer in bcache now. :-) */
252 /*Calc ref blocks max depth*/
253 if (bc->max_ref_blocks < bc->ref_blocks)
254 bc->max_ref_blocks = bc->ref_blocks;
257 ext4_bcache_inc_ref(buf);
258 /* Assign new value to LRU id and increment LRU counter
260 buf->lru_id = ++bc->lru_ctr;
269 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b)
271 struct ext4_buf *buf = b->buf;
273 ext4_assert(bc && b);
276 ext4_assert(b->lb_id);
278 /*Block should have a valid pointer to ext4_buf.*/
281 /*Check if someone don't try free unreferenced block cache.*/
282 ext4_assert(buf->refctr);
284 /*Just decrease reference counter*/
285 ext4_bcache_dec_ref(buf);
287 /* We are the last one touching this buffer, do the cleanups. */
289 RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
290 /* This buffer is ready to be flushed. */
291 if (ext4_bcache_test_flag(buf, BC_DIRTY) &&
292 ext4_bcache_test_flag(buf, BC_UPTODATE)) {
293 if (bc->bdev->cache_write_back &&
294 !ext4_bcache_test_flag(buf, BC_FLUSH) &&
295 !ext4_bcache_test_flag(buf, BC_TMP))
296 ext4_bcache_insert_dirty_node(bc, buf);
298 ext4_block_flush_buf(bc->bdev, buf);
299 ext4_bcache_clear_flag(buf, BC_FLUSH);
303 /* The buffer is invalidated...drop it. */
304 if (!ext4_bcache_test_flag(buf, BC_UPTODATE) ||
305 ext4_bcache_test_flag(buf, BC_TMP))
306 ext4_bcache_drop_buf(bc, buf);
316 bool ext4_bcache_is_full(struct ext4_bcache *bc)
318 return (bc->cnt <= bc->ref_blocks);