X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=cmds-check.c;h=e9a4d862bdd524f09df2132b5eba22025ec03626;hb=cf4ada1f13201a29a4261a5599cdea0cbd1572a4;hp=ef3e3a101284e0a59524d340c6e770d92a22f701;hpb=9a0f2f1e53e4620b21680f64c263b3cbbcd8d512;p=platform%2Fupstream%2Fbtrfs-progs.git diff --git a/cmds-check.c b/cmds-check.c index ef3e3a1..e9a4d86 100644 --- a/cmds-check.c +++ b/cmds-check.c @@ -41,6 +41,7 @@ #include "rbtree-utils.h" #include "backref.h" #include "ulist.h" +#include "hash.h" enum task_position { TASK_EXTENTS, @@ -84,7 +85,7 @@ enum btrfs_check_mode { static enum btrfs_check_mode check_mode = CHECK_MODE_DEFAULT; struct extent_backref { - struct rb_node node; + struct list_head list; unsigned int is_data:1; unsigned int found_extent_tree:1; unsigned int full_backref:1; @@ -92,9 +93,9 @@ struct extent_backref { unsigned int broken:1; }; -static inline struct extent_backref* rb_node_to_extent_backref(struct rb_node *node) +static inline struct extent_backref* to_extent_backref(struct list_head *entry) { - return rb_entry(node, struct extent_backref, node); + return list_entry(entry, struct extent_backref, list); } struct data_backref { @@ -117,56 +118,6 @@ static inline struct data_backref* to_data_backref(struct extent_backref *back) return container_of(back, struct data_backref, node); } -static int compare_data_backref(struct rb_node *node1, struct rb_node *node2) -{ - struct extent_backref *ext1 = rb_node_to_extent_backref(node1); - struct extent_backref *ext2 = rb_node_to_extent_backref(node2); - struct data_backref *back1 = to_data_backref(ext1); - struct data_backref *back2 = to_data_backref(ext2); - - WARN_ON(!ext1->is_data); - WARN_ON(!ext2->is_data); - - /* parent and root are a union, so this covers both */ - if (back1->parent > back2->parent) - return 1; - if (back1->parent < back2->parent) - return -1; - - /* This is a full backref and the parents match. */ - if (back1->node.full_backref) - return 0; - - if (back1->owner > back2->owner) - return 1; - if (back1->owner < back2->owner) - return -1; - - if (back1->offset > back2->offset) - return 1; - if (back1->offset < back2->offset) - return -1; - - if (back1->bytes > back2->bytes) - return 1; - if (back1->bytes < back2->bytes) - return -1; - - if (back1->found_ref && back2->found_ref) { - if (back1->disk_bytenr > back2->disk_bytenr) - return 1; - if (back1->disk_bytenr < back2->disk_bytenr) - return -1; - - if (back1->found_ref > back2->found_ref) - return 1; - if (back1->found_ref < back2->found_ref) - return -1; - } - - return 0; -} - /* * Much like data_backref, just removed the undetermined members * and change it to use list_head. @@ -195,54 +146,12 @@ static inline struct tree_backref* to_tree_backref(struct extent_backref *back) return container_of(back, struct tree_backref, node); } -static int compare_tree_backref(struct rb_node *node1, struct rb_node *node2) -{ - struct extent_backref *ext1 = rb_node_to_extent_backref(node1); - struct extent_backref *ext2 = rb_node_to_extent_backref(node2); - struct tree_backref *back1 = to_tree_backref(ext1); - struct tree_backref *back2 = to_tree_backref(ext2); - - WARN_ON(ext1->is_data); - WARN_ON(ext2->is_data); - - /* parent and root are a union, so this covers both */ - if (back1->parent > back2->parent) - return 1; - if (back1->parent < back2->parent) - return -1; - - return 0; -} - -static int compare_extent_backref(struct rb_node *node1, struct rb_node *node2) -{ - struct extent_backref *ext1 = rb_node_to_extent_backref(node1); - struct extent_backref *ext2 = rb_node_to_extent_backref(node2); - - if (ext1->is_data > ext2->is_data) - return 1; - - if (ext1->is_data < ext2->is_data) - return -1; - - if (ext1->full_backref > ext2->full_backref) - return 1; - if (ext1->full_backref < ext2->full_backref) - return -1; - - if (ext1->is_data) - return compare_data_backref(node1, node2); - else - return compare_tree_backref(node1, node2); -} - /* Explicit initialization for extent_record::flag_block_full_backref */ enum { FLAG_UNSET = 2 }; struct extent_record { struct list_head backrefs; struct list_head dups; - struct rb_root backref_tree; struct list_head list; struct cache_extent cache; struct btrfs_disk_key parent_key; @@ -277,9 +186,9 @@ struct inode_backref { unsigned int found_dir_item:1; unsigned int found_dir_index:1; unsigned int found_inode_ref:1; - unsigned int filetype:8; + u8 filetype; + u8 ref_type; int errors; - unsigned int ref_type; u64 dir; u64 index; u16 namelen; @@ -751,6 +660,7 @@ static struct inode_record *clone_inode_rec(struct inode_record *orig_rec) struct inode_backref *tmp; struct orphan_data_extent *src_orphan; struct orphan_data_extent *dst_orphan; + struct rb_node *rb; size_t size; int ret; @@ -783,10 +693,21 @@ static struct inode_record *clone_inode_rec(struct inode_record *orig_rec) list_add_tail(&dst_orphan->list, &rec->orphan_extents); } ret = copy_file_extent_holes(&rec->holes, &orig_rec->holes); - BUG_ON(ret < 0); + if (ret < 0) + goto cleanup_rb; return rec; +cleanup_rb: + rb = rb_first(&rec->holes); + while (rb) { + struct file_extent_hole *hole; + + hole = rb_entry(rb, struct file_extent_hole, node); + rb = rb_next(rb); + free(hole); + } + cleanup: if (!list_empty(&rec->backrefs)) list_for_each_entry_safe(orig, tmp, &rec->backrefs, list) { @@ -1016,7 +937,7 @@ static void maybe_free_inode_rec(struct cache_tree *inode_cache, struct cache_extent *cache; struct inode_backref *tmp, *backref; struct ptr_node *node; - unsigned char filetype; + u8 filetype; if (!rec->found_inode_item) return; @@ -1147,7 +1068,7 @@ static struct inode_backref *get_inode_backref(struct inode_record *rec, static int add_inode_backref(struct cache_tree *inode_cache, u64 ino, u64 dir, u64 index, const char *name, int namelen, - int filetype, int itemtype, int errors) + u8 filetype, u8 itemtype, int errors) { struct inode_record *rec; struct inode_backref *backref; @@ -1550,7 +1471,7 @@ static int process_dir_item(struct btrfs_root *root, u32 data_len; int error; int nritems = 0; - int filetype; + u8 filetype; struct btrfs_dir_item *di; struct inode_record *rec; struct cache_tree *root_cache; @@ -2266,7 +2187,7 @@ static int add_missing_dir_index(struct btrfs_root *root, struct inode_record *rec, struct inode_backref *backref) { - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_trans_handle *trans; struct btrfs_dir_item *dir_item; struct extent_buffer *leaf; @@ -2277,27 +2198,22 @@ static int add_missing_dir_index(struct btrfs_root *root, u32 data_size = sizeof(*dir_item) + backref->namelen; int ret; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } fprintf(stderr, "repairing missing dir index item for inode %llu\n", (unsigned long long)rec->ino); + + btrfs_init_path(&path); key.objectid = backref->dir; key.type = BTRFS_DIR_INDEX_KEY; key.offset = backref->index; - - ret = btrfs_insert_empty_item(trans, root, path, &key, data_size); + ret = btrfs_insert_empty_item(trans, root, &path, &key, data_size); BUG_ON(ret); - leaf = path->nodes[0]; - dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item); + leaf = path.nodes[0]; + dir_item = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_dir_item); disk_key.objectid = cpu_to_le64(rec->ino); disk_key.type = BTRFS_INODE_ITEM_KEY; @@ -2310,7 +2226,7 @@ static int add_missing_dir_index(struct btrfs_root *root, name_ptr = (unsigned long)(dir_item + 1); write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen); btrfs_mark_buffer_dirty(leaf); - btrfs_free_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, root); backref->found_dir_index = 1; @@ -2335,31 +2251,25 @@ static int delete_dir_index(struct btrfs_root *root, { struct btrfs_trans_handle *trans; struct btrfs_dir_item *di; - struct btrfs_path *path; + struct btrfs_path path; int ret = 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } - fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n", (unsigned long long)backref->dir, BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index, (unsigned long long)root->objectid); - di = btrfs_lookup_dir_index(trans, root, path, backref->dir, + btrfs_init_path(&path); + di = btrfs_lookup_dir_index(trans, root, &path, backref->dir, backref->name, backref->namelen, backref->index, -1); if (IS_ERR(di)) { ret = PTR_ERR(di); - btrfs_free_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, root); if (ret == -ENOENT) return 0; @@ -2367,11 +2277,11 @@ static int delete_dir_index(struct btrfs_root *root, } if (!di) - ret = btrfs_del_item(trans, root, path); + ret = btrfs_del_item(trans, root, &path); else - ret = btrfs_delete_one_dir_name(trans, root, path, di); + ret = btrfs_delete_one_dir_name(trans, root, &path, di); BUG_ON(ret); - btrfs_free_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, root); return ret; } @@ -2774,48 +2684,46 @@ out: */ static int find_normal_file_extent(struct btrfs_root *root, u64 ino) { - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_key key; struct btrfs_key found_key; struct btrfs_file_extent_item *fi; u8 type; int ret = 0; - path = btrfs_alloc_path(); - if (!path) - goto out; + btrfs_init_path(&path); key.objectid = ino; key.type = BTRFS_EXTENT_DATA_KEY; key.offset = 0; - ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); if (ret < 0) { ret = 0; goto out; } - if (ret && path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(root, path); + if (ret && path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(root, &path); if (ret) { ret = 0; goto out; } } while (1) { - btrfs_item_key_to_cpu(path->nodes[0], &found_key, - path->slots[0]); + btrfs_item_key_to_cpu(path.nodes[0], &found_key, + path.slots[0]); if (found_key.objectid != ino || found_key.type != BTRFS_EXTENT_DATA_KEY) break; - fi = btrfs_item_ptr(path->nodes[0], path->slots[0], + fi = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_file_extent_item); - type = btrfs_file_extent_type(path->nodes[0], fi); + type = btrfs_file_extent_type(path.nodes[0], fi); if (type != BTRFS_FILE_EXTENT_INLINE) { ret = 1; goto out; } } out: - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -3006,7 +2914,7 @@ out: static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec) { struct btrfs_trans_handle *trans; - struct btrfs_path *path; + struct btrfs_path path; int ret = 0; if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG | @@ -3018,10 +2926,6 @@ static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec) I_ERR_FILE_NBYTES_WRONG))) return rec->errors; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - /* * For nlink repair, it may create a dir and add link, so * 2 for parent(256)'s dir_index and dir_item @@ -3030,27 +2934,26 @@ static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec) * 2 for lost+found dir's dir_index and dir_item for the file */ trans = btrfs_start_transaction(root, 7); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } + btrfs_init_path(&path); if (rec->errors & I_ERR_NO_INODE_ITEM) - ret = repair_inode_no_item(trans, root, path, rec); + ret = repair_inode_no_item(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_FILE_EXTENT_ORPHAN) - ret = repair_inode_orphan_extent(trans, root, path, rec); + ret = repair_inode_orphan_extent(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_FILE_EXTENT_DISCOUNT) - ret = repair_inode_discount_extent(trans, root, path, rec); + ret = repair_inode_discount_extent(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG) - ret = repair_inode_isize(trans, root, path, rec); + ret = repair_inode_isize(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM) - ret = repair_inode_orphan_item(trans, root, path, rec); + ret = repair_inode_orphan_item(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG) - ret = repair_inode_nlinks(trans, root, path, rec); + ret = repair_inode_nlinks(trans, root, &path, rec); if (!ret && rec->errors & I_ERR_FILE_NBYTES_WRONG) - ret = repair_inode_nbytes(trans, root, path, rec); + ret = repair_inode_nbytes(trans, root, &path, rec); btrfs_commit_transaction(trans, root); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -3302,7 +3205,7 @@ static void free_root_record(struct cache_extent *cache) free(backref); } - kfree(rec); + free(rec); } FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record); @@ -3583,7 +3486,7 @@ static int repair_btree(struct btrfs_root *root, struct cache_tree *corrupt_blocks) { struct btrfs_trans_handle *trans; - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_corrupt_block *corrupt; struct cache_extent *cache; struct btrfs_key key; @@ -3594,23 +3497,20 @@ static int repair_btree(struct btrfs_root *root, if (cache_tree_empty(corrupt_blocks)) return 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 1); if (IS_ERR(trans)) { ret = PTR_ERR(trans); fprintf(stderr, "Error starting transaction: %s\n", strerror(-ret)); - goto out_free_path; + return ret; } + btrfs_init_path(&path); cache = first_cache_extent(corrupt_blocks); while (cache) { corrupt = container_of(cache, struct btrfs_corrupt_block, cache); level = corrupt->level; - path->lowest_level = level; + path.lowest_level = level; key.objectid = corrupt->key.objectid; key.type = corrupt->key.type; key.offset = corrupt->key.offset; @@ -3621,22 +3521,22 @@ static int repair_btree(struct btrfs_root *root, * so ins_len set to 0 here. * Balance will be done after all corrupt node/leaf is deleted. */ - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + ret = btrfs_search_slot(trans, root, &key, &path, 0, 1); if (ret < 0) goto out; - offset = btrfs_node_blockptr(path->nodes[level], - path->slots[level]); + offset = btrfs_node_blockptr(path.nodes[level], + path.slots[level]); /* Remove the ptr */ - ret = btrfs_del_ptr(trans, root, path, level, - path->slots[level]); + ret = btrfs_del_ptr(trans, root, &path, level, + path.slots[level]); if (ret < 0) goto out; /* * Remove the corresponding extent * return value is not concerned. */ - btrfs_release_path(path); + btrfs_release_path(&path); ret = btrfs_free_extent(trans, root, offset, root->nodesize, 0, root->root_key.objectid, level - 1, 0); @@ -3649,18 +3549,17 @@ static int repair_btree(struct btrfs_root *root, corrupt = container_of(cache, struct btrfs_corrupt_block, cache); memcpy(&key, &corrupt->key, sizeof(key)); - ret = btrfs_search_slot(trans, root, &key, path, -1, 1); + ret = btrfs_search_slot(trans, root, &key, &path, -1, 1); if (ret < 0) goto out; /* return will always >0 since it won't find the item */ ret = 0; - btrfs_release_path(path); + btrfs_release_path(&path); cache = next_cache_extent(cache); } out: btrfs_commit_transaction(trans, root); -out_free_path: - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -3928,17 +3827,459 @@ out: return err; } +#define ROOT_DIR_ERROR (1<<1) /* bad ROOT_DIR */ +#define DIR_ITEM_MISSING (1<<2) /* DIR_ITEM not found */ +#define DIR_ITEM_MISMATCH (1<<3) /* DIR_ITEM found but not match */ +#define INODE_REF_MISSING (1<<4) /* INODE_REF/INODE_EXTREF not found */ + +/* + * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified + * INODE_REF/INODE_EXTREF match. + * + * @root: the root of the fs/file tree + * @ref_key: the key of the INODE_REF/INODE_EXTREF + * @key: the key of the DIR_ITEM/DIR_INDEX + * @index: the index in the INODE_REF/INODE_EXTREF, be used to + * distinguish root_dir between normal dir/file + * @name: the name in the INODE_REF/INODE_EXTREF + * @namelen: the length of name in the INODE_REF/INODE_EXTREF + * @mode: the st_mode of INODE_ITEM + * + * Return 0 if no error occurred. + * Return ROOT_DIR_ERROR if found DIR_ITEM/DIR_INDEX for root_dir. + * Return DIR_ITEM_MISSING if couldn't find DIR_ITEM/DIR_INDEX for normal + * dir/file. + * Return DIR_ITEM_MISMATCH if INODE_REF/INODE_EXTREF and DIR_ITEM/DIR_INDEX + * not match for normal dir/file. + */ +static int find_dir_item(struct btrfs_root *root, struct btrfs_key *ref_key, + struct btrfs_key *key, u64 index, char *name, + u32 namelen, u32 mode) +{ + struct btrfs_path path; + struct extent_buffer *node; + struct btrfs_dir_item *di; + struct btrfs_key location; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u32 data_len; + u8 filetype; + int slot; + int ret; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret < 0) { + ret = DIR_ITEM_MISSING; + goto out; + } + + /* Process root dir and goto out*/ + if (index == 0) { + if (ret == 0) { + ret = ROOT_DIR_ERROR; + error( + "root %llu INODE %s[%llu %llu] ROOT_DIR shouldn't have %s", + root->objectid, + ref_key->type == BTRFS_INODE_REF_KEY ? + "REF" : "EXTREF", + ref_key->objectid, ref_key->offset, + key->type == BTRFS_DIR_ITEM_KEY ? + "DIR_ITEM" : "DIR_INDEX"); + } else { + ret = 0; + } + + goto out; + } + + /* Process normal file/dir */ + if (ret > 0) { + ret = DIR_ITEM_MISSING; + error( + "root %llu INODE %s[%llu %llu] doesn't have related %s[%llu %llu] namelen %u filename %s filetype %d", + root->objectid, + ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF", + ref_key->objectid, ref_key->offset, + key->type == BTRFS_DIR_ITEM_KEY ? + "DIR_ITEM" : "DIR_INDEX", + key->objectid, key->offset, namelen, name, + imode_to_type(mode)); + goto out; + } + + /* Check whether inode_id/filetype/name match */ + node = path.nodes[0]; + slot = path.slots[0]; + di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); + total = btrfs_item_size_nr(node, slot); + while (cur < total) { + ret = DIR_ITEM_MISMATCH; + name_len = btrfs_dir_name_len(node, di); + data_len = btrfs_dir_data_len(node, di); + + btrfs_dir_item_key_to_cpu(node, di, &location); + if (location.objectid != ref_key->objectid || + location.type != BTRFS_INODE_ITEM_KEY || + location.offset != 0) + goto next; + + filetype = btrfs_dir_type(node, di); + if (imode_to_type(mode) != filetype) + goto next; + + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu %s[%llu %llu] name too long %u, trimmed", + root->objectid, + key->type == BTRFS_DIR_ITEM_KEY ? + "DIR_ITEM" : "DIR_INDEX", + key->objectid, key->offset, name_len); + } + read_extent_buffer(node, namebuf, (unsigned long)(di + 1), len); + if (len != namelen || strncmp(namebuf, name, len)) + goto next; + + ret = 0; + goto out; +next: + len = sizeof(*di) + name_len + data_len; + di = (struct btrfs_dir_item *)((char *)di + len); + cur += len; + } + if (ret == DIR_ITEM_MISMATCH) + error( + "root %llu INODE %s[%llu %llu] and %s[%llu %llu] mismatch namelen %u filename %s filetype %d", + root->objectid, + ref_key->type == BTRFS_INODE_REF_KEY ? "REF" : "EXTREF", + ref_key->objectid, ref_key->offset, + key->type == BTRFS_DIR_ITEM_KEY ? + "DIR_ITEM" : "DIR_INDEX", + key->objectid, key->offset, namelen, name, + imode_to_type(mode)); +out: + btrfs_release_path(&path); + return ret; +} + +/* + * Traverse the given INODE_REF and call find_dir_item() to find related + * DIR_ITEM/DIR_INDEX. + * + * @root: the root of the fs/file tree + * @ref_key: the key of the INODE_REF + * @refs: the count of INODE_REF + * @mode: the st_mode of INODE_ITEM + * + * Return 0 if no error occurred. + */ +static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key, + struct extent_buffer *node, int slot, u64 *refs, + int mode) +{ + struct btrfs_key key; + struct btrfs_inode_ref *ref; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u64 index; + int ret, err = 0; + + ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); + total = btrfs_item_size_nr(node, slot); + +next: + /* Update inode ref count */ + (*refs)++; + + index = btrfs_inode_ref_index(node, ref); + name_len = btrfs_inode_ref_name_len(node, ref); + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE_REF[%llu %llu] name too long", + root->objectid, ref_key->objectid, ref_key->offset); + } + + read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len); + + /* Check root dir ref name */ + if (index == 0 && strncmp(namebuf, "..", name_len)) { + error("root %llu INODE_REF[%llu %llu] ROOT_DIR name shouldn't be %s", + root->objectid, ref_key->objectid, ref_key->offset, + namebuf); + err |= ROOT_DIR_ERROR; + } + + /* Find related DIR_INDEX */ + key.objectid = ref_key->offset; + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = index; + ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode); + err |= ret; + + /* Find related dir_item */ + key.objectid = ref_key->offset; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(namebuf, len); + ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode); + err |= ret; + + len = sizeof(*ref) + name_len; + ref = (struct btrfs_inode_ref *)((char *)ref + len); + cur += len; + if (cur < total) + goto next; + + return err; +} + +/* + * Traverse the given INODE_EXTREF and call find_dir_item() to find related + * DIR_ITEM/DIR_INDEX. + * + * @root: the root of the fs/file tree + * @ref_key: the key of the INODE_EXTREF + * @refs: the count of INODE_EXTREF + * @mode: the st_mode of INODE_ITEM + * + * Return 0 if no error occurred. + */ +static int check_inode_extref(struct btrfs_root *root, + struct btrfs_key *ref_key, + struct extent_buffer *node, int slot, u64 *refs, + int mode) +{ + struct btrfs_key key; + struct btrfs_inode_extref *extref; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u64 index; + u64 parent; + int ret; + int err = 0; + + extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); + total = btrfs_item_size_nr(node, slot); + +next: + /* update inode ref count */ + (*refs)++; + name_len = btrfs_inode_extref_name_len(node, extref); + index = btrfs_inode_extref_index(node, extref); + parent = btrfs_inode_extref_parent(node, extref); + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE_EXTREF[%llu %llu] name too long", + root->objectid, ref_key->objectid, ref_key->offset); + } + read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len); + + /* Check root dir ref name */ + if (index == 0 && strncmp(namebuf, "..", name_len)) { + error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s", + root->objectid, ref_key->objectid, ref_key->offset, + namebuf); + err |= ROOT_DIR_ERROR; + } + + /* find related dir_index */ + key.objectid = parent; + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = index; + ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode); + err |= ret; + + /* find related dir_item */ + key.objectid = parent; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(namebuf, len); + ret = find_dir_item(root, ref_key, &key, index, namebuf, len, mode); + err |= ret; + + len = sizeof(*extref) + name_len; + extref = (struct btrfs_inode_extref *)((char *)extref + len); + cur += len; + + if (cur < total) + goto next; + + return err; +} + +/* + * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified + * DIR_ITEM/DIR_INDEX match. + * + * @root: the root of the fs/file tree + * @key: the key of the INODE_REF/INODE_EXTREF + * @name: the name in the INODE_REF/INODE_EXTREF + * @namelen: the length of name in the INODE_REF/INODE_EXTREF + * @index: the index in the INODE_REF/INODE_EXTREF, for DIR_ITEM set index + * to (u64)-1 + * @ext_ref: the EXTENDED_IREF feature + * + * Return 0 if no error occurred. + * Return >0 for error bitmap + */ +static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key, + char *name, int namelen, u64 index, + unsigned int ext_ref) +{ + struct btrfs_path path; + struct btrfs_inode_ref *ref; + struct btrfs_inode_extref *extref; + struct extent_buffer *node; + char ref_namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 ref_namelen; + u64 ref_index; + u64 parent; + u64 dir_id; + int slot; + int ret; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret) { + ret = INODE_REF_MISSING; + goto extref; + } + + node = path.nodes[0]; + slot = path.slots[0]; + + ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); + total = btrfs_item_size_nr(node, slot); + + /* Iterate all entry of INODE_REF */ + while (cur < total) { + ret = INODE_REF_MISSING; + + ref_namelen = btrfs_inode_ref_name_len(node, ref); + ref_index = btrfs_inode_ref_index(node, ref); + if (index != (u64)-1 && index != ref_index) + goto next_ref; + + if (ref_namelen <= BTRFS_NAME_LEN) { + len = ref_namelen; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE %s[%llu %llu] name too long", + root->objectid, + key->type == BTRFS_INODE_REF_KEY ? + "REF" : "EXTREF", + key->objectid, key->offset); + } + read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1), + len); + + if (len != namelen || strncmp(ref_namebuf, name, len)) + goto next_ref; + + ret = 0; + goto out; +next_ref: + len = sizeof(*ref) + ref_namelen; + ref = (struct btrfs_inode_ref *)((char *)ref + len); + cur += len; + } + +extref: + /* Skip if not support EXTENDED_IREF feature */ + if (!ext_ref) + goto out; + + btrfs_release_path(&path); + btrfs_init_path(&path); + + dir_id = key->offset; + key->type = BTRFS_INODE_EXTREF_KEY; + key->offset = btrfs_extref_hash(dir_id, name, namelen); + + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret) { + ret = INODE_REF_MISSING; + goto out; + } + + node = path.nodes[0]; + slot = path.slots[0]; + + extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); + cur = 0; + total = btrfs_item_size_nr(node, slot); + + /* Iterate all entry of INODE_EXTREF */ + while (cur < total) { + ret = INODE_REF_MISSING; + + ref_namelen = btrfs_inode_extref_name_len(node, extref); + ref_index = btrfs_inode_extref_index(node, extref); + parent = btrfs_inode_extref_parent(node, extref); + if (index != (u64)-1 && index != ref_index) + goto next_extref; + + if (parent != dir_id) + goto next_extref; + + if (ref_namelen <= BTRFS_NAME_LEN) { + len = ref_namelen; + } else { + len = BTRFS_NAME_LEN; + warning("Warning: root %llu INODE %s[%llu %llu] name too long\n", + root->objectid, + key->type == BTRFS_INODE_REF_KEY ? + "REF" : "EXTREF", + key->objectid, key->offset); + } + read_extent_buffer(node, ref_namebuf, + (unsigned long)(extref + 1), len); + + if (len != namelen || strncmp(ref_namebuf, name, len)) + goto next_extref; + + ret = 0; + goto out; + +next_extref: + len = sizeof(*extref) + ref_namelen; + extref = (struct btrfs_inode_extref *)((char *)extref + len); + cur += len; + + } +out: + btrfs_release_path(&path); + return ret; +} + static int all_backpointers_checked(struct extent_record *rec, int print_errs) { - struct rb_node *n; + struct list_head *cur = rec->backrefs.next; struct extent_backref *back; struct tree_backref *tback; struct data_backref *dback; u64 found = 0; int err = 0; - for (n = rb_first(&rec->backref_tree); n; n = rb_next(n)) { - back = rb_node_to_extent_backref(n); + while(cur != &rec->backrefs) { + back = to_extent_backref(cur); + cur = cur->next; if (!back->found_extent_tree) { err = 1; if (!print_errs) @@ -4041,16 +4382,17 @@ out: return err; } -static void __free_one_backref(struct rb_node *node) +static int free_all_extent_backrefs(struct extent_record *rec) { - struct extent_backref *back = rb_node_to_extent_backref(node); - - free(back); -} - -static void free_all_extent_backrefs(struct extent_record *rec) -{ - rb_free_nodes(&rec->backref_tree, __free_one_backref); + struct extent_backref *back; + struct list_head *cur; + while (!list_empty(&rec->backrefs)) { + cur = rec->backrefs.next; + back = to_extent_backref(cur); + list_del(cur); + free(back); + } + return 0; } static void free_extent_record_cache(struct btrfs_fs_info *fs_info, @@ -4090,7 +4432,7 @@ static int check_owner_ref(struct btrfs_root *root, struct extent_record *rec, struct extent_buffer *buf) { - struct extent_backref *node, *tmp; + struct extent_backref *node; struct tree_backref *back; struct btrfs_root *ref_root; struct btrfs_key key; @@ -4100,8 +4442,7 @@ static int check_owner_ref(struct btrfs_root *root, int found = 0; int ret; - rbtree_postorder_for_each_entry_safe(node, tmp, - &rec->backref_tree, node) { + list_for_each_entry(node, &rec->backrefs, list) { if (node->is_data) continue; if (!node->found_ref) @@ -4146,16 +4487,18 @@ static int check_owner_ref(struct btrfs_root *root, static int is_extent_tree_record(struct extent_record *rec) { - struct extent_backref *ref, *tmp; + struct list_head *cur = rec->backrefs.next; + struct extent_backref *node; struct tree_backref *back; int is_extent = 0; - rbtree_postorder_for_each_entry_safe(ref, tmp, - &rec->backref_tree, node) { - if (ref->is_data) + while(cur != &rec->backrefs) { + node = to_extent_backref(cur); + cur = cur->next; + if (node->is_data) return 0; - back = to_tree_backref(ref); - if (ref->full_backref) + back = to_tree_backref(node); + if (node->full_backref) return 0; if (back->root == BTRFS_EXTENT_TREE_OBJECTID) is_extent = 1; @@ -4399,7 +4742,7 @@ static int try_to_fix_bad_block(struct btrfs_root *root, struct ulist *roots; struct ulist_node *node; struct btrfs_root *search_root; - struct btrfs_path *path; + struct btrfs_path path; struct ulist_iterator iter; struct btrfs_key root_key, key; int ret; @@ -4408,17 +4751,11 @@ static int try_to_fix_bad_block(struct btrfs_root *root, status != BTRFS_TREE_BLOCK_INVALID_OFFSETS) return -EIO; - path = btrfs_alloc_path(); - if (!path) - return -EIO; - - ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start, - 0, &roots); - if (ret) { - btrfs_free_path(path); + ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start, 0, &roots); + if (ret) return -EIO; - } + btrfs_init_path(&path); ULIST_ITER_INIT(&iter); while ((node = ulist_next(roots, &iter))) { root_key.objectid = node->val; @@ -4438,31 +4775,31 @@ static int try_to_fix_bad_block(struct btrfs_root *root, break; } - path->lowest_level = btrfs_header_level(buf); - path->skip_check_block = 1; - if (path->lowest_level) + path.lowest_level = btrfs_header_level(buf); + path.skip_check_block = 1; + if (path.lowest_level) btrfs_node_key_to_cpu(buf, &key, 0); else btrfs_item_key_to_cpu(buf, &key, 0); - ret = btrfs_search_slot(trans, search_root, &key, path, 0, 1); + ret = btrfs_search_slot(trans, search_root, &key, &path, 0, 1); if (ret) { ret = -EIO; btrfs_commit_transaction(trans, search_root); break; } if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER) - ret = fix_key_order(trans, search_root, path); + ret = fix_key_order(trans, search_root, &path); else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS) - ret = fix_item_offset(trans, search_root, path); + ret = fix_item_offset(trans, search_root, &path); if (ret) { btrfs_commit_transaction(trans, search_root); break; } - btrfs_release_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, search_root); } ulist_free(roots); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -4529,31 +4866,32 @@ static int check_block(struct btrfs_root *root, return ret; } - static struct tree_backref *find_tree_backref(struct extent_record *rec, u64 parent, u64 root) { - struct rb_node *node; - struct tree_backref *back = NULL; - struct tree_backref match = { - .node = { - .is_data = 0, - }, - }; + struct list_head *cur = rec->backrefs.next; + struct extent_backref *node; + struct tree_backref *back; - if (parent) { - match.parent = parent; - match.node.full_backref = 1; - } else { - match.root = root; + while(cur != &rec->backrefs) { + node = to_extent_backref(cur); + cur = cur->next; + if (node->is_data) + continue; + back = to_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; + } } - - node = rb_search(&rec->backref_tree, &match.node.node, - (rb_compare_keys)compare_extent_backref, NULL); - if (node) - back = to_tree_backref(rb_node_to_extent_backref(node)); - - return back; + return NULL; } static struct tree_backref *alloc_tree_backref(struct extent_record *rec, @@ -4571,7 +4909,7 @@ static struct tree_backref *alloc_tree_backref(struct extent_record *rec, ref->root = root; ref->node.full_backref = 0; } - rb_insert(&rec->backref_tree, &ref->node.node, compare_extent_backref); + list_add_tail(&ref->node.list, &rec->backrefs); return ref; } @@ -4582,32 +4920,35 @@ static struct data_backref *find_data_backref(struct extent_record *rec, int found_ref, u64 disk_bytenr, u64 bytes) { - struct rb_node *node; - struct data_backref *back = NULL; - struct data_backref match = { - .node = { - .is_data = 1, - }, - .owner = owner, - .offset = offset, - .bytes = bytes, - .found_ref = found_ref, - .disk_bytenr = disk_bytenr, - }; + struct list_head *cur = rec->backrefs.next; + struct extent_backref *node; + struct data_backref *back; - if (parent) { - match.parent = parent; - match.node.full_backref = 1; - } else { - match.root = root; + while(cur != &rec->backrefs) { + node = to_extent_backref(cur); + cur = cur->next; + if (!node->is_data) + continue; + back = to_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) { + if (found_ref && node->found_ref && + (back->bytes != bytes || + back->disk_bytenr != disk_bytenr)) + continue; + return back; + } + } } - - node = rb_search(&rec->backref_tree, &match.node.node, - (rb_compare_keys)compare_extent_backref, NULL); - if (node) - back = to_data_backref(rb_node_to_extent_backref(node)); - - return back; + return NULL; } static struct data_backref *alloc_data_backref(struct extent_record *rec, @@ -4636,7 +4977,7 @@ static struct data_backref *alloc_data_backref(struct extent_record *rec, ref->bytes = max_size; ref->found_ref = 0; ref->num_refs = 0; - rb_insert(&rec->backref_tree, &ref->node.node, compare_extent_backref); + list_add_tail(&ref->node.list, &rec->backrefs); if (max_size > rec->max_size) rec->max_size = max_size; return ref; @@ -4669,12 +5010,12 @@ static void check_extent_type(struct extent_record *rec) * Check SYSTEM extent, as it's also marked as metadata, we can only * make sure it's a SYSTEM extent by its backref */ - if (!RB_EMPTY_ROOT(&rec->backref_tree)) { + if (!list_empty(&rec->backrefs)) { struct extent_backref *node; struct tree_backref *tback; u64 bg_type; - node = rb_node_to_extent_backref(rb_first(&rec->backref_tree)); + node = to_extent_backref(rec->backrefs.next); if (node->is_data) { /* tree block shouldn't have data backref */ rec->wrong_chunk_type = 1; @@ -4724,17 +5065,19 @@ static int add_extent_rec_nolookup(struct cache_tree *extent_cache, INIT_LIST_HEAD(&rec->backrefs); INIT_LIST_HEAD(&rec->dups); INIT_LIST_HEAD(&rec->list); - rec->backref_tree = RB_ROOT; memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key)); rec->cache.start = tmpl->start; rec->cache.size = tmpl->nr; ret = insert_cache_extent(extent_cache, &rec->cache); - BUG_ON(ret); + if (ret) { + free(rec); + return ret; + } bytes_used += rec->nr; if (tmpl->metadata) - rec->crossing_stripes = check_crossing_stripes(rec->start, - global_info->tree_root->nodesize); + rec->crossing_stripes = check_crossing_stripes(global_info, + rec->start, global_info->tree_root->nodesize); check_extent_type(rec); return ret; } @@ -4835,7 +5178,8 @@ static int add_extent_rec(struct cache_tree *extent_cache, */ if (tmpl->metadata) rec->crossing_stripes = check_crossing_stripes( - rec->start, global_info->tree_root->nodesize); + global_info, rec->start, + global_info->tree_root->nodesize); check_extent_type(rec); maybe_free_extent_rec(extent_cache, rec); return ret; @@ -4852,6 +5196,7 @@ static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr, struct extent_record *rec; struct tree_backref *back; struct cache_extent *cache; + int ret; cache = lookup_cache_extent(extent_cache, bytenr, 1); if (!cache) { @@ -4862,7 +5207,9 @@ static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr, tmpl.nr = 1; tmpl.metadata = 1; - add_extent_rec_nolookup(extent_cache, &tmpl); + ret = add_extent_rec_nolookup(extent_cache, &tmpl); + if (ret) + return ret; /* really a bug in cache_extent implement now */ cache = lookup_cache_extent(extent_cache, bytenr, 1); @@ -4916,6 +5263,7 @@ static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr, struct extent_record *rec; struct data_backref *back; struct cache_extent *cache; + int ret; cache = lookup_cache_extent(extent_cache, bytenr, 1); if (!cache) { @@ -4926,7 +5274,9 @@ static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr, tmpl.nr = 1; tmpl.max_size = max_size; - add_extent_rec_nolookup(extent_cache, &tmpl); + ret = add_extent_rec_nolookup(extent_cache, &tmpl); + if (ret) + return ret; cache = lookup_cache_extent(extent_cache, bytenr, 1); if (!cache) @@ -5560,7 +5910,7 @@ static int check_cache_range(struct btrfs_root *root, continue; if (logical[nr] == offset) { if (stripe_len >= bytes) { - kfree(logical); + free(logical); return 0; } bytes -= stripe_len; @@ -5568,7 +5918,7 @@ static int check_cache_range(struct btrfs_root *root, } else if (logical[nr] < offset) { if (logical[nr] + stripe_len >= offset + bytes) { - kfree(logical); + free(logical); return 0; } bytes = (offset + bytes) - @@ -5591,7 +5941,7 @@ static int check_cache_range(struct btrfs_root *root, offset, logical[nr] - offset); if (ret) { - kfree(logical); + free(logical); return ret; } @@ -5602,7 +5952,7 @@ static int check_cache_range(struct btrfs_root *root, } } - kfree(logical); + free(logical); } entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes); @@ -5632,31 +5982,27 @@ static int check_cache_range(struct btrfs_root *root, static int verify_space_cache(struct btrfs_root *root, struct btrfs_block_group_cache *cache) { - struct btrfs_path *path; + struct btrfs_path path; struct extent_buffer *leaf; struct btrfs_key key; u64 last; int ret = 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - root = root->fs_info->extent_root; last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET); + btrfs_init_path(&path); key.objectid = last; key.offset = 0; key.type = BTRFS_EXTENT_ITEM_KEY; - - ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); if (ret < 0) goto out; ret = 0; while (1) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(root, path); + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(root, &path); if (ret < 0) goto out; if (ret > 0) { @@ -5664,13 +6010,13 @@ static int verify_space_cache(struct btrfs_root *root, break; } } - leaf = path->nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + leaf = path.nodes[0]; + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.objectid >= cache->key.offset + cache->key.objectid) break; if (key.type != BTRFS_EXTENT_ITEM_KEY && key.type != BTRFS_METADATA_ITEM_KEY) { - path->slots[0]++; + path.slots[0]++; continue; } @@ -5679,7 +6025,7 @@ static int verify_space_cache(struct btrfs_root *root, last = key.objectid + key.offset; else last = key.objectid + root->nodesize; - path->slots[0]++; + path.slots[0]++; continue; } @@ -5691,7 +6037,7 @@ static int verify_space_cache(struct btrfs_root *root, last = key.objectid + key.offset; else last = key.objectid + root->nodesize; - path->slots[0]++; + path.slots[0]++; } if (last < cache->key.objectid + cache->key.offset) @@ -5700,7 +6046,7 @@ static int verify_space_cache(struct btrfs_root *root, cache->key.offset - last); out: - btrfs_free_path(path); + btrfs_release_path(&path); if (!ret && !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) { @@ -5826,7 +6172,7 @@ again: csum = btrfs_csum_data(NULL, (char *)data + tmp, csum, root->sectorsize); - btrfs_csum_final(csum, (char *)&csum); + btrfs_csum_final(csum, (u8 *)&csum); csum_offset = leaf_offset + tmp / root->sectorsize * csum_size; @@ -5857,33 +6203,28 @@ out: static int check_extent_exists(struct btrfs_root *root, u64 bytenr, u64 num_bytes) { - struct btrfs_path *path; + struct btrfs_path path; struct extent_buffer *leaf; struct btrfs_key key; int ret; - path = btrfs_alloc_path(); - if (!path) { - fprintf(stderr, "Error allocating path\n"); - return -ENOMEM; - } - + btrfs_init_path(&path); key.objectid = bytenr; key.type = BTRFS_EXTENT_ITEM_KEY; key.offset = (u64)-1; again: - ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path, + ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path, 0, 0); if (ret < 0) { fprintf(stderr, "Error looking up extent record %d\n", ret); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } else if (ret) { - if (path->slots[0] > 0) { - path->slots[0]--; + if (path.slots[0] > 0) { + path.slots[0]--; } else { - ret = btrfs_prev_leaf(root, path); + ret = btrfs_prev_leaf(root, &path); if (ret < 0) { goto out; } else if (ret > 0) { @@ -5893,7 +6234,7 @@ again: } } - btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); /* * Block group items come before extent items if they have the same @@ -5904,10 +6245,10 @@ again: * EXTENT_ITEM_KEY please? */ while (key.type > BTRFS_EXTENT_ITEM_KEY) { - if (path->slots[0] > 0) { - path->slots[0]--; + if (path.slots[0] > 0) { + path.slots[0]--; } else { - ret = btrfs_prev_leaf(root, path); + ret = btrfs_prev_leaf(root, &path); if (ret < 0) { goto out; } else if (ret > 0) { @@ -5915,29 +6256,29 @@ again: goto out; } } - btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); } while (num_bytes) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(root, path); + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(root, &path); if (ret < 0) { fprintf(stderr, "Error going to next leaf " "%d\n", ret); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } else if (ret) { break; } } - leaf = path->nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + leaf = path.nodes[0]; + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.type != BTRFS_EXTENT_ITEM_KEY) { - path->slots[0]++; + path.slots[0]++; continue; } if (key.objectid + key.offset < bytenr) { - path->slots[0]++; + path.slots[0]++; continue; } if (key.objectid > bytenr + num_bytes) @@ -5970,7 +6311,7 @@ again: * in real life, but no harm in coding it up * anyway just in case. */ - btrfs_release_path(path); + btrfs_release_path(&path); ret = check_extent_exists(root, new_start, new_bytes); if (ret) { @@ -5983,7 +6324,7 @@ again: } num_bytes = key.objectid - bytenr; } - path->slots[0]++; + path.slots[0]++; } ret = 0; @@ -5994,13 +6335,13 @@ out: ret = 1; } - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } static int check_csums(struct btrfs_root *root) { - struct btrfs_path *path; + struct btrfs_path path; struct extent_buffer *leaf; struct btrfs_key key; u64 offset = 0, num_bytes = 0; @@ -6016,28 +6357,24 @@ static int check_csums(struct btrfs_root *root) return -ENOENT; } + btrfs_init_path(&path); key.objectid = BTRFS_EXTENT_CSUM_OBJECTID; key.type = BTRFS_EXTENT_CSUM_KEY; key.offset = 0; - - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - - ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); if (ret < 0) { fprintf(stderr, "Error searching csum tree %d\n", ret); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } - if (ret > 0 && path->slots[0]) - path->slots[0]--; + if (ret > 0 && path.slots[0]) + path.slots[0]--; ret = 0; while (1) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(root, path); + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(root, &path); if (ret < 0) { fprintf(stderr, "Error going to next leaf " "%d\n", ret); @@ -6046,19 +6383,19 @@ static int check_csums(struct btrfs_root *root) if (ret) break; } - leaf = path->nodes[0]; + leaf = path.nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.type != BTRFS_EXTENT_CSUM_KEY) { - path->slots[0]++; + path.slots[0]++; continue; } - data_len = (btrfs_item_size_nr(leaf, path->slots[0]) / + data_len = (btrfs_item_size_nr(leaf, path.slots[0]) / csum_size) * root->sectorsize; if (!check_data_csum) goto skip_csum_check; - leaf_offset = btrfs_item_ptr_offset(leaf, path->slots[0]); + leaf_offset = btrfs_item_ptr_offset(leaf, path.slots[0]); ret = check_extent_csums(root, key.offset, data_len, leaf_offset, leaf); if (ret) @@ -6078,10 +6415,10 @@ skip_csum_check: num_bytes = 0; } num_bytes += data_len; - path->slots[0]++; + path.slots[0]++; } - btrfs_free_path(path); + btrfs_release_path(&path); return errors; } @@ -6133,7 +6470,9 @@ static int calc_extent_flag(struct btrfs_root *root, cache = lookup_cache_extent(extent_cache, buf->start, 1); /* we have added this extent before */ - BUG_ON(!cache); + if (!cache) + return -ENOENT; + rec = container_of(cache, struct extent_record, cache); /* @@ -6649,7 +6988,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans, back->node.found_extent_tree = 0; if (!back->node.found_extent_tree && back->node.found_ref) { - rb_erase(&back->node.node, &rec->backref_tree); + list_del(&back->node.list); free(back); } } else { @@ -6668,7 +7007,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans, back->node.found_extent_tree = 0; } if (!back->node.found_extent_tree && back->node.found_ref) { - rb_erase(&back->node.node, &rec->backref_tree); + list_del(&back->node.list); free(back); } } @@ -6773,7 +7112,6 @@ static int record_extent(struct btrfs_trans_handle *trans, struct extent_buffer *leaf; struct btrfs_key ins_key; struct btrfs_extent_item *ei; - struct tree_backref *tback; struct data_backref *dback; struct btrfs_tree_block_info *bi; @@ -6809,7 +7147,6 @@ static int record_extent(struct btrfs_trans_handle *trans, } else { struct btrfs_disk_key copy_key;; - tback = to_tree_backref(back); bi = (struct btrfs_tree_block_info *)(ei + 1); memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi)); @@ -6875,6 +7212,7 @@ static int record_extent(struct btrfs_trans_handle *trans, dback->found_ref); } else { u64 parent; + struct tree_backref *tback; tback = to_tree_backref(back); if (back->full_backref) @@ -6912,11 +7250,6 @@ static struct extent_entry *find_most_right_entry(struct list_head *entries) struct extent_entry *entry, *best = NULL, *prev = NULL; list_for_each_entry(entry, entries, list) { - if (!prev) { - prev = entry; - continue; - } - /* * If there are as many broken entries as entries then we know * not to trust this particular entry. @@ -6925,6 +7258,16 @@ static struct extent_entry *find_most_right_entry(struct list_head *entries) continue; /* + * Special case, when there are only two entries and 'best' is + * the first one + */ + if (!prev) { + best = entry; + prev = entry; + continue; + } + + /* * If our current entry == best then we can't be sure our best * is really the best, so we need to keep searching. */ @@ -7105,7 +7448,7 @@ out: static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, struct extent_record *rec) { - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct extent_entry *entry, *best = NULL; LIST_HEAD(entries); @@ -7121,8 +7464,7 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, if (rec->metadata) return 0; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data) continue; @@ -7248,8 +7590,7 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, * Ok great we all agreed on an extent record, let's go find the real * references and fix up the ones that don't match. */ - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data) continue; @@ -7372,17 +7713,13 @@ static int delete_duplicate_records(struct btrfs_root *root, { struct btrfs_trans_handle *trans; LIST_HEAD(delete_list); - struct btrfs_path *path; + struct btrfs_path path; struct extent_record *tmp, *good, *n; int nr_del = 0; int ret = 0, err; struct btrfs_key key; - path = btrfs_alloc_path(); - if (!path) { - ret = -ENOMEM; - goto out; - } + btrfs_init_path(&path); good = rec; /* Find the record that covers all of the duplicates. */ @@ -7434,16 +7771,16 @@ static int delete_duplicate_records(struct btrfs_root *root, abort(); } - ret = btrfs_search_slot(trans, root, &key, path, -1, 1); + ret = btrfs_search_slot(trans, root, &key, &path, -1, 1); if (ret) { if (ret > 0) ret = -EINVAL; break; } - ret = btrfs_del_item(trans, root, path); + ret = btrfs_del_item(trans, root, &path); if (ret) break; - btrfs_release_path(path); + btrfs_release_path(&path); nr_del++; } err = btrfs_commit_transaction(trans, root); @@ -7464,7 +7801,7 @@ out: free(tmp); } - btrfs_free_path(path); + btrfs_release_path(&path); if (!ret && !nr_del) rec->num_duplicates = 0; @@ -7478,7 +7815,7 @@ static int find_possible_backrefs(struct btrfs_fs_info *info, struct extent_record *rec) { struct btrfs_root *root; - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct cache_extent *cache; struct btrfs_file_extent_item *fi; @@ -7486,8 +7823,7 @@ static int find_possible_backrefs(struct btrfs_fs_info *info, u64 bytenr, bytes; int ret; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { /* Don't care about full backrefs (poor unloved backrefs) */ if (back->full_backref || !back->is_data) continue; @@ -7575,20 +7911,17 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info, { struct btrfs_key key; struct btrfs_root *dest_root; - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct orphan_data_extent *orphan; - struct btrfs_path *path; + struct btrfs_path path; int recorded_data_ref = 0; int ret = 0; if (rec->metadata) return 1; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + btrfs_init_path(&path); + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data || !back->found_extent_tree) continue; @@ -7609,7 +7942,8 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info, key.type = BTRFS_EXTENT_DATA_KEY; key.offset = dback->offset; - ret = btrfs_search_slot(NULL, dest_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, dest_root, &key, &path, 0, 0); + btrfs_release_path(&path); /* * For ret < 0, it's OK since the fs-tree may be corrupted, * we need to record it for inode/file extent rebuild. @@ -7636,7 +7970,7 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info, recorded_data_ref = 1; } out: - btrfs_free_path(path); + btrfs_release_path(&path); if (!ret) return !recorded_data_ref; else @@ -7654,19 +7988,17 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, { struct btrfs_trans_handle *trans = NULL; int ret; - struct btrfs_path *path; + struct btrfs_path path; + struct list_head *cur = rec->backrefs.next; struct cache_extent *cache; - struct extent_backref *back, *tmp; + struct extent_backref *back; int allocated = 0; u64 flags = 0; if (rec->flag_block_full_backref) flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); if (rec->refs != rec->extent_item_refs && !rec->metadata) { /* * Sometimes the backrefs themselves are so broken they don't @@ -7675,13 +8007,13 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, * them into the list if we find the backref so that * verify_backrefs can figure out what to do. */ - ret = find_possible_backrefs(info, path, extent_cache, rec); + ret = find_possible_backrefs(info, &path, extent_cache, rec); if (ret < 0) goto out; } /* step one, make sure all of the backrefs agree */ - ret = verify_backrefs(info, path, rec); + ret = verify_backrefs(info, &path, rec); if (ret < 0) goto out; @@ -7692,7 +8024,7 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, } /* step two, delete all the existing records */ - ret = delete_extent_records(trans, info->extent_root, path, + ret = delete_extent_records(trans, info->extent_root, &path, rec->start, rec->max_size); if (ret < 0) @@ -7707,8 +8039,10 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, } /* step three, recreate all the refs we did find */ - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + while(cur != &rec->backrefs) { + back = to_extent_backref(cur); + cur = cur->next; + /* * if we didn't find any references, don't create a * new extent record @@ -7717,7 +8051,7 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, continue; rec->bad_full_backref = 0; - ret = record_extent(trans, info, path, rec, back, allocated, flags); + ret = record_extent(trans, info, &path, rec, back, allocated, flags); allocated = 1; if (ret) @@ -7730,7 +8064,7 @@ out: ret = err; } - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -7739,7 +8073,7 @@ static int fixup_extent_flags(struct btrfs_fs_info *fs_info, { struct btrfs_trans_handle *trans; struct btrfs_root *root = fs_info->extent_root; - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_extent_item *ei; struct btrfs_key key; u64 flags; @@ -7754,32 +8088,27 @@ static int fixup_extent_flags(struct btrfs_fs_info *fs_info, key.offset = rec->max_size; } - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 0); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + btrfs_init_path(&path); + ret = btrfs_search_slot(trans, root, &key, &path, 0, 1); if (ret < 0) { - btrfs_free_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, root); return ret; } else if (ret) { fprintf(stderr, "Didn't find extent for %llu\n", (unsigned long long)rec->start); - btrfs_free_path(path); + btrfs_release_path(&path); btrfs_commit_transaction(trans, root); return -ENOENT; } - ei = btrfs_item_ptr(path->nodes[0], path->slots[0], + ei = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_extent_item); - flags = btrfs_extent_flags(path->nodes[0], ei); + flags = btrfs_extent_flags(path.nodes[0], ei); if (rec->flag_block_full_backref) { fprintf(stderr, "setting full backref on %llu\n", (unsigned long long)key.objectid); @@ -7789,9 +8118,9 @@ static int fixup_extent_flags(struct btrfs_fs_info *fs_info, (unsigned long long)key.objectid); flags &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF; } - btrfs_set_extent_flags(path->nodes[0], ei, flags); - btrfs_mark_buffer_dirty(path->nodes[0]); - btrfs_free_path(path); + btrfs_set_extent_flags(path.nodes[0], ei, flags); + btrfs_mark_buffer_dirty(path.nodes[0]); + btrfs_release_path(&path); return btrfs_commit_transaction(trans, root); } @@ -8573,7 +8902,7 @@ again: btrfs_init_path(&path); key.offset = 0; key.objectid = 0; - btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY); + key.type = BTRFS_ROOT_ITEM_KEY; ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path, 0, 0); if (ret < 0) @@ -8589,7 +8918,7 @@ again: slot = path.slots[0]; } btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]); - if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) { + if (found_key.type == BTRFS_ROOT_ITEM_KEY) { unsigned long offset; u64 last_snapshot; @@ -9150,9 +9479,10 @@ static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id, free_extent_buffer(eb); btrfs_init_path(&path); + path.lowest_level = level; /* Search with the first key, to ensure we can reach it */ ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret) { + if (ret < 0) { err |= REFERENCER_MISSING; goto release_out; } @@ -9270,7 +9600,7 @@ static int check_extent_data_backref(struct btrfs_fs_info *fs_info, btrfs_release_path(&path); } key.objectid = root_id; - btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY); + key.type = BTRFS_ROOT_ITEM_KEY; key.offset = (u64)-1; btrfs_init_path(&path); @@ -9422,7 +9752,8 @@ static int check_extent_item(struct btrfs_fs_info *fs_info, if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) metadata = 1; - if (metadata && check_crossing_stripes(key.objectid, eb->len)) { + if (metadata && check_crossing_stripes(global_info, key.objectid, + eb->len)) { error("bad metadata [%llu, %llu) crossing stripe boundary", key.objectid, key.objectid + nodesize); err |= CROSSING_STRIPE_BOUNDARY; @@ -9870,7 +10201,7 @@ static int check_leaf_items(struct btrfs_root *root, struct extent_buffer *eb) next: btrfs_item_key_to_cpu(eb, &key, slot); - type = btrfs_key_type(&key); + type = key.type; switch (type) { case BTRFS_EXTENT_DATA_KEY: @@ -10035,6 +10366,8 @@ static int traverse_tree_block(struct btrfs_root *root, struct extent_buffer *node) { struct extent_buffer *eb; + struct btrfs_key key; + struct btrfs_key drop_key; int level; u64 nr; int i; @@ -10080,6 +10413,7 @@ static int traverse_tree_block(struct btrfs_root *root, } nr = btrfs_header_nritems(node); + btrfs_disk_key_to_cpu(&drop_key, &root->root_item.drop_progress); btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) - nr) * sizeof(struct btrfs_key_ptr); @@ -10087,6 +10421,11 @@ static int traverse_tree_block(struct btrfs_root *root, for (i = 0; i < nr; i++) { u64 blocknr = btrfs_node_blockptr(node, i); + btrfs_node_key_to_cpu(node, &key, i); + if (level == root->root_item.drop_level && + is_dropped_key(&key, &drop_key)) + continue; + /* * As a btrfs tree has most 8 levels (0..7), so it's quite safe * to call the function itself. @@ -10320,24 +10659,20 @@ static int pin_metadata_blocks(struct btrfs_fs_info *fs_info) static int reset_block_groups(struct btrfs_fs_info *fs_info) { struct btrfs_block_group_cache *cache; - struct btrfs_path *path; + struct btrfs_path path; struct extent_buffer *leaf; struct btrfs_chunk *chunk; struct btrfs_key key; int ret; u64 start; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); key.objectid = 0; key.type = BTRFS_CHUNK_ITEM_KEY; key.offset = 0; - - ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, &path, 0, 0); if (ret < 0) { - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -10352,10 +10687,10 @@ static int reset_block_groups(struct btrfs_fs_info *fs_info) /* First we need to create the in-memory block groups */ while (1) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(fs_info->chunk_root, path); + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(fs_info->chunk_root, &path); if (ret < 0) { - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } if (ret) { @@ -10363,15 +10698,14 @@ static int reset_block_groups(struct btrfs_fs_info *fs_info) break; } } - leaf = path->nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + leaf = path.nodes[0]; + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.type != BTRFS_CHUNK_ITEM_KEY) { - path->slots[0]++; + path.slots[0]++; continue; } - chunk = btrfs_item_ptr(leaf, path->slots[0], - struct btrfs_chunk); + chunk = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_chunk); btrfs_add_block_group(fs_info, 0, btrfs_chunk_type(leaf, chunk), key.objectid, key.offset, @@ -10379,7 +10713,7 @@ static int reset_block_groups(struct btrfs_fs_info *fs_info) set_extent_dirty(&fs_info->free_space_cache, key.offset, key.offset + btrfs_chunk_length(leaf, chunk), GFP_NOFS); - path->slots[0]++; + path.slots[0]++; } start = 0; while (1) { @@ -10390,7 +10724,7 @@ static int reset_block_groups(struct btrfs_fs_info *fs_info) start = cache->key.objectid + cache->key.offset; } - btrfs_free_path(path); + btrfs_release_path(&path); return 0; } @@ -10398,22 +10732,18 @@ static int reset_balance(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info) { struct btrfs_root *root = fs_info->tree_root; - struct btrfs_path *path; + struct btrfs_path path; struct extent_buffer *leaf; struct btrfs_key key; int del_slot, del_nr = 0; int ret; int found = 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); key.objectid = BTRFS_BALANCE_OBJECTID; key.type = BTRFS_BALANCE_ITEM_KEY; key.offset = 0; - - ret = btrfs_search_slot(trans, root, &key, path, -1, 1); + ret = btrfs_search_slot(trans, root, &key, &path, -1, 1); if (ret) { if (ret > 0) ret = 0; @@ -10423,64 +10753,63 @@ static int reset_balance(struct btrfs_trans_handle *trans, goto out; } - ret = btrfs_del_item(trans, root, path); + ret = btrfs_del_item(trans, root, &path); if (ret) goto out; - btrfs_release_path(path); + btrfs_release_path(&path); key.objectid = BTRFS_TREE_RELOC_OBJECTID; key.type = BTRFS_ROOT_ITEM_KEY; key.offset = 0; - - ret = btrfs_search_slot(trans, root, &key, path, -1, 1); + ret = btrfs_search_slot(trans, root, &key, &path, -1, 1); if (ret < 0) goto out; while (1) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { if (!found) break; if (del_nr) { - ret = btrfs_del_items(trans, root, path, + ret = btrfs_del_items(trans, root, &path, del_slot, del_nr); del_nr = 0; if (ret) goto out; } key.offset++; - btrfs_release_path(path); + btrfs_release_path(&path); found = 0; - ret = btrfs_search_slot(trans, root, &key, path, + ret = btrfs_search_slot(trans, root, &key, &path, -1, 1); if (ret < 0) goto out; continue; } found = 1; - leaf = path->nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + leaf = path.nodes[0]; + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.objectid > BTRFS_TREE_RELOC_OBJECTID) break; if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) { - path->slots[0]++; + path.slots[0]++; continue; } if (!del_nr) { - del_slot = path->slots[0]; + del_slot = path.slots[0]; del_nr = 1; } else { del_nr++; } - path->slots[0]++; + path.slots[0]++; } if (del_nr) { - ret = btrfs_del_items(trans, root, path, del_slot, del_nr); + ret = btrfs_del_items(trans, root, &path, del_slot, del_nr); if (ret) goto out; } - btrfs_release_path(path); + btrfs_release_path(&path); reinit_data_reloc: key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID; @@ -10498,7 +10827,7 @@ reinit_data_reloc: goto out; ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID); out: - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -10588,7 +10917,7 @@ static int reinit_extent_tree(struct btrfs_trans_handle *trans, static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb) { - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_trans_handle *trans; struct btrfs_key key; int ret; @@ -10605,31 +10934,26 @@ static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb return PTR_ERR(root); } - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } - path->lowest_level = btrfs_header_level(eb); - if (path->lowest_level) + btrfs_init_path(&path); + path.lowest_level = btrfs_header_level(eb); + if (path.lowest_level) btrfs_node_key_to_cpu(eb, &key, 0); else btrfs_item_key_to_cpu(eb, &key, 0); - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + ret = btrfs_search_slot(trans, root, &key, &path, 0, 1); btrfs_commit_transaction(trans, root); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad) { - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_trans_handle *trans; struct btrfs_key key; int ret; @@ -10647,26 +10971,21 @@ static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad) return PTR_ERR(root); } - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - btrfs_free_path(path); + if (IS_ERR(trans)) return PTR_ERR(trans); - } - ret = btrfs_search_slot(trans, root, &bad->key, path, -1, 1); + btrfs_init_path(&path); + ret = btrfs_search_slot(trans, root, &bad->key, &path, -1, 1); if (ret) { if (ret > 0) ret = 0; goto out; } - ret = btrfs_del_item(trans, root, path); + ret = btrfs_del_item(trans, root, &path); out: btrfs_commit_transaction(trans, root); - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -10713,7 +11032,7 @@ static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans, struct btrfs_root *csum_root, struct btrfs_root *cur_root) { - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_key key; struct extent_buffer *node; struct btrfs_file_extent_item *fi; @@ -10723,30 +11042,25 @@ static int fill_csum_tree_from_one_fs_root(struct btrfs_trans_handle *trans, int slot = 0; int ret = 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; buf = malloc(cur_root->fs_info->csum_root->sectorsize); - if (!buf) { - ret = -ENOMEM; - goto out; - } + if (!buf) + return -ENOMEM; + btrfs_init_path(&path); key.objectid = 0; key.offset = 0; key.type = 0; - - ret = btrfs_search_slot(NULL, cur_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, cur_root, &key, &path, 0, 0); if (ret < 0) goto out; /* Iterate all regular file extents and fill its csum */ while (1) { - btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); if (key.type != BTRFS_EXTENT_DATA_KEY) goto next; - node = path->nodes[0]; - slot = path->slots[0]; + node = path.nodes[0]; + slot = path.slots[0]; fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item); if (btrfs_file_extent_type(node, fi) != BTRFS_FILE_EXTENT_REG) goto next; @@ -10763,7 +11077,7 @@ next: * TODO: if next leaf is corrupted, jump to nearest next valid * leaf. */ - ret = btrfs_next_item(cur_root, path); + ret = btrfs_next_item(cur_root, &path); if (ret < 0) goto out; if (ret > 0) { @@ -10773,7 +11087,7 @@ next: } out: - btrfs_free_path(path); + btrfs_release_path(&path); free(buf); return ret; } @@ -10782,7 +11096,7 @@ static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans, struct btrfs_root *csum_root) { struct btrfs_fs_info *fs_info = csum_root->fs_info; - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_root *tree_root = fs_info->tree_root; struct btrfs_root *cur_root; struct extent_buffer *node; @@ -10790,15 +11104,11 @@ static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans, int slot = 0; int ret = 0; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); key.objectid = BTRFS_FS_TREE_OBJECTID; key.offset = 0; key.type = BTRFS_ROOT_ITEM_KEY; - - ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0); if (ret < 0) goto out; if (ret > 0) { @@ -10807,8 +11117,8 @@ static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans, } while (1) { - node = path->nodes[0]; - slot = path->slots[0]; + node = path.nodes[0]; + slot = path.slots[0]; btrfs_item_key_to_cpu(node, &key, slot); if (key.objectid > BTRFS_LAST_FREE_OBJECTID) goto out; @@ -10829,7 +11139,7 @@ static int fill_csum_tree_from_fs(struct btrfs_trans_handle *trans, if (ret < 0) goto out; next: - ret = btrfs_next_item(tree_root, path); + ret = btrfs_next_item(tree_root, &path); if (ret > 0) { ret = 0; goto out; @@ -10839,7 +11149,7 @@ next: } out: - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -10847,36 +11157,32 @@ static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans, struct btrfs_root *csum_root) { struct btrfs_root *extent_root = csum_root->fs_info->extent_root; - struct btrfs_path *path; + struct btrfs_path path; struct btrfs_extent_item *ei; struct extent_buffer *leaf; char *buf; struct btrfs_key key; int ret; - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); key.objectid = 0; key.type = BTRFS_EXTENT_ITEM_KEY; key.offset = 0; - - ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); if (ret < 0) { - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } buf = malloc(csum_root->sectorsize); if (!buf) { - btrfs_free_path(path); + btrfs_release_path(&path); return -ENOMEM; } while (1) { - if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { - ret = btrfs_next_leaf(extent_root, path); + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) { + ret = btrfs_next_leaf(extent_root, &path); if (ret < 0) break; if (ret) { @@ -10884,19 +11190,19 @@ static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans, break; } } - leaf = path->nodes[0]; + leaf = path.nodes[0]; - btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); + btrfs_item_key_to_cpu(leaf, &key, path.slots[0]); if (key.type != BTRFS_EXTENT_ITEM_KEY) { - path->slots[0]++; + path.slots[0]++; continue; } - ei = btrfs_item_ptr(leaf, path->slots[0], + ei = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_extent_item); if (!(btrfs_extent_flags(leaf, ei) & BTRFS_EXTENT_FLAG_DATA)) { - path->slots[0]++; + path.slots[0]++; continue; } @@ -10904,10 +11210,10 @@ static int fill_csum_tree_from_extent(struct btrfs_trans_handle *trans, key.offset); if (ret) break; - path->slots[0]++; + path.slots[0]++; } - btrfs_free_path(path); + btrfs_release_path(&path); free(buf); return ret; } @@ -10955,7 +11261,7 @@ static int build_roots_info_cache(struct btrfs_fs_info *info) int ret = 0; struct btrfs_key key; struct extent_buffer *leaf; - struct btrfs_path *path; + struct btrfs_path path; if (!roots_info_cache) { roots_info_cache = malloc(sizeof(*roots_info_cache)); @@ -10964,24 +11270,20 @@ static int build_roots_info_cache(struct btrfs_fs_info *info) cache_tree_init(roots_info_cache); } - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - + btrfs_init_path(&path); key.objectid = 0; key.type = BTRFS_EXTENT_ITEM_KEY; key.offset = 0; - - ret = btrfs_search_slot(NULL, info->extent_root, &key, path, 0, 0); + ret = btrfs_search_slot(NULL, info->extent_root, &key, &path, 0, 0); if (ret < 0) goto out; - leaf = path->nodes[0]; + leaf = path.nodes[0]; while (1) { struct btrfs_key found_key; struct btrfs_extent_item *ei; struct btrfs_extent_inline_ref *iref; - int slot = path->slots[0]; + int slot = path.slots[0]; int type; u64 flags; u64 root_id; @@ -10990,18 +11292,18 @@ static int build_roots_info_cache(struct btrfs_fs_info *info) struct root_item_info *rii; if (slot >= btrfs_header_nritems(leaf)) { - ret = btrfs_next_leaf(info->extent_root, path); + ret = btrfs_next_leaf(info->extent_root, &path); if (ret < 0) { break; } else if (ret) { ret = 0; break; } - leaf = path->nodes[0]; - slot = path->slots[0]; + leaf = path.nodes[0]; + slot = path.slots[0]; } - btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); + btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]); if (found_key.type != BTRFS_EXTENT_ITEM_KEY && found_key.type != BTRFS_METADATA_ITEM_KEY) @@ -11064,11 +11366,11 @@ static int build_roots_info_cache(struct btrfs_fs_info *info) rii->node_count++; } next: - path->slots[0]++; + path.slots[0]++; } out: - btrfs_free_path(path); + btrfs_release_path(&path); return ret; } @@ -11164,7 +11466,7 @@ static int maybe_repair_root_item(struct btrfs_fs_info *info, */ static int repair_root_items(struct btrfs_fs_info *info) { - struct btrfs_path *path = NULL; + struct btrfs_path path; struct btrfs_key key; struct extent_buffer *leaf; struct btrfs_trans_handle *trans = NULL; @@ -11172,16 +11474,12 @@ static int repair_root_items(struct btrfs_fs_info *info) int bad_roots = 0; int need_trans = 0; + btrfs_init_path(&path); + ret = build_roots_info_cache(info); if (ret) goto out; - path = btrfs_alloc_path(); - if (!path) { - ret = -ENOMEM; - goto out; - } - key.objectid = BTRFS_FIRST_FREE_OBJECTID; key.type = BTRFS_ROOT_ITEM_KEY; key.offset = 0; @@ -11200,19 +11498,19 @@ again: } } - ret = btrfs_search_slot(trans, info->tree_root, &key, path, + ret = btrfs_search_slot(trans, info->tree_root, &key, &path, 0, trans ? 1 : 0); if (ret < 0) goto out; - leaf = path->nodes[0]; + leaf = path.nodes[0]; while (1) { struct btrfs_key found_key; - if (path->slots[0] >= btrfs_header_nritems(leaf)) { - int no_more_keys = find_next_key(path, &key); + if (path.slots[0] >= btrfs_header_nritems(leaf)) { + int no_more_keys = find_next_key(&path, &key); - btrfs_release_path(path); + btrfs_release_path(&path); if (trans) { ret = btrfs_commit_transaction(trans, info->tree_root); @@ -11226,14 +11524,14 @@ again: goto again; } - btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); + btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]); if (found_key.type != BTRFS_ROOT_ITEM_KEY) goto next; if (found_key.objectid == BTRFS_TREE_RELOC_OBJECTID) goto next; - ret = maybe_repair_root_item(info, path, &found_key, + ret = maybe_repair_root_item(info, &path, &found_key, trans ? 0 : 1); if (ret < 0) goto out; @@ -11241,18 +11539,18 @@ again: if (!trans && repair) { need_trans = 1; key = found_key; - btrfs_release_path(path); + btrfs_release_path(&path); goto again; } bad_roots++; } next: - path->slots[0]++; + path.slots[0]++; } ret = 0; out: free_roots_info_cache(); - btrfs_free_path(path); + btrfs_release_path(&path); if (trans) btrfs_commit_transaction(trans, info->tree_root); if (ret < 0) @@ -11261,6 +11559,36 @@ out: return bad_roots; } +static int clear_free_space_cache(struct btrfs_fs_info *fs_info) +{ + struct btrfs_trans_handle *trans; + struct btrfs_block_group_cache *bg_cache; + u64 current = 0; + int ret = 0; + + /* Clear all free space cache inodes and its extent data */ + while (1) { + bg_cache = btrfs_lookup_first_block_group(fs_info, current); + if (!bg_cache) + break; + ret = btrfs_clear_free_space_cache(fs_info, bg_cache); + if (ret < 0) + return ret; + current = bg_cache->key.objectid + bg_cache->key.offset; + } + + /* Don't forget to set cache_generation to -1 */ + trans = btrfs_start_transaction(fs_info->tree_root, 0); + if (IS_ERR(trans)) { + error("failed to update super block cache generation"); + return PTR_ERR(trans); + } + btrfs_set_super_cache_generation(fs_info->super_copy, (u64)-1); + btrfs_commit_transaction(trans, fs_info->tree_root); + + return ret; +} + const char * const cmd_check_usage[] = { "btrfs check [options] ", "Check structural integrity of a filesystem (unmounted).", @@ -11275,19 +11603,20 @@ const char * const cmd_check_usage[] = { "--readonly run in read-only mode (default)", "--init-csum-tree create a new CRC tree", "--init-extent-tree create a new extent tree", - "--mode select mode, allows to make some memory/IO", - " trade-offs, where MODE is one of:", + "--mode allows choice of memory/IO trade-offs", + " where MODE is one of:", " original - read inodes and extents to memory (requires", " more memory, does less IO)", " lowmem - try to use less memory but read blocks again", " when needed", "--check-data-csum verify checksums of data blocks", - "-Q|--qgroup-report print a report on qgroup consistency", + "-Q|--qgroup-report print a report on qgroup consistency", "-E|--subvol-extents ", " print subvolume extents and sharing state", "-r|--tree-root use the given bytenr for the tree root", "--chunk-root use the given bytenr for the chunk tree root", "-p|--progress indicate progress", + "--clear-space-cache v1|v2 clear space cache for v1 or v2", NULL }; @@ -11305,6 +11634,7 @@ int cmd_check(int argc, char **argv) u64 num; int init_csum_tree = 0; int readonly = 0; + int clear_space_cache = 0; int qgroup_report = 0; int qgroups_repaired = 0; unsigned ctree_flags = OPEN_CTREE_EXCLUSIVE; @@ -11314,7 +11644,7 @@ int cmd_check(int argc, char **argv) enum { GETOPT_VAL_REPAIR = 257, GETOPT_VAL_INIT_CSUM, GETOPT_VAL_INIT_EXTENT, GETOPT_VAL_CHECK_CSUM, GETOPT_VAL_READONLY, GETOPT_VAL_CHUNK_TREE, - GETOPT_VAL_MODE }; + GETOPT_VAL_MODE, GETOPT_VAL_CLEAR_SPACE_CACHE }; static const struct option long_options[] = { { "super", required_argument, NULL, 's' }, { "repair", no_argument, NULL, GETOPT_VAL_REPAIR }, @@ -11334,6 +11664,8 @@ int cmd_check(int argc, char **argv) { "progress", no_argument, NULL, 'p' }, { "mode", required_argument, NULL, GETOPT_VAL_MODE }, + { "clear-space-cache", required_argument, NULL, + GETOPT_VAL_CLEAR_SPACE_CACHE}, { NULL, 0, NULL, 0} }; @@ -11348,8 +11680,8 @@ int cmd_check(int argc, char **argv) case 's': num = arg_strtou64(optarg); if (num >= BTRFS_SUPER_MIRROR_MAX) { - fprintf(stderr, - "ERROR: super mirror should be less than: %d\n", + error( + "super mirror should be less than %d", BTRFS_SUPER_MIRROR_MAX); exit(1); } @@ -11405,6 +11737,19 @@ int cmd_check(int argc, char **argv) exit(1); } break; + case GETOPT_VAL_CLEAR_SPACE_CACHE: + if (strcmp(optarg, "v1") == 0) { + clear_space_cache = 1; + } else if (strcmp(optarg, "v2") == 0) { + clear_space_cache = 2; + ctree_flags |= OPEN_CTREE_INVALIDATE_FST; + } else { + error( + "invalid argument to --clear-space-cache, must be v1 or v2"); + exit(1); + } + ctree_flags |= OPEN_CTREE_WRITES; + break; } } @@ -11418,7 +11763,7 @@ int cmd_check(int argc, char **argv) /* This check is the only reason for --readonly to exist */ if (readonly && repair) { - fprintf(stderr, "Repair options are not compatible with --readonly\n"); + error("repair options are not compatible with --readonly"); exit(1); } @@ -11426,7 +11771,7 @@ int cmd_check(int argc, char **argv) * Not supported yet */ if (repair && check_mode == CHECK_MODE_LOWMEM) { - error("Low memory mode doesn't support repair yet"); + error("low memory mode doesn't support repair yet"); exit(1); } @@ -11434,10 +11779,10 @@ int cmd_check(int argc, char **argv) cache_tree_init(&root_cache); if((ret = check_mounted(argv[optind])) < 0) { - fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret)); + error("could not check mount status: %s", strerror(-ret)); goto err_out; } else if(ret) { - fprintf(stderr, "%s is currently mounted. Aborting.\n", argv[optind]); + error("%s is currently mounted, aborting", argv[optind]); ret = -EBUSY; goto err_out; } @@ -11449,27 +11794,61 @@ int cmd_check(int argc, char **argv) info = open_ctree_fs_info(argv[optind], bytenr, tree_root_bytenr, chunk_root_bytenr, ctree_flags); if (!info) { - fprintf(stderr, "Couldn't open file system\n"); + error("cannot open file system"); ret = -EIO; goto err_out; } global_info = info; root = info->fs_root; + if (clear_space_cache == 1) { + if (btrfs_fs_compat_ro(info, + BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) { + error( + "free space cache v2 detected, use --clear-space-cache v2"); + ret = 1; + goto close_out; + } + printf("Clearing free space cache\n"); + ret = clear_free_space_cache(info); + if (ret) { + error("failed to clear free space cache"); + ret = 1; + } else { + printf("Free space cache cleared\n"); + } + goto close_out; + } else if (clear_space_cache == 2) { + if (!btrfs_fs_compat_ro(info, + BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)) { + printf("no free space cache v2 to clear\n"); + ret = 0; + goto close_out; + } + printf("Clear free space cache v2\n"); + ret = btrfs_clear_free_space_tree(info); + if (ret) { + error("failed to clear free space cache v2: %d", ret); + ret = 1; + } else { + printf("free space cache v2 cleared\n"); + } + goto close_out; + } /* * repair mode will force us to commit transaction which * will make us fail to load log tree when mounting. */ if (repair && btrfs_super_log_root(info->super_copy)) { - ret = ask_user("repair mode will force to clear out log tree, Are you sure?"); + ret = ask_user("repair mode will force to clear out log tree, are you sure?"); if (!ret) { ret = 1; goto close_out; } ret = zero_log_tree(root); if (ret) { - fprintf(stderr, "fail to zero log tree\n"); + error("failed to zero log tree: %d", ret); goto close_out; } } @@ -11494,7 +11873,7 @@ int cmd_check(int argc, char **argv) if (!extent_buffer_uptodate(info->tree_root->node) || !extent_buffer_uptodate(info->dev_root->node) || !extent_buffer_uptodate(info->chunk_root->node)) { - fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n"); + error("critical roots corrupted, unable to check the filesystem"); ret = -EIO; goto close_out; } @@ -11504,7 +11883,7 @@ int cmd_check(int argc, char **argv) trans = btrfs_start_transaction(info->extent_root, 0); if (IS_ERR(trans)) { - fprintf(stderr, "Error starting transaction\n"); + error("error starting transaction"); ret = PTR_ERR(trans); goto close_out; } @@ -11517,10 +11896,11 @@ int cmd_check(int argc, char **argv) } if (init_csum_tree) { - fprintf(stderr, "Reinit crc root\n"); + printf("Reinitialize checksum tree\n"); ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0); if (ret) { - fprintf(stderr, "crc root initialization failed\n"); + error("checksum tree initialization failed: %d", + ret); ret = -EIO; goto close_out; } @@ -11528,7 +11908,7 @@ int cmd_check(int argc, char **argv) ret = fill_csum_tree(trans, info->csum_root, init_extent_tree); if (ret) { - fprintf(stderr, "crc refilling failed\n"); + error("checksum tree refilling failed: %d", ret); return -EIO; } } @@ -11541,12 +11921,12 @@ int cmd_check(int argc, char **argv) goto close_out; } if (!extent_buffer_uptodate(info->extent_root->node)) { - fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n"); + error("critical: extent_root, unable to check the filesystem"); ret = -EIO; goto close_out; } if (!extent_buffer_uptodate(info->csum_root->node)) { - fprintf(stderr, "Checksum root corrupted, rerun with --init-csum-tree option\n"); + error("critical: csum_root, unable to check the filesystem"); ret = -EIO; goto close_out; } @@ -11558,7 +11938,8 @@ int cmd_check(int argc, char **argv) else ret = check_chunks_and_extents(root); if (ret) - fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n"); + error( + "errors found in extent allocation tree or chunk allocation"); ret = repair_root_items(info); if (ret < 0) @@ -11644,7 +12025,7 @@ int cmd_check(int argc, char **argv) } if (!list_empty(&root->fs_info->recow_ebs)) { - fprintf(stderr, "Transid errors in file system\n"); + error("transid errors in file system"); ret = 1; } out: