Lines Matching +full:parent +full:- +full:locked
1 // SPDX-License-Identifier: GPL-2.0
3 #include "tree-mod-log.h"
4 #include "disk-io.h"
45 return atomic64_inc_return(&fs_info->tree_mod_seq); in btrfs_inc_tree_mod_seq()
51 * to record tree modifications, it should ensure to set elem->seq to zero
59 write_lock(&fs_info->tree_mod_log_lock); in btrfs_get_tree_mod_seq()
60 if (!elem->seq) { in btrfs_get_tree_mod_seq()
61 elem->seq = btrfs_inc_tree_mod_seq(fs_info); in btrfs_get_tree_mod_seq()
62 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list); in btrfs_get_tree_mod_seq()
63 set_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags); in btrfs_get_tree_mod_seq()
65 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_get_tree_mod_seq()
67 return elem->seq; in btrfs_get_tree_mod_seq()
78 u64 seq_putting = elem->seq; in btrfs_put_tree_mod_seq()
83 write_lock(&fs_info->tree_mod_log_lock); in btrfs_put_tree_mod_seq()
84 list_del(&elem->list); in btrfs_put_tree_mod_seq()
85 elem->seq = 0; in btrfs_put_tree_mod_seq()
87 if (list_empty(&fs_info->tree_mod_seq_list)) { in btrfs_put_tree_mod_seq()
88 clear_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags); in btrfs_put_tree_mod_seq()
92 first = list_first_entry(&fs_info->tree_mod_seq_list, in btrfs_put_tree_mod_seq()
94 if (seq_putting > first->seq) { in btrfs_put_tree_mod_seq()
99 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_put_tree_mod_seq()
102 min_seq = first->seq; in btrfs_put_tree_mod_seq()
109 tm_root = &fs_info->tree_mod_log; in btrfs_put_tree_mod_seq()
113 if (tm->seq >= min_seq) in btrfs_put_tree_mod_seq()
118 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_put_tree_mod_seq()
123 * node/leaf start address -> sequence
134 struct rb_node *parent = NULL; in tree_mod_log_insert() local
137 lockdep_assert_held_write(&fs_info->tree_mod_log_lock); in tree_mod_log_insert()
139 tm->seq = btrfs_inc_tree_mod_seq(fs_info); in tree_mod_log_insert()
141 tm_root = &fs_info->tree_mod_log; in tree_mod_log_insert()
142 new = &tm_root->rb_node; in tree_mod_log_insert()
145 parent = *new; in tree_mod_log_insert()
146 if (cur->logical < tm->logical) in tree_mod_log_insert()
147 new = &((*new)->rb_left); in tree_mod_log_insert()
148 else if (cur->logical > tm->logical) in tree_mod_log_insert()
149 new = &((*new)->rb_right); in tree_mod_log_insert()
150 else if (cur->seq < tm->seq) in tree_mod_log_insert()
151 new = &((*new)->rb_left); in tree_mod_log_insert()
152 else if (cur->seq > tm->seq) in tree_mod_log_insert()
153 new = &((*new)->rb_right); in tree_mod_log_insert()
155 return -EEXIST; in tree_mod_log_insert()
158 rb_link_node(&tm->node, parent, new); in tree_mod_log_insert()
159 rb_insert_color(&tm->node, tm_root); in tree_mod_log_insert()
172 if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags)) in tree_mod_dont_log()
177 write_lock(&fs_info->tree_mod_log_lock); in tree_mod_dont_log()
178 if (list_empty(&(fs_info)->tree_mod_seq_list)) { in tree_mod_dont_log()
179 write_unlock(&fs_info->tree_mod_log_lock); in tree_mod_dont_log()
190 if (!test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags)) in tree_mod_need_log()
209 tm->logical = eb->start; in alloc_tree_mod_elem()
211 btrfs_node_key(eb, &tm->key, slot); in alloc_tree_mod_elem()
212 tm->blockptr = btrfs_node_blockptr(eb, slot); in alloc_tree_mod_elem()
214 tm->op = op; in alloc_tree_mod_elem()
215 tm->slot = slot; in alloc_tree_mod_elem()
216 tm->generation = btrfs_node_ptr_generation(eb, slot); in alloc_tree_mod_elem()
217 RB_CLEAR_NODE(&tm->node); in alloc_tree_mod_elem()
228 if (!tree_mod_need_log(eb->fs_info, eb)) in btrfs_tree_mod_log_insert_key()
233 return -ENOMEM; in btrfs_tree_mod_log_insert_key()
235 if (tree_mod_dont_log(eb->fs_info, eb)) { in btrfs_tree_mod_log_insert_key()
240 ret = tree_mod_log_insert(eb->fs_info, tm); in btrfs_tree_mod_log_insert_key()
241 write_unlock(&eb->fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_insert_key()
256 bool locked = false; in btrfs_tree_mod_log_insert_move() local
258 if (!tree_mod_need_log(eb->fs_info, eb)) in btrfs_tree_mod_log_insert_move()
263 return -ENOMEM; in btrfs_tree_mod_log_insert_move()
267 ret = -ENOMEM; in btrfs_tree_mod_log_insert_move()
271 tm->logical = eb->start; in btrfs_tree_mod_log_insert_move()
272 tm->slot = src_slot; in btrfs_tree_mod_log_insert_move()
273 tm->move.dst_slot = dst_slot; in btrfs_tree_mod_log_insert_move()
274 tm->move.nr_items = nr_items; in btrfs_tree_mod_log_insert_move()
275 tm->op = BTRFS_MOD_LOG_MOVE_KEYS; in btrfs_tree_mod_log_insert_move()
281 ret = -ENOMEM; in btrfs_tree_mod_log_insert_move()
286 if (tree_mod_dont_log(eb->fs_info, eb)) in btrfs_tree_mod_log_insert_move()
288 locked = true; in btrfs_tree_mod_log_insert_move()
296 ret = tree_mod_log_insert(eb->fs_info, tm_list[i]); in btrfs_tree_mod_log_insert_move()
301 ret = tree_mod_log_insert(eb->fs_info, tm); in btrfs_tree_mod_log_insert_move()
304 write_unlock(&eb->fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_insert_move()
311 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node)) in btrfs_tree_mod_log_insert_move()
312 rb_erase(&tm_list[i]->node, &eb->fs_info->tree_mod_log); in btrfs_tree_mod_log_insert_move()
315 if (locked) in btrfs_tree_mod_log_insert_move()
316 write_unlock(&eb->fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_insert_move()
330 for (i = nritems - 1; i >= 0; i--) { in tree_mod_log_free_eb()
333 for (j = nritems - 1; j > i; j--) in tree_mod_log_free_eb()
334 rb_erase(&tm_list[j]->node, in tree_mod_log_free_eb()
335 &fs_info->tree_mod_log); in tree_mod_log_free_eb()
347 struct btrfs_fs_info *fs_info = old_root->fs_info; in btrfs_tree_mod_log_insert_root()
362 ret = -ENOMEM; in btrfs_tree_mod_log_insert_root()
369 ret = -ENOMEM; in btrfs_tree_mod_log_insert_root()
377 ret = -ENOMEM; in btrfs_tree_mod_log_insert_root()
381 tm->logical = new_root->start; in btrfs_tree_mod_log_insert_root()
382 tm->old_root.logical = old_root->start; in btrfs_tree_mod_log_insert_root()
383 tm->old_root.level = btrfs_header_level(old_root); in btrfs_tree_mod_log_insert_root()
384 tm->generation = btrfs_header_generation(old_root); in btrfs_tree_mod_log_insert_root()
385 tm->op = BTRFS_MOD_LOG_ROOT_REPLACE; in btrfs_tree_mod_log_insert_root()
395 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_insert_root()
422 read_lock(&fs_info->tree_mod_log_lock); in __tree_mod_log_search()
423 tm_root = &fs_info->tree_mod_log; in __tree_mod_log_search()
424 node = tm_root->rb_node; in __tree_mod_log_search()
427 if (cur->logical < start) { in __tree_mod_log_search()
428 node = node->rb_left; in __tree_mod_log_search()
429 } else if (cur->logical > start) { in __tree_mod_log_search()
430 node = node->rb_right; in __tree_mod_log_search()
431 } else if (cur->seq < min_seq) { in __tree_mod_log_search()
432 node = node->rb_left; in __tree_mod_log_search()
436 BUG_ON(found->seq > cur->seq); in __tree_mod_log_search()
438 node = node->rb_left; in __tree_mod_log_search()
439 } else if (cur->seq > min_seq) { in __tree_mod_log_search()
442 BUG_ON(found->seq < cur->seq); in __tree_mod_log_search()
444 node = node->rb_right; in __tree_mod_log_search()
450 read_unlock(&fs_info->tree_mod_log_lock); in __tree_mod_log_search()
483 struct btrfs_fs_info *fs_info = dst->fs_info; in btrfs_tree_mod_log_eb_copy()
488 bool locked = false; in btrfs_tree_mod_log_eb_copy() local
499 return -ENOMEM; in btrfs_tree_mod_log_eb_copy()
507 ret = -ENOMEM; in btrfs_tree_mod_log_eb_copy()
514 ret = -ENOMEM; in btrfs_tree_mod_log_eb_copy()
521 locked = true; in btrfs_tree_mod_log_eb_copy()
532 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_eb_copy()
539 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node)) in btrfs_tree_mod_log_eb_copy()
540 rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log); in btrfs_tree_mod_log_eb_copy()
543 if (locked) in btrfs_tree_mod_log_eb_copy()
544 write_unlock(&fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_eb_copy()
557 if (!tree_mod_need_log(eb->fs_info, eb)) in btrfs_tree_mod_log_free_eb()
563 return -ENOMEM; in btrfs_tree_mod_log_free_eb()
569 ret = -ENOMEM; in btrfs_tree_mod_log_free_eb()
574 if (tree_mod_dont_log(eb->fs_info, eb)) in btrfs_tree_mod_log_free_eb()
577 ret = tree_mod_log_free_eb(eb->fs_info, tm_list, nritems); in btrfs_tree_mod_log_free_eb()
578 write_unlock(&eb->fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_free_eb()
602 u64 root_logical = eb_root->start; in tree_mod_log_oldest_root()
615 tm = tree_mod_log_search_oldest(eb_root->fs_info, root_logical, in tree_mod_log_oldest_root()
632 if (tm->op != BTRFS_MOD_LOG_ROOT_REPLACE) in tree_mod_log_oldest_root()
636 root_logical = tm->old_root.logical; in tree_mod_log_oldest_root()
666 read_lock(&fs_info->tree_mod_log_lock); in tree_mod_log_rewind()
667 while (tm && tm->seq >= time_seq) { in tree_mod_log_rewind()
673 switch (tm->op) { in tree_mod_log_rewind()
675 BUG_ON(tm->slot < n); in tree_mod_log_rewind()
679 btrfs_set_node_key(eb, &tm->key, tm->slot); in tree_mod_log_rewind()
680 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr); in tree_mod_log_rewind()
681 btrfs_set_node_ptr_generation(eb, tm->slot, in tree_mod_log_rewind()
682 tm->generation); in tree_mod_log_rewind()
686 BUG_ON(tm->slot >= n); in tree_mod_log_rewind()
687 btrfs_set_node_key(eb, &tm->key, tm->slot); in tree_mod_log_rewind()
688 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr); in tree_mod_log_rewind()
689 btrfs_set_node_ptr_generation(eb, tm->slot, in tree_mod_log_rewind()
690 tm->generation); in tree_mod_log_rewind()
694 n--; in tree_mod_log_rewind()
697 o_dst = btrfs_node_key_ptr_offset(tm->slot); in tree_mod_log_rewind()
698 o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot); in tree_mod_log_rewind()
700 tm->move.nr_items * p_size); in tree_mod_log_rewind()
706 * For non-roots, this operation may exist if the node in tree_mod_log_rewind()
707 * was a root: root A -> child B; then A gets empty and in tree_mod_log_rewind()
709 * have a root-replace operation for B, a tree block in tree_mod_log_rewind()
714 next = rb_next(&tm->node); in tree_mod_log_rewind()
718 if (tm->logical != first_tm->logical) in tree_mod_log_rewind()
721 read_unlock(&fs_info->tree_mod_log_lock); in tree_mod_log_rewind()
726 * Called with eb read locked. If the buffer cannot be rewound, the same buffer
728 * returned buffer is always read-locked. If the returned buffer is not the
746 tm = tree_mod_log_search(fs_info, eb->start, time_seq); in btrfs_tree_mod_log_rewind()
750 if (tm->op == BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) { in btrfs_tree_mod_log_rewind()
751 BUG_ON(tm->slot != 0); in btrfs_tree_mod_log_rewind()
752 eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start); in btrfs_tree_mod_log_rewind()
758 btrfs_set_header_bytenr(eb_rewin, eb->start); in btrfs_tree_mod_log_rewind()
787 * If there are no changes, the current root->root_node is returned. If anything
789 * operations are done. In any case, the returned buffer is read locked.
794 struct btrfs_fs_info *fs_info = root->fs_info; in btrfs_get_old_root()
810 if (tm->op == BTRFS_MOD_LOG_ROOT_REPLACE) { in btrfs_get_old_root()
811 old_root = &tm->old_root; in btrfs_get_old_root()
812 old_generation = tm->generation; in btrfs_get_old_root()
813 logical = old_root->logical; in btrfs_get_old_root()
814 level = old_root->level; in btrfs_get_old_root()
816 logical = eb_root->start; in btrfs_get_old_root()
821 if (old_root && tm && tm->op != BTRFS_MOD_LOG_KEY_REMOVE_WHILE_FREEING) { in btrfs_get_old_root()
824 old = read_tree_block(fs_info, logical, root->root_key.objectid, in btrfs_get_old_root()
839 * above and before we locked and cloned the extent buffer in btrfs_get_old_root()
851 ASSERT(tm2 == tm || tm2->seq > tm->seq); in btrfs_get_old_root()
852 if (!tm2 || tm2->seq < tm->seq) { in btrfs_get_old_root()
872 btrfs_set_header_bytenr(eb, eb->start); in btrfs_get_old_root()
875 btrfs_set_header_level(eb, old_root->level); in btrfs_get_old_root()
897 if (tm && tm->op == BTRFS_MOD_LOG_ROOT_REPLACE) in btrfs_old_root_level()
898 level = tm->old_root.level; in btrfs_old_root_level()
918 read_lock(&fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_lowest_seq()
919 if (!list_empty(&fs_info->tree_mod_seq_list)) { in btrfs_tree_mod_log_lowest_seq()
922 elem = list_first_entry(&fs_info->tree_mod_seq_list, in btrfs_tree_mod_log_lowest_seq()
924 ret = elem->seq; in btrfs_tree_mod_log_lowest_seq()
926 read_unlock(&fs_info->tree_mod_log_lock); in btrfs_tree_mod_log_lowest_seq()