Lines Matching full:upper
44 /* list of upper level blocks reference this block */
45 struct list_head upper; member
65 * 1 if corresponding block has been cowed but some upper
85 #define UPPER 1 macro
95 * pointers in upper level blocks may not reflect the
242 INIT_LIST_HEAD(&node->upper); in alloc_backref_node()
343 while (!list_empty(&node->upper)) { in walk_up_backref()
344 edge = list_entry(node->upper.next, in walk_up_backref()
347 node = edge->node[UPPER]; in walk_up_backref()
367 if (list_is_last(&edge->list[LOWER], &lower->upper)) { in walk_down_backref()
375 return edge->node[UPPER]; in walk_down_backref()
401 BUG_ON(!list_empty(&node->upper)); in drop_backref_node()
417 struct backref_node *upper; in remove_backref_node() local
424 while (!list_empty(&node->upper)) { in remove_backref_node()
425 edge = list_entry(node->upper.next, struct backref_edge, in remove_backref_node()
427 upper = edge->node[UPPER]; in remove_backref_node()
429 list_del(&edge->list[UPPER]); in remove_backref_node()
432 if (RB_EMPTY_NODE(&upper->rb_node)) { in remove_backref_node()
433 BUG_ON(!list_empty(&node->upper)); in remove_backref_node()
435 node = upper; in remove_backref_node()
443 if (list_empty(&upper->lower)) { in remove_backref_node()
444 list_add_tail(&upper->lower, &cache->leaves); in remove_backref_node()
445 upper->lowest = 1; in remove_backref_node()
637 * to find upper level blocks that reference the block, and then check
638 * backrefs of these upper level blocks recursively. the recursion stop
642 * for all upper level blocks that directly/indirectly reference the
656 struct backref_node *upper; in build_backref_tree() local
712 if (!list_empty(&cur->upper)) { in build_backref_tree()
717 ASSERT(list_is_singular(&cur->upper)); in build_backref_tree()
718 edge = list_entry(cur->upper.next, struct backref_edge, in build_backref_tree()
720 ASSERT(list_empty(&edge->list[UPPER])); in build_backref_tree()
721 exist = edge->node[UPPER]; in build_backref_tree()
723 * add the upper level block to pending list if we need in build_backref_tree()
727 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
809 upper = alloc_backref_node(cache); in build_backref_tree()
810 if (!upper) { in build_backref_tree()
815 upper->bytenr = key.offset; in build_backref_tree()
816 upper->level = cur->level + 1; in build_backref_tree()
818 * backrefs for the upper level block isn't in build_backref_tree()
821 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
823 upper = rb_entry(rb_node, struct backref_node, in build_backref_tree()
825 ASSERT(upper->checked); in build_backref_tree()
826 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
828 list_add_tail(&edge->list[LOWER], &cur->upper); in build_backref_tree()
830 edge->node[UPPER] = upper; in build_backref_tree()
867 * searching the tree to find upper level blocks in build_backref_tree()
915 upper = alloc_backref_node(cache); in build_backref_tree()
916 if (!upper) { in build_backref_tree()
921 upper->bytenr = eb->start; in build_backref_tree()
922 upper->owner = btrfs_header_owner(eb); in build_backref_tree()
923 upper->level = lower->level + 1; in build_backref_tree()
926 upper->cowonly = 1; in build_backref_tree()
933 upper->checked = 0; in build_backref_tree()
935 upper->checked = 1; in build_backref_tree()
943 if (!upper->checked && need_check) { in build_backref_tree()
945 list_add_tail(&edge->list[UPPER], in build_backref_tree()
948 if (upper->checked) in build_backref_tree()
950 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
953 upper = rb_entry(rb_node, struct backref_node, in build_backref_tree()
955 ASSERT(upper->checked); in build_backref_tree()
956 INIT_LIST_HEAD(&edge->list[UPPER]); in build_backref_tree()
957 if (!upper->owner) in build_backref_tree()
958 upper->owner = btrfs_header_owner(eb); in build_backref_tree()
960 list_add_tail(&edge->list[LOWER], &lower->upper); in build_backref_tree()
962 edge->node[UPPER] = upper; in build_backref_tree()
966 lower = upper; in build_backref_tree()
967 upper = NULL; in build_backref_tree()
989 edge = list_entry(list.next, struct backref_edge, list[UPPER]); in build_backref_tree()
990 list_del_init(&edge->list[UPPER]); in build_backref_tree()
991 cur = edge->node[UPPER]; in build_backref_tree()
1009 list_for_each_entry(edge, &node->upper, list[LOWER]) in build_backref_tree()
1010 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1013 edge = list_entry(list.next, struct backref_edge, list[UPPER]); in build_backref_tree()
1014 list_del_init(&edge->list[UPPER]); in build_backref_tree()
1015 upper = edge->node[UPPER]; in build_backref_tree()
1016 if (upper->detached) { in build_backref_tree()
1020 if (list_empty(&lower->upper)) in build_backref_tree()
1025 if (!RB_EMPTY_NODE(&upper->rb_node)) { in build_backref_tree()
1026 if (upper->lowest) { in build_backref_tree()
1027 list_del_init(&upper->lower); in build_backref_tree()
1028 upper->lowest = 0; in build_backref_tree()
1031 list_add_tail(&edge->list[UPPER], &upper->lower); in build_backref_tree()
1035 if (!upper->checked) { in build_backref_tree()
1044 if (cowonly != upper->cowonly) { in build_backref_tree()
1051 rb_node = tree_insert(&cache->rb_root, upper->bytenr, in build_backref_tree()
1052 &upper->rb_node); in build_backref_tree()
1055 upper->bytenr); in build_backref_tree()
1058 list_add_tail(&edge->list[UPPER], &upper->lower); in build_backref_tree()
1060 list_for_each_entry(edge, &upper->upper, list[LOWER]) in build_backref_tree()
1061 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1065 * are deleted from the cache. backref nodes for upper level in build_backref_tree()
1070 upper = list_entry(useless.next, struct backref_node, list); in build_backref_tree()
1071 list_del_init(&upper->list); in build_backref_tree()
1072 ASSERT(list_empty(&upper->upper)); in build_backref_tree()
1073 if (upper == node) in build_backref_tree()
1075 if (upper->lowest) { in build_backref_tree()
1076 list_del_init(&upper->lower); in build_backref_tree()
1077 upper->lowest = 0; in build_backref_tree()
1079 while (!list_empty(&upper->lower)) { in build_backref_tree()
1080 edge = list_entry(upper->lower.next, in build_backref_tree()
1081 struct backref_edge, list[UPPER]); in build_backref_tree()
1082 list_del(&edge->list[UPPER]); in build_backref_tree()
1087 if (list_empty(&lower->upper)) in build_backref_tree()
1090 __mark_block_processed(rc, upper); in build_backref_tree()
1091 if (upper->level > 0) { in build_backref_tree()
1092 list_add(&upper->list, &cache->detached); in build_backref_tree()
1093 upper->detached = 1; in build_backref_tree()
1095 rb_erase(&upper->rb_node, &cache->rb_root); in build_backref_tree()
1096 free_backref_node(cache, upper); in build_backref_tree()
1110 list[UPPER]); in build_backref_tree()
1111 list_del(&edge->list[UPPER]); in build_backref_tree()
1114 upper = edge->node[UPPER]; in build_backref_tree()
1118 * Lower is no longer linked to any upper backref nodes in build_backref_tree()
1121 if (list_empty(&lower->upper) && in build_backref_tree()
1125 if (!RB_EMPTY_NODE(&upper->rb_node)) in build_backref_tree()
1128 /* Add this guy's upper edges to the list to process */ in build_backref_tree()
1129 list_for_each_entry(edge, &upper->upper, list[LOWER]) in build_backref_tree()
1130 list_add_tail(&edge->list[UPPER], &list); in build_backref_tree()
1131 if (list_empty(&upper->upper)) in build_backref_tree()
1132 list_add(&upper->list, &useless); in build_backref_tree()
1205 list_for_each_entry(edge, &node->lower, list[UPPER]) { in clone_backref_node()
1210 new_edge->node[UPPER] = new_node; in clone_backref_node()
1212 list_add_tail(&new_edge->list[UPPER], in clone_backref_node()
1225 list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) { in clone_backref_node()
1227 &new_edge->node[LOWER]->upper); in clone_backref_node()
1234 struct backref_edge, list[UPPER]); in clone_backref_node()
1235 list_del(&new_edge->list[UPPER]); in clone_backref_node()
2535 next = edges[index]->node[UPPER]; in select_reloc_root()
2603 if (list_empty(&next->upper)) in calcu_metadata_size()
2606 edge = list_entry(next->upper.next, in calcu_metadata_size()
2609 next = edge->node[UPPER]; in calcu_metadata_size()
2658 * relocate a block tree, and then update pointers in upper level
2671 struct backref_node *upper; in do_relocation() local
2687 list_for_each_entry(edge, &node->upper, list[LOWER]) { in do_relocation()
2692 upper = edge->node[UPPER]; in do_relocation()
2693 root = select_reloc_root(trans, rc, upper, edges); in do_relocation()
2696 if (upper->eb && !upper->locked) { in do_relocation()
2698 ret = btrfs_bin_search(upper->eb, key, in do_relocation()
2699 upper->level, &slot); in do_relocation()
2701 bytenr = btrfs_node_blockptr(upper->eb, slot); in do_relocation()
2705 drop_node_buffer(upper); in do_relocation()
2708 if (!upper->eb) { in do_relocation()
2720 if (!upper->eb) { in do_relocation()
2721 upper->eb = path->nodes[upper->level]; in do_relocation()
2722 path->nodes[upper->level] = NULL; in do_relocation()
2724 BUG_ON(upper->eb != path->nodes[upper->level]); in do_relocation()
2727 upper->locked = 1; in do_relocation()
2728 path->locks[upper->level] = 0; in do_relocation()
2730 slot = path->slots[upper->level]; in do_relocation()
2733 ret = btrfs_bin_search(upper->eb, key, upper->level, in do_relocation()
2738 bytenr = btrfs_node_blockptr(upper->eb, slot); in do_relocation()
2742 "lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu", in do_relocation()
2744 upper->eb->start); in do_relocation()
2754 generation = btrfs_node_ptr_generation(upper->eb, slot); in do_relocation()
2755 btrfs_node_key_to_cpu(upper->eb, &first_key, slot); in do_relocation()
2757 upper->level - 1, &first_key); in do_relocation()
2770 ret = btrfs_cow_block(trans, root, eb, upper->eb, in do_relocation()
2780 btrfs_set_node_blockptr(upper->eb, slot, in do_relocation()
2782 btrfs_set_node_ptr_generation(upper->eb, slot, in do_relocation()
2784 btrfs_mark_buffer_dirty(upper->eb); in do_relocation()
2788 upper->eb->start, in do_relocation()
2789 btrfs_header_owner(upper->eb), in do_relocation()
2793 ret = btrfs_drop_subtree(trans, root, eb, upper->eb); in do_relocation()
2797 if (!upper->pending) in do_relocation()
2798 drop_node_buffer(upper); in do_relocation()
2800 unlock_node_buffer(upper); in do_relocation()
2894 if (list_empty(&next->upper)) in update_processed_blocks()
2897 edge = list_entry(next->upper.next, in update_processed_blocks()
2900 next = edge->node[UPPER]; in update_processed_blocks()