Lines Matching full:upper
46 /* list of upper level blocks reference this block */
47 struct list_head upper; member
67 * 1 if corresponding block has been cowed but some upper
87 #define UPPER 1 macro
97 * pointers in upper level blocks may not reflect the
246 INIT_LIST_HEAD(&node->upper); in alloc_backref_node()
347 while (!list_empty(&node->upper)) { in walk_up_backref()
348 edge = list_entry(node->upper.next, in walk_up_backref()
351 node = edge->node[UPPER]; in walk_up_backref()
371 if (list_is_last(&edge->list[LOWER], &lower->upper)) { in walk_down_backref()
379 return edge->node[UPPER]; in walk_down_backref()
405 BUG_ON(!list_empty(&node->upper)); in drop_backref_node()
421 struct backref_node *upper; in remove_backref_node() local
428 while (!list_empty(&node->upper)) { in remove_backref_node()
429 edge = list_entry(node->upper.next, struct backref_edge, in remove_backref_node()
431 upper = edge->node[UPPER]; in remove_backref_node()
433 list_del(&edge->list[UPPER]); in remove_backref_node()
436 if (RB_EMPTY_NODE(&upper->rb_node)) { in remove_backref_node()
437 BUG_ON(!list_empty(&node->upper)); in remove_backref_node()
439 node = upper; in remove_backref_node()
447 if (list_empty(&upper->lower)) { in remove_backref_node()
448 list_add_tail(&upper->lower, &cache->leaves); in remove_backref_node()
449 upper->lowest = 1; in remove_backref_node()
641 * to find upper level blocks that reference the block, and then check
642 * backrefs of these upper level blocks recursively. the recursion stop
646 * for all upper level blocks that directly/indirectly reference the
660 struct backref_node *upper; in build_backref_tree() local
669 LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */ in build_backref_tree()
716 if (!list_empty(&cur->upper)) { in build_backref_tree()
721 ASSERT(list_is_singular(&cur->upper)); in build_backref_tree()
722 edge = list_entry(cur->upper.next, struct backref_edge, in build_backref_tree()
724 ASSERT(list_empty(&edge->list[UPPER])); in build_backref_tree()
725 exist = edge->node[UPPER]; in build_backref_tree()
727 * add the upper level block to pending list if we need in build_backref_tree()
731 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
818 upper = alloc_backref_node(cache); in build_backref_tree()
819 if (!upper) { in build_backref_tree()
824 upper->bytenr = key.offset; in build_backref_tree()
825 upper->level = cur->level + 1; in build_backref_tree()
827 * backrefs for the upper level block isn't in build_backref_tree()
830 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
832 upper = rb_entry(rb_node, struct backref_node, in build_backref_tree()
834 ASSERT(upper->checked); in build_backref_tree()
835 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
837 list_add_tail(&edge->list[LOWER], &cur->upper); in build_backref_tree()
839 edge->node[UPPER] = upper; in build_backref_tree()
928 upper = alloc_backref_node(cache); in build_backref_tree()
929 if (!upper) { in build_backref_tree()
934 upper->bytenr = eb->start; in build_backref_tree()
935 upper->owner = btrfs_header_owner(eb); in build_backref_tree()
936 upper->level = lower->level + 1; in build_backref_tree()
939 upper->cowonly = 1; in build_backref_tree()
946 upper->checked = 0; in build_backref_tree()
948 upper->checked = 1; in build_backref_tree()
956 if (!upper->checked && need_check) { in build_backref_tree()
958 list_add_tail(&edge->list[UPPER], in build_backref_tree()
961 if (upper->checked) in build_backref_tree()
963 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
966 upper = rb_entry(rb_node, struct backref_node, in build_backref_tree()
968 ASSERT(upper->checked); in build_backref_tree()
969 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
970 if (!upper->owner) in build_backref_tree()
971 upper->owner = btrfs_header_owner(eb); in build_backref_tree()
973 list_add_tail(&edge->list[LOWER], &lower->upper); in build_backref_tree()
975 edge->node[UPPER] = upper; in build_backref_tree()
979 lower = upper; in build_backref_tree()
980 upper = NULL; in build_backref_tree()
1002 edge = list_entry(list.next, struct backref_edge, list[UPPER]); in build_backref_tree()
1003 list_del_init(&edge->list[UPPER]); in build_backref_tree()
1004 cur = edge->node[UPPER]; in build_backref_tree()
1022 list_for_each_entry(edge, &node->upper, list[LOWER]) in build_backref_tree()
1023 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1026 edge = list_entry(list.next, struct backref_edge, list[UPPER]); in build_backref_tree()
1027 list_del_init(&edge->list[UPPER]); in build_backref_tree()
1028 upper = edge->node[UPPER]; in build_backref_tree()
1029 if (upper->detached) { in build_backref_tree()
1033 if (list_empty(&lower->upper)) in build_backref_tree()
1038 if (!RB_EMPTY_NODE(&upper->rb_node)) { in build_backref_tree()
1039 if (upper->lowest) { in build_backref_tree()
1040 list_del_init(&upper->lower); in build_backref_tree()
1041 upper->lowest = 0; in build_backref_tree()
1044 list_add_tail(&edge->list[UPPER], &upper->lower); in build_backref_tree()
1048 if (!upper->checked) { in build_backref_tree()
1057 if (cowonly != upper->cowonly) { in build_backref_tree()
1064 rb_node = tree_insert(&cache->rb_root, upper->bytenr, in build_backref_tree()
1065 &upper->rb_node); in build_backref_tree()
1068 upper->bytenr); in build_backref_tree()
1071 list_add_tail(&edge->list[UPPER], &upper->lower); in build_backref_tree()
1073 list_for_each_entry(edge, &upper->upper, list[LOWER]) in build_backref_tree()
1074 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1078 * are deleted from the cache. backref nodes for upper level in build_backref_tree()
1083 upper = list_entry(useless.next, struct backref_node, list); in build_backref_tree()
1084 list_del_init(&upper->list); in build_backref_tree()
1085 ASSERT(list_empty(&upper->upper)); in build_backref_tree()
1086 if (upper == node) in build_backref_tree()
1088 if (upper->lowest) { in build_backref_tree()
1089 list_del_init(&upper->lower); in build_backref_tree()
1090 upper->lowest = 0; in build_backref_tree()
1092 while (!list_empty(&upper->lower)) { in build_backref_tree()
1093 edge = list_entry(upper->lower.next, in build_backref_tree()
1094 struct backref_edge, list[UPPER]); in build_backref_tree()
1095 list_del(&edge->list[UPPER]); in build_backref_tree()
1100 if (list_empty(&lower->upper)) in build_backref_tree()
1103 __mark_block_processed(rc, upper); in build_backref_tree()
1104 if (upper->level > 0) { in build_backref_tree()
1105 list_add(&upper->list, &cache->detached); in build_backref_tree()
1106 upper->detached = 1; in build_backref_tree()
1108 rb_erase(&upper->rb_node, &cache->rb_root); in build_backref_tree()
1109 free_backref_node(cache, upper); in build_backref_tree()
1123 list[UPPER]); in build_backref_tree()
1124 list_del(&edge->list[UPPER]); in build_backref_tree()
1127 upper = edge->node[UPPER]; in build_backref_tree()
1131 * Lower is no longer linked to any upper backref nodes in build_backref_tree()
1134 if (list_empty(&lower->upper) && in build_backref_tree()
1138 if (!RB_EMPTY_NODE(&upper->rb_node)) in build_backref_tree()
1141 /* Add this guy's upper edges to the list to process */ in build_backref_tree()
1142 list_for_each_entry(edge, &upper->upper, list[LOWER]) in build_backref_tree()
1143 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1144 if (list_empty(&upper->upper)) in build_backref_tree()
1145 list_add(&upper->list, &useless); in build_backref_tree()
1218 list_for_each_entry(edge, &node->lower, list[UPPER]) { in clone_backref_node()
1223 new_edge->node[UPPER] = new_node; in clone_backref_node()
1225 list_add_tail(&new_edge->list[UPPER], in clone_backref_node()
1238 list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) { in clone_backref_node()
1240 &new_edge->node[LOWER]->upper); in clone_backref_node()
1247 struct backref_edge, list[UPPER]); in clone_backref_node()
1248 list_del(&new_edge->list[UPPER]); in clone_backref_node()
2606 next = edges[index]->node[UPPER]; in select_reloc_root()
2674 if (list_empty(&next->upper)) in calcu_metadata_size()
2677 edge = list_entry(next->upper.next, in calcu_metadata_size()
2680 next = edge->node[UPPER]; in calcu_metadata_size()
2729 * relocate a block tree, and then update pointers in upper level
2742 struct backref_node *upper; in do_relocation() local
2758 list_for_each_entry(edge, &node->upper, list[LOWER]) { in do_relocation()
2764 upper = edge->node[UPPER]; in do_relocation()
2765 root = select_reloc_root(trans, rc, upper, edges); in do_relocation()
2768 if (upper->eb && !upper->locked) { in do_relocation()
2770 ret = btrfs_bin_search(upper->eb, key, in do_relocation()
2771 upper->level, &slot); in do_relocation()
2777 bytenr = btrfs_node_blockptr(upper->eb, slot); in do_relocation()
2781 drop_node_buffer(upper); in do_relocation()
2784 if (!upper->eb) { in do_relocation()
2796 if (!upper->eb) { in do_relocation()
2797 upper->eb = path->nodes[upper->level]; in do_relocation()
2798 path->nodes[upper->level] = NULL; in do_relocation()
2800 BUG_ON(upper->eb != path->nodes[upper->level]); in do_relocation()
2803 upper->locked = 1; in do_relocation()
2804 path->locks[upper->level] = 0; in do_relocation()
2806 slot = path->slots[upper->level]; in do_relocation()
2809 ret = btrfs_bin_search(upper->eb, key, upper->level, in do_relocation()
2818 bytenr = btrfs_node_blockptr(upper->eb, slot); in do_relocation()
2822 "lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu", in do_relocation()
2824 upper->eb->start); in do_relocation()
2834 generation = btrfs_node_ptr_generation(upper->eb, slot); in do_relocation()
2835 btrfs_node_key_to_cpu(upper->eb, &first_key, slot); in do_relocation()
2837 upper->level - 1, &first_key); in do_relocation()
2850 ret = btrfs_cow_block(trans, root, eb, upper->eb, in do_relocation()
2860 btrfs_set_node_blockptr(upper->eb, slot, in do_relocation()
2862 btrfs_set_node_ptr_generation(upper->eb, slot, in do_relocation()
2864 btrfs_mark_buffer_dirty(upper->eb); in do_relocation()
2868 upper->eb->start); in do_relocation()
2871 btrfs_header_owner(upper->eb)); in do_relocation()
2875 ret = btrfs_drop_subtree(trans, root, eb, upper->eb); in do_relocation()
2879 if (!upper->pending) in do_relocation()
2880 drop_node_buffer(upper); in do_relocation()
2882 unlock_node_buffer(upper); in do_relocation()
2976 if (list_empty(&next->upper)) in update_processed_blocks()
2979 edge = list_entry(next->upper.next, in update_processed_blocks()
2982 next = edge->node[UPPER]; in update_processed_blocks()