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