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 #ifndef EXT4_BCACHE_H_
38 #define EXT4_BCACHE_H_
44 #include "ext4_config.h"
48 #include "misc/tree.h"
49 #include "misc/queue.h"
51 #define EXT4_BLOCK_ZERO() \
52 {.lb_id = 0, .data = 0}
54 /**@brief Single block descriptor*/
56 /**@brief Logical block ID*/
62 /**@brief Data buffer.*/
68 /**@brief Single block descriptor*/
73 /**@brief Logical block address*/
76 /**@brief Data buffer.*/
79 /**@brief LRU priority. (unused) */
85 /**@brief Reference count table*/
88 /**@brief The block cache this buffer belongs to. */
89 struct ext4_bcache *bc;
91 /**@brief Whether or not buffer is on dirty list.*/
94 /**@brief LBA tree node*/
95 RB_ENTRY(ext4_buf) lba_node;
97 /**@brief LRU tree node*/
98 RB_ENTRY(ext4_buf) lru_node;
100 /**@brief Dirty list node*/
101 SLIST_ENTRY(ext4_buf) dirty_node;
103 /**@brief Callback routine after a disk-write operation.
104 * @param bc block cache descriptor
105 * @param buf buffer descriptor
106 * @param standard error code returned by bdev->bwrite()
107 * @param arg argument passed to this routine*/
108 void (*end_write)(struct ext4_bcache *bc,
109 struct ext4_buf *buf,
113 /**@brief argument passed to end_write() callback.*/
117 /**@brief Block cache descriptor*/
120 /**@brief Item count in block cache*/
123 /**@brief Item size in block cache*/
126 /**@brief Last recently used counter*/
129 /**@brief Currently referenced datablocks*/
132 /**@brief Maximum referenced datablocks*/
133 uint32_t max_ref_blocks;
135 /**@brief The blockdev binded to this block cache*/
136 struct ext4_blockdev *bdev;
138 /**@brief A tree holding all bufs*/
139 RB_HEAD(ext4_buf_lba, ext4_buf) lba_root;
141 /**@brief A tree holding unreferenced bufs*/
142 RB_HEAD(ext4_buf_lru, ext4_buf) lru_root;
144 /**@brief A singly-linked list holding dirty buffers*/
145 SLIST_HEAD(ext4_buf_dirty, ext4_buf) dirty_list;
148 /**@brief buffer state bits
150 * - BC♡UPTODATE: Buffer contains valid data.
151 * - BC_DIRTY: Buffer is dirty.
152 * - BC_FLUSH: Buffer will be immediately flushed,
153 * when no one references it.
154 * - BC_TMP: Buffer will be dropped once its refctr
157 enum bcache_state_bits {
164 #define ext4_bcache_set_flag(buf, b) \
165 (buf)->flags |= 1 << (b)
167 #define ext4_bcache_clear_flag(buf, b) \
168 (buf)->flags &= ~(1 << (b))
170 #define ext4_bcache_test_flag(buf, b) \
171 (((buf)->flags & (1 << (b))) >> (b))
173 static inline void ext4_bcache_set_dirty(struct ext4_buf *buf) {
174 ext4_bcache_set_flag(buf, BC_UPTODATE);
175 ext4_bcache_set_flag(buf, BC_DIRTY);
178 static inline void ext4_bcache_clear_dirty(struct ext4_buf *buf) {
179 ext4_bcache_clear_flag(buf, BC_UPTODATE);
180 ext4_bcache_clear_flag(buf, BC_DIRTY);
183 /**@brief Increment reference counter of buf by 1.*/
184 #define ext4_bcache_inc_ref(buf) ((buf)->refctr++)
186 /**@brief Decrement reference counter of buf by 1.*/
187 #define ext4_bcache_dec_ref(buf) ((buf)->refctr--)
189 /**@brief Insert buffer to dirty cache list
190 * @param bc block cache descriptor
191 * @param buf buffer descriptor */
193 ext4_bcache_insert_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
194 if (!buf->on_dirty_list) {
195 SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node);
196 buf->on_dirty_list = true;
200 /**@brief Remove buffer to dirty cache list
201 * @param bc block cache descriptor
202 * @param buf buffer descriptor */
204 ext4_bcache_remove_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) {
205 if (buf->on_dirty_list) {
206 SLIST_REMOVE(&bc->dirty_list, buf, ext4_buf, dirty_node);
207 buf->on_dirty_list = false;
212 /**@brief Dynamic initialization of block cache.
213 * @param bc block cache descriptor
214 * @param cnt items count in block cache
215 * @param itemsize single item size (in bytes)
216 * @return standard error code*/
217 int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
220 /**@brief Do cleanup works on block cache.
221 * @param bc block cache descriptor.*/
222 void ext4_bcache_cleanup(struct ext4_bcache *bc);
224 /**@brief Dynamic de-initialization of block cache.
225 * @param bc block cache descriptor
226 * @return standard error code*/
227 int ext4_bcache_fini_dynamic(struct ext4_bcache *bc);
229 /**@brief Get a buffer with the lowest LRU counter in bcache.
230 * @param bc block cache descriptor
231 * @return buffer with the lowest LRU counter*/
232 struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc);
234 /**@brief Drop unreferenced buffer from bcache.
235 * @param bc block cache descriptor
236 * @param buf buffer*/
237 void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf);
239 /**@brief Invalidate a range of buffers.
240 * @param bc block cache descriptor
241 * @param from starting lba
242 * @param cnt block counts
243 * @param buf buffer*/
244 void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
248 /**@brief Find existing buffer from block cache memory.
249 * Unreferenced block allocation is based on LRU
250 * (Last Recently Used) algorithm.
251 * @param bc block cache descriptor
252 * @param b block to alloc
253 * @param lba logical block address
254 * @return block cache buffer */
256 ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
259 /**@brief Allocate block from block cache memory.
260 * Unreferenced block allocation is based on LRU
261 * (Last Recently Used) algorithm.
262 * @param bc block cache descriptor
263 * @param b block to alloc
264 * @param is_new block is new (needs to be read)
265 * @return standard error code*/
266 int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
269 /**@brief Free block from cache memory (decrement reference counter).
270 * @param bc block cache descriptor
271 * @param b block to free
272 * @return standard error code*/
273 int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b);
275 /**@brief Return a full status of block cache.
276 * @param bc block cache descriptor
277 * @return full status*/
278 bool ext4_bcache_is_full(struct ext4_bcache *bc);
284 #endif /* EXT4_BCACHE_H_ */