Skip to contentSkip to conversation

btrfs: relocation: Fix KASAN reports caused by extended reloc tree lifespan

PATCH In review Qu Wenruo 5 participants 16 messages Jan 8, 2020 – Jan 13, 2020 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

PATCH v2 1/1 btrfs: relocation: Fix KASAN reports caused by extended reloc tree lifespan

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

   should_ignore_root+0x54/0xb0 [btrfs]
   build_backref_tree+0x11af/0x2280 [btrfs]
   relocate_tree_blocks+0x391/0xb80 [btrfs]
   relocate_block_group+0x3e5/0xa00 [btrfs]
   btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
   btrfs_relocate_chunk+0x53/0xf0 [btrfs]
   btrfs_balance+0xc91/0x1840 [btrfs]
   btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
   btrfs_ioctl+0x8af/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   create_reloc_root+0x9f/0x460 [btrfs]
   btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
   create_pending_snapshot+0xa9b/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
   create_pending_snapshot+0x209/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

	NULL: reloc_root is NULL	PTR: reloc_root is not NULL
	0: DEAD_RELOC_ROOT bit not set	DEAD: DEAD_RELOC_ROOT bit set

	(NULL, 0)    Initial state		 __
	  |					 /\ Section A
        btrfs_init_reloc_root()			 \/
	  |				 	 __
	(PTR, 0)     reloc_root initialized      /\
          |					 |
	btrfs_update_reloc_root()		 |  Section B
          |					 |
	(PTR, DEAD)  reloc_root has been merged  \/
          |					 __
	=== btrfs_commit_transaction() ====================
	  |					 /\
	clean_dirty_subvols()			 |
	  |					 |  Section C
	(NULL, DEAD) reloc_root cleanup starts   \/
          |					 __
	btrfs_drop_snapshot()			 /\
	  |					 |  Section D
	(NULL, 0)    Back to initial state	 \/

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.

---
 fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +28 -4
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct btrfs_trans_handle *trans,
 	return 1;
 }
 
+/*
+ * Check if this subvolume tree has valid reloc(*) tree.
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.
+ *    But should_ignore_root() below is a special case.
+ */
+static bool have_reloc_root(struct btrfs_root *root)
+{
+	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+		return false;
+	if (!root->reloc_root)
+		return false;
+	return true;
+}
 
 static int should_ignore_root(struct btrfs_root *root)
 {
@@ -525,6 +541,10 @@ static int should_ignore_root(struct btrfs_root *root)
 	if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
 		return 0;
 
+	/* This root has been merged with its reloc tree, we can ignore it */
+	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+		return 1;
+
 	reloc_root = root->reloc_root;
 	if (!reloc_root)
 		return 0;
@@ -1478,8 +1498,7 @@ int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
 	struct btrfs_root_item *root_item;
 	int ret;
 
-	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state) ||
-	    !root->reloc_root)
+	if (!have_reloc_root(root))
 		goto out;
 
 	reloc_root = root->reloc_root;
@@ -2201,6 +2220,11 @@ static int clean_dirty_subvols(struct reloc_control *rc)
 				if (ret2 < 0 && !ret)
 					ret = ret2;
 			}
+			/*
+			 * Need barrier to ensure clear_bit() only happens after
+			 * root->reloc_root = NULL.
+			 */
+			smp_mb__before_atomic();
 			clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
 			btrfs_put_fs_root(root);
 		} else {
@@ -4717,7 +4741,7 @@ void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
 	struct btrfs_root *root = pending->root;
 	struct reloc_control *rc = root->fs_info->reloc_ctl;
 
-	if (!root->reloc_root || !rc)
+	if (!rc || !have_reloc_root(root))
 		return;
 
 	if (!rc->merge_reloc_tree)
@@ -4751,7 +4775,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
 	struct reloc_control *rc = root->fs_info->reloc_ctl;
 	int ret;
 
-	if (!root->reloc_root || !rc)
+	if (!rc || !have_reloc_root(root))
 		return 0;
 
 	rc = root->fs_info->reloc_ctl;
Signature · 1 line
2.24.1
#1 lore raw
Quoted 49 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

   should_ignore_root+0x54/0xb0 [btrfs]
   build_backref_tree+0x11af/0x2280 [btrfs]
   relocate_tree_blocks+0x391/0xb80 [btrfs]
   relocate_block_group+0x3e5/0xa00 [btrfs]
   btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
   btrfs_relocate_chunk+0x53/0xf0 [btrfs]
   btrfs_balance+0xc91/0x1840 [btrfs]
   btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
   btrfs_ioctl+0x8af/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   create_reloc_root+0x9f/0x460 [btrfs]
   btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
   create_pending_snapshot+0xa9b/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
   create_pending_snapshot+0x209/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe
Quoted 3 lines

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount

what do you mean by "root->reloc_root can undergo btrfs_drop_snapshot" ?

Quoted 2 lines

based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

what's the relationship between not having a refcount protection and reaching reloc roots, perhaps you could expand the explanation?

Quoted 40 lines

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

	NULL: reloc_root is NULL	PTR: reloc_root is not NULL
	0: DEAD_RELOC_ROOT bit not set	DEAD: DEAD_RELOC_ROOT bit set

	(NULL, 0)    Initial state		 __
	  |					 /\ Section A
        btrfs_init_reloc_root()			 \/
	  |				 	 __
	(PTR, 0)     reloc_root initialized      /\
          |					 |
	btrfs_update_reloc_root()		 |  Section B
          |					 |
	(PTR, DEAD)  reloc_root has been merged  \/
          |					 __
	=== btrfs_commit_transaction() ====================
	  |					 /\
	clean_dirty_subvols()			 |
	  |					 |  Section C
	(NULL, DEAD) reloc_root cleanup starts   \/
          |					 __
	btrfs_drop_snapshot()			 /\
	  |					 |  Section D
	(NULL, 0)    Back to initial state	 \/
Quoted 1 line

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a

^^ Perhaps you meant: Every caller of have_reloc_root or
test_bit(DED_RELOC_ROOT) holds a transaction handle which ensures modifications in those function are limited to a single transaction?

Quoted 125 lines

transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.

---
 fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----
 1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +28 -4
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct btrfs_trans_handle *trans,
 	return 1;
 }
 
