1 // SPDX-License-Identifier: GPL-2.0 2 3 #include <linux/err.h> 4 #include <linux/slab.h> 5 #include <linux/spinlock.h> 6 #include "ctree.h" 7 #include "volumes.h" 8 #include "extent_map.h" 9 #include "compression.h" 10 #include "btrfs_inode.h" 11 12 13 static struct kmem_cache *extent_map_cache; 14 15 int __init extent_map_init(void) 16 { 17 extent_map_cache = kmem_cache_create("btrfs_extent_map", 18 sizeof(struct extent_map), 0, 19 SLAB_MEM_SPREAD, NULL); 20 if (!extent_map_cache) 21 return -ENOMEM; 22 return 0; 23 } 24 25 void __cold extent_map_exit(void) 26 { 27 kmem_cache_destroy(extent_map_cache); 28 } 29 30 /** 31 * extent_map_tree_init - initialize extent map tree 32 * @tree: tree to initialize 33 * 34 * Initialize the extent tree @tree. Should be called for each new inode 35 * or other user of the extent_map interface. 36 */ 37 void extent_map_tree_init(struct extent_map_tree *tree) 38 { 39 tree->map = RB_ROOT_CACHED; 40 INIT_LIST_HEAD(&tree->modified_extents); 41 rwlock_init(&tree->lock); 42 } 43 44 /** 45 * alloc_extent_map - allocate new extent map structure 46 * 47 * Allocate a new extent_map structure. The new structure is 48 * returned with a reference count of one and needs to be 49 * freed using free_extent_map() 50 */ 51 struct extent_map *alloc_extent_map(void) 52 { 53 struct extent_map *em; 54 em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS); 55 if (!em) 56 return NULL; 57 RB_CLEAR_NODE(&em->rb_node); 58 em->flags = 0; 59 em->compress_type = BTRFS_COMPRESS_NONE; 60 em->generation = 0; 61 refcount_set(&em->refs, 1); 62 INIT_LIST_HEAD(&em->list); 63 return em; 64 } 65 66 /** 67 * free_extent_map - drop reference count of an extent_map 68 * @em: extent map being released 69 * 70 * Drops the reference out on @em by one and free the structure 71 * if the reference count hits zero. 72 */ 73 void free_extent_map(struct extent_map *em) 74 { 75 if (!em) 76 return; 77 WARN_ON(refcount_read(&em->refs) == 0); 78 if (refcount_dec_and_test(&em->refs)) { 79 WARN_ON(extent_map_in_tree(em)); 80 WARN_ON(!list_empty(&em->list)); 81 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) 82 kfree(em->map_lookup); 83 kmem_cache_free(extent_map_cache, em); 84 } 85 } 86 87 /* simple helper to do math around the end of an extent, handling wrap */ 88 static u64 range_end(u64 start, u64 len) 89 { 90 if (start + len < start) 91 return (u64)-1; 92 return start + len; 93 } 94 95 static int tree_insert(struct rb_root_cached *root, struct extent_map *em) 96 { 97 struct rb_node **p = &root->rb_root.rb_node; 98 struct rb_node *parent = NULL; 99 struct extent_map *entry = NULL; 100 struct rb_node *orig_parent = NULL; 101 u64 end = range_end(em->start, em->len); 102 bool leftmost = true; 103 104 while (*p) { 105 parent = *p; 106 entry = rb_entry(parent, struct extent_map, rb_node); 107 108 if (em->start < entry->start) { 109 p = &(*p)->rb_left; 110 } else if (em->start >= extent_map_end(entry)) { 111 p = &(*p)->rb_right; 112 leftmost = false; 113 } else { 114 return -EEXIST; 115 } 116 } 117 118 orig_parent = parent; 119 while (parent && em->start >= extent_map_end(entry)) { 120 parent = rb_next(parent); 121 entry = rb_entry(parent, struct extent_map, rb_node); 122 } 123 if (parent) 124 if (end > entry->start && em->start < extent_map_end(entry)) 125 return -EEXIST; 126 127 parent = orig_parent; 128 entry = rb_entry(parent, struct extent_map, rb_node); 129 while (parent && em->start < entry->start) { 130 parent = rb_prev(parent); 131 entry = rb_entry(parent, struct extent_map, rb_node); 132 } 133 if (parent) 134 if (end > entry->start && em->start < extent_map_end(entry)) 135 return -EEXIST; 136 137 rb_link_node(&em->rb_node, orig_parent, p); 138 rb_insert_color_cached(&em->rb_node, root, leftmost); 139 return 0; 140 } 141 142 /* 143 * search through the tree for an extent_map with a given offset. If 144 * it can't be found, try to find some neighboring extents 145 */ 146 static struct rb_node *__tree_search(struct rb_root *root, u64 offset, 147 struct rb_node **prev_ret, 148 struct rb_node **next_ret) 149 { 150 struct rb_node *n = root->rb_node; 151 struct rb_node *prev = NULL; 152 struct rb_node *orig_prev = NULL; 153 struct extent_map *entry; 154 struct extent_map *prev_entry = NULL; 155 156 while (n) { 157 entry = rb_entry(n, struct extent_map, rb_node); 158 prev = n; 159 prev_entry = entry; 160 161 if (offset < entry->start) 162 n = n->rb_left; 163 else if (offset >= extent_map_end(entry)) 164 n = n->rb_right; 165 else 166 return n; 167 } 168 169 if (prev_ret) { 170 orig_prev = prev; 171 while (prev && offset >= extent_map_end(prev_entry)) { 172 prev = rb_next(prev); 173 prev_entry = rb_entry(prev, struct extent_map, rb_node); 174 } 175 *prev_ret = prev; 176 prev = orig_prev; 177 } 178 179 if (next_ret) { 180 prev_entry = rb_entry(prev, struct extent_map, rb_node); 181 while (prev && offset < prev_entry->start) { 182 prev = rb_prev(prev); 183 prev_entry = rb_entry(prev, struct extent_map, rb_node); 184 } 185 *next_ret = prev; 186 } 187 return NULL; 188 } 189 190 /* check to see if two extent_map structs are adjacent and safe to merge */ 191 static int mergable_maps(struct extent_map *prev, struct extent_map *next) 192 { 193 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) 194 return 0; 195 196 /* 197 * don't merge compressed extents, we need to know their 198 * actual size 199 */ 200 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) 201 return 0; 202 203 if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || 204 test_bit(EXTENT_FLAG_LOGGING, &next->flags)) 205 return 0; 206 207 /* 208 * We don't want to merge stuff that hasn't been written to the log yet 209 * since it may not reflect exactly what is on disk, and that would be 210 * bad. 211 */ 212 if (!list_empty(&prev->list) || !list_empty(&next->list)) 213 return 0; 214 215 ASSERT(next->block_start != EXTENT_MAP_DELALLOC && 216 prev->block_start != EXTENT_MAP_DELALLOC); 217 218 if (prev->map_lookup || next->map_lookup) 219 ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) && 220 test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags)); 221 222 if (extent_map_end(prev) == next->start && 223 prev->flags == next->flags && 224 prev->map_lookup == next->map_lookup && 225 ((next->block_start == EXTENT_MAP_HOLE && 226 prev->block_start == EXTENT_MAP_HOLE) || 227 (next->block_start == EXTENT_MAP_INLINE && 228 prev->block_start == EXTENT_MAP_INLINE) || 229 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && 230 next->block_start == extent_map_block_end(prev)))) { 231 return 1; 232 } 233 return 0; 234 } 235 236 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) 237 { 238 struct extent_map *merge = NULL; 239 struct rb_node *rb; 240 241 /* 242 * We can't modify an extent map that is in the tree and that is being 243 * used by another task, as it can cause that other task to see it in 244 * inconsistent state during the merging. We always have 1 reference for 245 * the tree and 1 for this task (which is unpinning the extent map or 246 * clearing the logging flag), so anything > 2 means it's being used by 247 * other tasks too. 248 */ 249 if (refcount_read(&em->refs) > 2) 250 return; 251 252 if (em->start != 0) { 253 rb = rb_prev(&em->rb_node); 254 if (rb) 255 merge = rb_entry(rb, struct extent_map, rb_node); 256 if (rb && mergable_maps(merge, em)) { 257 em->start = merge->start; 258 em->orig_start = merge->orig_start; 259 em->len += merge->len; 260 em->block_len += merge->block_len; 261 em->block_start = merge->block_start; 262 em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; 263 em->mod_start = merge->mod_start; 264 em->generation = max(em->generation, merge->generation); 265 set_bit(EXTENT_FLAG_MERGED, &em->flags); 266 267 rb_erase_cached(&merge->rb_node, &tree->map); 268 RB_CLEAR_NODE(&merge->rb_node); 269 free_extent_map(merge); 270 } 271 } 272 273 rb = rb_next(&em->rb_node); 274 if (rb) 275 merge = rb_entry(rb, struct extent_map, rb_node); 276 if (rb && mergable_maps(em, merge)) { 277 em->len += merge->len; 278 em->block_len += merge->block_len; 279 rb_erase_cached(&merge->rb_node, &tree->map); 280 RB_CLEAR_NODE(&merge->rb_node); 281 em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; 282 em->generation = max(em->generation, merge->generation); 283 set_bit(EXTENT_FLAG_MERGED, &em->flags); 284 free_extent_map(merge); 285 } 286 } 287 288 /** 289 * unpin_extent_cache - unpin an extent from the cache 290 * @tree: tree to unpin the extent in 291 * @start: logical offset in the file 292 * @len: length of the extent 293 * @gen: generation that this extent has been modified in 294 * 295 * Called after an extent has been written to disk properly. Set the generation 296 * to the generation that actually added the file item to the inode so we know 297 * we need to sync this extent when we call fsync(). 298 */ 299 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, 300 u64 gen) 301 { 302 int ret = 0; 303 struct extent_map *em; 304 bool prealloc = false; 305 306 write_lock(&tree->lock); 307 em = lookup_extent_mapping(tree, start, len); 308 309 WARN_ON(!em || em->start != start); 310 311 if (!em) 312 goto out; 313 314 em->generation = gen; 315 clear_bit(EXTENT_FLAG_PINNED, &em->flags); 316 em->mod_start = em->start; 317 em->mod_len = em->len; 318 319 if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { 320 prealloc = true; 321 clear_bit(EXTENT_FLAG_FILLING, &em->flags); 322 } 323 324 try_merge_map(tree, em); 325 326 if (prealloc) { 327 em->mod_start = em->start; 328 em->mod_len = em->len; 329 } 330 331 free_extent_map(em); 332 out: 333 write_unlock(&tree->lock); 334 return ret; 335 336 } 337 338 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) 339 { 340 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); 341 if (extent_map_in_tree(em)) 342 try_merge_map(tree, em); 343 } 344 345 static inline void setup_extent_mapping(struct extent_map_tree *tree, 346 struct extent_map *em, 347 int modified) 348 { 349 refcount_inc(&em->refs); 350 em->mod_start = em->start; 351 em->mod_len = em->len; 352 353 if (modified) 354 list_move(&em->list, &tree->modified_extents); 355 else 356 try_merge_map(tree, em); 357 } 358 359 static void extent_map_device_set_bits(struct extent_map *em, unsigned bits) 360 { 361 struct map_lookup *map = em->map_lookup; 362 u64 stripe_size = em->orig_block_len; 363 int i; 364 365 for (i = 0; i < map->num_stripes; i++) { 366 struct btrfs_io_stripe *stripe = &map->stripes[i]; 367 struct btrfs_device *device = stripe->dev; 368 369 set_extent_bits_nowait(&device->alloc_state, stripe->physical, 370 stripe->physical + stripe_size - 1, bits); 371 } 372 } 373 374 static void extent_map_device_clear_bits(struct extent_map *em, unsigned bits) 375 { 376 struct map_lookup *map = em->map_lookup; 377 u64 stripe_size = em->orig_block_len; 378 int i; 379 380 for (i = 0; i < map->num_stripes; i++) { 381 struct btrfs_io_stripe *stripe = &map->stripes[i]; 382 struct btrfs_device *device = stripe->dev; 383 384 __clear_extent_bit(&device->alloc_state, stripe->physical, 385 stripe->physical + stripe_size - 1, bits, 386 NULL, GFP_NOWAIT, NULL); 387 } 388 } 389 390 /** 391 * Add new extent map to the extent tree 392 * 393 * @tree: tree to insert new map in 394 * @em: map to insert 395 * @modified: indicate whether the given @em should be added to the 396 * modified list, which indicates the extent needs to be logged 397 * 398 * Insert @em into @tree or perform a simple forward/backward merge with 399 * existing mappings. The extent_map struct passed in will be inserted 400 * into the tree directly, with an additional reference taken, or a 401 * reference dropped if the merge attempt was successful. 402 */ 403 int add_extent_mapping(struct extent_map_tree *tree, 404 struct extent_map *em, int modified) 405 { 406 int ret = 0; 407 408 lockdep_assert_held_write(&tree->lock); 409 410 ret = tree_insert(&tree->map, em); 411 if (ret) 412 goto out; 413 414 setup_extent_mapping(tree, em, modified); 415 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) { 416 extent_map_device_set_bits(em, CHUNK_ALLOCATED); 417 extent_map_device_clear_bits(em, CHUNK_TRIMMED); 418 } 419 out: 420 return ret; 421 } 422 423 static struct extent_map * 424 __lookup_extent_mapping(struct extent_map_tree *tree, 425 u64 start, u64 len, int strict) 426 { 427 struct extent_map *em; 428 struct rb_node *rb_node; 429 struct rb_node *prev = NULL; 430 struct rb_node *next = NULL; 431 u64 end = range_end(start, len); 432 433 rb_node = __tree_search(&tree->map.rb_root, start, &prev, &next); 434 if (!rb_node) { 435 if (prev) 436 rb_node = prev; 437 else if (next) 438 rb_node = next; 439 else 440 return NULL; 441 } 442 443 em = rb_entry(rb_node, struct extent_map, rb_node); 444 445 if (strict && !(end > em->start && start < extent_map_end(em))) 446 return NULL; 447 448 refcount_inc(&em->refs); 449 return em; 450 } 451 452 /** 453 * lookup_extent_mapping - lookup extent_map 454 * @tree: tree to lookup in 455 * @start: byte offset to start the search 456 * @len: length of the lookup range 457 * 458 * Find and return the first extent_map struct in @tree that intersects the 459 * [start, len] range. There may be additional objects in the tree that 460 * intersect, so check the object returned carefully to make sure that no 461 * additional lookups are needed. 462 */ 463 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, 464 u64 start, u64 len) 465 { 466 return __lookup_extent_mapping(tree, start, len, 1); 467 } 468 469 /** 470 * search_extent_mapping - find a nearby extent map 471 * @tree: tree to lookup in 472 * @start: byte offset to start the search 473 * @len: length of the lookup range 474 * 475 * Find and return the first extent_map struct in @tree that intersects the 476 * [start, len] range. 477 * 478 * If one can't be found, any nearby extent may be returned 479 */ 480 struct extent_map *search_extent_mapping(struct extent_map_tree *tree, 481 u64 start, u64 len) 482 { 483 return __lookup_extent_mapping(tree, start, len, 0); 484 } 485 486 /** 487 * remove_extent_mapping - removes an extent_map from the extent tree 488 * @tree: extent tree to remove from 489 * @em: extent map being removed 490 * 491 * Removes @em from @tree. No reference counts are dropped, and no checks 492 * are done to see if the range is in use 493 */ 494 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) 495 { 496 lockdep_assert_held_write(&tree->lock); 497 498 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); 499 rb_erase_cached(&em->rb_node, &tree->map); 500 if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) 501 list_del_init(&em->list); 502 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) 503 extent_map_device_clear_bits(em, CHUNK_ALLOCATED); 504 RB_CLEAR_NODE(&em->rb_node); 505 } 506 507 void replace_extent_mapping(struct extent_map_tree *tree, 508 struct extent_map *cur, 509 struct extent_map *new, 510 int modified) 511 { 512 lockdep_assert_held_write(&tree->lock); 513 514 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); 515 ASSERT(extent_map_in_tree(cur)); 516 if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) 517 list_del_init(&cur->list); 518 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); 519 RB_CLEAR_NODE(&cur->rb_node); 520 521 setup_extent_mapping(tree, new, modified); 522 } 523 524 static struct extent_map *next_extent_map(struct extent_map *em) 525 { 526 struct rb_node *next; 527 528 next = rb_next(&em->rb_node); 529 if (!next) 530 return NULL; 531 return container_of(next, struct extent_map, rb_node); 532 } 533 534 static struct extent_map *prev_extent_map(struct extent_map *em) 535 { 536 struct rb_node *prev; 537 538 prev = rb_prev(&em->rb_node); 539 if (!prev) 540 return NULL; 541 return container_of(prev, struct extent_map, rb_node); 542 } 543 544 /* 545 * Helper for btrfs_get_extent. Given an existing extent in the tree, 546 * the existing extent is the nearest extent to map_start, 547 * and an extent that you want to insert, deal with overlap and insert 548 * the best fitted new extent into the tree. 549 */ 550 static noinline int merge_extent_mapping(struct extent_map_tree *em_tree, 551 struct extent_map *existing, 552 struct extent_map *em, 553 u64 map_start) 554 { 555 struct extent_map *prev; 556 struct extent_map *next; 557 u64 start; 558 u64 end; 559 u64 start_diff; 560 561 BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); 562 563 if (existing->start > map_start) { 564 next = existing; 565 prev = prev_extent_map(next); 566 } else { 567 prev = existing; 568 next = next_extent_map(prev); 569 } 570 571 start = prev ? extent_map_end(prev) : em->start; 572 start = max_t(u64, start, em->start); 573 end = next ? next->start : extent_map_end(em); 574 end = min_t(u64, end, extent_map_end(em)); 575 start_diff = start - em->start; 576 em->start = start; 577 em->len = end - start; 578 if (em->block_start < EXTENT_MAP_LAST_BYTE && 579 !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { 580 em->block_start += start_diff; 581 em->block_len = em->len; 582 } 583 return add_extent_mapping(em_tree, em, 0); 584 } 585 586 /** 587 * Add extent mapping into em_tree 588 * 589 * @fs_info: the filesystem 590 * @em_tree: extent tree into which we want to insert the extent mapping 591 * @em_in: extent we are inserting 592 * @start: start of the logical range btrfs_get_extent() is requesting 593 * @len: length of the logical range btrfs_get_extent() is requesting 594 * 595 * Note that @em_in's range may be different from [start, start+len), 596 * but they must be overlapped. 597 * 598 * Insert @em_in into @em_tree. In case there is an overlapping range, handle 599 * the -EEXIST by either: 600 * a) Returning the existing extent in @em_in if @start is within the 601 * existing em. 602 * b) Merge the existing extent with @em_in passed in. 603 * 604 * Return 0 on success, otherwise -EEXIST. 605 * 606 */ 607 int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info, 608 struct extent_map_tree *em_tree, 609 struct extent_map **em_in, u64 start, u64 len) 610 { 611 int ret; 612 struct extent_map *em = *em_in; 613 614 ret = add_extent_mapping(em_tree, em, 0); 615 /* it is possible that someone inserted the extent into the tree 616 * while we had the lock dropped. It is also possible that 617 * an overlapping map exists in the tree 618 */ 619 if (ret == -EEXIST) { 620 struct extent_map *existing; 621 622 ret = 0; 623 624 existing = search_extent_mapping(em_tree, start, len); 625 626 trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); 627 628 /* 629 * existing will always be non-NULL, since there must be 630 * extent causing the -EEXIST. 631 */ 632 if (start >= existing->start && 633 start < extent_map_end(existing)) { 634 free_extent_map(em); 635 *em_in = existing; 636 ret = 0; 637 } else { 638 u64 orig_start = em->start; 639 u64 orig_len = em->len; 640 641 /* 642 * The existing extent map is the one nearest to 643 * the [start, start + len) range which overlaps 644 */ 645 ret = merge_extent_mapping(em_tree, existing, 646 em, start); 647 if (ret) { 648 free_extent_map(em); 649 *em_in = NULL; 650 WARN_ONCE(ret, 651 "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n", 652 ret, existing->start, existing->len, 653 orig_start, orig_len); 654 } 655 free_extent_map(existing); 656 } 657 } 658 659 ASSERT(ret == 0 || ret == -EEXIST); 660 return ret; 661 } 662 663 /* 664 * Drop all extent maps from a tree in the fastest possible way, rescheduling 665 * if needed. This avoids searching the tree, from the root down to the first 666 * extent map, before each deletion. 667 */ 668 static void drop_all_extent_maps_fast(struct extent_map_tree *tree) 669 { 670 write_lock(&tree->lock); 671 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) { 672 struct extent_map *em; 673 struct rb_node *node; 674 675 node = rb_first_cached(&tree->map); 676 em = rb_entry(node, struct extent_map, rb_node); 677 clear_bit(EXTENT_FLAG_PINNED, &em->flags); 678 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); 679 remove_extent_mapping(tree, em); 680 free_extent_map(em); 681 cond_resched_rwlock_write(&tree->lock); 682 } 683 write_unlock(&tree->lock); 684 } 685 686 /* 687 * Drop all extent maps in a given range. 688 * 689 * @inode: The target inode. 690 * @start: Start offset of the range. 691 * @end: End offset of the range (inclusive value). 692 * @skip_pinned: Indicate if pinned extent maps should be ignored or not. 693 * 694 * This drops all the extent maps that intersect the given range [@start, @end]. 695 * Extent maps that partially overlap the range and extend behind or beyond it, 696 * are split. 697 * The caller should have locked an appropriate file range in the inode's io 698 * tree before calling this function. 699 */ 700 void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end, 701 bool skip_pinned) 702 { 703 struct extent_map *split = NULL; 704 struct extent_map *split2 = NULL; 705 struct extent_map_tree *em_tree = &inode->extent_tree; 706 u64 len = end - start + 1; 707 bool testend = true; 708 709 WARN_ON(end < start); 710 if (end == (u64)-1) { 711 if (start == 0 && !skip_pinned) { 712 drop_all_extent_maps_fast(em_tree); 713 return; 714 } 715 len = (u64)-1; 716 testend = false; 717 } 718 while (1) { 719 struct extent_map *em; 720 u64 em_end; 721 u64 gen; 722 unsigned long flags; 723 bool ends_after_range = false; 724 bool no_splits = false; 725 bool modified; 726 bool compressed; 727 728 if (!split) 729 split = alloc_extent_map(); 730 if (!split2) 731 split2 = alloc_extent_map(); 732 if (!split || !split2) 733 no_splits = true; 734 735 write_lock(&em_tree->lock); 736 em = lookup_extent_mapping(em_tree, start, len); 737 if (!em) { 738 write_unlock(&em_tree->lock); 739 break; 740 } 741 em_end = extent_map_end(em); 742 if (testend && em_end > start + len) 743 ends_after_range = true; 744 if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) { 745 if (ends_after_range) { 746 free_extent_map(em); 747 write_unlock(&em_tree->lock); 748 break; 749 } 750 start = em_end; 751 if (testend) 752 len = start + len - em_end; 753 free_extent_map(em); 754 write_unlock(&em_tree->lock); 755 continue; 756 } 757 flags = em->flags; 758 gen = em->generation; 759 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags); 760 clear_bit(EXTENT_FLAG_PINNED, &em->flags); 761 clear_bit(EXTENT_FLAG_LOGGING, &flags); 762 modified = !list_empty(&em->list); 763 if (no_splits) 764 goto next; 765 766 if (em->start < start) { 767 split->start = em->start; 768 split->len = start - em->start; 769 770 if (em->block_start < EXTENT_MAP_LAST_BYTE) { 771 split->orig_start = em->orig_start; 772 split->block_start = em->block_start; 773 774 if (compressed) 775 split->block_len = em->block_len; 776 else 777 split->block_len = split->len; 778 split->orig_block_len = max(split->block_len, 779 em->orig_block_len); 780 split->ram_bytes = em->ram_bytes; 781 } else { 782 split->orig_start = split->start; 783 split->block_len = 0; 784 split->block_start = em->block_start; 785 split->orig_block_len = 0; 786 split->ram_bytes = split->len; 787 } 788 789 split->generation = gen; 790 split->flags = flags; 791 split->compress_type = em->compress_type; 792 replace_extent_mapping(em_tree, em, split, modified); 793 free_extent_map(split); 794 split = split2; 795 split2 = NULL; 796 } 797 if (ends_after_range) { 798 split->start = start + len; 799 split->len = em_end - (start + len); 800 split->block_start = em->block_start; 801 split->flags = flags; 802 split->compress_type = em->compress_type; 803 split->generation = gen; 804 805 if (em->block_start < EXTENT_MAP_LAST_BYTE) { 806 split->orig_block_len = max(em->block_len, 807 em->orig_block_len); 808 809 split->ram_bytes = em->ram_bytes; 810 if (compressed) { 811 split->block_len = em->block_len; 812 split->orig_start = em->orig_start; 813 } else { 814 const u64 diff = start + len - em->start; 815 816 split->block_len = split->len; 817 split->block_start += diff; 818 split->orig_start = em->orig_start; 819 } 820 } else { 821 split->ram_bytes = split->len; 822 split->orig_start = split->start; 823 split->block_len = 0; 824 split->orig_block_len = 0; 825 } 826 827 if (extent_map_in_tree(em)) { 828 replace_extent_mapping(em_tree, em, split, 829 modified); 830 } else { 831 int ret; 832 833 ret = add_extent_mapping(em_tree, split, 834 modified); 835 /* Logic error, shouldn't happen. */ 836 ASSERT(ret == 0); 837 if (WARN_ON(ret != 0) && modified) 838 btrfs_set_inode_full_sync(inode); 839 } 840 free_extent_map(split); 841 split = NULL; 842 } 843 next: 844 if (extent_map_in_tree(em)) { 845 /* 846 * If the extent map is still in the tree it means that 847 * either of the following is true: 848 * 849 * 1) It fits entirely in our range (doesn't end beyond 850 * it or starts before it); 851 * 852 * 2) It starts before our range and/or ends after our 853 * range, and we were not able to allocate the extent 854 * maps for split operations, @split and @split2. 855 * 856 * If we are at case 2) then we just remove the entire 857 * extent map - this is fine since if anyone needs it to 858 * access the subranges outside our range, will just 859 * load it again from the subvolume tree's file extent 860 * item. However if the extent map was in the list of 861 * modified extents, then we must mark the inode for a 862 * full fsync, otherwise a fast fsync will miss this 863 * extent if it's new and needs to be logged. 864 */ 865 if ((em->start < start || ends_after_range) && modified) { 866 ASSERT(no_splits); 867 btrfs_set_inode_full_sync(inode); 868 } 869 remove_extent_mapping(em_tree, em); 870 } 871 write_unlock(&em_tree->lock); 872 873 /* Once for us. */ 874 free_extent_map(em); 875 /* And once for the tree. */ 876 free_extent_map(em); 877 } 878 879 free_extent_map(split); 880 free_extent_map(split2); 881 } 882 883 /* 884 * Replace a range in the inode's extent map tree with a new extent map. 885 * 886 * @inode: The target inode. 887 * @new_em: The new extent map to add to the inode's extent map tree. 888 * @modified: Indicate if the new extent map should be added to the list of 889 * modified extents (for fast fsync tracking). 890 * 891 * Drops all the extent maps in the inode's extent map tree that intersect the 892 * range of the new extent map and adds the new extent map to the tree. 893 * The caller should have locked an appropriate file range in the inode's io 894 * tree before calling this function. 895 */ 896 int btrfs_replace_extent_map_range(struct btrfs_inode *inode, 897 struct extent_map *new_em, 898 bool modified) 899 { 900 const u64 end = new_em->start + new_em->len - 1; 901 struct extent_map_tree *tree = &inode->extent_tree; 902 int ret; 903 904 ASSERT(!extent_map_in_tree(new_em)); 905 906 /* 907 * The caller has locked an appropriate file range in the inode's io 908 * tree, but getting -EEXIST when adding the new extent map can still 909 * happen in case there are extents that partially cover the range, and 910 * this is due to two tasks operating on different parts of the extent. 911 * See commit 18e83ac75bfe67 ("Btrfs: fix unexpected EEXIST from 912 * btrfs_get_extent") for an example and details. 913 */ 914 do { 915 btrfs_drop_extent_map_range(inode, new_em->start, end, false); 916 write_lock(&tree->lock); 917 ret = add_extent_mapping(tree, new_em, modified); 918 write_unlock(&tree->lock); 919 } while (ret == -EEXIST); 920 921 return ret; 922 } 923