btrfs does not work on usermode linux

According to https://btrfs.wiki.kernel.org/index.php/Debugging_Btrfs_with_GDB
UML did work once.

Now it corrupts data and triggers BUG_ON once you start to use it. I tried both 2.6.38 and 2.6.39-rc2 (x86_64) I need some help to track it down.

doing 'touch seq 1 11; rm 11' kills the kernel:

#run> mount -t btrfs /dev/ubda /mnt/btr/

[    2.220000] device fsid 754599771c9b69eb-66689f77c1542bb9 devid 1 transid 7 /dev/ubda

#status: 0
#run> cd /mnt/btr/
#status: 0
touching files 1 .. 11
#run> touch 1 2 3 4 5 6 7 8 9 10 11
#status: 0
#run> ls

[    2.220000] btrfS: invalid dir item name len: 12594
[    2.220000] btrfS: invalid dir item name len: 0
[    2.220000] btrfS: invalid dir item name len: 0

11
#status: 0
Fasten your belts: removing file 11
#run> rm 11

[    2.220000] btrfs failed to delete reference to 11, inode 267 parent 256
[    2.220000] Kernel panic - not syncing: Kernel mode signal 4
[    2.220000] Call Trace: 
[    2.220000] 6024b918:  [<601b2567>] panic+0xea/0x1dc
[    2.220000] 6024b9c8:  [<601b491e>] _raw_spin_unlock_irqrestore+0x18/0x1c
[    2.220000] 6024b9e8:  [<60017d00>] free_irqs+0x74/0xde
[    2.220000] 6024ba18:  [<60015faa>] relay_signal+0x38/0x79
[    2.220000] 6024ba28:  [<60013c8e>] sigio_handler+0x5a/0x60
[    2.220000] 6024ba48:  [<6001f224>] sig_handler_common+0x84/0x98
[    2.220000] 6024ba68:  [<6001f2d1>] real_alarm_handler+0x3c/0x3e
[    2.220000] 6024baf0:  [<600579f7>] get_page_from_freelist+0x129/0x478
[    2.220000] 6024bb78:  [<6001f36a>] sig_handler+0x30/0x3b
[    2.220000] 6024bb98:  [<6001f59c>] handle_signal+0x6d/0xa3
[    2.220000] 6024bbe8:  [<600203b0>] hard_handler+0x10/0x14
[    2.220000] 6024bca8:  [<600e04c3>] btrfs_unlink+0x77/0xef

==

I've cooked whole root into small archive (3.1MB):
https://slyfox.ath.cx/btrfs/linux-2.6-um-x86_64-fs.tar.gz

You just need to start './run' to enter into UML root fs and there to issue ./kill_btr to get fault above.

Archive contains minimal .config for kernel 2.6.39-rc2, statically linked busybox binary and fresh image of btrfs.
It also has tiny script, which will help you to generate the same rootfs if you are afraid to run suspicious binaries.

  Sergei

2.6.36 works 2.6.37 doesn't. bsecting

  Sergei

Bisected down to:

commit 59daa706fbec745684702741b9f5373142dd9fdc (v2.6.36-rc2-2-g59daa70)

Author: Ma Ling <[email protected]>
Date:   Tue Jun 29 03:24:25 2010 +0800

x86, mem: Optimize memcpy by avoiding memory false dependece

Which means btrfs passes overlapping areas to memcpy. I've added some debug info and found out rough place:
touching files 1 .. 11
#run> touch 1 2 3 4 5 6 7 8 9 10 11

