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.c
34 * @brief Block cache allocator.
35 */
36
37#include <ext4_config.h>
38#include <ext4_types.h>
39#include <ext4_bcache.h>
40#include <ext4_blockdev.h>
41#include <ext4_debug.h>
42#include <ext4_errno.h>
43
44#include <string.h>
45#include <stdlib.h>
46
47static int ext4_bcache_lba_compare(struct ext4_buf *a, struct ext4_buf *b)
48{
49 if (a->lba > b->lba)
50 return 1;
51 else if (a->lba < b->lba)
52 return -1;
53 return 0;
54}
55
56static int ext4_bcache_lru_compare(struct ext4_buf *a, struct ext4_buf *b)
57{
58 if (a->lru_id > b->lru_id)
59 return 1;
60 else if (a->lru_id < b->lru_id)
61 return -1;
62 return 0;
63}
64
65RB_GENERATE_INTERNAL(ext4_buf_lba, ext4_buf, lba_node,
66 ext4_bcache_lba_compare, static inline)
67RB_GENERATE_INTERNAL(ext4_buf_lru, ext4_buf, lru_node,
68 ext4_bcache_lru_compare, static inline)
69
70int ext4_bcache_init_dynamic(struct ext4_bcache *bc, uint32_t cnt,
71 uint32_t itemsize)
72{
73 ext4_assert(bc && cnt && itemsize);
74
75 memset(dest: bc, c: 0, size: sizeof(struct ext4_bcache));
76
77 bc->cnt = cnt;
78 bc->itemsize = itemsize;
79 bc->ref_blocks = 0;
80 bc->max_ref_blocks = 0;
81
82 return EOK;
83}
84
85void ext4_bcache_cleanup(struct ext4_bcache *bc)
86{
87 struct ext4_buf *buf, *tmp;
88 RB_FOREACH_SAFE(buf, ext4_buf_lba, &bc->lba_root, tmp) {
89 ext4_block_flush_buf(bdev: bc->bdev, buf);
90 ext4_bcache_drop_buf(bc, buf);
91 }
92}
93
94int ext4_bcache_fini_dynamic(struct ext4_bcache *bc)
95{
96 memset(dest: bc, c: 0, size: sizeof(struct ext4_bcache));
97 return EOK;
98}
99
100/**@brief:
101 *
102 * This is ext4_bcache, the module handling basic buffer-cache stuff.
103 *
104 * Buffers in a bcache are sorted by their LBA and stored in a
105 * RB-Tree(lba_root).
106 *
107 * Bcache also maintains another RB-Tree(lru_root) right now, where
108 * buffers are sorted by their LRU id.
109 *
110 * A singly-linked list is used to track those dirty buffers which are
111 * ready to be flushed. (Those buffers which are dirty but also referenced
112 * are not considered ready to be flushed.)
113 *
114 * When a buffer is not referenced, it will be stored in both lba_root
115 * and lru_root, while it will only be stored in lba_root when it is
116 * referenced.
117 */
118
119static struct ext4_buf *
120ext4_buf_alloc(struct ext4_bcache *bc, uint64_t lba)
121{
122 void *data;
123 struct ext4_buf *buf;
124 data = ext4_malloc(size: bc->itemsize);
125 if (!data)
126 return NULL;
127
128 buf = ext4_calloc(count: 1, size: sizeof(struct ext4_buf));
129 if (!buf) {
130 ext4_free(pointer: data);
131 return NULL;
132 }
133
134 buf->lba = lba;
135 buf->data = data;
136 buf->bc = bc;
137 return buf;
138}
139
140static void ext4_buf_free(struct ext4_buf *buf)
141{
142 ext4_free(pointer: buf->data);
143 ext4_free(pointer: buf);
144}
145
146static struct ext4_buf *
147ext4_buf_lookup(struct ext4_bcache *bc, uint64_t lba)
148{
149 struct ext4_buf tmp = {
150 .lba = lba
151 };
152
153 return RB_FIND(ext4_buf_lba, &bc->lba_root, &tmp);
154}
155
156struct ext4_buf *ext4_buf_lowest_lru(struct ext4_bcache *bc)
157{
158 return RB_MIN(ext4_buf_lru, &bc->lru_root);
159}
160
161void ext4_bcache_drop_buf(struct ext4_bcache *bc, struct ext4_buf *buf)
162{
163 /* Warn on dropping any referenced buffers.*/
164 if (buf->refctr) {
165 ext4_dbg(DEBUG_BCACHE, DBG_WARN "Buffer is still referenced. "
166 "lba: %" PRIu64 ", refctr: %" PRIu32 "\n",
167 buf->lba, buf->refctr);
168 } else
169 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
170
171 RB_REMOVE(ext4_buf_lba, &bc->lba_root, buf);
172
173 /*Forcibly drop dirty buffer.*/
174 if (ext4_bcache_test_flag(buf, BC_DIRTY))
175 ext4_bcache_remove_dirty_node(bc, buf);
176
177 ext4_buf_free(buf);
178 bc->ref_blocks--;
179}
180
181void ext4_bcache_invalidate_buf(struct ext4_bcache *bc,
182 struct ext4_buf *buf)
183{
184 buf->end_write = NULL;
185 buf->end_write_arg = NULL;
186
187 /* Clear both dirty and up-to-date flags. */
188 if (ext4_bcache_test_flag(buf, BC_DIRTY))
189 ext4_bcache_remove_dirty_node(bc, buf);
190
191 ext4_bcache_clear_dirty(buf);
192}
193
194void ext4_bcache_invalidate_lba(struct ext4_bcache *bc,
195 uint64_t from,
196 uint32_t cnt)
197{
198 uint64_t end = from + cnt - 1;
199 struct ext4_buf *tmp = ext4_buf_lookup(bc, lba: from), *buf;
200 RB_FOREACH_FROM(buf, ext4_buf_lba, tmp) {
201 if (buf->lba > end)
202 break;
203
204 ext4_bcache_invalidate_buf(bc, buf);
205 }
206}
207
208struct ext4_buf *
209ext4_bcache_find_get(struct ext4_bcache *bc, struct ext4_block *b,
210 uint64_t lba)
211{
212 struct ext4_buf *buf = ext4_buf_lookup(bc, lba);
213 if (buf) {
214 /* If buffer is not referenced. */
215 if (!buf->refctr) {
216 /* Assign new value to LRU id and increment LRU counter
217 * by 1*/
218 buf->lru_id = ++bc->lru_ctr;
219 RB_REMOVE(ext4_buf_lru, &bc->lru_root, buf);
220 if (ext4_bcache_test_flag(buf, BC_DIRTY))
221 ext4_bcache_remove_dirty_node(bc, buf);
222
223 }
224
225 ext4_bcache_inc_ref(buf);
226
227 b->lb_id = lba;
228 b->buf = buf;
229 b->data = buf->data;
230 }
231 return buf;
232}
233
234int ext4_bcache_alloc(struct ext4_bcache *bc, struct ext4_block *b,
235 bool *is_new)
236{
237 /* Try to search the buffer with exaxt LBA. */
238 struct ext4_buf *buf = ext4_bcache_find_get(bc, b, lba: b->lb_id);
239 if (buf) {
240 *is_new = false;
241 return EOK;
242 }
243
244 /* We need to allocate one buffer.*/
245 buf = ext4_buf_alloc(bc, lba: b->lb_id);
246 if (!buf)
247 return ENOMEM;
248
249 RB_INSERT(ext4_buf_lba, &bc->lba_root, buf);
250 /* One more buffer in bcache now. :-) */
251 bc->ref_blocks++;
252
253 /*Calc ref blocks max depth*/
254 if (bc->max_ref_blocks < bc->ref_blocks)
255 bc->max_ref_blocks = bc->ref_blocks;
256
257
258 ext4_bcache_inc_ref(buf);
259 /* Assign new value to LRU id and increment LRU counter
260 * by 1*/
261 buf->lru_id = ++bc->lru_ctr;
262
263 b->buf = buf;
264 b->data = buf->data;
265
266 *is_new = true;
267 return EOK;
268}
269
270int ext4_bcache_free(struct ext4_bcache *bc, struct ext4_block *b)
271{
272 struct ext4_buf *buf = b->buf;
273
274 ext4_assert(bc && b);
275
276 /*Check if valid.*/
277 ext4_assert(b->lb_id);
278
279 /*Block should have a valid pointer to ext4_buf.*/
280 ext4_assert(buf);
281
282 /*Check if someone don't try free unreferenced block cache.*/
283 ext4_assert(buf->refctr);
284
285 /*Just decrease reference counter*/
286 ext4_bcache_dec_ref(buf);
287
288 /* We are the last one touching this buffer, do the cleanups. */
289 if (!buf->refctr) {
290 RB_INSERT(ext4_buf_lru, &bc->lru_root, buf);
291 /* This buffer is ready to be flushed. */
292 if (ext4_bcache_test_flag(buf, BC_DIRTY) &&
293 ext4_bcache_test_flag(buf, BC_UPTODATE)) {
294 if (bc->bdev->cache_write_back &&
295 !ext4_bcache_test_flag(buf, BC_FLUSH) &&
296 !ext4_bcache_test_flag(buf, BC_TMP))
297 ext4_bcache_insert_dirty_node(bc, buf);
298 else {
299 ext4_block_flush_buf(bdev: bc->bdev, buf);
300 ext4_bcache_clear_flag(buf, BC_FLUSH);
301 }
302 }
303
304 /* The buffer is invalidated...drop it. */
305 if (!ext4_bcache_test_flag(buf, BC_UPTODATE) ||
306 ext4_bcache_test_flag(buf, BC_TMP))
307 ext4_bcache_drop_buf(bc, buf);
308
309 }
310
311 b->lb_id = 0;
312 b->data = 0;
313
314 return EOK;
315}
316
317bool ext4_bcache_is_full(struct ext4_bcache *bc)
318{
319 return (bc->cnt <= bc->ref_blocks);
320}
321
322
323/**
324 * @}
325 */
326