+/*
+ * Check if this subvolume tree has valid reloc(*) tree.
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.
+ *    But should_ignore_root() below is a special case.
+ */
+static bool have_reloc_root(struct btrfs_root *root)
+{
+	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+		return false;
+	if (!root->reloc_root)
+		return false;
+	return true;
+}
 
 static int should_ignore_root(struct btrfs_root *root)
 {
@@ -525,6 +541,10 @@ static int should_ignore_root(struct btrfs_root *root)
 	if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
 		return 0;
 
+	/* This root has been merged with its reloc tree, we can ignore it */
+	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+		return 1;
+
 	reloc_root = root->reloc_root;
 	if (!reloc_root)
 		return 0;
@@ -1478,8 +1498,7 @@ int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
 	struct btrfs_root_item *root_item;
 	int ret;
 
-	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state) ||
-	    !root->reloc_root)
+	if (!have_reloc_root(root))
 		goto out;
 
 	reloc_root = root->reloc_root;
@@ -2201,6 +2220,11 @@ static int clean_dirty_subvols(struct reloc_control *rc)
 				if (ret2 < 0 && !ret)
 					ret = ret2;
 			}
+			/*
+			 * Need barrier to ensure clear_bit() only happens after
+			 * root->reloc_root = NULL.
+			 */
+			smp_mb__before_atomic();
 			clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
 			btrfs_put_fs_root(root);
 		} else {
@@ -4717,7 +4741,7 @@ void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
 	struct btrfs_root *root = pending->root;
 	struct reloc_control *rc = root->fs_info->reloc_ctl;
 
-	if (!root->reloc_root || !rc)
+	if (!rc || !have_reloc_root(root))
 		return;
 
 	if (!rc->merge_reloc_tree)
@@ -4751,7 +4775,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
 	struct reloc_control *rc = root->fs_info->reloc_ctl;
 	int ret;
 
-	if (!root->reloc_root || !rc)
+	if (!rc || !have_reloc_root(root))
 		return 0;
 
 	rc = root->fs_info->reloc_ctl;
author
#2 lore raw
Quoted 52 lines · Nikolay Borisov
Quoted 49 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

   should_ignore_root+0x54/0xb0 [btrfs]
   build_backref_tree+0x11af/0x2280 [btrfs]
   relocate_tree_blocks+0x391/0xb80 [btrfs]
   relocate_block_group+0x3e5/0xa00 [btrfs]
   btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
   btrfs_relocate_chunk+0x53/0xf0 [btrfs]
   btrfs_balance+0xc91/0x1840 [btrfs]
   btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
   btrfs_ioctl+0x8af/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   create_reloc_root+0x9f/0x460 [btrfs]
   btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
   create_pending_snapshot+0xa9b/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe

   btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
   create_pending_snapshot+0x209/0x15f0 [btrfs]
   create_pending_snapshots+0x111/0x140 [btrfs]
   btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
   btrfs_mksubvol+0x915/0x960 [btrfs]
   btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
   btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
   btrfs_ioctl+0x241b/0x3e60 [btrfs]
   do_vfs_ioctl+0x831/0xb10
   ksys_ioctl+0x67/0x90
   __x64_sys_ioctl+0x43/0x50
   do_syscall_64+0x79/0xe0
   entry_SYSCALL_64_after_hwframe+0x49/0xbe
Quoted 5 lines
Quoted 3 lines

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount

what do you mean by "root->reloc_root can undergo btrfs_drop_snapshot" ?

I mean some caller got root->reloc_root and use it, while root->reloc_root soon get dropped by btrfs_drop_snapshot().

Quoted 5 lines
Quoted 3 lines

based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

what's the relationship between not having a refcount protection and reaching reloc roots, perhaps you could expand the explanation?

If we had a proper refcount protection, we could wait until we're the last holder of reloc_root before calling btrfs_drop_snapshot().

And to me, that should be the correct solution, while this patch is just a quick and maybe dirty fix mostly for backport.

Quoted 41 lines
Quoted 41 lines

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

	NULL: reloc_root is NULL	PTR: reloc_root is not NULL
	0: DEAD_RELOC_ROOT bit not set	DEAD: DEAD_RELOC_ROOT bit set

	(NULL, 0)    Initial state		 __
	  |					 /\ Section A
        btrfs_init_reloc_root()			 \/
	  |				 	 __
	(PTR, 0)     reloc_root initialized      /\
          |					 |
	btrfs_update_reloc_root()		 |  Section B
          |					 |
	(PTR, DEAD)  reloc_root has been merged  \/
          |					 __
	=== btrfs_commit_transaction() ====================
	  |					 /\
	clean_dirty_subvols()			 |
	  |					 |  Section C
	(NULL, DEAD) reloc_root cleanup starts   \/
          |					 __
	btrfs_drop_snapshot()			 /\
	  |					 |  Section D
	(NULL, 0)    Back to initial state	 \/
Quoted 5 lines
Quoted 1 line

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a

^^ Perhaps you meant: Every caller of have_reloc_root or
test_bit(DED_RELOC_ROOT) holds a transaction handle which ensures modifications in those function are limited to a single transaction?

Yep, I mean *E*very.
It looks I need to replace the switch of my 'e' key...

Thanks,
Qu

#3 lore raw
In reply to Qu Wenruo
Quoted 151 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

    should_ignore_root+0x54/0xb0 [btrfs]
    build_backref_tree+0x11af/0x2280 [btrfs]
    relocate_tree_blocks+0x391/0xb80 [btrfs]
    relocate_block_group+0x3e5/0xa00 [btrfs]
    btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
    btrfs_relocate_chunk+0x53/0xf0 [btrfs]
    btrfs_balance+0xc91/0x1840 [btrfs]
    btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
    btrfs_ioctl+0x8af/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    create_reloc_root+0x9f/0x460 [btrfs]
    btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
    create_pending_snapshot+0xa9b/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
    create_pending_snapshot+0x209/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

	NULL: reloc_root is NULL	PTR: reloc_root is not NULL
	0: DEAD_RELOC_ROOT bit not set	DEAD: DEAD_RELOC_ROOT bit set

	(NULL, 0)    Initial state		 __
	  |					 /\ Section A
         btrfs_init_reloc_root()			 \/
	  |				 	 __
	(PTR, 0)     reloc_root initialized      /\
           |					 |
	btrfs_update_reloc_root()		 |  Section B
           |					 |
	(PTR, DEAD)  reloc_root has been merged  \/
           |					 __
	=== btrfs_commit_transaction() ====================
	  |					 /\
	clean_dirty_subvols()			 |
	  |					 |  Section C
	(NULL, DEAD) reloc_root cleanup starts   \/
           |					 __
	btrfs_drop_snapshot()			 /\
	  |					 |  Section D
	(NULL, 0)    Back to initial state	 \/

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.

---
  fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----
  1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +2 -0
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct btrfs_trans_handle *trans,
  	return 1;
  }
 
