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
41extern "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*/
55struct 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
66struct ext4_bcache;
67
68/**@brief Single block descriptor*/
69struct 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*/
118struct 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 */
160enum 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
176static 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
181static 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 */
195static inline void
196ext4_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 */
206static inline void
207ext4_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*/
220int 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.*/
225void 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*/
230int 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*/
235struct 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*/
240void 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*/
245void 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*/
252void 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 */
263struct ext4_buf *
264ext4_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*/
274int 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*/
281int 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*/
286bool 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