[PATCH v6 93/99] f2fs: Convert ino_root to XArray

[Matthew Wilcox]

From: Matthew Wilcox 

I did a fairly major rewrite of __add_ino_entry(); please check carefully.
Also, we can remove ino_list unless it's important to write out orphan
inodes in the order they were orphaned.  It may also make more sense to
combine the array of inode_management structures into a single XArray
with tags, but that would be a job for someone who understands this
filesystem better than I do.

Signed-off-by: Matthew Wilcox 
---
 fs/f2fs/checkpoint.c | 85 +++-
 fs/f2fs/f2fs.h   |  3 +-
 2 files changed, 38 insertions(+), 50 deletions(-)

diff --git a/fs/f2fs/checkpoint.c b/fs/f2fs/checkpoint.c
index 4aa69bc1c70a..04d69679da13 100644
--- a/fs/f2fs/checkpoint.c
+++ b/fs/f2fs/checkpoint.c
@@ -403,33 +403,30 @@ static void __add_ino_entry(struct f2fs_sb_info *sbi, 
nid_t ino,
struct inode_management *im = >im[type];
struct ino_entry *e, *tmp;
 
-   tmp = f2fs_kmem_cache_alloc(ino_entry_slab, GFP_NOFS);
-
-   radix_tree_preload(GFP_NOFS | __GFP_NOFAIL);
-
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
-   if (!e) {
-   e = tmp;
-   if (unlikely(radix_tree_insert(>ino_root, ino, e)))
-   f2fs_bug_on(sbi, 1);
-
-   memset(e, 0, sizeof(struct ino_entry));
-   e->ino = ino;
-
-   list_add_tail(>list, >ino_list);
-   if (type != ORPHAN_INO)
-   im->ino_num++;
+   xa_lock(>ino_root);
+   e = xa_load(>ino_root, ino);
+   if (e)
+   goto found;
+   xa_unlock(>ino_root);
+
+   tmp = f2fs_kmem_cache_alloc(ino_entry_slab, GFP_NOFS | __GFP_ZERO);
+   xa_lock(>ino_root);
+   e = __xa_cmpxchg(>ino_root, ino, NULL, tmp,
+   GFP_NOFS | __GFP_NOFAIL);
+   if (e) {
+   kmem_cache_free(ino_entry_slab, tmp);
+   goto found;
}
+   e = tmp;
 
+   e->ino = ino;
+   list_add_tail(>list, >ino_list);
+   if (type != ORPHAN_INO)
+   im->ino_num++;
+found:
if (type == FLUSH_INO)
f2fs_set_bit(devidx, (char *)>dirty_device);
-
-   spin_unlock(>ino_lock);
-   radix_tree_preload_end();
-
-   if (e != tmp)
-   kmem_cache_free(ino_entry_slab, tmp);
+   xa_unlock(>ino_root);
 }
 
 static void __remove_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, int type)
@@ -437,17 +434,14 @@ static void __remove_ino_entry(struct f2fs_sb_info *sbi, 
nid_t ino, int type)
struct inode_management *im = >im[type];
struct ino_entry *e;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
+   xa_lock(>ino_root);
+   e = __xa_erase(>ino_root, ino);
if (e) {
list_del(>list);
-   radix_tree_delete(>ino_root, ino);
im->ino_num--;
-   spin_unlock(>ino_lock);
kmem_cache_free(ino_entry_slab, e);
-   return;
}
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
 }
 
 void add_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, int type)
@@ -466,12 +460,8 @@ void remove_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, 
int type)
 bool exist_written_data(struct f2fs_sb_info *sbi, nid_t ino, int mode)
 {
struct inode_management *im = >im[mode];
-   struct ino_entry *e;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
-   spin_unlock(>ino_lock);
-   return e ? true : false;
+   return xa_load(>ino_root, ino) ? true : false;
 }
 
 void release_ino_entry(struct f2fs_sb_info *sbi, bool all)
@@ -482,14 +472,14 @@ void release_ino_entry(struct f2fs_sb_info *sbi, bool all)
for (i = all ? ORPHAN_INO : APPEND_INO; i < MAX_INO_ENTRY; i++) {
struct inode_management *im = >im[i];
 
-   spin_lock(>ino_lock);
+   xa_lock(>ino_root);
list_for_each_entry_safe(e, tmp, >ino_list, list) {
list_del(>list);
-   radix_tree_delete(>ino_root, e->ino);
+   __xa_erase(>ino_root, e->ino);
kmem_cache_free(ino_entry_slab, e);
im->ino_num--;
}
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
}
 }
 
@@ -506,11 +496,11 @@ bool is_dirty_device(struct f2fs_sb_info *sbi, nid_t ino,
struct ino_entry *e;
bool is_dirty = false;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
+   xa_lock(>ino_root);
+   e = xa_load(>ino_root, ino);
if (e && f2fs_test_bit(devidx, (char *)>dirty_device))
is_dirty = true;
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
return is_dirty;
 }
 
@@ -519,11 +509,11 @@ int 

[PATCH v6 93/99] f2fs: Convert ino_root to XArray

[Matthew Wilcox]

From: Matthew Wilcox 

