X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=ctree.c;h=4fc33b14000ad0dae26f38f9d31dfedd226e05d1;hb=37c737d7cbb3d03be26b1d000c186dac4b73e00e;hp=130c61fa036e12d50a02e008a4382c78a00b66bc;hpb=ccdd0a067f36b689a0928074d53e5020f3ff5f5d;p=platform%2Fupstream%2Fbtrfs-progs.git diff --git a/ctree.c b/ctree.c index 130c61f..4fc33b1 100644 --- a/ctree.c +++ b/ctree.c @@ -20,6 +20,8 @@ #include "transaction.h" #include "print-tree.h" #include "repair.h" +#include "internal.h" +#include "sizes.h" static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct btrfs_path *path, int level); @@ -141,7 +143,7 @@ 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. @@ -367,7 +369,7 @@ 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; @@ -521,6 +523,20 @@ btrfs_check_leaf(struct btrfs_root *root, struct btrfs_disk_key *parent_key, goto fail; } } + + for (i = 0; i < nritems; i++) { + if (btrfs_item_end_nr(buf, i) > BTRFS_LEAF_DATA_SIZE(root)) { + 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)); + goto fail; + } + } + return BTRFS_TREE_BLOCK_CLEAN; fail: if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) { @@ -621,7 +637,7 @@ static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, slot); } -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) { int level = btrfs_header_level(parent); @@ -633,8 +649,7 @@ 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), + return read_tree_block(fs_info, btrfs_node_blockptr(parent, slot), btrfs_node_ptr_generation(parent, slot)); } @@ -646,6 +661,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; @@ -676,7 +692,7 @@ static int balance_level(struct btrfs_trans_handle *trans, return 0; /* promote the child to a root */ - child = read_node_slot(root, mid, 0); + 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); @@ -685,7 +701,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); @@ -700,7 +715,7 @@ static int balance_level(struct btrfs_trans_handle *trans, BTRFS_NODEPTRS_PER_BLOCK(root) / 4) return 0; - left = read_node_slot(root, parent, pslot - 1); + 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); @@ -709,7 +724,7 @@ static int balance_level(struct btrfs_trans_handle *trans, goto enospc; } } - right = read_node_slot(root, parent, pslot + 1); + 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); @@ -739,11 +754,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, @@ -787,10 +800,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, @@ -842,6 +854,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; @@ -861,7 +874,7 @@ static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, 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 (extent_buffer_uptodate(left)) { @@ -902,7 +915,7 @@ 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 @@ -954,6 +967,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; @@ -964,7 +978,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) @@ -975,8 +988,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; @@ -1006,14 +1018,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) @@ -1044,26 +1056,28 @@ int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path, path = found_path; ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); - if ((ret < 0) || (found_key == NULL)) { - if (path != found_path) - btrfs_free_path(path); - return ret; - } + 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) - return 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) - return 1; + found_key->objectid != key.objectid) { + ret = 1; + goto out; + } - return 0; +out: + if (path != found_path) + btrfs_free_path(path); + return ret; } /* @@ -1088,6 +1102,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; @@ -1155,7 +1170,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 { @@ -1406,7 +1421,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); @@ -1473,7 +1488,8 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root BUG(); if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 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), @@ -1529,7 +1545,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)) @@ -1603,13 +1619,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) : 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; } @@ -1629,6 +1646,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; @@ -1650,7 +1668,7 @@ 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); @@ -1782,6 +1800,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; @@ -1806,7 +1825,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); @@ -2095,7 +2114,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)) { @@ -2226,6 +2245,7 @@ split: 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; @@ -2233,7 +2253,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), @@ -2275,9 +2295,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; @@ -2372,8 +2390,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; @@ -2487,7 +2504,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, slot = path->slots[0]; BUG_ON(slot < 0); - if (slot != nritems) { + if (slot < nritems) { unsigned int old_data = btrfs_item_end_nr(leaf, slot); if (old_data < data_end) { @@ -2561,7 +2578,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]; @@ -2580,15 +2599,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; 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), @@ -2629,7 +2649,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; @@ -2692,8 +2712,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) @@ -2730,8 +2748,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); @@ -2759,6 +2775,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]) @@ -2774,7 +2791,7 @@ 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); @@ -2794,7 +2811,7 @@ 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); @@ -2815,6 +2832,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]) @@ -2832,7 +2850,7 @@ 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); + next = read_node_slot(fs_info, c, slot); if (!extent_buffer_uptodate(next)) return -EIO; break; @@ -2848,7 +2866,7 @@ 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); + next = read_node_slot(fs_info, next, 0); if (!extent_buffer_uptodate(next)) return -EIO; } @@ -2861,6 +2879,7 @@ int btrfs_previous_item(struct btrfs_root *root, { struct btrfs_key found_key; struct extent_buffer *leaf; + u32 nritems; int ret; while(1) { @@ -2872,9 +2891,20 @@ 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; } @@ -2920,3 +2950,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root, } 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; + } +}