projects/linux·blob master · refs

833 lines · 26.0 KiB

1// SPDX-License-Identifier: GPL-2.0-or-later
2
3#include "cache.h"
4#include "backing_dev.h"
5#include "cache_dev.h"
6#include "dm_pcache.h"
7
8static int cache_data_head_init(struct pcache_cache *cache)
9{
10 struct pcache_cache_segment *next_seg;
11 struct pcache_cache_data_head *data_head;
12
13 data_head = get_data_head(cache);
14 next_seg = get_cache_segment(cache);
15 if (!next_seg)
16 return -EBUSY;
17
18 cache_seg_get(next_seg);
19 data_head->head_pos.cache_seg = next_seg;
20 data_head->head_pos.seg_off = 0;
21
22 return 0;
23}
24
25/**
26 * cache_data_alloc - Allocate data for a cache key.
27 * @cache: Pointer to the cache structure.
28 * @key: Pointer to the cache key to allocate data for.
29 *
30 * This function tries to allocate space from the cache segment specified by the
31 * data head. If the remaining space in the segment is insufficient to allocate
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
34 * space that crosses segment boundaries.
35 */
36static int cache_data_alloc(struct pcache_cache *cache, struct pcache_cache_key *key)
37{
38 struct pcache_cache_data_head *data_head;
39 struct pcache_cache_pos *head_pos;
40 struct pcache_cache_segment *cache_seg;
41 u32 seg_remain;
42 int ret = 0;
43
44 preempt_disable();
45 data_head = get_data_head(cache);
46again:
47 if (!data_head->head_pos.cache_seg) {
48 seg_remain = 0;
49 } else {
50 cache_pos_copy(&key->cache_pos, &data_head->head_pos);
51 key->seg_gen = key->cache_pos.cache_seg->gen;
52
53 head_pos = &data_head->head_pos;
54 cache_seg = head_pos->cache_seg;
55 seg_remain = cache_seg_remain(head_pos);
56 }
57
58 if (seg_remain > key->len) {
59 /* If remaining space in segment is sufficient for the cache key, allocate it. */
60 cache_pos_advance(head_pos, key->len);
61 cache_seg_get(cache_seg);
62 } else if (seg_remain) {
63 /* If remaining space is not enough, allocate the remaining space and adjust the cache key length. */
64 cache_pos_advance(head_pos, seg_remain);
65 key->len = seg_remain;
66
67 /* Get for key: obtain a reference to the cache segment for the key. */
68 cache_seg_get(cache_seg);
69 /* Put for head_pos->cache_seg: release the reference for the current head's segment. */
70 cache_seg_put(head_pos->cache_seg);
71 head_pos->cache_seg = NULL;
72 } else {
73 /* Initialize a new data head if no segment is available. */
74 ret = cache_data_head_init(cache);
75 if (ret)
76 goto out;
77
78 goto again;
79 }
80
81out:
82 preempt_enable();
83
84 return ret;
85}
86
87static int cache_copy_from_req_bio(struct pcache_cache *cache, struct pcache_cache_key *key,
88 struct pcache_request *pcache_req, u32 bio_off)
89{
90 struct pcache_cache_pos *pos = &key->cache_pos;
91 struct pcache_segment *segment;
92
93 segment = &pos->cache_seg->segment;
94
95 return segment_copy_from_bio(segment, pos->seg_off, key->len, pcache_req->bio, bio_off);
96}
97
98static int cache_copy_to_req_bio(struct pcache_cache *cache, struct pcache_request *pcache_req,
99 u32 bio_off, u32 len, struct pcache_cache_pos *pos, u64 key_gen)
100{
101 struct pcache_cache_segment *cache_seg = pos->cache_seg;
102 struct pcache_segment *segment = &cache_seg->segment;
103 int ret;
104
105 spin_lock(&cache_seg->gen_lock);
106 if (key_gen < cache_seg->gen) {
107 spin_unlock(&cache_seg->gen_lock);
108 return -EINVAL;
109 }
110
111 ret = segment_copy_to_bio(segment, pos->seg_off, len, pcache_req->bio, bio_off);
112 spin_unlock(&cache_seg->gen_lock);
113
114 return ret;
115}
116
117/**
118 * miss_read_end_req - Handle the end of a miss read request.
119 * @backing_req: Pointer to the request structure.
120 * @read_ret: Return value of read.
121 *
122 * This function is called when a backing request to read data from
123 * the backing_dev is completed. If the key associated with the request
124 * is empty (a placeholder), it allocates cache space for the key,
125 * copies the data read from the bio into the cache, and updates
126 * the key's status. If the key has been overwritten by a write
127 * request during this process, it will be deleted from the cache
128 * tree and no further action will be taken.
129 */
130static void miss_read_end_req(struct pcache_backing_dev_req *backing_req, int read_ret)
131{
132 void *priv_data = backing_req->priv_data;
133 struct pcache_request *pcache_req = backing_req->req.upper_req;
134 struct pcache_cache *cache = backing_req->backing_dev->cache;
135 int ret;
136
137 if (priv_data) {
138 struct pcache_cache_key *key;
139 struct pcache_cache_subtree *cache_subtree;
140
141 key = (struct pcache_cache_key *)priv_data;
142 cache_subtree = key->cache_subtree;
143
144 /* if this key was deleted from cache_subtree by a write, key->flags should be cleared,
145 * so if cache_key_empty() return true, this key is still in cache_subtree
146 */
147 spin_lock(&cache_subtree->tree_lock);
148 if (cache_key_empty(key)) {
149 /* Check if the backing request was successful. */
150 if (read_ret) {
151 cache_key_delete(key);
152 goto unlock;
153 }
154
155 /* Allocate cache space for the key and copy data from the backing_dev. */
156 ret = cache_data_alloc(cache, key);
157 if (ret) {
158 cache_key_delete(key);
159 goto unlock;
160 }
161
162 ret = cache_copy_from_req_bio(cache, key, pcache_req, backing_req->req.bio_off);
163 if (ret) {
164 cache_seg_put(key->cache_pos.cache_seg);
165 cache_key_delete(key);
166 goto unlock;
167 }
168 key->flags &= ~PCACHE_CACHE_KEY_FLAGS_EMPTY;
169 key->flags |= PCACHE_CACHE_KEY_FLAGS_CLEAN;
170
171 /* Append the key to the cache. */
172 ret = cache_key_append(cache, key, false);
173 if (ret) {
174 cache_seg_put(key->cache_pos.cache_seg);
175 cache_key_delete(key);
176 goto unlock;
177 }
178 }
179unlock:
180 spin_unlock(&cache_subtree->tree_lock);
181 cache_key_put(key);
182 }
183}
184
185/**
186 * submit_cache_miss_req - Submit a backing request when cache data is missing
187 * @cache: The cache context that manages cache operations
188 * @backing_req: The cache request containing information about the read request
189 *
190 * This function is used to handle cases where a cache read request cannot locate
191 * the required data in the cache. When such a miss occurs during `cache_subtree_walk`,
192 * it triggers a backing read request to fetch data from the backing storage.
193 *
194 * If `pcache_req->priv_data` is set, it points to a `pcache_cache_key`, representing
195 * a new cache key to be inserted into the cache. The function calls `cache_key_insert`
196 * to attempt adding the key. On insertion failure, it releases the key reference and
197 * clears `priv_data` to avoid further processing.
198 */
199static void submit_cache_miss_req(struct pcache_cache *cache, struct pcache_backing_dev_req *backing_req)
200{
201 if (backing_req->priv_data) {
202 struct pcache_cache_key *key;
203
204 /* Attempt to insert the key into the cache if priv_data is set */
205 key = (struct pcache_cache_key *)backing_req->priv_data;
206 cache_key_insert(&cache->req_key_tree, key, true);
207 }
208 backing_dev_req_submit(backing_req, false);
209}
210
211static void cache_miss_req_free(struct pcache_backing_dev_req *backing_req)
212{
213 struct pcache_cache_key *key;
214
215 if (backing_req->priv_data) {
216 key = backing_req->priv_data;
217 backing_req->priv_data = NULL;
218 cache_key_put(key); /* for ->priv_data */
219 cache_key_put(key); /* for init ref in alloc */
220 }
221
222 backing_dev_req_end(backing_req);
223}
224
225static struct pcache_backing_dev_req *cache_miss_req_alloc(struct pcache_cache *cache,
226 struct pcache_request *parent,
227 gfp_t gfp_mask)
228{
229 struct pcache_backing_dev *backing_dev = cache->backing_dev;
230 struct pcache_backing_dev_req *backing_req;
231 struct pcache_cache_key *key = NULL;
232 struct pcache_backing_dev_req_opts req_opts = { 0 };
233
234 req_opts.type = BACKING_DEV_REQ_TYPE_REQ;
235 req_opts.gfp_mask = gfp_mask;
236 req_opts.req.upper_req = parent;
237
238 backing_req = backing_dev_req_alloc(backing_dev, &req_opts);
239 if (!backing_req)
240 return NULL;
241
242 key = cache_key_alloc(&cache->req_key_tree, gfp_mask);
243 if (!key)
244 goto free_backing_req;
245
246 cache_key_get(key);
247 backing_req->priv_data = key;
248
249 return backing_req;
250
251free_backing_req:
252 cache_miss_req_free(backing_req);
253 return NULL;
254}
255
256static void cache_miss_req_init(struct pcache_cache *cache,
257 struct pcache_backing_dev_req *backing_req,
258 struct pcache_request *parent,
259 u32 off, u32 len, bool insert_key)
260{
261 struct pcache_cache_key *key;
262 struct pcache_backing_dev_req_opts req_opts = { 0 };
263
264 req_opts.type = BACKING_DEV_REQ_TYPE_REQ;
265 req_opts.req.upper_req = parent;
266 req_opts.req.req_off = off;
267 req_opts.req.len = len;
268 req_opts.end_fn = miss_read_end_req;
269
270 backing_dev_req_init(backing_req, &req_opts);
271
272 if (insert_key) {
273 key = backing_req->priv_data;
274 key->off = parent->off + off;
275 key->len = len;
276 key->flags |= PCACHE_CACHE_KEY_FLAGS_EMPTY;
277 } else {
278 key = backing_req->priv_data;
279 backing_req->priv_data = NULL;
280 cache_key_put(key);
281 cache_key_put(key);
282 }
283}
284
285static struct pcache_backing_dev_req *get_pre_alloc_req(struct pcache_cache_subtree_walk_ctx *ctx)
286{
287 struct pcache_cache *cache = ctx->cache_tree->cache;
288 struct pcache_request *pcache_req = ctx->pcache_req;
289 struct pcache_backing_dev_req *backing_req;
290
291 if (ctx->pre_alloc_req) {
292 backing_req = ctx->pre_alloc_req;
293 ctx->pre_alloc_req = NULL;
294
295 return backing_req;
296 }
297
298 return cache_miss_req_alloc(cache, pcache_req, GFP_NOWAIT);
299}
300
301/*
302 * In the process of walking the cache tree to locate cached data, this
303 * function handles the situation where the requested data range lies
304 * entirely before an existing cache node (`key_tmp`). This outcome
305 * signifies that the target data is absent from the cache (cache miss).
306 *
307 * To fulfill this portion of the read request, the function creates a
308 * backing request (`backing_req`) for the missing data range represented
309 * by `key`. It then appends this request to the submission list in the
310 * `ctx`, which will later be processed to retrieve the data from backing
311 * storage. After setting up the backing request, `req_done` in `ctx` is
312 * updated to reflect the length of the handled range, and the range
313 * in `key` is adjusted by trimming off the portion that is now handled.
314 *
315 * The scenario handled here:
316 *
317 * |--------| key_tmp (existing cached range)
318 * |====| key (requested range, preceding key_tmp)
319 *
320 * Since `key` is before `key_tmp`, it signifies that the requested data
321 * range is missing in the cache (cache miss) and needs retrieval from
322 * backing storage.
323 */
324static int read_before(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,
325 struct pcache_cache_subtree_walk_ctx *ctx)
326{
327 struct pcache_backing_dev_req *backing_req;
328 struct pcache_cache *cache = ctx->cache_tree->cache;
329
330 /*
331 * In this scenario, `key` represents a range that precedes `key_tmp`,
332 * meaning the requested data range is missing from the cache tree
333 * and must be retrieved from the backing_dev.
334 */
335 backing_req = get_pre_alloc_req(ctx);
336 if (!backing_req)
337 return SUBTREE_WALK_RET_NEED_REQ;
338
339 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);
340
341 list_add(&backing_req->node, ctx->submit_req_list);
342 ctx->req_done += key->len;
343 cache_key_cutfront(key, key->len);
344
345 return SUBTREE_WALK_RET_OK;
346}
347
348/*
349 * During cache_subtree_walk, this function manages a scenario where part of the
350 * requested data range overlaps with an existing cache node (`key_tmp`).
351 *
352 * |----------------| key_tmp (existing cached range)
353 * |===========| key (requested range, overlapping the tail of key_tmp)
354 */
355static int read_overlap_tail(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,
356 struct pcache_cache_subtree_walk_ctx *ctx)
357{
358 struct pcache_cache *cache = ctx->cache_tree->cache;
359 struct pcache_backing_dev_req *backing_req;
360 u32 io_len;
361 int ret;
362
363 /*
364 * Calculate the length of the non-overlapping portion of `key`
365 * before `key_tmp`, representing the data missing in the cache.
366 */
367 io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);
368 if (io_len) {
369 backing_req = get_pre_alloc_req(ctx);
370 if (!backing_req)
371 return SUBTREE_WALK_RET_NEED_REQ;
372
373 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true);
374
375 list_add(&backing_req->node, ctx->submit_req_list);
376 ctx->req_done += io_len;
377 cache_key_cutfront(key, io_len);
378 }
379
380 /*
381 * Handle the overlapping portion by calculating the length of
382 * the remaining data in `key` that coincides with `key_tmp`.
383 */
384 io_len = cache_key_lend(key) - cache_key_lstart(key_tmp);
385 if (cache_key_empty(key_tmp)) {
386 backing_req = get_pre_alloc_req(ctx);
387 if (!backing_req)
388 return SUBTREE_WALK_RET_NEED_REQ;
389
390 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
391 submit_cache_miss_req(cache, backing_req);
392 } else {
393 ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,
394 io_len, &key_tmp->cache_pos, key_tmp->seg_gen);
395 if (ret) {
396 if (ret == -EINVAL) {
397 cache_key_delete(key_tmp);
398 return SUBTREE_WALK_RET_RESEARCH;
399 }
400
401 ctx->ret = ret;
402 return SUBTREE_WALK_RET_ERR;
403 }
404 }
405
406 ctx->req_done += io_len;
407 cache_key_cutfront(key, io_len);
408
409 return SUBTREE_WALK_RET_OK;
410}
411
412/*
413 * |----| key_tmp (existing cached range)
414 * |==========| key (requested range)
415 */
416static int read_overlap_contain(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,
417 struct pcache_cache_subtree_walk_ctx *ctx)
418{
419 struct pcache_cache *cache = ctx->cache_tree->cache;
420 struct pcache_backing_dev_req *backing_req;
421 u32 io_len;
422 int ret;
423
424 /*
425 * Calculate the non-overlapping part of `key` before `key_tmp`
426 * to identify the missing data length.
427 */
428 io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);
429 if (io_len) {
430 backing_req = get_pre_alloc_req(ctx);
431 if (!backing_req)
432 return SUBTREE_WALK_RET_NEED_REQ;
433
434 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true);
435
436 list_add(&backing_req->node, ctx->submit_req_list);
437
438 ctx->req_done += io_len;
439 cache_key_cutfront(key, io_len);
440 }
441
442 /*
443 * Handle the overlapping portion between `key` and `key_tmp`.
444 */
445 io_len = key_tmp->len;
446 if (cache_key_empty(key_tmp)) {
447 backing_req = get_pre_alloc_req(ctx);
448 if (!backing_req)
449 return SUBTREE_WALK_RET_NEED_REQ;
450
451 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
452 submit_cache_miss_req(cache, backing_req);
453 } else {
454 ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,
455 io_len, &key_tmp->cache_pos, key_tmp->seg_gen);
456 if (ret) {
457 if (ret == -EINVAL) {
458 cache_key_delete(key_tmp);
459 return SUBTREE_WALK_RET_RESEARCH;
460 }
461
462 ctx->ret = ret;
463 return SUBTREE_WALK_RET_ERR;
464 }
465 }
466
467 ctx->req_done += io_len;
468 cache_key_cutfront(key, io_len);
469
470 return SUBTREE_WALK_RET_OK;
471}
472
473/*
474 * |-----------| key_tmp (existing cached range)
475 * |====| key (requested range, fully within key_tmp)
476 *
477 * If `key_tmp` contains valid cached data, this function copies the relevant
478 * portion to the request's bio. Otherwise, it sends a backing request to
479 * fetch the required data range.
480 */
481static int read_overlap_contained(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,
482 struct pcache_cache_subtree_walk_ctx *ctx)
483{
484 struct pcache_cache *cache = ctx->cache_tree->cache;
485 struct pcache_backing_dev_req *backing_req;
486 struct pcache_cache_pos pos;
487 int ret;
488
489 /*
490 * Check if `key_tmp` is empty, indicating a miss. If so, initiate
491 * a backing request to fetch the required data for `key`.
492 */
493 if (cache_key_empty(key_tmp)) {
494 backing_req = get_pre_alloc_req(ctx);
495 if (!backing_req)
496 return SUBTREE_WALK_RET_NEED_REQ;
497
498 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, false);
499 submit_cache_miss_req(cache, backing_req);
500 } else {
501 cache_pos_copy(&pos, &key_tmp->cache_pos);
502 cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));
503
504 ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,
505 key->len, &pos, key_tmp->seg_gen);
506 if (ret) {
507 if (ret == -EINVAL) {
508 cache_key_delete(key_tmp);
509 return SUBTREE_WALK_RET_RESEARCH;
510 }
511
512 ctx->ret = ret;
513 return SUBTREE_WALK_RET_ERR;
514 }
515 }
516
517 ctx->req_done += key->len;
518 cache_key_cutfront(key, key->len);
519
520 return SUBTREE_WALK_RET_OK;
521}
522
523/*
524 * |--------| key_tmp (existing cached range)
525 * |==========| key (requested range, overlapping the head of key_tmp)
526 */
527static int read_overlap_head(struct pcache_cache_key *key, struct pcache_cache_key *key_tmp,
528 struct pcache_cache_subtree_walk_ctx *ctx)
529{
530 struct pcache_cache *cache = ctx->cache_tree->cache;
531 struct pcache_backing_dev_req *backing_req;
532 struct pcache_cache_pos pos;
533 u32 io_len;
534 int ret;
535
536 io_len = cache_key_lend(key_tmp) - cache_key_lstart(key);
537
538 if (cache_key_empty(key_tmp)) {
539 backing_req = get_pre_alloc_req(ctx);
540 if (!backing_req)
541 return SUBTREE_WALK_RET_NEED_REQ;
542
543 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
544 submit_cache_miss_req(cache, backing_req);
545 } else {
546 cache_pos_copy(&pos, &key_tmp->cache_pos);
547 cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));
548
549 ret = cache_copy_to_req_bio(ctx->cache_tree->cache, ctx->pcache_req, ctx->req_done,
550 io_len, &pos, key_tmp->seg_gen);
551 if (ret) {
552 if (ret == -EINVAL) {
553 cache_key_delete(key_tmp);
554 return SUBTREE_WALK_RET_RESEARCH;
555 }
556
557 ctx->ret = ret;
558 return SUBTREE_WALK_RET_ERR;
559 }
560 }
561
562 ctx->req_done += io_len;
563 cache_key_cutfront(key, io_len);
564
565 return SUBTREE_WALK_RET_OK;
566}
567
568/**
569 * read_walk_finally - Finalizes the cache read tree walk by submitting any
570 * remaining backing requests
571 * @ctx: Context structure holding information about the cache,
572 * read request, and submission list
573 * @ret: the return value after this walk.
574 *
575 * This function is called at the end of the `cache_subtree_walk` during a
576 * cache read operation. It completes the walk by checking if any data
577 * requested by `key` was not found in the cache tree, and if so, it sends
578 * a backing request to retrieve that data. Then, it iterates through the
579 * submission list of backing requests created during the walk, removing
580 * each request from the list and submitting it.
581 *
582 * The scenario managed here includes:
583 * - Sending a backing request for the remaining length of `key` if it was
584 * not fulfilled by existing cache entries.
585 * - Iterating through `ctx->submit_req_list` to submit each backing request
586 * enqueued during the walk.
587 *
588 * This ensures all necessary backing requests for cache misses are submitted
589 * to the backing storage to retrieve any data that could not be found in
590 * the cache.
591 */
592static int read_walk_finally(struct pcache_cache_subtree_walk_ctx *ctx, int ret)
593{
594 struct pcache_cache *cache = ctx->cache_tree->cache;
595 struct pcache_backing_dev_req *backing_req, *next_req;
596 struct pcache_cache_key *key = ctx->key;
597
598 list_for_each_entry_safe(backing_req, next_req, ctx->submit_req_list, node) {
599 list_del_init(&backing_req->node);
600 submit_cache_miss_req(ctx->cache_tree->cache, backing_req);
601 }
602
603 if (ret != SUBTREE_WALK_RET_OK)
604 return ret;
605
606 if (key->len) {
607 backing_req = get_pre_alloc_req(ctx);
608 if (!backing_req)
609 return SUBTREE_WALK_RET_NEED_REQ;
610
611 cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);
612 submit_cache_miss_req(cache, backing_req);
613 ctx->req_done += key->len;
614 }
615
616 return SUBTREE_WALK_RET_OK;
617}
618
619/*
620 * This function is used within `cache_subtree_walk` to determine whether the
621 * read operation has covered the requested data length. It compares the
622 * amount of data processed (`ctx->req_done`) with the total data length
623 * specified in the original request (`ctx->pcache_req->data_len`).
624 *
625 * If `req_done` meets or exceeds the required data length, the function
626 * returns `true`, indicating the walk is complete. Otherwise, it returns `false`,
627 * signaling that additional data processing is needed to fulfill the request.
628 */
629static bool read_walk_done(struct pcache_cache_subtree_walk_ctx *ctx)
630{
631 return (ctx->req_done >= ctx->pcache_req->data_len);
632}
633
634/**
635 * cache_read - Process a read request by traversing the cache tree
636 * @cache: Cache structure holding cache trees and related configurations
637 * @pcache_req: Request structure with information about the data to read
638 *
639 * This function attempts to fulfill a read request by traversing the cache tree(s)
640 * to locate cached data for the requested range. If parts of the data are missing
641 * in the cache, backing requests are generated to retrieve the required segments.
642 *
643 * The function operates by initializing a key for the requested data range and
644 * preparing a context (`walk_ctx`) to manage the cache tree traversal. The context
645 * includes pointers to functions (e.g., `read_before`, `read_overlap_tail`) that handle
646 * specific conditions encountered during the traversal. The `walk_finally` and `walk_done`
647 * functions manage the end stages of the traversal, while the `delete_key_list` and
648 * `submit_req_list` lists track any keys to be deleted or requests to be submitted.
649 *
650 * The function first calculates the requested range and checks if it fits within the
651 * current cache tree (based on the tree's size limits). It then locks the cache tree
652 * and performs a search to locate any matching keys. If there are outdated keys,
653 * these are deleted, and the search is restarted to ensure accurate data retrieval.
654 *
655 * If the requested range spans multiple cache trees, the function moves on to the
656 * next tree once the current range has been processed. This continues until the
657 * entire requested data length has been handled.
658 */
659static int cache_read(struct pcache_cache *cache, struct pcache_request *pcache_req)
660{
661 struct pcache_cache_key key_data = { .off = pcache_req->off, .len = pcache_req->data_len };
662 struct pcache_cache_subtree *cache_subtree;
663 struct pcache_cache_key *key_tmp = NULL, *key_next;
664 struct rb_node *prev_node = NULL;
665 struct pcache_cache_key *key = &key_data;
666 struct pcache_cache_subtree_walk_ctx walk_ctx = { 0 };
667 struct pcache_backing_dev_req *backing_req, *next_req;
668 LIST_HEAD(delete_key_list);
669 LIST_HEAD(submit_req_list);
670 int ret;
671
672 walk_ctx.cache_tree = &cache->req_key_tree;
673 walk_ctx.req_done = 0;
674 walk_ctx.pcache_req = pcache_req;
675 walk_ctx.before = read_before;
676 walk_ctx.overlap_tail = read_overlap_tail;
677 walk_ctx.overlap_head = read_overlap_head;
678 walk_ctx.overlap_contain = read_overlap_contain;
679 walk_ctx.overlap_contained = read_overlap_contained;
680 walk_ctx.walk_finally = read_walk_finally;
681 walk_ctx.walk_done = read_walk_done;
682 walk_ctx.delete_key_list = &delete_key_list;
683 walk_ctx.submit_req_list = &submit_req_list;
684
685next:
686 key->off = pcache_req->off + walk_ctx.req_done;
687 key->len = pcache_req->data_len - walk_ctx.req_done;
688 if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))
689 key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);
690
691 cache_subtree = get_subtree(&cache->req_key_tree, key->off);
692 spin_lock(&cache_subtree->tree_lock);
693search:
694 prev_node = cache_subtree_search(cache_subtree, key, NULL, NULL, &delete_key_list);
695 if (!list_empty(&delete_key_list)) {
696 list_for_each_entry_safe(key_tmp, key_next, &delete_key_list, list_node) {
697 list_del_init(&key_tmp->list_node);
698 cache_key_delete(key_tmp);
699 }
700 goto search;
701 }
702
703 walk_ctx.start_node = prev_node;
704 walk_ctx.key = key;
705
706 ret = cache_subtree_walk(&walk_ctx);
707 if (ret == SUBTREE_WALK_RET_RESEARCH)
708 goto search;
709 spin_unlock(&cache_subtree->tree_lock);
710
711 if (ret == SUBTREE_WALK_RET_ERR) {
712 ret = walk_ctx.ret;
713 goto out;
714 }
715
716 if (ret == SUBTREE_WALK_RET_NEED_REQ) {
717 walk_ctx.pre_alloc_req = cache_miss_req_alloc(cache, pcache_req, GFP_NOIO);
718 pcache_dev_debug(CACHE_TO_PCACHE(cache), "allocate pre_alloc_req with GFP_NOIO");
719 }
720
721 if (walk_ctx.req_done < pcache_req->data_len)
722 goto next;
723 ret = 0;
724out:
725 if (walk_ctx.pre_alloc_req)
726 cache_miss_req_free(walk_ctx.pre_alloc_req);
727
728 list_for_each_entry_safe(backing_req, next_req, &submit_req_list, node) {
729 list_del_init(&backing_req->node);
730 backing_dev_req_end(backing_req);
731 }
732
733 return ret;
734}
735
736static int cache_write(struct pcache_cache *cache, struct pcache_request *pcache_req)
737{
738 struct pcache_cache_subtree *cache_subtree;
739 struct pcache_cache_key *key;
740 u64 offset = pcache_req->off;
741 u32 length = pcache_req->data_len;
742 u32 io_done = 0;
743 int ret;
744
745 while (true) {
746 if (io_done >= length)
747 break;
748
749 key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);
750 key->off = offset + io_done;
751 key->len = length - io_done;
752 if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))
753 key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);
754
755 ret = cache_data_alloc(cache, key);
756 if (ret) {
757 cache_key_put(key);
758 goto err;
759 }
760
761 ret = cache_copy_from_req_bio(cache, key, pcache_req, io_done);
762 if (ret) {
763 cache_seg_put(key->cache_pos.cache_seg);
764 cache_key_put(key);
765 goto err;
766 }
767
768 cache_subtree = get_subtree(&cache->req_key_tree, key->off);
769 spin_lock(&cache_subtree->tree_lock);
770 cache_key_insert(&cache->req_key_tree, key, true);
771 ret = cache_key_append(cache, key, pcache_req->bio->bi_opf & REQ_FUA);
772 if (ret) {
773 cache_seg_put(key->cache_pos.cache_seg);
774 cache_key_delete(key);
775 goto unlock;
776 }
777
778 io_done += key->len;
779 spin_unlock(&cache_subtree->tree_lock);
780 }
781
782 return 0;
783unlock:
784 spin_unlock(&cache_subtree->tree_lock);
785err:
786 return ret;
787}
788
789/**
790 * pcache_cache_flush - Flush all ksets to persist any pending cache data
791 * @cache: Pointer to the cache structure
792 *
793 * This function iterates through all ksets associated with the provided `cache`
794 * and ensures that any data marked for persistence is written to media. For each
795 * kset, it acquires the kset lock, then invokes `cache_kset_close`, which handles
796 * the persistence logic for that kset.
797 *
798 * If `cache_kset_close` encounters an error, the function exits immediately with
799 * the respective error code, preventing the flush operation from proceeding to
800 * subsequent ksets.
801 */
802int pcache_cache_flush(struct pcache_cache *cache)
803{
804 struct pcache_cache_kset *kset;
805 int ret;
806 u32 i;
807
808 for (i = 0; i < cache->n_ksets; i++) {
809 kset = get_kset(cache, i);
810
811 spin_lock(&kset->kset_lock);
812 ret = cache_kset_close(cache, kset);
813 spin_unlock(&kset->kset_lock);
814
815 if (ret)
816 return ret;
817 }
818
819 return 0;
820}
821
822int pcache_cache_handle_req(struct pcache_cache *cache, struct pcache_request *pcache_req)
823{
824 struct bio *bio = pcache_req->bio;
825
826 if (unlikely(bio->bi_opf & REQ_PREFLUSH))
827 return pcache_cache_flush(cache);
828
829 if (bio_data_dir(bio) == READ)
830 return cache_read(cache, pcache_req);
831
832 return cache_write(cache, pcache_req);
833}