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, "Inconsistency in ordered tree at offset " 71 "%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_root *root = BTRFS_I(inode)->root; 190 struct btrfs_ordered_inode_tree *tree; 191 struct rb_node *node; 192 struct btrfs_ordered_extent *entry; 193 194 tree = &BTRFS_I(inode)->ordered_tree; 195 entry = kmem_cache_zalloc(btrfs_ordered_extent_cache, GFP_NOFS); 196 if (!entry) 197 return -ENOMEM; 198 199 entry->file_offset = file_offset; 200 entry->start = start; 201 entry->len = len; 202 entry->disk_len = disk_len; 203 entry->bytes_left = len; 204 entry->inode = igrab(inode); 205 entry->compress_type = compress_type; 206 entry->truncated_len = (u64)-1; 207 if (type != BTRFS_ORDERED_IO_DONE && type != BTRFS_ORDERED_COMPLETE) 208 set_bit(type, &entry->flags); 209 210 if (dio) 211 set_bit(BTRFS_ORDERED_DIRECT, &entry->flags); 212 213 /* one ref for the tree */ 214 atomic_set(&entry->refs, 1); 215 init_waitqueue_head(&entry->wait); 216 INIT_LIST_HEAD(&entry->list); 217 INIT_LIST_HEAD(&entry->root_extent_list); 218 INIT_LIST_HEAD(&entry->work_list); 219 init_completion(&entry->completion); 220 INIT_LIST_HEAD(&entry->log_list); 221 INIT_LIST_HEAD(&entry->trans_list); 222 223 trace_btrfs_ordered_extent_add(inode, entry); 224 225 spin_lock_irq(&tree->lock); 226 node = tree_insert(&tree->tree, file_offset, 227 &entry->rb_node); 228 if (node) 229 ordered_data_tree_panic(inode, -EEXIST, file_offset); 230 spin_unlock_irq(&tree->lock); 231 232 spin_lock(&root->ordered_extent_lock); 233 list_add_tail(&entry->root_extent_list, 234 &root->ordered_extents); 235 root->nr_ordered_extents++; 236 if (root->nr_ordered_extents == 1) { 237 spin_lock(&root->fs_info->ordered_root_lock); 238 BUG_ON(!list_empty(&root->ordered_root)); 239 list_add_tail(&root->ordered_root, 240 &root->fs_info->ordered_roots); 241 spin_unlock(&root->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_ordered_inode_tree *tree; 307 struct rb_node *node; 308 struct btrfs_ordered_extent *entry = NULL; 309 int ret; 310 unsigned long flags; 311 u64 dec_end; 312 u64 dec_start; 313 u64 to_dec; 314 315 tree = &BTRFS_I(inode)->ordered_tree; 316 spin_lock_irqsave(&tree->lock, flags); 317 node = tree_search(tree, *file_offset); 318 if (!node) { 319 ret = 1; 320 goto out; 321 } 322 323 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 324 if (!offset_in_entry(entry, *file_offset)) { 325 ret = 1; 326 goto out; 327 } 328 329 dec_start = max(*file_offset, entry->file_offset); 330 dec_end = min(*file_offset + io_size, entry->file_offset + 331 entry->len); 332 *file_offset = dec_end; 333 if (dec_start > dec_end) { 334 btrfs_crit(BTRFS_I(inode)->root->fs_info, 335 "bad ordering dec_start %llu end %llu", dec_start, dec_end); 336 } 337 to_dec = dec_end - dec_start; 338 if (to_dec > entry->bytes_left) { 339 btrfs_crit(BTRFS_I(inode)->root->fs_info, 340 "bad ordered accounting left %llu size %llu", 341 entry->bytes_left, to_dec); 342 } 343 entry->bytes_left -= to_dec; 344 if (!uptodate) 345 set_bit(BTRFS_ORDERED_IOERR, &entry->flags); 346 347 if (entry->bytes_left == 0) { 348 ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags); 349 /* 350 * Implicit memory barrier after test_and_set_bit 351 */ 352 if (waitqueue_active(&entry->wait)) 353 wake_up(&entry->wait); 354 } else { 355 ret = 1; 356 } 357 out: 358 if (!ret && cached && entry) { 359 *cached = entry; 360 atomic_inc(&entry->refs); 361 } 362 spin_unlock_irqrestore(&tree->lock, flags); 363 return ret == 0; 364 } 365 366 /* 367 * this is used to account for finished IO across a given range 368 * of the file. The IO should not span ordered extents. If 369 * a given ordered_extent is completely done, 1 is returned, otherwise 370 * 0. 371 * 372 * test_and_set_bit on a flag in the struct btrfs_ordered_extent is used 373 * to make sure this function only returns 1 once for a given ordered extent. 374 */ 375 int btrfs_dec_test_ordered_pending(struct inode *inode, 376 struct btrfs_ordered_extent **cached, 377 u64 file_offset, u64 io_size, int uptodate) 378 { 379 struct btrfs_ordered_inode_tree *tree; 380 struct rb_node *node; 381 struct btrfs_ordered_extent *entry = NULL; 382 unsigned long flags; 383 int ret; 384 385 tree = &BTRFS_I(inode)->ordered_tree; 386 spin_lock_irqsave(&tree->lock, flags); 387 if (cached && *cached) { 388 entry = *cached; 389 goto have_entry; 390 } 391 392 node = tree_search(tree, file_offset); 393 if (!node) { 394 ret = 1; 395 goto out; 396 } 397 398 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 399 have_entry: 400 if (!offset_in_entry(entry, file_offset)) { 401 ret = 1; 402 goto out; 403 } 404 405 if (io_size > entry->bytes_left) { 406 btrfs_crit(BTRFS_I(inode)->root->fs_info, 407 "bad ordered accounting left %llu size %llu", 408 entry->bytes_left, io_size); 409 } 410 entry->bytes_left -= io_size; 411 if (!uptodate) 412 set_bit(BTRFS_ORDERED_IOERR, &entry->flags); 413 414 if (entry->bytes_left == 0) { 415 ret = test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags); 416 /* 417 * Implicit memory barrier after test_and_set_bit 418 */ 419 if (waitqueue_active(&entry->wait)) 420 wake_up(&entry->wait); 421 } else { 422 ret = 1; 423 } 424 out: 425 if (!ret && cached && entry) { 426 *cached = entry; 427 atomic_inc(&entry->refs); 428 } 429 spin_unlock_irqrestore(&tree->lock, flags); 430 return ret == 0; 431 } 432 433 /* Needs to either be called under a log transaction or the log_mutex */ 434 void btrfs_get_logged_extents(struct inode *inode, 435 struct list_head *logged_list, 436 const loff_t start, 437 const loff_t end) 438 { 439 struct btrfs_ordered_inode_tree *tree; 440 struct btrfs_ordered_extent *ordered; 441 struct rb_node *n; 442 struct rb_node *prev; 443 444 tree = &BTRFS_I(inode)->ordered_tree; 445 spin_lock_irq(&tree->lock); 446 n = __tree_search(&tree->tree, end, &prev); 447 if (!n) 448 n = prev; 449 for (; n; n = rb_prev(n)) { 450 ordered = rb_entry(n, struct btrfs_ordered_extent, rb_node); 451 if (ordered->file_offset > end) 452 continue; 453 if (entry_end(ordered) <= start) 454 break; 455 if (test_and_set_bit(BTRFS_ORDERED_LOGGED, &ordered->flags)) 456 continue; 457 list_add(&ordered->log_list, logged_list); 458 atomic_inc(&ordered->refs); 459 } 460 spin_unlock_irq(&tree->lock); 461 } 462 463 void btrfs_put_logged_extents(struct list_head *logged_list) 464 { 465 struct btrfs_ordered_extent *ordered; 466 467 while (!list_empty(logged_list)) { 468 ordered = list_first_entry(logged_list, 469 struct btrfs_ordered_extent, 470 log_list); 471 list_del_init(&ordered->log_list); 472 btrfs_put_ordered_extent(ordered); 473 } 474 } 475 476 void btrfs_submit_logged_extents(struct list_head *logged_list, 477 struct btrfs_root *log) 478 { 479 int index = log->log_transid % 2; 480 481 spin_lock_irq(&log->log_extents_lock[index]); 482 list_splice_tail(logged_list, &log->logged_list[index]); 483 spin_unlock_irq(&log->log_extents_lock[index]); 484 } 485 486 void btrfs_wait_logged_extents(struct btrfs_trans_handle *trans, 487 struct btrfs_root *log, u64 transid) 488 { 489 struct btrfs_ordered_extent *ordered; 490 int index = transid % 2; 491 492 spin_lock_irq(&log->log_extents_lock[index]); 493 while (!list_empty(&log->logged_list[index])) { 494 struct inode *inode; 495 ordered = list_first_entry(&log->logged_list[index], 496 struct btrfs_ordered_extent, 497 log_list); 498 list_del_init(&ordered->log_list); 499 inode = ordered->inode; 500 spin_unlock_irq(&log->log_extents_lock[index]); 501 502 if (!test_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags) && 503 !test_bit(BTRFS_ORDERED_DIRECT, &ordered->flags)) { 504 u64 start = ordered->file_offset; 505 u64 end = ordered->file_offset + ordered->len - 1; 506 507 WARN_ON(!inode); 508 filemap_fdatawrite_range(inode->i_mapping, start, end); 509 } 510 wait_event(ordered->wait, test_bit(BTRFS_ORDERED_IO_DONE, 511 &ordered->flags)); 512 513 /* 514 * In order to keep us from losing our ordered extent 515 * information when committing the transaction we have to make 516 * sure that any logged extents are completed when we go to 517 * commit the transaction. To do this we simply increase the 518 * current transactions pending_ordered counter and decrement it 519 * when the ordered extent completes. 520 */ 521 if (!test_bit(BTRFS_ORDERED_COMPLETE, &ordered->flags)) { 522 struct btrfs_ordered_inode_tree *tree; 523 524 tree = &BTRFS_I(inode)->ordered_tree; 525 spin_lock_irq(&tree->lock); 526 if (!test_bit(BTRFS_ORDERED_COMPLETE, &ordered->flags)) { 527 set_bit(BTRFS_ORDERED_PENDING, &ordered->flags); 528 atomic_inc(&trans->transaction->pending_ordered); 529 } 530 spin_unlock_irq(&tree->lock); 531 } 532 btrfs_put_ordered_extent(ordered); 533 spin_lock_irq(&log->log_extents_lock[index]); 534 } 535 spin_unlock_irq(&log->log_extents_lock[index]); 536 } 537 538 void btrfs_free_logged_extents(struct btrfs_root *log, u64 transid) 539 { 540 struct btrfs_ordered_extent *ordered; 541 int index = transid % 2; 542 543 spin_lock_irq(&log->log_extents_lock[index]); 544 while (!list_empty(&log->logged_list[index])) { 545 ordered = list_first_entry(&log->logged_list[index], 546 struct btrfs_ordered_extent, 547 log_list); 548 list_del_init(&ordered->log_list); 549 spin_unlock_irq(&log->log_extents_lock[index]); 550 btrfs_put_ordered_extent(ordered); 551 spin_lock_irq(&log->log_extents_lock[index]); 552 } 553 spin_unlock_irq(&log->log_extents_lock[index]); 554 } 555 556 /* 557 * used to drop a reference on an ordered extent. This will free 558 * the extent if the last reference is dropped 559 */ 560 void btrfs_put_ordered_extent(struct btrfs_ordered_extent *entry) 561 { 562 struct list_head *cur; 563 struct btrfs_ordered_sum *sum; 564 565 trace_btrfs_ordered_extent_put(entry->inode, entry); 566 567 if (atomic_dec_and_test(&entry->refs)) { 568 ASSERT(list_empty(&entry->log_list)); 569 ASSERT(list_empty(&entry->trans_list)); 570 ASSERT(list_empty(&entry->root_extent_list)); 571 ASSERT(RB_EMPTY_NODE(&entry->rb_node)); 572 if (entry->inode) 573 btrfs_add_delayed_iput(entry->inode); 574 while (!list_empty(&entry->list)) { 575 cur = entry->list.next; 576 sum = list_entry(cur, struct btrfs_ordered_sum, list); 577 list_del(&sum->list); 578 kfree(sum); 579 } 580 kmem_cache_free(btrfs_ordered_extent_cache, entry); 581 } 582 } 583 584 /* 585 * remove an ordered extent from the tree. No references are dropped 586 * and waiters are woken up. 587 */ 588 void btrfs_remove_ordered_extent(struct inode *inode, 589 struct btrfs_ordered_extent *entry) 590 { 591 struct btrfs_ordered_inode_tree *tree; 592 struct btrfs_root *root = BTRFS_I(inode)->root; 593 struct rb_node *node; 594 bool dec_pending_ordered = false; 595 596 tree = &BTRFS_I(inode)->ordered_tree; 597 spin_lock_irq(&tree->lock); 598 node = &entry->rb_node; 599 rb_erase(node, &tree->tree); 600 RB_CLEAR_NODE(node); 601 if (tree->last == node) 602 tree->last = NULL; 603 set_bit(BTRFS_ORDERED_COMPLETE, &entry->flags); 604 if (test_and_clear_bit(BTRFS_ORDERED_PENDING, &entry->flags)) 605 dec_pending_ordered = true; 606 spin_unlock_irq(&tree->lock); 607 608 /* 609 * The current running transaction is waiting on us, we need to let it 610 * know that we're complete and wake it up. 611 */ 612 if (dec_pending_ordered) { 613 struct btrfs_transaction *trans; 614 615 /* 616 * The checks for trans are just a formality, it should be set, 617 * but if it isn't we don't want to deref/assert under the spin 618 * lock, so be nice and check if trans is set, but ASSERT() so 619 * if it isn't set a developer will notice. 620 */ 621 spin_lock(&root->fs_info->trans_lock); 622 trans = root->fs_info->running_transaction; 623 if (trans) 624 atomic_inc(&trans->use_count); 625 spin_unlock(&root->fs_info->trans_lock); 626 627 ASSERT(trans); 628 if (trans) { 629 if (atomic_dec_and_test(&trans->pending_ordered)) 630 wake_up(&trans->pending_wait); 631 btrfs_put_transaction(trans); 632 } 633 } 634 635 spin_lock(&root->ordered_extent_lock); 636 list_del_init(&entry->root_extent_list); 637 root->nr_ordered_extents--; 638 639 trace_btrfs_ordered_extent_remove(inode, entry); 640 641 if (!root->nr_ordered_extents) { 642 spin_lock(&root->fs_info->ordered_root_lock); 643 BUG_ON(list_empty(&root->ordered_root)); 644 list_del_init(&root->ordered_root); 645 spin_unlock(&root->fs_info->ordered_root_lock); 646 } 647 spin_unlock(&root->ordered_extent_lock); 648 wake_up(&entry->wait); 649 } 650 651 static void btrfs_run_ordered_extent_work(struct btrfs_work *work) 652 { 653 struct btrfs_ordered_extent *ordered; 654 655 ordered = container_of(work, struct btrfs_ordered_extent, flush_work); 656 btrfs_start_ordered_extent(ordered->inode, ordered, 1); 657 complete(&ordered->completion); 658 } 659 660 /* 661 * wait for all the ordered extents in a root. This is done when balancing 662 * space between drives. 663 */ 664 int btrfs_wait_ordered_extents(struct btrfs_root *root, int nr) 665 { 666 struct list_head splice, works; 667 struct btrfs_ordered_extent *ordered, *next; 668 int count = 0; 669 670 INIT_LIST_HEAD(&splice); 671 INIT_LIST_HEAD(&works); 672 673 mutex_lock(&root->ordered_extent_mutex); 674 spin_lock(&root->ordered_extent_lock); 675 list_splice_init(&root->ordered_extents, &splice); 676 while (!list_empty(&splice) && nr) { 677 ordered = list_first_entry(&splice, struct btrfs_ordered_extent, 678 root_extent_list); 679 list_move_tail(&ordered->root_extent_list, 680 &root->ordered_extents); 681 atomic_inc(&ordered->refs); 682 spin_unlock(&root->ordered_extent_lock); 683 684 btrfs_init_work(&ordered->flush_work, 685 btrfs_flush_delalloc_helper, 686 btrfs_run_ordered_extent_work, NULL, NULL); 687 list_add_tail(&ordered->work_list, &works); 688 btrfs_queue_work(root->fs_info->flush_workers, 689 &ordered->flush_work); 690 691 cond_resched(); 692 spin_lock(&root->ordered_extent_lock); 693 if (nr != -1) 694 nr--; 695 count++; 696 } 697 list_splice_tail(&splice, &root->ordered_extents); 698 spin_unlock(&root->ordered_extent_lock); 699 700 list_for_each_entry_safe(ordered, next, &works, work_list) { 701 list_del_init(&ordered->work_list); 702 wait_for_completion(&ordered->completion); 703 btrfs_put_ordered_extent(ordered); 704 cond_resched(); 705 } 706 mutex_unlock(&root->ordered_extent_mutex); 707 708 return count; 709 } 710 711 void btrfs_wait_ordered_roots(struct btrfs_fs_info *fs_info, int nr) 712 { 713 struct btrfs_root *root; 714 struct list_head splice; 715 int done; 716 717 INIT_LIST_HEAD(&splice); 718 719 mutex_lock(&fs_info->ordered_operations_mutex); 720 spin_lock(&fs_info->ordered_root_lock); 721 list_splice_init(&fs_info->ordered_roots, &splice); 722 while (!list_empty(&splice) && nr) { 723 root = list_first_entry(&splice, struct btrfs_root, 724 ordered_root); 725 root = btrfs_grab_fs_root(root); 726 BUG_ON(!root); 727 list_move_tail(&root->ordered_root, 728 &fs_info->ordered_roots); 729 spin_unlock(&fs_info->ordered_root_lock); 730 731 done = btrfs_wait_ordered_extents(root, nr); 732 btrfs_put_fs_root(root); 733 734 spin_lock(&fs_info->ordered_root_lock); 735 if (nr != -1) { 736 nr -= done; 737 WARN_ON(nr < 0); 738 } 739 } 740 list_splice_tail(&splice, &fs_info->ordered_roots); 741 spin_unlock(&fs_info->ordered_root_lock); 742 mutex_unlock(&fs_info->ordered_operations_mutex); 743 } 744 745 /* 746 * Used to start IO or wait for a given ordered extent to finish. 747 * 748 * If wait is one, this effectively waits on page writeback for all the pages 749 * in the extent, and it waits on the io completion code to insert 750 * metadata into the btree corresponding to the extent 751 */ 752 void btrfs_start_ordered_extent(struct inode *inode, 753 struct btrfs_ordered_extent *entry, 754 int wait) 755 { 756 u64 start = entry->file_offset; 757 u64 end = start + entry->len - 1; 758 759 trace_btrfs_ordered_extent_start(inode, entry); 760 761 /* 762 * pages in the range can be dirty, clean or writeback. We 763 * start IO on any dirty ones so the wait doesn't stall waiting 764 * for the flusher thread to find them 765 */ 766 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) 767 filemap_fdatawrite_range(inode->i_mapping, start, end); 768 if (wait) { 769 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, 770 &entry->flags)); 771 } 772 } 773 774 /* 775 * Used to wait on ordered extents across a large range of bytes. 776 */ 777 int btrfs_wait_ordered_range(struct inode *inode, u64 start, u64 len) 778 { 779 int ret = 0; 780 int ret_wb = 0; 781 u64 end; 782 u64 orig_end; 783 struct btrfs_ordered_extent *ordered; 784 785 if (start + len < start) { 786 orig_end = INT_LIMIT(loff_t); 787 } else { 788 orig_end = start + len - 1; 789 if (orig_end > INT_LIMIT(loff_t)) 790 orig_end = INT_LIMIT(loff_t); 791 } 792 793 /* start IO across the range first to instantiate any delalloc 794 * extents 795 */ 796 ret = btrfs_fdatawrite_range(inode, start, orig_end); 797 if (ret) 798 return ret; 799 800 /* 801 * If we have a writeback error don't return immediately. Wait first 802 * for any ordered extents that haven't completed yet. This is to make 803 * sure no one can dirty the same page ranges and call writepages() 804 * before the ordered extents complete - to avoid failures (-EEXIST) 805 * when adding the new ordered extents to the ordered tree. 806 */ 807 ret_wb = filemap_fdatawait_range(inode->i_mapping, start, orig_end); 808 809 end = orig_end; 810 while (1) { 811 ordered = btrfs_lookup_first_ordered_extent(inode, end); 812 if (!ordered) 813 break; 814 if (ordered->file_offset > orig_end) { 815 btrfs_put_ordered_extent(ordered); 816 break; 817 } 818 if (ordered->file_offset + ordered->len <= start) { 819 btrfs_put_ordered_extent(ordered); 820 break; 821 } 822 btrfs_start_ordered_extent(inode, ordered, 1); 823 end = ordered->file_offset; 824 if (test_bit(BTRFS_ORDERED_IOERR, &ordered->flags)) 825 ret = -EIO; 826 btrfs_put_ordered_extent(ordered); 827 if (ret || end == 0 || end == start) 828 break; 829 end--; 830 } 831 return ret_wb ? ret_wb : ret; 832 } 833 834 /* 835 * find an ordered extent corresponding to file_offset. return NULL if 836 * nothing is found, otherwise take a reference on the extent and return it 837 */ 838 struct btrfs_ordered_extent *btrfs_lookup_ordered_extent(struct inode *inode, 839 u64 file_offset) 840 { 841 struct btrfs_ordered_inode_tree *tree; 842 struct rb_node *node; 843 struct btrfs_ordered_extent *entry = NULL; 844 845 tree = &BTRFS_I(inode)->ordered_tree; 846 spin_lock_irq(&tree->lock); 847 node = tree_search(tree, file_offset); 848 if (!node) 849 goto out; 850 851 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 852 if (!offset_in_entry(entry, file_offset)) 853 entry = NULL; 854 if (entry) 855 atomic_inc(&entry->refs); 856 out: 857 spin_unlock_irq(&tree->lock); 858 return entry; 859 } 860 861 /* Since the DIO code tries to lock a wide area we need to look for any ordered 862 * extents that exist in the range, rather than just the start of the range. 863 */ 864 struct btrfs_ordered_extent *btrfs_lookup_ordered_range(struct inode *inode, 865 u64 file_offset, 866 u64 len) 867 { 868 struct btrfs_ordered_inode_tree *tree; 869 struct rb_node *node; 870 struct btrfs_ordered_extent *entry = NULL; 871 872 tree = &BTRFS_I(inode)->ordered_tree; 873 spin_lock_irq(&tree->lock); 874 node = tree_search(tree, file_offset); 875 if (!node) { 876 node = tree_search(tree, file_offset + len); 877 if (!node) 878 goto out; 879 } 880 881 while (1) { 882 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 883 if (range_overlaps(entry, file_offset, len)) 884 break; 885 886 if (entry->file_offset >= file_offset + len) { 887 entry = NULL; 888 break; 889 } 890 entry = NULL; 891 node = rb_next(node); 892 if (!node) 893 break; 894 } 895 out: 896 if (entry) 897 atomic_inc(&entry->refs); 898 spin_unlock_irq(&tree->lock); 899 return entry; 900 } 901 902 bool btrfs_have_ordered_extents_in_range(struct inode *inode, 903 u64 file_offset, 904 u64 len) 905 { 906 struct btrfs_ordered_extent *oe; 907 908 oe = btrfs_lookup_ordered_range(inode, file_offset, len); 909 if (oe) { 910 btrfs_put_ordered_extent(oe); 911 return true; 912 } 913 return false; 914 } 915 916 /* 917 * lookup and return any extent before 'file_offset'. NULL is returned 918 * if none is found 919 */ 920 struct btrfs_ordered_extent * 921 btrfs_lookup_first_ordered_extent(struct inode *inode, u64 file_offset) 922 { 923 struct btrfs_ordered_inode_tree *tree; 924 struct rb_node *node; 925 struct btrfs_ordered_extent *entry = NULL; 926 927 tree = &BTRFS_I(inode)->ordered_tree; 928 spin_lock_irq(&tree->lock); 929 node = tree_search(tree, file_offset); 930 if (!node) 931 goto out; 932 933 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node); 934 atomic_inc(&entry->refs); 935 out: 936 spin_unlock_irq(&tree->lock); 937 return entry; 938 } 939 940 /* 941 * After an extent is done, call this to conditionally update the on disk 942 * i_size. i_size is updated to cover any fully written part of the file. 943 */ 944 int btrfs_ordered_update_i_size(struct inode *inode, u64 offset, 945 struct btrfs_ordered_extent *ordered) 946 { 947 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; 948 u64 disk_i_size; 949 u64 new_i_size; 950 u64 i_size = i_size_read(inode); 951 struct rb_node *node; 952 struct rb_node *prev = NULL; 953 struct btrfs_ordered_extent *test; 954 int ret = 1; 955 956 spin_lock_irq(&tree->lock); 957 if (ordered) { 958 offset = entry_end(ordered); 959 if (test_bit(BTRFS_ORDERED_TRUNCATED, &ordered->flags)) 960 offset = min(offset, 961 ordered->file_offset + 962 ordered->truncated_len); 963 } else { 964 offset = ALIGN(offset, BTRFS_I(inode)->root->sectorsize); 965 } 966 disk_i_size = BTRFS_I(inode)->disk_i_size; 967 968 /* truncate file */ 969 if (disk_i_size > i_size) { 970 BTRFS_I(inode)->disk_i_size = i_size; 971 ret = 0; 972 goto out; 973 } 974 975 /* 976 * if the disk i_size is already at the inode->i_size, or 977 * this ordered extent is inside the disk i_size, we're done 978 */ 979 if (disk_i_size == i_size) 980 goto out; 981 982 /* 983 * We still need to update disk_i_size if outstanding_isize is greater 984 * than disk_i_size. 985 */ 986 if (offset <= disk_i_size && 987 (!ordered || ordered->outstanding_isize <= disk_i_size)) 988 goto out; 989 990 /* 991 * walk backward from this ordered extent to disk_i_size. 992 * if we find an ordered extent then we can't update disk i_size 993 * yet 994 */ 995 if (ordered) { 996 node = rb_prev(&ordered->rb_node); 997 } else { 998 prev = tree_search(tree, offset); 999 /* 1000 * we insert file extents without involving ordered struct, 1001 * so there should be no ordered struct cover this offset 1002 */ 1003 if (prev) { 1004 test = rb_entry(prev, struct btrfs_ordered_extent, 1005 rb_node); 1006 BUG_ON(offset_in_entry(test, offset)); 1007 } 1008 node = prev; 1009 } 1010 for (; node; node = rb_prev(node)) { 1011 test = rb_entry(node, struct btrfs_ordered_extent, rb_node); 1012 1013 /* We treat this entry as if it doesn't exist */ 1014 if (test_bit(BTRFS_ORDERED_UPDATED_ISIZE, &test->flags)) 1015 continue; 1016 if (test->file_offset + test->len <= disk_i_size) 1017 break; 1018 if (test->file_offset >= i_size) 1019 break; 1020 if (entry_end(test) > disk_i_size) { 1021 /* 1022 * we don't update disk_i_size now, so record this 1023 * undealt i_size. Or we will not know the real 1024 * i_size. 1025 */ 1026 if (test->outstanding_isize < offset) 1027 test->outstanding_isize = offset; 1028 if (ordered && 1029 ordered->outstanding_isize > 1030 test->outstanding_isize) 1031 test->outstanding_isize = 1032 ordered->outstanding_isize; 1033 goto out; 1034 } 1035 } 1036 new_i_size = min_t(u64, offset, i_size); 1037 1038 /* 1039 * Some ordered extents may completed before the current one, and 1040 * we hold the real i_size in ->outstanding_isize. 1041 */ 1042 if (ordered && ordered->outstanding_isize > new_i_size) 1043 new_i_size = min_t(u64, ordered->outstanding_isize, i_size); 1044 BTRFS_I(inode)->disk_i_size = new_i_size; 1045 ret = 0; 1046 out: 1047 /* 1048 * We need to do this because we can't remove ordered extents until 1049 * after the i_disk_size has been updated and then the inode has been 1050 * updated to reflect the change, so we need to tell anybody who finds 1051 * this ordered extent that we've already done all the real work, we 1052 * just haven't completed all the other work. 1053 */ 1054 if (ordered) 1055 set_bit(BTRFS_ORDERED_UPDATED_ISIZE, &ordered->flags); 1056 spin_unlock_irq(&tree->lock); 1057 return ret; 1058 } 1059 1060 /* 1061 * search the ordered extents for one corresponding to 'offset' and 1062 * try to find a checksum. This is used because we allow pages to 1063 * be reclaimed before their checksum is actually put into the btree 1064 */ 1065 int btrfs_find_ordered_sum(struct inode *inode, u64 offset, u64 disk_bytenr, 1066 u32 *sum, int len) 1067 { 1068 struct btrfs_ordered_sum *ordered_sum; 1069 struct btrfs_ordered_extent *ordered; 1070 struct btrfs_ordered_inode_tree *tree = &BTRFS_I(inode)->ordered_tree; 1071 unsigned long num_sectors; 1072 unsigned long i; 1073 u32 sectorsize = BTRFS_I(inode)->root->sectorsize; 1074 int index = 0; 1075 1076 ordered = btrfs_lookup_ordered_extent(inode, offset); 1077 if (!ordered) 1078 return 0; 1079 1080 spin_lock_irq(&tree->lock); 1081 list_for_each_entry_reverse(ordered_sum, &ordered->list, list) { 1082 if (disk_bytenr >= ordered_sum->bytenr && 1083 disk_bytenr < ordered_sum->bytenr + ordered_sum->len) { 1084 i = (disk_bytenr - ordered_sum->bytenr) >> 1085 inode->i_sb->s_blocksize_bits; 1086 num_sectors = ordered_sum->len >> 1087 inode->i_sb->s_blocksize_bits; 1088 num_sectors = min_t(int, len - index, num_sectors - i); 1089 memcpy(sum + index, ordered_sum->sums + i, 1090 num_sectors); 1091 1092 index += (int)num_sectors; 1093 if (index == len) 1094 goto out; 1095 disk_bytenr += num_sectors * sectorsize; 1096 } 1097 } 1098 out: 1099 spin_unlock_irq(&tree->lock); 1100 btrfs_put_ordered_extent(ordered); 1101 return index; 1102 } 1103 1104 int __init ordered_data_init(void) 1105 { 1106 btrfs_ordered_extent_cache = kmem_cache_create("btrfs_ordered_extent", 1107 sizeof(struct btrfs_ordered_extent), 0, 1108 SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, 1109 NULL); 1110 if (!btrfs_ordered_extent_cache) 1111 return -ENOMEM; 1112 1113 return 0; 1114 } 1115 1116 void ordered_data_exit(void) 1117 { 1118 kmem_cache_destroy(btrfs_ordered_extent_cache); 1119 } 1120