X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=fs%2Fbtrfs%2Fctree.c;h=bbf9bf3740664e6e3d521377d1cff0de4afa9e87;hb=7d9eb12c8739e7dc80c78c6b3596f912ecd8f941;hp=75625c68fdd8d867bbdd9c071a9449f17429876f;hpb=925baeddc5b0764a53f2214a1253251bab0e0324;p=deliverable%2Flinux.git diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 75625c68fdd8..bbf9bf374066 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -63,7 +63,9 @@ void btrfs_free_path(struct btrfs_path *p) void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) { int i; + for (i = 0; i < BTRFS_MAX_LEVEL; i++) { + p->slots[i] = 0; if (!p->nodes[i]) continue; if (p->locks[i]) { @@ -71,8 +73,8 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) p->locks[i] = 0; } free_extent_buffer(p->nodes[i]); + p->nodes[i] = NULL; } - memset(p, 0, sizeof(*p)); } struct extent_buffer *btrfs_root_node(struct btrfs_root *root) @@ -349,7 +351,6 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans, struct btrfs_key *progress) { struct extent_buffer *cur; - struct extent_buffer *tmp; u64 blocknr; u64 gen; u64 search_start = *last_ret; @@ -365,9 +366,6 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans, int progress_passed = 0; struct btrfs_disk_key disk_key; - /* FIXME this code needs locking */ - return 0; - parent_level = btrfs_header_level(parent); if (cache_only && parent_level != 1) return 0; @@ -449,20 +447,21 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans, if (search_start == 0) search_start = last_block; + btrfs_tree_lock(cur); err = __btrfs_cow_block(trans, root, cur, parent, i, - &tmp, search_start, + &cur, search_start, min(16 * blocksize, (end_slot - i) * blocksize)); if (err) { + btrfs_tree_unlock(cur); free_extent_buffer(cur); break; } - search_start = tmp->start; - last_block = tmp->start; + search_start = cur->start; + last_block = cur->start; *last_ret = search_start; - if (parent_level == 1) - btrfs_clear_buffer_defrag(tmp); - free_extent_buffer(tmp); + btrfs_tree_unlock(cur); + free_extent_buffer(cur); } if (parent->map_token) { unmap_extent_buffer(parent, parent->map_token, @@ -1132,7 +1131,6 @@ static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, return; node = path->nodes[level]; - WARN_ON(!path->skip_locking && !btrfs_tree_locked(node)); search = btrfs_node_blockptr(node, slot); blocksize = btrfs_level_size(root, level - 1); @@ -1187,6 +1185,7 @@ static void unlock_up(struct btrfs_path *path, int level, int lowest_unlock) { int i; int skip_level = level; + int no_skips = 0; struct extent_buffer *t; for (i = level; i < BTRFS_MAX_LEVEL; i++) { @@ -1194,19 +1193,22 @@ static void unlock_up(struct btrfs_path *path, int level, int lowest_unlock) break; if (!path->locks[i]) break; - if (path->slots[i] == 0) { + if (!no_skips && path->slots[i] == 0) { skip_level = i + 1; continue; } - if (path->keep_locks) { + if (!no_skips && path->keep_locks) { u32 nritems; t = path->nodes[i]; nritems = btrfs_header_nritems(t); - if (path->slots[i] >= nritems - 1) { + if (nritems < 1 || path->slots[i] >= nritems - 1) { skip_level = i + 1; continue; } } + if (skip_level < i && i >= lowest_unlock) + no_skips = 1; + t = path->nodes[i]; if (i >= lowest_unlock && i > skip_level && path->locks[i]) { btrfs_tree_unlock(t); @@ -1233,30 +1235,29 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root ins_len, int cow) { struct extent_buffer *b; + struct extent_buffer *tmp; int slot; int ret; int level; int should_reada = p->reada; int lowest_unlock = 1; + int blocksize; u8 lowest_level = 0; + u64 blocknr; + u64 gen; lowest_level = p->lowest_level; WARN_ON(lowest_level && ins_len); WARN_ON(p->nodes[0] != NULL); - // WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); - WARN_ON(root == root->fs_info->extent_root && + WARN_ON(cow && root == root->fs_info->extent_root && !mutex_is_locked(&root->fs_info->alloc_mutex)); - WARN_ON(root == root->fs_info->chunk_root && - !mutex_is_locked(&root->fs_info->chunk_mutex)); - WARN_ON(root == root->fs_info->dev_root && - !mutex_is_locked(&root->fs_info->chunk_mutex)); if (ins_len < 0) lowest_unlock = 2; again: - if (!p->skip_locking) - b = btrfs_lock_root_node(root); - else + if (p->skip_locking) b = btrfs_root_node(root); + else + b = btrfs_lock_root_node(root); while (b) { level = btrfs_header_level(b); @@ -1308,20 +1309,52 @@ again: slot = p->slots[level]; BUG_ON(btrfs_header_nritems(b) == 1); } + unlock_up(p, level, lowest_unlock); + /* this is only true while dropping a snapshot */ if (level == lowest_level) { - unlock_up(p, level, lowest_unlock); break; } - if (should_reada) - reada_for_search(root, p, level, slot, - key->objectid); + blocknr = btrfs_node_blockptr(b, slot); + gen = btrfs_node_ptr_generation(b, slot); + blocksize = btrfs_level_size(root, level - 1); - b = read_node_slot(root, b, slot); + tmp = btrfs_find_tree_block(root, blocknr, blocksize); + if (tmp && btrfs_buffer_uptodate(tmp, gen)) { + b = tmp; + } else { + /* + * reduce lock contention at high levels + * of the btree by dropping locks before + * we read. + */ + if (level > 1) { + btrfs_release_path(NULL, p); + if (tmp) + free_extent_buffer(tmp); + if (should_reada) + reada_for_search(root, p, + level, slot, + key->objectid); + + tmp = read_tree_block(root, blocknr, + blocksize, gen); + if (tmp) + free_extent_buffer(tmp); + goto again; + } else { + if (tmp) + free_extent_buffer(tmp); + if (should_reada) + reada_for_search(root, p, + level, slot, + key->objectid); + b = read_node_slot(root, b, slot); + } + } if (!p->skip_locking) btrfs_tree_lock(b); - unlock_up(p, level, lowest_unlock); } else { p->slots[level] = slot; if (ins_len > 0 && btrfs_leaf_free_space(root, b) < @@ -1363,13 +1396,6 @@ static int fixup_low_keys(struct btrfs_trans_handle *trans, break; t = path->nodes[i]; btrfs_set_node_key(t, key, tslot); - if (!btrfs_tree_locked(path->nodes[i])) { - int ii; -printk("fixup without lock on level %d\n", btrfs_header_level(path->nodes[i])); - for (ii = 0; ii < BTRFS_MAX_LEVEL; ii++) { -printk("level %d slot %d\n", ii, path->slots[ii]); - } - } btrfs_mark_buffer_dirty(path->nodes[i]); if (tslot != 0) break; @@ -1804,6 +1830,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root if (slot >= btrfs_header_nritems(upper) - 1) return 1; + WARN_ON(!btrfs_tree_locked(path->nodes[1])); + right = read_node_slot(root, upper, slot + 1); btrfs_tree_lock(right); free_space = btrfs_leaf_free_space(root, right); @@ -1981,6 +2009,8 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root return 1; } + WARN_ON(!btrfs_tree_locked(path->nodes[1])); + left = read_node_slot(root, path->nodes[1], slot - 1); btrfs_tree_lock(left); free_space = btrfs_leaf_free_space(root, left); @@ -2935,6 +2965,186 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) return 1; } +/* + * A helper function to walk down the tree starting at min_key, and looking + * for nodes or leaves that are either in cache or have a minimum + * transaction id. This is used by the btree defrag code, but could + * also be used to search for blocks that have changed since a given + * transaction id. + * + * This does not cow, but it does stuff the starting key it finds back + * into min_key, so you can call btrfs_search_slot with cow=1 on the + * key and get a writable path. + * + * This does lock as it descends, and path->keep_locks should be set + * to 1 by the caller. + * + * This honors path->lowest_level to prevent descent past a given level + * of the tree. + * + * returns zero if something useful was found, < 0 on error and 1 if there + * was nothing in the tree that matched the search criteria. + */ +int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, + struct btrfs_path *path, int cache_only, + u64 min_trans) +{ + struct extent_buffer *cur; + struct btrfs_key found_key; + int slot; + u32 nritems; + int level; + int ret = 1; + +again: + cur = btrfs_lock_root_node(root); + level = btrfs_header_level(cur); + path->nodes[level] = cur; + path->locks[level] = 1; + + if (btrfs_header_generation(cur) < min_trans) { + ret = 1; + goto out; + } + while(1) { + nritems = btrfs_header_nritems(cur); + level = btrfs_header_level(cur); + bin_search(cur, min_key, level, &slot); + + /* at level = 0, we're done, setup the path and exit */ + if (level == 0) { + ret = 0; + path->slots[level] = slot; + btrfs_item_key_to_cpu(cur, &found_key, slot); + goto out; + } + /* + * check this node pointer against the cache_only and + * min_trans parameters. If it isn't in cache or is too + * old, skip to the next one. + */ + while(slot < nritems) { + u64 blockptr; + u64 gen; + struct extent_buffer *tmp; + blockptr = btrfs_node_blockptr(cur, slot); + gen = btrfs_node_ptr_generation(cur, slot); + if (gen < min_trans) { + slot++; + continue; + } + if (!cache_only) + break; + + tmp = btrfs_find_tree_block(root, blockptr, + btrfs_level_size(root, level - 1)); + + if (tmp && btrfs_buffer_uptodate(tmp, gen)) { + free_extent_buffer(tmp); + break; + } + if (tmp) + free_extent_buffer(tmp); + slot++; + } + /* + * we didn't find a candidate key in this node, walk forward + * and find another one + */ + if (slot >= nritems) { + ret = btrfs_find_next_key(root, path, min_key, level, + cache_only, min_trans); + if (ret == 0) { + btrfs_release_path(root, path); + goto again; + } else { + goto out; + } + } + /* save our key for returning back */ + btrfs_node_key_to_cpu(cur, &found_key, slot); + path->slots[level] = slot; + if (level == path->lowest_level) { + ret = 0; + unlock_up(path, level, 1); + goto out; + } + cur = read_node_slot(root, cur, slot); + + btrfs_tree_lock(cur); + path->locks[level - 1] = 1; + path->nodes[level - 1] = cur; + unlock_up(path, level, 1); + } +out: + if (ret == 0) + memcpy(min_key, &found_key, sizeof(found_key)); + return ret; +} + +/* + * this is similar to btrfs_next_leaf, but does not try to preserve + * and fixup the path. It looks for and returns the next key in the + * tree based on the current path and the cache_only and min_trans + * parameters. + * + * 0 is returned if another key is found, < 0 if there are any errors + * and 1 is returned if there are no higher keys in the tree + * + * path->keep_locks should be set to 1 on the search made before + * calling this function. + */ +int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, + struct btrfs_key *key, int lowest_level, + int cache_only, u64 min_trans) +{ + int level = lowest_level; + int slot; + struct extent_buffer *c; + + while(level < BTRFS_MAX_LEVEL) { + if (!path->nodes[level]) + return 1; + + slot = path->slots[level] + 1; + c = path->nodes[level]; +next: + if (slot >= btrfs_header_nritems(c)) { + level++; + if (level == BTRFS_MAX_LEVEL) { + return 1; + } + continue; + } + if (level == 0) + btrfs_item_key_to_cpu(c, key, slot); + else { + u64 blockptr = btrfs_node_blockptr(c, slot); + u64 gen = btrfs_node_ptr_generation(c, slot); + + if (cache_only) { + struct extent_buffer *cur; + cur = btrfs_find_tree_block(root, blockptr, + btrfs_level_size(root, level - 1)); + if (!cur || !btrfs_buffer_uptodate(cur, gen)) { + slot++; + if (cur) + free_extent_buffer(cur); + goto next; + } + free_extent_buffer(cur); + } + if (gen < min_trans) { + slot++; + goto next; + } + btrfs_node_key_to_cpu(c, key, slot); + } + return 0; + } + return 1; +} + /* * search the tree again to find a leaf with greater keys * returns 0 if it found something or 1 if there are no greater leaves. @@ -2957,15 +3167,23 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); - path->keep_locks = 1; btrfs_release_path(root, path); + path->keep_locks = 1; ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); path->keep_locks = 0; if (ret < 0) return ret; - if (path->slots[0] < nritems - 1) { + nritems = btrfs_header_nritems(path->nodes[0]); + /* + * by releasing the path above we dropped all our locks. A balance + * could have added more items next to the key that used to be + * at the very end of the block. So, check again here and + * advance the path if there are now more items available. + */ + if (nritems > 0 && path->slots[0] < nritems - 1) { + path->slots[0]++; goto done; } @@ -2992,8 +3210,10 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) reada_for_search(root, path, level, slot, 0); next = read_node_slot(root, c, slot); - if (!path->skip_locking) + if (!path->skip_locking) { + WARN_ON(!btrfs_tree_locked(c)); btrfs_tree_lock(next); + } break; } path->slots[level] = slot; @@ -3005,20 +3225,29 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) free_extent_buffer(c); path->nodes[level] = next; path->slots[level] = 0; - path->locks[level] = 1; + if (!path->skip_locking) + path->locks[level] = 1; if (!level) break; if (level == 1 && path->locks[1] && path->reada) reada_for_search(root, path, level, slot, 0); next = read_node_slot(root, next, 0); - if (!path->skip_locking) + if (!path->skip_locking) { + WARN_ON(!btrfs_tree_locked(path->nodes[level])); btrfs_tree_lock(next); + } } done: unlock_up(path, 0, 1); return 0; } +/* + * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps + * searching until it gets past min_objectid or finds an item of 'type' + * + * returns 0 if something is found, 1 if nothing was found and < 0 on error + */ int btrfs_previous_item(struct btrfs_root *root, struct btrfs_path *path, u64 min_objectid, int type)