Btrfs: fix full backref problem when inserting shared block reference

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

I chose the 1st way to fix it.

and down, no problems so far, and the "wikipedia" test-subvol stresstest that caused trouble to one of your patches is also ok. I'll do some more testing on other machines and will report problems eventually.

Quoted 3 lines · David Sterba

and down, no problems so far, and the "wikipedia" test-subvol stresstest that caused trouble to one of your patches is also ok. I'll do some more testing on other machines and will report problems eventually.

So it won't be so easy :)

The test generated 15+ G of data, ~500 snapshots, then umount and fsck:

lots of

ref mismatch on [9655283712 4096] extent item 1, found 0
Incorrect local backref count on 9655283712 root 5 owner 589776 offset 110592 found 0 wanted 1 back 0x86badf0 backpointer mismatch on [9655283712 4096]
owner ref check failed [9655283712 4096]

and then

checking fs roots
root 2854 inode 233882 errors 2500
root 2880 inode 271639 errors 2200

and it's not finished yet, other types of error may pop up.

Quoted 3 lines · David Sterba

and down, no problems so far, and the "wikipedia" test-subvol stresstest that caused trouble to one of your patches is also ok. I'll do some more testing on other machines and will report problems eventually.

So it won't be so easy :)

The test generated 15+ G of data, ~500 snapshots, then umount and fsck:

lots of

ref mismatch on [9655283712 4096] extent item 1, found 0
Incorrect local backref count on 9655283712 root 5 owner 589776 offset 110592 found 0 wanted 1 back 0x86badf0 backpointer mismatch on [9655283712 4096]
owner ref check failed [9655283712 4096]

and then

checking fs roots
root 2854 inode 233882 errors 2500
root 2880 inode 271639 errors 2200

and it's not finished yet, other types of error may pop up.

Quoted 3 lines · David Sterba

and down, no problems so far, and the "wikipedia" test-subvol stresstest that caused trouble to one of your patches is also ok. I'll do some more testing on other machines and will report problems eventually.

So it won't be so easy :)

The test generated 15+ G of data, ~500 snapshots, then umount and fsck:

lots of

ref mismatch on [9655283712 4096] extent item 1, found 0
Incorrect local backref count on 9655283712 root 5 owner 589776 offset 110592 found 0 wanted 1 back 0x86badf0 backpointer mismatch on [9655283712 4096]
owner ref check failed [9655283712 4096]

From 77e9bcaae464354c0b0176631ba51374e3d31cfc Mon Sep 17 00:00:00 2001

and then

checking fs roots
root 2854 inode 233882 errors 2500
root 2880 inode 271639 errors 2200

and it's not finished yet, other types of error may pop up.

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

The reason is:
Before transaction commit, some operations changed the fs tree and new tree blocks were allocated because of COW. We used the implicit non-shared back reference for those newly allocated tree blocks because they were not shared by two or more trees.

And then we created the first snapshot for the fs tree, according to the back reference rules, we also used implicit back refs for the child tree blocks of the root node of the fs tree, now those child nodes/leaves were shared by two trees.

Then We didn't deal with the delayed references, and continued to change the fs tree(created the second snapshot and inserted the dir item of the new snapshot into the fs tree). According to the rules of the back reference, we added full back refs for those tree blocks whose parents have be shared by two trees. Now some newly allocated tree blocks had two types of the references.

As we know, the delayed reference system handles these delayed references from back to front, and the full delayed reference is inserted after the implicit ones. So when we dealt with the back references of those newly allocated tree blocks, the full references was dealt with at first. And if the first reference is a shared back reference and the tree block that the reference points to is newly allocated, It would be considered as a tree block which is shared by two or more trees when it is allocated and should be a full back reference not a implicit one, the flag of its reference also should be set to FULL_BACKREF. But in fact, it was a non-shared tree block with a implicit reference at beginning, so it was not compulsory to set the flags to FULL_BACKREF. So BUG_ON was triggered.

We have several methods to fix this bug:
1. deal with delayed references after the snapshot is created and before we change the source tree of the snapshot. This is the easiest and safest way.
2. modify the sort method of the delayed reference tree, make the full delayed references be inserted before the implicit ones. It is also very easy, but I don't know if it will introduce some problems or not.

