1#include <block/bcache.h>
2#include <block/block.h>
3#include <block/sched.h>
4#include <console/panic.h>
5#include <math/align.h>
6#include <mem/alloc.h>
7#include <mem/nofail.h>
8#include <stdbool.h>
9#include <stddef.h>
10#include <stdint.h>
11#include <sync/lock_chk_assert.h>
12#include <thread/workqueue.h>
13#include <tsa.h>
14
15static bool remove(struct bcache *cache, uint64_t key, uint64_t spb);
16
17static bool insert_locked(struct bcache *cache, uint64_t key,
18 struct bcache_entry *value)
19 TSA_CALLER_HOLDS(&cache->lock);
20
21static bool insert(struct bcache *cache, uint64_t key,
22 struct bcache_entry *value);
23
24static struct bcache_entry *get(struct bcache *cache, uint64_t key);
25static bool write(struct block_device *d, struct bcache *cache,
26 struct bcache_entry *ent, uint64_t spb);
27
28/* prefetch is asynchronous */
29static enum err prefetch(struct block_device *disk, struct bcache *cache,
30 uint64_t lba, uint64_t block_size, uint64_t spb);
31
32/* eviction must be explicitly and separately called */
33static bool insert_locked(struct bcache *cache, uint64_t key,
34 struct bcache_entry *value) {
35 uint64_t index = bcache_hash(x: key, capacity: cache->capacity);
36 struct bcache_wrapper *head = cache->entries[index];
37
38 /* Key already exists */
39 for (struct bcache_wrapper *node = head; node; node = node->next) {
40 if (node->key == key) {
41 node->value = value;
42 node->value->access_time = bcache_get_ticks(cache);
43 return true;
44 }
45 }
46
47 /* New head */
48 struct bcache_wrapper *new_node = vnew(new_node);
49 if (!new_node) {
50 return false;
51 }
52
53 new_node->key = key;
54 new_node->value = value;
55 new_node->value->access_time = bcache_get_ticks(cache);
56 new_node->next = head;
57
58 cache->entries[index] = new_node;
59 cache->count++;
60
61 return true;
62}
63
64static bool insert(struct bcache *cache, uint64_t key,
65 struct bcache_entry *value) {
66 enum irql irql = spin_lock(&cache->lock);
67 bool ret = insert_locked(cache, key, value);
68 spin_unlock(&cache->lock, irql);
69 return ret;
70}
71
72static struct bcache_entry *get(struct bcache *cache, uint64_t key) {
73 enum irql irql = spin_lock(&cache->lock);
74
75 uint64_t index = bcache_hash(x: key, capacity: cache->capacity);
76 struct bcache_wrapper *node = cache->entries[index];
77
78 while (node) {
79 if (node->key == key) {
80 node->value->access_time = bcache_get_ticks(cache);
81 spin_unlock(&cache->lock, irql);
82 return node->value;
83 }
84 node = node->next;
85 }
86
87 spin_unlock(&cache->lock, irql);
88 return NULL;
89}
90
91static bool can_remove_lba_group(struct bcache *cache, uint64_t base_lba,
92 uint64_t spb) {
93 /* caller must already hold the lock */
94
95 for (uint64_t i = 0; i < spb; i++) {
96 uint64_t key = base_lba + i;
97 uint64_t index = bcache_hash(x: key, capacity: cache->capacity);
98 struct bcache_wrapper *node = cache->entries[index];
99 bool found = false;
100
101 while (node) {
102 if (node->key == key) {
103 found = true;
104 break;
105 }
106 node = node->next;
107 }
108
109 if (i == 0 && !found)
110 return false; /* base_lba must exist */
111 else if (i > 0 && found)
112 return false; /* another lba in the group is still cached */
113 }
114
115 return true;
116}
117
118static bool remove(struct bcache *cache, uint64_t key, uint64_t spb) {
119 enum irql irql = spin_lock(&cache->lock);
120 uint64_t index = bcache_hash(x: key, capacity: cache->capacity);
121
122 struct bcache_wrapper *prev = NULL;
123 struct bcache_wrapper *node = cache->entries[index];
124
125 while (node) {
126 if (node->key == key) {
127 if (prev)
128 prev->next = node->next;
129 else
130 cache->entries[index] = node->next;
131
132 struct bcache_entry *val = node->value;
133 cache->count--;
134 vfree(node);
135
136 bool should_free = false;
137 if (val && key == val->lba && !val->no_evict) {
138 if (can_remove_lba_group(cache, base_lba: key, spb: val->size / spb)) {
139 should_free = true;
140 }
141 }
142
143 if (should_free) {
144 vfree_aligned(val->buffer);
145 vfree(val);
146 }
147
148 spin_unlock(&cache->lock, irql);
149 return true;
150 }
151
152 prev = node;
153 node = node->next;
154 }
155
156 spin_unlock(&cache->lock, irql);
157 return false;
158}
159
160struct bcache_pf_data {
161 struct bcache_entry *new_entry;
162 struct bcache *cache;
163};
164
165static void prefetch_callback(struct bio_request *bio) {
166 struct bcache_pf_data *data = bio->user_data;
167 insert(cache: data->cache, key: bio->lba, value: data->new_entry);
168
169 vfree(data);
170 vfree(bio);
171}
172
173static enum err prefetch(struct block_device *disk, struct bcache *cache,
174 uint64_t lba, uint64_t block_size, uint64_t spb) {
175 uint64_t base_lba = ALIGN_DOWN(lba, spb);
176
177 /* no need to re-fetch existing entry */
178 if (get(cache, key: base_lba))
179 return ERR_EXIST;
180
181 struct bcache_pf_data *pf = vnew(pf);
182 if (!pf)
183 return ERR_NO_MEM;
184
185 struct bio_request *req = bio_create_read(d: disk, lba: base_lba, sectors: spb, size: block_size,
186 cb: prefetch_callback, user: pf, NULL);
187 if (!req)
188 return ERR_NO_MEM;
189
190 pf->cache = cache;
191 pf->new_entry = vnew(pf->new_entry, ALLOC_ZERO);
192 if (!pf->new_entry)
193 return ERR_NO_MEM;
194
195 struct bcache_entry *ent = pf->new_entry;
196
197 ent->lba = lba;
198 ent->size = block_size;
199 ent->dirty = false;
200 ent->no_evict = false;
201 ent->buffer = req->buffer;
202
203 bio_sched_enqueue(disk, req);
204 return ERR_OK;
205}
206
207static bool evict(struct bcache *cache, uint64_t spb) {
208 enum irql irql = spin_lock(&cache->lock);
209
210 uint64_t oldest = UINT64_MAX;
211 uint64_t target_key = 0;
212 bool found = false;
213
214 for (uint64_t i = 0; i < cache->capacity; i++) {
215 struct bcache_wrapper *node = cache->entries[i];
216 while (node) {
217 struct bcache_entry *entry = node->value;
218
219 if (!entry || entry->no_evict ||
220 atomic_load(&entry->refcount) > 0) {
221 node = node->next;
222 continue;
223 }
224
225 if (entry->access_time < oldest) {
226 oldest = entry->access_time;
227 target_key = node->key;
228 found = true;
229 }
230
231 node = node->next;
232 }
233 }
234
235 spin_unlock(&cache->lock, irql);
236
237 if (found)
238 return remove(cache, key: target_key, spb);
239
240 return false;
241}
242
243static void stat(struct bcache *cache, uint64_t *total_dirty_out,
244 uint64_t *total_present_out) {
245 enum irql irql = spin_lock(&cache->lock);
246
247 uint64_t total_dirty = 0;
248 uint64_t total_present = 0;
249
250 for (uint64_t i = 0; i < cache->capacity; i++) {
251 struct bcache_wrapper *node = cache->entries[i];
252 while (node) {
253 if (node->value) {
254 total_present++;
255 if (node->value->dirty)
256 total_dirty++;
257 }
258 node = node->next;
259 }
260 }
261
262 if (total_dirty_out)
263 *total_dirty_out = total_dirty;
264
265 if (total_present_out)
266 *total_present_out = total_present;
267
268 spin_unlock(&cache->lock, irql);
269}
270
271/* TODO: writeback */
272static bool write(struct block_device *d, struct bcache *cache,
273 struct bcache_entry *ent, uint64_t spb) {
274 enum irql irql = spin_lock(&cache->lock);
275
276 bool ret = d->write_sector(d, ent->lba, ent->buffer, spb);
277 uint64_t aligned = ALIGN_DOWN(ent->lba, spb);
278 if (aligned != ent->lba)
279 vfree(ent);
280
281 spin_unlock(&cache->lock, irql);
282 return ret;
283}
284
285static void write_enqueue_cb(struct bio_request *req) {
286 struct bcache_entry *ent = req->user_data;
287
288 ent->dirty = false;
289 ent->request = NULL;
290 bcache_ent_unpin(ent);
291
292 vfree(req);
293}
294
295static void write_queue(struct block_device *d, struct bcache_entry *ent,
296 uint64_t spb, enum bio_request_priority prio) {
297
298 ent->dirty = true;
299
300 struct bio_request *req = bio_create_write(
301 d, lba: ent->lba, sectors: spb, size: ent->size, cb: write_enqueue_cb, user: ent, buf: ent->buffer);
302
303 req->priority = prio;
304 ent->request = req;
305
306 bcache_ent_pin(ent);
307 bio_sched_enqueue(disk: d, req);
308}
309
310void bcache_destroy(struct bcache *cache) {
311 for (uint64_t i = 0; i < cache->capacity; i++) {
312 struct bcache_wrapper *node = cache->entries[i];
313 while (node) {
314 struct bcache_wrapper *next = node->next;
315 if (node->value) {
316 vfree_aligned(node->value->buffer);
317 vfree(node->value);
318 }
319 vfree(node);
320 node = next;
321 }
322 }
323
324 vfree(cache->entries);
325 cache->entries = NULL;
326 cache->capacity = 0;
327 cache->count = 0;
328}
329
330void *bcache_get(struct block_device *disk, uint64_t lba, uint64_t block_size,
331 uint64_t spb, bool no_evict, struct bcache_entry **out_entry) {
332 uint64_t base_lba = ALIGN_DOWN(lba, spb);
333 struct bcache_entry *ent = get(cache: disk->cache, key: base_lba);
334
335 if (!ent)
336 return bcache_create_ent(disk, lba, block_size, sectors_per_block: spb, no_evict,
337 out_entry);
338
339 *out_entry = ent;
340
341 uint64_t offset = (lba - base_lba) * disk->sector_size;
342 return ent->buffer + offset;
343}
344
345bool bcache_insert(struct block_device *disk, uint64_t lba,
346 struct bcache_entry *ent, uint64_t spb) {
347 if (insert(cache: disk->cache, key: lba, value: ent)) {
348 return true;
349 } else {
350 evict(cache: disk->cache, spb);
351 return insert(cache: disk->cache, key: lba, value: ent);
352 }
353}
354
355bool bcache_evict(struct block_device *disk, uint64_t spb) {
356 return evict(cache: disk->cache, spb);
357}
358
359bool bcache_writethrough(struct block_device *disk, struct bcache_entry *ent,
360 uint64_t spb) {
361 return write(d: disk, cache: disk->cache, ent, spb);
362}
363
364void bcache_write_queue(struct block_device *disk, struct bcache_entry *ent,
365 uint64_t spb, enum bio_request_priority prio) {
366 write_queue(d: disk, ent, spb, prio);
367}
368
369void bcache_stat(struct block_device *disk, uint64_t *total_dirty_out,
370 uint64_t *total_present_out) {
371 stat(cache: disk->cache, total_dirty_out, total_present_out);
372}
373
374/* TODO: error code here */
375void *bcache_create_ent(struct block_device *disk, uint64_t lba,
376 uint64_t block_size, uint64_t sectors_per_block,
377 bool no_evict, struct bcache_entry **out_entry) {
378 uint64_t base_lba = ALIGN_DOWN(lba, sectors_per_block);
379
380 struct bcache_entry *ent = get(cache: disk->cache, key: base_lba);
381 if (!ent) {
382 uint8_t *buf =
383 valloc_aligned(PAGE_SIZE, PAGE_SIZE, .flags = ALLOC_FLAGS_PAGEABLE,
384 .behavior = ALLOC_BEHAVIOR_NORMAL);
385 if (!buf)
386 return NULL;
387
388 if (!disk->read_sector(disk, base_lba, buf, sectors_per_block)) {
389 vfree_aligned(buf);
390 *out_entry = NULL;
391 return NULL;
392 }
393
394 ent = vnew(ent, ALLOC_ZERO);
395 if (!ent)
396 return NULL;
397
398 mutex_init(&ent->lock, LOCK_CHKD_THREAD);
399
400 ent->buffer = buf;
401 ent->lba = base_lba;
402 ent->size = block_size;
403 ent->no_evict = no_evict;
404
405 bcache_insert(disk, lba: base_lba, ent, spb: sectors_per_block);
406 }
407
408 *out_entry = ent;
409
410 uint64_t offset = (lba - base_lba) * disk->sector_size;
411 return ent->buffer + offset;
412}
413
414enum err bcache_prefetch_async(struct block_device *disk, uint64_t lba,
415 uint64_t block_size, uint64_t spb) {
416 return prefetch(disk, cache: disk->cache, ALIGN_DOWN(lba, spb), block_size, spb);
417}
418
419void bcache_init(struct bcache *cache, uint64_t capacity) {
420 spinlock_init(&cache->lock);
421 cache->capacity = capacity;
422 cache->count = 0;
423 cache->entries = nofail_vnews(cache->entries, capacity, ALLOC_ZERO);
424}
425