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_debug.h"
40 #include "ext4_errno.h"
46 ext4_bcache_lba_compare(struct ext4_buf *a,
49 return a->lba - b->lba;
53 ext4_bcache_lru_compare(struct ext4_buf *a,
56 return a->lru_id - b->lru_id;
59 RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
60 ext4_bcache_lba_compare, static inline)
61 RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
62 ext4_bcache_lru_compare, static inline)
64 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
67 ext4_assert(bc && cnt && itemsize);
69 memset(bc, 0, sizeof(struct ext4_bcache));
72 bc->itemsize = itemsize;
74 bc->max_ref_blocks = 0;
79 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
81 memset(bc, 0, sizeof(struct ext4_bcache));
87 * This is ext4_bcache, the module handling basic buffer-cache stuff.
89 * Buffers in a bcache are sorted by their LBA and stored in a
92 * Bcache also maintains another RB-Tree(lru_root) right now, where
93 * buffers are sorted by their LRU id.
95 * A singly-linked list is used to track those dirty buffers which are
96 * ready to be flushed. (Those buffers which are dirty but also referenced
97 * are not considered ready to be flushed.)
99 * When a buffer is not referenced, it will be stored in both lba_root
100 * and lru_root, while it will only be stored in lba_root when it is
104 static struct ext4_buf *
105 ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
108 struct ext4_buf *buf;
109 data = malloc(bc->itemsize);
113 buf = calloc(1, sizeof(struct ext4_buf));
124 static void ext4_buf_free(struct ext4_buf *buf)
130 static struct ext4_buf *
131 ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
133 struct ext4_buf tmp = {
137 return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
140 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
142 return RB_MIN(ext4_buf_lru, &bc->lru_root);
145 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
147 /*Cannot drop any referenced buffers.*/
148 ext4_assert(!buf->refctr);
150 RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
151 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
153 /*Forcibly drop dirty buffer.*/
154 if (ext4_bcache_test_flag(buf, BC_DIRTY))
155 SLIST_REMOVE(&bc->dirty_list,
164 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
167 /* Try to search the buffer with exaxt LBA. */
168 struct ext4_buf *buf = ext4_buf_lookup(bc, b->lb_id);
170 /* If buffer is not referenced. */
172 /* Assign new value to LRU id and increment LRU counter
174 buf->lru_id = ++bc->lru_ctr;
175 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
176 if (ext4_bcache_test_flag(buf, BC_DIRTY))
177 SLIST_REMOVE(&bc->dirty_list,
186 b->uptodate = ext4_bcache_test_flag(buf, BC_UPTODATE);
187 /* Right now we don't propagate the dirty flag from ext4_buf to
197 /* We need to allocate one buffer.*/
198 buf = ext4_buf_alloc(bc, b->lb_id);
202 RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
203 /* One more buffer in bcache now. :-) */
207 /* Assign new value to LRU id and increment LRU counter
209 buf->lru_id = ++bc->lru_ctr;
220 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b)
222 struct ext4_buf *buf = b->buf;
224 ext4_assert(bc && b);
227 ext4_assert(b->lb_id);
229 /*Block should have a valid pointer to ext4_buf.*/
232 /*Check if someone don't try free unreferenced block cache.*/
233 ext4_assert(buf->refctr);
235 /*Just decrease reference counter*/
238 /* If buffer is modified, buf will be mark up-to-date and dirty. */
240 ext4_bcache_set_flag(buf, BC_DIRTY);
241 ext4_bcache_set_flag(buf, BC_UPTODATE);
244 /* Someone might want to drop this buffer from bcache. */
246 ext4_bcache_clear_flag(buf, BC_UPTODATE);
248 /* We are the last one touching this buffer, do the cleanups. */
250 RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
251 /* This buffer is ready to be flushed. */
252 if (ext4_bcache_test_flag(buf, BC_DIRTY))
253 SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
255 /* The buffer is invalidated...drop it. */
256 if (!ext4_bcache_test_flag(buf, BC_UPTODATE))
257 ext4_bcache_drop_buf(bc, buf);
269 bool ext4_bcache_is_full(struct ext4_bcache *bc)
271 return (bc->cnt <= bc->ref_blocks);