diff options
Diffstat (limited to 'btrfsck.c')
-rw-r--r-- | btrfsck.c | 725 |
1 files changed, 556 insertions, 169 deletions
@@ -32,19 +32,38 @@ static u64 bytes_used = 0; static u64 total_csum_bytes = 0; static u64 total_btree_bytes = 0; +static u64 total_fs_tree_bytes = 0; static u64 btree_space_waste = 0; static u64 data_bytes_allocated = 0; static u64 data_bytes_referenced = 0; +int found_old_backref = 0; struct extent_backref { struct list_head list; - u64 parent; - u64 root; - u64 generation; + unsigned int is_data:1; + unsigned int found_extent_tree:1; + unsigned int full_backref:1; + unsigned int found_ref:1; +}; + +struct data_backref { + struct extent_backref node; + union { + u64 parent; + u64 root; + }; u64 owner; + u64 offset; u32 num_refs; u32 found_ref; - int found_extent_tree; +}; + +struct tree_backref { + struct extent_backref node; + union { + u64 parent; + u64 root; + }; }; struct extent_record { @@ -53,9 +72,11 @@ struct extent_record { struct btrfs_disk_key parent_key; u64 start; u64 nr; - u32 refs; - u32 extent_item_refs; - int checked; + u64 refs; + u64 extent_item_refs; + unsigned int content_checked:1; + unsigned int owner_ref_checked:1; + unsigned int is_root:1; }; struct inode_backref { @@ -84,6 +105,7 @@ struct inode_backref { struct inode_record { struct list_head backrefs; unsigned int checked:1; + unsigned int merging:1; unsigned int found_inode_item:1; unsigned int found_dir_item:1; unsigned int found_file_extent:1; @@ -120,6 +142,7 @@ struct inode_record { #define I_ERR_FILE_NBYTES_WRONG (1 << 10) // 400 #define I_ERR_ODD_CSUM_ITEM (1 << 11) #define I_ERR_SOME_CSUM_MISSING (1 << 12) +#define I_ERR_LINK_COUNT_WRONG (1 << 13) struct ptr_node { struct cache_extent cache; @@ -258,7 +281,7 @@ static void maybe_free_inode_rec(struct cache_tree *inode_cache, } } - if (!rec->checked) + if (!rec->checked || rec->merging) return; if (S_ISDIR(rec->imode)) { @@ -425,6 +448,7 @@ static int merge_inode_recs(struct inode_record *src, struct inode_record *dst, struct inode_backref *backref; struct cache_tree *dst_cache = &dst_node->inode_cache; + dst->merging = 1; list_for_each_entry(backref, &src->backrefs, list) { if (backref->found_dir_index) { add_inode_backref(dst_cache, dst->ino, backref->dir, @@ -492,6 +516,7 @@ static int merge_inode_recs(struct inode_record *src, struct inode_record *dst, if (dst_node->current == dst) dst_node->current = NULL; } + dst->merging = 0; maybe_free_inode_rec(dst_cache, dst); return 0; } @@ -1001,13 +1026,13 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path, struct extent_buffer *cur; u32 blocksize; int ret; - u32 refs; + u64 refs; WARN_ON(*level < 0); WARN_ON(*level >= BTRFS_MAX_LEVEL); - ret = btrfs_lookup_extent_ref(NULL, root, - path->nodes[*level]->start, - path->nodes[*level]->len, &refs); + ret = btrfs_lookup_extent_info(NULL, root, + path->nodes[*level]->start, + path->nodes[*level]->len, &refs, NULL); BUG_ON(ret); if (refs > 1) { ret = enter_shared_node(root, path->nodes[*level]->start, @@ -1033,8 +1058,8 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path, bytenr = btrfs_node_blockptr(cur, path->slots[*level]); ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]); blocksize = btrfs_level_size(root, *level - 1); - ret = btrfs_lookup_extent_ref(NULL, root, bytenr, blocksize, - &refs); + ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize, + &refs, NULL); BUG_ON(ret); if (refs > 1) { @@ -1072,7 +1097,7 @@ static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path, for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) { leaf = path->nodes[i]; - if (path->slots[i] < btrfs_header_nritems(leaf) - 1) { + if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) { path->slots[i]++; *level = i; return 0; @@ -1161,6 +1186,8 @@ static int check_inode_recs(struct btrfs_root *root, error++; if (!rec->found_inode_item) rec->errors |= I_ERR_NO_INODE_ITEM; + if (rec->found_link != rec->nlink) + rec->errors |= I_ERR_LINK_COUNT_WRONG; fprintf(stderr, "root %llu inode %llu errors %x\n", (unsigned long long) root->root_key.objectid, (unsigned long long) rec->ino, rec->errors); @@ -1204,7 +1231,8 @@ static int check_fs_root(struct btrfs_root *root, wc->active_node = level; wc->root_level = level; - if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) { + if (btrfs_root_refs(root_item) > 0 || + btrfs_disk_key_objectid(&root_item->drop_progress) == 0) { path.nodes[level] = root->node; extent_buffer_get(root->node); path.slots[level] = 0; @@ -1289,7 +1317,8 @@ static int check_fs_roots(struct btrfs_root *root) btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.type == BTRFS_ROOT_ITEM_KEY && fs_root_objectid(key.objectid)) { - tmp_root = btrfs_read_fs_root(root->fs_info, &key); + tmp_root = btrfs_read_fs_root_no_cache(root->fs_info, + &key); ret = check_fs_root(tmp_root, &wc); if (ret) err = 1; @@ -1389,7 +1418,9 @@ static int all_backpointers_checked(struct extent_record *rec, int print_errs) { struct list_head *cur = rec->backrefs.next; struct extent_backref *back; - u32 found = 0; + struct tree_backref *tback; + struct data_backref *dback; + u64 found = 0; int err = 0; while(cur != &rec->backrefs) { @@ -1399,50 +1430,77 @@ static int all_backpointers_checked(struct extent_record *rec, int print_errs) err = 1; if (!print_errs) goto out; - fprintf(stderr, "Backref %llu parent %llu" - " [%llu %llu %llu %lu]" - " not found in extent tree\n", - (unsigned long long)rec->start, - (unsigned long long)back->parent, - (unsigned long long)back->root, - (unsigned long long)back->generation, - (unsigned long long)back->owner, - (unsigned long)back->num_refs); + if (back->is_data) { + dback = (struct data_backref *)back; + fprintf(stderr, "Backref %llu %s %llu" + " owner %llu offset %llu num_refs %lu" + " not found in extent tree\n", + (unsigned long long)rec->start, + back->full_backref ? + "parent" : "root", + back->full_backref ? + (unsigned long long)dback->parent: + (unsigned long long)dback->root, + (unsigned long long)dback->owner, + (unsigned long long)dback->offset, + (unsigned long)dback->num_refs); + } else { + tback = (struct tree_backref *)back; + fprintf(stderr, "Backref %llu parent %llu" + " root %llu not found in extent tree\n", + (unsigned long long)rec->start, + (unsigned long long)tback->parent, + (unsigned long long)tback->root); + } } - if (!back->found_ref) { + if (!back->is_data && !back->found_ref) { err = 1; if (!print_errs) goto out; - fprintf(stderr, "Backref %llu parent %llu" - " [%llu %llu %llu %lu]" - " not referenced\n", + tback = (struct tree_backref *)back; + fprintf(stderr, "Backref %llu %s %llu not referenced\n", (unsigned long long)rec->start, - (unsigned long long)back->parent, - (unsigned long long)back->root, - (unsigned long long)back->generation, - (unsigned long long)back->owner, - (unsigned long)back->num_refs); + back->full_backref ? "parent" : "root", + back->full_backref ? + (unsigned long long)tback->parent : + (unsigned long long)tback->root); } - if (back->found_ref != back->num_refs) { - err = 1; - if (!print_errs) - goto out; - fprintf(stderr, "Incorrect local backref count " - "on %llu parent %llu found %u wanted %u\n", - (unsigned long long)rec->start, - (unsigned long long)back->parent, - back->found_ref, back->num_refs); + if (back->is_data) { + dback = (struct data_backref *)back; + if (dback->found_ref != dback->num_refs) { + err = 1; + if (!print_errs) + goto out; + fprintf(stderr, "Incorrect local backref count" + " on %llu %s %llu owner %llu" + " offset %llu found %u wanted %u\n", + (unsigned long long)rec->start, + back->full_backref ? + "parent" : "root", + back->full_backref ? + (unsigned long long)dback->parent: + (unsigned long long)dback->root, + (unsigned long long)dback->owner, + (unsigned long long)dback->offset, + dback->found_ref, dback->num_refs); + } + } + if (!back->is_data) { + found += 1; + } else { + dback = (struct data_backref *)back; + found += dback->found_ref; } - found += back->found_ref; } if (found != rec->refs) { err = 1; if (!print_errs) goto out; fprintf(stderr, "Incorrect global backref count " - "on %llu found %u wanted %u\n", + "on %llu found %llu wanted %llu\n", (unsigned long long)rec->start, - found, rec->refs); + (unsigned long long)found, + (unsigned long long)rec->refs); } out: return err; @@ -1464,8 +1522,9 @@ static int free_all_extent_backrefs(struct extent_record *rec) static int maybe_free_extent_rec(struct cache_tree *extent_cache, struct extent_record *rec) { - if (rec->checked && rec->extent_item_refs == rec->refs && - rec->refs > 0 && !all_backpointers_checked(rec, 0)) { + if (rec->content_checked && rec->owner_ref_checked && + rec->extent_item_refs == rec->refs && rec->refs > 0 && + !all_backpointers_checked(rec, 0)) { remove_cache_extent(extent_cache, &rec->cache); free_all_extent_backrefs(rec); free(rec); @@ -1473,9 +1532,61 @@ static int maybe_free_extent_rec(struct cache_tree *extent_cache, return 0; } +static int check_owner_ref(struct btrfs_root *root, + struct extent_record *rec, + struct extent_buffer *buf) +{ + struct extent_backref *node; + struct tree_backref *back; + struct btrfs_root *ref_root; + struct btrfs_key key; + struct btrfs_path path; + int ret; + int level; + int found = 0; + + list_for_each_entry(node, &rec->backrefs, list) { + if (node->is_data) + continue; + if (!node->found_ref) + continue; + if (node->full_backref) + continue; + back = (struct tree_backref *)node; + if (btrfs_header_owner(buf) == back->root) + return 0; + } + BUG_ON(rec->is_root); + + /* try to find the block by search corresponding fs tree */ + key.objectid = btrfs_header_owner(buf); + key.type = BTRFS_ROOT_ITEM_KEY; + key.offset = (u64)-1; + + ref_root = btrfs_read_fs_root(root->fs_info, &key); + BUG_ON(IS_ERR(ref_root)); + + level = btrfs_header_level(buf); + if (level == 0) + btrfs_item_key_to_cpu(buf, &key, 0); + else + btrfs_node_key_to_cpu(buf, &key, 0); + + btrfs_init_path(&path); + path.lowest_level = level + 1; + ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0); + + if (buf->start == btrfs_node_blockptr(path.nodes[level + 1], + path.slots[level + 1])) + rec->owner_ref_checked = 1; + + btrfs_release_path(ref_root, &path); + return found ? 0 : 1; +} + static int check_block(struct btrfs_root *root, struct cache_tree *extent_cache, - struct extent_buffer *buf) + struct extent_buffer *buf, u64 flags) { struct extent_record *rec; struct cache_extent *cache; @@ -1490,50 +1601,126 @@ static int check_block(struct btrfs_root *root, } else { ret = check_node(root, &rec->parent_key, buf); } - rec->checked = 1; + if (ret) { + fprintf(stderr, "bad block %llu\n", + (unsigned long long)buf->start); + } else { + rec->content_checked = 1; + if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) + rec->owner_ref_checked = 1; + else { + ret = check_owner_ref(root, rec, buf); + if (!ret) + rec->owner_ref_checked = 1; + } + } if (!ret) maybe_free_extent_rec(extent_cache, rec); return ret; } -static struct extent_backref *find_extent_backref(struct extent_record *rec, - u64 parent, u64 root, u64 gen) +static struct tree_backref *find_tree_backref(struct extent_record *rec, + u64 parent, u64 root) { struct list_head *cur = rec->backrefs.next; - struct extent_backref *back; + struct extent_backref *node; + struct tree_backref *back; while(cur != &rec->backrefs) { - back = list_entry(cur, struct extent_backref, list); + node = list_entry(cur, struct extent_backref, list); cur = cur->next; - if (back->parent != parent) + if (node->is_data) continue; - if (back->root != root || back->generation != gen) + back = (struct tree_backref *)node; + if (parent > 0) { + if (!node->full_backref) + continue; + if (parent == back->parent) + return back; + } else { + if (node->full_backref) + continue; + if (back->root == root) + return back; + } + } + return NULL; +} + +static struct tree_backref *alloc_tree_backref(struct extent_record *rec, + u64 parent, u64 root) +{ + struct tree_backref *ref = malloc(sizeof(*ref)); + memset(&ref->node, 0, sizeof(ref->node)); + if (parent > 0) { + ref->parent = parent; + ref->node.full_backref = 1; + } else { + ref->root = root; + ref->node.full_backref = 0; + } + list_add_tail(&ref->node.list, &rec->backrefs); + return ref; +} + +static struct data_backref *find_data_backref(struct extent_record *rec, + u64 parent, u64 root, + u64 owner, u64 offset) +{ + struct list_head *cur = rec->backrefs.next; + struct extent_backref *node; + struct data_backref *back; + + while(cur != &rec->backrefs) { + node = list_entry(cur, struct extent_backref, list); + cur = cur->next; + if (!node->is_data) continue; - return back; + back = (struct data_backref *)node; + if (parent > 0) { + if (!node->full_backref) + continue; + if (parent == back->parent) + return back; + } else { + if (node->full_backref) + continue; + if (back->root == root && back->owner == owner && + back->offset == offset) + return back; + } } return NULL; } -static struct extent_backref *alloc_extent_backref(struct extent_record *rec, - u64 parent, u64 root, - u64 gen, u64 owner) +static struct data_backref *alloc_data_backref(struct extent_record *rec, + u64 parent, u64 root, + u64 owner, u64 offset) { - struct extent_backref *ref = malloc(sizeof(*ref)); - ref->parent = parent; - ref->root = root; - ref->generation = gen; - ref->owner = owner; - ref->num_refs = 0; - ref->found_extent_tree = 0; + struct data_backref *ref = malloc(sizeof(*ref)); + memset(&ref->node, 0, sizeof(ref->node)); + ref->node.is_data = 1; + if (parent > 0) { + ref->parent = parent; + ref->owner = 0; + ref->offset = 0; + ref->node.full_backref = 1; + } else { + ref->root = root; + ref->owner = owner; + ref->offset = offset; + ref->node.full_backref = 0; + } ref->found_ref = 0; - list_add_tail(&ref->list, &rec->backrefs); + ref->num_refs = 0; + list_add_tail(&ref->node.list, &rec->backrefs); return ref; } static int add_extent_rec(struct cache_tree *extent_cache, - struct btrfs_disk_key *parent_key, - u64 ref, u64 start, u64 nr, - u32 extent_item_refs, int inc_ref, int set_checked) + struct btrfs_key *parent_key, + u64 start, u64 nr, u64 extent_item_refs, + int is_root, int inc_ref, int set_checked) { struct extent_record *rec; struct cache_extent *cache; @@ -1556,31 +1743,39 @@ static int add_extent_rec(struct cache_tree *extent_cache, if (extent_item_refs) { if (rec->extent_item_refs) { fprintf(stderr, "block %llu rec " - "extent_item_refs %u, passed %u\n", + "extent_item_refs %llu, passed %llu\n", (unsigned long long)start, - rec->extent_item_refs, - extent_item_refs); + (unsigned long long) + rec->extent_item_refs, + (unsigned long long)extent_item_refs); } rec->extent_item_refs = extent_item_refs; } - if (set_checked) - rec->checked = 1; + if (is_root) + rec->is_root = 1; + if (set_checked) { + rec->content_checked = 1; + rec->owner_ref_checked = 1; + } if (parent_key) - memcpy(&rec->parent_key, parent_key, - sizeof(*parent_key)); + btrfs_cpu_key_to_disk(&rec->parent_key, parent_key); maybe_free_extent_rec(extent_cache, rec); return ret; } rec = malloc(sizeof(*rec)); - if (start == 0) - extent_item_refs = 0; rec->start = start; rec->nr = nr; - rec->checked = 0; + rec->content_checked = 0; + rec->owner_ref_checked = 0; INIT_LIST_HEAD(&rec->backrefs); + if (is_root) + rec->is_root = 1; + else + rec->is_root = 0; + if (inc_ref) rec->refs = 1; else @@ -1592,7 +1787,7 @@ static int add_extent_rec(struct cache_tree *extent_cache, rec->extent_item_refs = 0; if (parent_key) - memcpy(&rec->parent_key, parent_key, sizeof(*parent_key)); + btrfs_cpu_key_to_disk(&rec->parent_key, parent_key); else memset(&rec->parent_key, 0, sizeof(*parent_key)); @@ -1601,22 +1796,23 @@ static int add_extent_rec(struct cache_tree *extent_cache, ret = insert_existing_cache_extent(extent_cache, &rec->cache); BUG_ON(ret); bytes_used += nr; - if (set_checked) - rec->checked = 1; + if (set_checked) { + rec->content_checked = 1; + rec->owner_ref_checked = 1; + } return ret; } -static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr, - u64 parent, u64 root, u64 gen, u64 owner, - u32 num_refs, int found_ref) +static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr, + u64 parent, u64 root, int found_ref) { struct extent_record *rec; - struct extent_backref *back; + struct tree_backref *back; struct cache_extent *cache; cache = find_cache_extent(extent_cache, bytenr, 1); if (!cache) { - add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0); + add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0); cache = find_cache_extent(extent_cache, bytenr, 1); if (!cache) abort(); @@ -1626,39 +1822,75 @@ static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr, if (rec->start != bytenr) { abort(); } - back = find_extent_backref(rec, parent, root, gen); + + back = find_tree_backref(rec, parent, root); if (!back) - back = alloc_extent_backref(rec, parent, root, gen, owner); + back = alloc_tree_backref(rec, parent, root); if (found_ref) { - if (back->found_ref > 0 && - back->owner < BTRFS_FIRST_FREE_OBJECTID) { + if (back->node.found_ref) { fprintf(stderr, "Extent back ref already exists " - "for %llu parent %llu root %llu gen %llu " - "owner %llu num_refs %lu\n", + "for %llu parent %llu root %llu \n", + (unsigned long long)bytenr, (unsigned long long)parent, + (unsigned long long)root); + } + back->node.found_ref = 1; + } else { + if (back->node.found_extent_tree) { + fprintf(stderr, "Extent back ref already exists " + "for %llu parent %llu root %llu \n", (unsigned long long)bytenr, - (unsigned long long)root, - (unsigned long long)gen, - (unsigned long long)owner, - (unsigned long)num_refs); + (unsigned long long)parent, + (unsigned long long)root); } + back->node.found_extent_tree = 1; + } + return 0; +} + +static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr, + u64 parent, u64 root, u64 owner, u64 offset, + u32 num_refs, int found_ref) +{ + struct extent_record *rec; + struct data_backref *back; + struct cache_extent *cache; + + cache = find_cache_extent(extent_cache, bytenr, 1); + if (!cache) { + add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0); + cache = find_cache_extent(extent_cache, bytenr, 1); + if (!cache) + abort(); + } + + rec = container_of(cache, struct extent_record, cache); + if (rec->start != bytenr) { + abort(); + } + back = find_data_backref(rec, parent, root, owner, offset); + if (!back) + back = alloc_data_backref(rec, parent, root, owner, offset); + + if (found_ref) { BUG_ON(num_refs != 1); + back->node.found_ref = 1; back->found_ref += 1; } else { - if (back->found_extent_tree) { + if (back->node.found_extent_tree) { fprintf(stderr, "Extent back ref already exists " - "for %llu parent %llu root %llu gen %llu " - "owner %llu num_refs %lu\n", - (unsigned long long)parent, + "for %llu parent %llu root %llu" + "owner %llu offset %llu num_refs %lu\n", (unsigned long long)bytenr, + (unsigned long long)parent, (unsigned long long)root, - (unsigned long long)gen, (unsigned long long)owner, + (unsigned long long)offset, (unsigned long)num_refs); } back->num_refs = num_refs; - back->found_extent_tree = 1; + back->node.found_extent_tree = 1; } return 0; } @@ -1674,6 +1906,7 @@ static int add_pending(struct cache_tree *pending, insert_cache_extent(pending, bytenr, size); return 0; } + static int pick_next_pending(struct cache_tree *pending, struct cache_tree *reada, struct cache_tree *nodes, @@ -1742,6 +1975,106 @@ static int pick_next_pending(struct cache_tree *pending, return ret; } +#ifdef BTRFS_COMPAT_EXTENT_TREE_V0 +static int process_extent_ref_v0(struct cache_tree *extent_cache, + struct extent_buffer *leaf, int slot) +{ + struct btrfs_extent_ref_v0 *ref0; + struct btrfs_key key; + + btrfs_item_key_to_cpu(leaf, &key, slot); + ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0); + if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) { + add_tree_backref(extent_cache, key.objectid, key.offset, + 0, 0); + } else { + add_data_backref(extent_cache, key.objectid, key.offset, 0, + 0, 0, btrfs_ref_count_v0(leaf, ref0), 0); + } + return 0; +} +#endif + +static int process_extent_item(struct cache_tree *extent_cache, + struct extent_buffer *eb, int slot) +{ + struct btrfs_extent_item *ei; + struct btrfs_extent_inline_ref *iref; + struct btrfs_extent_data_ref *dref; + struct btrfs_shared_data_ref *sref; + struct btrfs_key key; + unsigned long end; + unsigned long ptr; + int type; + u32 item_size = btrfs_item_size_nr(eb, slot); + u64 refs = 0; + u64 offset; + + btrfs_item_key_to_cpu(eb, &key, slot); + + if (item_size < sizeof(*ei)) { +#ifdef BTRFS_COMPAT_EXTENT_TREE_V0 + struct btrfs_extent_item_v0 *ei0; + BUG_ON(item_size != sizeof(*ei0)); + ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0); + refs = btrfs_extent_refs_v0(eb, ei0); +#else + BUG(); +#endif + return add_extent_rec(extent_cache, NULL, key.objectid, + key.offset, refs, 0, 0, 0); + } + + ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item); + refs = btrfs_extent_refs(eb, ei); + + add_extent_rec(extent_cache, NULL, key.objectid, key.offset, + refs, 0, 0, 0); + + ptr = (unsigned long)(ei + 1); + if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK) + ptr += sizeof(struct btrfs_tree_block_info); + + end = (unsigned long)ei + item_size; + while (ptr < end) { + iref = (struct btrfs_extent_inline_ref *)ptr; + type = btrfs_extent_inline_ref_type(eb, iref); + offset = btrfs_extent_inline_ref_offset(eb, iref); + switch (type) { + case BTRFS_TREE_BLOCK_REF_KEY: + add_tree_backref(extent_cache, key.objectid, + 0, offset, 0); + break; + case BTRFS_SHARED_BLOCK_REF_KEY: + add_tree_backref(extent_cache, key.objectid, + offset, 0, 0); + break; + case BTRFS_EXTENT_DATA_REF_KEY: + dref = (struct btrfs_extent_data_ref *)(&iref->offset); + add_data_backref(extent_cache, key.objectid, 0, + btrfs_extent_data_ref_root(eb, dref), + btrfs_extent_data_ref_objectid(eb, + dref), + btrfs_extent_data_ref_offset(eb, dref), + btrfs_extent_data_ref_count(eb, dref), + 0); + break; + case BTRFS_SHARED_DATA_REF_KEY: + sref = (struct btrfs_shared_data_ref *)(iref + 1); + add_data_backref(extent_cache, key.objectid, offset, + 0, 0, 0, + btrfs_shared_data_ref_count(eb, sref), + 0); + break; + default: + BUG(); + } + ptr += btrfs_extent_inline_ref_size(type); + } + WARN_ON(ptr > end); + return 0; +} + static int run_next_block(struct btrfs_root *root, struct block_info *bits, int bits_nr, @@ -1755,11 +2088,13 @@ static int run_next_block(struct btrfs_root *root, struct extent_buffer *buf; u64 bytenr; u32 size; + u64 parent; + u64 owner; + u64 flags; int ret; int i; int nritems; - struct btrfs_extent_ref *ref; - struct btrfs_disk_key disk_key; + struct btrfs_key key; struct cache_extent *cache; int reada_bits; @@ -1801,38 +2136,34 @@ static int run_next_block(struct btrfs_root *root, /* fixme, get the real parent transid */ buf = read_tree_block(root, bytenr, size, 0); nritems = btrfs_header_nritems(buf); - ret = check_block(root, extent_cache, buf); - if (ret) { - fprintf(stderr, "bad block %llu\n", - (unsigned long long)bytenr); + + ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags); + + if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { + parent = bytenr; + owner = 0; + } else { + parent = 0; + owner = btrfs_header_owner(buf); } + + ret = check_block(root, extent_cache, buf, flags); + if (btrfs_is_leaf(buf)) { btree_space_waste += btrfs_leaf_free_space(root, buf); for (i = 0; i < nritems; i++) { struct btrfs_file_extent_item *fi; - btrfs_item_key(buf, &disk_key, i); - if (btrfs_disk_key_type(&disk_key) == - BTRFS_EXTENT_ITEM_KEY) { - struct btrfs_key found; - struct btrfs_extent_item *ei; - btrfs_disk_key_to_cpu(&found, &disk_key); - ei = btrfs_item_ptr(buf, i, - struct btrfs_extent_item); - add_extent_rec(extent_cache, NULL, 0, - found.objectid, - found.offset, - btrfs_extent_refs(buf, ei), - 0, 0); + btrfs_item_key_to_cpu(buf, &key, i); + if (key.type == BTRFS_EXTENT_ITEM_KEY) { + process_extent_item(extent_cache, buf, i); continue; } - if (btrfs_disk_key_type(&disk_key) == - BTRFS_EXTENT_CSUM_KEY) { + if (key.type == BTRFS_EXTENT_CSUM_KEY) { total_csum_bytes += btrfs_item_size_nr(buf, i); continue; } - if (btrfs_disk_key_type(&disk_key) == - BTRFS_BLOCK_GROUP_ITEM_KEY) { + if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { struct btrfs_block_group_item *bi; bi = btrfs_item_ptr(buf, i, struct btrfs_block_group_item); @@ -1845,21 +2176,50 @@ static int run_next_block(struct btrfs_root *root, #endif continue; } - if (btrfs_disk_key_type(&disk_key) == - BTRFS_EXTENT_REF_KEY) { + if (key.type == BTRFS_EXTENT_REF_V0_KEY) { +#ifdef BTRFS_COMPAT_EXTENT_TREE_V0 + process_extent_ref_v0(extent_cache, buf, i); +#else + BUG(); +#endif + continue; + } + + if (key.type == BTRFS_TREE_BLOCK_REF_KEY) { + add_tree_backref(extent_cache, key.objectid, 0, + key.offset, 0); + continue; + } + if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) { + add_tree_backref(extent_cache, key.objectid, + key.offset, 0, 0); + continue; + } + if (key.type == BTRFS_EXTENT_DATA_REF_KEY) { + struct btrfs_extent_data_ref *ref; ref = btrfs_item_ptr(buf, i, - struct btrfs_extent_ref); - add_extent_backref(extent_cache, - btrfs_disk_key_objectid(&disk_key), - btrfs_disk_key_offset(&disk_key), - btrfs_ref_root(buf, ref), - btrfs_ref_generation(buf, ref), - btrfs_ref_objectid(buf, ref), - btrfs_ref_num_refs(buf, ref), 0); + struct btrfs_extent_data_ref); + add_data_backref(extent_cache, + key.objectid, 0, + btrfs_extent_data_ref_root(buf, ref), + btrfs_extent_data_ref_objectid(buf, + ref), + btrfs_extent_data_ref_offset(buf, ref), + btrfs_extent_data_ref_count(buf, ref), + 0); continue; } - if (btrfs_disk_key_type(&disk_key) != - BTRFS_EXTENT_DATA_KEY) + if (key.type == BTRFS_SHARED_DATA_REF_KEY) { + struct btrfs_shared_data_ref *ref; + ref = btrfs_item_ptr(buf, i, + struct btrfs_shared_data_ref); + add_data_backref(extent_cache, + key.objectid, key.offset, 0, 0, 0, + btrfs_shared_data_ref_count(buf, ref), + 0); + continue; + } + if (key.type != BTRFS_EXTENT_DATA_KEY) continue; fi = btrfs_item_ptr(buf, i, struct btrfs_file_extent_item); @@ -1876,15 +2236,14 @@ static int run_next_block(struct btrfs_root *root, } data_bytes_referenced += btrfs_file_extent_num_bytes(buf, fi); - ret = add_extent_rec(extent_cache, NULL, bytenr, + ret = add_extent_rec(extent_cache, NULL, btrfs_file_extent_disk_bytenr(buf, fi), btrfs_file_extent_disk_num_bytes(buf, fi), - 0, 1, 1); - add_extent_backref(extent_cache, + 0, 0, 1, 1); + add_data_backref(extent_cache, btrfs_file_extent_disk_bytenr(buf, fi), - buf->start, btrfs_header_owner(buf), - btrfs_header_generation(buf), - btrfs_disk_key_objectid(&disk_key), 1, 1); + parent, owner, key.objectid, key.offset - + btrfs_file_extent_offset(buf, fi), 1, 1); BUG_ON(ret); } } else { @@ -1893,17 +2252,13 @@ static int run_next_block(struct btrfs_root *root, for (i = 0; i < nritems; i++) { u64 ptr = btrfs_node_blockptr(buf, i); u32 size = btrfs_level_size(root, level - 1); - btrfs_node_key(buf, &disk_key, i); - ret = add_extent_rec(extent_cache, - &disk_key, - bytenr, ptr, size, - 0, 1, 0); + btrfs_node_key_to_cpu(buf, &key, i); + ret = add_extent_rec(extent_cache, &key, + ptr, size, 0, 0, 1, 0); BUG_ON(ret); - add_extent_backref(extent_cache, ptr, - buf->start, btrfs_header_owner(buf), - btrfs_header_generation(buf), - level - 1, 1, 1); + add_tree_backref(extent_cache, ptr, parent, + owner, 1); if (level > 1) { add_pending(nodes, seen, ptr, size); @@ -1915,6 +2270,13 @@ static int run_next_block(struct btrfs_root *root, nritems) * sizeof(struct btrfs_key_ptr); } total_btree_bytes += buf->len; + if (fs_root_objectid(btrfs_header_owner(buf))) + total_fs_tree_bytes += buf->len; + if (!found_old_backref && + btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID && + btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV && + !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) + found_old_backref = 1; free_extent_buffer(buf); return 0; } @@ -1926,18 +2288,22 @@ static int add_root_to_pending(struct extent_buffer *buf, struct cache_tree *pending, struct cache_tree *seen, struct cache_tree *reada, - struct cache_tree *nodes, u64 root_objectid) + struct cache_tree *nodes, + struct btrfs_key *root_key) { if (btrfs_header_level(buf) > 0) add_pending(nodes, seen, buf->start, buf->len); else add_pending(pending, seen, buf->start, buf->len); - add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len, - 0, 1, 0); + add_extent_rec(extent_cache, NULL, buf->start, buf->len, + 0, 1, 1, 0); - add_extent_backref(extent_cache, buf->start, buf->start, - root_objectid, btrfs_header_generation(buf), - btrfs_header_level(buf), 1, 1); + if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID || + btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) + add_tree_backref(extent_cache, buf->start, buf->start, 0, 1); + else + add_tree_backref(extent_cache, buf->start, 0, + root_key->objectid, 1); return 0; } @@ -1957,9 +2323,9 @@ static int check_extent_refs(struct btrfs_root *root, fprintf(stderr, "ref mismatch on [%llu %llu] ", (unsigned long long)rec->start, (unsigned long long)rec->nr); - fprintf(stderr, "extent item %u, found %u\n", - rec->extent_item_refs, - rec->refs); + fprintf(stderr, "extent item %llu, found %llu\n", + (unsigned long long)rec->extent_item_refs, + (unsigned long long)rec->refs); err = 1; } if (all_backpointers_checked(rec, 1)) { @@ -1969,6 +2335,13 @@ static int check_extent_refs(struct btrfs_root *root, err = 1; } + if (!rec->owner_ref_checked) { + fprintf(stderr, "owner ref check failed [%llu %llu]\n", + (unsigned long long)rec->start, + (unsigned long long)rec->nr); + err = 1; + } + remove_cache_extent(extent_cache, cache); free_all_extent_backrefs(rec); free(rec); @@ -2009,11 +2382,11 @@ static int check_extents(struct btrfs_root *root) add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr, &extent_cache, &pending, &seen, &reada, &nodes, - root->fs_info->tree_root->root_key.objectid); + &root->fs_info->tree_root->root_key); add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr, &extent_cache, &pending, &seen, &reada, &nodes, - root->fs_info->chunk_root->root_key.objectid); + &root->fs_info->chunk_root->root_key); btrfs_init_path(&path); key.offset = 0; @@ -2045,7 +2418,7 @@ static int check_extents(struct btrfs_root *root) btrfs_root_level(&ri)), 0); add_root_to_pending(buf, bits, bits_nr, &extent_cache, &pending, &seen, &reada, &nodes, - found_key.objectid); + &found_key); free_extent_buffer(buf); } path.slots[0]++; @@ -2089,11 +2462,25 @@ int main(int ac, char **av) out: close_ctree(root); + if (found_old_backref) { + /* + * there was a disk format change when mixed + * backref was in testing tree. The old format + * existed about one week. + */ + printf("\n * Found old mixed backref format. " + "The old format is not supported! *" + "\n * Please mount the FS in readonly mode, " + "backup data and re-format the FS. *\n\n"); + ret = 1; + } printf("found %llu bytes used err is %d\n", (unsigned long long)bytes_used, ret); printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes); printf("total tree bytes: %llu\n", (unsigned long long)total_btree_bytes); + printf("total fs tree bytes: %llu\n", + (unsigned long long)total_fs_tree_bytes); printf("btree space waste bytes: %llu\n", (unsigned long long)btree_space_waste); printf("file data blocks allocated: %llu\n referenced %llu\n", |