cache_key.c

  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
 94	key->off = key_onmedia->off;
 95	key->len = key_onmedia->len;
 96
 97	key->cache_pos.cache_seg = &cache->segments[key_onmedia->cache_seg_id];
 98	key->cache_pos.seg_off = key_onmedia->cache_seg_off;
 99
100	key->seg_gen = key_onmedia->seg_gen;
101	key->flags = key_onmedia->flags;
102
103	if (cache_data_crc_on(cache) &&
104			key_onmedia->data_crc != cache_key_data_crc(key)) {
105		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		return -EIO;
109	}
110
111	return 0;
112}
113
114static void append_last_kset(struct pcache_cache *cache, u32 next_seg)
115{
116	struct pcache_cache_kset_onmedia kset_onmedia = { 0 };
117
118	kset_onmedia.flags |= PCACHE_KSET_FLAGS_LAST;
119	kset_onmedia.next_cache_seg_id = next_seg;
120	kset_onmedia.magic = PCACHE_KSET_MAGIC;
121	kset_onmedia.crc = cache_kset_crc(&kset_onmedia);
122
123	memcpy_flushcache(get_key_head_addr(cache), &kset_onmedia, sizeof(struct pcache_cache_kset_onmedia));
124	pmem_wmb();
125	cache_pos_advance(&cache->key_head, sizeof(struct pcache_cache_kset_onmedia));
126}
127
128int cache_kset_close(struct pcache_cache *cache, struct pcache_cache_kset *kset)
129{
130	struct pcache_cache_kset_onmedia *kset_onmedia;
131	u32 kset_onmedia_size;
132	int ret;
133
134	kset_onmedia = &kset->kset_onmedia;
135
136	if (!kset_onmedia->key_num)
137		return 0;
138
139	kset_onmedia_size = struct_size(kset_onmedia, data, kset_onmedia->key_num);
140
141	spin_lock(&cache->key_head_lock);
142again:
143	/* Reserve space for the last kset */
144	if (cache_seg_remain(&cache->key_head) < kset_onmedia_size + sizeof(struct pcache_cache_kset_onmedia)) {
145		struct pcache_cache_segment *next_seg;
146
147		next_seg = get_cache_segment(cache);
148		if (!next_seg) {
149			ret = -EBUSY;
150			goto out;
151		}
152
153		/* clear outdated kset in next seg */
154		memcpy_flushcache(next_seg->segment.data, &pcache_empty_kset,
155					sizeof(struct pcache_cache_kset_onmedia));
156		append_last_kset(cache, next_seg->cache_seg_id);
157		cache->key_head.cache_seg = next_seg;
158		cache->key_head.seg_off = 0;
159		goto again;
160	}
161
162	kset_onmedia->magic = PCACHE_KSET_MAGIC;
163	kset_onmedia->crc = cache_kset_crc(kset_onmedia);
164
165	/* clear outdated kset after current kset */
166	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	memcpy_flushcache(get_key_head_addr(cache), kset_onmedia, kset_onmedia_size);
170	pmem_wmb();
171
172	/* reset kset_onmedia */
173	memset(kset_onmedia, 0, sizeof(struct pcache_cache_kset_onmedia));
174	cache_pos_advance(&cache->key_head, kset_onmedia_size);
175
176	ret = 0;
177out:
178	spin_unlock(&cache->key_head_lock);
179
180	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 */
195int cache_key_append(struct pcache_cache *cache, struct pcache_cache_key *key, bool force_close)
196{
197	struct pcache_cache_kset *kset;
198	struct pcache_cache_kset_onmedia *kset_onmedia;
199	struct pcache_cache_key_onmedia *key_onmedia;
200	u32 kset_id = get_kset_id(cache, key->off);
201	int ret = 0;
202
203	kset = get_kset(cache, kset_id);
204	kset_onmedia = &kset->kset_onmedia;
205
206	spin_lock(&kset->kset_lock);
207	key_onmedia = &kset_onmedia->data[kset_onmedia->key_num];
208	cache_key_encode(cache, key_onmedia, key);
209
210	/* Check if the current kset has reached the maximum number of keys */
211	if (++kset_onmedia->key_num == PCACHE_KSET_KEYS_MAX || force_close) {
212		/* If full, close the kset */
213		ret = cache_kset_close(cache, kset);
214		if (ret) {
215			kset_onmedia->key_num--;
216			goto out;
217		}
218	} else {
219		/* If not full, queue a delayed work to flush the kset */
220		queue_delayed_work(cache_get_wq(cache), &kset->flush_work, 1 * HZ);
221	}
222out:
223	spin_unlock(&kset->kset_lock);
224
225	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 */
238int cache_subtree_walk(struct pcache_cache_subtree_walk_ctx *ctx)
239{
240	struct pcache_cache_key *key_tmp, *key;
241	struct rb_node *node_tmp;
242	int ret = SUBTREE_WALK_RET_OK;
243
244	key = ctx->key;
245	node_tmp = ctx->start_node;
246
247	while (node_tmp) {
248		if (ctx->walk_done && ctx->walk_done(ctx))
249			break;
250
251		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		if (cache_key_lend(key_tmp) <= cache_key_lstart(key)) {
258			if (ctx->after) {
259				ret = ctx->after(key, key_tmp, ctx);
260				if (ret)
261					goto out;
262			}
263			goto next;
264		}
265
266		/*
267		 * If key_tmp starts after the end of key, stop traversing.
268		 *	  |--------|
269		 * |====|
270		 */
271		if (cache_key_lstart(key_tmp) >= cache_key_lend(key)) {
272			if (ctx->before) {
273				ret = ctx->before(key, key_tmp, ctx);
274				if (ret)
275					goto out;
276			}
277			break;
278		}
279
280		/* Handle overlapping keys */
281		if (cache_key_lstart(key_tmp) >= cache_key_lstart(key)) {
282			/*
283			 * If key_tmp encompasses key.
284			 *     |----------------|	key_tmp
285			 * |===========|		key
286			 */
287			if (cache_key_lend(key_tmp) >= cache_key_lend(key)) {
288				if (ctx->overlap_tail) {
289					ret = ctx->overlap_tail(key, key_tmp, ctx);
290					if (ret)
291						goto out;
292				}
293				break;
294			}
295
296			/*
297			 * If key_tmp is contained within key.
298			 *    |----|		key_tmp
299			 * |==========|		key
300			 */
301			if (ctx->overlap_contain) {
302				ret = ctx->overlap_contain(key, key_tmp, ctx);
303				if (ret)
304					goto out;
305			}
306
307			goto next;
308		}
309
310		/*
311		 * If key_tmp starts before key ends but ends after key.
312		 * |-----------|	key_tmp
313		 *   |====|		key
314		 */
315		if (cache_key_lend(key_tmp) > cache_key_lend(key)) {
316			if (ctx->overlap_contained) {
317				ret = ctx->overlap_contained(key, key_tmp, ctx);
318				if (ret)
319					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		if (ctx->overlap_head) {
330			ret = ctx->overlap_head(key, key_tmp, ctx);
331			if (ret)
332				goto out;
333		}
334next:
335		node_tmp = rb_next(node_tmp);
336	}
337
338out:
339	if (ctx->walk_finally)
340		ret = ctx->walk_finally(ctx, ret);
341
342	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 */
360struct 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	struct rb_node **new, *parent = NULL;
365	struct pcache_cache_key *key_tmp;
366	struct rb_node *prev_node = NULL;
367
368	new = &(cache_subtree->root.rb_node);
369	while (*new) {
370		key_tmp = container_of(*new, struct pcache_cache_key, rb_node);
371		if (cache_key_invalid(key_tmp))
372			list_add(&key_tmp->list_node, delete_key_list);
373
374		parent = *new;
375		if (key_tmp->off >= key->off) {
376			new = &((*new)->rb_left);
377		} else {
378			prev_node = *new;
379			new = &((*new)->rb_right);
380		}
381	}
382
383	if (!prev_node)
384		prev_node = rb_first(&cache_subtree->root);
385
386	if (parentp)
387		*parentp = parent;
388
389	if (newp)
390		*newp = new;
391
392	return prev_node;
393}
394
395static struct pcache_cache_key *get_pre_alloc_key(struct pcache_cache_subtree_walk_ctx *ctx)
396{
397	struct pcache_cache_key *key;
398
399	if (ctx->pre_alloc_key) {
400		key = ctx->pre_alloc_key;
401		ctx->pre_alloc_key = NULL;
402
403		return key;
404	}
405
406	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 */
419static 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	BUG_ON(cache_key_empty(key));
428	if (cache_key_empty(key_tmp)) {
429		cache_key_delete(key_tmp);
430		return SUBTREE_WALK_RET_RESEARCH;
431	}
432
433	cache_key_cutfront(key_tmp, cache_key_lend(key) - cache_key_lstart(key_tmp));
434	if (key_tmp->len == 0) {
435		cache_key_delete(key_tmp);
436		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 */
453static 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	BUG_ON(cache_key_empty(key));
462	cache_key_delete(key_tmp);
463
464	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 */
481static 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	struct pcache_cache_tree *cache_tree = ctx->cache_tree;
485
486	/*
487	 * |-----------|		key_tmp
488	 *   |====|			key
489	 */
490	BUG_ON(cache_key_empty(key));
491	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		cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
496		if (key_tmp->len == 0) {
497			cache_key_delete(key_tmp);
498			return SUBTREE_WALK_RET_RESEARCH;
499		}
500	} else {
501		struct pcache_cache_key *key_fixup;
502		bool need_research = false;
503
504		key_fixup = get_pre_alloc_key(ctx);
505		if (!key_fixup)
506			return SUBTREE_WALK_RET_NEED_KEY;
507
508		cache_key_copy(key_fixup, key_tmp);
509
510		/* Split key_tmp based on the new key's range */
511		cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
512		if (key_tmp->len == 0) {
513			cache_key_delete(key_tmp);
514			need_research = true;
515		}
516
517		/* Create a new portion for key_fixup */
518		cache_key_cutfront(key_fixup, cache_key_lend(key) - cache_key_lstart(key_tmp));
519		if (key_fixup->len == 0) {
520			cache_key_put(key_fixup);
521		} else {
522			/* Insert the new key into the cache */
523			cache_key_insert(cache_tree, key_fixup, false);
524			need_research = true;
525		}
526
527		if (need_research)
528			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 */
546static 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	BUG_ON(cache_key_empty(key));
554	/* Adjust key_tmp by cutting back based on the new key's start */
555	cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));
556	if (key_tmp->len == 0) {
557		/* If the adjusted key_tmp length is zero, delete it */
558		cache_key_delete(key_tmp);
559		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 */
575void cache_key_insert(struct pcache_cache_tree *cache_tree, struct pcache_cache_key *key, bool fixup)
576{
577	struct pcache_cache *cache = cache_tree->cache;
578	struct pcache_cache_subtree_walk_ctx walk_ctx = { 0 };
579	struct rb_node **new, *parent = NULL;
580	struct pcache_cache_subtree *cache_subtree;
581	struct pcache_cache_key *key_tmp = NULL, *key_next;
582	struct rb_node *prev_node = NULL;
583	LIST_HEAD(delete_key_list);
584	int ret;
585
586	cache_subtree = get_subtree(cache_tree, key->off);
587	key->cache_subtree = cache_subtree;
588search:
589	prev_node = cache_subtree_search(cache_subtree, key, &parent, &new, &delete_key_list);
590	if (!list_empty(&delete_key_list)) {
591		/* Remove invalid keys from the delete list */
592		list_for_each_entry_safe(key_tmp, key_next, &delete_key_list, list_node) {
593			list_del_init(&key_tmp->list_node);
594			cache_key_delete(key_tmp);
595		}
596		goto search;
597	}
598
599	if (fixup) {
600		/* Set up the context with the cache, start node, and new key */
601		walk_ctx.cache_tree = cache_tree;
602		walk_ctx.start_node = prev_node;
603		walk_ctx.key = key;
604
605		/* Assign overlap handling functions for different scenarios */
606		walk_ctx.overlap_tail = fixup_overlap_tail;
607		walk_ctx.overlap_head = fixup_overlap_head;
608		walk_ctx.overlap_contain = fixup_overlap_contain;
609		walk_ctx.overlap_contained = fixup_overlap_contained;
610
611		ret = cache_subtree_walk(&walk_ctx);
612		switch (ret) {
613		case SUBTREE_WALK_RET_OK:
614			break;
615		case SUBTREE_WALK_RET_RESEARCH:
616			goto search;
617		case SUBTREE_WALK_RET_NEED_KEY:
618			spin_unlock(&cache_subtree->tree_lock);
619			pcache_dev_debug(CACHE_TO_PCACHE(cache), "allocate pre_alloc_key with GFP_NOIO");
620			walk_ctx.pre_alloc_key = cache_key_alloc(cache_tree, GFP_NOIO);
621			spin_lock(&cache_subtree->tree_lock);
622			goto search;
623		default:
624			BUG();
625		}
626	}
627
628	if (walk_ctx.pre_alloc_key)
629		cache_key_put(walk_ctx.pre_alloc_key);
630
631	/* Link and insert the new key into the red-black tree */
632	rb_link_node(&key->rb_node, parent, new);
633	rb_insert_color(&key->rb_node, &cache_subtree->root);
634}
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 */
645void clean_fn(struct work_struct *work)
646{
647	struct pcache_cache *cache = container_of(work, struct pcache_cache, clean_work);
648	struct pcache_cache_subtree *cache_subtree;
649	struct rb_node *node;
650	struct pcache_cache_key *key;
651	int i, count;
652
653	for (i = 0; i < cache->req_key_tree.n_subtrees; i++) {
654		cache_subtree = &cache->req_key_tree.subtrees[i];
655
656again:
657		if (pcache_is_stopping(CACHE_TO_PCACHE(cache)))
658			return;
659
660		/* Delete up to PCACHE_CLEAN_KEYS_MAX keys in one iteration */
661		count = 0;
662		spin_lock(&cache_subtree->tree_lock);
663		node = rb_first(&cache_subtree->root);
664		while (node) {
665			key = CACHE_KEY(node);
666			node = rb_next(node);
667			if (cache_key_invalid(key)) {
668				count++;
669				cache_key_delete(key);
670			}
671
672			if (count >= PCACHE_CLEAN_KEYS_MAX) {
673				/* Unlock and pause before continuing cleanup */
674				spin_unlock(&cache_subtree->tree_lock);
675				usleep_range(1000, 2000);
676				goto again;
677			}
678		}
679		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 */
694void kset_flush_fn(struct work_struct *work)
695{
696	struct pcache_cache_kset *kset = container_of(work, struct pcache_cache_kset, flush_work.work);
697	struct pcache_cache *cache = kset->cache;
698	int ret;
699
700	if (pcache_is_stopping(CACHE_TO_PCACHE(cache)))
701		return;
702
703	spin_lock(&kset->kset_lock);
704	ret = cache_kset_close(cache, kset);
705	spin_unlock(&kset->kset_lock);
706
707	if (ret) {
708		/* Failed to flush kset, schedule a retry. */
709		queue_delayed_work(cache_get_wq(cache), &kset->flush_work, msecs_to_jiffies(100));
710	}
711}
712
713static int kset_replay(struct pcache_cache *cache, struct pcache_cache_kset_onmedia *kset_onmedia)
714{
715	struct pcache_cache_key_onmedia *key_onmedia;
716	struct pcache_cache_subtree *cache_subtree;
717	struct pcache_cache_key *key;
718	int ret;
719	int i;
720
721	for (i = 0; i < kset_onmedia->key_num; i++) {
722		key_onmedia = &kset_onmedia->data[i];
723
724		key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);
725		ret = cache_key_decode(cache, key_onmedia, key);
726		if (ret) {
727			cache_key_put(key);
728			goto err;
729		}
730
731		__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		if (key->seg_gen < key->cache_pos.cache_seg->gen) {
735			cache_key_put(key);
736		} else {
737			cache_subtree = get_subtree(&cache->req_key_tree, key->off);
738			spin_lock(&cache_subtree->tree_lock);
739			cache_key_insert(&cache->req_key_tree, key, true);
740			spin_unlock(&cache_subtree->tree_lock);
741		}
742
743		cache_seg_get(key->cache_pos.cache_seg);
744	}
745
746	return 0;
747err:
748	return ret;
749}
750
751int cache_replay(struct pcache_cache *cache)
752{
753	struct dm_pcache *pcache = CACHE_TO_PCACHE(cache);
754	struct pcache_cache_pos pos_tail;
755	struct pcache_cache_pos *pos;
756	struct pcache_cache_kset_onmedia *kset_onmedia;
757	u32 to_copy, count = 0;
758	int ret = 0;
759
760	kset_onmedia = kzalloc(PCACHE_KSET_ONMEDIA_SIZE_MAX, GFP_KERNEL);
761	if (!kset_onmedia)
762		return -ENOMEM;
763
764	cache_pos_copy(&pos_tail, &cache->key_tail);
765	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	__set_bit(pos->cache_seg->cache_seg_id, cache->seg_map);
772
773	while (true) {
774		to_copy = min(PCACHE_KSET_ONMEDIA_SIZE_MAX, PCACHE_SEG_SIZE - pos->seg_off);
775		ret = copy_mc_to_kernel(kset_onmedia, cache_pos_addr(pos), to_copy);
776		if (ret) {
777			ret = -EIO;
778			goto out;
779		}
780
781		if (kset_onmedia->magic != PCACHE_KSET_MAGIC ||
782				kset_onmedia->crc != cache_kset_crc(kset_onmedia)) {
783			break;
784		}
785
786		/* Process the last kset and prepare for the next segment. */
787		if (kset_onmedia->flags & PCACHE_KSET_FLAGS_LAST) {
788			struct pcache_cache_segment *next_seg;
789
790			pcache_dev_debug(pcache, "last kset replay, next: %u\n", kset_onmedia->next_cache_seg_id);
791
792			next_seg = &cache->segments[kset_onmedia->next_cache_seg_id];
793
794			pos->cache_seg = next_seg;
795			pos->seg_off = 0;
796
797			__set_bit(pos->cache_seg->cache_seg_id, cache->seg_map);
798			continue;
799		}
800
801		/* Replay the kset and check for errors. */
802		ret = kset_replay(cache, kset_onmedia);
803		if (ret)
804			goto out;
805
806		/* Advance the position after processing the kset. */
807		cache_pos_advance(pos, get_kset_onmedia_size(kset_onmedia));
808		if (++count > 512) {
809			cond_resched();
810			count = 0;
811		}
812	}
813
814	/* Update the key_head position after replaying. */
815	spin_lock(&cache->key_head_lock);
816	cache_pos_copy(&cache->key_head, pos);
817	spin_unlock(&cache->key_head_lock);
818out:
819	kfree(kset_onmedia);
820	return ret;
821}
822
823int cache_tree_init(struct pcache_cache *cache, struct pcache_cache_tree *cache_tree, u32 n_subtrees)
824{
825	int ret;
826	u32 i;
827
828	cache_tree->cache = cache;
829	cache_tree->n_subtrees = n_subtrees;
830
831	ret = mempool_init_slab_pool(&cache_tree->key_pool, 1024, key_cache);
832	if (ret)
833		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	cache_tree->subtrees = kvcalloc(cache_tree->n_subtrees, sizeof(struct pcache_cache_subtree), GFP_KERNEL);
841	if (!cache_tree->subtrees) {
842		ret = -ENOMEM;
843		goto key_pool_exit;
844	}
845
846	for (i = 0; i < cache_tree->n_subtrees; i++) {
847		struct pcache_cache_subtree *cache_subtree = &cache_tree->subtrees[i];
848
849		cache_subtree->root = RB_ROOT;
850		spin_lock_init(&cache_subtree->tree_lock);
851	}
852
853	return 0;
854
855key_pool_exit:
856	mempool_exit(&cache_tree->key_pool);
857err:
858	return ret;
859}
860
861void cache_tree_clear(struct pcache_cache_tree *cache_tree)
862{
863	struct pcache_cache_subtree *cache_subtree;
864	struct rb_node *node;
865	struct pcache_cache_key *key;
866	u32 i;
867
868	for (i = 0; i < cache_tree->n_subtrees; i++) {
869		cache_subtree = &cache_tree->subtrees[i];
870
871		spin_lock(&cache_subtree->tree_lock);
872		node = rb_first(&cache_subtree->root);
873		while (node) {
874			key = CACHE_KEY(node);
875			node = rb_next(node);
876
877			cache_key_delete(key);
878		}
879		spin_unlock(&cache_subtree->tree_lock);
880	}
881}
882
883void cache_tree_exit(struct pcache_cache_tree *cache_tree)
884{
885	cache_tree_clear(cache_tree);
886	kvfree(cache_tree->subtrees);
887	mempool_exit(&cache_tree->key_pool);
888}