[    2.270000]  memcpy overlap detected: memcpy(dst=0000000070654e8a, src=0000000070654ea9, size=171) [delta=31]
[    2.270000] ------------[ cut here ]------------
[    2.270000] WARNING: at /home/slyfox/linux-2.6/fs/btrfs/memcpy_debug.c:18 btrfs_memcpy+0x52/0x68()
[    2.270000] Call Trace: 
[    2.270000] 7064b748:  [<600eff46>] map_extent_buffer+0x62/0x9e
[    2.270000] 7064b758:  [<60029ad9>] warn_slowpath_common+0x59/0x70
[    2.270000] 7064b798:  [<60029b05>] warn_slowpath_null+0x15/0x17
[    2.270000] 7064b7a8:  [<6011129e>] btrfs_memcpy+0x52/0x68
[    2.270000] 7064b7d8:  [<600efa01>] memcpy_extent_buffer+0x18d/0x1da
[    2.270000] 7064b858:  [<600efae2>] memmove_extent_buffer+0x94/0x208
[    2.270000] 7064b8d8:  [<600bc4b0>] setup_items_for_insert+0x2b8/0x426
[    2.270000] 7064b8e8:  [<600bb25a>] btrfs_leaf_free_space+0x62/0xa6
[    2.270000] 7064b9c8:  [<600c13f3>] btrfs_insert_empty_items+0xa3/0xb5
[    2.270000] 7064ba38:  [<600ce690>] insert_with_overflow+0x33/0xf1
[    2.270000] 7064ba88:  [<600ce7d4>] btrfs_insert_dir_item+0x86/0x268
[    2.270000] 7064bae8:  [<601b498b>] _raw_spin_unlock+0x9/0xb
[    2.270000] 7064bb48:  [<600ddef1>] btrfs_add_link+0x10d/0x170
[    2.270000] 7064bbc8:  [<600ddf7a>] btrfs_add_nondir+0x26/0x52
[    2.270000] 7064bc08:  [<600de73f>] btrfs_create+0xf2/0x1c0
[    2.270000] 7064bc18:  [<6007ccff>] generic_permission+0x57/0x9d
[    2.270000] 7064bc68:  [<6007cf60>] vfs_create+0x6a/0x75

which is in extent_io:copy_pages. I haven't dig further only made sure the following patch below (practically converts copy_pages to move_pages). It certainly does not look the right thing, but I don't understand extent_io contents yet to understand what actually happened.

index 20ddb28..4cab7db 100644
@@ -3893,14 +3893,17 @@ static void copy_pages(struct page *dst_page, struct page *src_page,
        char *src_kaddr;
 
        if (dst_page != src_page)
+       {
                src_kaddr = kmap_atomic(src_page, KM_USER1);
+               memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
+               kunmap_atomic(src_kaddr, KM_USER1);
+       }
        else
+       {
                src_kaddr = dst_kaddr;
-
-       memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
+               memmove(dst_kaddr + dst_off, src_kaddr + src_off, len);
+       }
        kunmap_atomic(dst_kaddr, KM_USER0);
-       if (dst_page != src_page)
-               kunmap_atomic(src_kaddr, KM_USER1);
 }
 
 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,

  Sergei

Changes since v1:

  Sergei

------------[ cut here ]------------
WARNING: at /home/slyfox/linux-2.6/fs/btrfs/extent_io.c:3900 memcpy_extent_buffer+0x1a5/0x219()
Call Trace:
6fa39a58:  [<601b495e>] _raw_spin_unlock_irqrestore+0x18/0x1c
6fa39a68:  [<60029ad9>] warn_slowpath_common+0x59/0x70
6fa39aa8:  [<60029b05>] warn_slowpath_null+0x15/0x17
6fa39ab8:  [<600efc97>] memcpy_extent_buffer+0x1a5/0x219
6fa39b48:  [<600efd9f>] memmove_extent_buffer+0x94/0x208
6fa39bc8:  [<600becbf>] btrfs_del_items+0x214/0x473
6fa39c78:  [<600ce1b0>] btrfs_delete_one_dir_name+0x7c/0xda
6fa39cc8:  [<600dad6b>] __btrfs_unlink_inode+0xad/0x25d
6fa39d08:  [<600d7864>] btrfs_start_transaction+0xe/0x10
6fa39d48:  [<600dc9ff>] btrfs_unlink_inode+0x1b/0x3b
6fa39d78:  [<600e04bc>] btrfs_unlink+0x70/0xef
6fa39dc8:  [<6007f0d0>] vfs_unlink+0x58/0xa3
6fa39df8:  [<60080278>] do_unlinkat+0xd4/0x162
6fa39e48:  [<600517db>] call_rcu_sched+0xe/0x10
6fa39e58:  [<600452a8>] __put_cred+0x58/0x5a
6fa39e78:  [<6007446c>] sys_faccessat+0x154/0x166
6fa39ed8:  [<60080317>] sys_unlink+0x11/0x13
6fa39ee8:  [<60016b80>] handle_syscall+0x58/0x70
6fa39f08:  [<60021377>] userspace+0x2d4/0x381
6fa39fc8:  [<60014507>] fork_handler+0x62/0x69
---[ end trace 70b0ca2ef0266b93 ]---

