1 | /* |
2 | * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com) |
3 | * All rights reserved. |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
7 | * are met: |
8 | * |
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. |
16 | * |
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. |
27 | */ |
28 | |
29 | /** @addtogroup lwext4 |
30 | * @{ |
31 | */ |
32 | /** |
33 | * @file ext4_bcache.h |
34 | * @brief Block cache allocator. |
35 | */ |
36 | |
37 | #ifndef EXT4_BCACHE_H_ |
38 | #define EXT4_BCACHE_H_ |
39 | |
40 | #ifdef __cplusplus |
41 | extern "C" { |
42 | #endif |
43 | |
44 | #include <ext4_config.h> |
45 | |
46 | #include <stdint.h> |
47 | #include <stdbool.h> |
48 | #include <misc/tree.h> |
49 | #include <misc/queue.h> |
50 | |
51 | #define EXT4_BLOCK_ZERO() \ |
52 | {.lb_id = 0, .data = 0} |
53 | |
54 | /**@brief Single block descriptor*/ |
55 | struct ext4_block { |
56 | /**@brief Logical block ID*/ |
57 | uint64_t lb_id; |
58 | |
59 | /**@brief Buffer */ |
60 | struct ext4_buf *buf; |
61 | |
62 | /**@brief Data buffer.*/ |
63 | uint8_t *data; |
64 | }; |
65 | |
66 | struct ext4_bcache; |
67 | |
68 | /**@brief Single block descriptor*/ |
69 | struct ext4_buf { |
70 | /**@brief Flags*/ |
71 | int flags; |
72 | |
73 | /**@brief Logical block address*/ |
74 | uint64_t lba; |
75 | |
76 | /**@brief Data buffer.*/ |
77 | uint8_t *data; |
78 | |
79 | /**@brief LRU priority. (unused) */ |
80 | uint32_t lru_prio; |
81 | |
82 | /**@brief LRU id.*/ |
83 | uint32_t lru_id; |
84 | |
85 | /**@brief Reference count table*/ |
86 | uint32_t refctr; |
87 | |
88 | /**@brief The block cache this buffer belongs to. */ |
89 | struct ext4_bcache *bc; |
90 | |
91 | /**@brief Whether or not buffer is on dirty list.*/ |
92 | bool on_dirty_list; |
93 | |
94 | /**@brief LBA tree node*/ |
95 | RB_ENTRY(ext4_buf) lba_node; |
96 | |
97 | /**@brief LRU tree node*/ |
98 | RB_ENTRY(ext4_buf) lru_node; |
99 | |
100 | /**@brief Dirty list node*/ |
101 | SLIST_ENTRY(ext4_buf) dirty_node; |
102 | |
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, |
110 | int res, |
111 | void *arg); |
112 | |
113 | /**@brief argument passed to end_write() callback.*/ |
114 | void *end_write_arg; |
115 | }; |
116 | |
117 | /**@brief Block cache descriptor*/ |
118 | struct ext4_bcache { |
119 | |
120 | /**@brief Item count in block cache*/ |
121 | uint32_t cnt; |
122 | |
123 | /**@brief Item size in block cache*/ |
124 | uint32_t itemsize; |
125 | |
126 | /**@brief Last recently used counter*/ |
127 | uint32_t lru_ctr; |
128 | |
129 | /**@brief Currently referenced datablocks*/ |
130 | uint32_t ref_blocks; |
131 | |
132 | /**@brief Maximum referenced datablocks*/ |
133 | uint32_t max_ref_blocks; |
134 | |
135 | /**@brief The blockdev binded to this block cache*/ |
136 | struct ext4_blockdev *bdev; |
137 | |
138 | /**@brief The cache should not be shaked */ |
139 | bool dont_shake; |
140 | |
141 | /**@brief A tree holding all bufs*/ |
142 | RB_HEAD(ext4_buf_lba, ext4_buf) lba_root; |
143 | |
144 | /**@brief A tree holding unreferenced bufs*/ |
145 | RB_HEAD(ext4_buf_lru, ext4_buf) lru_root; |
146 | |
147 | /**@brief A singly-linked list holding dirty buffers*/ |
148 | SLIST_HEAD(ext4_buf_dirty, ext4_buf) dirty_list; |
149 | }; |
150 | |
151 | /**@brief buffer state bits |
152 | * |
153 | * - BC♡UPTODATE: Buffer contains valid data. |
154 | * - BC_DIRTY: Buffer is dirty. |
155 | * - BC_FLUSH: Buffer will be immediately flushed, |
156 | * when no one references it. |
157 | * - BC_TMP: Buffer will be dropped once its refctr |
158 | * reaches zero. |
159 | */ |
160 | enum bcache_state_bits { |
161 | BC_UPTODATE, |
162 | BC_DIRTY, |
163 | BC_FLUSH, |
164 | BC_TMP |
165 | }; |
166 | |
167 | #define ext4_bcache_set_flag(buf, b) \ |
168 | (buf)->flags |= 1 << (b) |
169 | |
170 | #define ext4_bcache_clear_flag(buf, b) \ |
171 | (buf)->flags &= ~(1 << (b)) |
172 | |
173 | #define ext4_bcache_test_flag(buf, b) \ |
174 | (((buf)->flags & (1 << (b))) >> (b)) |
175 | |
176 | static inline void ext4_bcache_set_dirty(struct ext4_buf *buf) { |
177 | ext4_bcache_set_flag(buf, BC_UPTODATE); |
178 | ext4_bcache_set_flag(buf, BC_DIRTY); |
179 | } |
180 | |
181 | static inline void ext4_bcache_clear_dirty(struct ext4_buf *buf) { |
182 | ext4_bcache_clear_flag(buf, BC_UPTODATE); |
183 | ext4_bcache_clear_flag(buf, BC_DIRTY); |
184 | } |
185 | |
186 | /**@brief Increment reference counter of buf by 1.*/ |
187 | #define ext4_bcache_inc_ref(buf) ((buf)->refctr++) |
188 | |
189 | /**@brief Decrement reference counter of buf by 1.*/ |
190 | #define ext4_bcache_dec_ref(buf) ((buf)->refctr--) |
191 | |
192 | /**@brief Insert buffer to dirty cache list |
193 | * @param bc block cache descriptor |
194 | * @param buf buffer descriptor */ |
195 | static inline void |
196 | ext4_bcache_insert_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) { |
197 | if (!buf->on_dirty_list) { |
198 | SLIST_INSERT_HEAD(&bc->dirty_list, buf, dirty_node); |
199 | buf->on_dirty_list = true; |
200 | } |
201 | } |
202 | |
203 | /**@brief Remove buffer to dirty cache list |
204 | * @param bc block cache descriptor |
205 | * @param buf buffer descriptor */ |
206 | static inline void |
207 | ext4_bcache_remove_dirty_node(struct ext4_bcache *bc, struct ext4_buf *buf) { |
208 | if (buf->on_dirty_list) { |
209 | SLIST_REMOVE(&bc->dirty_list, buf, ext4_buf, dirty_node); |
210 | buf->on_dirty_list = false; |
211 | } |
212 | } |
213 | |
214 | |
215 | /**@brief Dynamic initialization of block cache. |
216 | * @param bc block cache descriptor |
217 | * @param cnt items count in block cache |
218 | * @param itemsize single item size (in bytes) |
219 | * @return standard error code*/ |
220 | int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt, |
221 | uint32_t itemsize); |
222 | |
223 | /**@brief Do cleanup works on block cache. |
224 | * @param bc block cache descriptor.*/ |
225 | void ext4_bcache_cleanup(struct ext4_bcache *bc); |
226 | |
227 | /**@brief Dynamic de-initialization of block cache. |
228 | * @param bc block cache descriptor |
229 | * @return standard error code*/ |
230 | int ext4_bcache_fini_dynamic(struct ext4_bcache *bc); |
231 | |
232 | /**@brief Get a buffer with the lowest LRU counter in bcache. |
233 | * @param bc block cache descriptor |
234 | * @return buffer with the lowest LRU counter*/ |
235 | struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc); |
236 | |
237 | /**@brief Drop unreferenced buffer from bcache. |
238 | * @param bc block cache descriptor |
239 | * @param buf buffer*/ |
240 | void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf); |
241 | |
242 | /**@brief Invalidate a buffer. |
243 | * @param bc block cache descriptor |
244 | * @param buf buffer*/ |
245 | void ext4_bcache_invalidate_buf(struct ext4_bcache *bc, |
246 | struct ext4_buf *buf); |
247 | |
248 | /**@brief Invalidate a range of buffers. |
249 | * @param bc block cache descriptor |
250 | * @param from starting lba |
251 | * @param cnt block counts*/ |
252 | void ext4_bcache_invalidate_lba(struct ext4_bcache *bc, |
253 | uint64_t from, |
254 | uint32_t cnt); |
255 | |
256 | /**@brief Find existing buffer from block cache memory. |
257 | * Unreferenced block allocation is based on LRU |
258 | * (Last Recently Used) algorithm. |
259 | * @param bc block cache descriptor |
260 | * @param b block to alloc |
261 | * @param lba logical block address |
262 | * @return block cache buffer */ |
263 | struct ext4_buf * |
264 | ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b, |
265 | uint64_t lba); |
266 | |
267 | /**@brief Allocate block from block cache memory. |
268 | * Unreferenced block allocation is based on LRU |
269 | * (Last Recently Used) algorithm. |
270 | * @param bc block cache descriptor |
271 | * @param b block to alloc |
272 | * @param is_new block is new (needs to be read) |
273 | * @return standard error code*/ |
274 | int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b, |
275 | bool *is_new); |
276 | |
277 | /**@brief Free block from cache memory (decrement reference counter). |
278 | * @param bc block cache descriptor |
279 | * @param b block to free |
280 | * @return standard error code*/ |
281 | int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b); |
282 | |
283 | /**@brief Return a full status of block cache. |
284 | * @param bc block cache descriptor |
285 | * @return full status*/ |
286 | bool ext4_bcache_is_full(struct ext4_bcache *bc); |
287 | |
288 | #ifdef __cplusplus |
289 | } |
290 | #endif |
291 | |
292 | #endif /* EXT4_BCACHE_H_ */ |
293 | |
294 | /** |
295 | * @} |
296 | */ |
297 | |