+/*
+ * Check if this subvolume tree has valid reloc(*) tree.

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 10 lines
fs/btrfs/relocation.c +10 -0
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.
+ *    But should_ignore_root() below is a special case.
+ */
+static bool have_reloc_root(struct btrfs_root *root)
+{
+	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+		return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered. Thanks,

Josef

#4 lore raw
Quoted 159 lines · Josef Bacik
Quoted 158 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

    should_ignore_root+0x54/0xb0 [btrfs]
    build_backref_tree+0x11af/0x2280 [btrfs]
    relocate_tree_blocks+0x391/0xb80 [btrfs]
    relocate_block_group+0x3e5/0xa00 [btrfs]
    btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
    btrfs_relocate_chunk+0x53/0xf0 [btrfs]
    btrfs_balance+0xc91/0x1840 [btrfs]
    btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
    btrfs_ioctl+0x8af/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    create_reloc_root+0x9f/0x460 [btrfs]
    btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
    create_pending_snapshot+0xa9b/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
    create_pending_snapshot+0x209/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

    NULL: reloc_root is NULL    PTR: reloc_root is not NULL 0: DEAD_RELOC_ROOT bit not set    DEAD: DEAD_RELOC_ROOT bit set

    (NULL, 0)    Initial state         __
      |                     /\ Section A
         btrfs_init_reloc_root()             \/
      |                      __
    (PTR, 0)     reloc_root initialized      /\

           |                     |
    btrfs_update_reloc_root()         |  Section B
           |                     |

    (PTR, DEAD)  reloc_root has been merged  \/ |                     __
    === btrfs_commit_transaction() ==================== |                     /\
    clean_dirty_subvols()             |
      |                     |  Section C (NULL, DEAD) reloc_root cleanup starts   \/ |                     __ btrfs_drop_snapshot()             /\
      |                     |  Section D (NULL, 0)    Back to initial state     \/

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion

after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
   This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.
---
  fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----

  1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +0 -0
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct
 btrfs_trans_handle *trans,
       return 1;
   }

  +/*
+ * Check if this subvolume tree has valid reloc(*) tree.
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.

Quoted 8 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 6 lines

+ *    But should_ignore_root() below is a special case.
+ */

fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

test_bit()

Furthermore from atomic_t.txt:

The barriers:

smp_mb__{before,after}_atomic()

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

Quoted 3 lines

Thanks,

Josef

#5 lore raw
Quoted 188 lines · Nikolay Borisov
Quoted 159 lines · Josef Bacik
Quoted 158 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

    should_ignore_root+0x54/0xb0 [btrfs]
    build_backref_tree+0x11af/0x2280 [btrfs]
    relocate_tree_blocks+0x391/0xb80 [btrfs]
    relocate_block_group+0x3e5/0xa00 [btrfs]
    btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
    btrfs_relocate_chunk+0x53/0xf0 [btrfs]
    btrfs_balance+0xc91/0x1840 [btrfs]
    btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
    btrfs_ioctl+0x8af/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    create_reloc_root+0x9f/0x460 [btrfs]
    btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
    create_pending_snapshot+0xa9b/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

    btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
    create_pending_snapshot+0x209/0x15f0 [btrfs]
    create_pending_snapshots+0x111/0x140 [btrfs]
    btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
    btrfs_mksubvol+0x915/0x960 [btrfs]
    btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
    btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
    btrfs_ioctl+0x241b/0x3e60 [btrfs]
    do_vfs_ioctl+0x831/0xb10
    ksys_ioctl+0x67/0x90
    __x64_sys_ioctl+0x43/0x50
    do_syscall_64+0x79/0xe0
    entry_SYSCALL_64_after_hwframe+0x49/0xbe

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

    NULL: reloc_root is NULL    PTR: reloc_root is not NULL 0: DEAD_RELOC_ROOT bit not set    DEAD: DEAD_RELOC_ROOT bit set

    (NULL, 0)    Initial state         __
      |                     /\ Section A
         btrfs_init_reloc_root()             \/
      |                      __
    (PTR, 0)     reloc_root initialized      /\

           |                     |
    btrfs_update_reloc_root()         |  Section B
           |                     |

    (PTR, DEAD)  reloc_root has been merged  \/ |                     __
    === btrfs_commit_transaction() ==================== |                     /\
    clean_dirty_subvols()             |
      |                     |  Section C (NULL, DEAD) reloc_root cleanup starts   \/ |                     __ btrfs_drop_snapshot()             /\
      |                     |  Section D (NULL, 0)    Back to initial state     \/

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion

after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
   This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.
