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 "extent_map.h" 8 #include "compression.h" 9 10 11 static struct kmem_cache *extent_map_cache; 12 13 int __init extent_map_init(void) 14 { 15 extent_map_cache = kmem_cache_create("btrfs_extent_map", 16 sizeof(struct extent_map), 0, 17 SLAB_MEM_SPREAD, NULL); 18 if (!extent_map_cache) 19 return -ENOMEM; 20 return 0; 21 } 22 23 void __cold extent_map_exit(void) 24 { 25 kmem_cache_destroy(extent_map_cache); 26 } 27 28 /** 29 * extent_map_tree_init - initialize extent map tree 30 * @tree: tree to initialize 31 * 32 * Initialize the extent tree @tree. Should be called for each new inode 33 * or other user of the extent_map interface. 34 */ 35 void extent_map_tree_init(struct extent_map_tree *tree) 36 { 37 tree->map = RB_ROOT_CACHED; 38 INIT_LIST_HEAD(&tree->modified_extents); 39 rwlock_init(&tree->lock); 40 } 41 42 /** 43 * alloc_extent_map - allocate new extent map structure 44 * 45 * Allocate a new extent_map structure. The new structure is 46 * returned with a reference count of one and needs to be 47 * freed using free_extent_map() 48 */ 49 struct extent_map *alloc_extent_map(void) 50 { 51 struct extent_map *em; 52 em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS); 53 if (!em) 54 return NULL; 55 RB_CLEAR_NODE(&em->rb_node); 56 em->flags = 0; 57 em->compress_type = BTRFS_COMPRESS_NONE; 58 em->generation = 0; 59 refcount_set(&em->refs, 1); 60 INIT_LIST_HEAD(&em->list); 61 return em; 62 } 63 64 /** 65 * free_extent_map - drop reference count of an extent_map 66 * @em: extent map being released 67 * 68 * Drops the reference out on @em by one and free the structure 69 * if the reference count hits zero. 70 */ 71 void free_extent_map(struct extent_map *em) 72 { 73 if (!em) 74 return; 75 WARN_ON(refcount_read(&em->refs) == 0); 76 if (refcount_dec_and_test(&em->refs)) { 77 WARN_ON(extent_map_in_tree(em)); 78 WARN_ON(!list_empty(&em->list)); 79 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) 80 kfree(em->map_lookup); 81 kmem_cache_free(extent_map_cache, em); 82 } 83 } 84 85 /* simple helper to do math around the end of an extent, handling wrap */ 86 static u64 range_end(u64 start, u64 len) 87 { 88 if (start + len < start) 89 return (u64)-1; 90 return start + len; 91 } 92 93 static int tree_insert(struct rb_root_cached *root, struct extent_map *em) 94 { 95 struct rb_node **p = &root->rb_root.rb_node; 96 struct rb_node *parent = NULL; 97 struct extent_map *entry = NULL; 98 struct rb_node *orig_parent = NULL; 99 u64 end = range_end(em->start, em->len); 100 bool leftmost = true; 101 102 while (*p) { 103 parent = *p; 104 entry = rb_entry(parent, struct extent_map, rb_node); 105 106 if (em->start < entry->start) { 107 p = &(*p)->rb_left; 108 } else if (em->start >= extent_map_end(entry)) { 109 p = &(*p)->rb_right; 110 leftmost = false; 111 } else { 112 return -EEXIST; 113 } 114 } 115 116 orig_parent = parent; 117 while (parent && em->start >= extent_map_end(entry)) { 118 parent = rb_next(parent); 119 entry = rb_entry(parent, struct extent_map, rb_node); 120 } 121 if (parent) 122 if (end > entry->start && em->start < extent_map_end(entry)) 123 return -EEXIST; 124 125 parent = orig_parent; 126 entry = rb_entry(parent, struct extent_map, rb_node); 127 while (parent && em->start < entry->start) { 128 parent = rb_prev(parent); 129 entry = rb_entry(parent, struct extent_map, rb_node); 130 } 131 if (parent) 132 if (end > entry->start && em->start < extent_map_end(entry)) 133 return -EEXIST; 134 135 rb_link_node(&em->rb_node, orig_parent, p); 136 rb_insert_color_cached(&em->rb_node, root, leftmost); 137 return 0; 138 } 139 140 /* 141 * search through the tree for an extent_map with a given offset. If 142 * it can't be found, try to find some neighboring extents 143 */ 144 static struct rb_node *__tree_search(struct rb_root *root, u64 offset, 145 struct rb_node **prev_ret, 146 struct rb_node **next_ret) 147 { 148 struct rb_node *n = root->rb_node; 149 struct rb_node *prev = NULL; 150 struct rb_node *orig_prev = NULL; 151 struct extent_map *entry; 152 struct extent_map *prev_entry = NULL; 153 154 while (n) { 155 entry = rb_entry(n, struct extent_map, rb_node); 156 prev = n; 157 prev_entry = entry; 158 159 if (offset < entry->start) 160 n = n->rb_left; 161 else if (offset >= extent_map_end(entry)) 162 n = n->rb_right; 163 else 164 return n; 165 } 166 167 if (prev_ret) { 168 orig_prev = prev; 169 while (prev && offset >= extent_map_end(prev_entry)) { 170 prev = rb_next(prev); 171 prev_entry = rb_entry(prev, struct extent_map, rb_node); 172 } 173 *prev_ret = prev; 174 prev = orig_prev; 175 } 176 177 if (next_ret) { 178 prev_entry = rb_entry(prev, struct extent_map, rb_node); 179 while (prev && offset < prev_entry->start) { 180 prev = rb_prev(prev); 181 prev_entry = rb_entry(prev, struct extent_map, rb_node); 182 } 183 *next_ret = prev; 184 } 185 return NULL; 186 } 187 188 /* check to see if two extent_map structs are adjacent and safe to merge */ 189 static int mergable_maps(struct extent_map *prev, struct extent_map *next) 190 { 191 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) 192 return 0; 193 194 /* 195 * don't merge compressed extents, we need to know their 196 * actual size 197 */ 198 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) 199 return 0; 200 201 if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || 202 test_bit(EXTENT_FLAG_LOGGING, &next->flags)) 203 return 0; 204 205 /* 206 * We don't want to merge stuff that hasn't been written to the log yet 207 * since it may not reflect exactly what is on disk, and that would be 208 * bad. 209 */ 210 if (!list_empty(&prev->list) || !list_empty(&next->list)) 211 return 0; 212 213 ASSERT(next->block_start != EXTENT_MAP_DELALLOC && 214 prev->block_start != EXTENT_MAP_DELALLOC); 215 216 if (extent_map_end(prev) == next->start && 217 prev->flags == next->flags && 218 prev->bdev == next->bdev && 219 ((next->block_start == EXTENT_MAP_HOLE && 220 prev->block_start == EXTENT_MAP_HOLE) || 221 (next->block_start == EXTENT_MAP_INLINE && 222 prev->block_start == EXTENT_MAP_INLINE) || 223 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && 224 next->block_start == extent_map_block_end(prev)))) { 225 return 1; 226 } 227 return 0; 228 } 229 230 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) 231 { 232 struct extent_map *merge = NULL; 233 struct rb_node *rb; 234 235 if (em->start != 0) { 236 rb = rb_prev(&em->rb_node); 237 if (rb) 238 merge = rb_entry(rb, struct extent_map, rb_node); 239 if (rb && mergable_maps(merge, em)) { 240 em->start = merge->start; 241 em->orig_start = merge->orig_start; 242 em->len += merge->len; 243 em->block_len += merge->block_len; 244 em->block_start = merge->block_start; 245 em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; 246 em->mod_start = merge->mod_start; 247 em->generation = max(em->generation, merge->generation); 248 249 rb_erase_cached(&merge->rb_node, &tree->map); 250 RB_CLEAR_NODE(&merge->rb_node); 251 free_extent_map(merge); 252 } 253 } 254 255 rb = rb_next(&em->rb_node); 256 if (rb) 257 merge = rb_entry(rb, struct extent_map, rb_node); 258 if (rb && mergable_maps(em, merge)) { 259 em->len += merge->len; 260 em->block_len += merge->block_len; 261 rb_erase_cached(&merge->rb_node, &tree->map); 262 RB_CLEAR_NODE(&merge->rb_node); 263 em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; 264 em->generation = max(em->generation, merge->generation); 265 free_extent_map(merge); 266 } 267 } 268 269 /** 270 * unpin_extent_cache - unpin an extent from the cache 271 * @tree: tree to unpin the extent in 272 * @start: logical offset in the file 273 * @len: length of the extent 274 * @gen: generation that this extent has been modified in 275 * 276 * Called after an extent has been written to disk properly. Set the generation 277 * to the generation that actually added the file item to the inode so we know 278 * we need to sync this extent when we call fsync(). 279 */ 280 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, 281 u64 gen) 282 { 283 int ret = 0; 284 struct extent_map *em; 285 bool prealloc = false; 286 287 write_lock(&tree->lock); 288 em = lookup_extent_mapping(tree, start, len); 289 290 WARN_ON(!em || em->start != start); 291 292 if (!em) 293 goto out; 294 295 em->generation = gen; 296 clear_bit(EXTENT_FLAG_PINNED, &em->flags); 297 em->mod_start = em->start; 298 em->mod_len = em->len; 299 300 if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { 301 prealloc = true; 302 clear_bit(EXTENT_FLAG_FILLING, &em->flags); 303 } 304 305 try_merge_map(tree, em); 306 307 if (prealloc) { 308 em->mod_start = em->start; 309 em->mod_len = em->len; 310 } 311 312 free_extent_map(em); 313 out: 314 write_unlock(&tree->lock); 315 return ret; 316 317 } 318 319 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) 320 { 321 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); 322 if (extent_map_in_tree(em)) 323 try_merge_map(tree, em); 324 } 325 326 static inline void setup_extent_mapping(struct extent_map_tree *tree, 327 struct extent_map *em, 328 int modified) 329 { 330 refcount_inc(&em->refs); 331 em->mod_start = em->start; 332 em->mod_len = em->len; 333 334 if (modified) 335 list_move(&em->list, &tree->modified_extents); 336 else 337 try_merge_map(tree, em); 338 } 339 340 /** 341 * add_extent_mapping - add new extent map to the extent tree 342 * @tree: tree to insert new map in 343 * @em: map to insert 344 * 345 * Insert @em into @tree or perform a simple forward/backward merge with 346 * existing mappings. The extent_map struct passed in will be inserted 347 * into the tree directly, with an additional reference taken, or a 348 * reference dropped if the merge attempt was successful. 349 */ 350 int add_extent_mapping(struct extent_map_tree *tree, 351 struct extent_map *em, int modified) 352 { 353 int ret = 0; 354 355 ret = tree_insert(&tree->map, em); 356 if (ret) 357 goto out; 358 359 setup_extent_mapping(tree, em, modified); 360 out: 361 return ret; 362 } 363 364 static struct extent_map * 365 __lookup_extent_mapping(struct extent_map_tree *tree, 366 u64 start, u64 len, int strict) 367 { 368 struct extent_map *em; 369 struct rb_node *rb_node; 370 struct rb_node *prev = NULL; 371 struct rb_node *next = NULL; 372 u64 end = range_end(start, len); 373 374 rb_node = __tree_search(&tree->map.rb_root, start, &prev, &next); 375 if (!rb_node) { 376 if (prev) 377 rb_node = prev; 378 else if (next) 379 rb_node = next; 380 else 381 return NULL; 382 } 383 384 em = rb_entry(rb_node, struct extent_map, rb_node); 385 386 if (strict && !(end > em->start && start < extent_map_end(em))) 387 return NULL; 388 389 refcount_inc(&em->refs); 390 return em; 391 } 392 393 /** 394 * lookup_extent_mapping - lookup extent_map 395 * @tree: tree to lookup in 396 * @start: byte offset to start the search 397 * @len: length of the lookup range 398 * 399 * Find and return the first extent_map struct in @tree that intersects the 400 * [start, len] range. There may be additional objects in the tree that 401 * intersect, so check the object returned carefully to make sure that no 402 * additional lookups are needed. 403 */ 404 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, 405 u64 start, u64 len) 406 { 407 return __lookup_extent_mapping(tree, start, len, 1); 408 } 409 410 /** 411 * search_extent_mapping - find a nearby extent map 412 * @tree: tree to lookup in 413 * @start: byte offset to start the search 414 * @len: length of the lookup range 415 * 416 * Find and return the first extent_map struct in @tree that intersects the 417 * [start, len] range. 418 * 419 * If one can't be found, any nearby extent may be returned 420 */ 421 struct extent_map *search_extent_mapping(struct extent_map_tree *tree, 422 u64 start, u64 len) 423 { 424 return __lookup_extent_mapping(tree, start, len, 0); 425 } 426 427 /** 428 * remove_extent_mapping - removes an extent_map from the extent tree 429 * @tree: extent tree to remove from 430 * @em: extent map being removed 431 * 432 * Removes @em from @tree. No reference counts are dropped, and no checks 433 * are done to see if the range is in use 434 */ 435 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) 436 { 437 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); 438 rb_erase_cached(&em->rb_node, &tree->map); 439 if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) 440 list_del_init(&em->list); 441 RB_CLEAR_NODE(&em->rb_node); 442 } 443 444 void replace_extent_mapping(struct extent_map_tree *tree, 445 struct extent_map *cur, 446 struct extent_map *new, 447 int modified) 448 { 449 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); 450 ASSERT(extent_map_in_tree(cur)); 451 if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) 452 list_del_init(&cur->list); 453 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); 454 RB_CLEAR_NODE(&cur->rb_node); 455 456 setup_extent_mapping(tree, new, modified); 457 } 458 459 static struct extent_map *next_extent_map(struct extent_map *em) 460 { 461 struct rb_node *next; 462 463 next = rb_next(&em->rb_node); 464 if (!next) 465 return NULL; 466 return container_of(next, struct extent_map, rb_node); 467 } 468 469 static struct extent_map *prev_extent_map(struct extent_map *em) 470 { 471 struct rb_node *prev; 472 473 prev = rb_prev(&em->rb_node); 474 if (!prev) 475 return NULL; 476 return container_of(prev, struct extent_map, rb_node); 477 } 478 479 /* 480 * Helper for btrfs_get_extent. Given an existing extent in the tree, 481 * the existing extent is the nearest extent to map_start, 482 * and an extent that you want to insert, deal with overlap and insert 483 * the best fitted new extent into the tree. 484 */ 485 static noinline int merge_extent_mapping(struct extent_map_tree *em_tree, 486 struct extent_map *existing, 487 struct extent_map *em, 488 u64 map_start) 489 { 490 struct extent_map *prev; 491 struct extent_map *next; 492 u64 start; 493 u64 end; 494 u64 start_diff; 495 496 BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); 497 498 if (existing->start > map_start) { 499 next = existing; 500 prev = prev_extent_map(next); 501 } else { 502 prev = existing; 503 next = next_extent_map(prev); 504 } 505 506 start = prev ? extent_map_end(prev) : em->start; 507 start = max_t(u64, start, em->start); 508 end = next ? next->start : extent_map_end(em); 509 end = min_t(u64, end, extent_map_end(em)); 510 start_diff = start - em->start; 511 em->start = start; 512 em->len = end - start; 513 if (em->block_start < EXTENT_MAP_LAST_BYTE && 514 !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { 515 em->block_start += start_diff; 516 em->block_len = em->len; 517 } 518 return add_extent_mapping(em_tree, em, 0); 519 } 520 521 /** 522 * btrfs_add_extent_mapping - add extent mapping into em_tree 523 * @fs_info - used for tracepoint 524 * @em_tree - the extent tree into which we want to insert the extent mapping 525 * @em_in - extent we are inserting 526 * @start - start of the logical range btrfs_get_extent() is requesting 527 * @len - length of the logical range btrfs_get_extent() is requesting 528 * 529 * Note that @em_in's range may be different from [start, start+len), 530 * but they must be overlapped. 531 * 532 * Insert @em_in into @em_tree. In case there is an overlapping range, handle 533 * the -EEXIST by either: 534 * a) Returning the existing extent in @em_in if @start is within the 535 * existing em. 536 * b) Merge the existing extent with @em_in passed in. 537 * 538 * Return 0 on success, otherwise -EEXIST. 539 * 540 */ 541 int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info, 542 struct extent_map_tree *em_tree, 543 struct extent_map **em_in, u64 start, u64 len) 544 { 545 int ret; 546 struct extent_map *em = *em_in; 547 548 ret = add_extent_mapping(em_tree, em, 0); 549 /* it is possible that someone inserted the extent into the tree 550 * while we had the lock dropped. It is also possible that 551 * an overlapping map exists in the tree 552 */ 553 if (ret == -EEXIST) { 554 struct extent_map *existing; 555 556 ret = 0; 557 558 existing = search_extent_mapping(em_tree, start, len); 559 560 trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); 561 562 /* 563 * existing will always be non-NULL, since there must be 564 * extent causing the -EEXIST. 565 */ 566 if (start >= existing->start && 567 start < extent_map_end(existing)) { 568 free_extent_map(em); 569 *em_in = existing; 570 ret = 0; 571 } else { 572 u64 orig_start = em->start; 573 u64 orig_len = em->len; 574 575 /* 576 * The existing extent map is the one nearest to 577 * the [start, start + len) range which overlaps 578 */ 579 ret = merge_extent_mapping(em_tree, existing, 580 em, start); 581 if (ret) { 582 free_extent_map(em); 583 *em_in = NULL; 584 WARN_ONCE(ret, 585 "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n", 586 ret, existing->start, existing->len, 587 orig_start, orig_len); 588 } 589 free_extent_map(existing); 590 } 591 } 592 593 ASSERT(ret == 0 || ret == -EEXIST); 594 return ret; 595 } 596