9 void cache_key_init(struct pcache_cache_tree *cache_tree, struct pcache_cache_key *key)  in cache_key_init()  argument
11 	kref_init(&key->ref);  in cache_key_init()
12 	key->cache_tree = cache_tree;  in cache_key_init()
13 	INIT_LIST_HEAD(&key->list_node);  in cache_key_init()
14 	RB_CLEAR_NODE(&key->rb_node);  in cache_key_init()
19 	struct pcache_cache_key *key;  in cache_key_alloc()  local
21 	key = mempool_alloc(&cache_tree->key_pool, gfp_mask);  in cache_key_alloc()
22 	if (!key)  in cache_key_alloc()
25 	memset(key, 0, sizeof(struct pcache_cache_key));  in cache_key_alloc()
26 	cache_key_init(cache_tree, key);  in cache_key_alloc()
28 	return key;  in cache_key_alloc()
32  * cache_key_get - Increment the reference count of a cache key.
33  * @key: Pointer to the pcache_cache_key structure.
35  * This function increments the reference count of the specified cache key,
38 void cache_key_get(struct pcache_cache_key *key)  in cache_key_get()  argument
40 	kref_get(&key->ref);  in cache_key_get()
44  * cache_key_destroy - Free a cache key structure when its reference count drops to zero.
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.
52 	struct pcache_cache_key *key = container_of(ref, struct pcache_cache_key, ref);  in cache_key_destroy()  local
53 	struct pcache_cache_tree *cache_tree = key->cache_tree;  in cache_key_destroy()
55 	mempool_free(key, &cache_tree->key_pool);  in cache_key_destroy()
58 void cache_key_put(struct pcache_cache_key *key)  in cache_key_put()  argument
60 	kref_put(&key->ref, cache_key_destroy);  in cache_key_put()
73 			     struct pcache_cache_key *key)  in cache_key_encode()  argument
75 	key_onmedia->off = key->off;  in cache_key_encode()
76 	key_onmedia->len = key->len;  in cache_key_encode()
78 	key_onmedia->cache_seg_id = key->cache_pos.cache_seg->cache_seg_id;  in cache_key_encode()
79 	key_onmedia->cache_seg_off = key->cache_pos.seg_off;  in cache_key_encode()
81 	key_onmedia->seg_gen = key->seg_gen;  in cache_key_encode()
82 	key_onmedia->flags = key->flags;  in cache_key_encode()
85 		key_onmedia->data_crc = cache_key_data_crc(key);  in cache_key_encode()
90 			struct pcache_cache_key *key)  in cache_key_decode()  argument
94 	key->off = key_onmedia->off;  in cache_key_decode()
95 	key->len = key_onmedia->len;  in cache_key_decode()
97 	key->cache_pos.cache_seg = &cache->segments[key_onmedia->cache_seg_id];  in cache_key_decode()
98 	key->cache_pos.seg_off = key_onmedia->cache_seg_off;  in cache_key_decode()
100 	key->seg_gen = key_onmedia->seg_gen;  in cache_key_decode()
101 	key->flags = key_onmedia->flags;  in cache_key_decode()
104 			key_onmedia->data_crc != cache_key_data_crc(key)) {  in cache_key_decode()
105 		pcache_dev_err(pcache, "key: %llu:%u seg %u:%u data_crc error: %x, expected: %x\n",  in cache_key_decode()
106 				key->off, key->len, key->cache_pos.cache_seg->cache_seg_id,  in cache_key_decode()
107 				key->cache_pos.seg_off, cache_key_data_crc(key), key_onmedia->data_crc);  in cache_key_decode()
184  * cache_key_append - Append a cache key to the related kset.
186  * @key: Pointer to the cache key structure to append.
189  * This function appends a cache key to the appropriate kset. If the kset
195 int cache_key_append(struct pcache_cache *cache, struct pcache_cache_key *key, bool force_close)  in cache_key_append()  argument
200 	u32 kset_id = get_kset_id(cache, key->off);  in cache_key_append()
208 	cache_key_encode(cache, key_onmedia, key);  in cache_key_append()
240 	struct pcache_cache_key *key_tmp, *key;  in cache_subtree_walk()  local
244 	key = ctx->key;  in cache_subtree_walk()
253 		 * If key_tmp ends before the start of key, continue to the next node.  in cache_subtree_walk()
257 		if (cache_key_lend(key_tmp) <= cache_key_lstart(key)) {  in cache_subtree_walk()
259 				ret = ctx->after(key, key_tmp, ctx);  in cache_subtree_walk()
267 		 * If key_tmp starts after the end of key, stop traversing.  in cache_subtree_walk()
271 		if (cache_key_lstart(key_tmp) >= cache_key_lend(key)) {  in cache_subtree_walk()
273 				ret = ctx->before(key, key_tmp, ctx);  in cache_subtree_walk()
281 		if (cache_key_lstart(key_tmp) >= cache_key_lstart(key)) {  in cache_subtree_walk()
283 			 * If key_tmp encompasses key.  in cache_subtree_walk()
285 			 * |===========|		key  in cache_subtree_walk()
287 			if (cache_key_lend(key_tmp) >= cache_key_lend(key)) {  in cache_subtree_walk()
289 					ret = ctx->overlap_tail(key, key_tmp, ctx);  in cache_subtree_walk()
297 			 * If key_tmp is contained within key.  in cache_subtree_walk()
299 			 * |==========|		key  in cache_subtree_walk()
302 				ret = ctx->overlap_contain(key, key_tmp, ctx);  in cache_subtree_walk()
311 		 * If key_tmp starts before key ends but ends after key.  in cache_subtree_walk()
313 		 *   |====|		key  in cache_subtree_walk()
315 		if (cache_key_lend(key_tmp) > cache_key_lend(key)) {  in cache_subtree_walk()
317 				ret = ctx->overlap_contained(key, key_tmp, ctx);  in cache_subtree_walk()
325 		 * If key_tmp starts before key and ends within key.  in cache_subtree_walk()
327 		 *   |==========|	key  in cache_subtree_walk()
330 			ret = ctx->overlap_head(key, key_tmp, ctx);  in cache_subtree_walk()
346  * cache_subtree_search - Search for a key in the cache tree.
348  * @key: Pointer to the cache key to search for.
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
360 …ode *cache_subtree_search(struct pcache_cache_subtree *cache_subtree, struct pcache_cache_key *key,  in cache_subtree_search()  argument
375 		if (key_tmp->off >= key->off) {  in cache_subtree_search()
397 	struct pcache_cache_key *key;  in get_pre_alloc_key()  local
400 		key = ctx->pre_alloc_key;  in get_pre_alloc_key()
403 		return key;  in get_pre_alloc_key()
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.
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
419 static int fixup_overlap_tail(struct pcache_cache_key *key,  in fixup_overlap_tail()  argument
425 	 * |===========|		key  in fixup_overlap_tail()
427 	BUG_ON(cache_key_empty(key));  in fixup_overlap_tail()
433 	cache_key_cutfront(key_tmp, cache_key_lend(key) - cache_key_lstart(key_tmp));  in fixup_overlap_tail()
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.
448  * This function deletes the existing key (key_tmp) when the new key
451  * the new key.
453 static int fixup_overlap_contain(struct pcache_cache_key *key,  in fixup_overlap_contain()  argument
459 	 * |==========|			key  in fixup_overlap_contain()
461 	BUG_ON(cache_key_empty(key));  in fixup_overlap_contain()
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.
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
476  * updated with real data from the backing_dev, making it no longer an empty key.
478  * If we delete key or insert a key, the structure of the entire cache tree may change,
481 static int fixup_overlap_contained(struct pcache_cache_key *key,  in fixup_overlap_contained()  argument
488 	 *   |====|			key  in fixup_overlap_contained()
490 	BUG_ON(cache_key_empty(key));  in fixup_overlap_contained()
493 		 * it's a placeholder key for miss reads that will be updated later.  in fixup_overlap_contained()
495 		cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));  in fixup_overlap_contained()
510 		/* Split key_tmp based on the new key's range */  in fixup_overlap_contained()
511 		cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));  in fixup_overlap_contained()
518 		cache_key_cutfront(key_fixup, cache_key_lend(key) - cache_key_lstart(key_tmp));  in fixup_overlap_contained()
522 			/* Insert the new key into the cache */  in fixup_overlap_contained()
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.
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
546 static int fixup_overlap_head(struct pcache_cache_key *key,  in fixup_overlap_head()  argument
551 	 *   |==========|	key  in fixup_overlap_head()
553 	BUG_ON(cache_key_empty(key));  in fixup_overlap_head()
554 	/* Adjust key_tmp by cutting back based on the new key's start */  in fixup_overlap_head()
555 	cache_key_cutback(key_tmp, cache_key_lend(key_tmp) - cache_key_lstart(key));  in fixup_overlap_head()
566  * cache_key_insert - Insert a new cache key into the cache tree.
568  * @key: The cache key to insert.
569  * @fixup: Indicates if this is a new key being inserted.
572  * a new cache key into the cache tree. It handles key overlaps
575 void cache_key_insert(struct pcache_cache_tree *cache_tree, struct pcache_cache_key *key, bool fixu…  in cache_key_insert()  argument
586 	cache_subtree = get_subtree(cache_tree, key->off);  in cache_key_insert()
587 	key->cache_subtree = cache_subtree;  in cache_key_insert()
589 	prev_node = cache_subtree_search(cache_subtree, key, &parent, &new, &delete_key_list);  in cache_key_insert()
600 		/* Set up the context with the cache, start node, and new key */  in cache_key_insert()
603 		walk_ctx.key = key;  in cache_key_insert()
631 	/* Link and insert the new key into the red-black tree */  in cache_key_insert()
632 	rb_link_node(&key->rb_node, parent, new);  in cache_key_insert()
633 	rb_insert_color(&key->rb_node, &cache_subtree->root);  in cache_key_insert()
650 	struct pcache_cache_key *key;  in clean_fn()  local
665 			key = CACHE_KEY(node);  in clean_fn()
667 			if (cache_key_invalid(key)) {  in clean_fn()
669 				cache_key_delete(key);  in clean_fn()
717 	struct pcache_cache_key *key;  in kset_replay()  local
724 		key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);  in kset_replay()
725 		ret = cache_key_decode(cache, key_onmedia, key);  in kset_replay()
727 			cache_key_put(key);  in kset_replay()
731 		__set_bit(key->cache_pos.cache_seg->cache_seg_id, cache->seg_map);  in kset_replay()
734 		if (key->seg_gen < key->cache_pos.cache_seg->gen) {  in kset_replay()
735 			cache_key_put(key);  in kset_replay()
737 			cache_subtree = get_subtree(&cache->req_key_tree, key->off);  in kset_replay()
739 			cache_key_insert(&cache->req_key_tree, key, true);  in kset_replay()
743 		cache_seg_get(key->cache_pos.cache_seg);  in kset_replay()
866 	struct pcache_cache_key *key;  in cache_tree_clear()  local
875 			key = CACHE_KEY(node);  in cache_tree_clear()
878 			cache_key_delete(key);  in cache_tree_clear()