---
  fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----

  1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +0 -0
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct
 btrfs_trans_handle *trans,
       return 1;
   }

  +/*
+ * Check if this subvolume tree has valid reloc(*) tree.
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.

Quoted 8 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 6 lines

+ *    But should_ignore_root() below is a special case.
+ */

fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

test_bit()

Furthermore from atomic_t.txt:

The barriers:

Quoted 7 lines

smp_mb__{before,after}_atomic()

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

#6 lore raw
Quoted 28 lines · David Sterba
Quoted 28 lines
Quoted 6 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 4 lines
fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

test_bit()

Furthermore from atomic_t.txt:

The barriers:

smp_mb__{before,after}_atomic()

Quoted 8 lines
Quoted 3 lines

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

#7 lore raw
Quoted 38 lines · David Sterba
Quoted 28 lines · David Sterba
Quoted 28 lines
Quoted 6 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 4 lines
fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

test_bit()

Furthermore from atomic_t.txt:

The barriers:

smp_mb__{before,after}_atomic()

Quoted 8 lines
Quoted 3 lines

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

Quoted 8 lines

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

I used to believe the same fairy tail, that mb() works like a flush(), but we're not living in a fairy tail.

What mb really does is keep certain ordering from happening. And ordering means, we have at least *2* different memory accesses.

It's not to ensure every reader get the same result, as there is no way to do that. Read can happen whenever they want.

So before we talk about mb, we first need to know which 2 memory accesses we're talking about.
If there is even no 2 memory access, then there is no need for mb().

E.g. for the mb implied by spinlock(), it's not to ensure the spinlock counter reader, but to ensure the memory ordering between the spinlock counter itself and the memory it's protecting.

So for memory barrier around test_bit(), as long as the compiler is not doing reordering, we don't need extra mb.

And if the compiler is really doing re-ordering for the have_reloc_root(), then the compiler is doing something wrong, as that would makes the test_bit() meaningless.

Thanks,
Qu

#8 lore raw
Quoted 9 lines · Qu Wenruo
Quoted 9 lines
Quoted 4 lines

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Quoted 6 lines
Quoted 4 lines

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

I used to believe the same fairy tail, that mb() works like a flush(), but we're not living in a fairy tail.

This sounds strange, by flush I was refering to internal CPU mechanism that makes all temporary changes visible to other cpus, so you're saying that this does not work as everybody expects?

Quoted 2 lines

What mb really does is keep certain ordering from happening. And ordering means, we have at least *2* different memory accesses.

Sorry but I think you're missing some pieces here. There are 2 memory
accesses: set_bit/clear_bit (writer) and test_bit (reader).

The same could be achieved by a plain variable, that it's a bit brings more confusion about what barrier should be really used.

The pattern we want to use here is pretty standard. Read barrier before read and write barrier that separates the data change from the indicator of the change. If you line up the barriers, there's a clear line between the data changes and the indicator value.

reloc_root = NULL
smp_wmb smp_rmb()

                                  test_bit()
                                  ... here

set_bit(DEAD)
... or here, it'll be always reloc_root == NULL, but it still could be before or after set_bit

You should also distinguish between mb() and smp_mb() (and the rmb/wmb). mb is a unconditional barrier, used to synchronize access to hardware io ports, suitable in drivers.

We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

Quoted 2 lines

It's not to ensure every reader get the same result, as there is no way to do that. Read can happen whenever they want.

That is true about the 'whenever', but what we need to guarantee here is that when the read happens the following condition will have view of the changes implied by the pairing barrier.

Quoted 10 lines

So before we talk about mb, we first need to know which 2 memory accesses we're talking about.
If there is even no 2 memory access, then there is no need for mb().

E.g. for the mb implied by spinlock(), it's not to ensure the spinlock counter reader, but to ensure the memory ordering between the spinlock counter itself and the memory it's protecting.

So for memory barrier around test_bit(), as long as the compiler is not doing reordering, we don't need extra mb.

This is not about compiler.

Quoted 3 lines

And if the compiler is really doing re-ordering for the have_reloc_root(), then the compiler is doing something wrong, as that would makes the test_bit() meaningless.

#9 lore raw
Quoted 14 lines · David Sterba
Quoted 13 lines · Qu Wenruo
Quoted 13 lines
Quoted 4 lines

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

Quoted 6 lines
Quoted 2 lines

I used to believe the same fairy tail, that mb() works like a flush(), but we're not living in a fairy tail.

This sounds strange, by flush I was refering to internal CPU mechanism that makes all temporary changes visible to other cpus, so you're saying that this does not work as everybody expects?

Because no matter whether mb ensures that or not, the result is the same.

What would happen if the reader get schedule just before the mb() command? Reader can still get older value.
That makes no difference if we had mb() or not.

Quoted 7 lines
Quoted 3 lines

What mb really does is keep certain ordering from happening. And ordering means, we have at least *2* different memory accesses.

Sorry but I think you're missing some pieces here. There are 2 memory
accesses: set_bit/clear_bit (writer) and test_bit (reader).

Quoted 7 lines

The same could be achieved by a plain variable, that it's a bit brings more confusion about what barrier should be really used.

The pattern we want to use here is pretty standard. Read barrier before read and write barrier that separates the data change from the indicator of the change. If you line up the barriers, there's a clear line between the data changes and the indicator value.

Again, test_bit() can happen whenever they like, and smp_rmb() before test_bit() makes no sense.

test_bit() can happen before reloc_root = NULL assign. after reloc_root = NULL assign but before set_bit(), or after set_bit().

That smp_wmb() makes sure set_bit() won't happen before reloc_root, than that's enough.
BTW, smp_mb__before_atomic() should be full mb, not just wmb or rmb.

Quoted 10 lines

reloc_root = NULL
smp_wmb smp_rmb()

                                  test_bit()
                                  ... here

set_bit(DEAD)
... or here, it'll be always reloc_root == NULL, but it still could be before or after set_bit

Quoted 8 lines

You should also distinguish between mb() and smp_mb() (and the rmb/wmb). mb is a unconditional barrier, used to synchronize access to hardware io ports, suitable in drivers.