---
 fs/btrfs/extent_io.c |   11 ++++++++++-
 1 files changed, 10 insertions(+), 1 deletions(-)

index 20ddb28..786a0f7 100644
@@ -3878,31 +3878,40 @@ static void move_pages(struct page *dst_page, struct page *src_page,
 		char *s = src_kaddr + src_off + len;
 
 		while (len--)
 			*--p = *--s;
 
 		kunmap_atomic(src_kaddr, KM_USER1);
 	}
 	kunmap_atomic(dst_kaddr, KM_USER0);
 }
 
+static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
+{
+	unsigned long distance = (src > dst) ? src - dst : dst - src;
+	return distance < len;
+}
+
 static void copy_pages(struct page *dst_page, struct page *src_page,
 		       unsigned long dst_off, unsigned long src_off,
 		       unsigned long len)
 {
 	char *dst_kaddr = kmap_atomic(dst_page, KM_USER0);
 	char *src_kaddr;
 
 	if (dst_page != src_page)
 		src_kaddr = kmap_atomic(src_page, KM_USER1);
 	else
+	{
 		src_kaddr = dst_kaddr;
+		BUG_ON(areas_overlap(src_off, dst_off, len));
+	}
 
 	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
 	kunmap_atomic(dst_kaddr, KM_USER0);
 	if (dst_page != src_page)
 		kunmap_atomic(src_kaddr, KM_USER1);
 }
 
 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 			   unsigned long src_offset, unsigned long len)
 {

@@ -3963,21 +3972,21 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 	if (src_offset + len > dst->len) {
 		printk(KERN_ERR "btrfs memmove bogus src_offset %lu move "
 		       "len %lu len %lu\n", src_offset, len, dst->len);
 		BUG_ON(1);
 	}
 	if (dst_offset + len > dst->len) {
 		printk(KERN_ERR "btrfs memmove bogus dst_offset %lu move "
 		       "len %lu len %lu\n", dst_offset, len, dst->len);
 		BUG_ON(1);
 	}
-	if (dst_offset < src_offset) {
+	if (!areas_overlap(src_offset, dst_offset, len)) {
 		memcpy_extent_buffer(dst, dst_offset, src_offset, len);
 		return;
 	}
 	while (len > 0) {
 		dst_i = (start_offset + dst_end) >> PAGE_CACHE_SHIFT;
 		src_i = (start_offset + src_end) >> PAGE_CACHE_SHIFT;
 
 		dst_off_in_page = (start_offset + dst_end) &
 			((unsigned long)PAGE_CACHE_SIZE - 1);
 		src_off_in_page = (start_offset + src_end) &

1.7.3.4

Very nice catch, one nit

if (dst_page != src_page)
src_kaddr = kmap_atomic(src_page, KM_USER1);
else
+ {
src_kaddr = dst_kaddr;
+ BUG_ON(areas_overlap(src_off, dst_off, len));
+ }

you will want to turn that into

if (dst_page != src_page) {
	src_kaddr = kmap_atomic(src_page, KM_USER1);
} else {
	src_kaddr = dst_kaddr;
	BUG_ON(areas_overlap(src_off, dst_off, len));
}

Also maybe BUG_ON() is a little strong, since the kernel will do this right, it just screws up UML. So maybe just do a WARN_ON() so we notice it. Thanks,

Josef

Changes since v2:
- Code style cleanup
- 2 versions of patch: BUG_ON and WARN_ON variants, _but_ see below why I prefer BUG_ON

Changes since v1:

done

I'm afaid I didn't understand this part. The commit I've found a deviation was linux's implementation of memcpy (UML uses it as kernel does). Why the kernel differs to UML in that respect? Seems I don't know/understand something fundamental here.
So, if data overlaps - it's a moment before data corruption, thus BUG_ON.

Another thought is (if memcpy semantics differ from standard C's function):
does linux's memcpy guarantee copying direction behaviour?
If it does, then it's really a weird memmove and x86/memcpy_64.S is a bit broken.

Attached both patches, I personally like BUG_ON variant. Pick the one you like more :]

Thanks for the feedback!

  Sergei

From aaaf03ebcdee3f65e898016b14bc81c66bfdd31c Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <[email protected]>
Date: Sun, 10 Apr 2011 23:19:53 +0300
Subject: [PATCH 1/2] btrfs: properly handle overlapping areas in memmove_extent_buffer
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Fix data corruption caused by memcpy() usage on overlapping data. I've observed it first when found out usermode linux crash on btrfs.

Сall chain is the following:

------------[ cut here ]------------
WARNING: at /home/slyfox/linux-2.6/fs/btrfs/extent_io.c:3900 memcpy_extent_buffer+0x1a5/0x219()
Call Trace:
6fa39a58:  [<601b495e>] _raw_spin_unlock_irqrestore+0x18/0x1c
6fa39a68:  [<60029ad9>] warn_slowpath_common+0x59/0x70
6fa39aa8:  [<60029b05>] warn_slowpath_null+0x15/0x17
6fa39ab8:  [<600efc97>] memcpy_extent_buffer+0x1a5/0x219
6fa39b48:  [<600efd9f>] memmove_extent_buffer+0x94/0x208
6fa39bc8:  [<600becbf>] btrfs_del_items+0x214/0x473
6fa39c78:  [<600ce1b0>] btrfs_delete_one_dir_name+0x7c/0xda
6fa39cc8:  [<600dad6b>] __btrfs_unlink_inode+0xad/0x25d
6fa39d08:  [<600d7864>] btrfs_start_transaction+0xe/0x10
6fa39d48:  [<600dc9ff>] btrfs_unlink_inode+0x1b/0x3b
6fa39d78:  [<600e04bc>] btrfs_unlink+0x70/0xef
6fa39dc8:  [<6007f0d0>] vfs_unlink+0x58/0xa3
6fa39df8:  [<60080278>] do_unlinkat+0xd4/0x162
6fa39e48:  [<600517db>] call_rcu_sched+0xe/0x10
6fa39e58:  [<600452a8>] __put_cred+0x58/0x5a
6fa39e78:  [<6007446c>] sys_faccessat+0x154/0x166
6fa39ed8:  [<60080317>] sys_unlink+0x11/0x13
6fa39ee8:  [<60016b80>] handle_syscall+0x58/0x70
6fa39f08:  [<60021377>] userspace+0x2d4/0x381
6fa39fc8:  [<60014507>] fork_handler+0x62/0x69
---[ end trace 70b0ca2ef0266b93 ]---

http://www.mail-archive.com/[email protected]/msg09302.html

---
 fs/btrfs/extent_io.c |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

index 20ddb28..10db989 100644
@@ -3885,6 +3885,12 @@ static void move_pages(struct page *dst_page, struct page *src_page,
 	kunmap_atomic(dst_kaddr, KM_USER0);
 }
 
+static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
+{
+	unsigned long distance = (src > dst) ? src - dst : dst - src;
+	return distance < len;
+}
+
 static void copy_pages(struct page *dst_page, struct page *src_page,
 		       unsigned long dst_off, unsigned long src_off,
 		       unsigned long len)

@@ -3892,10 +3898,12 @@ static void copy_pages(struct page *dst_page, struct page *src_page,
 	char *dst_kaddr = kmap_atomic(dst_page, KM_USER0);
 	char *src_kaddr;
 
-	if (dst_page != src_page)
+	if (dst_page != src_page) {
 		src_kaddr = kmap_atomic(src_page, KM_USER1);
-	else
+	} else {
 		src_kaddr = dst_kaddr;
+		BUG_ON(areas_overlap(src_off, dst_off, len));
+	}
 
 	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
 	kunmap_atomic(dst_kaddr, KM_USER0);

@@ -3970,7 +3978,7 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 		       "len %lu len %lu\n", dst_offset, len, dst->len);
 		BUG_ON(1);
 	}
-	if (dst_offset < src_offset) {
+	if (!areas_overlap(src_offset, dst_offset, len)) {
 		memcpy_extent_buffer(dst, dst_offset, src_offset, len);
 		return;
 	}

1.7.3.4

From 51602c049c4583fc7b1ef454f630138f12dba70e Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <[email protected]>
Date: Sun, 10 Apr 2011 23:19:53 +0300
Subject: [PATCH 1/2] btrfs: properly handle overlapping areas in memmove_extent_buffer
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Fix data corruption caused by memcpy() usage on overlapping data. I've observed it first when found out usermode linux crash on btrfs.

Сall chain is the following:

------------[ cut here ]------------
WARNING: at /home/slyfox/linux-2.6/fs/btrfs/extent_io.c:3900 memcpy_extent_buffer+0x1a5/0x219()
Call Trace:
6fa39a58:  [<601b495e>] _raw_spin_unlock_irqrestore+0x18/0x1c
6fa39a68:  [<60029ad9>] warn_slowpath_common+0x59/0x70
6fa39aa8:  [<60029b05>] warn_slowpath_null+0x15/0x17
6fa39ab8:  [<600efc97>] memcpy_extent_buffer+0x1a5/0x219
6fa39b48:  [<600efd9f>] memmove_extent_buffer+0x94/0x208
6fa39bc8:  [<600becbf>] btrfs_del_items+0x214/0x473
6fa39c78:  [<600ce1b0>] btrfs_delete_one_dir_name+0x7c/0xda
6fa39cc8:  [<600dad6b>] __btrfs_unlink_inode+0xad/0x25d
6fa39d08:  [<600d7864>] btrfs_start_transaction+0xe/0x10
6fa39d48:  [<600dc9ff>] btrfs_unlink_inode+0x1b/0x3b
6fa39d78:  [<600e04bc>] btrfs_unlink+0x70/0xef
6fa39dc8:  [<6007f0d0>] vfs_unlink+0x58/0xa3
6fa39df8:  [<60080278>] do_unlinkat+0xd4/0x162
6fa39e48:  [<600517db>] call_rcu_sched+0xe/0x10
6fa39e58:  [<600452a8>] __put_cred+0x58/0x5a
6fa39e78:  [<6007446c>] sys_faccessat+0x154/0x166
6fa39ed8:  [<60080317>] sys_unlink+0x11/0x13
6fa39ee8:  [<60016b80>] handle_syscall+0x58/0x70
6fa39f08:  [<60021377>] userspace+0x2d4/0x381
6fa39fc8:  [<60014507>] fork_handler+0x62/0x69
---[ end trace 70b0ca2ef0266b93 ]---

http://www.mail-archive.com/[email protected]/msg09302.html

---
 fs/btrfs/extent_io.c |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

index 20ddb28..2655aef 100644
@@ -3885,6 +3885,12 @@ static void move_pages(struct page *dst_page, struct page *src_page,
 	kunmap_atomic(dst_kaddr, KM_USER0);
 }
 
+static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
+{
+	unsigned long distance = (src > dst) ? src - dst : dst - src;
+	return distance < len;
+}
+
 static void copy_pages(struct page *dst_page, struct page *src_page,
 		       unsigned long dst_off, unsigned long src_off,
 		       unsigned long len)

@@ -3892,10 +3898,12 @@ static void copy_pages(struct page *dst_page, struct page *src_page,
 	char *dst_kaddr = kmap_atomic(dst_page, KM_USER0);
 	char *src_kaddr;
 
-	if (dst_page != src_page)
+	if (dst_page != src_page) {
 		src_kaddr = kmap_atomic(src_page, KM_USER1);
-	else
+	} else {
 		src_kaddr = dst_kaddr;
+		WARN_ON(areas_overlap(src_off, dst_off, len));
+	}
 
 	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
 	kunmap_atomic(dst_kaddr, KM_USER0);

@@ -3970,7 +3978,7 @@ void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
 		       "len %lu len %lu\n", dst_offset, len, dst->len);
 		BUG_ON(1);
 	}
-	if (dst_offset < src_offset) {
+	if (!areas_overlap(src_offset, dst_offset, len)) {
 		memcpy_extent_buffer(dst, dst_offset, src_offset, len);
 		return;
 	}

1.7.3.4

I think the problem here is that memcpy beahviour changed in recent glibc in this regard see here http://lwn.net/Articles/414467/

Fair enough, BUG_ON() it is. Repost that version and you can add my

Thanks,

Josef

...

Thank you! Added and resent as:
http://www.mail-archive.com/[email protected]/msg09357.html

  Sergei

Excerpts from Sergei Trofimovich's message of 2011-04-12 17:23:33 -0400:

This is in the master branch now, please give it another test. Thanks a lot for bisecting down and patching!

-chris

Tested on btrfs-unstable/master. Works correctly. Reverting 3387206f26e1b48703e810175b98611a4fd8e8ea (to make sure) on top of master returns panic.

Thank you!

  Sergei