26  * cache_data_alloc - Allocate data for a cache key.
28  * @key: Pointer to the cache key to allocate data for.
32  * the requested length for the cache key, it will allocate whatever is available
33  * and adjust the key's length accordingly. This function does not allocate
36 static int cache_data_alloc(struct pcache_cache *cache, struct pcache_cache_key *key)  in cache_data_alloc()  argument
48 	to_alloc = key->len - allocated;  in cache_data_alloc()
52 		cache_pos_copy(&key->cache_pos, &data_head->head_pos);  in cache_data_alloc()
53 		key->seg_gen = key->cache_pos.cache_seg->gen;  in cache_data_alloc()
61 		/* If remaining space in segment is sufficient for the cache key, allocate it. */  in cache_data_alloc()
66 …/* If remaining space is not enough, allocate the remaining space and adjust the cache key length.…  in cache_data_alloc()
68 		key->len = seg_remain;  in cache_data_alloc()
70 		/* Get for key: obtain a reference to the cache segment for the key. */  in cache_data_alloc()
90 static int cache_copy_from_req_bio(struct pcache_cache *cache, struct pcache_cache_key *key,  in cache_copy_from_req_bio()  argument
93 	struct pcache_cache_pos *pos = &key->cache_pos;  in cache_copy_from_req_bio()
98 	return segment_copy_from_bio(segment, pos->seg_off, key->len, pcache_req->bio, bio_off);  in cache_copy_from_req_bio()
126  * the backing_dev is completed. If the key associated with the request
127  * is empty (a placeholder), it allocates cache space for the key,
129  * the key's status. If the key has been overwritten by a write
141 		struct pcache_cache_key *key;  in miss_read_end_req()  local
144 		key = (struct pcache_cache_key *)priv_data;  in miss_read_end_req()
145 		cache_subtree = key->cache_subtree;  in miss_read_end_req()
147 		/* if this key was deleted from cache_subtree by a write, key->flags should be cleared,  in miss_read_end_req()
148 		 * so if cache_key_empty() return true, this key is still in cache_subtree  in miss_read_end_req()
151 		if (cache_key_empty(key)) {  in miss_read_end_req()
154 				cache_key_delete(key);  in miss_read_end_req()
158 			/* Allocate cache space for the key and copy data from the backing_dev. */  in miss_read_end_req()
159 			ret = cache_data_alloc(cache, key);  in miss_read_end_req()
161 				cache_key_delete(key);  in miss_read_end_req()
165 			ret = cache_copy_from_req_bio(cache, key, pcache_req, backing_req->req.bio_off);  in miss_read_end_req()
167 				cache_seg_put(key->cache_pos.cache_seg);  in miss_read_end_req()
168 				cache_key_delete(key);  in miss_read_end_req()
171 			key->flags &= ~PCACHE_CACHE_KEY_FLAGS_EMPTY;  in miss_read_end_req()
172 			key->flags |= PCACHE_CACHE_KEY_FLAGS_CLEAN;  in miss_read_end_req()
174 			/* Append the key to the cache. */  in miss_read_end_req()
175 			ret = cache_key_append(cache, key, false);  in miss_read_end_req()
177 				cache_seg_put(key->cache_pos.cache_seg);  in miss_read_end_req()
178 				cache_key_delete(key);  in miss_read_end_req()
184 		cache_key_put(key);  in miss_read_end_req()
198  * a new cache key to be inserted into the cache. The function calls `cache_key_insert`
199  * to attempt adding the key. On insertion failure, it releases the key reference and
205 		struct pcache_cache_key *key;  in submit_cache_miss_req()  local
207 		/* Attempt to insert the key into the cache if priv_data is set */  in submit_cache_miss_req()
208 		key = (struct pcache_cache_key *)backing_req->priv_data;  in submit_cache_miss_req()
209 		cache_key_insert(&cache->req_key_tree, key, true);  in submit_cache_miss_req()
216 	struct pcache_cache_key *key;  in cache_miss_req_free()  local
219 		key = backing_req->priv_data;  in cache_miss_req_free()
221 		cache_key_put(key); /* for ->priv_data */  in cache_miss_req_free()
222 		cache_key_put(key); /* for init ref in alloc */  in cache_miss_req_free()
234 	struct pcache_cache_key *key = NULL;  in cache_miss_req_alloc()  local
245 	key = cache_key_alloc(&cache->req_key_tree, gfp_mask);  in cache_miss_req_alloc()
246 	if (!key)  in cache_miss_req_alloc()
249 	cache_key_get(key);  in cache_miss_req_alloc()
250 	backing_req->priv_data = key;  in cache_miss_req_alloc()
264 	struct pcache_cache_key *key;  in cache_miss_req_init()  local
276 		key = backing_req->priv_data;  in cache_miss_req_init()
277 		key->off = parent->off + off;  in cache_miss_req_init()
278 		key->len = len;  in cache_miss_req_init()
279 		key->flags |= PCACHE_CACHE_KEY_FLAGS_EMPTY;  in cache_miss_req_init()
281 		key = backing_req->priv_data;  in cache_miss_req_init()
283 		cache_key_put(key);  in cache_miss_req_init()
284 		cache_key_put(key);  in cache_miss_req_init()
312  * by `key`. It then appends this request to the submission list in the
316  * in `key` is adjusted by trimming off the portion that is now handled.
321  * |====|					   key (requested range, preceding key_tmp)
323  * Since `key` is before `key_tmp`, it signifies that the requested data
327 static int read_before(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,  in read_before()  argument
334 	 * In this scenario, `key` represents a range that precedes `key_tmp`,  in read_before()
342 	cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);  in read_before()
345 	ctx->req_done += key->len;  in read_before()
346 	cache_key_cutfront(key, key->len);  in read_before()
356  * |===========|		   key (requested range, overlapping the tail of key_tmp)
358 static int read_overlap_tail(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,  in read_overlap_tail()  argument
367 	 * Calculate the length of the non-overlapping portion of `key`  in read_overlap_tail()
370 	io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);  in read_overlap_tail()
380 		cache_key_cutfront(key, io_len);  in read_overlap_tail()
385 	 * the remaining data in `key` that coincides with `key_tmp`.  in read_overlap_tail()
387 	io_len = cache_key_lend(key) - cache_key_lstart(key_tmp);  in read_overlap_tail()
410 	cache_key_cutfront(key, io_len);  in read_overlap_tail()
417  * |==========|       key (requested range)
419 static int read_overlap_contain(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,  in read_overlap_contain()  argument
428 	 * Calculate the non-overlapping part of `key` before `key_tmp`  in read_overlap_contain()
431 	io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);  in read_overlap_contain()
442 		cache_key_cutfront(key, io_len);  in read_overlap_contain()
446 	 * Handle the overlapping portion between `key` and `key_tmp`.  in read_overlap_contain()
471 	cache_key_cutfront(key, io_len);  in read_overlap_contain()
478  *	   |====|			key (requested range, fully within key_tmp)
484 static int read_overlap_contained(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,  in read_overlap_contained()  argument
494 	 * a backing request to fetch the required data for `key`.  in read_overlap_contained()
501 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, false);  in read_overlap_contained()
505 		cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));  in read_overlap_contained()
508 					key->len, &pos, key_tmp->seg_gen);  in read_overlap_contained()
520 	ctx->req_done += key->len;  in read_overlap_contained()
521 	cache_key_cutfront(key, key->len);  in read_overlap_contained()
528  *	   |==========|	  key (requested range, overlapping the head of key_tmp)
530 static int read_overlap_head(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,  in read_overlap_head()  argument
539 	io_len = cache_key_lend(key_tmp) - cache_key_lstart(key);  in read_overlap_head()
550 		cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));  in read_overlap_head()
566 	cache_key_cutfront(key, io_len);  in read_overlap_head()
580  * requested by `key` was not found in the cache tree, and if so, it sends
586  * - Sending a backing request for the remaining length of `key` if it was
599 	struct pcache_cache_key *key = ctx->key;  in read_walk_finally()  local
609 	if (key->len) {  in read_walk_finally()
614 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);  in read_walk_finally()
616 		ctx->req_done += key->len;  in read_walk_finally()
646  * The function operates by initializing a key for the requested data range and
668 	struct pcache_cache_key *key = &key_data;  in cache_read()  local
689 	key->off = pcache_req->off + walk_ctx.req_done;  in cache_read()
690 	key->len = pcache_req->data_len - walk_ctx.req_done;  in cache_read()
691 	if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))  in cache_read()
692 		key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);  in cache_read()
694 	cache_subtree = get_subtree(&cache->req_key_tree, key->off);  in cache_read()
697 	prev_node = cache_subtree_search(cache_subtree, key, NULL, NULL, &delete_key_list);  in cache_read()
707 	walk_ctx.key = key;  in cache_read()
742 	struct pcache_cache_key *key;  in cache_write()  local
752 		key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);  in cache_write()
753 		key->off = offset + io_done;  in cache_write()
754 		key->len = length - io_done;  in cache_write()
755 		if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))  in cache_write()
756 			key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);  in cache_write()
758 		ret = cache_data_alloc(cache, key);  in cache_write()
760 			cache_key_put(key);  in cache_write()
764 		ret = cache_copy_from_req_bio(cache, key, pcache_req, io_done);  in cache_write()
766 			cache_seg_put(key->cache_pos.cache_seg);  in cache_write()
767 			cache_key_put(key);  in cache_write()
771 		cache_subtree = get_subtree(&cache->req_key_tree, key->off);  in cache_write()
773 		cache_key_insert(&cache->req_key_tree, key, true);  in cache_write()
774 		ret = cache_key_append(cache, key, pcache_req->bio->bi_opf & REQ_FUA);  in cache_write()
776 			cache_seg_put(key->cache_pos.cache_seg);  in cache_write()
777 			cache_key_delete(key);  in cache_write()
781 		io_done += key->len;  in cache_write()