We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

Yes, but schedule can put that smp_rmb(); test_bit() line where ever they want. So smp_rmb(); test_bit() can still get all the 3 difference timing. It's that smp_mb__before_atomic() killing the 4th case, not the smp_rmb().

Quoted 7 lines
Quoted 3 lines

It's not to ensure every reader get the same result, as there is no way to do that. Read can happen whenever they want.

That is true about the 'whenever', but what we need to guarantee here is that when the read happens the following condition will have view of the changes implied by the pairing barrier.

Still, if reader still gets the temporary value, it's the same as random schedule timing.
What we need to ensure is the order, which is solely ensured by that smb_mb__before_atomic().

Thanks,
Qu

Quoted 17 lines
Quoted 11 lines

So before we talk about mb, we first need to know which 2 memory accesses we're talking about.
If there is even no 2 memory access, then there is no need for mb().

E.g. for the mb implied by spinlock(), it's not to ensure the spinlock counter reader, but to ensure the memory ordering between the spinlock counter itself and the memory it's protecting.

So for memory barrier around test_bit(), as long as the compiler is not doing reordering, we don't need extra mb.

This is not about compiler.

Quoted 3 lines

And if the compiler is really doing re-ordering for the have_reloc_root(), then the compiler is doing something wrong, as that would makes the test_bit() meaningless.

#10 lore raw
Quoted 48 lines · Qu Wenruo
Quoted 14 lines · David Sterba
Quoted 13 lines · Qu Wenruo
Quoted 13 lines
Quoted 4 lines

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

Quoted 6 lines
Quoted 2 lines

I used to believe the same fairy tail, that mb() works like a flush(), but we're not living in a fairy tail.

This sounds strange, by flush I was refering to internal CPU mechanism that makes all temporary changes visible to other cpus, so you're saying that this does not work as everybody expects?

Because no matter whether mb ensures that or not, the result is the same.

What would happen if the reader get schedule just before the mb() command? Reader can still get older value.
That makes no difference if we had mb() or not.

Quoted 7 lines
Quoted 3 lines

What mb really does is keep certain ordering from happening. And ordering means, we have at least *2* different memory accesses.

Sorry but I think you're missing some pieces here. There are 2 memory
accesses: set_bit/clear_bit (writer) and test_bit (reader).

Quoted 7 lines

The same could be achieved by a plain variable, that it's a bit brings more confusion about what barrier should be really used.

The pattern we want to use here is pretty standard. Read barrier before read and write barrier that separates the data change from the indicator of the change. If you line up the barriers, there's a clear line between the data changes and the indicator value.

Again, test_bit() can happen whenever they like, and smp_rmb() before test_bit() makes no sense.

Quoted 25 lines

test_bit() can happen before reloc_root = NULL assign. after reloc_root = NULL assign but before set_bit(), or after set_bit().

That smp_wmb() makes sure set_bit() won't happen before reloc_root, than that's enough.
BTW, smp_mb__before_atomic() should be full mb, not just wmb or rmb.

Quoted 18 lines

reloc_root = NULL
smp_wmb smp_rmb()

                                  test_bit()
                                  ... here

set_bit(DEAD)
... or here, it'll be always reloc_root == NULL, but it still could be before or after set_bit

You should also distinguish between mb() and smp_mb() (and the rmb/wmb). mb is a unconditional barrier, used to synchronize access to hardware io ports, suitable in drivers.

We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

I guess the main difference between us is the effect of "per-cpu viewable temporary value".

It looks like your point is, without rmb() we can't see consistent values the writer sees.

But my point is, even we can only see a temporary value, the __before_atomic() mb at the writer side, ensures only 3 possible temporary values combination can be seen.
(PTR, DEAD), (NULL, DEAD), (NULL, 0).

The killed (PTR, 0) combination is killed by that writer side mb. Thus no need for the reader side mb before test_bit().

That's why I insist on the "test_bit() can happen whenever they like" point, as that has the same effect as schedule.

Thanks,
Qu

Quoted 39 lines

Yes, but schedule can put that smp_rmb(); test_bit() line where ever they want. So smp_rmb(); test_bit() can still get all the 3 difference timing. It's that smp_mb__before_atomic() killing the 4th case, not the smp_rmb().

Quoted 7 lines
Quoted 3 lines

It's not to ensure every reader get the same result, as there is no way to do that. Read can happen whenever they want.

That is true about the 'whenever', but what we need to guarantee here is that when the read happens the following condition will have view of the changes implied by the pairing barrier.

Still, if reader still gets the temporary value, it's the same as random schedule timing.
What we need to ensure is the order, which is solely ensured by that smb_mb__before_atomic().

Thanks,
Qu

Quoted 17 lines
Quoted 11 lines

So before we talk about mb, we first need to know which 2 memory accesses we're talking about.
If there is even no 2 memory access, then there is no need for mb().

E.g. for the mb implied by spinlock(), it's not to ensure the spinlock counter reader, but to ensure the memory ordering between the spinlock counter itself and the memory it's protecting.

So for memory barrier around test_bit(), as long as the compiler is not doing reordering, we don't need extra mb.

This is not about compiler.

Quoted 3 lines

And if the compiler is really doing re-ordering for the have_reloc_root(), then the compiler is doing something wrong, as that would makes the test_bit() meaningless.

#11 lore raw
Quoted 88 lines · Qu Wenruo
Quoted 48 lines · Qu Wenruo
Quoted 14 lines · David Sterba
Quoted 13 lines · Qu Wenruo
Quoted 13 lines
Quoted 4 lines

The way I read it is more like smp_rmb/smp_wmb, but for bits in this case, so the smp_mb__before/after_atomic was only a syntactic sugar to match that it's atomic bitops. I realize this could have caused some confusion, however I still think that some sort of barrier is needed.

There's an existing pattern used for serializing set/clear of BTRFS_ROOT_IN_TRANS_SETUP (record_root_in_trans, btrfs_record_root_in_trans).

