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)
314 return (ret == 1 ? ret : -EINVAL);
315
316 leaf = path->nodes[0];
317 slot = path->slots[0];
318
319 write_extent_buffer(leaf, stripe_extent, btrfs_item_ptr_offset(leaf, slot),
320 item_size);
321
322 return ret;
323 }
324
325 EXPORT_FOR_TESTS
btrfs_insert_one_raid_extent(struct btrfs_trans_handle * trans,struct btrfs_io_context * bioc)326 int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
327 struct btrfs_io_context *bioc)
328 {
329 struct btrfs_fs_info *fs_info = trans->fs_info;
330 struct btrfs_key stripe_key;
331 struct btrfs_root *stripe_root = fs_info->stripe_root;
332 const int num_stripes = btrfs_bg_type_to_factor(bioc->map_type);
333 struct btrfs_stripe_extent AUTO_KFREE(stripe_extent);
334 const size_t item_size = struct_size(stripe_extent, strides, num_stripes);
335 int ret;
336
337 stripe_extent = kzalloc(item_size, GFP_NOFS);
338 if (unlikely(!stripe_extent)) {
339 btrfs_abort_transaction(trans, -ENOMEM);
340 btrfs_end_transaction(trans);
341 return -ENOMEM;
342 }
343
344 trace_btrfs_insert_one_raid_extent(fs_info, bioc->logical, bioc->size,
345 num_stripes);
346 for (int i = 0; i < num_stripes; i++) {
347 u64 devid = bioc->stripes[i].dev->devid;
348 u64 physical = bioc->stripes[i].physical;
349 struct btrfs_raid_stride *raid_stride = &stripe_extent->strides[i];
350
351 btrfs_set_stack_raid_stride_devid(raid_stride, devid);
352 btrfs_set_stack_raid_stride_physical(raid_stride, physical);
353 }
354
355 stripe_key.objectid = bioc->logical;
356 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
357 stripe_key.offset = bioc->size;
358
359 ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
360 item_size);
361 if (ret == -EEXIST) {
362 ret = update_raid_extent_item(trans, &stripe_key, stripe_extent,
363 item_size);
364 if (ret)
365 btrfs_abort_transaction(trans, ret);
366 } else if (ret) {
367 btrfs_abort_transaction(trans, ret);
368 }
369
370 return ret;
371 }
372
btrfs_insert_raid_extent(struct btrfs_trans_handle * trans,struct btrfs_ordered_extent * ordered_extent)373 int btrfs_insert_raid_extent(struct btrfs_trans_handle *trans,
374 struct btrfs_ordered_extent *ordered_extent)
375 {
376 struct btrfs_io_context *bioc;
377 int ret;
378
379 if (!btrfs_fs_incompat(trans->fs_info, RAID_STRIPE_TREE))
380 return 0;
381
382 list_for_each_entry(bioc, &ordered_extent->bioc_list, rst_ordered_entry) {
383 ret = btrfs_insert_one_raid_extent(trans, bioc);
384 if (ret)
385 return ret;
386 }
387
388 while (!list_empty(&ordered_extent->bioc_list)) {
389 bioc = list_first_entry(&ordered_extent->bioc_list,
390 typeof(*bioc), rst_ordered_entry);
391 list_del(&bioc->rst_ordered_entry);
392 btrfs_put_bioc(bioc);
393 }
394
395 return 0;
396 }
397
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)398 int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
399 u64 logical, u64 *length, u64 map_type,
400 u32 stripe_index, struct btrfs_io_stripe *stripe)
401 {
402 struct btrfs_root *stripe_root = fs_info->stripe_root;
403 struct btrfs_stripe_extent *stripe_extent;
404 struct btrfs_key stripe_key;
405 struct btrfs_key found_key;
406 BTRFS_PATH_AUTO_FREE(path);
407 struct extent_buffer *leaf;
408 const u64 end = logical + *length;
409 int num_stripes;
410 u64 offset;
411 u64 found_logical;
412 u64 found_length;
413 u64 found_end;
414 int slot;
415 int ret;
416
417 if (unlikely(!stripe_root)) {
418 btrfs_err_rl(fs_info, "missing raid stripe tree root for logical %llu",
419 logical);
420 return -EUCLEAN;
421 }
422
423 stripe_key.objectid = logical;
424 stripe_key.type = BTRFS_RAID_STRIPE_KEY;
425 stripe_key.offset = 0;
426
427 path = btrfs_alloc_path();
428 if (!path)
429 return -ENOMEM;
430
431 if (stripe->rst_search_commit_root) {
432 path->skip_locking = true;
433 path->search_commit_root = true;
434 }
435
436 ret = btrfs_search_slot(NULL, stripe_root, &stripe_key, path, 0, 0);
437 if (ret < 0)
438 return ret;
439 if (ret) {
440 if (path->slots[0] != 0)
441 path->slots[0]--;
442 }
443
444 while (1) {
445 leaf = path->nodes[0];
446 slot = path->slots[0];
447
448 btrfs_item_key_to_cpu(leaf, &found_key, slot);
449 found_logical = found_key.objectid;
450 found_length = found_key.offset;
451 found_end = found_logical + found_length;
452
453 if (found_logical > end) {
454 ret = -ENODATA;
455 goto out;
456 }
457
458 if (in_range(logical, found_logical, found_length))
459 break;
460
461 ret = btrfs_next_item(stripe_root, path);
462 if (ret)
463 goto out;
464 }
465
466 offset = logical - found_logical;
467
468 /*
469 * If we have a logically contiguous, but physically non-continuous
470 * range, we need to split the bio. Record the length after which we
471 * must split the bio.
472 */
473 if (end > found_end)
474 *length -= end - found_end;
475
476 num_stripes = btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
477 stripe_extent = btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
478
479 for (int i = 0; i < num_stripes; i++) {
480 struct btrfs_raid_stride *stride = &stripe_extent->strides[i];
481 u64 devid = btrfs_raid_stride_devid(leaf, stride);
482 u64 physical = btrfs_raid_stride_physical(leaf, stride);
483
484 if (devid != stripe->dev->devid)
485 continue;
486
487 if ((map_type & BTRFS_BLOCK_GROUP_DUP) && stripe_index != i)
488 continue;
489
490 stripe->physical = physical + offset;
491
492 trace_btrfs_get_raid_extent_offset(fs_info, logical, *length,
493 stripe->physical, devid);
494
495 return 0;
496 }
497
498 /* If we're here, we haven't found the requested devid in the stripe. */
499 ret = -ENODATA;
500 out:
501 if (ret > 0)
502 ret = -ENODATA;
503 if (ret && ret != -EIO && !stripe->rst_search_commit_root) {
504 btrfs_debug(fs_info,
505 "cannot find raid-stripe for logical [%llu, %llu] devid %llu, profile %s",
506 logical, logical + *length, stripe->dev->devid,
507 btrfs_bg_type_to_raid_name(map_type));
508 }
509
510 return ret;
511 }
512