[PATCH v6 84/99] btrfs: Convert fs_roots_radix to XArray

[Matthew Wilcox]

From: Matthew Wilcox 

Most of the gang lookups being done can be expressed just as efficiently
and somewhat more naturally as xa_for_each() loops.  I opted not to
change the one in btrfs_cleanup_fs_roots() as it's using SRCU which is
subtle and quick to anger.

Signed-off-by: Matthew Wilcox 
---
 fs/btrfs/ctree.h |  3 +-
 fs/btrfs/disk-io.c   | 65 +++--
 fs/btrfs/tests/btrfs-tests.c |  3 +-
 fs/btrfs/transaction.c   | 87 ++--
 4 files changed, 59 insertions(+), 99 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 13c260b525a1..173d72dfaab6 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -741,8 +741,7 @@ struct btrfs_fs_info {
/* the log root tree is a directory of all the other log roots */
struct btrfs_root *log_root_tree;
 
-   spinlock_t fs_roots_radix_lock;
-   struct radix_tree_root fs_roots_radix;
+   struct xarray fs_roots;
 
/* block group cache stuff */
spinlock_t block_group_cache_lock;
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index a8ecccfc36de..62995a55d112 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -1519,13 +1519,7 @@ int btrfs_init_fs_root(struct btrfs_root *root)
 struct btrfs_root *btrfs_lookup_fs_root(struct btrfs_fs_info *fs_info,
u64 root_id)
 {
-   struct btrfs_root *root;
-
-   spin_lock(_info->fs_roots_radix_lock);
-   root = radix_tree_lookup(_info->fs_roots_radix,
-(unsigned long)root_id);
-   spin_unlock(_info->fs_roots_radix_lock);
-   return root;
+   return xa_load(_info->fs_roots, (unsigned long)root_id);
 }
 
 int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info,
@@ -1533,18 +1527,13 @@ int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info,
 {
int ret;
 
-   ret = radix_tree_preload(GFP_NOFS);
-   if (ret)
-   return ret;
-
-   spin_lock(_info->fs_roots_radix_lock);
-   ret = radix_tree_insert(_info->fs_roots_radix,
+   xa_lock(_info->fs_roots);
+   ret = __xa_insert(_info->fs_roots,
(unsigned long)root->root_key.objectid,
-   root);
+   root, GFP_NOFS);
if (ret == 0)
set_bit(BTRFS_ROOT_IN_RADIX, >state);
-   spin_unlock(_info->fs_roots_radix_lock);
-   radix_tree_preload_end();
+   xa_unlock(_info->fs_roots);
 
return ret;
 }
@@ -2079,33 +2068,25 @@ static void free_root_pointers(struct btrfs_fs_info 
*info, int chunk_root)
 
 void btrfs_free_fs_roots(struct btrfs_fs_info *fs_info)
 {
-   int ret;
-   struct btrfs_root *gang[8];
-   int i;
+   struct btrfs_root *root;
+   unsigned long i = 0;
 
while (!list_empty(_info->dead_roots)) {
-   gang[0] = list_entry(fs_info->dead_roots.next,
+   root = list_entry(fs_info->dead_roots.next,
 struct btrfs_root, root_list);
-   list_del([0]->root_list);
+   list_del(>root_list);
 
-   if (test_bit(BTRFS_ROOT_IN_RADIX, [0]->state)) {
-   btrfs_drop_and_free_fs_root(fs_info, gang[0]);
+   if (test_bit(BTRFS_ROOT_IN_RADIX, >state)) {
+   btrfs_drop_and_free_fs_root(fs_info, root);
} else {
-   free_extent_buffer(gang[0]->node);
-   free_extent_buffer(gang[0]->commit_root);
-   btrfs_put_fs_root(gang[0]);
+   free_extent_buffer(root->node);
+   free_extent_buffer(root->commit_root);
+   btrfs_put_fs_root(root);
}
}
 
-   while (1) {
-   ret = radix_tree_gang_lookup(_info->fs_roots_radix,
-(void **)gang, 0,
-ARRAY_SIZE(gang));
-   if (!ret)
-   break;
-   for (i = 0; i < ret; i++)
-   btrfs_drop_and_free_fs_root(fs_info, gang[i]);
-   }
+   xa_for_each(_info->fs_roots, root, i, ULONG_MAX, XA_PRESENT)
+   btrfs_drop_and_free_fs_root(fs_info, root);
 
if (test_bit(BTRFS_FS_STATE_ERROR, _info->fs_state)) {
btrfs_free_log_root_tree(NULL, fs_info);
@@ -2447,7 +2428,7 @@ int open_ctree(struct super_block *sb,
goto fail_delalloc_bytes;
}
 
-   INIT_RADIX_TREE(_info->fs_roots_radix, GFP_ATOMIC);
+   xa_init(_info->fs_roots);
INIT_RADIX_TREE(_info->buffer_radix, GFP_ATOMIC);
INIT_LIST_HEAD(_info->trans_list);
INIT_LIST_HEAD(_info->dead_roots);
@@ -2456,7 +2437,6 @@ int open_ctree(struct super_block *sb,

[PATCH v6 84/99] btrfs: Convert fs_roots_radix to XArray

[Matthew Wilcox]

From: Matthew Wilcox 

Most of the gang lookups being done can be expressed just as efficiently
and somewhat more naturally as xa_for_each() loops.  I opted not to
change the one in btrfs_cleanup_fs_roots() as it's using SRCU which is
subtle and quick to anger.

Signed-off-by: Matthew Wilcox 
---
 fs/btrfs/ctree.h |  3 +-
 fs/btrfs/disk-io.c   | 65 +++--
 fs/btrfs/tests/btrfs-tests.c |  3 +-
 fs/btrfs/transaction.c   | 87 ++--
 4 files changed, 59 insertions(+), 99 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 13c260b525a1..173d72dfaab6 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -741,8 +741,7 @@ struct btrfs_fs_info {
/* the log root tree is a directory of all the other log roots */
struct btrfs_root *log_root_tree;
 
-   spinlock_t fs_roots_radix_lock;
-   struct radix_tree_root fs_roots_radix;
+   struct xarray fs_roots;
 
/* block group cache stuff */
spinlock_t block_group_cache_lock;
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index a8ecccfc36de..62995a55d112 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -1519,13 +1519,7 @@ int btrfs_init_fs_root(struct btrfs_root *root)
 struct btrfs_root *btrfs_lookup_fs_root(struct btrfs_fs_info *fs_info,
u64 root_id)
 {
-   struct btrfs_root *root;
-
-   spin_lock(_info->fs_roots_radix_lock);
-   root = radix_tree_lookup(_info->fs_roots_radix,
-(unsigned long)root_id);
-   spin_unlock(_info->fs_roots_radix_lock);
-   return root;
+   return xa_load(_info->fs_roots, (unsigned long)root_id);
 }
 
 int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info,
@@ -1533,18 +1527,13 @@ int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info,
 {
int ret;
 
-   ret = radix_tree_preload(GFP_NOFS);
-   if (ret)
-   return ret;
-
-   spin_lock(_info->fs_roots_radix_lock);
-   ret = radix_tree_insert(_info->fs_roots_radix,
+   xa_lock(_info->fs_roots);
+   ret = __xa_insert(_info->fs_roots,
(unsigned long)root->root_key.objectid,
-   root);
+   root, GFP_NOFS);
if (ret == 0)
set_bit(BTRFS_ROOT_IN_RADIX, >state);
-   spin_unlock(_info->fs_roots_radix_lock);
-   radix_tree_preload_end();
+   xa_unlock(_info->fs_roots);
 
return ret;
 }
@@ -2079,33 +2068,25 @@ static void free_root_pointers(struct btrfs_fs_info 
*info, int chunk_root)
 
 void btrfs_free_fs_roots(struct btrfs_fs_info *fs_info)
 {
-   int ret;
-   struct btrfs_root *gang[8];
-   int i;
+   struct btrfs_root *root;
+   unsigned long i = 0;
 
while (!list_empty(_info->dead_roots)) {
-   gang[0] = list_entry(fs_info->dead_roots.next,
+   root = list_entry(fs_info->dead_roots.next,
 struct btrfs_root, root_list);
-   list_del([0]->root_list);
+   list_del(>root_list);
 
-   if (test_bit(BTRFS_ROOT_IN_RADIX, [0]->state)) {
-   btrfs_drop_and_free_fs_root(fs_info, gang[0]);
+   if (test_bit(BTRFS_ROOT_IN_RADIX, >state)) {
+   btrfs_drop_and_free_fs_root(fs_info, root);
} else {
-   free_extent_buffer(gang[0]->node);
-   free_extent_buffer(gang[0]->commit_root);
-   btrfs_put_fs_root(gang[0]);
+   free_extent_buffer(root->node);
+   free_extent_buffer(root->commit_root);
+   btrfs_put_fs_root(root);
}
}
 
-   while (1) {
-   ret = radix_tree_gang_lookup(_info->fs_roots_radix,
-(void **)gang, 0,
-ARRAY_SIZE(gang));
-   if (!ret)
-   break;
-   for (i = 0; i < ret; i++)
-   btrfs_drop_and_free_fs_root(fs_info, gang[i]);
-   }
+   xa_for_each(_info->fs_roots, root, i, ULONG_MAX, XA_PRESENT)
+   btrfs_drop_and_free_fs_root(fs_info, root);
 
if (test_bit(BTRFS_FS_STATE_ERROR, _info->fs_state)) {
btrfs_free_log_root_tree(NULL, fs_info);
@@ -2447,7 +2428,7 @@ int open_ctree(struct super_block *sb,
goto fail_delalloc_bytes;
}
 
-   INIT_RADIX_TREE(_info->fs_roots_radix, GFP_ATOMIC);
+   xa_init(_info->fs_roots);
INIT_RADIX_TREE(_info->buffer_radix, GFP_ATOMIC);
INIT_LIST_HEAD(_info->trans_list);
INIT_LIST_HEAD(_info->dead_roots);
@@ -2456,7 +2437,6 @@ int open_ctree(struct super_block *sb,
INIT_LIST_HEAD(_info->caching_block_groups);