Once upon a time there were barriers like smp_mb__before_clear_bit but they got unified to just smp_mb__before_atomic for all set/clear operations, so I believe I was not all wrong with using them.

Quoted 6 lines
Quoted 2 lines

I used to believe the same fairy tail, that mb() works like a flush(), but we're not living in a fairy tail.

This sounds strange, by flush I was refering to internal CPU mechanism that makes all temporary changes visible to other cpus, so you're saying that this does not work as everybody expects?

Because no matter whether mb ensures that or not, the result is the same.

What would happen if the reader get schedule just before the mb() command? Reader can still get older value.
That makes no difference if we had mb() or not.

Quoted 7 lines
Quoted 3 lines

What mb really does is keep certain ordering from happening. And ordering means, we have at least *2* different memory accesses.

Sorry but I think you're missing some pieces here. There are 2 memory
accesses: set_bit/clear_bit (writer) and test_bit (reader).

Quoted 7 lines

The same could be achieved by a plain variable, that it's a bit brings more confusion about what barrier should be really used.

The pattern we want to use here is pretty standard. Read barrier before read and write barrier that separates the data change from the indicator of the change. If you line up the barriers, there's a clear line between the data changes and the indicator value.

Again, test_bit() can happen whenever they like, and smp_rmb() before test_bit() makes no sense.

Quoted 25 lines

test_bit() can happen before reloc_root = NULL assign. after reloc_root = NULL assign but before set_bit(), or after set_bit().

That smp_wmb() makes sure set_bit() won't happen before reloc_root, than that's enough.
BTW, smp_mb__before_atomic() should be full mb, not just wmb or rmb.

Quoted 18 lines

reloc_root = NULL
smp_wmb smp_rmb()

                                  test_bit()
                                  ... here

set_bit(DEAD)
... or here, it'll be always reloc_root == NULL, but it still could be before or after set_bit

You should also distinguish between mb() and smp_mb() (and the rmb/wmb). mb is a unconditional barrier, used to synchronize access to hardware io ports, suitable in drivers.

We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

I guess the main difference between us is the effect of "per-cpu viewable temporary value".

It looks like your point is, without rmb() we can't see consistent values the writer sees.

But my point is, even we can only see a temporary value, the __before_atomic() mb at the writer side, ensures only 3 possible temporary values combination can be seen.
(PTR, DEAD), (NULL, DEAD), (NULL, 0).

Quoted 8 lines

The killed (PTR, 0) combination is killed by that writer side mb. Thus no need for the reader side mb before test_bit().

That's why I insist on the "test_bit() can happen whenever they like" point, as that has the same effect as schedule.

Thanks,
Qu

Can we push the fix to upstream? I hope it to be fixed in late rc of v5.5.

Thanks,
Qu

Quoted 40 lines
Quoted 40 lines

Yes, but schedule can put that smp_rmb(); test_bit() line where ever they want. So smp_rmb(); test_bit() can still get all the 3 difference timing. It's that smp_mb__before_atomic() killing the 4th case, not the smp_rmb().

Quoted 7 lines
Quoted 3 lines

It's not to ensure every reader get the same result, as there is no way to do that. Read can happen whenever they want.

That is true about the 'whenever', but what we need to guarantee here is that when the read happens the following condition will have view of the changes implied by the pairing barrier.

Still, if reader still gets the temporary value, it's the same as random schedule timing.
What we need to ensure is the order, which is solely ensured by that smb_mb__before_atomic().

Thanks,
Qu

Quoted 17 lines
Quoted 11 lines

So before we talk about mb, we first need to know which 2 memory accesses we're talking about.
If there is even no 2 memory access, then there is no need for mb().

E.g. for the mb implied by spinlock(), it's not to ensure the spinlock counter reader, but to ensure the memory ordering between the spinlock counter itself and the memory it's protecting.

So for memory barrier around test_bit(), as long as the compiler is not doing reordering, we don't need extra mb.

This is not about compiler.

Quoted 3 lines

And if the compiler is really doing re-ordering for the have_reloc_root(), then the compiler is doing something wrong, as that would makes the test_bit() meaningless.

#12 lore raw
Quoted 20 lines · Qu Wenruo
Quoted 19 lines · Qu Wenruo
Quoted 6 lines · Qu Wenruo
Quoted 5 lines · David Sterba

On Thu, Jan 09, 2020 at 01:54:34PM +0800, Qu Wenruo wrote:
We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

I guess the main difference between us is the effect of "per-cpu viewable temporary value".

It looks like your point is, without rmb() we can't see consistent values the writer sees.

But my point is, even we can only see a temporary value, the __before_atomic() mb at the writer side, ensures only 3 possible temporary values combination can be seen.
(PTR, DEAD), (NULL, DEAD), (NULL, 0).

Quoted 7 lines
Quoted 5 lines

The killed (PTR, 0) combination is killed by that writer side mb. Thus no need for the reader side mb before test_bit().

That's why I insist on the "test_bit() can happen whenever they like" point, as that has the same effect as schedule.

Can we push the fix to upstream? I hope it to be fixed in late rc of v5.5.

Yes the plan is to push it to 5.5-rc so we can get the stable backports.

About the barriers, we seem to have a conclusion to use smp_rmb/smp_wmb and not the smp_mb__before/after_atomic. Zygo also tested the patch and reported it's ok so I don't want to hold it back.

Understanding the memory barriers takes time to digest (which basically means to develop a cpu simulator in ones head with speculative writes and execution and then keep sanity when reasoning about them).

#13 lore raw
Quoted 31 lines · David Sterba
Quoted 20 lines · Qu Wenruo
Quoted 19 lines · Qu Wenruo
Quoted 6 lines · Qu Wenruo
Quoted 5 lines · David Sterba

On Thu, Jan 09, 2020 at 01:54:34PM +0800, Qu Wenruo wrote:
We use smp_mb() because this serializes memory among multipe CPUs, when one changes memory but stores it to some temporary structures, while other CPUs don't see the effects. I'm sure you've read about that in the memory barrier docs.

