From ff04981b3fffdc04bca324949545bd9545d86ab3 Mon Sep 17 00:00:00 2001 From: Miao Xie Date: Wed, 3 Jul 2013 21:25:14 +0800 Subject: [PATCH] Btrfs-progs: use rb-tree instead of extent cache tree for fs/file roots Because the fs/file roots are not extents, so it is better to use rb-tree to manage them. Fix it. Signed-off-by: Miao Xie Signed-off-by: Chris Mason --- ctree.h | 4 ++-- disk-io.c | 50 ++++++++++++++++++++++++++++++++++++-------------- 2 files changed, 38 insertions(+), 16 deletions(-) diff --git a/ctree.h b/ctree.h index 3fe14b0..4347c8a 100644 --- a/ctree.h +++ b/ctree.h @@ -909,7 +909,7 @@ struct btrfs_fs_info { struct btrfs_root *dev_root; struct btrfs_root *csum_root; - struct cache_tree fs_root_cache; + struct rb_root fs_root_tree; /* the log root tree is a directory of all the other log roots */ struct btrfs_root *log_root_tree; @@ -993,7 +993,7 @@ struct btrfs_root { /* the dirty list is only used by non-reference counted roots */ struct list_head dirty_list; - struct cache_extent cache; + struct rb_node rb_node; }; /* diff --git a/disk-io.c b/disk-io.c index 4541573..7140367 100644 --- a/disk-io.c +++ b/disk-io.c @@ -681,15 +681,15 @@ int btrfs_free_fs_root(struct btrfs_root *root) return 0; } -static void __free_fs_root(struct cache_extent *cache) +static void __free_fs_root(struct rb_node *node) { struct btrfs_root *root; - root = container_of(cache, struct btrfs_root, cache); + root = container_of(node, struct btrfs_root, rb_node); btrfs_free_fs_root(root); } -FREE_EXTENT_CACHE_BASED_TREE(fs_roots, __free_fs_root); +FREE_RB_BASED_TREE(fs_roots, __free_fs_root); struct btrfs_root *btrfs_read_fs_root_no_cache(struct btrfs_fs_info *fs_info, struct btrfs_key *location) @@ -751,11 +751,35 @@ insert: return root; } +static int btrfs_fs_roots_compare_objectids(struct rb_node *node, + void *data) +{ + u64 objectid = *((u64 *)data); + struct btrfs_root *root; + + root = rb_entry(node, struct btrfs_root, rb_node); + if (objectid > root->objectid) + return 1; + else if (objectid < root->objectid) + return -1; + else + return 0; +} + +static int btrfs_fs_roots_compare_roots(struct rb_node *node1, + struct rb_node *node2) +{ + struct btrfs_root *root; + + root = rb_entry(node2, struct btrfs_root, rb_node); + return btrfs_fs_roots_compare_objectids(node1, (void *)&root->objectid); +} + struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info, struct btrfs_key *location) { struct btrfs_root *root; - struct cache_extent *cache; + struct rb_node *node; int ret; if (location->objectid == BTRFS_ROOT_TREE_OBJECTID) @@ -772,18 +796,17 @@ struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info, BUG_ON(location->objectid == BTRFS_TREE_RELOC_OBJECTID || location->offset != (u64)-1); - cache = find_cache_extent(&fs_info->fs_root_cache, - location->objectid, 1); - if (cache) - return container_of(cache, struct btrfs_root, cache); + node = rb_search(&fs_info->fs_root_tree, (void *)&location->objectid, + btrfs_fs_roots_compare_objectids, NULL); + if (node) + return container_of(node, struct btrfs_root, rb_node); root = btrfs_read_fs_root_no_cache(fs_info, location); if (IS_ERR(root)) return root; - root->cache.start = location->objectid; - root->cache.size = 1; - ret = insert_cache_extent(&fs_info->fs_root_cache, &root->cache); + ret = rb_insert(&fs_info->fs_root_tree, &root->rb_node, + btrfs_fs_roots_compare_roots); BUG_ON(ret); return root; } @@ -835,8 +858,7 @@ struct btrfs_fs_info *btrfs_new_fs_info(int writable, u64 sb_bytenr) extent_io_tree_init(&fs_info->pinned_extents); extent_io_tree_init(&fs_info->pending_del); extent_io_tree_init(&fs_info->extent_ins); - - cache_tree_init(&fs_info->fs_root_cache); + fs_info->fs_root_tree = RB_ROOT; cache_tree_init(&fs_info->mapping_tree.cache_tree); mutex_init(&fs_info->fs_mutex); @@ -1383,7 +1405,7 @@ int close_ctree(struct btrfs_root *root) } btrfs_free_block_groups(fs_info); - free_fs_roots_tree(&fs_info->fs_root_cache); + free_fs_roots_tree(&fs_info->fs_root_tree); btrfs_release_all_roots(fs_info); btrfs_close_devices(fs_info->fs_devices); -- 2.7.4