X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=ctree.c;h=e26a1c29bb757964ae6eedfab9062acb7096b014;hb=7cdd58b2e92863f055c70ef7134d3a70760473c7;hp=1a4f3f06f38a0d59d8f09a33678bd9a1e87a4bb9;hpb=194aa4a1bd6447bb545286d0bcb0b0be8204d79f;p=platform%2Fupstream%2Fbtrfs-progs.git diff --git a/ctree.c b/ctree.c index 1a4f3f0..e26a1c2 100644 --- a/ctree.c +++ b/ctree.c @@ -20,6 +20,9 @@ #include "transaction.h" #include "print-tree.h" #include "repair.h" +#include "internal.h" +#include "sizes.h" +#include "messages.h" static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct btrfs_path *path, int level); @@ -42,21 +45,19 @@ inline void btrfs_init_path(struct btrfs_path *p) struct btrfs_path *btrfs_alloc_path(void) { struct btrfs_path *path; - path = kmalloc(sizeof(struct btrfs_path), GFP_NOFS); - if (path) { - btrfs_init_path(path); - path->reada = 0; - } + path = kzalloc(sizeof(struct btrfs_path), GFP_NOFS); return path; } void btrfs_free_path(struct btrfs_path *p) { - btrfs_release_path(NULL, p); + if (!p) + return; + btrfs_release_path(p); kfree(p); } -void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) +void btrfs_release_path(struct btrfs_path *p) { int i; for (i = 0; i < BTRFS_MAX_LEVEL; i++) { @@ -67,7 +68,7 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) memset(p, 0, sizeof(*p)); } -static void add_root_to_dirty_list(struct btrfs_root *root) +void add_root_to_dirty_list(struct btrfs_root *root) { if (root->track_dirty && list_empty(&root->dirty_list)) { list_add(&root->dirty_list, @@ -122,8 +123,7 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans, btrfs_set_header_owner(cow, new_root_objectid); write_extent_buffer(cow, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(cow), - BTRFS_FSID_SIZE); + btrfs_header_fsid(), BTRFS_FSID_SIZE); WARN_ON(btrfs_header_generation(buf) > trans->transid); ret = btrfs_inc_ref(trans, new_root, cow, 0); @@ -137,61 +137,14 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans, return 0; } -int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans, - struct btrfs_root *root, int overwrite) -{ - struct extent_buffer *c; - struct extent_buffer *old = root->node; - int level; - struct btrfs_disk_key disk_key = {0,0,0}; - - level = 0; - - if (overwrite) { - c = old; - extent_buffer_get(c); - goto init; - } - c = btrfs_alloc_free_block(trans, root, - btrfs_level_size(root, 0), - root->root_key.objectid, - &disk_key, level, 0, 0); - if (IS_ERR(c)) { - c = old; - extent_buffer_get(c); - } -init: - memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header)); - btrfs_set_header_level(c, level); - btrfs_set_header_bytenr(c, c->start); - btrfs_set_header_generation(c, trans->transid); - btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV); - btrfs_set_header_owner(c, root->root_key.objectid); - - write_extent_buffer(c, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(c), - BTRFS_FSID_SIZE); - - write_extent_buffer(c, root->fs_info->chunk_tree_uuid, - (unsigned long)btrfs_header_chunk_tree_uuid(c), - BTRFS_UUID_SIZE); - - btrfs_mark_buffer_dirty(c); - - free_extent_buffer(old); - root->node = c; - add_root_to_dirty_list(root); - return 0; -} - /* * check if the tree block can be shared by multiple trees */ -int btrfs_block_can_be_shared(struct btrfs_root *root, - struct extent_buffer *buf) +static int btrfs_block_can_be_shared(struct btrfs_root *root, + struct extent_buffer *buf) { /* - * Tree blocks not in refernece counted trees and tree roots + * Tree blocks not in reference counted trees and tree roots * are never shared. If a block was allocated after the last * snapshot and the block was not allocated by tree relocation, * we know the block is not shared. @@ -343,10 +296,10 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans, btrfs_set_header_owner(cow, root->root_key.objectid); write_extent_buffer(cow, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(cow), - BTRFS_FSID_SIZE); + btrfs_header_fsid(), BTRFS_FSID_SIZE); - WARN_ON(btrfs_header_generation(buf) > trans->transid); + WARN_ON(!(buf->flags & EXTENT_BAD_TRANSID) && + btrfs_header_generation(buf) > trans->transid); update_ref_for_cow(trans, root, buf, cow); @@ -370,6 +323,10 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans, btrfs_free_extent(trans, root, buf->start, buf->len, 0, root->root_key.objectid, level, 1); } + if (!list_empty(&buf->recow)) { + list_del_init(&buf->recow); + free_extent_buffer(buf); + } free_extent_buffer(buf); btrfs_mark_buffer_dirty(cow); *cow_ret = cow; @@ -413,214 +370,81 @@ int btrfs_cow_block(struct btrfs_trans_handle *trans, return 0; } - search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); + search_start = buf->start & ~((u64)SZ_1G - 1); ret = __btrfs_cow_block(trans, root, buf, parent, parent_slot, cow_ret, search_start, 0); return ret; } -/* -static int close_blocks(u64 blocknr, u64 other, u32 blocksize) +int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) { - if (blocknr < other && other - (blocknr + blocksize) < 32768) + if (k1->objectid > k2->objectid) return 1; - if (blocknr > other && blocknr - (other + blocksize) < 32768) + if (k1->objectid < k2->objectid) + return -1; + if (k1->type > k2->type) + return 1; + if (k1->type < k2->type) + return -1; + if (k1->offset > k2->offset) return 1; + if (k1->offset < k2->offset) + return -1; return 0; } -*/ /* * compare two keys in a memcmp fashion */ -int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) +static int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) { struct btrfs_key k1; btrfs_disk_key_to_cpu(&k1, disk); - - if (k1.objectid > k2->objectid) - return 1; - if (k1.objectid < k2->objectid) - return -1; - if (k1.type > k2->type) - return 1; - if (k1.type < k2->type) - return -1; - if (k1.offset > k2->offset) - return 1; - if (k1.offset < k2->offset) - return -1; - return 0; -} - - -#if 0 -int btrfs_realloc_node(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct extent_buffer *parent, - int start_slot, int cache_only, u64 *last_ret, - struct btrfs_key *progress) -{ - struct extent_buffer *cur; - struct extent_buffer *tmp; - u64 blocknr; - u64 gen; - u64 search_start = *last_ret; - u64 last_block = 0; - u64 other; - u32 parent_nritems; - int end_slot; - int i; - int err = 0; - int parent_level; - int uptodate; - u32 blocksize; - int progress_passed = 0; - struct btrfs_disk_key disk_key; - - parent_level = btrfs_header_level(parent); - if (cache_only && parent_level != 1) - return 0; - - if (trans->transaction != root->fs_info->running_transaction) { - printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, - root->fs_info->running_transaction->transid); - WARN_ON(1); - } - if (trans->transid != root->fs_info->generation) { - printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, - root->fs_info->generation); - WARN_ON(1); - } - - parent_nritems = btrfs_header_nritems(parent); - blocksize = btrfs_level_size(root, parent_level - 1); - end_slot = parent_nritems; - - if (parent_nritems == 1) - return 0; - - for (i = start_slot; i < end_slot; i++) { - int close = 1; - - if (!parent->map_token) { - map_extent_buffer(parent, - btrfs_node_key_ptr_offset(i), - sizeof(struct btrfs_key_ptr), - &parent->map_token, &parent->kaddr, - &parent->map_start, &parent->map_len, - KM_USER1); - } - btrfs_node_key(parent, &disk_key, i); - if (!progress_passed && comp_keys(&disk_key, progress) < 0) - continue; - - progress_passed = 1; - blocknr = btrfs_node_blockptr(parent, i); - gen = btrfs_node_ptr_generation(parent, i); - if (last_block == 0) - last_block = blocknr; - - if (i > 0) { - other = btrfs_node_blockptr(parent, i - 1); - close = close_blocks(blocknr, other, blocksize); - } - if (close && i < end_slot - 2) { - other = btrfs_node_blockptr(parent, i + 1); - close = close_blocks(blocknr, other, blocksize); - } - if (close) { - last_block = blocknr; - continue; - } - if (parent->map_token) { - unmap_extent_buffer(parent, parent->map_token, - KM_USER1); - parent->map_token = NULL; - } - - cur = btrfs_find_tree_block(root, blocknr, blocksize); - if (cur) - uptodate = btrfs_buffer_uptodate(cur, gen); - else - uptodate = 0; - if (!cur || !uptodate) { - if (cache_only) { - free_extent_buffer(cur); - continue; - } - if (!cur) { - cur = read_tree_block(root, blocknr, - blocksize, gen); - } else if (!uptodate) { - btrfs_read_buffer(cur, gen); - } - } - if (search_start == 0) - search_start = last_block; - - err = __btrfs_cow_block(trans, root, cur, parent, i, - &tmp, search_start, - min(16 * blocksize, - (end_slot - i) * blocksize)); - if (err) { - free_extent_buffer(cur); - break; - } - search_start = tmp->start; - last_block = tmp->start; - *last_ret = search_start; - if (parent_level == 1) - btrfs_clear_buffer_defrag(tmp); - free_extent_buffer(tmp); - } - if (parent->map_token) { - unmap_extent_buffer(parent, parent->map_token, - KM_USER1); - parent->map_token = NULL; - } - return err; + return btrfs_comp_cpu_keys(&k1, k2); } -#endif /* * The leaf data grows from end-to-front in the node. * this returns the address of the start of the last item, * which is the stop of the leaf data stack */ -static inline unsigned int leaf_data_end(struct btrfs_root *root, - struct extent_buffer *leaf) +static inline unsigned int leaf_data_end(const struct btrfs_fs_info *fs_info, + const struct extent_buffer *leaf) { u32 nr = btrfs_header_nritems(leaf); if (nr == 0) - return BTRFS_LEAF_DATA_SIZE(root); + return BTRFS_LEAF_DATA_SIZE(fs_info); return btrfs_item_offset_nr(leaf, nr - 1); } -int btrfs_check_node(struct btrfs_root *root, - struct btrfs_disk_key *parent_key, - struct extent_buffer *buf) +enum btrfs_tree_block_status +btrfs_check_node(struct btrfs_root *root, struct btrfs_disk_key *parent_key, + struct extent_buffer *buf) { int i; struct btrfs_key cpukey; struct btrfs_disk_key key; u32 nritems = btrfs_header_nritems(buf); + enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS; - if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root)) + if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root->fs_info)) goto fail; + ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY; if (parent_key && parent_key->type) { btrfs_node_key(buf, &key, 0); if (memcmp(parent_key, &key, sizeof(key))) goto fail; } + ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER; for (i = 0; nritems > 1 && i < nritems - 2; i++) { btrfs_node_key(buf, &key, i); btrfs_node_key_to_cpu(buf, &cpukey, i + 1); if (btrfs_comp_keys(&key, &cpukey) >= 0) goto fail; } - return 0; + return BTRFS_TREE_BLOCK_CLEAN; fail: if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) { if (parent_key) @@ -631,17 +455,18 @@ fail: buf->start, buf->len, btrfs_header_level(buf)); } - return -EIO; + return ret; } -int btrfs_check_leaf(struct btrfs_root *root, - struct btrfs_disk_key *parent_key, - struct extent_buffer *buf) +enum btrfs_tree_block_status +btrfs_check_leaf(struct btrfs_root *root, struct btrfs_disk_key *parent_key, + struct extent_buffer *buf) { int i; struct btrfs_key cpukey; struct btrfs_disk_key key; u32 nritems = btrfs_header_nritems(buf); + enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS; if (nritems * sizeof(struct btrfs_item) > buf->len) { fprintf(stderr, "invalid number of items %llu\n", @@ -650,11 +475,13 @@ int btrfs_check_leaf(struct btrfs_root *root, } if (btrfs_header_level(buf) != 0) { + ret = BTRFS_TREE_BLOCK_INVALID_LEVEL; fprintf(stderr, "leaf is not a leaf %llu\n", (unsigned long long)btrfs_header_bytenr(buf)); goto fail; } if (btrfs_leaf_free_space(root, buf) < 0) { + ret = BTRFS_TREE_BLOCK_INVALID_FREE_SPACE; fprintf(stderr, "leaf free space incorrect %llu %d\n", (unsigned long long)btrfs_header_bytenr(buf), btrfs_leaf_free_space(root, buf)); @@ -662,38 +489,58 @@ int btrfs_check_leaf(struct btrfs_root *root, } if (nritems == 0) - return 0; + return BTRFS_TREE_BLOCK_CLEAN; btrfs_item_key(buf, &key, 0); if (parent_key && parent_key->type && memcmp(parent_key, &key, sizeof(key))) { + ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY; fprintf(stderr, "leaf parent key incorrect %llu\n", (unsigned long long)btrfs_header_bytenr(buf)); goto fail; } - for (i = 0; nritems > 1 && i < nritems - 2; i++) { + for (i = 0; nritems > 1 && i < nritems - 1; i++) { btrfs_item_key(buf, &key, i); btrfs_item_key_to_cpu(buf, &cpukey, i + 1); if (btrfs_comp_keys(&key, &cpukey) >= 0) { + ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER; fprintf(stderr, "bad key ordering %d %d\n", i, i+1); goto fail; } if (btrfs_item_offset_nr(buf, i) != btrfs_item_end_nr(buf, i + 1)) { + ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; fprintf(stderr, "incorrect offsets %u %u\n", btrfs_item_offset_nr(buf, i), btrfs_item_end_nr(buf, i + 1)); goto fail; } if (i == 0 && btrfs_item_end_nr(buf, i) != - BTRFS_LEAF_DATA_SIZE(root)) { + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { + ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; fprintf(stderr, "bad item end %u wanted %u\n", btrfs_item_end_nr(buf, i), - (unsigned)BTRFS_LEAF_DATA_SIZE(root)); + (unsigned)BTRFS_LEAF_DATA_SIZE(root->fs_info)); goto fail; } } - return 0; + + for (i = 0; i < nritems; i++) { + if (btrfs_item_end_nr(buf, i) > + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { + btrfs_item_key(buf, &key, 0); + btrfs_print_key(&key); + fflush(stdout); + ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS; + fprintf(stderr, "slot end outside of leaf %llu > %llu\n", + (unsigned long long)btrfs_item_end_nr(buf, i), + (unsigned long long)BTRFS_LEAF_DATA_SIZE( + root->fs_info)); + goto fail; + } + } + + return BTRFS_TREE_BLOCK_CLEAN; fail: if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) { if (parent_key) @@ -704,7 +551,7 @@ fail: btrfs_add_corrupt_extent_record(root->fs_info, &cpukey, buf->start, buf->len, 0); } - return -EIO; + return ret; } static int noinline check_block(struct btrfs_root *root, @@ -713,15 +560,22 @@ static int noinline check_block(struct btrfs_root *root, struct btrfs_disk_key key; struct btrfs_disk_key *key_ptr = NULL; struct extent_buffer *parent; + enum btrfs_tree_block_status ret; + if (path->skip_check_block) + return 0; if (path->nodes[level + 1]) { parent = path->nodes[level + 1]; btrfs_node_key(parent, &key, path->slots[level + 1]); key_ptr = &key; } if (level == 0) - return btrfs_check_leaf(root, key_ptr, path->nodes[0]); - return btrfs_check_node(root, key_ptr, path->nodes[level]); + ret = btrfs_check_leaf(root, key_ptr, path->nodes[0]); + else + ret = btrfs_check_node(root, key_ptr, path->nodes[level]); + if (ret == BTRFS_TREE_BLOCK_CLEAN) + return 0; + return -EIO; } /* @@ -772,26 +626,26 @@ static int generic_bin_search(struct extent_buffer *eb, unsigned long p, static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, int level, int *slot) { - if (level == 0) { + if (level == 0) return generic_bin_search(eb, offsetof(struct btrfs_leaf, items), sizeof(struct btrfs_item), key, btrfs_header_nritems(eb), slot); - } else { + else return generic_bin_search(eb, offsetof(struct btrfs_node, ptrs), sizeof(struct btrfs_key_ptr), key, btrfs_header_nritems(eb), slot); - } - return -1; } -struct extent_buffer *read_node_slot(struct btrfs_root *root, +struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info, struct extent_buffer *parent, int slot) { + struct extent_buffer *ret; int level = btrfs_header_level(parent); + if (slot < 0) return NULL; if (slot >= btrfs_header_nritems(parent)) @@ -800,9 +654,20 @@ struct extent_buffer *read_node_slot(struct btrfs_root *root, if (level == 0) return NULL; - return read_tree_block(root, btrfs_node_blockptr(parent, slot), - btrfs_level_size(root, level - 1), + ret = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot), btrfs_node_ptr_generation(parent, slot)); + if (!extent_buffer_uptodate(ret)) + return ERR_PTR(-EIO); + + if (btrfs_header_level(ret) != level - 1) { + error( +"child eb corrupted: parent bytenr=%llu item=%d parent level=%d child level=%d", + btrfs_header_bytenr(parent), slot, + btrfs_header_level(parent), btrfs_header_level(ret)); + free_extent_buffer(ret); + return ERR_PTR(-EIO); + } + return ret; } static int balance_level(struct btrfs_trans_handle *trans, @@ -813,6 +678,7 @@ static int balance_level(struct btrfs_trans_handle *trans, struct extent_buffer *mid; struct extent_buffer *left = NULL; struct extent_buffer *parent = NULL; + struct btrfs_fs_info *fs_info = root->fs_info; int ret = 0; int wret; int pslot; @@ -827,9 +693,10 @@ static int balance_level(struct btrfs_trans_handle *trans, orig_ptr = btrfs_node_blockptr(mid, orig_slot); - if (level < BTRFS_MAX_LEVEL - 1) + if (level < BTRFS_MAX_LEVEL - 1) { parent = path->nodes[level + 1]; - pslot = path->slots[level + 1]; + pslot = path->slots[level + 1]; + } /* * deal with the case where there is only one pointer in the root @@ -842,8 +709,8 @@ static int balance_level(struct btrfs_trans_handle *trans, return 0; /* promote the child to a root */ - child = read_node_slot(root, mid, 0); - BUG_ON(!child); + child = read_node_slot(fs_info, mid, 0); + BUG_ON(!extent_buffer_uptodate(child)); ret = btrfs_cow_block(trans, root, child, mid, 0, &child); BUG_ON(ret); @@ -851,7 +718,6 @@ static int balance_level(struct btrfs_trans_handle *trans, add_root_to_dirty_list(root); path->nodes[level] = NULL; clean_tree_block(trans, root, mid); - wait_on_tree_block_writeback(root, mid); /* once for the path */ free_extent_buffer(mid); @@ -863,11 +729,11 @@ static int balance_level(struct btrfs_trans_handle *trans, return ret; } if (btrfs_header_nritems(mid) > - BTRFS_NODEPTRS_PER_BLOCK(root) / 4) + BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4) return 0; - left = read_node_slot(root, parent, pslot - 1); - if (left) { + left = read_node_slot(fs_info, parent, pslot - 1); + if (extent_buffer_uptodate(left)) { wret = btrfs_cow_block(trans, root, left, parent, pslot - 1, &left); if (wret) { @@ -875,8 +741,8 @@ static int balance_level(struct btrfs_trans_handle *trans, goto enospc; } } - right = read_node_slot(root, parent, pslot + 1); - if (right) { + right = read_node_slot(fs_info, parent, pslot + 1); + if (extent_buffer_uptodate(right)) { wret = btrfs_cow_block(trans, root, right, parent, pslot + 1, &right); if (wret) { @@ -905,11 +771,9 @@ static int balance_level(struct btrfs_trans_handle *trans, u32 blocksize = right->len; clean_tree_block(trans, root, right); - wait_on_tree_block_writeback(root, right); free_extent_buffer(right); right = NULL; - wret = btrfs_del_ptr(trans, root, path, - level + 1, pslot + 1); + wret = btrfs_del_ptr(root, path, level + 1, pslot + 1); if (wret) ret = wret; wret = btrfs_free_extent(trans, root, bytenr, @@ -953,10 +817,9 @@ static int balance_level(struct btrfs_trans_handle *trans, u64 bytenr = mid->start; u32 blocksize = mid->len; clean_tree_block(trans, root, mid); - wait_on_tree_block_writeback(root, mid); free_extent_buffer(mid); mid = NULL; - wret = btrfs_del_ptr(trans, root, path, level + 1, pslot); + wret = btrfs_del_ptr(root, path, level + 1, pslot); if (wret) ret = wret; wret = btrfs_free_extent(trans, root, bytenr, blocksize, @@ -1008,6 +871,7 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, struct extent_buffer *mid; struct extent_buffer *left = NULL; struct extent_buffer *parent = NULL; + struct btrfs_fs_info *fs_info = root->fs_info; int ret = 0; int wret; int pslot; @@ -1019,20 +883,21 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, mid = path->nodes[level]; WARN_ON(btrfs_header_generation(mid) != trans->transid); - if (level < BTRFS_MAX_LEVEL - 1) + if (level < BTRFS_MAX_LEVEL - 1) { parent = path->nodes[level + 1]; - pslot = path->slots[level + 1]; + pslot = path->slots[level + 1]; + } if (!parent) return 1; - left = read_node_slot(root, parent, pslot - 1); + left = read_node_slot(fs_info, parent, pslot - 1); /* first, try to make some room in the middle buffer */ - if (left) { + if (extent_buffer_uptodate(left)) { u32 left_nr; left_nr = btrfs_header_nritems(left); - if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { + if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { wret = 1; } else { ret = btrfs_cow_block(trans, root, left, parent, @@ -1067,15 +932,15 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, } free_extent_buffer(left); } - right= read_node_slot(root, parent, pslot + 1); + right= read_node_slot(fs_info, parent, pslot + 1); /* * then try to empty the right most buffer into the middle */ - if (right) { + if (extent_buffer_uptodate(right)) { u32 right_nr; right_nr = btrfs_header_nritems(right); - if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { + if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - 1) { wret = 1; } else { ret = btrfs_cow_block(trans, root, right, @@ -1119,6 +984,7 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, int level, int slot, u64 objectid) { + struct btrfs_fs_info *fs_info = root->fs_info; struct extent_buffer *node; struct btrfs_disk_key disk_key; u32 nritems; @@ -1129,7 +995,6 @@ void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, int direction = path->reada; struct extent_buffer *eb; u32 nr; - u32 blocksize; u32 nscan = 0; if (level != 1) @@ -1140,8 +1005,7 @@ void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, node = path->nodes[level]; search = btrfs_node_blockptr(node, slot); - blocksize = btrfs_level_size(root, level - 1); - eb = btrfs_find_tree_block(root, search, blocksize); + eb = btrfs_find_tree_block(fs_info, search, fs_info->nodesize); if (eb) { free_extent_buffer(eb); return; @@ -1171,14 +1035,14 @@ void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, if ((search >= lowest_read && search <= highest_read) || (search < lowest_read && lowest_read - search <= 32768) || (search > highest_read && search - highest_read <= 32768)) { - readahead_tree_block(root, search, blocksize, + readahead_tree_block(fs_info, search, btrfs_node_ptr_generation(node, nr)); - nread += blocksize; + nread += fs_info->nodesize; } nscan++; - if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32)) + if (path->reada < 2 && (nread > SZ_256K || nscan > 32)) break; - if(nread > (1024 * 1024) || nscan > 128) + if(nread > SZ_1M || nscan > 128) break; if (search < lowest_read) @@ -1188,6 +1052,51 @@ void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, } } +int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path, + u64 iobjectid, u64 ioff, u8 key_type, + struct btrfs_key *found_key) +{ + int ret; + struct btrfs_key key; + struct extent_buffer *eb; + struct btrfs_path *path; + + key.type = key_type; + key.objectid = iobjectid; + key.offset = ioff; + + if (found_path == NULL) { + path = btrfs_alloc_path(); + if (!path) + return -ENOMEM; + } else + path = found_path; + + ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); + if ((ret < 0) || (found_key == NULL)) + goto out; + + eb = path->nodes[0]; + if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { + ret = btrfs_next_leaf(fs_root, path); + if (ret) + goto out; + eb = path->nodes[0]; + } + + btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); + if (found_key->type != key.type || + found_key->objectid != key.objectid) { + ret = 1; + goto out; + } + +out: + if (path != found_path) + btrfs_free_path(path); + return ret; +} + /* * look for key in the tree. path is filled in with nodes along the way * if key is found, we return zero and you can find the item in the leaf @@ -1210,6 +1119,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root int ret; int level; int should_reada = p->reada; + struct btrfs_fs_info *fs_info = root->fs_info; u8 lowest_level = 0; lowest_level = p->lowest_level; @@ -1249,7 +1159,7 @@ again: p->slots[level] = slot; if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= - BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { + BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) { int sret = split_node(trans, root, p, level); BUG_ON(sret > 0); if (sret) @@ -1263,7 +1173,7 @@ again: return sret; b = p->nodes[level]; if (!b) { - btrfs_release_path(NULL, p); + btrfs_release_path(p); goto again; } slot = p->slots[level]; @@ -1277,7 +1187,7 @@ again: reada_for_search(root, p, level, slot, key->objectid); - b = read_node_slot(root, b, slot); + b = read_node_slot(fs_info, b, slot); if (!extent_buffer_uptodate(b)) return -EIO; } else { @@ -1302,16 +1212,11 @@ again: * This is used after shifting pointers to the left, so it stops * fixing up pointers when a given leaf/node is not in slot 0 of the * higher levels - * - * If this fails to write a tree block, it returns -1, but continues - * fixing up the blocks in ram so the tree is consistent. */ -static int fixup_low_keys(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, +void btrfs_fixup_low_keys(struct btrfs_root *root, struct btrfs_path *path, struct btrfs_disk_key *key, int level) { int i; - int ret = 0; struct extent_buffer *t; for (i = level; i < BTRFS_MAX_LEVEL; i++) { @@ -1324,7 +1229,6 @@ static int fixup_low_keys(struct btrfs_trans_handle *trans, if (tslot != 0) break; } - return ret; } /* @@ -1333,8 +1237,7 @@ static int fixup_low_keys(struct btrfs_trans_handle *trans, * This function isn't completely safe. It's the caller's responsibility * that the new key won't break the order */ -int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, +int btrfs_set_item_key_safe(struct btrfs_root *root, struct btrfs_path *path, struct btrfs_key *new_key) { struct btrfs_disk_key disk_key; @@ -1358,11 +1261,33 @@ int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, btrfs_set_item_key(eb, &disk_key, slot); btrfs_mark_buffer_dirty(eb); if (slot == 0) - fixup_low_keys(trans, root, path, &disk_key, 1); + btrfs_fixup_low_keys(root, path, &disk_key, 1); return 0; } /* + * update an item key without the safety checks. This is meant to be called by + * fsck only. + */ +void btrfs_set_item_key_unsafe(struct btrfs_root *root, + struct btrfs_path *path, + struct btrfs_key *new_key) +{ + struct btrfs_disk_key disk_key; + struct extent_buffer *eb; + int slot; + + eb = path->nodes[0]; + slot = path->slots[0]; + + btrfs_cpu_key_to_disk(&disk_key, new_key); + btrfs_set_item_key(eb, &disk_key, slot); + btrfs_mark_buffer_dirty(eb); + if (slot == 0) + btrfs_fixup_low_keys(root, path, &disk_key, 1); +} + +/* * try to push data from one node into the next node left in the * tree. * @@ -1380,7 +1305,7 @@ static int push_node_left(struct btrfs_trans_handle *trans, src_nritems = btrfs_header_nritems(src); dst_nritems = btrfs_header_nritems(dst); - push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; + push_items = BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - dst_nritems; WARN_ON(btrfs_header_generation(src) != trans->transid); WARN_ON(btrfs_header_generation(dst) != trans->transid); @@ -1450,7 +1375,7 @@ static int balance_node_right(struct btrfs_trans_handle *trans, src_nritems = btrfs_header_nritems(src); dst_nritems = btrfs_header_nritems(dst); - push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; + push_items = BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - dst_nritems; if (push_items <= 0) { return 1; } @@ -1513,7 +1438,7 @@ static int noinline insert_new_root(struct btrfs_trans_handle *trans, else btrfs_node_key(lower, &lower_key, 0); - c = btrfs_alloc_free_block(trans, root, root->nodesize, + c = btrfs_alloc_free_block(trans, root, root->fs_info->nodesize, root->root_key.objectid, &lower_key, level, root->node->start, 0); @@ -1529,11 +1454,10 @@ static int noinline insert_new_root(struct btrfs_trans_handle *trans, btrfs_set_header_owner(c, root->root_key.objectid); write_extent_buffer(c, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(c), - BTRFS_FSID_SIZE); + btrfs_header_fsid(), BTRFS_FSID_SIZE); write_extent_buffer(c, root->fs_info->chunk_tree_uuid, - (unsigned long)btrfs_header_chunk_tree_uuid(c), + btrfs_header_chunk_tree_uuid(c), BTRFS_UUID_SIZE); btrfs_set_node_key(c, &lower_key, 0); @@ -1579,9 +1503,10 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root nritems = btrfs_header_nritems(lower); if (slot > nritems) BUG(); - if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) + if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root->fs_info)) BUG(); - if (slot != nritems) { + if (slot < nritems) { + /* shift the items */ memmove_extent_buffer(lower, btrfs_node_key_ptr_offset(slot + 1), btrfs_node_key_ptr_offset(slot), @@ -1627,7 +1552,7 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root ret = push_nodes_for_insert(trans, root, path, level); c = path->nodes[level]; if (!ret && btrfs_header_nritems(c) < - BTRFS_NODEPTRS_PER_BLOCK(root) - 3) + BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - 3) return 0; if (ret < 0) return ret; @@ -1637,7 +1562,7 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root mid = (c_nritems + 1) / 2; btrfs_node_key(c, &disk_key, mid); - split = btrfs_alloc_free_block(trans, root, root->nodesize, + split = btrfs_alloc_free_block(trans, root, root->fs_info->nodesize, root->root_key.objectid, &disk_key, level, c->start, 0); if (IS_ERR(split)) @@ -1650,10 +1575,9 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV); btrfs_set_header_owner(split, root->root_key.objectid); write_extent_buffer(split, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(split), - BTRFS_FSID_SIZE); + btrfs_header_fsid(), BTRFS_FSID_SIZE); write_extent_buffer(split, root->fs_info->chunk_tree_uuid, - (unsigned long)btrfs_header_chunk_tree_uuid(split), + btrfs_header_chunk_tree_uuid(split), BTRFS_UUID_SIZE); @@ -1712,13 +1636,14 @@ static int leaf_space_used(struct extent_buffer *l, int start, int nr) */ int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf) { + u32 nodesize = (root ? BTRFS_LEAF_DATA_SIZE(root->fs_info) : leaf->len); int nritems = btrfs_header_nritems(leaf); int ret; - ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); + ret = nodesize - leaf_space_used(leaf, 0, nritems); if (ret < 0) { - printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n", - ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), - leaf_space_used(leaf, 0, nritems), nritems); + printk("leaf free space ret %d, leaf data size %u, used %d nritems %d\n", + ret, nodesize, leaf_space_used(leaf, 0, nritems), + nritems); } return ret; } @@ -1738,6 +1663,7 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root struct extent_buffer *right; struct extent_buffer *upper; struct btrfs_disk_key disk_key; + struct btrfs_fs_info *fs_info = root->fs_info; int slot; u32 i; int free_space; @@ -1759,7 +1685,12 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root if (slot >= btrfs_header_nritems(upper) - 1) return 1; - right = read_node_slot(root, upper, slot + 1); + right = read_node_slot(fs_info, upper, slot + 1); + if (!extent_buffer_uptodate(right)) { + if (IS_ERR(right)) + return PTR_ERR(right); + return -EIO; + } free_space = btrfs_leaf_free_space(root, right); if (free_space < data_size) { free_extent_buffer(right); @@ -1792,7 +1723,7 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root i = left_nritems - 1; while (i >= nr) { - item = btrfs_item_nr(left, i); + item = btrfs_item_nr(i); if (path->slots[0] == i) push_space += data_size + sizeof(*item); @@ -1819,19 +1750,19 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root right_nritems = btrfs_header_nritems(right); push_space = btrfs_item_end_nr(left, left_nritems - push_items); - push_space -= leaf_data_end(root, left); + push_space -= leaf_data_end(fs_info, left); /* make room in the right data area */ - data_end = leaf_data_end(root, right); + data_end = leaf_data_end(fs_info, right); memmove_extent_buffer(right, btrfs_leaf_data(right) + data_end - push_space, btrfs_leaf_data(right) + data_end, - BTRFS_LEAF_DATA_SIZE(root) - data_end); + BTRFS_LEAF_DATA_SIZE(root->fs_info) - data_end); /* copy from the left data area */ copy_extent_buffer(right, left, btrfs_leaf_data(right) + - BTRFS_LEAF_DATA_SIZE(root) - push_space, - btrfs_leaf_data(left) + leaf_data_end(root, left), + BTRFS_LEAF_DATA_SIZE(root->fs_info) - push_space, + btrfs_leaf_data(left) + leaf_data_end(fs_info, left), push_space); memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), @@ -1846,9 +1777,9 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root /* update the item pointers */ right_nritems += push_items; btrfs_set_header_nritems(right, right_nritems); - push_space = BTRFS_LEAF_DATA_SIZE(root); + push_space = BTRFS_LEAF_DATA_SIZE(root->fs_info); for (i = 0; i < right_nritems; i++) { - item = btrfs_item_nr(right, i); + item = btrfs_item_nr(i); push_space -= btrfs_item_size(right, item); btrfs_set_item_offset(right, item, push_space); } @@ -1886,6 +1817,7 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root struct btrfs_disk_key disk_key; struct extent_buffer *right = path->nodes[0]; struct extent_buffer *left; + struct btrfs_fs_info *fs_info = root->fs_info; int slot; int i; int free_space; @@ -1896,7 +1828,6 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root u32 right_nritems; u32 nr; int ret = 0; - int wret; u32 this_item_size; u32 old_left_item_size; @@ -1911,7 +1842,7 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root return 1; } - left = read_node_slot(root, path->nodes[1], slot - 1); + left = read_node_slot(fs_info, path->nodes[1], slot - 1); free_space = btrfs_leaf_free_space(root, left); if (free_space < data_size) { free_extent_buffer(left); @@ -1939,7 +1870,7 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root nr = right_nritems - 1; for (i = 0; i < nr; i++) { - item = btrfs_item_nr(right, i); + item = btrfs_item_nr(i); if (path->slots[0] == i) push_space += data_size + sizeof(*item); @@ -1965,11 +1896,11 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_item_nr_offset(0), push_items * sizeof(struct btrfs_item)); - push_space = BTRFS_LEAF_DATA_SIZE(root) - + push_space = BTRFS_LEAF_DATA_SIZE(root->fs_info) - btrfs_item_offset_nr(right, push_items -1); copy_extent_buffer(left, right, btrfs_leaf_data(left) + - leaf_data_end(root, left) - push_space, + leaf_data_end(fs_info, left) - push_space, btrfs_leaf_data(right) + btrfs_item_offset_nr(right, push_items - 1), push_space); @@ -1980,10 +1911,11 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { u32 ioff; - item = btrfs_item_nr(left, i); + item = btrfs_item_nr(i); ioff = btrfs_item_offset(left, item); btrfs_set_item_offset(left, item, - ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); + ioff - (BTRFS_LEAF_DATA_SIZE(root->fs_info) - + old_left_item_size)); } btrfs_set_header_nritems(left, old_left_nritems + push_items); @@ -1995,11 +1927,13 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root if (push_items < right_nritems) { push_space = btrfs_item_offset_nr(right, push_items - 1) - - leaf_data_end(root, right); + leaf_data_end(fs_info, right); memmove_extent_buffer(right, btrfs_leaf_data(right) + - BTRFS_LEAF_DATA_SIZE(root) - push_space, + BTRFS_LEAF_DATA_SIZE(root->fs_info) - + push_space, btrfs_leaf_data(right) + - leaf_data_end(root, right), push_space); + leaf_data_end(fs_info, right), + push_space); memmove_extent_buffer(right, btrfs_item_nr_offset(0), btrfs_item_nr_offset(push_items), @@ -2008,9 +1942,9 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root } right_nritems -= push_items; btrfs_set_header_nritems(right, right_nritems); - push_space = BTRFS_LEAF_DATA_SIZE(root); + push_space = BTRFS_LEAF_DATA_SIZE(root->fs_info); for (i = 0; i < right_nritems; i++) { - item = btrfs_item_nr(right, i); + item = btrfs_item_nr(i); push_space = push_space - btrfs_item_size(right, item); btrfs_set_item_offset(right, item, push_space); } @@ -2020,9 +1954,7 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_mark_buffer_dirty(right); btrfs_item_key(right, &disk_key, 0); - wret = fixup_low_keys(trans, root, path, &disk_key, 1); - if (wret) - ret = wret; + btrfs_fixup_low_keys(root, path, &disk_key, 1); /* then fixup the leaf pointer in the path */ if (path->slots[0] < push_items) { @@ -2060,22 +1992,24 @@ static noinline int copy_for_split(struct btrfs_trans_handle *trans, nritems = nritems - mid; btrfs_set_header_nritems(right, nritems); - data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); + data_copy_size = btrfs_item_end_nr(l, mid) - + leaf_data_end(root->fs_info, l); copy_extent_buffer(right, l, btrfs_item_nr_offset(0), btrfs_item_nr_offset(mid), nritems * sizeof(struct btrfs_item)); copy_extent_buffer(right, l, - btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - + btrfs_leaf_data(right) + + BTRFS_LEAF_DATA_SIZE(root->fs_info) - data_copy_size, btrfs_leaf_data(l) + - leaf_data_end(root, l), data_copy_size); + leaf_data_end(root->fs_info, l), data_copy_size); - rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - + rt_data_off = BTRFS_LEAF_DATA_SIZE(root->fs_info) - btrfs_item_end_nr(l, mid); for (i = 0; i < nritems; i++) { - struct btrfs_item *item = btrfs_item_nr(right, i); + struct btrfs_item *item = btrfs_item_nr(i); u32 ioff = btrfs_item_offset(right, item); btrfs_set_item_offset(right, item, ioff + rt_data_off); } @@ -2129,6 +2063,12 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans, int split; int num_doubles = 0; + l = path->nodes[0]; + slot = path->slots[0]; + if (extend && data_size + btrfs_item_size_nr(l, slot) + + sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root->fs_info)) + return -EOVERFLOW; + /* first try to make some room by pushing left and right */ if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { wret = push_leaf_right(trans, root, path, data_size, 0); @@ -2161,21 +2101,22 @@ again: if (mid <= slot) { if (nritems == 1 || leaf_space_used(l, mid, nritems - mid) + data_size > - BTRFS_LEAF_DATA_SIZE(root)) { + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { if (slot >= nritems) { split = 0; } else { mid = slot; if (mid != nritems && leaf_space_used(l, mid, nritems - mid) + - data_size > BTRFS_LEAF_DATA_SIZE(root)) { + data_size > + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { split = 2; } } } } else { if (leaf_space_used(l, 0, mid) + data_size > - BTRFS_LEAF_DATA_SIZE(root)) { + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { if (!extend && data_size && slot == 0) { split = 0; } else if ((extend || !data_size) && slot == 0) { @@ -2184,7 +2125,8 @@ again: mid = slot; if (mid != nritems && leaf_space_used(l, mid, nritems - mid) + - data_size > BTRFS_LEAF_DATA_SIZE(root)) { + data_size > + BTRFS_LEAF_DATA_SIZE(root->fs_info)) { split = 2 ; } } @@ -2196,7 +2138,7 @@ again: else btrfs_item_key(l, &disk_key, mid); - right = btrfs_alloc_free_block(trans, root, root->leafsize, + right = btrfs_alloc_free_block(trans, root, root->fs_info->nodesize, root->root_key.objectid, &disk_key, 0, l->start, 0); if (IS_ERR(right)) { @@ -2211,11 +2153,10 @@ again: btrfs_set_header_owner(right, root->root_key.objectid); btrfs_set_header_level(right, 0); write_extent_buffer(right, root->fs_info->fsid, - (unsigned long)btrfs_header_fsid(right), - BTRFS_FSID_SIZE); + btrfs_header_fsid(), BTRFS_FSID_SIZE); write_extent_buffer(right, root->fs_info->chunk_tree_uuid, - (unsigned long)btrfs_header_chunk_tree_uuid(right), + btrfs_header_chunk_tree_uuid(right), BTRFS_UUID_SIZE); if (split == 0) { @@ -2243,10 +2184,8 @@ again: path->nodes[0] = right; path->slots[0] = 0; if (path->slots[1] == 0) { - wret = fixup_low_keys(trans, root, - path, &disk_key, 1); - if (wret) - ret = wret; + btrfs_fixup_low_keys(root, path, + &disk_key, 1); } } btrfs_mark_buffer_dirty(right); @@ -2304,7 +2243,7 @@ int btrfs_split_item(struct btrfs_trans_handle *trans, goto split; item_size = btrfs_item_size_nr(leaf, path->slots[0]); - btrfs_release_path(root, path); + btrfs_release_path(path); path->search_for_split = 1; @@ -2324,12 +2263,13 @@ int btrfs_split_item(struct btrfs_trans_handle *trans, leaf = path->nodes[0]; split: - item = btrfs_item_nr(leaf, path->slots[0]); + item = btrfs_item_nr(path->slots[0]); orig_offset = btrfs_item_offset(leaf, item); item_size = btrfs_item_size(leaf, item); buf = kmalloc(item_size, GFP_NOFS); + BUG_ON(!buf); read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, path->slots[0]), item_size); slot = path->slots[0] + 1; @@ -2337,7 +2277,7 @@ split: nritems = btrfs_header_nritems(leaf); - if (slot != nritems) { + if (slot < nritems) { /* shift the items */ memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), btrfs_item_nr_offset(slot), @@ -2348,7 +2288,7 @@ split: btrfs_cpu_key_to_disk(&disk_key, new_key); btrfs_set_item_key(leaf, &disk_key, slot); - new_item = btrfs_item_nr(leaf, slot); + new_item = btrfs_item_nr(slot); btrfs_set_item_offset(leaf, new_item, orig_offset); btrfs_set_item_size(leaf, new_item, item_size - split_offset); @@ -2379,9 +2319,7 @@ split: return ret; } -int btrfs_truncate_item(struct btrfs_trans_handle *trans, - struct btrfs_root *root, - struct btrfs_path *path, +int btrfs_truncate_item(struct btrfs_root *root, struct btrfs_path *path, u32 new_size, int from_end) { int ret = 0; @@ -2403,7 +2341,7 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans, return 0; nritems = btrfs_header_nritems(leaf); - data_end = leaf_data_end(root, leaf); + data_end = leaf_data_end(root->fs_info, leaf); old_data_start = btrfs_item_offset_nr(leaf, slot); @@ -2418,7 +2356,7 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans, /* first correct the data pointers */ for (i = slot; i < nritems; i++) { u32 ioff; - item = btrfs_item_nr(leaf, i); + item = btrfs_item_nr(i); ioff = btrfs_item_offset(leaf, item); btrfs_set_item_offset(leaf, item, ioff + size_diff); } @@ -2461,10 +2399,10 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans, btrfs_set_disk_key_offset(&disk_key, offset + size_diff); btrfs_set_item_key(leaf, &disk_key, slot); if (slot == 0) - fixup_low_keys(trans, root, path, &disk_key, 1); + btrfs_fixup_low_keys(root, path, &disk_key, 1); } - item = btrfs_item_nr(leaf, slot); + item = btrfs_item_nr(slot); btrfs_set_item_size(leaf, item, new_size); btrfs_mark_buffer_dirty(leaf); @@ -2476,8 +2414,7 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans, return ret; } -int btrfs_extend_item(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, +int btrfs_extend_item(struct btrfs_root *root, struct btrfs_path *path, u32 data_size) { int ret = 0; @@ -2493,7 +2430,7 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, leaf = path->nodes[0]; nritems = btrfs_header_nritems(leaf); - data_end = leaf_data_end(root, leaf); + data_end = leaf_data_end(root->fs_info, leaf); if (btrfs_leaf_free_space(root, leaf) < data_size) { btrfs_print_leaf(root, leaf); @@ -2515,7 +2452,7 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, /* first correct the data pointers */ for (i = slot; i < nritems; i++) { u32 ioff; - item = btrfs_item_nr(leaf, i); + item = btrfs_item_nr(i); ioff = btrfs_item_offset(leaf, item); btrfs_set_item_offset(leaf, item, ioff - data_size); } @@ -2527,7 +2464,7 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, data_end = old_data; old_size = btrfs_item_size_nr(leaf, slot); - item = btrfs_item_nr(leaf, slot); + item = btrfs_item_nr(slot); btrfs_set_item_size(leaf, item, old_size + data_size); btrfs_mark_buffer_dirty(leaf); @@ -2579,7 +2516,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, leaf = path->nodes[0]; nritems = btrfs_header_nritems(leaf); - data_end = leaf_data_end(root, leaf); + data_end = leaf_data_end(root->fs_info, leaf); if (btrfs_leaf_free_space(root, leaf) < total_size) { btrfs_print_leaf(root, leaf); @@ -2591,8 +2528,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, slot = path->slots[0]; BUG_ON(slot < 0); - if (slot != nritems) { - int i; + if (slot < nritems) { unsigned int old_data = btrfs_item_end_nr(leaf, slot); if (old_data < data_end) { @@ -2608,7 +2544,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, for (i = slot; i < nritems; i++) { u32 ioff; - item = btrfs_item_nr(leaf, i); + item = btrfs_item_nr(i); ioff = btrfs_item_offset(leaf, item); btrfs_set_item_offset(leaf, item, ioff - total_data); } @@ -2629,7 +2565,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, for (i = 0; i < nr; i++) { btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); btrfs_set_item_key(leaf, &disk_key, slot + i); - item = btrfs_item_nr(leaf, slot + i); + item = btrfs_item_nr(slot + i); btrfs_set_item_offset(leaf, item, data_end - data_size[i]); data_end -= data_size[i]; btrfs_set_item_size(leaf, item, data_size[i]); @@ -2640,7 +2576,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, ret = 0; if (slot == 0) { btrfs_cpu_key_to_disk(&disk_key, cpu_key); - ret = fixup_low_keys(trans, root, path, &disk_key, 1); + btrfs_fixup_low_keys(root, path, &disk_key, 1); } if (btrfs_leaf_free_space(root, leaf) < 0) { @@ -2666,7 +2602,9 @@ int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root unsigned long ptr; path = btrfs_alloc_path(); - BUG_ON(!path); + if (!path) + return -ENOMEM; + ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); if (!ret) { leaf = path->nodes[0]; @@ -2685,16 +2623,16 @@ int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root * continuing all the way the root if required. The root is converted into * a leaf if all the nodes are emptied. */ -int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, - struct btrfs_path *path, int level, int slot) +int btrfs_del_ptr(struct btrfs_root *root, struct btrfs_path *path, + int level, int slot) { struct extent_buffer *parent = path->nodes[level]; u32 nritems; int ret = 0; - int wret; nritems = btrfs_header_nritems(parent); - if (slot != nritems -1) { + if (slot < nritems - 1) { + /* shift the items */ memmove_extent_buffer(parent, btrfs_node_key_ptr_offset(slot), btrfs_node_key_ptr_offset(slot + 1), @@ -2711,9 +2649,7 @@ int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct btrfs_disk_key disk_key; btrfs_node_key(parent, &disk_key, 0); - wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); - if (wret) - ret = wret; + btrfs_fixup_low_keys(root, path, &disk_key, level + 1); } btrfs_mark_buffer_dirty(parent); return ret; @@ -2737,7 +2673,7 @@ static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans, int ret; WARN_ON(btrfs_header_generation(leaf) != trans->transid); - ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]); + ret = btrfs_del_ptr(root, path, 1, path->slots[1]); if (ret) return ret; @@ -2771,8 +2707,7 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, nritems = btrfs_header_nritems(leaf); if (slot + nr != nritems) { - int i; - int data_end = leaf_data_end(root, leaf); + int data_end = leaf_data_end(root->fs_info, leaf); memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + data_end + dsize, @@ -2782,7 +2717,7 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, for (i = slot + nr; i < nritems; i++) { u32 ioff; - item = btrfs_item_nr(leaf, i); + item = btrfs_item_nr(i); ioff = btrfs_item_offset(leaf, item); btrfs_set_item_offset(leaf, item, ioff + dsize); } @@ -2801,8 +2736,6 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, btrfs_set_header_level(leaf, 0); } else { clean_tree_block(trans, root, leaf); - wait_on_tree_block_writeback(root, leaf); - wret = btrfs_del_leaf(trans, root, path, leaf); BUG_ON(ret); if (wret) @@ -2814,14 +2747,11 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct btrfs_disk_key disk_key; btrfs_item_key(leaf, &disk_key, 0); - wret = fixup_low_keys(trans, root, path, - &disk_key, 1); - if (wret) - ret = wret; + btrfs_fixup_low_keys(root, path, &disk_key, 1); } /* delete the leaf if it is mostly empty */ - if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { + if (used < BTRFS_LEAF_DATA_SIZE(root->fs_info) / 4) { /* push_leaf_left fixes the path. * make sure the path still points to our leaf * for possible call to del_ptr below @@ -2842,8 +2772,6 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, if (btrfs_header_nritems(leaf) == 0) { clean_tree_block(trans, root, leaf); - wait_on_tree_block_writeback(root, leaf); - path->slots[1] = slot; ret = btrfs_del_leaf(trans, root, path, leaf); BUG_ON(ret); @@ -2871,6 +2799,7 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) int level = 1; struct extent_buffer *c; struct extent_buffer *next = NULL; + struct btrfs_fs_info *fs_info = root->fs_info; while(level < BTRFS_MAX_LEVEL) { if (!path->nodes[level]) @@ -2886,7 +2815,12 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) } slot--; - next = read_node_slot(root, c, slot); + next = read_node_slot(fs_info, c, slot); + if (!extent_buffer_uptodate(next)) { + if (IS_ERR(next)) + return PTR_ERR(next); + return -EIO; + } break; } path->slots[level] = slot; @@ -2901,7 +2835,12 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) path->slots[level] = slot; if (!level) break; - next = read_node_slot(root, next, slot); + next = read_node_slot(fs_info, next, slot); + if (!extent_buffer_uptodate(next)) { + if (IS_ERR(next)) + return PTR_ERR(next); + return -EIO; + } } return 0; } @@ -2917,6 +2856,7 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) int level = 1; struct extent_buffer *c; struct extent_buffer *next = NULL; + struct btrfs_fs_info *fs_info = root->fs_info; while(level < BTRFS_MAX_LEVEL) { if (!path->nodes[level]) @@ -2934,8 +2874,8 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) if (path->reada) reada_for_search(root, path, level, slot, 0); - next = read_node_slot(root, c, slot); - if (!next) + next = read_node_slot(fs_info, c, slot); + if (!extent_buffer_uptodate(next)) return -EIO; break; } @@ -2950,8 +2890,8 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) break; if (path->reada) reada_for_search(root, path, level, 0, 0); - next = read_node_slot(root, next, 0); - if (!next) + next = read_node_slot(fs_info, next, 0); + if (!extent_buffer_uptodate(next)) return -EIO; } return 0; @@ -2963,6 +2903,7 @@ int btrfs_previous_item(struct btrfs_root *root, { struct btrfs_key found_key; struct extent_buffer *leaf; + u32 nritems; int ret; while(1) { @@ -2974,10 +2915,86 @@ int btrfs_previous_item(struct btrfs_root *root, path->slots[0]--; } leaf = path->nodes[0]; + nritems = btrfs_header_nritems(leaf); + if (nritems == 0) + return 1; + if (path->slots[0] == nritems) + path->slots[0]--; + btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); + if (found_key.objectid < min_objectid) + break; if (found_key.type == type) return 0; + if (found_key.objectid == min_objectid && + found_key.type < type) + break; } return 1; } +/* + * search in extent tree to find a previous Metadata/Data extent item with + * min objecitd. + * + * returns 0 if something is found, 1 if nothing was found and < 0 on error + */ +int btrfs_previous_extent_item(struct btrfs_root *root, + struct btrfs_path *path, u64 min_objectid) +{ + struct btrfs_key found_key; + struct extent_buffer *leaf; + u32 nritems; + int ret; + + while (1) { + if (path->slots[0] == 0) { + ret = btrfs_prev_leaf(root, path); + if (ret != 0) + return ret; + } else { + path->slots[0]--; + } + leaf = path->nodes[0]; + nritems = btrfs_header_nritems(leaf); + if (nritems == 0) + return 1; + if (path->slots[0] == nritems) + path->slots[0]--; + + btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); + if (found_key.objectid < min_objectid) + break; + if (found_key.type == BTRFS_EXTENT_ITEM_KEY || + found_key.type == BTRFS_METADATA_ITEM_KEY) + return 0; + if (found_key.objectid == min_objectid && + found_key.type < BTRFS_EXTENT_ITEM_KEY) + break; + } + return 1; +} + +/* + * Search in extent tree to found next meta/data extent + * Caller needs to check for no-hole or skinny metadata features. + */ +int btrfs_next_extent_item(struct btrfs_root *root, + struct btrfs_path *path, u64 max_objectid) +{ + struct btrfs_key found_key; + int ret; + + while (1) { + ret = btrfs_next_item(root, path); + if (ret) + return ret; + btrfs_item_key_to_cpu(path->nodes[0], &found_key, + path->slots[0]); + if (found_key.objectid > max_objectid) + return 1; + if (found_key.type == BTRFS_EXTENT_ITEM_KEY || + found_key.type == BTRFS_METADATA_ITEM_KEY) + return 0; + } +}