projects/linux·blob master · refs

995 lines · 27.6 KiB

1// SPDX-License-Identifier: GPL-2.0-or-later
2#include "cache.h"
3#include "backing_dev.h"
4#include "cache_dev.h"
5#include "dm_pcache.h"
6
7struct pcache_cache_kset_onmedia pcache_empty_kset = { 0 };
8
9void cache_key_init(struct pcache_cache_tree *cache_tree, struct pcache_cache_key *key)
10{
11 kref_init(&key->ref);
12 key->cache_tree = cache_tree;
13 INIT_LIST_HEAD(&key->list_node);
14 RB_CLEAR_NODE(&key->rb_node);
15}
16
17struct pcache_cache_key *cache_key_alloc(struct pcache_cache_tree *cache_tree, gfp_t gfp_mask)
18{
19 struct pcache_cache_key *key;
20
21 key = mempool_alloc(&cache_tree->key_pool, gfp_mask);
22 if (!key)
23 return NULL;
24
25 memset(key, 0, sizeof(struct pcache_cache_key));
26 cache_key_init(cache_tree, key);
27
28 return key;
29}
30
31/**
32 * cache_key_get - Increment the reference count of a cache key.
33 * @key: Pointer to the pcache_cache_key structure.
34 *
35 * This function increments the reference count of the specified cache key,
36 * ensuring that it is not freed while still in use.
37 */
38void cache_key_get(struct pcache_cache_key *key)
39{
40 kref_get(&key->ref);
41}
42
43/**
44 * cache_key_destroy - Free a cache key structure when its reference count drops to zero.
45 * @ref: Pointer to the kref structure.
46 *
47 * This function is called when the reference count of the cache key reaches zero.
48 * It frees the allocated cache key back to the slab cache.
49 */
50static void cache_key_destroy(struct kref *ref)
51{
52 struct pcache_cache_key *key = container_of(ref, struct pcache_cache_key, ref);
53 struct pcache_cache_tree *cache_tree = key->cache_tree;
54
55 mempool_free(key, &cache_tree->key_pool);
56}
57
58void cache_key_put(struct pcache_cache_key *key)
59{
60 kref_put(&key->ref, cache_key_destroy);
61}
62
63void cache_pos_advance(struct pcache_cache_pos *pos, u32 len)
64{
65 /* Ensure enough space remains in the current segment */
66 BUG_ON(cache_seg_remain(pos) < len);
67
68 pos->seg_off += len;
69}
70
71static void cache_key_encode(struct pcache_cache *cache,
72 struct pcache_cache_key_onmedia *key_onmedia,
73 struct pcache_cache_key *key)
74{
75 key_onmedia->off = key->off;
76 key_onmedia->len = key->len;
77
78 key_onmedia->cache_seg_id = key->cache_pos.cache_seg->cache_seg_id;
79 key_onmedia->cache_seg_off = key->cache_pos.seg_off;
80
81 key_onmedia->seg_gen = key->seg_gen;
82 key_onmedia->flags = key->flags;
83
84 if (cache_data_crc_on(cache))
85 key_onmedia->data_crc = cache_key_data_crc(key);
86}
87
88int cache_key_decode(struct pcache_cache *cache,
89 struct pcache_cache_key_onmedia *key_onmedia,
90 struct pcache_cache_key *key)
91{
92 struct dm_pcache *pcache = CACHE_TO_PCACHE(cache);
93 u64 dev_bytes = (u64)cache->dev_size << SECTOR_SHIFT;
94
95 key->off = key_onmedia->off;
96 key->len = key_onmedia->len;
97
98 if (key_onmedia->len == 0 ||
99 key_onmedia->len > dev_bytes ||
100 key_onmedia->off > dev_bytes - key_onmedia->len) {
101 pcache_dev_err(pcache, "key off %llu + len %u exceeds device size\n",
102 key_onmedia->off, key_onmedia->len);
103 return -EIO;
104 }
105
106 if (!cache_seg_id_valid(cache, key_onmedia->cache_seg_id)) {
107 pcache_dev_err(pcache, "invalid cache_seg_id %u in cache key (n_segs %u)\n",
108 key_onmedia->cache_seg_id, cache->n_segs);
109 return -EIO;
110 }
111
112 key->cache_pos.cache_seg = &cache->segments[key_onmedia->cache_seg_id];
113 key->cache_pos.seg_off = key_onmedia->cache_seg_off;
114
115 if ((u64)key->cache_pos.seg_off + key->len >
116 key->cache_pos.cache_seg->segment.data_size) {
117 pcache_dev_err(pcache, "key seg_off %u + len %u exceeds segment data size %u\n",
118 key->cache_pos.seg_off, key->len,
119 key->cache_pos.cache_seg->segment.data_size);
120 return -EIO;
121 }
122
123 key->seg_gen = key_onmedia->seg_gen;
124 key->flags = key_onmedia->flags;
125
126 if (cache_data_crc_on(cache) &&
127 key_onmedia->data_crc != cache_key_data_crc(key)) {
128 pcache_dev_err(pcache, "key: %llu:%u seg %u:%u data_crc error: %x, expected: %x\n",
129 key->off, key->len, key->cache_pos.cache_seg->cache_seg_id,
130 key->cache_pos.seg_off, cache_key_data_crc(key), key_onmedia->data_crc);
131 return -EIO;
132 }
133
134 return 0;
135}
136
137static void append_last_kset(struct pcache_cache *cache, u32 next_seg)
138{
139 struct pcache_cache_kset_onmedia kset_onmedia = { 0 };
140
141 kset_onmedia.flags |= PCACHE_KSET_FLAGS_LAST;
142 kset_onmedia.next_cache_seg_id = next_seg;
143 kset_onmedia.magic = PCACHE_KSET_MAGIC;
144 kset_onmedia.crc = cache_kset_crc(&kset_onmedia);
145
146 memcpy_flushcache(get_key_head_addr(cache), &kset_onmedia, sizeof(struct pcache_cache_kset_onmedia));
147 pmem_wmb();
148 cache_pos_advance(&cache->key_head, sizeof(struct pcache_cache_kset_onmedia));
149}
150
151int cache_kset_close(struct pcache_cache *cache, struct pcache_cache_kset *kset)
152{
153 struct pcache_cache_kset_onmedia *kset_onmedia;
154 u32 kset_onmedia_size;
155 int ret;
156
157 kset_onmedia = &kset->kset_onmedia;
158
159 if (!kset_onmedia->key_num)
160 return 0;
161
162 kset_onmedia_size = struct_size(kset_onmedia, data, kset_onmedia->key_num);
163
164 spin_lock(&cache->key_head_lock);
165again:
166 /* Reserve space for the last kset */
167 if (cache_seg_remain(&cache->key_head) < kset_onmedia_size + sizeof(struct pcache_cache_kset_onmedia)) {
168 struct pcache_cache_segment *next_seg;
169
170 next_seg = get_cache_segment(cache);
171 if (!next_seg) {
172 ret = -EBUSY;
173 goto out;
174 }
175
176 /* clear outdated kset in next seg */
177 memcpy_flushcache(next_seg->segment.data, &pcache_empty_kset,
178 sizeof(struct pcache_cache_kset_onmedia));
179 append_last_kset(cache, next_seg->cache_seg_id);
180 cache->key_head.cache_seg = next_seg;
181 cache->key_head.seg_off = 0;
182 goto again;
183 }
184
185 kset_onmedia->magic = PCACHE_KSET_MAGIC;
186 kset_onmedia->crc = cache_kset_crc(kset_onmedia);
187
188 /* clear outdated kset after current kset */
189 memcpy_flushcache(get_key_head_addr(cache) + kset_onmedia_size, &pcache_empty_kset,
190 sizeof(struct pcache_cache_kset_onmedia));
191 /* write current kset into segment */
192 memcpy_flushcache(get_key_head_addr(cache), kset_onmedia, kset_onmedia_size);
193 pmem_wmb();
194
195 /* reset kset_onmedia */
196 memset(kset_onmedia, 0, sizeof(struct pcache_cache_kset_onmedia));
197 cache_pos_advance(&cache->key_head, kset_onmedia_size);
198
199 ret = 0;
200out:
201 spin_unlock(&cache->key_head_lock);
202
203 return ret;
204}
205
206/**
207 * cache_key_append - Append a cache key to the related kset.
208 * @cache: Pointer to the pcache_cache structure.
209 * @key: Pointer to the cache key structure to append.
210 * @force_close: Need to close current kset if true.
211 *
212 * This function appends a cache key to the appropriate kset. If the kset
213 * is full, it closes the kset. If not, it queues a flush work to write
214 * the kset to media.
215 *
216 * Returns 0 on success, or a negative error code on failure.
217 */
218int cache_key_append(struct pcache_cache *cache, struct pcache_cache_key *key, bool force_close)
219{
220 struct pcache_cache_kset *kset;
221 struct pcache_cache_kset_onmedia *kset_onmedia;
222 struct pcache_cache_key_onmedia *key_onmedia;
223 u32 kset_id = get_kset_id(cache, key->off);
224 int ret = 0;
225
226 kset = get_kset(cache, kset_id);
227 kset_onmedia = &kset->kset_onmedia;
228
229 spin_lock(&kset->kset_lock);
230 key_onmedia = &kset_onmedia->data[kset_onmedia->key_num];
231 cache_key_encode(cache, key_onmedia, key);
232
233 /* Check if the current kset has reached the maximum number of keys */
234 if (++kset_onmedia->key_num == PCACHE_KSET_KEYS_MAX || force_close) {
235 /* If full, close the kset */
236 ret = cache_kset_close(cache, kset);
237 if (ret) {
238 kset_onmedia->key_num--;
239 goto out;
240 }
241 } else {
242 /* If not full, queue a delayed work to flush the kset */
243 queue_delayed_work(cache_get_wq(cache), &kset->flush_work, 1 * HZ);
244 }
245out:
246 spin_unlock(&kset->kset_lock);
247
248 return ret;
249}
250
251/**
252 * cache_subtree_walk - Traverse the cache tree.
253 * @ctx: Pointer to the context structure for traversal.
254 *
255 * This function traverses the cache tree starting from the specified node.
256 * It calls the appropriate callback functions based on the relationships
257 * between the keys in the cache tree.
258 *
259 * Returns 0 on success, or a negative error code on failure.
260 */
261int cache_subtree_walk(struct pcache_cache_subtree_walk_ctx *ctx)
262{
263 struct pcache_cache_key *key_tmp, *key;
264 struct rb_node *node_tmp;
265 int ret = SUBTREE_WALK_RET_OK;
266
267 key = ctx->key;
268 node_tmp = ctx->start_node;
269
270 while (node_tmp) {
271 if (ctx->walk_done && ctx->walk_done(ctx))
272 break;
273
274 key_tmp = CACHE_KEY(node_tmp);
275 /*
276 * If key_tmp ends before the start of key, continue to the next node.
277 * |----------|
278 * |=====|
279 */
280 if (cache_key_lend(key_tmp) <= cache_key_lstart(key)) {
281 if (ctx->after) {
282 ret = ctx->after(key, key_tmp, ctx);
283 if (ret)
284 goto out;
285 }
286 goto next;
287 }
288
289 /*
290 * If key_tmp starts after the end of key, stop traversing.
291 * |--------|
292 * |====|
293 */
294 if (cache_key_lstart(key_tmp) >= cache_key_lend(key)) {
295 if (ctx->before) {
296 ret = ctx->before(key, key_tmp, ctx);
297 if (ret)
298 goto out;
299 }
300 break;
301 }
302
303 /* Handle overlapping keys */
304 if (cache_key_lstart(key_tmp) >= cache_key_lstart(key)) {
305 /*
306 * If key_tmp encompasses key.
307 * |----------------| key_tmp
308 * |===========| key
309 */
310 if (cache_key_lend(key_tmp) >= cache_key_lend(key)) {
311 if (ctx->overlap_tail) {
312 ret = ctx->overlap_tail(key, key_tmp, ctx);
313 if (ret)
314 goto out;
315 }
316 break;
317 }
318
319 /*
320 * If key_tmp is contained within key.
321 * |----| key_tmp
322 * |==========| key
323 */
324 if (ctx->overlap_contain) {
325 ret = ctx->overlap_contain(key, key_tmp, ctx);
326 if (ret)
327 goto out;
328 }
329
330 goto next;
331 }
332
333 /*
334 * If key_tmp starts before key ends but ends after key.
335 * |-----------| key_tmp
336 * |====| key
337 */
338 if (cache_key_lend(key_tmp) > cache_key_lend(key)) {
339 if (ctx->overlap_contained) {
340 ret = ctx->overlap_contained(key, key_tmp, ctx);
341 if (ret)
342 goto out;
343 }
344 break;
345 }
346
347 /*
348 * If key_tmp starts before key and ends within key.
349 * |--------| key_tmp
350 * |==========| key
351 */
352 if (ctx->overlap_head) {
353 ret = ctx->overlap_head(key, key_tmp, ctx);
354 if (ret)
355 goto out;
356 }
357next:
358 node_tmp = rb_next(node_tmp);
359 }
360
361out:
362 if (ctx->walk_finally)
363 ret = ctx->walk_finally(ctx, ret);
364
365 return ret;
366}
367
368/**
369 * cache_subtree_search - Search for a key in the cache tree.
370 * @cache_subtree: Pointer to the cache tree structure.
371 * @key: Pointer to the cache key to search for.
372 * @parentp: Pointer to store the parent node of the found node.
373 * @newp: Pointer to store the location where the new node should be inserted.
374 * @delete_key_list: List to collect invalid keys for deletion.
375 *
376 * This function searches the cache tree for a specific key and returns
377 * the node that is the predecessor of the key, or first node if the key is
378 * less than all keys in the tree. If any invalid keys are found during
379 * the search, they are added to the delete_key_list for later cleanup.
380 *
381 * Returns a pointer to the previous node.
382 */
383struct rb_node *cache_subtree_search(struct pcache_cache_subtree *cache_subtree, struct pcache_cache_key *key,
384 struct rb_node **parentp, struct rb_node ***newp,
385 struct list_head *delete_key_list)
386{
387 struct rb_node **new, *parent = NULL;
388 struct pcache_cache_key *key_tmp;
389 struct rb_node *prev_node = NULL;
390
391 new = &(cache_subtree->root.rb_node);
392 while (*new) {
393 key_tmp = container_of(*new, struct pcache_cache_key, rb_node);
394 if (cache_key_invalid(key_tmp))
395 list_add(&key_tmp->list_node, delete_key_list);
396
397 parent = *new;
398 if (key_tmp->off >= key->off) {
399 new = &((*new)->rb_left);
400 } else {
401 prev_node = *new;
402 new = &((*new)->rb_right);
403 }
404 }
405
406 if (!prev_node)
407 prev_node = rb_first(&cache_subtree->root);
408
409 if (parentp)
410 *parentp = parent;
411
412 if (newp)
413 *newp = new;
414
415 return prev_node;
416}
417
418static struct pcache_cache_key *get_pre_alloc_key(struct pcache_cache_subtree_walk_ctx *ctx)
419{
420 struct pcache_cache_key *key;
421
422 if (ctx->pre_alloc_key) {
423 key = ctx->pre_alloc_key;
424 ctx->pre_alloc_key = NULL;
425
426 return key;
427 }
428
429 return cache_key_alloc(ctx->cache_tree, GFP_NOWAIT);
430}
431
432/**
433 * fixup_overlap_tail - Adjust the key when it overlaps at the tail.
434 * @key: Pointer to the new cache key being inserted.
435 * @key_tmp: Pointer to the existing key that overlaps.
436 * @ctx: Pointer to the context for walking the cache tree.
437 *
438 * This function modifies the existing key (key_tmp) when there is an
439 * overlap at the tail with the new key. If the modified key becomes
440 * empty, it is deleted.
441 */
442static int fixup_overlap_tail(struct pcache_cache_key *key,
443 struct pcache_cache_key *key_tmp,
444 struct pcache_cache_subtree_walk_ctx *ctx)
445{
446 /*
447 * |----------------| key_tmp
448 * |===========| key
449 */
450 BUG_ON(cache_key_empty(key));
451 if (cache_key_empty(key_tmp)) {
452 cache_key_delete(key_tmp);
453 return SUBTREE_WALK_RET_RESEARCH;
454 }
455
456 cache_key_cutfront(key_tmp, cache_key_lend(key) - cache_key_lstart(key_tmp));
457 if (key_tmp->len == 0) {
458 cache_key_delete(key_tmp);
459 return SUBTREE_WALK_RET_RESEARCH;
460 }
461
462 return SUBTREE_WALK_RET_OK;
463}
464
465/**
466 * fixup_overlap_contain - Handle case where new key completely contains an existing key.
467 * @key: Pointer to the new cache key being inserted.
468 * @key_tmp: Pointer to the existing key that is being contained.
469 * @ctx: Pointer to the context for walking the cache tree.
470 *
471 * This function deletes the existing key (key_tmp) when the new key
472 * completely contains it. It returns SUBTREE_WALK_RET_RESEARCH to indicate that the
473 * tree structure may have changed, necessitating a re-insertion of
474 * the new key.
475 */
476static int fixup_overlap_contain(struct pcache_cache_key *key,
477 struct pcache_cache_key *key_tmp,
478 struct pcache_cache_subtree_walk_ctx *ctx)
479{
480 /*
481 * |----| key_tmp
482 * |==========| key
483 */
484 BUG_ON(cache_key_empty(key));
485 cache_key_delete(key_tmp);
486
487 return SUBTREE_WALK_RET_RESEARCH;
488}
489
490/**
491 * fixup_overlap_contained - Handle overlap when a new key is contained in an existing key.
492 * @key: The new cache key being inserted.
493 * @key_tmp: The existing cache key that overlaps with the new key.
494 * @ctx: Context for the cache tree walk.
495 *
496 * This function adjusts the existing key if the new key is contained
497 * within it. If the existing key is empty, it indicates a placeholder key
498 * that was inserted during a miss read. This placeholder will later be
499 * updated with real data from the backing_dev, making it no longer an empty key.
500 *
501 * If we delete key or insert a key, the structure of the entire cache tree may change,
502 * requiring a full research of the tree to find a new insertion point.
503 */
504static int fixup_overlap_contained(struct pcache_cache_key *key,
505 struct pcache_cache_key *key_tmp, struct pcache_cache_subtree_walk_ctx *ctx)
506{
507 struct pcache_cache_tree *cache_tree = ctx->cache_tree;
508
509 /*
510 * |-----------| key_tmp
511 * |====| key
512 */
513 BUG_ON(cache_key_empty(key));
514 if (cache_key_empty(key_tmp)) {
515 /* If key_tmp is empty, don't split it;
516 * it's a placeholder key for miss reads that will be updated later.
517 */
518 cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
519 if (key_tmp->len == 0) {
520 cache_key_delete(key_tmp);
521 return SUBTREE_WALK_RET_RESEARCH;
522 }
523 } else {
524 struct pcache_cache_key *key_fixup;
525 bool need_research = false;
526
527 key_fixup = get_pre_alloc_key(ctx);
528 if (!key_fixup)
529 return SUBTREE_WALK_RET_NEED_KEY;
530
531 cache_key_copy(key_fixup, key_tmp);
532
533 /* Split key_tmp based on the new key's range */
534 cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
535 if (key_tmp->len == 0) {
536 cache_key_delete(key_tmp);
537 need_research = true;
538 }
539
540 /* Create a new portion for key_fixup */
541 cache_key_cutfront(key_fixup, cache_key_lend(key) - cache_key_lstart(key_tmp));
542 if (key_fixup->len == 0) {
543 cache_key_put(key_fixup);
544 } else {
545 /* Insert the new key into the cache */
546 cache_key_insert(cache_tree, key_fixup, false);
547 need_research = true;
548 }
549
550 if (need_research)
551 return SUBTREE_WALK_RET_RESEARCH;
552 }
553
554 return SUBTREE_WALK_RET_OK;
555}
556
557/**
558 * fixup_overlap_head - Handle overlap when a new key overlaps with the head of an existing key.
559 * @key: The new cache key being inserted.
560 * @key_tmp: The existing cache key that overlaps with the new key.
561 * @ctx: Context for the cache tree walk.
562 *
563 * This function adjusts the existing key if the new key overlaps
564 * with the beginning of it. If the resulting key length is zero
565 * after the adjustment, the key is deleted. This indicates that
566 * the key no longer holds valid data and requires the tree to be
567 * re-researched for a new insertion point.
568 */
569static int fixup_overlap_head(struct pcache_cache_key *key,
570 struct pcache_cache_key *key_tmp, struct pcache_cache_subtree_walk_ctx *ctx)
571{
572 /*
573 * |--------| key_tmp
574 * |==========| key
575 */
576 BUG_ON(cache_key_empty(key));
577 /* Adjust key_tmp by cutting back based on the new key's start */
578 cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
579 if (key_tmp->len == 0) {
580 /* If the adjusted key_tmp length is zero, delete it */
581 cache_key_delete(key_tmp);
582 return SUBTREE_WALK_RET_RESEARCH;
583 }
584
585 return SUBTREE_WALK_RET_OK;
586}
587
588/**
589 * cache_key_insert - Insert a new cache key into the cache tree.
590 * @cache_tree: Pointer to the cache_tree structure.
591 * @key: The cache key to insert.
592 * @fixup: Indicates if this is a new key being inserted.
593 *
594 * This function searches for the appropriate location to insert
595 * a new cache key into the cache tree. It handles key overlaps
596 * and ensures any invalid keys are removed before insertion.
597 */
598void cache_key_insert(struct pcache_cache_tree *cache_tree, struct pcache_cache_key *key, bool fixup)
599{
600 struct pcache_cache *cache = cache_tree->cache;
601 struct pcache_cache_subtree_walk_ctx walk_ctx = { 0 };
602 struct rb_node **new, *parent = NULL;
603 struct pcache_cache_subtree *cache_subtree;
604 struct pcache_cache_key *key_tmp = NULL, *key_next;
605 struct rb_node *prev_node = NULL;
606 LIST_HEAD(delete_key_list);
607 int ret;
608
609 cache_subtree = get_subtree(cache_tree, key->off);
610 key->cache_subtree = cache_subtree;
611search:
612 prev_node = cache_subtree_search(cache_subtree, key, &parent, &new, &delete_key_list);
613 if (!list_empty(&delete_key_list)) {
614 /* Remove invalid keys from the delete list */
615 list_for_each_entry_safe(key_tmp, key_next, &delete_key_list, list_node) {
616 list_del_init(&key_tmp->list_node);
617 cache_key_delete(key_tmp);
618 }
619 goto search;
620 }
621
622 if (fixup) {
623 /* Set up the context with the cache, start node, and new key */
624 walk_ctx.cache_tree = cache_tree;
625 walk_ctx.start_node = prev_node;
626 walk_ctx.key = key;
627
628 /* Assign overlap handling functions for different scenarios */
629 walk_ctx.overlap_tail = fixup_overlap_tail;
630 walk_ctx.overlap_head = fixup_overlap_head;
631 walk_ctx.overlap_contain = fixup_overlap_contain;
632 walk_ctx.overlap_contained = fixup_overlap_contained;
633
634 ret = cache_subtree_walk(&walk_ctx);
635 switch (ret) {
636 case SUBTREE_WALK_RET_OK:
637 break;
638 case SUBTREE_WALK_RET_RESEARCH:
639 goto search;
640 case SUBTREE_WALK_RET_NEED_KEY:
641 spin_unlock(&cache_subtree->tree_lock);
642 pcache_dev_debug(CACHE_TO_PCACHE(cache), "allocate pre_alloc_key with GFP_NOIO");
643 walk_ctx.pre_alloc_key = cache_key_alloc(cache_tree, GFP_NOIO);
644 spin_lock(&cache_subtree->tree_lock);
645 goto search;
646 default:
647 BUG();
648 }
649 }
650
651 if (walk_ctx.pre_alloc_key)
652 cache_key_put(walk_ctx.pre_alloc_key);
653
654 /* Link and insert the new key into the red-black tree */
655 rb_link_node(&key->rb_node, parent, new);
656 rb_insert_color(&key->rb_node, &cache_subtree->root);
657}
658
659/**
660 * clean_fn - Cleanup function to remove invalid keys from the cache tree.
661 * @work: Pointer to the work_struct associated with the cleanup.
662 *
663 * This function cleans up invalid keys from the cache tree in the background
664 * after a cache segment has been invalidated during cache garbage collection.
665 * It processes a maximum of PCACHE_CLEAN_KEYS_MAX keys per iteration and holds
666 * the tree lock to ensure thread safety.
667 */
668void clean_fn(struct work_struct *work)
669{
670 struct pcache_cache *cache = container_of(work, struct pcache_cache, clean_work);
671 struct pcache_cache_subtree *cache_subtree;
672 struct rb_node *node;
673 struct pcache_cache_key *key;
674 int i, count;
675
676 for (i = 0; i < cache->req_key_tree.n_subtrees; i++) {
677 cache_subtree = &cache->req_key_tree.subtrees[i];
678
679again:
680 if (pcache_is_stopping(CACHE_TO_PCACHE(cache)))
681 return;
682
683 /* Delete up to PCACHE_CLEAN_KEYS_MAX keys in one iteration */
684 count = 0;
685 spin_lock(&cache_subtree->tree_lock);
686 node = rb_first(&cache_subtree->root);
687 while (node) {
688 key = CACHE_KEY(node);
689 node = rb_next(node);
690 if (cache_key_invalid(key)) {
691 count++;
692 cache_key_delete(key);
693 }
694
695 if (count >= PCACHE_CLEAN_KEYS_MAX) {
696 /* Unlock and pause before continuing cleanup */
697 spin_unlock(&cache_subtree->tree_lock);
698 usleep_range(1000, 2000);
699 goto again;
700 }
701 }
702 spin_unlock(&cache_subtree->tree_lock);
703 }
704}
705
706/*
707 * kset_flush_fn - Flush work for a cache kset.
708 *
709 * This function is called when a kset flush work is queued from
710 * cache_key_append(). If the kset is full, it will be closed
711 * immediately. If not, the flush work will be queued for later closure.
712 *
713 * If cache_kset_close detects that a new segment is required to store
714 * the kset and there are no available segments, it will return an error.
715 * In this scenario, a retry will be attempted.
716 */
717void kset_flush_fn(struct work_struct *work)
718{
719 struct pcache_cache_kset *kset = container_of(work, struct pcache_cache_kset, flush_work.work);
720 struct pcache_cache *cache = kset->cache;
721 int ret;
722
723 if (pcache_is_stopping(CACHE_TO_PCACHE(cache)))
724 return;
725
726 spin_lock(&kset->kset_lock);
727 ret = cache_kset_close(cache, kset);
728 spin_unlock(&kset->kset_lock);
729
730 if (ret) {
731 /* Failed to flush kset, schedule a retry. */
732 queue_delayed_work(cache_get_wq(cache), &kset->flush_work, msecs_to_jiffies(100));
733 }
734}
735
736static int kset_replay(struct pcache_cache *cache, struct pcache_cache_kset_onmedia *kset_onmedia)
737{
738 struct pcache_cache_key_onmedia *key_onmedia;
739 struct pcache_cache_subtree *cache_subtree;
740 struct pcache_cache_key *key;
741 int ret;
742 int i;
743
744 for (i = 0; i < kset_onmedia->key_num; i++) {
745 key_onmedia = &kset_onmedia->data[i];
746
747 key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);
748 ret = cache_key_decode(cache, key_onmedia, key);
749 if (ret) {
750 cache_key_put(key);
751 goto err;
752 }
753
754 /* Check if the segment generation is valid for insertion. */
755 if (key->seg_gen < key->cache_pos.cache_seg->gen) {
756 cache_key_put(key);
757 continue;
758 }
759
760 __set_bit(key->cache_pos.cache_seg->cache_seg_id, cache->seg_map);
761 cache_subtree = get_subtree(&cache->req_key_tree, key->off);
762 spin_lock(&cache_subtree->tree_lock);
763 cache_key_insert(&cache->req_key_tree, key, true);
764 spin_unlock(&cache_subtree->tree_lock);
765 cache_seg_get(key->cache_pos.cache_seg);
766 }
767
768 return 0;
769err:
770 return ret;
771}
772
773int cache_replay(struct pcache_cache *cache)
774{
775 struct dm_pcache *pcache = CACHE_TO_PCACHE(cache);
776 struct pcache_cache_pos pos_tail;
777 struct pcache_cache_pos *pos;
778 struct pcache_cache_kset_onmedia *kset_onmedia;
779 u32 to_copy, count = 0, last_hops = 0;
780 int ret = 0;
781
782 kset_onmedia = kzalloc(PCACHE_KSET_ONMEDIA_SIZE_MAX, GFP_KERNEL);
783 if (!kset_onmedia)
784 return -ENOMEM;
785
786 cache_pos_copy(&pos_tail, &cache->key_tail);
787 pos = &pos_tail;
788
789 /*
790 * In cache replaying stage, there is no other one will access
791 * cache->seg_map, so we can set bit here without cache->seg_map_lock.
792 */
793 __set_bit(pos->cache_seg->cache_seg_id, cache->seg_map);
794
795 while (true) {
796 to_copy = min(PCACHE_KSET_ONMEDIA_SIZE_MAX, cache_seg_remain(pos));
797 ret = copy_mc_to_kernel(kset_onmedia, cache_pos_addr(pos), to_copy);
798 if (ret) {
799 ret = -EIO;
800 goto out;
801 }
802
803 if (!kset_onmedia_valid(kset_onmedia) ||
804 kset_onmedia->crc != cache_kset_crc(kset_onmedia)) {
805 break;
806 }
807
808 /* Process the last kset and prepare for the next segment. */
809 if (kset_onmedia->flags & PCACHE_KSET_FLAGS_LAST) {
810 struct pcache_cache_segment *next_seg;
811
812 pcache_dev_debug(pcache, "last kset replay, next: %u\n", kset_onmedia->next_cache_seg_id);
813
814 if (!cache_seg_id_valid(cache, kset_onmedia->next_cache_seg_id)) {
815 ret = -EIO;
816 goto out;
817 }
818
819 if (++last_hops > cache->n_segs) {
820 ret = -EIO;
821 goto out;
822 }
823
824 next_seg = &cache->segments[kset_onmedia->next_cache_seg_id];
825
826 pos->cache_seg = next_seg;
827 pos->seg_off = 0;
828
829 __set_bit(pos->cache_seg->cache_seg_id, cache->seg_map);
830 continue;
831 }
832
833 /* Replay the kset and check for errors. */
834 if (get_kset_onmedia_size(kset_onmedia) > cache_seg_remain(pos)) {
835 ret = -EIO;
836 goto out;
837 }
838
839 ret = kset_replay(cache, kset_onmedia);
840 if (ret)
841 goto out;
842
843 /* Advance the position after processing the kset. */
844 cache_pos_advance(pos, get_kset_onmedia_size(kset_onmedia));
845 if (++count > 512) {
846 cond_resched();
847 count = 0;
848 }
849 }
850
851 /* Update the key_head position after replaying. */
852 spin_lock(&cache->key_head_lock);
853 cache_pos_copy(&cache->key_head, pos);
854 spin_unlock(&cache->key_head_lock);
855out:
856 kfree(kset_onmedia);
857 return ret;
858}
859
860/*
861 * cache_verify_dirty_tail - reject a persisted dirty_tail whose last-kset
862 * chain does not terminate.
863 *
864 * dirty_tail is decoded independently of the key_tail chain cache_replay()
865 * walks, so replay's hop cap does not cover it. A crafted chain that loops
866 * back on itself makes the writeback worker re-arm forever; walk it once here
867 * with the same cap and fail the load if it does not end within n_segs hops.
868 */
869int cache_verify_dirty_tail(struct pcache_cache *cache)
870{
871 struct pcache_cache_pos pos;
872 struct pcache_cache_kset_onmedia *kset_onmedia;
873 u32 to_copy, last_hops = 0, count = 0;
874 int ret = 0;
875
876 kset_onmedia = kzalloc(PCACHE_KSET_ONMEDIA_SIZE_MAX, GFP_KERNEL);
877 if (!kset_onmedia)
878 return -ENOMEM;
879
880 cache_pos_copy(&pos, &cache->dirty_tail);
881
882 while (true) {
883 to_copy = min(PCACHE_KSET_ONMEDIA_SIZE_MAX, cache_seg_remain(&pos));
884 ret = copy_mc_to_kernel(kset_onmedia, cache_pos_addr(&pos), to_copy);
885 if (ret) {
886 ret = -EIO;
887 goto out;
888 }
889
890 /* A missing, short or corrupt kset is the normal end of the chain. */
891 if (!kset_onmedia_valid(kset_onmedia) ||
892 kset_onmedia->crc != cache_kset_crc(kset_onmedia)) {
893 ret = 0;
894 goto out;
895 }
896
897 if (kset_onmedia->flags & PCACHE_KSET_FLAGS_LAST) {
898 if (!cache_seg_id_valid(cache, kset_onmedia->next_cache_seg_id)) {
899 ret = -EIO;
900 goto out;
901 }
902
903 if (++last_hops > cache->n_segs) {
904 ret = -EIO;
905 goto out;
906 }
907
908 pos.cache_seg = &cache->segments[kset_onmedia->next_cache_seg_id];
909 pos.seg_off = 0;
910 continue;
911 }
912
913 if (get_kset_onmedia_size(kset_onmedia) > cache_seg_remain(&pos)) {
914 ret = -EIO;
915 goto out;
916 }
917
918 cache_pos_advance(&pos, get_kset_onmedia_size(kset_onmedia));
919 if (++count > 512) {
920 cond_resched();
921 count = 0;
922 }
923 }
924out:
925 kfree(kset_onmedia);
926 return ret;
927}
928
929int cache_tree_init(struct pcache_cache *cache, struct pcache_cache_tree *cache_tree, u32 n_subtrees)
930{
931 int ret;
932 u32 i;
933
934 cache_tree->cache = cache;
935 cache_tree->n_subtrees = n_subtrees;
936
937 ret = mempool_init_slab_pool(&cache_tree->key_pool, 1024, key_cache);
938 if (ret)
939 goto err;
940
941 /*
942 * Allocate and initialize the subtrees array.
943 * Each element is a cache tree structure that contains
944 * an RB tree root and a spinlock for protecting its contents.
945 */
946 cache_tree->subtrees = kvzalloc_objs(struct pcache_cache_subtree,
947 cache_tree->n_subtrees);
948 if (!cache_tree->subtrees) {
949 ret = -ENOMEM;
950 goto key_pool_exit;
951 }
952
953 for (i = 0; i < cache_tree->n_subtrees; i++) {
954 struct pcache_cache_subtree *cache_subtree = &cache_tree->subtrees[i];
955
956 cache_subtree->root = RB_ROOT;
957 spin_lock_init(&cache_subtree->tree_lock);
958 }
959
960 return 0;
961
962key_pool_exit:
963 mempool_exit(&cache_tree->key_pool);
964err:
965 return ret;
966}
967
968void cache_tree_clear(struct pcache_cache_tree *cache_tree)
969{
970 struct pcache_cache_subtree *cache_subtree;
971 struct rb_node *node;
972 struct pcache_cache_key *key;
973 u32 i;
974
975 for (i = 0; i < cache_tree->n_subtrees; i++) {
976 cache_subtree = &cache_tree->subtrees[i];
977
978 spin_lock(&cache_subtree->tree_lock);
979 node = rb_first(&cache_subtree->root);
980 while (node) {
981 key = CACHE_KEY(node);
982 node = rb_next(node);
983
984 cache_key_delete(key);
985 }
986 spin_unlock(&cache_subtree->tree_lock);
987 }
988}
989
990void cache_tree_exit(struct pcache_cache_tree *cache_tree)
991{
992 cache_tree_clear(cache_tree);
993 kvfree(cache_tree->subtrees);
994 mempool_exit(&cache_tree->key_pool);
995}