I guess the main difference between us is the effect of "per-cpu viewable temporary value".

It looks like your point is, without rmb() we can't see consistent values the writer sees.

But my point is, even we can only see a temporary value, the __before_atomic() mb at the writer side, ensures only 3 possible temporary values combination can be seen.
(PTR, DEAD), (NULL, DEAD), (NULL, 0).

Quoted 7 lines
Quoted 5 lines

The killed (PTR, 0) combination is killed by that writer side mb. Thus no need for the reader side mb before test_bit().

That's why I insist on the "test_bit() can happen whenever they like" point, as that has the same effect as schedule.

Can we push the fix to upstream? I hope it to be fixed in late rc of v5.5.

Yes the plan is to push it to 5.5-rc so we can get the stable backports.

Quoted 7 lines

About the barriers, we seem to have a conclusion to use smp_rmb/smp_wmb and not the smp_mb__before/after_atomic. Zygo also tested the patch and reported it's ok so I don't want to hold it back.

Understanding the memory barriers takes time to digest (which basically means to develop a cpu simulator in ones head with speculative writes and execution and then keep sanity when reasoning about them).

Or simply using the memory model tool and just write a "simple" litmus test to see what's possible and what not in the given situation. (And no, I don't think it's that trivial to do that either :) )

Quoted 1 line
#14 lore raw
In reply to Nikolay Borisov
Quoted 188 lines · Nikolay Borisov
Quoted 159 lines · Josef Bacik
Quoted 158 lines · Qu Wenruo

[BUG]
There are several different KASAN reports for balance + snapshot workloads.
Involved call paths include:

     should_ignore_root+0x54/0xb0 [btrfs]
     build_backref_tree+0x11af/0x2280 [btrfs]
     relocate_tree_blocks+0x391/0xb80 [btrfs]
     relocate_block_group+0x3e5/0xa00 [btrfs]
     btrfs_relocate_block_group+0x240/0x4d0 [btrfs]
     btrfs_relocate_chunk+0x53/0xf0 [btrfs]
     btrfs_balance+0xc91/0x1840 [btrfs]
     btrfs_ioctl_balance+0x416/0x4e0 [btrfs]
     btrfs_ioctl+0x8af/0x3e60 [btrfs]
     do_vfs_ioctl+0x831/0xb10
     ksys_ioctl+0x67/0x90
     __x64_sys_ioctl+0x43/0x50
     do_syscall_64+0x79/0xe0
     entry_SYSCALL_64_after_hwframe+0x49/0xbe

     create_reloc_root+0x9f/0x460 [btrfs]
     btrfs_reloc_post_snapshot+0xff/0x6c0 [btrfs]
     create_pending_snapshot+0xa9b/0x15f0 [btrfs]
     create_pending_snapshots+0x111/0x140 [btrfs]
     btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
     btrfs_mksubvol+0x915/0x960 [btrfs]
     btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
     btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
     btrfs_ioctl+0x241b/0x3e60 [btrfs]
     do_vfs_ioctl+0x831/0xb10
     ksys_ioctl+0x67/0x90
     __x64_sys_ioctl+0x43/0x50
     do_syscall_64+0x79/0xe0
     entry_SYSCALL_64_after_hwframe+0x49/0xbe

     btrfs_reloc_pre_snapshot+0x85/0xc0 [btrfs]
     create_pending_snapshot+0x209/0x15f0 [btrfs]
     create_pending_snapshots+0x111/0x140 [btrfs]
     btrfs_commit_transaction+0x7a6/0x1360 [btrfs]
     btrfs_mksubvol+0x915/0x960 [btrfs]
     btrfs_ioctl_snap_create_transid+0x1d5/0x1e0 [btrfs]
     btrfs_ioctl_snap_create_v2+0x1d3/0x270 [btrfs]
     btrfs_ioctl+0x241b/0x3e60 [btrfs]
     do_vfs_ioctl+0x831/0xb10
     ksys_ioctl+0x67/0x90
     __x64_sys_ioctl+0x43/0x50
     do_syscall_64+0x79/0xe0
     entry_SYSCALL_64_after_hwframe+0x49/0xbe

[CAUSE]
All these call sites are only relying on root->reloc_root, which can undergo btrfs_drop_snapshot(), and since we don't have real refcount based protection to reloc roots, we can reach already dropped reloc root, triggering KASAN.

[FIX]
To avoid such access to unstable root->reloc_root, we should check BTRFS_ROOT_DEAD_RELOC_TREE bit first.

This patch introduces a new wrapper, have_reloc_root(), to do the proper check for most callers who don't distinguish merged reloc tree and no reloc tree.

The only exception is should_ignore_root(), as merged reloc tree can be ignored, while no reloc tree shouldn't.

[CRITICAL SECTION ANALYSE]
Although test_bit()/set_bit()/clear_bit() doesn't imply a barrier, the DEAD_RELOC_TREE bit has extra help from transaction as a higher level barrier, the lifespan of root::reloc_root and DEAD_RELOC_TREE bit are:

    NULL: reloc_root is NULL    PTR: reloc_root is not NULL 0: DEAD_RELOC_ROOT bit not set    DEAD: DEAD_RELOC_ROOT bit set

    (NULL, 0)    Initial state         __
      |                     /\ Section A
         btrfs_init_reloc_root()             \/
      |                      __
    (PTR, 0)     reloc_root initialized      /\

            |                     |
     btrfs_update_reloc_root()         |  Section B
            |                     |

    (PTR, DEAD)  reloc_root has been merged  \/ |                     __
    === btrfs_commit_transaction() ==================== |                     /\
    clean_dirty_subvols()             |
      |                     |  Section C (NULL, DEAD) reloc_root cleanup starts   \/ |                     __ btrfs_drop_snapshot()             /\
      |                     |  Section D (NULL, 0)    Back to initial state     \/

