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 9940731 : static int cache_data_head_init(struct pcache_cache *cache)
9 : {
10 9940731 : struct pcache_cache_segment *next_seg;
11 9940731 : struct pcache_cache_data_head *data_head;
12 :
13 9940731 : data_head = get_data_head(cache);
14 9940731 : next_seg = get_cache_segment(cache);
15 9940905 : if (!next_seg)
16 : return -EBUSY;
17 :
18 79199 : cache_seg_get(next_seg);
19 79201 : data_head->head_pos.cache_seg = next_seg;
20 79201 : data_head->head_pos.seg_off = 0;
21 :
22 79201 : 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 51611673 : static int cache_data_alloc(struct pcache_cache *cache, struct pcache_cache_key *key)
37 : {
38 51611673 : struct pcache_cache_data_head *data_head;
39 51611673 : struct pcache_cache_pos *head_pos;
40 51611673 : struct pcache_cache_segment *cache_seg;
41 51611673 : u32 seg_remain;
42 51611673 : u32 allocated = 0, to_alloc;
43 51611673 : int ret = 0;
44 :
45 51611673 : preempt_disable();
46 51610127 : data_head = get_data_head(cache);
47 51689328 : again:
48 51689328 : if (!data_head->head_pos.cache_seg) {
49 : seg_remain = 0;
50 : } else {
51 41744510 : cache_pos_copy(&key->cache_pos, &data_head->head_pos);
52 41614105 : key->seg_gen = key->cache_pos.cache_seg->gen;
53 :
54 41614105 : head_pos = &data_head->head_pos;
55 41614105 : cache_seg = head_pos->cache_seg;
56 41614105 : seg_remain = cache_seg_remain(head_pos);
57 41614105 : to_alloc = key->len - allocated;
58 : }
59 :
60 51558923 : if (seg_remain > to_alloc) {
61 : /* If remaining space in segment is sufficient for the cache key, allocate it. */
62 41511050 : cache_pos_advance(head_pos, to_alloc);
63 41355656 : allocated += to_alloc;
64 41355656 : cache_seg_get(cache_seg);
65 10047873 : } else if (seg_remain) {
66 : /* If remaining space is not enough, allocate the remaining space and adjust the cache key length. */
67 77323 : cache_pos_advance(head_pos, seg_remain);
68 77323 : key->len = seg_remain;
69 :
70 : /* Get for key: obtain a reference to the cache segment for the key. */
71 77323 : cache_seg_get(cache_seg);
72 : /* Put for head_pos->cache_seg: release the reference for the current head's segment. */
73 77323 : cache_seg_put(head_pos->cache_seg);
74 77323 : head_pos->cache_seg = NULL;
75 : } else {
76 : /* Initialize a new data head if no segment is available. */
77 9970550 : ret = cache_data_head_init(cache);
78 9940898 : if (ret)
79 9861697 : goto out;
80 :
81 79201 : goto again;
82 : }
83 :
84 51583383 : out:
85 51583383 : preempt_enable();
86 :
87 51598551 : return ret;
88 : }
89 :
90 41703477 : 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 41703477 : struct pcache_cache_pos *pos = &key->cache_pos;
94 41703477 : struct pcache_segment *segment;
95 :
96 41703477 : segment = &pos->cache_seg->segment;
97 :
98 41703477 : return segment_copy_from_bio(segment, pos->seg_off, key->len, pcache_req->bio, bio_off);
99 : }
100 :
101 21851929 : 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 21851929 : struct pcache_cache_segment *cache_seg = pos->cache_seg;
105 21851929 : struct pcache_segment *segment = &cache_seg->segment;
106 21851929 : int ret;
107 :
108 21851929 : spin_lock(&cache_seg->gen_lock);
109 21887924 : if (key_gen < cache_seg->gen) {
110 241 : spin_unlock(&cache_seg->gen_lock);
111 241 : return -EINVAL;
112 : }
113 :
114 21887683 : ret = segment_copy_to_bio(segment, pos->seg_off, len, pcache_req->bio, bio_off);
115 21882164 : spin_unlock(&cache_seg->gen_lock);
116 :
117 21882164 : 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 7157048 : static void miss_read_end_req(struct pcache_backing_dev_req *backing_req, int read_ret)
134 : {
135 7157048 : void *priv_data = backing_req->priv_data;
136 7157048 : struct pcache_request *pcache_req = backing_req->req.upper_req;
137 7157048 : struct pcache_cache *cache = backing_req->backing_dev->cache;
138 7157048 : int ret;
139 :
140 7157048 : if (priv_data) {
141 7138914 : struct pcache_cache_key *key;
142 7138914 : struct pcache_cache_subtree *cache_subtree;
143 :
144 7138914 : key = (struct pcache_cache_key *)priv_data;
145 7138914 : 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 7138914 : spin_lock(&cache_subtree->tree_lock);
151 7138914 : if (cache_key_empty(key)) {
152 : /* Check if the backing request was successful. */
153 7114839 : 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 7114831 : ret = cache_data_alloc(cache, key);
160 7114831 : if (ret) {
161 6417580 : cache_key_delete(key);
162 6417580 : goto unlock;
163 : }
164 :
165 697251 : ret = cache_copy_from_req_bio(cache, key, pcache_req, backing_req->req.bio_off);
166 697251 : if (ret) {
167 0 : cache_seg_put(key->cache_pos.cache_seg);
168 0 : cache_key_delete(key);
169 0 : goto unlock;
170 : }
171 697251 : key->flags &= ~PCACHE_CACHE_KEY_FLAGS_EMPTY;
172 697251 : key->flags |= PCACHE_CACHE_KEY_FLAGS_CLEAN;
173 :
174 : /* Append the key to the cache. */
175 697251 : ret = cache_key_append(cache, key, false);
176 697251 : if (ret) {
177 222 : cache_seg_put(key->cache_pos.cache_seg);
178 222 : cache_key_delete(key);
179 222 : goto unlock;
180 : }
181 : }
182 721104 : unlock:
183 7138914 : spin_unlock(&cache_subtree->tree_lock);
184 7138914 : cache_key_put(key);
185 : }
186 7157048 : }
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 7131451 : static void submit_cache_miss_req(struct pcache_cache *cache, struct pcache_backing_dev_req *backing_req)
203 : {
204 7131451 : if (backing_req->priv_data) {
205 7113317 : struct pcache_cache_key *key;
206 :
207 : /* Attempt to insert the key into the cache if priv_data is set */
208 7113317 : key = (struct pcache_cache_key *)backing_req->priv_data;
209 7113317 : cache_key_insert(&cache->req_key_tree, key, true);
210 : }
211 7118454 : backing_dev_req_submit(backing_req, false);
212 7156657 : }
213 :
214 8 : static void cache_miss_req_free(struct pcache_backing_dev_req *backing_req)
215 : {
216 8 : struct pcache_cache_key *key;
217 :
218 8 : if (backing_req->priv_data) {
219 0 : key = backing_req->priv_data;
220 0 : backing_req->priv_data = NULL;
221 0 : cache_key_put(key); /* for ->priv_data */
222 0 : cache_key_put(key); /* for init ref in alloc */
223 : }
224 :
225 8 : backing_dev_req_end(backing_req);
226 8 : }
227 :
228 7094267 : 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 : {
232 7094267 : struct pcache_backing_dev *backing_dev = cache->backing_dev;
233 7094267 : struct pcache_backing_dev_req *backing_req;
234 7094267 : struct pcache_cache_key *key = NULL;
235 7094267 : struct pcache_backing_dev_req_opts req_opts = { 0 };
236 :
237 7094267 : req_opts.type = BACKING_DEV_REQ_TYPE_REQ;
238 7094267 : req_opts.gfp_mask = gfp_mask;
239 7094267 : req_opts.req.upper_req = parent;
240 :
241 7094267 : backing_req = backing_dev_req_alloc(backing_dev, &req_opts);
242 7139984 : if (!backing_req)
243 : return NULL;
244 :
245 7139592 : key = cache_key_alloc(&cache->req_key_tree, gfp_mask);
246 7133924 : if (!key)
247 8 : goto free_backing_req;
248 :
249 7133916 : cache_key_get(key);
250 7141920 : backing_req->priv_data = key;
251 :
252 7141920 : return backing_req;
253 :
254 8 : free_backing_req:
255 8 : cache_miss_req_free(backing_req);
256 8 : return NULL;
257 : }
258 :
259 7128469 : 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 7128469 : struct pcache_cache_key *key;
265 7128469 : struct pcache_backing_dev_req_opts req_opts = { 0 };
266 :
267 7128469 : req_opts.type = BACKING_DEV_REQ_TYPE_REQ;
268 7128469 : req_opts.req.upper_req = parent;
269 7128469 : req_opts.req.req_off = off;
270 7128469 : req_opts.req.len = len;
271 7128469 : req_opts.end_fn = miss_read_end_req;
272 :
273 7128469 : backing_dev_req_init(backing_req, &req_opts);
274 :
275 7140062 : if (insert_key) {
276 7121928 : key = backing_req->priv_data;
277 7121928 : key->off = parent->off + off;
278 7121928 : key->len = len;
279 7121928 : key->flags |= PCACHE_CACHE_KEY_FLAGS_EMPTY;
280 : } else {
281 18134 : key = backing_req->priv_data;
282 18134 : backing_req->priv_data = NULL;
283 18134 : cache_key_put(key);
284 18134 : cache_key_put(key);
285 : }
286 7140062 : }
287 :
288 7098729 : static struct pcache_backing_dev_req *get_pre_alloc_req(struct pcache_cache_subtree_walk_ctx *ctx)
289 : {
290 7098729 : struct pcache_cache *cache = ctx->cache_tree->cache;
291 7098729 : struct pcache_request *pcache_req = ctx->pcache_req;
292 7098729 : struct pcache_backing_dev_req *backing_req;
293 :
294 7098729 : 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 7098329 : 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 4204018 : 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 4204018 : struct pcache_backing_dev_req *backing_req;
331 4204018 : 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 4204018 : backing_req = get_pre_alloc_req(ctx);
339 4212294 : if (!backing_req)
340 : return SUBTREE_WALK_RET_NEED_REQ;
341 :
342 4212289 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);
343 :
344 4212656 : list_add(&backing_req->node, ctx->submit_req_list);
345 4212656 : ctx->req_done += key->len;
346 4212656 : cache_key_cutfront(key, key->len);
347 :
348 4212656 : 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 6765072 : 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 6765072 : struct pcache_cache *cache = ctx->cache_tree->cache;
362 6765072 : struct pcache_backing_dev_req *backing_req;
363 6765072 : u32 io_len;
364 6765072 : 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 6765072 : io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);
371 6765072 : if (io_len) {
372 99839 : backing_req = get_pre_alloc_req(ctx);
373 99854 : if (!backing_req)
374 : return SUBTREE_WALK_RET_NEED_REQ;
375 :
376 99847 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true);
377 :
378 99847 : list_add(&backing_req->node, ctx->submit_req_list);
379 99847 : ctx->req_done += io_len;
380 99847 : 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 6765077 : io_len = cache_key_lend(key) - cache_key_lstart(key_tmp);
388 6765077 : if (cache_key_empty(key_tmp)) {
389 10163 : backing_req = get_pre_alloc_req(ctx);
390 10163 : if (!backing_req)
391 : return SUBTREE_WALK_RET_NEED_REQ;
392 :
393 10163 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
394 10163 : submit_cache_miss_req(cache, backing_req);
395 : } else {
396 6754914 : 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 6757948 : if (ret) {
399 31 : if (ret == -EINVAL) {
400 31 : cache_key_delete(key_tmp);
401 31 : return SUBTREE_WALK_RET_RESEARCH;
402 : }
403 :
404 0 : ctx->ret = ret;
405 0 : return SUBTREE_WALK_RET_ERR;
406 : }
407 : }
408 :
409 6768080 : ctx->req_done += io_len;
410 6768080 : cache_key_cutfront(key, io_len);
411 :
412 6768080 : return SUBTREE_WALK_RET_OK;
413 : }
414 :
415 : /*
416 : * |----| key_tmp (existing cached range)
417 : * |==========| key (requested range)
418 : */
419 10103832 : 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 10103832 : struct pcache_cache *cache = ctx->cache_tree->cache;
423 10103832 : struct pcache_backing_dev_req *backing_req;
424 10103832 : u32 io_len;
425 10103832 : int ret;
426 :
427 : /*
428 : * Calculate the non-overlapping part of `key` before `key_tmp`
429 : * to identify the missing data length.
430 : */
431 10103832 : io_len = cache_key_lstart(key_tmp) - cache_key_lstart(key);
432 10103832 : if (io_len) {
433 2411398 : backing_req = get_pre_alloc_req(ctx);
434 2416289 : if (!backing_req)
435 : return SUBTREE_WALK_RET_NEED_REQ;
436 :
437 2416282 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, true);
438 :
439 2416562 : list_add(&backing_req->node, ctx->submit_req_list);
440 :
441 2416562 : ctx->req_done += io_len;
442 2416562 : cache_key_cutfront(key, io_len);
443 : }
444 :
445 : /*
446 : * Handle the overlapping portion between `key` and `key_tmp`.
447 : */
448 10106823 : io_len = key_tmp->len;
449 10106823 : if (cache_key_empty(key_tmp)) {
450 7947 : backing_req = get_pre_alloc_req(ctx);
451 7947 : if (!backing_req)
452 : return SUBTREE_WALK_RET_NEED_REQ;
453 :
454 7947 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
455 7947 : submit_cache_miss_req(cache, backing_req);
456 : } else {
457 10098876 : 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 10106588 : if (ret) {
460 210 : if (ret == -EINVAL) {
461 210 : cache_key_delete(key_tmp);
462 210 : return SUBTREE_WALK_RET_RESEARCH;
463 : }
464 :
465 0 : ctx->ret = ret;
466 0 : return SUBTREE_WALK_RET_ERR;
467 : }
468 : }
469 :
470 10114325 : ctx->req_done += io_len;
471 10114325 : cache_key_cutfront(key, io_len);
472 :
473 10114325 : 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 3692085 : 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 3692085 : struct pcache_cache *cache = ctx->cache_tree->cache;
488 3692085 : struct pcache_backing_dev_req *backing_req;
489 3692085 : struct pcache_cache_pos pos;
490 3692085 : 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 3692085 : if (cache_key_empty(key_tmp)) {
497 18 : backing_req = get_pre_alloc_req(ctx);
498 18 : if (!backing_req)
499 : return SUBTREE_WALK_RET_NEED_REQ;
500 :
501 18 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, false);
502 18 : submit_cache_miss_req(cache, backing_req);
503 : } else {
504 3692067 : cache_pos_copy(&pos, &key_tmp->cache_pos);
505 3692024 : cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));
506 :
507 3691990 : 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 3692142 : 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 3692160 : ctx->req_done += key->len;
521 3692160 : cache_key_cutfront(key, key->len);
522 :
523 3692160 : 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 1326787 : 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 1326787 : struct pcache_cache *cache = ctx->cache_tree->cache;
534 1326787 : struct pcache_backing_dev_req *backing_req;
535 1326787 : struct pcache_cache_pos pos;
536 1326787 : u32 io_len;
537 1326787 : int ret;
538 :
539 1326787 : io_len = cache_key_lend(key_tmp) - cache_key_lstart(key);
540 :
541 1326787 : if (cache_key_empty(key_tmp)) {
542 6 : backing_req = get_pre_alloc_req(ctx);
543 6 : if (!backing_req)
544 : return SUBTREE_WALK_RET_NEED_REQ;
545 :
546 6 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, io_len, false);
547 6 : submit_cache_miss_req(cache, backing_req);
548 : } else {
549 1326781 : cache_pos_copy(&pos, &key_tmp->cache_pos);
550 1326544 : cache_pos_advance(&pos, cache_key_lstart(key) - cache_key_lstart(key_tmp));
551 :
552 1326379 : 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 1327136 : 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 1327142 : ctx->req_done += io_len;
566 1327142 : cache_key_cutfront(key, io_len);
567 :
568 1327142 : 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 16064731 : static int read_walk_finally(struct pcache_cache_subtree_walk_ctx *ctx, int ret)
596 : {
597 16064731 : struct pcache_cache *cache = ctx->cache_tree->cache;
598 16064731 : struct pcache_backing_dev_req *backing_req, *next_req;
599 16064731 : struct pcache_cache_key *key = ctx->key;
600 :
601 22803076 : list_for_each_entry_safe(backing_req, next_req, ctx->submit_req_list, node) {
602 6724721 : list_del_init(&backing_req->node);
603 6724721 : submit_cache_miss_req(ctx->cache_tree->cache, backing_req);
604 : }
605 :
606 16078355 : if (ret != SUBTREE_WALK_RET_OK)
607 : return ret;
608 :
609 16078095 : if (key->len) {
610 400218 : backing_req = get_pre_alloc_req(ctx);
611 400241 : if (!backing_req)
612 : return SUBTREE_WALK_RET_NEED_REQ;
613 :
614 399860 : cache_miss_req_init(cache, backing_req, ctx->pcache_req, ctx->req_done, key->len, true);
615 399858 : submit_cache_miss_req(cache, backing_req);
616 399928 : 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 37350002 : static bool read_walk_done(struct pcache_cache_subtree_walk_ctx *ctx)
633 : {
634 37350002 : 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 16043111 : static int cache_read(struct pcache_cache *cache, struct pcache_request *pcache_req)
663 : {
664 16043111 : struct pcache_cache_key key_data = { .off = pcache_req->off, .len = pcache_req->data_len };
665 16043111 : struct pcache_cache_subtree *cache_subtree;
666 16043111 : struct pcache_cache_key *key_tmp = NULL, *key_next;
667 16043111 : struct rb_node *prev_node = NULL;
668 16043111 : struct pcache_cache_key *key = &key_data;
669 16043111 : struct pcache_cache_subtree_walk_ctx walk_ctx = { 0 };
670 16043111 : struct pcache_backing_dev_req *backing_req, *next_req;
671 16043111 : LIST_HEAD(delete_key_list);
672 16043111 : LIST_HEAD(submit_req_list);
673 16043111 : int ret;
674 :
675 16043111 : walk_ctx.cache_tree = &cache->req_key_tree;
676 16043111 : walk_ctx.req_done = 0;
677 16043111 : walk_ctx.pcache_req = pcache_req;
678 16043111 : walk_ctx.before = read_before;
679 16043111 : walk_ctx.overlap_tail = read_overlap_tail;
680 16043111 : walk_ctx.overlap_head = read_overlap_head;
681 16043111 : walk_ctx.overlap_contain = read_overlap_contain;
682 16043111 : walk_ctx.overlap_contained = read_overlap_contained;
683 16043111 : walk_ctx.walk_finally = read_walk_finally;
684 16043111 : walk_ctx.walk_done = read_walk_done;
685 16043111 : walk_ctx.delete_key_list = &delete_key_list;
686 16043111 : walk_ctx.submit_req_list = &submit_req_list;
687 :
688 16079643 : next:
689 16079643 : key->off = pcache_req->off + walk_ctx.req_done;
690 16079643 : key->len = pcache_req->data_len - walk_ctx.req_done;
691 16079643 : if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))
692 37051 : key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);
693 :
694 16079643 : cache_subtree = get_subtree(&cache->req_key_tree, key->off);
695 16079643 : spin_lock(&cache_subtree->tree_lock);
696 : search:
697 16201239 : prev_node = cache_subtree_search(cache_subtree, key, NULL, NULL, &delete_key_list);
698 16190690 : if (!list_empty(&delete_key_list)) {
699 336329 : list_for_each_entry_safe(key_tmp, key_next, &delete_key_list, list_node) {
700 221030 : list_del_init(&key_tmp->list_node);
701 221030 : cache_key_delete(key_tmp);
702 : }
703 115299 : goto search;
704 : }
705 :
706 16075450 : walk_ctx.start_node = prev_node;
707 16075450 : walk_ctx.key = key;
708 :
709 16075450 : ret = cache_subtree_walk(&walk_ctx);
710 16076073 : if (ret == SUBTREE_WALK_RET_RESEARCH)
711 241 : goto search;
712 16075832 : spin_unlock(&cache_subtree->tree_lock);
713 :
714 16072044 : if (ret == SUBTREE_WALK_RET_ERR) {
715 0 : ret = walk_ctx.ret;
716 0 : goto out;
717 : }
718 :
719 16072044 : 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 16072044 : if (walk_ctx.req_done < pcache_req->data_len)
725 38287 : goto next;
726 : ret = 0;
727 16035512 : out:
728 16035512 : if (walk_ctx.pre_alloc_req)
729 0 : cache_miss_req_free(walk_ctx.pre_alloc_req);
730 :
731 16035621 : list_for_each_entry_safe(backing_req, next_req, &submit_req_list, node) {
732 1 : list_del_init(&backing_req->node);
733 1 : backing_dev_req_end(backing_req);
734 : }
735 :
736 16035692 : return ret;
737 : }
738 :
739 44363581 : static int cache_write(struct pcache_cache *cache, struct pcache_request *pcache_req)
740 : {
741 44363581 : struct pcache_cache_subtree *cache_subtree;
742 44363581 : struct pcache_cache_key *key;
743 44363581 : u64 offset = pcache_req->off;
744 44363581 : u32 length = pcache_req->data_len;
745 44363581 : u32 io_done = 0;
746 62766966 : int ret;
747 :
748 41032572 : while (true) {
749 85293117 : if (io_done >= length)
750 : break;
751 :
752 44702073 : key = cache_key_alloc(&cache->req_key_tree, GFP_NOIO);
753 44504582 : key->off = offset + io_done;
754 44504582 : key->len = length - io_done;
755 44504582 : if (key->len > PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK))
756 296888 : key->len = PCACHE_CACHE_SUBTREE_SIZE - (key->off & PCACHE_CACHE_SUBTREE_SIZE_MASK);
757 :
758 44504582 : ret = cache_data_alloc(cache, key);
759 44450338 : if (ret) {
760 3444112 : cache_key_put(key);
761 3444056 : goto err;
762 : }
763 :
764 41006226 : ret = cache_copy_from_req_bio(cache, key, pcache_req, io_done);
765 40559367 : 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 40559367 : cache_subtree = get_subtree(&cache->req_key_tree, key->off);
772 40559367 : spin_lock(&cache_subtree->tree_lock);
773 41191544 : cache_key_insert(&cache->req_key_tree, key, true);
774 40663247 : ret = cache_key_append(cache, key, pcache_req->bio->bi_opf & REQ_FUA);
775 41036078 : if (ret) {
776 3506 : cache_seg_put(key->cache_pos.cache_seg);
777 3506 : cache_key_delete(key);
778 3506 : goto unlock;
779 : }
780 :
781 41032572 : io_done += key->len;
782 41032572 : spin_unlock(&cache_subtree->tree_lock);
783 : }
784 :
785 : return 0;
786 3506 : unlock:
787 3506 : 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 1306625 : int cache_flush(struct pcache_cache *cache)
806 : {
807 1306625 : struct pcache_cache_kset *kset;
808 1306625 : u32 i, ret;
809 :
810 64548252 : for (i = 0; i < cache->n_ksets; i++) {
811 63239785 : kset = get_kset(cache, i);
812 :
813 63239785 : spin_lock(&kset->kset_lock);
814 63781197 : ret = cache_kset_close(cache, kset);
815 63419772 : spin_unlock(&kset->kset_lock);
816 :
817 63241646 : if (ret)
818 19 : return ret;
819 : }
820 :
821 : return 0;
822 : }
823 :
824 61756231 : int pcache_cache_handle_req(struct pcache_cache *cache, struct pcache_request *pcache_req)
825 : {
826 61756231 : struct bio *bio = pcache_req->bio;
827 :
828 61756231 : if (unlikely(bio->bi_opf & REQ_PREFLUSH))
829 1307381 : return cache_flush(cache);
830 :
831 60448850 : if (bio_data_dir(bio) == READ)
832 16046751 : return cache_read(cache, pcache_req);
833 :
834 44402099 : return cache_write(cache, pcache_req);
835 : }
|
