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