Very have_reloc_root() or test_bit(DEAD_RELOC_ROOT) caller has hold a transaction handler, so none of such caller can cross transaction boundary.

In Section A, every caller just found no DEAD bit, and grab reloc_root.

In the cross section A-B, caller may get no DEAD bit, but since reloc_root is still completely valid thus accessing reloc_root is completely safe.

No test_bit() caller can cross the boundary of Section B and Section C.

In Section C, every caller found the DEAD bit, so no one will access reloc_root.

In the cross section C-D, either caller gets the DEAD bit set, avoiding access reloc_root no matter if it's safe or not.
Or caller get the DEAD bit cleared, then access reloc_root, which is already NULL, nothing will be wrong.

Here we need extra memory barrier in cross section C-D, to ensure proper memory order between reloc_root and clear_bit().

In Section D, since no DEAD bit and no reloc_root, it's back to initial state.

With this lifespan, it should be clear only one memory barrier is needed, between setting reloc_root to NULL and clearing DEAD_RELOC_ROOT bit.

Fixes d2311e698578 ("btrfs: relocation: Delay reloc tree deletion

after merge_reloc_roots")

---
Changelog:
v2:
- Add the [CRITICAL SECTION ANALYSE] part
   This gets me into the rabbit hole of memory ordering, but thanks for the help from David (initially mentioning the mb hell) and Nikolay (for the proper doc), finally I could explain clearly why only one mb is needed.
- Add comment for the only needed memory barrier.

---
   fs/btrfs/relocation.c | 32 ++++++++++++++++++++++++++++----
   1 file changed, 28 insertions(+), 4 deletions(-)
fs/btrfs/relocation.c +3 -0
index d897a8e5e430..17a2484f76a5 100644
@@ -517,6 +517,22 @@ static int update_backref_cache(struct
 btrfs_trans_handle *trans,
       return 1;
   }
   +/*
+ * Check if this subvolume tree has valid reloc(*) tree.
+ *
+ * *: Reloc tree after swap is considered dead, thus not considered

as valid.
+ *    This is enough for most callers, as they don't distinguish dead reloc
+ *    root from no reloc root.

Quoted 8 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 6 lines

+ *    But should_ignore_root() below is a special case.
+ */

fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

   test_bit()

Furthermore from atomic_t.txt:

The barriers:

Quoted 7 lines
   smp_mb__{before,after}_atomic()

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

Right but the document says it's unordered. The problem we're trying to address here is making sure _either_ we see BTRFS_ROOT_DEAD_RELOC_TREE or we see !root->reloc_root. Which means we don't want the test_bit being re-ordered WRT the clear_bit on the other side. So the other side does

reloc_root = NULL;
smp_mb__before_atomic();
clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE);

now say on the other side we get re-ordered and we see reloc_root != NULL and we also see !test_bit(BTRFS_ROOT_DEAD_RELOC_TREE), and now we're screwed.

The smp_mb__after_atomic() guarantees that the re-ordering doesn't happen, correct?

I realize that this is mostly a moot point on real architectures, but I'm looking at things like ARM where test_bit() uses the generic asm helper, which could definitely be re-ordered as it's nothing special. Thanks,

Josef

#15 lore raw
Quoted 1 line · Josef Bacik

On 1/8/20 10:03 AM, Nikolay Borisov wrote:

[...]

Quoted 39 lines
Quoted 25 lines
Quoted 7 lines

fs/btrfs/relocation.c static int update_backref_cache(struct btrfs_trans_handle *trans, · line 531

Quoted 5 lines

+ */

fs/btrfs/relocation.c +4 -0
+static bool have_reloc_root(struct btrfs_root *root)
+{
+    if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
+        return false;

You still need a smp_mb__after_atomic() here, test_bit is unordered.

Nope, that won't do anything, since smp_mb__(After|before)_atomic only orders RMW operations and test_bit is not an RMW operation. From atomic_bitops.txt:

Non-RMW ops:

   test_bit()

Furthermore from atomic_t.txt:

The barriers:

Quoted 7 lines

   smp_mb__{before,after}_atomic()

only apply to the RMW atomic ops and can be used to augment/upgrade the

ordering inherent to the op.

Right but the document says it's unordered.  The problem we're trying to address here is making sure _either_ we see BTRFS_ROOT_DEAD_RELOC_TREE or we see !root->reloc_root.  Which means we don't want the test_bit being re-ordered WRT the clear_bit on the other side.  So the other side does

Quoted 3 lines

reloc_root = NULL;
smp_mb__before_atomic();
clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE);

Yes, that's correct.

Quoted 4 lines

now say on the other side we get re-ordered and we see reloc_root != NULL and we also see !test_bit(BTRFS_ROOT_DEAD_RELOC_TREE), and now we're screwed.

That's not possible. With above mb, there are only several possible results on the reader side:
A: Reloc_root == PTR, and DEAD_RELOC_TREE : Before NULL assignment
B: Reloc_root == NULL, and DEAD_RELOC_TREE: after NULL assignment
C: Reloc_root == NULL, no DEAD_RELOC_TREE: after clear_bit().

That's what mb() is doing, killing the unwanted case:
D: Reloc_root == PTR, no DEAD_RELOC_TREE.

On the reader side, even with the mb, the test_bit() can happen whatever they want, mb makes no sense for *single* memory access.

Quoted 3 lines

The smp_mb__after_atomic() guarantees that the re-ordering doesn't happen, correct?

That smp_mb() has no effect, as it's not defining any extra order, since there is no extra memory access to start with.

And definitely has nothing to do with reader side, as reader can really happen whenever they like.

From what I learnt recently, mb is only needed between at least *two* memory access where the order is really important (to say, kill certain re-order possibility).

If there are no two critical accesses at both side, then a mb makes no sense.

Hopes this would help.

Thanks,
Qu

Quoted 8 lines

I realize that this is mostly a moot point on real architectures, but I'm looking at things like ARM where test_bit() uses the generic asm helper, which could definitely be re-ordered as it's nothing special. Thanks,

Josef