From 3c69faecb8d83cb2ef085a98b196a3fecea67725 Mon Sep 17 00:00:00 2001 From: Chris Mason Date: Tue, 7 Aug 2007 15:52:22 -0400 Subject: [PATCH] Btrfs: Fold some btree readahead routines into something more generic. Signed-off-by: Chris Mason --- fs/btrfs/ctree.c | 77 ++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/ctree.h | 1 + fs/btrfs/extent-tree.c | 30 +--------------- fs/btrfs/inode.c | 69 ++----------------------------------- 4 files changed, 81 insertions(+), 96 deletions(-) diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index aa824e2c521f..7a08491e208e 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c @@ -639,6 +639,73 @@ static int push_nodes_for_insert(struct btrfs_trans_handle *trans, return 1; } +/* + * readahead one full node of leaves + */ +static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, + int slot) +{ + struct btrfs_node *node; + int i; + u32 nritems; + u64 item_objectid; + u64 blocknr; + u64 search; + u64 cluster_start; + int ret; + int nread = 0; + int direction = path->reada; + struct radix_tree_root found; + unsigned long gang[8]; + struct buffer_head *bh; + + if (!path->nodes[1]) + return; + + node = btrfs_buffer_node(path->nodes[1]); + search = btrfs_node_blockptr(node, slot); + bh = btrfs_find_tree_block(root, search); + if (bh) { + brelse(bh); + return; + } + + init_bit_radix(&found); + nritems = btrfs_header_nritems(&node->header); + for (i = slot; i < nritems; i++) { + item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key); + blocknr = btrfs_node_blockptr(node, i); + set_radix_bit(&found, blocknr); + } + if (direction > 0) { + cluster_start = search - 4; + if (cluster_start > search) + cluster_start = 0; + } else + cluster_start = search + 4; + while(1) { + ret = find_first_radix_bit(&found, gang, 0, ARRAY_SIZE(gang)); + if (!ret) + break; + for (i = 0; i < ret; i++) { + blocknr = gang[i]; + clear_radix_bit(&found, blocknr); + if (nread > 64) + continue; + if (direction > 0 && cluster_start <= blocknr && + cluster_start + 8 > blocknr) { + cluster_start = blocknr; + readahead_tree_block(root, blocknr); + nread++; + } else if (direction < 0 && cluster_start >= blocknr && + blocknr + 8 > cluster_start) { + cluster_start = blocknr; + readahead_tree_block(root, blocknr); + nread++; + } + } + } +} /* * 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 @@ -660,9 +727,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root struct buffer_head *cow_buf; struct btrfs_node *c; struct btrfs_root_item *root_item = &root->root_item; + u64 blocknr; int slot; int ret; int level; + int should_reada = p->reada; u8 lowest_level = 0; if (btrfs_root_refs(root_item) == 0 && root->ref_cows) { @@ -728,7 +797,11 @@ again: /* this is only true while dropping a snapshot */ if (level == lowest_level) break; + blocknr = btrfs_node_blockptr(c, slot); + if (level == 1 && should_reada) + reada_for_search(root, p, slot); b = read_tree_block(root, btrfs_node_blockptr(c, slot)); + } else { struct btrfs_leaf *l = (struct btrfs_leaf *)c; p->slots[level] = slot; @@ -1915,6 +1988,8 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) blocknr = btrfs_node_blockptr(c_node, slot); if (next) btrfs_block_release(root, next); + if (level == 1 && path->reada) + reada_for_search(root, path, slot); next = read_tree_block(root, blocknr); break; } @@ -1927,6 +2002,8 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) path->slots[level] = 0; if (!level) break; + if (level == 1 && path->reada) + reada_for_search(root, path, slot); next = read_tree_block(root, btrfs_node_blockptr(btrfs_buffer_node(next), 0)); } diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 73c2e75a136d..c5a18d5d7f7c 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -177,6 +177,7 @@ struct btrfs_node { struct btrfs_path { struct buffer_head *nodes[BTRFS_MAX_LEVEL]; int slots[BTRFS_MAX_LEVEL]; + int reada; }; /* diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 9455974dabea..5d4d5d8db8ef 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -32,33 +32,6 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct static int del_pending_extents(struct btrfs_trans_handle *trans, struct btrfs_root *extent_root); -static void reada_extent_leaves(struct btrfs_root *root, - struct btrfs_path *path, u64 limit) -{ - struct btrfs_node *node; - int i; - int nritems; - u64 item_objectid; - u64 blocknr; - int slot; - int ret; - - if (!path->nodes[1]) - return; - node = btrfs_buffer_node(path->nodes[1]); - slot = path->slots[1] + 1; - nritems = btrfs_header_nritems(&node->header); - for (i = slot; i < nritems && i < slot + 8; i++) { - item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key); - if (item_objectid > limit) - break; - blocknr = btrfs_node_blockptr(node, i); - ret = readahead_tree_block(root, blocknr); - if (ret) - break; - } -} - static int cache_block_group(struct btrfs_root *root, struct btrfs_block_group_cache *block_group) { @@ -84,6 +57,7 @@ static int cache_block_group(struct btrfs_root *root, path = btrfs_alloc_path(); if (!path) return -ENOMEM; + path->reada = 1; key.objectid = block_group->key.objectid; key.flags = 0; key.offset = 0; @@ -94,12 +68,10 @@ static int cache_block_group(struct btrfs_root *root, if (ret && path->slots[0] > 0) path->slots[0]--; limit = block_group->key.objectid + block_group->key.offset; - reada_extent_leaves(root, path, limit); while(1) { leaf = btrfs_buffer_leaf(path->nodes[0]); slot = path->slots[0]; if (slot >= btrfs_header_nritems(&leaf->header)) { - reada_extent_leaves(root, path, limit); ret = btrfs_next_leaf(root, path); if (ret < 0) goto err; diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index fa9c531c86b7..3889032fc449 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -374,40 +374,6 @@ static int btrfs_free_inode(struct btrfs_trans_handle *trans, return ret; } -/* - * truncates go from a high offset to a low offset. So, walk - * from hi to lo in the node and issue readas. Stop when you find - * keys from a different objectid - */ -static void reada_truncate(struct btrfs_root *root, struct btrfs_path *path, - u64 objectid) -{ - struct btrfs_node *node; - int i; - int nritems; - u64 item_objectid; - u64 blocknr; - int slot; - int ret; - - if (!path->nodes[1]) - return; - node = btrfs_buffer_node(path->nodes[1]); - slot = path->slots[1]; - if (slot == 0) - return; - nritems = btrfs_header_nritems(&node->header); - for (i = slot - 1; i >= 0; i--) { - item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key); - if (item_objectid != objectid) - break; - blocknr = btrfs_node_blockptr(node, i); - ret = readahead_tree_block(root, blocknr); - if (ret) - break; - } -} - /* * this can truncate away extent items, csum items and directory items. * It starts at a high offset and removes keys until it can't find @@ -434,6 +400,7 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, int del_item; path = btrfs_alloc_path(); + path->reada = -1; BUG_ON(!path); /* FIXME, add redo link to tree so we don't leak on crash */ key.objectid = inode->i_ino; @@ -450,7 +417,6 @@ static int btrfs_truncate_in_trans(struct btrfs_trans_handle *trans, BUG_ON(path->slots[0] == 0); path->slots[0]--; } - reada_truncate(root, path, inode->i_ino); leaf = btrfs_buffer_leaf(path->nodes[0]); found_key = &leaf->items[path->slots[0]].key; found_type = btrfs_disk_key_type(found_key); @@ -827,36 +793,6 @@ static struct dentry *btrfs_lookup(struct inode *dir, struct dentry *dentry, return d_splice_alias(inode, dentry); } -/* - * readahead one full node of leaves as long as their keys include - * the objectid supplied - */ -static void reada_leaves(struct btrfs_root *root, struct btrfs_path *path, - u64 objectid) -{ - struct btrfs_node *node; - int i; - u32 nritems; - u64 item_objectid; - u64 blocknr; - int slot; - int ret; - - if (!path->nodes[1]) - return; - node = btrfs_buffer_node(path->nodes[1]); - slot = path->slots[1]; - nritems = btrfs_header_nritems(&node->header); - for (i = slot + 1; i < nritems; i++) { - item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key); - if (item_objectid != objectid) - break; - blocknr = btrfs_node_blockptr(node, i); - ret = readahead_tree_block(root, blocknr); - if (ret) - break; - } -} static unsigned char btrfs_filetype_table[] = { DT_UNKNOWN, DT_REG, DT_DIR, DT_CHR, DT_BLK, DT_FIFO, DT_SOCK, DT_LNK }; @@ -890,18 +826,17 @@ static int btrfs_readdir(struct file *filp, void *dirent, filldir_t filldir) btrfs_set_key_type(&key, key_type); key.offset = filp->f_pos; path = btrfs_alloc_path(); + path->reada = 1; ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); if (ret < 0) goto err; advance = 0; - reada_leaves(root, path, inode->i_ino); while(1) { leaf = btrfs_buffer_leaf(path->nodes[0]); nritems = btrfs_header_nritems(&leaf->header); slot = path->slots[0]; if (advance || slot >= nritems) { if (slot >= nritems -1) { - reada_leaves(root, path, inode->i_ino); ret = btrfs_next_leaf(root, path); if (ret) break; -- 2.30.2