I did a fairly major rewrite of __add_ino_entry(); please check carefully.
Also, we can remove ino_list unless it's important to write out orphan
inodes in the order they were orphaned.  It may also make more sense to
combine the array of inode_management structures into a single XArray
with tags, but that would be a job for someone who understands this
filesystem better than I do.

Signed-off-by: Matthew Wilcox 
---
 fs/f2fs/checkpoint.c | 85 +++-
 fs/f2fs/f2fs.h   |  3 +-
 2 files changed, 38 insertions(+), 50 deletions(-)

diff --git a/fs/f2fs/checkpoint.c b/fs/f2fs/checkpoint.c
index 4aa69bc1c70a..04d69679da13 100644
--- a/fs/f2fs/checkpoint.c
+++ b/fs/f2fs/checkpoint.c
@@ -403,33 +403,30 @@ static void __add_ino_entry(struct f2fs_sb_info *sbi, 
nid_t ino,
struct inode_management *im = >im[type];
struct ino_entry *e, *tmp;
 
-   tmp = f2fs_kmem_cache_alloc(ino_entry_slab, GFP_NOFS);
-
-   radix_tree_preload(GFP_NOFS | __GFP_NOFAIL);
-
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
-   if (!e) {
-   e = tmp;
-   if (unlikely(radix_tree_insert(>ino_root, ino, e)))
-   f2fs_bug_on(sbi, 1);
-
-   memset(e, 0, sizeof(struct ino_entry));
-   e->ino = ino;
-
-   list_add_tail(>list, >ino_list);
-   if (type != ORPHAN_INO)
-   im->ino_num++;
+   xa_lock(>ino_root);
+   e = xa_load(>ino_root, ino);
+   if (e)
+   goto found;
+   xa_unlock(>ino_root);
+
+   tmp = f2fs_kmem_cache_alloc(ino_entry_slab, GFP_NOFS | __GFP_ZERO);
+   xa_lock(>ino_root);
+   e = __xa_cmpxchg(>ino_root, ino, NULL, tmp,
+   GFP_NOFS | __GFP_NOFAIL);
+   if (e) {
+   kmem_cache_free(ino_entry_slab, tmp);
+   goto found;
}
+   e = tmp;
 
+   e->ino = ino;
+   list_add_tail(>list, >ino_list);
+   if (type != ORPHAN_INO)
+   im->ino_num++;
+found:
if (type == FLUSH_INO)
f2fs_set_bit(devidx, (char *)>dirty_device);
-
-   spin_unlock(>ino_lock);
-   radix_tree_preload_end();
-
-   if (e != tmp)
-   kmem_cache_free(ino_entry_slab, tmp);
+   xa_unlock(>ino_root);
 }
 
 static void __remove_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, int type)
@@ -437,17 +434,14 @@ static void __remove_ino_entry(struct f2fs_sb_info *sbi, 
nid_t ino, int type)
struct inode_management *im = >im[type];
struct ino_entry *e;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
+   xa_lock(>ino_root);
+   e = __xa_erase(>ino_root, ino);
if (e) {
list_del(>list);
-   radix_tree_delete(>ino_root, ino);
im->ino_num--;
-   spin_unlock(>ino_lock);
kmem_cache_free(ino_entry_slab, e);
-   return;
}
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
 }
 
 void add_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, int type)
@@ -466,12 +460,8 @@ void remove_ino_entry(struct f2fs_sb_info *sbi, nid_t ino, 
int type)
 bool exist_written_data(struct f2fs_sb_info *sbi, nid_t ino, int mode)
 {
struct inode_management *im = >im[mode];
-   struct ino_entry *e;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
-   spin_unlock(>ino_lock);
-   return e ? true : false;
+   return xa_load(>ino_root, ino) ? true : false;
 }
 
 void release_ino_entry(struct f2fs_sb_info *sbi, bool all)
@@ -482,14 +472,14 @@ void release_ino_entry(struct f2fs_sb_info *sbi, bool all)
for (i = all ? ORPHAN_INO : APPEND_INO; i < MAX_INO_ENTRY; i++) {
struct inode_management *im = >im[i];
 
-   spin_lock(>ino_lock);
+   xa_lock(>ino_root);
list_for_each_entry_safe(e, tmp, >ino_list, list) {
list_del(>list);
-   radix_tree_delete(>ino_root, e->ino);
+   __xa_erase(>ino_root, e->ino);
kmem_cache_free(ino_entry_slab, e);
im->ino_num--;
}
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
}
 }
 
@@ -506,11 +496,11 @@ bool is_dirty_device(struct f2fs_sb_info *sbi, nid_t ino,
struct ino_entry *e;
bool is_dirty = false;
 
-   spin_lock(>ino_lock);
-   e = radix_tree_lookup(>ino_root, ino);
+   xa_lock(>ino_root);
+   e = xa_load(>ino_root, ino);
if (e && f2fs_test_bit(devidx, (char *)>dirty_device))
is_dirty = true;
-   spin_unlock(>ino_lock);
+   xa_unlock(>ino_root);
return is_dirty;
 }
 
@@ -519,11 +509,11 @@ int acquire_orphan_inode(struct f2fs_sb_info *sbi)
struct