Quoted 48 lines · Miao Xie

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

The reason is:
Before transaction commit, some operations changed the fs tree and new tree blocks were allocated because of COW. We used the implicit non-shared back reference for those newly allocated tree blocks because they were not shared by two or more trees.

And then we created the first snapshot for the fs tree, according to the back reference rules, we also used implicit back refs for the child tree blocks of the root node of the fs tree, now those child nodes/leaves were shared by two trees.

Then We didn't deal with the delayed references, and continued to change the fs tree(created the second snapshot and inserted the dir item of the new snapshot into the fs tree). According to the rules of the back reference, we added full back refs for those tree blocks whose parents have be shared by two trees. Now some newly allocated tree blocks had two types of the references.

As we know, the delayed reference system handles these delayed references from back to front, and the full delayed reference is inserted after the implicit ones. So when we dealt with the back references of those newly allocated tree blocks, the full references was dealt with at first. And if the first reference is a shared back reference and the tree block that the reference points to is newly allocated, It would be considered as a tree block which is shared by two or more trees when it is allocated and should be a full back reference not a implicit one, the flag of its reference also should be set to FULL_BACKREF. But in fact, it was a non-shared tree block with a implicit reference at beginning, so it was not compulsory to set the flags to FULL_BACKREF. So BUG_ON was triggered.

Quoted 6 lines

We have several methods to fix this bug:
1. deal with delayed references after the snapshot is created and before we change the source tree of the snapshot. This is the easiest and safest way.
2. modify the sort method of the delayed reference tree, make the full delayed references be inserted before the implicit ones. It is also very easy, but I don't know if it will introduce some problems or not.

Thanks for tracking this down, FWIW I like option 2 the most, it would be intereseting to see if it does actually introduce new issues. Thanks,

Quoted 56 lines · Josef Bacik

Quoted 54 lines · Miao Xie

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

The reason is:
Before transaction commit, some operations changed the fs tree and new tree blocks were allocated because of COW. We used the implicit non-shared back reference for those newly allocated tree blocks because they were not shared by two or more trees.

And then we created the first snapshot for the fs tree, according to the back reference rules, we also used implicit back refs for the child tree blocks of the root node of the fs tree, now those child nodes/leaves were shared by two trees.

Then We didn't deal with the delayed references, and continued to change the fs tree(created the second snapshot and inserted the dir item of the new snapshot into the fs tree). According to the rules of the back reference, we added full back refs for those tree blocks whose parents have be shared by two trees. Now some newly allocated tree blocks had two types of the references.

As we know, the delayed reference system handles these delayed references from back to front, and the full delayed reference is inserted after the implicit ones. So when we dealt with the back references of those newly allocated tree blocks, the full references was dealt with at first. And if the first reference is a shared back reference and the tree block that the reference points to is newly allocated, It would be considered as a tree block which is shared by two or more trees when it is allocated and should be a full back reference not a implicit one, the flag of its reference also should be set to FULL_BACKREF. But in fact, it was a non-shared tree block with a implicit reference at beginning, so it was not compulsory to set the flags to FULL_BACKREF. So BUG_ON was triggered.

We have several methods to fix this bug:
1. deal with delayed references after the snapshot is created and before we change the source tree of the snapshot. This is the easiest and safest way.
2. modify the sort method of the delayed reference tree, make the full delayed references be inserted before the implicit ones. It is also very easy, but I don't know if it will introduce some problems or not.

Quoted 2 lines

Thanks for tracking this down, FWIW I like option 2 the most, it would be intereseting to see if it does actually introduce new issues. Thanks,

For this release, I like the current patch ;) Great job tracking it down Miao.

Quoted 57 lines · Chris L. Mason

Quoted 56 lines · Josef Bacik

Quoted 54 lines · Miao Xie

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

The reason is:
Before transaction commit, some operations changed the fs tree and new tree blocks were allocated because of COW. We used the implicit non-shared back reference for those newly allocated tree blocks because they were not shared by two or more trees.

And then we created the first snapshot for the fs tree, according to the back reference rules, we also used implicit back refs for the child tree blocks of the root node of the fs tree, now those child nodes/leaves were shared by two trees.

