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 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 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 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 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 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 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