// SPDX-License-Identifier: GPL-2.0-or-later #include "cache.h"#include "backing_dev.h"#include "cache_dev.h"#include "dm_pcache.h" static int cache_data_head_init(struct pcache_cache *cache){	struct pcache_cache_segment *next_seg;	struct pcache_cache_data_head *data_head; 	data_head = get_data_head(cache);	next_seg = get_cache_segment(cache);	if (!next_seg)		return -EBUSY; 	cache_seg_get(next_seg);	data_head->head_pos.cache_seg = next_seg;	data_head->head_pos.seg_off = 0; 	return 0;} /** * cache_data_alloc - Allocate data for a cache key. * @cache: Pointer to the cache structure. * @key: Pointer to the cache key to allocate data for. * * This function tries to allocate space from the cache segment specified by the * data head. If the remaining space in the segment is insufficient to allocate * the requested length for the cache key, it will allocate whatever is available * and adjust the key's length accordingly. This function does not allocate * space that crosses segment boundaries. */static int cache_data_alloc(struct pcache_cache *cache, struct pcache_cache_key *key){	struct pcache_cache_data_head *data_head;	struct pcache_cache_pos *head_pos;	struct pcache_cache_segment *cache_seg;	u32 seg_remain;	int ret = 0; 	preempt_disable();	data_head = get_data_head(cache);again:	if (!data_head->head_pos.cache_seg) {		seg_remain = 0;	} else {		cache_pos_copy(&key->cache_pos, &data_head->head_pos);		key->seg_gen = key->cache_pos.cache_seg->gen; 		head_pos = &data_head->head_pos;		cache_seg = head_pos->cache_seg;		seg_remain = cache_seg_remain(head_pos);	} 	if (seg_remain > key->len) {		/* If remaining space in segment is sufficient for the cache key, allocate it. */		cache_pos_advance(head_pos, key->len);		cache_seg_get(cache_seg);	} else if (seg_remain) {		/* If remaining space is not enough, allocate the remaining space and adjust the cache key length. */		cache_pos_advance(head_pos, seg_remain);		key->len = seg_remain; 		/* Get for key: obtain a reference to the cache segment for the key. */		cache_seg_get(cache_seg);		/* Put for head_pos->cache_seg: release the reference for the current head's segment. */		cache_seg_put(head_pos->cache_seg);		head_pos->cache_seg = NULL;	} else {		/* Initialize a new data head if no segment is available. */		ret = cache_data_head_init(cache);		if (ret)			goto out; 		goto again;	} out:	preempt_enable(); 	return ret;} static int cache_copy_from_req_bio(struct pcache_cache *cache, struct pcache_cache_key *key,				struct pcache_request *pcache_req, u32 bio_off){	struct pcache_cache_pos *pos = &key->cache_pos;	struct pcache_segment *segment; 	segment = &pos->cache_seg->segment; 	return segment_copy_from_bio(segment, pos->seg_off, key->len, pcache_req->bio, bio_off);} static int cache_copy_to_req_bio(struct pcache_cache *cache, struct pcache_request *pcache_req,			    u32 bio_off, u32 len, struct pcache_cache_pos *pos, u64 key_gen){	struct pcache_cache_segment *cache_seg = pos->cache_seg;	struct pcache_segment *segment = &cache_seg->segment;	int ret; 	spin_lock(&cache_seg->gen_lock);	if (key_gen < cache_seg->gen) {		spin_unlock(&cache_seg->gen_lock);		return -EINVAL;	} 	ret = segment_copy_to_bio(segment, pos->seg_off, len, pcache_req->bio, bio_off);	spin_unlock(&cache_seg->gen_lock); 	return ret;} /** * miss_read_end_req - Handle the end of a miss read request. * @backing_req: Pointer to the request structure. * @read_ret: Return value of read. * * This function is called when a backing request to read data from * the backing_dev is completed. If the key associated with the request * is empty (a placeholder), it allocates cache space for the key, * copies the data read from the bio into the cache, and updates * the key's status. If the key has been overwritten by a write * request during this process, it will be deleted from the cache * tree and no further action will be taken. */static void miss_read_end_req(struct pcache_backing_dev_req *backing_req, int read_ret){	void *priv_data = backing_req->priv_data;	struct pcache_request *pcache_req = backing_req->req.upper_req;	struct pcache_cache *cache = backing_req->backing_dev->cache;	int ret; 	if (priv_data) {		struct pcache_cache_key *key;		struct pcache_cache_subtree *cache_subtree; 		key = (struct pcache_cache_key *)priv_data;		cache_subtree = key->cache_subtree; 		/* if this key was deleted from cache_subtree by a write, key->flags should be cleared,		 * so if cache_key_empty() return true, this key is still in cache_subtree		 */		spin_lock(&cache_subtree->tree_lock);		if (cache_key_empty(key)) {			/* Check if the backing request was successful. */			if (read_ret) {				cache_key_delete(key);				goto unlock;			} 			/* Allocate cache space for the key and copy data from the backing_dev. */			ret = cache_data_alloc(cache, key);			if (ret) {				cache_key_delete(key);				goto unlock;			} 			ret = cache_copy_from_req_bio(cache, key, pcache_req, backing_req->req.bio_off);			if (ret) {				cache_seg_put(key->cache_pos.cache_seg);				cache_key_delete(key);				goto unlock;			}			key->flags &= ~PCACHE_CACHE_KEY_FLAGS_EMPTY;			key->flags |= PCACHE_CACHE_KEY_FLAGS_CLEAN; 			/* Append the key to the cache. */			ret = cache_key_append(cache, key, false);			if (ret) {				cache_seg_put(key->cache_pos.cache_seg);				cache_key_delete(key);				goto unlock;			}		}unlock:		spin_unlock(&cache_subtree->tree_lock);		cache_key_put(key);	}} /** * submit_cache_miss_req - Submit a backing request when cache data is missing * @cache: The cache context that manages cache operations * @backing_req: The cache request containing information about the read request * * This function is used to handle cases where a cache read request cannot locate * the required data in the cache. When such a miss occurs during `cache_subtree_walk`, * it triggers a backing read request to fetch data from the backing storage. * * If `pcache_req->priv_data` is set, it points to a `pcache_cache_key`, representing * a new cache key to be inserted into the cache. The function calls `cache_key_insert` * to attempt adding the key. On insertion failure, it releases the key reference and * clears `priv_data` to avoid further processing. */static void submit_cache_miss_req(struct pcache_cache *cache, struct pcache_backing_dev_req *backing_req){	if (backing_req->priv_data) {		struct pcache_cache_key *key; 		/* Attempt to insert the key into the cache if priv_data is set */		key = (struct pcache_cache_key *)backing_req->priv_data;		cache_key_insert(&cache->req_key_tree, key, true);	}	backing_dev_req_submit(backing_req, false);} static void cache_miss_req_free(struct pcache_backing_dev_req *backing_req){	struct pcache_cache_key *key; 	if (backing_req->priv_data) {		key = backing_req->priv_data;		backing_req->priv_data = NULL;		cache_key_put(key); /* for ->priv_data */		cache_key_put(key); /* for init ref in alloc */	} 	backing_dev_req_end(backing_req);} static struct pcache_backing_dev_req *cache_miss_req_alloc(struct pcache_cache *cache,							   struct pcache_request *parent,							   gfp_t gfp_mask){	struct pcache_backing_dev *backing_dev = cache->backing_dev;	struct pcache_backing_dev_req *backing_req;	struct pcache_cache_key *key = NULL;	struct pcache_backing_dev_req_opts req_opts = { 0 }; 	req_opts.type = BACKING_DEV_REQ_TYPE_REQ;	req_opts.gfp_mask = gfp_mask;	req_opts.req.upper_req = parent; 	backing_req = backing_dev_req_alloc(backing_dev, &req_opts);	if (!backing_req)		return NULL; 	key = cache_key_alloc(&cache->req_key_tree, gfp_mask);	if (!key)		goto free_backing_req; 	cache_key_get(key);	backing_req->priv_data = key; 	return backing_req; free_backing_req:	cache_miss_req_free(backing_req);	return NULL;} static void cache_miss_req_init(struct pcache_cache *cache,				struct pcache_backing_dev_req *backing_req,				struct pcache_request *parent,				u32 off, u32 len, bool insert_key){	struct pcache_cache_key *key;	struct pcache_backing_dev_req_opts req_opts = { 0 }; 	req_opts.type = BACKING_DEV_REQ_TYPE_REQ;	req_opts.req.upper_req = parent;	req_opts.req.req_off = off;	req_opts.req.len = len;	req_opts.end_fn = miss_read_end_req; 	backing_dev_req_init(backing_req, &req_opts); 	if (insert_key) {		key = backing_req->priv_data;		key->off = parent->off + off;		key->len = len;		key->flags |= PCACHE_CACHE_KEY_FLAGS_EMPTY;	} else {		key = backing_req->priv_data;		backing_req->priv_data = NULL;		cache_key_put(key);		cache_key_put(key);	}} static struct pcache_backing_dev_req *get_pre_alloc_req(struct pcache_cache_subtree_walk_ctx *ctx){	struct pcache_cache *cache = ctx->cache_tree->cache;	struct pcache_request *pcache_req = ctx->pcache_req;	struct pcache_backing_dev_req *backing_req; 	if (ctx->pre_alloc_req) {		backing_req = ctx->pre_alloc_req;		ctx->pre_alloc_req = NULL; 		return backing_req;	} 	return cache_miss_req_alloc(cache, pcache_req, GFP_NOWAIT);} /* * In the process of walking the cache tree to locate cached data, this * function handles the situation where the requested data range lies * entirely before an existing cache node (`key_tmp`). This outcome * signifies that the target data is absent from the cache (cache miss). * * To fulfill this portion of the read request, the function creates a * backing request (`backing_req`) for the missing data range represented * by `key`. It then appends this request to the submission list in the * `ctx`, which will later be processed to retrieve the data from backing * storage. After setting up the backing request, `req_done` in `ctx` is * updated to reflect the length of the handled range, and the range * in `key` is adjusted by trimming off the portion that is now handled. * * The scenario handled here: * *        |--------|			  key_tmp (existing cached range) * |====|					   key (requested range, preceding key_tmp) * * Since `key` is before `key_tmp`, it signifies that the requested data * range is missing in the cache (cache miss) and needs retrieval from * backing storage. */static int read_before(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,		struct pcache_cache_subtree_walk_ctx *ctx){	struct pcache_backing_dev_req *backing_req;	struct pcache_cache *cache = ctx->cache_tree->cache; 	/*	 * In this scenario, `key` represents a range that precedes `key_tmp`,	 * meaning the requested data range is missing from the cache tree	 * and must be retrieved from the backing_dev.	 */	backing_req = get_pre_alloc_req(ctx);	if (!backing_req)		return SUBTREE_WALK_RET_NEED_REQ; 	cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true); 	list_add(&backing_req->node, ctx->submit_req_list);	ctx->req_done += key->len;	cache_key_cutfront(key, key->len); 	return SUBTREE_WALK_RET_OK;} /* * During cache_subtree_walk, this function manages a scenario where part of the * requested data range overlaps with an existing cache node (`key_tmp`). * *     |----------------|  key_tmp (existing cached range) * |===========|		   key (requested range, overlapping the tail of key_tmp) */static int read_overlap_tail(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,		struct pcache_cache_subtree_walk_ctx *ctx){	struct pcache_cache *cache = ctx->cache_tree->cache;	struct pcache_backing_dev_req *backing_req;	u32 io_len;	int ret; 	/*	 * Calculate the length of the non-overlapping portion of `key`	 * before `key_tmp`, representing the data missing in the cache.	 */	io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);	if (io_len) {		backing_req = get_pre_alloc_req(ctx);		if (!backing_req)			return SUBTREE_WALK_RET_NEED_REQ; 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true); 		list_add(&backing_req->node, ctx->submit_req_list);		ctx->req_done += io_len;		cache_key_cutfront(key, io_len);	} 	/*	 * Handle the overlapping portion by calculating the length of	 * the remaining data in `key` that coincides with `key_tmp`.	 */	io_len = cache_key_lend(key) - cache_key_lstart(key_tmp);	if (cache_key_empty(key_tmp)) {		backing_req = get_pre_alloc_req(ctx);		if (!backing_req)			return SUBTREE_WALK_RET_NEED_REQ; 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);		submit_cache_miss_req(cache, backing_req);	} else {		ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,					io_len, &key_tmp->cache_pos, key_tmp->seg_gen);		if (ret) {			if (ret == -EINVAL) {				cache_key_delete(key_tmp);				return SUBTREE_WALK_RET_RESEARCH;			} 			ctx->ret = ret;			return SUBTREE_WALK_RET_ERR;		}	} 	ctx->req_done += io_len;	cache_key_cutfront(key, io_len); 	return SUBTREE_WALK_RET_OK;} /* *    |----|          key_tmp (existing cached range) * |==========|       key (requested range) */static int read_overlap_contain(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,		struct pcache_cache_subtree_walk_ctx *ctx){	struct pcache_cache *cache = ctx->cache_tree->cache;	struct pcache_backing_dev_req *backing_req;	u32 io_len;	int ret; 	/*	 * Calculate the non-overlapping part of `key` before `key_tmp`	 * to identify the missing data length.	 */	io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);	if (io_len) {		backing_req = get_pre_alloc_req(ctx);		if (!backing_req)			return SUBTREE_WALK_RET_NEED_REQ; 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true); 		list_add(&backing_req->node, ctx->submit_req_list); 		ctx->req_done += io_len;		cache_key_cutfront(key, io_len);	} 	/*	 * Handle the overlapping portion between `key` and `key_tmp`.	 */	io_len = key_tmp->len;	if (cache_key_empty(key_tmp)) {		backing_req = get_pre_alloc_req(ctx);		if (!backing_req)			return SUBTREE_WALK_RET_NEED_REQ; 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);		submit_cache_miss_req(cache, backing_req);	} else {		ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,					io_len, &key_tmp->cache_pos, key_tmp->seg_gen);		if (ret) {			if (ret == -EINVAL) {				cache_key_delete(key_tmp);				return SUBTREE_WALK_RET_RESEARCH;			} 			ctx->ret = ret;			return SUBTREE_WALK_RET_ERR;		}	} 	ctx->req_done += io_len;	cache_key_cutfront(key, io_len); 	return SUBTREE_WALK_RET_OK;} /* * |-----------|		key_tmp (existing cached range) *   |====|			key (requested range, fully within key_tmp) * * If `key_tmp` contains valid cached data, this function copies the relevant * portion to the request's bio. Otherwise, it sends a backing request to * fetch the required data range. */static int read_overlap_contained(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,		struct pcache_cache_subtree_walk_ctx *ctx){	struct pcache_cache *cache = ctx->cache_tree->cache;	struct pcache_backing_dev_req *backing_req;	struct pcache_cache_pos pos;	int ret; 	/*	 * Check if `key_tmp` is empty, indicating a miss. If so, initiate	 * a backing request to fetch the required data for `key`.	 */	if (cache_key_empty(key_tmp)) {		backing_req = get_pre_alloc_req(ctx);		if (!backing_req)			return SUBTREE_WALK_RET_NEED_REQ; 		cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, false);		submit_cache_miss_req(cache, backing_req);	} else {

Lines 1–500 of 833. Load more