Then We didn't deal with the delayed references, and continued to change the fs tree(created the second snapshot and inserted the dir item of the new snapshot into the fs tree). According to the rules of the back reference, we added full back refs for those tree blocks whose parents have be shared by two trees. Now some newly allocated tree blocks had two types of the references.

As we know, the delayed reference system handles these delayed references from back to front, and the full delayed reference is inserted after the implicit ones. So when we dealt with the back references of those newly allocated tree blocks, the full references was dealt with at first. And if the first reference is a shared back reference and the tree block that the reference points to is newly allocated, It would be considered as a tree block which is shared by two or more trees when it is allocated and should be a full back reference not a implicit one, the flag of its reference also should be set to FULL_BACKREF. But in fact, it was a non-shared tree block with a implicit reference at beginning, so it was not compulsory to set the flags to FULL_BACKREF. So BUG_ON was triggered.

We have several methods to fix this bug:
1. deal with delayed references after the snapshot is created and before we change the source tree of the snapshot. This is the easiest and safest way.
2. modify the sort method of the delayed reference tree, make the full delayed references be inserted before the implicit ones. It is also very easy, but I don't know if it will introduce some problems or not.

Quoted 6 lines

Quoted 2 lines

Thanks for tracking this down, FWIW I like option 2 the most, it would be intereseting to see if it does actually introduce new issues. Thanks,

For this release, I like the current patch ;) Great job tracking it down Miao.

Well sure it's much cleaner, but it appears to not work right?

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

Quoted 18 lines · Miao Xie

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

snapshot creation has a critical section. Once we copy a given root to its snapshot, we're not allowed to change it until the transaction is fully committed.

This means that if you're taking a snapshot of root A and storing the directory item of the snapshot in root A, you can only do it once per transaction with getting into trouble.

Looks like the code doesn't enforce this though. Dave, could you please give this a try:

fs/btrfs/ctree.c +2 -0

index fcc8c21..9e7c621 100644
@@ -1324,6 +1324,8 @@ noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
 	u64 search_start;
 	int ret;
 
