Skip to contentSkip to conversation

btrfs: Turn name_cache radix tree into XArray in send_ctx

PATCH In review Gabriel Niebler 2 participants 4 messages Apr 26, 2022 – May 5, 2022 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 btrfs: Turn name_cache radix tree into XArray in send_ctx

… and adjust all usages of this object to use the XArray API for the sake of consistency.

XArray API provides array semantics, so it is notionally easier to use and understand, and it also takes care of locking for us.

None of this makes a real difference in this particular patch, but it does in other places where similar replacements are or have been made and we want to be consistent in our usage of data structures in btrfs.

---

Changes from v1:
- Let commit message begin with "btrfs: "

---
 fs/btrfs/send.c | 40 +++++++++++++++++++---------------------
 1 file changed, 19 insertions(+), 21 deletions(-)
fs/btrfs/send.c +19 -21
index 7d1642937274..19e39cdae0bb 100644
@@ -10,7 +10,6 @@
 #include <linux/mount.h>
 #include <linux/xattr.h>
 #include <linux/posix_acl_xattr.h>
-#include <linux/radix-tree.h>
 #include <linux/vmalloc.h>
 #include <linux/string.h>
 #include <linux/compat.h>
@@ -128,7 +127,7 @@ struct send_ctx {
 	struct list_head new_refs;
 	struct list_head deleted_refs;
 
-	struct radix_tree_root name_cache;
+	struct xarray name_cache;
 	struct list_head name_cache_list;
 	int name_cache_size;
 
@@ -262,14 +261,14 @@ struct orphan_dir_info {
 struct name_cache_entry {
 	struct list_head list;
 	/*
-	 * radix_tree has only 32bit entries but we need to handle 64bit inums.
-	 * We use the lower 32bit of the 64bit inum to store it in the tree. If
-	 * more then one inum would fall into the same entry, we use radix_list
-	 * to store the additional entries. radix_list is also used to store
-	 * entries where two entries have the same inum but different
+	 * On 32bit kernels, XArray has only 32bit indices, but we need to
+	 * handle 64bit inums. We use the lower 32bit of the 64bit inum to store
+	 * it in the tree. If more than one inum would fall into the same entry,
+	 * we use inum_aliases to store the additional entries. inum_aliases is
+	 * also used to store entries with the same inum but different
 	 * generations.
 	 */
-	struct list_head radix_list;
+	struct list_head inum_aliases;
 	u64 ino;
 	u64 gen;
 	u64 parent_ino;
@@ -2019,9 +2018,9 @@ static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
 }
 
 /*
- * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit,
+ * Insert a name cache entry. On 32bit kernels the XArray index is 32bit,
  * so we need to do some special handling in case we have clashes. This function
- * takes care of this with the help of name_cache_entry::radix_list.
+ * takes care of this with the help of name_cache_entry::inum_aliases.
  * In case of error, nce is kfreed.
  */
 static int name_cache_insert(struct send_ctx *sctx,
@@ -2030,8 +2029,7 @@ static int name_cache_insert(struct send_ctx *sctx,
 	int ret = 0;
 	struct list_head *nce_head;
 
-	nce_head = radix_tree_lookup(&sctx->name_cache,
-			(unsigned long)nce->ino);
+	nce_head = xa_load(&sctx->name_cache, (unsigned long)nce->ino);
 	if (!nce_head) {
 		nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
 		if (!nce_head) {
@@ -2040,14 +2038,15 @@ static int name_cache_insert(struct send_ctx *sctx,
 		}
 		INIT_LIST_HEAD(nce_head);
 
-		ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
+		ret = xa_insert(&sctx->name_cache, nce->ino, nce_head,
+				GFP_KERNEL);
 		if (ret < 0) {
 			kfree(nce_head);
 			kfree(nce);
 			return ret;
 		}
 	}
-	list_add_tail(&nce->radix_list, nce_head);
+	list_add_tail(&nce->inum_aliases, nce_head);
 	list_add_tail(&nce->list, &sctx->name_cache_list);
 	sctx->name_cache_size++;
 
@@ -2059,15 +2058,14 @@ static void name_cache_delete(struct send_ctx *sctx,
 {
 	struct list_head *nce_head;
 
-	nce_head = radix_tree_lookup(&sctx->name_cache,
-			(unsigned long)nce->ino);
+	nce_head = xa_load(&sctx->name_cache, (unsigned long)nce->ino);
 	if (!nce_head) {
 		btrfs_err(sctx->send_root->fs_info,
 	      "name_cache_delete lookup failed ino %llu cache size %d, leaking memory",
 			nce->ino, sctx->name_cache_size);
 	}
 
-	list_del(&nce->radix_list);
+	list_del(&nce->inum_aliases);
 	list_del(&nce->list);
 	sctx->name_cache_size--;
 
@@ -2075,7 +2073,7 @@ static void name_cache_delete(struct send_ctx *sctx,
 	 * We may not get to the final release of nce_head if the lookup fails
 	 */
 	if (nce_head && list_empty(nce_head)) {
-		radix_tree_delete(&sctx->name_cache, (unsigned long)nce->ino);
+		xa_erase(&sctx->name_cache, (unsigned long)nce->ino);
 		kfree(nce_head);
 	}
 }
@@ -2086,11 +2084,11 @@ static struct name_cache_entry *name_cache_search(struct send_ctx *sctx,
 	struct list_head *nce_head;
 	struct name_cache_entry *cur;
 
-	nce_head = radix_tree_lookup(&sctx->name_cache, (unsigned long)ino);
+	nce_head = xa_load(&sctx->name_cache, (unsigned long)ino);
 	if (!nce_head)
 		return NULL;
 
-	list_for_each_entry(cur, nce_head, radix_list) {
+	list_for_each_entry(cur, nce_head, inum_aliases) {
 		if (cur->ino == ino && cur->gen == gen)
 			return cur;
 	}
@@ -7534,7 +7532,7 @@ long btrfs_ioctl_send(struct inode *inode, struct btrfs_ioctl_send_args *arg)
 
 	INIT_LIST_HEAD(&sctx->new_refs);
 	INIT_LIST_HEAD(&sctx->deleted_refs);
-	INIT_RADIX_TREE(&sctx->name_cache, GFP_KERNEL);
+	xa_init_flags(&sctx->name_cache, GFP_KERNEL);
 	INIT_LIST_HEAD(&sctx->name_cache_list);
 
 	sctx->flags = arg->flags;
Signature · 1 line
2.35.3
Reviewed-by on v2 1/1
#1 lore raw
Quoted 11 lines · Gabriel Niebler

… and adjust all usages of this object to use the XArray API for the sake of consistency.

XArray API provides array semantics, so it is notionally easier to use and understand, and it also takes care of locking for us.

None of this makes a real difference in this particular patch, but it does in other places where similar replacements are or have been made and we want to be consistent in our usage of data structures in btrfs.

Quoted 9 lines

---

Changes from v1:
- Let commit message begin with "btrfs: "

---
  fs/btrfs/send.c | 40 +++++++++++++++++++---------------------
  1 file changed, 19 insertions(+), 21 deletions(-)

LGTM, one minor nit below though.

<snip>

Quoted 34 lines
fs/btrfs/send.c +8 -8
@@ -262,14 +261,14 @@ struct orphan_dir_info {
  struct name_cache_entry {
  	struct list_head list;
  	/*
-	 * radix_tree has only 32bit entries but we need to handle 64bit inums.
-	 * We use the lower 32bit of the 64bit inum to store it in the tree. If
-	 * more then one inum would fall into the same entry, we use radix_list
-	 * to store the additional entries. radix_list is also used to store
-	 * entries where two entries have the same inum but different
+	 * On 32bit kernels, XArray has only 32bit indices, but we need to
+	 * handle 64bit inums. We use the lower 32bit of the 64bit inum to store
+	 * it in the tree. If more than one inum would fall into the same entry,
+	 * we use inum_aliases to store the additional entries. inum_aliases is
+	 * also used to store entries with the same inum but different
  	 * generations.
  	 */
-	struct list_head radix_list;
+	struct list_head inum_aliases;
  	u64 ino;
  	u64 gen;
  	u64 parent_ino;
@@ -2019,9 +2018,9 @@ static int did_overwrite_first_ref(struct send_ctx *sctx, u64 ino, u64 gen)
  }
 
  /*
- * Insert a name cache entry. On 32bit kernels the radix tree index is 32bit,
+ * Insert a name cache entry. On 32bit kernels the XArray index is 32bit,
   * so we need to do some special handling in case we have clashes. This function
- * takes care of this with the help of name_cache_entry::radix_list.
+ * takes care of this with the help of name_cache_entry::inum_aliases.
   * In case of error, nce is kfreed.
   */
  static int name_cache_insert(struct send_ctx *sctx,

fs/btrfs/send.c static int name_cache_insert(struct send_ctx *sctx, · line 2032

Quoted 6 lines
fs/btrfs/send.c +1 -2
@@ -2030,8 +2029,7 @@ static int name_cache_insert(struct send_ctx *sctx,
  	int ret = 0;
  	struct list_head *nce_head;
 
-	nce_head = radix_tree_lookup(&sctx->name_cache,
-			(unsigned long)nce->ino);
+	nce_head = xa_load(&sctx->name_cache, (unsigned long)nce->ino);

The casting is redundant since the function's argument is already declared as unsigned long so truncation happens anyway. The only rationale to keep is for documentation purposes but even this is somewhat dubious. But since there is already something said about that above the definition of inum_aliases I'd say lets do away with the casts.

fs/btrfs/send.c static int name_cache_insert(struct send_ctx *sctx, · line 2041

Quoted 9 lines
fs/btrfs/send.c +1 -1
  	if (!nce_head) {
  		nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
  		if (!nce_head) {
@@ -2040,14 +2038,15 @@ static int name_cache_insert(struct send_ctx *sctx,
  		}
  		INIT_LIST_HEAD(nce_head);
 
-		ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
+		ret = xa_insert(&sctx->name_cache, nce->ino, nce_head,

Here nce->ino is not cast, yet the parameter is still unsigned long meaning truncation occurs (as is expected). At the very least this makes the code style inconsistent.

Quoted 12 lines
fs/btrfs/send.c +2 -1
+				GFP_KERNEL);
  		if (ret < 0) {
  			kfree(nce_head);
  			kfree(nce);
  			return ret;
  		}
  	}
-	list_add_tail(&nce->radix_list, nce_head);
+	list_add_tail(&nce->inum_aliases, nce_head);
  	list_add_tail(&nce->list, &sctx->name_cache_list);
  	sctx->name_cache_size++;
 

<snip>

#2 lore raw

Am 27.04.22 um 13:46 schrieb Nikolay Borisov:

Quoted 69 lines · Gabriel Niebler
Quoted 11 lines

… and adjust all usages of this object to use the XArray API for the sake of consistency.

XArray API provides array semantics, so it is notionally easier to use and understand, and it also takes care of locking for us.

None of this makes a real difference in this particular patch, but it does in other places where similar replacements are or have been made and we want to be consistent in our usage of data structures in btrfs.

Quoted 9 lines

---

Changes from v1:
  - Let commit message begin with "btrfs: "

---
  fs/btrfs/send.c | 40 +++++++++++++++++++---------------------

  1 file changed, 19 insertions(+), 21 deletions(-)

LGTM, one minor nit below though.

<snip>

Quoted 41 lines
fs/btrfs/send.c +0 -1
@@ -262,14 +261,14 @@ struct orphan_dir_info {
   struct name_cache_entry {
       struct list_head list;
       /*
-     * radix_tree has only 32bit entries but we need to handle 64bit 

inums.
-     * We use the lower 32bit of the 64bit inum to store it in the tree. If
-     * more then one inum would fall into the same entry, we use radix_list
-     * to store the additional entries. radix_list is also used to store -     * entries where two entries have the same inum but different +     * On 32bit kernels, XArray has only 32bit indices, but we need to +     * handle 64bit inums. We use the lower 32bit of the 64bit inum to store
+     * it in the tree. If more than one inum would fall into the same entry,
+     * we use inum_aliases to store the additional entries. inum_aliases is
+     * also used to store entries with the same inum but different
       * generations.
       */
-    struct list_head radix_list;
+    struct list_head inum_aliases;
      u64 ino;
      u64 gen;
      u64 parent_ino;

fs/btrfs/send.c +2 -2
@@ -2019,9 +2018,9 @@ static int did_overwrite_first_ref(struct 
 send_ctx *sctx, u64 ino, u64 gen)
   }
   /*
- * Insert a name cache entry. On 32bit kernels the radix tree index 
 is 32bit,
+ * Insert a name cache entry. On 32bit kernels the XArray index is 
 32bit,
    * so we need to do some special handling in case we have clashes. This function
- * takes care of this with the help of name_cache_entry::radix_list.
+ * takes care of this with the help of name_cache_entry::inum_aliases.
    * In case of error, nce is kfreed.

   */
  static int name_cache_insert(struct send_ctx *sctx,

Quoted 8 lines

fs/btrfs/send.c static int name_cache_insert(struct send_ctx *sctx, · line 2031

Quoted 6 lines
fs/btrfs/send.c +1 -2
@@ -2030,8 +2029,7 @@ static int name_cache_insert(struct send_ctx *sctx,
       int ret = 0;
       struct list_head *nce_head;
-    nce_head = radix_tree_lookup(&sctx->name_cache,
-            (unsigned long)nce->ino);
+    nce_head = xa_load(&sctx->name_cache, (unsigned long)nce->ino);

The casting is redundant since the function's argument is already declared as unsigned long so truncation happens anyway. The only rationale to keep is for documentation purposes but even this is somewhat dubious. But since there is already something said about that above the definition of inum_aliases I'd say lets do away with the casts.

I see your point and I agree with you, but I'd like to point out that I didn't add this cast - it was already there (and I think there may be others, too).

I thought about removing it (as we had discussed and I've done in another patch), but then I decided to leave it, thinking that maybe there was a reason for it. Like communicating something explicitely to anyone reading the code.

It's true, though, that the comment actually explains it.

Quoted 11 lines

fs/btrfs/send.c static int name_cache_insert(struct send_ctx · line 2041

Quoted 9 lines
fs/btrfs/send.c +1 -1
       if (!nce_head) {
           nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
           if (!nce_head) {
@@ -2040,14 +2038,15 @@ static int name_cache_insert(struct send_ctx 
 *sctx,
           }
           INIT_LIST_HEAD(nce_head);
-        ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
+        ret = xa_insert(&sctx->name_cache, nce->ino, nce_head,

Here nce->ino is not cast, yet the parameter is still unsigned long meaning truncation occurs (as is expected). At the very least this makes the code style inconsistent.

Yeah, true. Again, it was inconsistent before I got there, but I'll admit that I didn't notice this one.

For the sake of consistency, I'm willing to remove the cast (and perhaps others, would have to check) and resend.

I'll leave that up to the maintainer to decide.

#3 lore raw

Should I resend with the casts removed?

Am 27.04.22 um 16:36 schrieb Gabriel Niebler:

Quoted 105 lines

Am 27.04.22 um 13:46 schrieb Nikolay Borisov:

Quoted 71 lines · Gabriel Niebler
Quoted 11 lines

… and adjust all usages of this object to use the XArray API for the sake of consistency.

XArray API provides array semantics, so it is notionally easier to use and understand, and it also takes care of locking for us.

None of this makes a real difference in this particular patch, but it does in other places where similar replacements are or have been made and we want to be consistent in our usage of data structures in btrfs.

Quoted 9 lines

---

Changes from v1:
  - Let commit message begin with "btrfs: "

---
  fs/btrfs/send.c | 40 +++++++++++++++++++---------------------

  1 file changed, 19 insertions(+), 21 deletions(-)

LGTM, one minor nit below though.

<snip>

Quoted 43 lines
fs/btrfs/send.c +0 -1
@@ -262,14 +261,14 @@ struct orphan_dir_info {
   struct name_cache_entry {
       struct list_head list;
       /*
-     * radix_tree has only 32bit entries but we need to handle 64bit 

inums.
-     * We use the lower 32bit of the 64bit inum to store it in the tree. If
-     * more then one inum would fall into the same entry, we use radix_list
-     * to store the additional entries. radix_list is also used to store
-     * entries where two entries have the same inum but different +     * On 32bit kernels, XArray has only 32bit indices, but we need to +     * handle 64bit inums. We use the lower 32bit of the 64bit inum to store
+     * it in the tree. If more than one inum would fall into the same entry,
+     * we use inum_aliases to store the additional entries. inum_aliases is
+     * also used to store entries with the same inum but different
       * generations.
       */
-    struct list_head radix_list;
+    struct list_head inum_aliases;
      u64 ino;
      u64 gen;
      u64 parent_ino;

fs/btrfs/send.c +2 -2
@@ -2019,9 +2018,9 @@ static int did_overwrite_first_ref(struct 
 send_ctx *sctx, u64 ino, u64 gen)
   }
   /*
- * Insert a name cache entry. On 32bit kernels the radix tree index 
 is 32bit,
+ * Insert a name cache entry. On 32bit kernels the XArray index is 
 32bit,
    * so we need to do some special handling in case we have clashes. This function
- * takes care of this with the help of name_cache_entry::radix_list.
+ * takes care of this with the help of name_cache_entry::inum_aliases.
    * In case of error, nce is kfreed.

   */
  static int name_cache_insert(struct send_ctx *sctx,

(quoted diff) +0 -0
@@ -2030,8 +2029,7 @@ static int name_cache_insert(struct send_ctx 
Quoted 8 lines

fs/btrfs/send.c static int name_cache_insert(struct send_ctx *sctx, · line 2032

Quoted 6 lines
fs/btrfs/send.c +1 -2
 *sctx,
       int ret = 0;
       struct list_head *nce_head;
-    nce_head = radix_tree_lookup(&sctx->name_cache,
-            (unsigned long)nce->ino);
+    nce_head = xa_load(&sctx->name_cache, (unsigned long)nce->ino);

The casting is redundant since the function's argument is already declared as unsigned long so truncation happens anyway. The only rationale to keep is for documentation purposes but even this is somewhat dubious. But since there is already something said about that above the definition of inum_aliases I'd say lets do away with the casts.

I see your point and I agree with you, but I'd like to point out that I didn't add this cast - it was already there  (and I think there may be others, too).

I thought about removing it (as we had discussed and I've done in another patch), but then I decided to leave it, thinking that maybe there was a reason for it. Like communicating something explicitely to anyone reading the code.

It's true, though, that the comment actually explains it.

Quoted 11 lines

fs/btrfs/send.c static int name_cache_insert(struct send_ctx · line 2041

Quoted 9 lines
fs/btrfs/send.c +1 -1
       if (!nce_head) {
           nce_head = kmalloc(sizeof(*nce_head), GFP_KERNEL);
           if (!nce_head) {
@@ -2040,14 +2038,15 @@ static int name_cache_insert(struct send_ctx 
 *sctx,
           }
           INIT_LIST_HEAD(nce_head);
-        ret = radix_tree_insert(&sctx->name_cache, nce->ino, nce_head);
+        ret = xa_insert(&sctx->name_cache, nce->ino, nce_head,

Here nce->ino is not cast, yet the parameter is still unsigned long meaning truncation occurs (as is expected). At the very least this makes the code style inconsistent.

Yeah, true. Again, it was inconsistent before I got there, but I'll admit that I didn't notice this one.

For the sake of consistency, I'm willing to remove the cast (and perhaps others, would have to check) and resend.

I'll leave that up to the maintainer to decide.