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