1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2007 Oracle. All rights reserved. 4 */ 5 6 #include <linux/slab.h> 7 #include <linux/blkdev.h> 8 #include <linux/writeback.h> 9 #include <linux/sched/mm.h> 10 #include "ctree.h" 11 #include "transaction.h" 12 #include "btrfs_inode.h" 13 #include "extent_io.h" 14 #include "disk-io.h" 15 #include "compression.h" 16 17 static struct kmem_cache *btrfs_ordered_extent_cache; 18 19 static u64 entry_end(struct btrfs_ordered_extent *entry) 20 { 21 if (entry->file_offset + entry->len < entry->file_offset) 22 return (u64)-1; 23 return entry->file_offset + entry->len; 24 } 25 26 /* returns NULL if the insertion worked, or it returns the node it did find 27 * in the tree 28 */ 29 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset, 30 struct rb_node *node) 31 { 32 struct rb_node **p = &root->rb_node; 33 struct rb_node *parent = NULL; 34 struct btrfs_ordered_extent *entry; 35 36 while (*p) { 37 parent = *p; 38 entry = rb_entry(parent, struct btrfs_ordered_extent, rb_node); 39 40 if (file_offset < entry->file_offset) 41 p = &(*p)->rb_left; 42 else if (file_offset >= entry_end(entry)) 43 p = &(*p)->rb_right; 44 else 45 return parent; 46 } 47 48 rb_link_node(node, parent, p); 49 rb_insert_color(node, root); 50 return NULL; 51 } 52 53 static void ordered_data_tree_panic(struct inode *inode, int errno, 54 u64 offset) 55 { 56 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); 57 btrfs_panic(fs_info, errno, 58 "Inconsistency in ordered tree at offset %llu", offset); 59 } 60 61 /* 62 * look for a given offset in the tree, and if it can't be found return the 63 * first lesser offset 64 */ 65 static struct rb_node *__tree_search(struct rb_root *root, u64 file_offset, 66 struct rb_node **prev_ret) 67 { 68 struct rb_node *n = root->rb_node; 69 struct rb_node *prev = NULL; 70 struct rb_node *test; 71 struct btrfs_ordered_extent *entry; 72 struct btrfs_ordered_extent *prev_entry = NULL; 73 74 while (n) { 75 entry = rb_entry(n, struct btrfs_ordered_extent, rb_node); 76 prev = n; 77 prev_entry = entry; 78 79 if (file_offset < entry->file_offset) 80 n = n->rb_left; 81 else if (file_offset >= entry_end(entry)) 82 n = n->rb_right; 83 else 84 return n; 85 } 86 if (!prev_ret) 87 return NULL; 88 89 while (prev && file_offset >= entry_end(prev_entry)) { 90 test = rb_next(prev); 91 if (!test) 92 break; 93 prev_entry = rb_entry(test, struct btrfs_ordered_extent, 94 rb_node); 95 if (file_offset < entry_end(prev_entry)) 96 break; 97 98 prev = test; 99 } 100 if (prev) 101 prev_entry = rb_entry(prev, struct btrfs_ordered_extent, 102 rb_node); 103 while (prev && file_offset < entry_end(prev_entry)) { 104 test = rb_prev(prev); 105 if (!test) 106 break; 107 prev_entry = rb_entry(test, struct btrfs_ordered_extent, 108 rb_node); 109 prev = test; 110 } 111 *prev_ret = prev; 112 return NULL; 113 } 114 115 /* 116 * helper to check if a given offset is inside a given entry 117 */ 118 static int offset_in_entry(struct btrfs_ordered_extent *entry, u64 file_offset) 119 { 120 if (file_offset < entry->file_offset || 121 entry->file_offset + entry->len <= file_offset) 122 return 0; 123 return 1; 124 } 125 126 static int range_overlaps(struct btrfs_ordered_extent *entry, u64 file_offset, 127 u64 len) 128 { 129 if (file_offset + len <= entry->file_offset || 130 entry->file_offset + entry->len <= file_offset) 131 return 0; 132 return 1; 133 } 134 135 /* 136 * look find the first ordered struct that has this offset, otherwise 137 * the first one less than this offset 138 */ 139 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, 140 u64 file_offset) 141 { 142 struct rb_root *root = &tree->tree; 143 struct rb_node *prev = NULL; 144 struct rb_node *ret; 145 struct btrfs_ordered_extent *entry; 146 147 if (tree->last) { 148 entry = rb_entry(tree->last, struct btrfs_ordered_extent, 149 rb_node); 150 if (offset_in_entry(entry, file_offset)) 151 return tree->last; 152 } 153 ret = __tree_search(root, file_offset, &prev); 154 if (!ret) 155 ret = prev; 156 if (ret) 157 tree->last = ret; 158 return ret; 159 } 160 161 /* allocate and add a new ordered_extent into the per-inode tree. 162 * file_offset is the logical offset in the file 163 * 164 * start is the disk block number of an extent already reserved in the 165 * extent allocation tree 166 * 167 * len is the length of the extent 168 * 169 * The tree is given a single reference on the ordered extent that was 170 * inserted. 171 */ 172 static int __btrfs_add_ordered_extent(struct inode *inode, u64 file_offset, 173 u64 start, u64 len, u64 disk_len, 174 int type, int dio, int compress_type) 175 { 176 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); 177 struct btrfs_root *root = BTRFS_I(inode)->root; 178 struct btrfs_ordered_inode_tree *tree; 179 struct rb_node *node; 180 struct btrfs_ordered_extent *entry; 181 182 tree = &BTRFS_I(inode)->ordered_tree; 183 entry = kmem_cache_zalloc(btrfs_ordered_extent_cache, GFP_NOFS); 184 if (!entry) 185 return -ENOMEM; 186 187 entry->file_offset = file_offset; 188 entry->start = start; 189 entry->len = len; 190 entry->disk_len = disk_len; 191 entry->bytes_left = len; 192 entry->inode = igrab(inode); 193 entry->compress_type = compress_type; 194 entry->truncated_len = (u64)-1; 195 if (type != BTRFS_ORDERED_IO_DONE && type != BTRFS_ORDERED_COMPLETE) 196 set_bit(type, &entry->flags); 197 198 if (dio) 199 set_bit(BTRFS_ORDERED_DIRECT, &entry->flags); 200 201 /* one ref for the tree */ 202 refcount_set(&entry->refs, 1); 203 init_waitqueue_head(&entry->wait); 204 INIT_LIST_HEAD(&entry->list); 205 INIT_LIST_HEAD(&entry->root_extent_list); 206 INIT_LIST_HEAD(&entry->work_list); 207 init_completion(&entry->completion); 208 INIT_LIST_HEAD(&entry->log_list); 209 INIT_LIST_HEAD(&entry->trans_list); 210 211 trace_btrfs_ordered_extent_add(inode, entry); 212 213 spin_lock_irq(&tree->lock); 214 node = tree_insert(&tree->tree, file_offset, 215 &entry->rb_node); 216 if (node) 217 ordered_data_tree_panic(inode, -EEXIST, file_offset); 218 spin_unlock_irq(&tree->lock); 219 220 spin_lock(&root->ordered_extent_lock); 221 list_add_tail(&entry->root_extent_list, 222 &root->ordered_extents); 223 root->nr_ordered_extents++; 224 if (root->nr_ordered_extents == 1) { 225 spin_lock(&fs_info->ordered_root_lock); 226 BUG_ON(!list_empty(&root->ordered_root)); 227 list_add_tail(&root->ordered_root, &fs_info->ordered_roots); 228 spin_unlock(&fs_info->ordered_root_lock); 229 } 230 spin_unlock(&root->ordered_extent_lock); 231 232 /* 233 * We don't need the count_max_extents here, we can assume that all of 234 * that work has been done at higher layers, so this is truly the 235 * smallest the extent is going to get. 236 */ 237 spin_lock(&BTRFS_I(inode)->lock); 238 btrfs_mod_outstanding_extents(BTRFS_I(inode), 1); 239 spin_unlock(&BTRFS_I(inode)->lock); 240 241 return 0; 242 } 243 244 int btrfs_add_ordered_extent(struct inode *inode, u64 file_offset, 245 u64 start, u64 len, u64 disk_len, int type) 246 { 247 return __btrfs_add_ordered_extent(inode, file_offset, start, len, 248 disk_len, type, 0, 249 BTRFS_COMPRESS_NONE); 250 } 251 252 int btrfs_add_ordered_extent_dio(struct inode *inode, u64 file_offset, 253 u64 start, u64 len, u64 disk_len, int type) 254 { 255 return __btrfs_add_ordered_extent(inode, file_offset, start, len, 256 disk_len, type, 1, 257 BTRFS_COMPRESS_NONE); 258 } 259 260 int btrfs_add_ordered_extent_compress(struct inode *inode, u64 file_offset, 261 u64 start, u64 len, u64 disk_len, 262 int type, int compress_type) 263 { 264 return __btrfs_add_ordered_extent(inode, file_offset, start, len, 265 disk_len, type, 0, 266 compress_type); 267 } 268 269 /* 270 * Add a struct btrfs_ordered_sum into the list of checksums to be inserted 271 * when an ordered extent is finished. If the list covers more than one 272 * ordered extent, it is split across multiples. 273 */ 274 void btrfs_add_ordered_sum(struct inode *inode, 275 struct btrfs_ordered_extent *entry, 276 struct btrfs_ordered_sum *sum) 277 { 278 struct btrfs_ordered_inode_tree *tree; 279 280 tree = &BTRFS_I(inode)->ordered_tree; 281 spin_lock_irq(&tree->lock); 282 list_add_tail(&sum->list, &entry->list); 283 spin_unlock_irq(&tree->lock); 284 } 285 286 /* 287 * this is used to account for finished IO across a given range 288 * of the file. The IO may span ordered extents. If 289 * a given ordered_extent is completely done, 1 is returned, otherwise 290 * 0. 291 * 292 * test_and_set_bit on a flag in the struct btrfs_ordered_extent is used 293 * to make sure this function only returns 1 once for a given ordered extent. 294 * 295 * file_offset is updated to one byte past the range that is recorded as 296 * complete. This allows you to walk forward in the file. 297 */ 298 int btrfs_dec_test_first_ordered_pending(struct inode *inode, 299 struct btrfs_ordered_extent **cached, 300 u64 *file_offset, u64 io_size, int uptodate) 301 { 302 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); 303 struct btrfs_ordered_inode_tree *tree; 304 struct rb_node *node; 305 struct btrfs_ordered_extent *entry = NULL; 306 int ret; 307 unsigned long flags; 308 u64 dec_end; 309 u64 dec_start; 310 u64 to_dec; 311 312 tree = &BTRFS_I(inode)->ordered_tree; 313 spin_lock_irqsave(&tree->lock, flags); 314 node = tree_search(tree, *file_offset); 315 if (!node) { 316 ret = 1; 317 goto out; 318 } 319 320 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 321 if (!offset_in_entry(entry, *file_offset)) { 322 ret = 1; 323 goto out; 324 } 325 326 dec_start = max(*file_offset, entry->file_offset); 327 dec_end = min(*file_offset + io_size, entry->file_offset + 328 entry->len); 329 *file_offset = dec_end; 330 if (dec_start > dec_end) { 331 btrfs_crit(fs_info, "bad ordering dec_start %llu end %llu", 332 dec_start, dec_end); 333 } 334 to_dec = dec_end - dec_start; 335 if (to_dec > entry->bytes_left) { 336 btrfs_crit(fs_info, 337 "bad ordered accounting left %llu size %llu", 338 entry->bytes_left, to_dec); 339 } 340 entry->bytes_left -= to_dec; 341 if (!uptodate) 342 set_bit(BTRFS_ORDERED_IOERR, &entry->flags); 343 344 if (entry->bytes_left == 0) { 345 ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags); 346 /* test_and_set_bit implies a barrier */ 347 cond_wake_up_nomb(&entry->wait); 348 } else { 349 ret = 1; 350 } 351 out: 352 if (!ret && cached && entry) { 353 *cached = entry; 354 refcount_inc(&entry->refs); 355 } 356 spin_unlock_irqrestore(&tree->lock, flags); 357 return ret == 0; 358 } 359 360 /* 361 * this is used to account for finished IO across a given range 362 * of the file. The IO should not span ordered extents. If 363 * a given ordered_extent is completely done, 1 is returned, otherwise 364 * 0. 365 * 366 * test_and_set_bit on a flag in the struct btrfs_ordered_extent is used 367 * to make sure this function only returns 1 once for a given ordered extent. 368 */ 369 int btrfs_dec_test_ordered_pending(struct inode *inode, 370 struct btrfs_ordered_extent **cached, 371 u64 file_offset, u64 io_size, int uptodate) 372 { 373 struct btrfs_ordered_inode_tree *tree; 374 struct rb_node *node; 375 struct btrfs_ordered_extent *entry = NULL; 376 unsigned long flags; 377 int ret; 378 379 tree = &BTRFS_I(inode)->ordered_tree; 380 spin_lock_irqsave(&tree->lock, flags); 381 if (cached && *cached) { 382 entry = *cached; 383 goto have_entry; 384 } 385 386 node = tree_search(tree, file_offset); 387 if (!node) { 388 ret = 1; 389 goto out; 390 } 391 392 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 393 have_entry: 394 if (!offset_in_entry(entry, file_offset)) { 395 ret = 1; 396 goto out; 397 } 398 399 if (io_size > entry->bytes_left) { 400 btrfs_crit(BTRFS_I(inode)->root->fs_info, 401 "bad ordered accounting left %llu size %llu", 402 entry->bytes_left, io_size); 403 } 404 entry->bytes_left -= io_size; 405 if (!uptodate) 406 set_bit(BTRFS_ORDERED_IOERR, &entry->flags); 407 408 if (entry->bytes_left == 0) { 409 ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags); 410 /* test_and_set_bit implies a barrier */ 411 cond_wake_up_nomb(&entry->wait); 412 } else { 413 ret = 1; 414 } 415 out: 416 if (!ret && cached && entry) { 417 *cached = entry; 418 refcount_inc(&entry->refs); 419 } 420 spin_unlock_irqrestore(&tree->lock, flags); 421 return ret == 0; 422 } 423 424 /* 425 * used to drop a reference on an ordered extent. This will free 426 * the extent if the last reference is dropped 427 */ 428 void btrfs_put_ordered_extent(struct btrfs_ordered_extent *entry) 429 { 430 struct list_head *cur; 431 struct btrfs_ordered_sum *sum; 432 433 trace_btrfs_ordered_extent_put(entry->inode, entry); 434 435 if (refcount_dec_and_test(&entry->refs)) { 436 ASSERT(list_empty(&entry->log_list)); 437 ASSERT(list_empty(&entry->trans_list)); 438 ASSERT(list_empty(&entry->root_extent_list)); 439 ASSERT(RB_EMPTY_NODE(&entry->rb_node)); 440 if (entry->inode) 441 btrfs_add_delayed_iput(entry->inode); 442 while (!list_empty(&entry->list)) { 443 cur = entry->list.next; 444 sum = list_entry(cur, struct btrfs_ordered_sum, list); 445 list_del(&sum->list); 446 kvfree(sum); 447 } 448 kmem_cache_free(btrfs_ordered_extent_cache, entry); 449 } 450 } 451 452 /* 453 * remove an ordered extent from the tree. No references are dropped 454 * and waiters are woken up. 455 */ 456 void btrfs_remove_ordered_extent(struct inode *inode, 457 struct btrfs_ordered_extent *entry) 458 { 459 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); 460 struct btrfs_ordered_inode_tree *tree; 461 struct btrfs_inode *btrfs_inode = BTRFS_I(inode); 462 struct btrfs_root *root = btrfs_inode->root; 463 struct rb_node *node; 464 465 /* This is paired with btrfs_add_ordered_extent. */ 466 spin_lock(&btrfs_inode->lock); 467 btrfs_mod_outstanding_extents(btrfs_inode, -1); 468 spin_unlock(&btrfs_inode->lock); 469 if (root != fs_info->tree_root) 470 btrfs_delalloc_release_metadata(btrfs_inode, entry->len, false); 471 472 tree = &btrfs_inode->ordered_tree; 473 spin_lock_irq(&tree->lock); 474 node = &entry->rb_node; 475 rb_erase(node, &tree->tree); 476 RB_CLEAR_NODE(node); 477 if (tree->last == node) 478 tree->last = NULL; 479 set_bit(BTRFS_ORDERED_COMPLETE, &entry->flags); 480 spin_unlock_irq(&tree->lock); 481 482 spin_lock(&root->ordered_extent_lock); 483 list_del_init(&entry->root_extent_list); 484 root->nr_ordered_extents--; 485 486 trace_btrfs_ordered_extent_remove(inode, entry); 487 488 if (!root->nr_ordered_extents) { 489 spin_lock(&fs_info->ordered_root_lock); 490 BUG_ON(list_empty(&root->ordered_root)); 491 list_del_init(&root->ordered_root); 492 spin_unlock(&fs_info->ordered_root_lock); 493 } 494 spin_unlock(&root->ordered_extent_lock); 495 wake_up(&entry->wait); 496 } 497 498 static void btrfs_run_ordered_extent_work(struct btrfs_work *work) 499 { 500 struct btrfs_ordered_extent *ordered; 501 502 ordered = container_of(work, struct btrfs_ordered_extent, flush_work); 503 btrfs_start_ordered_extent(ordered->inode, ordered, 1); 504 complete(&ordered->completion); 505 } 506 507 /* 508 * wait for all the ordered extents in a root. This is done when balancing 509 * space between drives. 510 */ 511 u64 btrfs_wait_ordered_extents(struct btrfs_root *root, u64 nr, 512 const u64 range_start, const u64 range_len) 513 { 514 struct btrfs_fs_info *fs_info = root->fs_info; 515 LIST_HEAD(splice); 516 LIST_HEAD(skipped); 517 LIST_HEAD(works); 518 struct btrfs_ordered_extent *ordered, *next; 519 u64 count = 0; 520 const u64 range_end = range_start + range_len; 521 522 mutex_lock(&root->ordered_extent_mutex); 523 spin_lock(&root->ordered_extent_lock); 524 list_splice_init(&root->ordered_extents, &splice); 525 while (!list_empty(&splice) && nr) { 526 ordered = list_first_entry(&splice, struct btrfs_ordered_extent, 527 root_extent_list); 528 529 if (range_end <= ordered->start || 530 ordered->start + ordered->disk_len <= range_start) { 531 list_move_tail(&ordered->root_extent_list, &skipped); 532 cond_resched_lock(&root->ordered_extent_lock); 533 continue; 534 } 535 536 list_move_tail(&ordered->root_extent_list, 537 &root->ordered_extents); 538 refcount_inc(&ordered->refs); 539 spin_unlock(&root->ordered_extent_lock); 540 541 btrfs_init_work(&ordered->flush_work, 542 btrfs_flush_delalloc_helper, 543 btrfs_run_ordered_extent_work, NULL, NULL); 544 list_add_tail(&ordered->work_list, &works); 545 btrfs_queue_work(fs_info->flush_workers, &ordered->flush_work); 546 547 cond_resched(); 548 spin_lock(&root->ordered_extent_lock); 549 if (nr != U64_MAX) 550 nr--; 551 count++; 552 } 553 list_splice_tail(&skipped, &root->ordered_extents); 554 list_splice_tail(&splice, &root->ordered_extents); 555 spin_unlock(&root->ordered_extent_lock); 556 557 list_for_each_entry_safe(ordered, next, &works, work_list) { 558 list_del_init(&ordered->work_list); 559 wait_for_completion(&ordered->completion); 560 btrfs_put_ordered_extent(ordered); 561 cond_resched(); 562 } 563 mutex_unlock(&root->ordered_extent_mutex); 564 565 return count; 566 } 567 568 u64 btrfs_wait_ordered_roots(struct btrfs_fs_info *fs_info, u64 nr, 569 const u64 range_start, const u64 range_len) 570 { 571 struct btrfs_root *root; 572 struct list_head splice; 573 u64 total_done = 0; 574 u64 done; 575 576 INIT_LIST_HEAD(&splice); 577 578 mutex_lock(&fs_info->ordered_operations_mutex); 579 spin_lock(&fs_info->ordered_root_lock); 580 list_splice_init(&fs_info->ordered_roots, &splice); 581 while (!list_empty(&splice) && nr) { 582 root = list_first_entry(&splice, struct btrfs_root, 583 ordered_root); 584 root = btrfs_grab_fs_root(root); 585 BUG_ON(!root); 586 list_move_tail(&root->ordered_root, 587 &fs_info->ordered_roots); 588 spin_unlock(&fs_info->ordered_root_lock); 589 590 done = btrfs_wait_ordered_extents(root, nr, 591 range_start, range_len); 592 btrfs_put_fs_root(root); 593 total_done += done; 594 595 spin_lock(&fs_info->ordered_root_lock); 596 if (nr != U64_MAX) { 597 nr -= done; 598 } 599 } 600 list_splice_tail(&splice, &fs_info->ordered_roots); 601 spin_unlock(&fs_info->ordered_root_lock); 602 mutex_unlock(&fs_info->ordered_operations_mutex); 603 604 return total_done; 605 } 606 607 /* 608 * Used to start IO or wait for a given ordered extent to finish. 609 * 610 * If wait is one, this effectively waits on page writeback for all the pages 611 * in the extent, and it waits on the io completion code to insert 612 * metadata into the btree corresponding to the extent 613 */ 614 void btrfs_start_ordered_extent(struct inode *inode, 615 struct btrfs_ordered_extent *entry, 616 int wait) 617 { 618 u64 start = entry->file_offset; 619 u64 end = start + entry->len - 1; 620 621 trace_btrfs_ordered_extent_start(inode, entry); 622 623 /* 624 * pages in the range can be dirty, clean or writeback. We 625 * start IO on any dirty ones so the wait doesn't stall waiting 626 * for the flusher thread to find them 627 */ 628 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) 629 filemap_fdatawrite_range(inode->i_mapping, start, end); 630 if (wait) { 631 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, 632 &entry->flags)); 633 } 634 } 635 636 /* 637 * Used to wait on ordered extents across a large range of bytes. 638 */ 639 int btrfs_wait_ordered_range(struct inode *inode, u64 start, u64 len) 640 { 641 int ret = 0; 642 int ret_wb = 0; 643 u64 end; 644 u64 orig_end; 645 struct btrfs_ordered_extent *ordered; 646 647 if (start + len < start) { 648 orig_end = INT_LIMIT(loff_t); 649 } else { 650 orig_end = start + len - 1; 651 if (orig_end > INT_LIMIT(loff_t)) 652 orig_end = INT_LIMIT(loff_t); 653 } 654 655 /* start IO across the range first to instantiate any delalloc 656 * extents 657 */ 658 ret = btrfs_fdatawrite_range(inode, start, orig_end); 659 if (ret) 660 return ret; 661 662 /* 663 * If we have a writeback error don't return immediately. Wait first 664 * for any ordered extents that haven't completed yet. This is to make 665 * sure no one can dirty the same page ranges and call writepages() 666 * before the ordered extents complete - to avoid failures (-EEXIST) 667 * when adding the new ordered extents to the ordered tree. 668 */ 669 ret_wb = filemap_fdatawait_range(inode->i_mapping, start, orig_end); 670 671 end = orig_end; 672 while (1) { 673 ordered = btrfs_lookup_first_ordered_extent(inode, end); 674 if (!ordered) 675 break; 676 if (ordered->file_offset > orig_end) { 677 btrfs_put_ordered_extent(ordered); 678 break; 679 } 680 if (ordered->file_offset + ordered->len <= start) { 681 btrfs_put_ordered_extent(ordered); 682 break; 683 } 684 btrfs_start_ordered_extent(inode, ordered, 1); 685 end = ordered->file_offset; 686 if (test_bit(BTRFS_ORDERED_IOERR, &ordered->flags)) 687 ret = -EIO; 688 btrfs_put_ordered_extent(ordered); 689 if (ret || end == 0 || end == start) 690 break; 691 end--; 692 } 693 return ret_wb ? ret_wb : ret; 694 } 695 696 /* 697 * find an ordered extent corresponding to file_offset. return NULL if 698 * nothing is found, otherwise take a reference on the extent and return it 699 */ 700 struct btrfs_ordered_extent *btrfs_lookup_ordered_extent(struct inode *inode, 701 u64 file_offset) 702 { 703 struct btrfs_ordered_inode_tree *tree; 704 struct rb_node *node; 705 struct btrfs_ordered_extent *entry = NULL; 706 707 tree = &BTRFS_I(inode)->ordered_tree; 708 spin_lock_irq(&tree->lock); 709 node = tree_search(tree, file_offset); 710 if (!node) 711 goto out; 712 713 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 714 if (!offset_in_entry(entry, file_offset)) 715 entry = NULL; 716 if (entry) 717 refcount_inc(&entry->refs); 718 out: 719 spin_unlock_irq(&tree->lock); 720 return entry; 721 } 722 723 /* Since the DIO code tries to lock a wide area we need to look for any ordered 724 * extents that exist in the range, rather than just the start of the range. 725 */ 726 struct btrfs_ordered_extent *btrfs_lookup_ordered_range( 727 struct btrfs_inode *inode, u64 file_offset, u64 len) 728 { 729 struct btrfs_ordered_inode_tree *tree; 730 struct rb_node *node; 731 struct btrfs_ordered_extent *entry = NULL; 732 733 tree = &inode->ordered_tree; 734 spin_lock_irq(&tree->lock); 735 node = tree_search(tree, file_offset); 736 if (!node) { 737 node = tree_search(tree, file_offset + len); 738 if (!node) 739 goto out; 740 } 741 742 while (1) { 743 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 744 if (range_overlaps(entry, file_offset, len)) 745 break; 746 747 if (entry->file_offset >= file_offset + len) { 748 entry = NULL; 749 break; 750 } 751 entry = NULL; 752 node = rb_next(node); 753 if (!node) 754 break; 755 } 756 out: 757 if (entry) 758 refcount_inc(&entry->refs); 759 spin_unlock_irq(&tree->lock); 760 return entry; 761 } 762 763 /* 764 * lookup and return any extent before 'file_offset'. NULL is returned 765 * if none is found 766 */ 767 struct btrfs_ordered_extent * 768 btrfs_lookup_first_ordered_extent(struct inode *inode, u64 file_offset) 769 { 770 struct btrfs_ordered_inode_tree *tree; 771 struct rb_node *node; 772 struct btrfs_ordered_extent *entry = NULL; 773 774 tree = &BTRFS_I(inode)->ordered_tree; 775 spin_lock_irq(&tree->lock); 776 node = tree_search(tree, file_offset); 777 if (!node) 778 goto out; 779 780 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 781 refcount_inc(&entry->refs); 782 out: 783 spin_unlock_irq(&tree->lock); 784 return entry; 785 } 786 787 /* 788 * After an extent is done, call this to conditionally update the on disk 789 * i_size. i_size is updated to cover any fully written part of the file. 790 */ 791 int btrfs_ordered_update_i_size(struct inode *inode, u64 offset, 792 struct btrfs_ordered_extent *ordered) 793 { 794 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; 795 u64 disk_i_size; 796 u64 new_i_size; 797 u64 i_size = i_size_read(inode); 798 struct rb_node *node; 799 struct rb_node *prev = NULL; 800 struct btrfs_ordered_extent *test; 801 int ret = 1; 802 u64 orig_offset = offset; 803 804 spin_lock_irq(&tree->lock); 805 if (ordered) { 806 offset = entry_end(ordered); 807 if (test_bit(BTRFS_ORDERED_TRUNCATED, &ordered->flags)) 808 offset = min(offset, 809 ordered->file_offset + 810 ordered->truncated_len); 811 } else { 812 offset = ALIGN(offset, btrfs_inode_sectorsize(inode)); 813 } 814 disk_i_size = BTRFS_I(inode)->disk_i_size; 815 816 /* 817 * truncate file. 818 * If ordered is not NULL, then this is called from endio and 819 * disk_i_size will be updated by either truncate itself or any 820 * in-flight IOs which are inside the disk_i_size. 821 * 822 * Because btrfs_setsize() may set i_size with disk_i_size if truncate 823 * fails somehow, we need to make sure we have a precise disk_i_size by 824 * updating it as usual. 825 * 826 */ 827 if (!ordered && disk_i_size > i_size) { 828 BTRFS_I(inode)->disk_i_size = orig_offset; 829 ret = 0; 830 goto out; 831 } 832 833 /* 834 * if the disk i_size is already at the inode->i_size, or 835 * this ordered extent is inside the disk i_size, we're done 836 */ 837 if (disk_i_size == i_size) 838 goto out; 839 840 /* 841 * We still need to update disk_i_size if outstanding_isize is greater 842 * than disk_i_size. 843 */ 844 if (offset <= disk_i_size && 845 (!ordered || ordered->outstanding_isize <= disk_i_size)) 846 goto out; 847 848 /* 849 * walk backward from this ordered extent to disk_i_size. 850 * if we find an ordered extent then we can't update disk i_size 851 * yet 852 */ 853 if (ordered) { 854 node = rb_prev(&ordered->rb_node); 855 } else { 856 prev = tree_search(tree, offset); 857 /* 858 * we insert file extents without involving ordered struct, 859 * so there should be no ordered struct cover this offset 860 */ 861 if (prev) { 862 test = rb_entry(prev, struct btrfs_ordered_extent, 863 rb_node); 864 BUG_ON(offset_in_entry(test, offset)); 865 } 866 node = prev; 867 } 868 for (; node; node = rb_prev(node)) { 869 test = rb_entry(node, struct btrfs_ordered_extent, rb_node); 870 871 /* We treat this entry as if it doesn't exist */ 872 if (test_bit(BTRFS_ORDERED_UPDATED_ISIZE, &test->flags)) 873 continue; 874 875 if (entry_end(test) <= disk_i_size) 876 break; 877 if (test->file_offset >= i_size) 878 break; 879 880 /* 881 * We don't update disk_i_size now, so record this undealt 882 * i_size. Or we will not know the real i_size. 883 */ 884 if (test->outstanding_isize < offset) 885 test->outstanding_isize = offset; 886 if (ordered && 887 ordered->outstanding_isize > test->outstanding_isize) 888 test->outstanding_isize = ordered->outstanding_isize; 889 goto out; 890 } 891 new_i_size = min_t(u64, offset, i_size); 892 893 /* 894 * Some ordered extents may completed before the current one, and 895 * we hold the real i_size in ->outstanding_isize. 896 */ 897 if (ordered && ordered->outstanding_isize > new_i_size) 898 new_i_size = min_t(u64, ordered->outstanding_isize, i_size); 899 BTRFS_I(inode)->disk_i_size = new_i_size; 900 ret = 0; 901 out: 902 /* 903 * We need to do this because we can't remove ordered extents until 904 * after the i_disk_size has been updated and then the inode has been 905 * updated to reflect the change, so we need to tell anybody who finds 906 * this ordered extent that we've already done all the real work, we 907 * just haven't completed all the other work. 908 */ 909 if (ordered) 910 set_bit(BTRFS_ORDERED_UPDATED_ISIZE, &ordered->flags); 911 spin_unlock_irq(&tree->lock); 912 return ret; 913 } 914 915 /* 916 * search the ordered extents for one corresponding to 'offset' and 917 * try to find a checksum. This is used because we allow pages to 918 * be reclaimed before their checksum is actually put into the btree 919 */ 920 int btrfs_find_ordered_sum(struct inode *inode, u64 offset, u64 disk_bytenr, 921 u32 *sum, int len) 922 { 923 struct btrfs_ordered_sum *ordered_sum; 924 struct btrfs_ordered_extent *ordered; 925 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; 926 unsigned long num_sectors; 927 unsigned long i; 928 u32 sectorsize = btrfs_inode_sectorsize(inode); 929 int index = 0; 930 931 ordered = btrfs_lookup_ordered_extent(inode, offset); 932 if (!ordered) 933 return 0; 934 935 spin_lock_irq(&tree->lock); 936 list_for_each_entry_reverse(ordered_sum, &ordered->list, list) { 937 if (disk_bytenr >= ordered_sum->bytenr && 938 disk_bytenr < ordered_sum->bytenr + ordered_sum->len) { 939 i = (disk_bytenr - ordered_sum->bytenr) >> 940 inode->i_sb->s_blocksize_bits; 941 num_sectors = ordered_sum->len >> 942 inode->i_sb->s_blocksize_bits; 943 num_sectors = min_t(int, len - index, num_sectors - i); 944 memcpy(sum + index, ordered_sum->sums + i, 945 num_sectors); 946 947 index += (int)num_sectors; 948 if (index == len) 949 goto out; 950 disk_bytenr += num_sectors * sectorsize; 951 } 952 } 953 out: 954 spin_unlock_irq(&tree->lock); 955 btrfs_put_ordered_extent(ordered); 956 return index; 957 } 958 959 int __init ordered_data_init(void) 960 { 961 btrfs_ordered_extent_cache = kmem_cache_create("btrfs_ordered_extent", 962 sizeof(struct btrfs_ordered_extent), 0, 963 SLAB_MEM_SPREAD, 964 NULL); 965 if (!btrfs_ordered_extent_cache) 966 return -ENOMEM; 967 968 return 0; 969 } 970 971 void __cold ordered_data_exit(void) 972 { 973 kmem_cache_destroy(btrfs_ordered_extent_cache); 974 } 975