1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2023 Western Digital Corporation or its affiliates.
4 */
5
6 #include <linux/btrfs_tree.h>
7 #include "ctree.h"
8 #include "fs.h"
9 #include "accessors.h"
10 #include "transaction.h"
11 #include "disk-io.h"
12 #include "raid-stripe-tree.h"
13 #include "volumes.h"
14 #include "print-tree.h"
15
btrfs_partially_delete_raid_extent(struct btrfs_trans_handle * trans,struct btrfs_path * path,const struct btrfs_key * oldkey,u64 newlen,u64 frontpad)16 static int btrfs_partially_delete_raid_extent(struct btrfs_trans_handle *trans,
17 struct btrfs_path *path,
18 const struct btrfs_key *oldkey,
19 u64 newlen, u64 frontpad)
20 {
21 struct btrfs_root *stripe_root = trans->fs_info->stripe_root;
22 struct btrfs_stripe_extent *extent, AUTO_KFREE(newitem);
23 struct extent_buffer *leaf;
24 int slot;
25 size_t item_size;
26 struct btrfs_key newkey = {
27 .objectid = oldkey->objectid + frontpad,
28 .type = BTRFS_RAID_STRIPE_KEY,
29 .offset = newlen,
30 };
31 int ret;
32
33 ASSERT(newlen > 0);
34 ASSERT(oldkey->type == BTRFS_RAID_STRIPE_KEY);
35
36 leaf = path->nodes[0];
37 slot = path->slots[0];
38 item_size = btrfs_item_size(leaf, slot);
39
40 newitem = kzalloc(item_size, GFP_NOFS);
41 if (!newitem)
42 return -ENOMEM;
43
44 extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
45
46 for (int i = 0; i < btrfs_num_raid_stripes(item_size); i++) {
47 struct btrfs_raid_stride *stride = &extent->strides[i];
48 u64 devid;
49 u64 phys;
50
51 devid = btrfs_raid_stride_devid(leaf, stride);
52 btrfs_set_stack_raid_stride_devid(&newitem->strides[i], devid);
53 phys = btrfs_raid_stride_physical(leaf, stride) + frontpad;
54 btrfs_set_stack_raid_stride_physical(&newitem->strides[i], phys);
55 }
56
57 ret = btrfs_del_item(trans, stripe_root, path);
58 if (ret)
59 return ret;
60
61 btrfs_release_path(path);
62 return btrfs_insert_item(trans, stripe_root, &newkey, newitem, item_size);
63 }
64
btrfs_delete_raid_extent(struct btrfs_trans_handle * trans,u64 start,u64 length)65 int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 length)
66 {
67 struct btrfs_fs_info *fs_info = trans->fs_info;
68 struct btrfs_root *stripe_root = fs_info->stripe_root;
69 BTRFS_PATH_AUTO_FREE(path);
70 struct btrfs_key key;
71 struct extent_buffer *leaf;
72 u64 found_start;
73 u64 found_end;
74 u64 end = start + length;
75 int slot;
76 int ret;
77
78 if (!btrfs_fs_incompat(fs_info, RAID_STRIPE_TREE) || !stripe_root)
79 return 0;
80
81 if (!btrfs_is_testing(fs_info)) {
82 struct btrfs_chunk_map *map;
83 bool use_rst;
84
85 map = btrfs_find_chunk_map(fs_info, start, length);
86 if (!map)
87 return -EINVAL;
88 use_rst = btrfs_need_stripe_tree_update(fs_info, map->type);
89 btrfs_free_chunk_map(map);
90 if (!use_rst)
91 return 0;
92 }
93
94 path = btrfs_alloc_path();
95 if (!path)
96 return -ENOMEM;
97
98 while (1) {
99 key.objectid = start;
100 key.type = BTRFS_RAID_STRIPE_KEY;
101 key.offset = (u64)-1;
102
103 ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
104 if (ret < 0)
105 break;
106
107 /*
108 * Search with offset=(u64)-1 ensures we land on the correct
109 * leaf even when the target entry is the first item on a leaf.
110 * Since no real entry has offset=(u64)-1, ret is always 1 and
111 * slot points past the last entry with objectid==start (or
112 * past the end of the leaf if that entry is the last item).
113 * Back up one slot to find the actual entry.
114 */
115 if (path->slots[0] == 0) {
116 /* No entry with objectid <= start exists. */
117 ret = 0;
118 break;
119 }
120 path->slots[0]--;
121
122 leaf = path->nodes[0];
123 slot = path->slots[0];
124 btrfs_item_key_to_cpu(leaf, &key, slot);
125 found_start = key.objectid;
126 found_end = found_start + key.offset;
127 ret = 0;
128
129 /*
130 * The stripe extent starts before the range we want to delete,
131 * but the range spans more than one stripe extent:
132 *
133 * |--- RAID Stripe Extent ---||--- RAID Stripe Extent ---|
134 * |--- keep ---|--- drop ---|
135 *
136 * This means we have to get the previous item, truncate its
137 * length and then restart the search.
138 */
139 if (found_start > start) {
140 if (slot == 0) {
141 ret = btrfs_previous_item(stripe_root, path, 0,
142 BTRFS_RAID_STRIPE_KEY);
143 if (ret) {
144 if (ret > 0)
145 ret = -ENOENT;
146 break;
147 }
148 } else {
149 path->slots[0]--;
150 }
151
152 leaf = path->nodes[0];
153 slot = path->slots[0];
154 btrfs_item_key_to_cpu(leaf, &key, slot);
155 found_start = key.objectid;
156 found_end = found_start + key.offset;
157 if (found_start > start || found_end <= start) {
158 ret = -ENOENT;
159 break;
160 }
161 }
162
163 if (key.type != BTRFS_RAID_STRIPE_KEY)
164 break;
165
166 /* That stripe ends before we start, we're done. */
167 if (found_end <= start)
168 break;
169
170 trace_btrfs_raid_extent_delete(fs_info, start, end,
171 found_start, found_end);
172
173 /*
174 * The stripe extent starts before the range we want to delete
175 * and ends after the range we want to delete, i.e. we're
176 * punching a hole in the stripe extent:
177 *
178 * |--- RAID Stripe Extent ---|
179 * | keep |--- drop ---| keep |
180 *
181 * This means we need to a) truncate the existing item and b)
182 * create a second item for the remaining range.
183 */
184 if (found_start < start && found_end > end) {
185 size_t item_size;
186 u64 diff_start = start - found_start;
187 u64 diff_end = found_end - end;
188 struct btrfs_stripe_extent *extent;
189 struct btrfs_key newkey = {
190 .objectid = end,
191 .type = BTRFS_RAID_STRIPE_KEY,
192 .offset = diff_end,
193 };
194
195 /* The "right" item. */
196 ret = btrfs_duplicate_item(trans, stripe_root, path, &newkey);
197 if (ret == -EAGAIN) {
198 btrfs_release_path(path);
199 continue;
200 }
201 if (ret)
202 break;
203
204 /*
205 * btrfs_duplicate_item() may have triggered a leaf
206 * split via setup_leaf_for_split(), so we must refresh
207 * our leaf pointer from the path.
208 */
209 leaf = path->nodes[0];
210 item_size = btrfs_item_size(leaf, path->slots[0]);
211 extent = btrfs_item_ptr(leaf, path->slots[0],
212 struct btrfs_stripe_extent);
213
214 for (int i = 0; i < btrfs_num_raid_stripes(item_size); i++) {
215 struct btrfs_raid_stride *stride = &extent->strides[i];
216 u64 phys;
217
218 phys = btrfs_raid_stride_physical(leaf, stride);
219 phys += diff_start + length;
220 btrfs_set_raid_stride_physical(leaf, stride, phys);
221 }
222
223 /* The "left" item. */
224 path->slots[0]--;
225 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
226 ret = btrfs_partially_delete_raid_extent(trans, path,
227 &key,
228 diff_start, 0);
229 break;
230 }
231
232 /*
233 * The stripe extent starts before the range we want to delete:
234 *
235 * |--- RAID Stripe Extent ---|
236 * |--- keep ---|--- drop ---|
237 *
238 * This means we have to duplicate the tree item, truncate the
239 * length to the new size and then re-insert the item.
240 */
241 if (found_start < start) {
242 u64 diff_start = start - found_start;
243
244 ret = btrfs_partially_delete_raid_extent(trans, path,
245 &key,
246 diff_start, 0);
247 if (ret)
248 break;
249
250 start += (key.offset - diff_start);
251 length -= (key.offset - diff_start);
252 if (length == 0)
253 break;
254
255 btrfs_release_path(path);
256 continue;
257 }
258
259 /*
260 * The stripe extent ends after the range we want to delete:
261 *
262 * |--- RAID Stripe Extent ---|
263 * |--- drop ---|--- keep ---|
264 *
265 * This means we have to duplicate the tree item, truncate the
266 * length to the new size and then re-insert the item.
267 */
268 if (found_end > end) {
269 u64 diff_end = found_end - end;
270
271 ret = btrfs_partially_delete_raid_extent(trans, path,
272 &key,
273 key.offset - length,
274 length);
275 ASSERT(key.offset - diff_end == length,
276 "key.offset=%llu diff_end=%llu length=%llu",
277 key.offset, diff_end, length);
278 break;
279 }
280
281 /* Finally we can delete the whole item, no more special cases. */
282 ret = btrfs_del_item(trans, stripe_root, path);
283 if (ret)
284 break;
285
286 start += key.offset;
287 length -= key.offset;
288 if (length == 0)
289 break;
290
291 btrfs_release_path(path);
292 }
293
294 return ret;
295 }
296
update_raid_extent_item(struct btrfs_trans_handle * trans,struct btrfs_key * key,struct btrfs_stripe_extent * stripe_extent,const size_t item_size)297 static int update_raid_extent_item(struct btrfs_trans_handle *trans,
298 struct btrfs_key *key,
299 struct btrfs_stripe_extent *stripe_extent,
300 const size_t item_size)
301 {
302 BTRFS_PATH_AUTO_FREE(path);
303 struct extent_buffer *leaf;
304 int ret;
305 int slot;
306
307 path = btrfs_alloc_path();
308 if (!path)
309 return -ENOMEM;
310
311 ret = btrfs_search_slot(trans, trans->fs_info->stripe_root, key, path,
312 0, 1);
313 if (ret > 0)
314 ret = -ENOENT;
315 if (ret < 0)
316 return ret;
317
318 leaf = path->nodes[0];
319 slot = path->slots[0];
320
321 write_extent_buffer(leaf, stripe_extent, btrfs_item_ptr_offset(leaf, slot),
322 item_size);
323
324 return ret;
325 }
326
327 EXPORT_FOR_TESTS
btrfs_insert_one_raid_extent(struct btrfs_trans_handle * trans,struct btrfs_io_context * bioc)328 int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
329 struct btrfs_io_context *bioc)
330 {
331 struct btrfs_fs_info *fs_info = trans->fs_info;
332 struct btrfs_key stripe_key;
333 struct btrfs_root *stripe_root = fs_info->stripe_root;
334 const int num_stripes = btrfs_bg_type_to_factor(bioc->map_type);
335 struct btrfs_stripe_extent AUTO_KFREE(stripe_extent);
336 const size_t item_size = struct_size(stripe_extent, strides, num_stripes);
337 int ret;
338
339 stripe_extent = kzalloc(item_size, GFP_NOFS);
340 if (unlikely(!stripe_extent)) {
341 btrfs_abort_transaction(trans, -ENOMEM);
342 return -ENOMEM;
343 }
344
345 trace_btrfs_insert_one_raid_extent(fs_info, bioc->logical, bioc->size,
346 num_stripes);
347 for (int i = 0; i < num_stripes; i++) {
348 u64 devid = bioc->stripes[i].dev->devid;
349 u64 physical = bioc->stripes[i].physical;
350 struct btrfs_raid_stride *raid_stride = &stripe_extent->strides[i];
351
352 btrfs_set_stack_raid_stride_devid(raid_stride, devid);
353 btrfs_set_stack_raid_stride_physical(raid_stride, physical);
354 }
355
356 stripe_key.objectid = bioc->logical;
357 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
358 stripe_key.offset = bioc->size;
359
360 ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
361 item_size);
362 if (ret == -EEXIST) {
363 ret = update_raid_extent_item(trans, &stripe_key, stripe_extent,
364 item_size);
365 if (ret)
366 btrfs_abort_transaction(trans, ret);
367 } else if (ret) {
368 btrfs_abort_transaction(trans, ret);
369 }
370
371 return ret;
372 }
373
btrfs_insert_raid_extent(struct btrfs_trans_handle * trans,struct btrfs_ordered_extent * ordered_extent)374 int btrfs_insert_raid_extent(struct btrfs_trans_handle *trans,
375 struct btrfs_ordered_extent *ordered_extent)
376 {
377 struct btrfs_io_context *bioc;
378 int ret = 0;
379
380 if (!btrfs_fs_incompat(trans->fs_info, RAID_STRIPE_TREE))
381 return 0;
382
383 list_for_each_entry(bioc, &ordered_extent->bioc_list, rst_ordered_entry) {
384 ret = btrfs_insert_one_raid_extent(trans, bioc);
385 if (ret)
386 break;
387 }
388
389 btrfs_cleanup_ordered_bioc_list(ordered_extent);
390 return ret;
391 }
392
btrfs_cleanup_ordered_bioc_list(struct btrfs_ordered_extent * ordered)393 void btrfs_cleanup_ordered_bioc_list(struct btrfs_ordered_extent *ordered)
394 {
395 while (!list_empty(&ordered->bioc_list)) {
396 struct btrfs_io_context *bioc;
397
398 bioc = list_first_entry(&ordered->bioc_list,
399 typeof(*bioc), rst_ordered_entry);
400 list_del(&bioc->rst_ordered_entry);
401 btrfs_put_bioc(bioc);
402 }
403 }
404
btrfs_get_raid_extent_offset(struct btrfs_fs_info * fs_info,u64 logical,u64 * length,u64 map_type,u32 stripe_index,struct btrfs_io_stripe * stripe)405 int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
406 u64 logical, u64 *length, u64 map_type,
407 u32 stripe_index, struct btrfs_io_stripe *stripe)
408 {
409 struct btrfs_root *stripe_root = fs_info->stripe_root;
410 struct btrfs_stripe_extent *stripe_extent;
411 struct btrfs_key stripe_key;
412 struct btrfs_key found_key;
413 BTRFS_PATH_AUTO_FREE(path);
414 struct extent_buffer *leaf;
415 const u64 end = logical + *length;
416 int num_stripes;
417 u64 offset;
418 u64 found_logical;
419 u64 found_length;
420 u64 found_end;
421 int slot;
422 int ret;
423
424 if (unlikely(!stripe_root)) {
425 btrfs_err_rl(fs_info, "missing raid stripe tree root for logical %llu",
426 logical);
427 return -EUCLEAN;
428 }
429
430 stripe_key.objectid = logical;
431 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
432 stripe_key.offset = 0;
433
434 path = btrfs_alloc_path();
435 if (!path)
436 return -ENOMEM;
437
438 if (stripe->rst_search_commit_root) {
439 path->skip_locking = true;
440 path->search_commit_root = true;
441 }
442
443 ret = btrfs_search_slot(NULL, stripe_root, &stripe_key, path, 0, 0);
444 if (ret < 0)
445 return ret;
446 if (ret) {
447 if (path->slots[0] != 0)
448 path->slots[0]--;
449 }
450
451 while (1) {
452 leaf = path->nodes[0];
453 slot = path->slots[0];
454
455 btrfs_item_key_to_cpu(leaf, &found_key, slot);
456 found_logical = found_key.objectid;
457 found_length = found_key.offset;
458 found_end = found_logical + found_length;
459
460 if (found_logical > end) {
461 ret = -ENODATA;
462 goto out;
463 }
464
465 if (in_range(logical, found_logical, found_length))
466 break;
467
468 ret = btrfs_next_item(stripe_root, path);
469 if (ret)
470 goto out;
471 }
472
473 offset = logical - found_logical;
474
475 /*
476 * If we have a logically contiguous, but physically non-continuous
477 * range, we need to split the bio. Record the length after which we
478 * must split the bio.
479 */
480 if (end > found_end)
481 *length -= end - found_end;
482
483 num_stripes = btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
484 stripe_extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
485
486 for (int i = 0; i < num_stripes; i++) {
487 struct btrfs_raid_stride *stride = &stripe_extent->strides[i];
488 u64 devid = btrfs_raid_stride_devid(leaf, stride);
489 u64 physical = btrfs_raid_stride_physical(leaf, stride);
490
491 if (devid != stripe->dev->devid)
492 continue;
493
494 if ((map_type & BTRFS_BLOCK_GROUP_DUP) && stripe_index != i)
495 continue;
496
497 stripe->physical = physical + offset;
498
499 trace_btrfs_get_raid_extent_offset(fs_info, logical, *length,
500 stripe->physical, devid);
501
502 return 0;
503 }
504
505 /* If we're here, we haven't found the requested devid in the stripe. */
506 ret = -ENODATA;
507 out:
508 if (ret > 0)
509 ret = -ENODATA;
510 if (ret && ret != -EIO && !stripe->rst_search_commit_root) {
511 btrfs_debug(fs_info,
512 "cannot find raid-stripe for logical [%llu, %llu] devid %llu, profile %s",
513 logical, logical + *length, stripe->dev->devid,
514 btrfs_bg_type_to_raid_name(map_type));
515 }
516
517 return ret;
518 }
519