Lines Matching +full:root +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0
16 #include "disk-io.h"
18 #include "delalloc-space.h"
22 #include "block-group.h"
28 if (entry->file_offset + entry->num_bytes < entry->file_offset)
29 return (u64)-1;
30 return entry->file_offset + entry->num_bytes;
33 /* returns NULL if the insertion worked, or it returns the node it did find
36 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset,
37 struct rb_node *node)
39 struct rb_node **p = &root->rb_node;
47 if (file_offset < entry->file_offset)
48 p = &(*p)->rb_left;
50 p = &(*p)->rb_right;
55 rb_link_node(node, parent, p);
56 rb_insert_color(node, root);
64 static struct rb_node *__tree_search(struct rb_root *root, u64 file_offset,
67 struct rb_node *n = root->rb_node;
78 if (file_offset < entry->file_offset)
79 n = n->rb_left;
81 n = n->rb_right;
117 if (file_offset + len <= entry->file_offset ||
118 entry->file_offset + entry->num_bytes <= file_offset)
134 if (inode->ordered_tree_last) {
135 entry = rb_entry(inode->ordered_tree_last, struct btrfs_ordered_extent,
137 if (in_range(file_offset, entry->file_offset, entry->num_bytes))
138 return inode->ordered_tree_last;
140 ret = __tree_search(&inode->ordered_tree, file_offset, &prev);
144 inode->ordered_tree_last = ret;
177 entry = ERR_PTR(-ENOMEM);
181 entry->file_offset = file_offset;
182 entry->num_bytes = num_bytes;
183 entry->ram_bytes = ram_bytes;
184 entry->disk_bytenr = disk_bytenr;
185 entry->disk_num_bytes = disk_num_bytes;
186 entry->offset = offset;
187 entry->bytes_left = num_bytes;
188 if (WARN_ON_ONCE(!igrab(&inode->vfs_inode))) {
190 entry = ERR_PTR(-ESTALE);
193 entry->inode = inode;
194 entry->compress_type = compress_type;
195 entry->truncated_len = (u64)-1;
196 entry->qgroup_rsv = qgroup_rsv;
197 entry->flags = flags;
198 refcount_set(&entry->refs, 1);
199 init_waitqueue_head(&entry->wait);
200 INIT_LIST_HEAD(&entry->list);
201 INIT_LIST_HEAD(&entry->log_list);
202 INIT_LIST_HEAD(&entry->root_extent_list);
203 INIT_LIST_HEAD(&entry->work_list);
204 INIT_LIST_HEAD(&entry->bioc_list);
205 init_completion(&entry->completion);
212 spin_lock(&inode->lock);
214 spin_unlock(&inode->lock);
218 btrfs_qgroup_free_refroot(inode->root->fs_info,
219 btrfs_root_id(inode->root),
227 struct btrfs_inode *inode = entry->inode;
228 struct btrfs_root *root = inode->root;
229 struct btrfs_fs_info *fs_info = root->fs_info;
230 struct rb_node *node;
234 percpu_counter_add_batch(&fs_info->ordered_bytes, entry->num_bytes,
235 fs_info->delalloc_batch);
238 refcount_inc(&entry->refs);
240 spin_lock_irq(&inode->ordered_tree_lock);
241 node = tree_insert(&inode->ordered_tree, entry->file_offset,
242 &entry->rb_node);
243 if (unlikely(node))
244 btrfs_panic(fs_info, -EEXIST,
246 entry->file_offset);
247 spin_unlock_irq(&inode->ordered_tree_lock);
249 spin_lock(&root->ordered_extent_lock);
250 list_add_tail(&entry->root_extent_list,
251 &root->ordered_extents);
252 root->nr_ordered_extents++;
253 if (root->nr_ordered_extents == 1) {
254 spin_lock(&fs_info->ordered_root_lock);
255 BUG_ON(!list_empty(&root->ordered_root));
256 list_add_tail(&root->ordered_root, &fs_info->ordered_roots);
257 spin_unlock(&fs_info->ordered_root_lock);
259 spin_unlock(&root->ordered_extent_lock);
263 * Add an ordered extent to the per-inode tree.
293 * file_extent->num_bytes, as we won't insert a file extent item at all.
303 file_extent->num_bytes,
304 file_extent->num_bytes,
305 file_extent->disk_bytenr + file_extent->offset,
306 file_extent->num_bytes, 0, flags,
307 file_extent->compression);
310 file_extent->num_bytes,
311 file_extent->ram_bytes,
312 file_extent->disk_bytenr,
313 file_extent->disk_num_bytes,
314 file_extent->offset, flags,
315 file_extent->compression);
329 struct btrfs_inode *inode = entry->inode;
331 spin_lock_irq(&inode->ordered_tree_lock);
332 list_add_tail(&sum->list, &entry->list);
333 spin_unlock_irq(&inode->ordered_tree_lock);
338 if (!test_and_set_bit(BTRFS_ORDERED_IOERR, &ordered->flags))
339 mapping_set_error(ordered->inode->vfs_inode.i_mapping, -EIO);
354 struct btrfs_inode *inode = ordered->inode;
355 struct btrfs_fs_info *fs_info = inode->root->fs_info;
357 lockdep_assert_held(&inode->ordered_tree_lock);
360 ASSERT(folio->mapping);
376 if (WARN_ON_ONCE(len > ordered->bytes_left)) {
378 "bad ordered extent accounting, root=%llu ino=%llu OE offset=%llu OE len=%llu to_dec=%llu left=%llu",
379 btrfs_root_id(inode->root), btrfs_ino(inode),
380 ordered->file_offset, ordered->num_bytes,
381 len, ordered->bytes_left);
382 ordered->bytes_left = 0;
384 ordered->bytes_left -= len;
388 set_bit(BTRFS_ORDERED_IOERR, &ordered->flags);
390 if (ordered->bytes_left)
397 set_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags);
398 cond_wake_up(&ordered->wait);
399 refcount_inc(&ordered->refs);
406 struct btrfs_inode *inode = ordered->inode;
407 struct btrfs_fs_info *fs_info = inode->root->fs_info;
409 fs_info->endio_freespace_worker : fs_info->endio_write_workers;
411 btrfs_init_work(&ordered->work, finish_ordered_fn, NULL);
412 btrfs_queue_work(wq, &ordered->work);
419 struct btrfs_inode *inode = ordered->inode;
425 spin_lock_irqsave(&inode->ordered_tree_lock, flags);
428 spin_unlock_irqrestore(&inode->ordered_tree_lock, flags);
458 if (!uptodate && !test_bit(BTRFS_ORDERED_NOCOW, &ordered->flags))
459 set_bit(BTRFS_INODE_COW_WRITE_ERROR, &inode->runtime_flags);
482 struct rb_node *node;
488 file_offset + num_bytes - 1,
491 spin_lock_irqsave(&inode->ordered_tree_lock, flags);
497 node = ordered_tree_search(inode, cur);
499 if (!node)
502 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
503 entry_end = entry->file_offset + entry->num_bytes;
505 * |<-- OE --->| |
510 node = rb_next(node);
512 if (!node)
514 entry = rb_entry(node, struct btrfs_ordered_extent,
518 cur = entry->file_offset;
522 * | |<--- OE --->|
526 if (cur < entry->file_offset) {
527 cur = entry->file_offset;
534 * |<--- OE --->|
538 end = min(entry->file_offset + entry->num_bytes,
539 file_offset + num_bytes) - 1;
540 ASSERT(end + 1 - cur < U32_MAX);
541 len = end + 1 - cur;
544 spin_unlock_irqrestore(&inode->ordered_tree_lock, flags);
546 spin_lock_irqsave(&inode->ordered_tree_lock, flags);
550 spin_unlock_irqrestore(&inode->ordered_tree_lock, flags);
574 struct rb_node *node;
579 spin_lock_irqsave(&inode->ordered_tree_lock, flags);
585 node = ordered_tree_search(inode, file_offset);
586 if (!node)
589 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
591 if (!in_range(file_offset, entry->file_offset, entry->num_bytes))
594 if (io_size > entry->bytes_left)
595 btrfs_crit(inode->root->fs_info,
597 entry->bytes_left, io_size);
599 entry->bytes_left -= io_size;
601 if (entry->bytes_left == 0) {
606 finished = !test_and_set_bit(BTRFS_ORDERED_IO_DONE, &entry->flags);
608 cond_wake_up_nomb(&entry->wait);
613 refcount_inc(&entry->refs);
616 spin_unlock_irqrestore(&inode->ordered_tree_lock, flags);
626 trace_btrfs_ordered_extent_put(entry->inode, entry);
628 if (refcount_dec_and_test(&entry->refs)) {
632 ASSERT(list_empty(&entry->root_extent_list));
633 ASSERT(list_empty(&entry->log_list));
634 ASSERT(RB_EMPTY_NODE(&entry->rb_node));
635 btrfs_add_delayed_iput(entry->inode);
636 list_for_each_entry_safe(sum, tmp, &entry->list, list)
649 struct btrfs_root *root = btrfs_inode->root;
650 struct btrfs_fs_info *fs_info = root->fs_info;
651 struct rb_node *node;
663 spin_lock(&btrfs_inode->lock);
664 btrfs_mod_outstanding_extents(btrfs_inode, -1);
665 spin_unlock(&btrfs_inode->lock);
666 if (root != fs_info->tree_root) {
669 if (test_bit(BTRFS_ORDERED_ENCODED, &entry->flags))
670 release = entry->disk_num_bytes;
672 release = entry->num_bytes;
675 &entry->flags));
678 percpu_counter_add_batch(&fs_info->ordered_bytes, -entry->num_bytes,
679 fs_info->delalloc_batch);
681 spin_lock_irq(&btrfs_inode->ordered_tree_lock);
682 node = &entry->rb_node;
683 rb_erase(node, &btrfs_inode->ordered_tree);
684 RB_CLEAR_NODE(node);
685 if (btrfs_inode->ordered_tree_last == node)
686 btrfs_inode->ordered_tree_last = NULL;
687 set_bit(BTRFS_ORDERED_COMPLETE, &entry->flags);
688 pending = test_and_clear_bit(BTRFS_ORDERED_PENDING, &entry->flags);
689 spin_unlock_irq(&btrfs_inode->ordered_tree_lock);
704 spin_lock(&fs_info->trans_lock);
705 trans = fs_info->running_transaction;
707 refcount_inc(&trans->use_count);
708 spin_unlock(&fs_info->trans_lock);
712 if (atomic_dec_and_test(&trans->pending_ordered))
713 wake_up(&trans->pending_wait);
720 spin_lock(&root->ordered_extent_lock);
721 list_del_init(&entry->root_extent_list);
722 root->nr_ordered_extents--;
726 if (!root->nr_ordered_extents) {
727 spin_lock(&fs_info->ordered_root_lock);
728 BUG_ON(list_empty(&root->ordered_root));
729 list_del_init(&root->ordered_root);
730 spin_unlock(&fs_info->ordered_root_lock);
732 spin_unlock(&root->ordered_extent_lock);
733 wake_up(&entry->wait);
744 complete(&ordered->completion);
748 * Wait for all the ordered extents in a root. Use @bg as range or do whole
751 u64 btrfs_wait_ordered_extents(struct btrfs_root *root, u64 nr,
754 struct btrfs_fs_info *fs_info = root->fs_info;
764 range_start = bg->start;
765 range_len = bg->length;
772 mutex_lock(&root->ordered_extent_mutex);
773 spin_lock(&root->ordered_extent_lock);
774 list_splice_init(&root->ordered_extents, &splice);
779 if (range_end <= ordered->disk_bytenr ||
780 ordered->disk_bytenr + ordered->disk_num_bytes <= range_start) {
781 list_move_tail(&ordered->root_extent_list, &skipped);
782 cond_resched_lock(&root->ordered_extent_lock);
786 list_move_tail(&ordered->root_extent_list,
787 &root->ordered_extents);
788 refcount_inc(&ordered->refs);
789 spin_unlock(&root->ordered_extent_lock);
791 btrfs_init_work(&ordered->flush_work,
793 list_add_tail(&ordered->work_list, &works);
794 btrfs_queue_work(fs_info->flush_workers, &ordered->flush_work);
798 nr--;
800 spin_lock(&root->ordered_extent_lock);
802 list_splice_tail(&skipped, &root->ordered_extents);
803 list_splice_tail(&splice, &root->ordered_extents);
804 spin_unlock(&root->ordered_extent_lock);
807 list_del_init(&ordered->work_list);
808 wait_for_completion(&ordered->completion);
812 mutex_unlock(&root->ordered_extent_mutex);
824 struct btrfs_root *root;
828 mutex_lock(&fs_info->ordered_operations_mutex);
829 spin_lock(&fs_info->ordered_root_lock);
830 list_splice_init(&fs_info->ordered_roots, &splice);
832 root = list_first_entry(&splice, struct btrfs_root,
834 root = btrfs_grab_root(root);
835 BUG_ON(!root);
836 list_move_tail(&root->ordered_root,
837 &fs_info->ordered_roots);
838 spin_unlock(&fs_info->ordered_root_lock);
840 done = btrfs_wait_ordered_extents(root, nr, bg);
841 btrfs_put_root(root);
844 nr -= done;
846 spin_lock(&fs_info->ordered_root_lock);
848 list_splice_tail(&splice, &fs_info->ordered_roots);
849 spin_unlock(&fs_info->ordered_root_lock);
850 mutex_unlock(&fs_info->ordered_operations_mutex);
863 u64 start = entry->file_offset;
864 u64 end = start + entry->num_bytes - 1;
865 struct btrfs_inode *inode = entry->inode;
881 if (!test_bit(BTRFS_ORDERED_DIRECT, &entry->flags)) {
883 filemap_fdatawrite_range(inode->vfs_inode.i_mapping, start, end);
886 filemap_fdatawrite_range(inode->vfs_inode.i_mapping, start,
887 nowriteback_start - 1);
889 filemap_fdatawrite_range(inode->vfs_inode.i_mapping,
896 btrfs_might_wait_for_event(inode->root->fs_info, btrfs_ordered_extent);
897 wait_event(entry->wait, test_bit(BTRFS_ORDERED_COMPLETE, &entry->flags));
914 orig_end = start + len - 1;
930 * before the ordered extents complete - to avoid failures (-EEXIST)
933 ret_wb = filemap_fdatawait_range(inode->vfs_inode.i_mapping, start, orig_end);
940 if (ordered->file_offset > orig_end) {
944 if (ordered->file_offset + ordered->num_bytes <= start) {
949 end = ordered->file_offset;
955 if (test_bit(BTRFS_ORDERED_IOERR, &ordered->flags))
956 ret = -EIO;
960 end--;
972 struct rb_node *node;
976 spin_lock_irqsave(&inode->ordered_tree_lock, flags);
977 node = ordered_tree_search(inode, file_offset);
978 if (!node)
981 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
982 if (!in_range(file_offset, entry->file_offset, entry->num_bytes))
985 refcount_inc(&entry->refs);
989 spin_unlock_irqrestore(&inode->ordered_tree_lock, flags);
999 struct rb_node *node;
1002 spin_lock_irq(&inode->ordered_tree_lock);
1003 node = ordered_tree_search(inode, file_offset);
1004 if (!node) {
1005 node = ordered_tree_search(inode, file_offset + len);
1006 if (!node)
1011 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
1015 if (entry->file_offset >= file_offset + len) {
1020 node = rb_next(node);
1021 if (!node)
1026 refcount_inc(&entry->refs);
1029 spin_unlock_irq(&inode->ordered_tree_lock);
1044 spin_lock_irq(&inode->ordered_tree_lock);
1045 for (n = rb_first(&inode->ordered_tree); n; n = rb_next(n)) {
1050 if (test_bit(BTRFS_ORDERED_LOGGED, &ordered->flags))
1053 ASSERT(list_empty(&ordered->log_list));
1054 list_add_tail(&ordered->log_list, list);
1055 refcount_inc(&ordered->refs);
1058 spin_unlock_irq(&inode->ordered_tree_lock);
1068 struct rb_node *node;
1071 spin_lock_irq(&inode->ordered_tree_lock);
1072 node = ordered_tree_search(inode, file_offset);
1073 if (!node)
1076 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
1077 refcount_inc(&entry->refs);
1080 spin_unlock_irq(&inode->ordered_tree_lock);
1096 struct rb_node *node;
1102 spin_lock_irq(&inode->ordered_tree_lock);
1103 node = inode->ordered_tree.rb_node;
1105 * Here we don't want to use tree_search() which will use tree->last
1110 while (node) {
1111 entry = rb_entry(node, struct btrfs_ordered_extent, rb_node);
1113 if (file_offset < entry->file_offset) {
1114 node = node->rb_left;
1116 node = node->rb_right;
1130 cur = &entry->rb_node;
1132 if (entry->file_offset < file_offset) {
1153 refcount_inc(&entry->refs);
1157 spin_unlock_irq(&inode->ordered_tree_lock);
1187 btrfs_lock_extent(&inode->io_tree, start, end, cachedp);
1189 end - start + 1);
1197 refcount_dec(&cache->refs);
1200 btrfs_unlock_extent(&inode->io_tree, start, end, cachedp);
1218 if (!btrfs_try_lock_extent(&inode->io_tree, start, end, cached_state))
1221 ordered = btrfs_lookup_ordered_range(inode, start, end - start + 1);
1226 btrfs_unlock_extent(&inode->io_tree, start, end, cached_state);
1235 struct btrfs_inode *inode = ordered->inode;
1236 struct btrfs_root *root = inode->root;
1237 struct btrfs_fs_info *fs_info = root->fs_info;
1238 u64 file_offset = ordered->file_offset;
1239 u64 disk_bytenr = ordered->disk_bytenr;
1240 unsigned long flags = ordered->flags;
1243 struct rb_node *node;
1254 if (WARN_ON_ONCE(len >= ordered->num_bytes))
1255 return ERR_PTR(-EINVAL);
1266 return fs_error ? ERR_PTR(fs_error) : ERR_PTR(-EIO);
1269 if (ordered->bytes_left) {
1271 if (WARN_ON_ONCE(ordered->bytes_left != ordered->disk_num_bytes))
1272 return ERR_PTR(-EINVAL);
1275 if (WARN_ON_ONCE(ordered->disk_num_bytes != ordered->num_bytes))
1276 return ERR_PTR(-EINVAL);
1279 len, 0, flags, ordered->compress_type);
1284 refcount_inc(&new->refs);
1287 * Take the root's ordered_extent_lock to avoid a race with
1300 * so we take the root's ordered_extent_lock to fix that race during
1303 spin_lock_irq(&root->ordered_extent_lock);
1304 spin_lock(&inode->ordered_tree_lock);
1310 * no need to remove it and re-insert it in the tree.
1312 ordered->file_offset += len;
1313 ordered->disk_bytenr += len;
1314 ordered->num_bytes -= len;
1315 ordered->disk_num_bytes -= len;
1316 ordered->ram_bytes -= len;
1318 if (test_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags)) {
1319 ASSERT(ordered->bytes_left == 0);
1320 new->bytes_left = 0;
1322 ordered->bytes_left -= len;
1325 if (test_bit(BTRFS_ORDERED_TRUNCATED, &ordered->flags)) {
1326 if (ordered->truncated_len > len) {
1327 ordered->truncated_len -= len;
1329 new->truncated_len = ordered->truncated_len;
1330 ordered->truncated_len = 0;
1334 list_for_each_entry_safe(sum, tmpsum, &ordered->list, list) {
1337 list_move_tail(&sum->list, &new->list);
1338 offset += sum->len;
1341 node = tree_insert(&inode->ordered_tree, new->file_offset, &new->rb_node);
1342 if (unlikely(node))
1343 btrfs_panic(fs_info, -EEXIST,
1345 new->file_offset);
1346 spin_unlock(&inode->ordered_tree_lock);
1348 list_add_tail(&new->root_extent_list, &root->ordered_extents);
1349 root->nr_ordered_extents++;
1350 spin_unlock_irq(&root->ordered_extent_lock);
1358 return -ENOMEM;