+	WARN_ON(root->danger_transid == trans->transid);
+
 	if (trans->transaction != root->fs_info->running_transaction) {
 		printk(KERN_CRIT "trans %llu running %llu\n",
 		       (unsigned long long)trans->transid,

fs/btrfs/ctree.h +13 -0

index 0d195b5..35b5603 100644
@@ -1490,6 +1490,12 @@ struct btrfs_root {
 	u64 objectid;
 	u64 last_trans;
 
+	/*
+	 * the last transaction that took a snapshot of this
+	 * root.  We're only allowed one snapshot per root per transaction
+	 */
+	u64 snapshot_trans;
+
 	/* data allocations are done in sectorsize units */
 	u32 sectorsize;
 

@@ -1550,6 +1556,13 @@ struct btrfs_root {
 
 	int force_cow;
 
+	/*
+	 * this marks the critical section of snapshot creation.  If we
+	 * make any changes to a root after this critical section starts,
+	 * we corrupt the FS.  It is checked by btrfs_cow_block
+	 */
+	u64 danger_transid;
+
 	spinlock_t root_times_lock;
 };
 

fs/btrfs/ioctl.c +16 -1

index 9df50fa..b20d835 100644
@@ -524,13 +524,28 @@ static int create_snapshot(struct btrfs_root *root, struct dentry *dentry,
 		pending_snapshot->inherit = *inherit;
 		*inherit = NULL;	/* take responsibility to free it */
 	}
-
+again:
 	trans = btrfs_start_transaction(root->fs_info->extent_root, 5);
 	if (IS_ERR(trans)) {
 		ret = PTR_ERR(trans);
 		goto fail;
 	}
 
+	/* we're only allowed to snapshot a given root once per transaction */
+	spin_lock(&root->fs_info->trans_lock);
+	if (root->snapshot_trans == trans->transid) {
+		spin_unlock(&root->fs_info->trans_lock);
+		ret = btrfs_commit_transaction(trans, root->fs_info->extent_root);
+		if (ret)
+			goto fail;
+		goto again;
+	}
+
+	root->snapshot_trans = trans->transid;
+
+	spin_unlock(&root->fs_info->trans_lock);
+
+
 	ret = btrfs_snap_reserve_metadata(trans, pending_snapshot);
 	BUG_ON(ret);
 

fs/btrfs/transaction.c +1 -1

index 27c2600..4507421 100644
@@ -1093,6 +1093,7 @@ static noinline int create_pending_snapshot(struct btrfs_trans_handle *trans,
 
 	/* see comments in should_cow_block() */
 	root->force_cow = 1;
+	root->danger_transid = trans->transid;
 	smp_wmb();
 
 	btrfs_set_root_node(new_root_item, tmp);
--

To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 20 lines · Chris Mason

Quoted 18 lines · Miao Xie

If we create several snapshots at the same time, the following BUG_ON() will be triggered.

kernel BUG at fs/btrfs/extent-tree.c:6047!

Steps to reproduce:

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

Quoted 3 lines

snapshot creation has a critical section. Once we copy a given root to its snapshot, we're not allowed to change it until the transaction is fully committed.

I knew this critical section. But I think we can kick it away by forcing the snapshoted tree to do COW.

BTW, I will take a vacation next week, so I can not reply it until the week after next. If it is not urgent, I will continue looking into this problem after I come back.

Quoted 13 lines

Quoted 13 lines

Quoted 12 lines

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

Quoted 3 lines

Quoted 3 lines

snapshot creation has a critical section. Once we copy a given root to its snapshot, we're not allowed to change it until the transaction is fully committed.

Hi Miao,
I was following this thread in the past, but I did not understand it fully, maybe you can explain?

Quoted 13 lines

Quoted 13 lines

Quoted 13 lines

Quoted 12 lines

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

snapshot creation has a critical section. Once we copy a given root to its snapshot, we're not allowed to change it until the transaction is fully committed.

Is the limitation that if we are creating a snap B of root A, and placing the root of B somewhere into the tree of A, then we can do this only once per transaction? Does this limitation still exist or your fix fixes it?

Also, according to your reproducer, each "btrfs sub snap" will start/join a transaction, but then it will call btrfs_commit_transaction() and not btrfs_commit_transaction_async(), so it will wait until the transaction commits. So how it may happen that you create more than one snap in the same transaction with your reproducer?

The reason I am asking, is that I want to try to write code that creates several snaps in one transaction and only then commits. Should this be possible or there is some limitation, like I mentioned above?

Quoted 17 lines · Alex Lyakas

Hi Miao,
I was following this thread in the past, but I did not understand it fully, maybe you can explain?

Quoted 13 lines

Quoted 13 lines

Quoted 13 lines

Quoted 12 lines

 # mkfs.btrfs <partition>
 # mount <partition> <mnt>
 # cd <mnt>
 # for ((i=0;i<2400;i++)); do touch long_name_to_make_tree_more_deep$i; done
 # for ((i=0; i<4; i++))

Quoted 7 lines

do
mkdir $i
for ((j=0; j<200; j++))
do
btrfs sub snap . $i/$j
done &
done

Quoted 8 lines

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

snapshot creation has a critical section. Once we copy a given root to its snapshot, we're not allowed to change it until the transaction is fully committed.

Is the limitation that if we are creating a snap B of root A, and placing the root of B somewhere into the tree of A, then we can do this only once per transaction? Does this limitation still exist or your fix fixes it?

The limitation is the snapshoted subvolume can not be changed until the transaction is committed. That is we can not insert anything(including the root of B and the directory item/index of B) into the tree of A after snap B is created.

This limitation was fixed.

Quoted 6 lines

Also, according to your reproducer, each "btrfs sub snap" will start/join a transaction, but then it will call btrfs_commit_transaction() and not btrfs_commit_transaction_async(), so it will wait until the transaction commits. So how it may happen that you create more than one snap in the same transaction with your reproducer?

run several tasks, and each task create snapshots repeatedly in its own directory.
(If we create snapshots in the same directory, the i_mutex of the directory
will make the process serialized)

Quoted 4 lines

The reason I am asking, is that I want to try to write code that creates several snaps in one transaction and only then commits. Should this be possible or there is some limitation, like I mentioned above?

As far as I know, it is possible, there is no limitation now.

Thanks
Miao