btrfs does not work on usermode linux

btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1: Type: text/plain, Size: 2237 bytes --]

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1: Type: text/plain, Size: 463 bytes --]

On Sun, 10 Apr 2011 13:37:10 +0300
Sergei Trofimovich <slyich@gmail.com> wrote:

> 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:

2.6.36 works 2.6.37 doesn't. bsecting

-- 

  Sergei

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1: Type: text/plain, Size: 3522 bytes --]

> > 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:
> 
> 2.6.36 works 2.6.37 doesn't. bsecting

Bisected down to:

commit 59daa706fbec745684702741b9f5373142dd9fdc (v2.6.36-rc2-2-g59daa70)
Author: Ma Ling <ling.ma@intel.com>
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.

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 20ddb28..4cab7db 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

[PATCH] Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1.1: Type: text/plain, Size: 3870 bytes --]

On Sun, 10 Apr 2011 23:06:22 +0300
Sergei Trofimovich <slyich@gmail.com> wrote:

> > > 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:
> > 
> > 2.6.36 works 2.6.37 doesn't. bsecting
> 
> Bisected down to:
> 
> commit 59daa706fbec745684702741b9f5373142dd9fdc (v2.6.36-rc2-2-g59daa70)
> Author: Ma Ling <ling.ma@intel.com>
> 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.
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index 20ddb28..4cab7db 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -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,

Attached nicer patch. Looks like original logic expected ceritain memcpy copy direction,
but there isn't one!

-- 

  Sergei

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: 0001-btrfs-properly-handle-overlapping-areas-in-memmove_e.patch --]
[-- Type: text/x-patch, Size: 2763 bytes --]

From 0eaf33265f8a2e0d76ee6db1ad74ee4422efb122 Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <slyfox@gentoo.org>
Date: Sun, 10 Apr 2011 23:19:53 +0300
Subject: [PATCH] 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/linux-btrfs@vger.kernel.org/msg09302.html

Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
---
 fs/btrfs/extent_io.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 20ddb28..3bbda41 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -3897,6 +3897,7 @@ static void copy_pages(struct page *dst_page, struct page *src_page,
 	else
 		src_kaddr = dst_kaddr;
 
+	BUG_ON(abs(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)
@@ -3970,7 +3971,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 (abs(dst_offset - src_offset) >= len) {
 		memcpy_extent_buffer(dst, dst_offset, src_offset, len);
 		return;
 	}
-- 
1.7.3.4


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

[PATCH v2] Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1.1: Type: text/plain, Size: 648 bytes --]

On Sun, 10 Apr 2011 23:24:03 +0300
Sergei Trofimovich <slyich@gmail.com> wrote:

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

Changes since v1:

>  	else
>  		src_kaddr = dst_kaddr;
>  
> +	BUG_ON(abs(src_off - dst_off) < len);
>  	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);

Too eager BUG_ON. Now used only for src_page == dst_page.

> -	if (dst_offset < src_offset) {
> +	if (abs(dst_offset - src_offset) >= len) {

abs() is not a good thing to use un unsigned values. aded helper overlapping_areas.

-- 

  Sergei

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: 0001-btrfs-properly-handle-overlapping-areas-in-memmove_e.patch --]
[-- Type: text/x-patch, Size: 4236 bytes --]

From 2ac9dd9cc54cee51c5c5219e35cca18a9f3f3a3f Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <slyfox@gentoo.org>
Date: Sun, 10 Apr 2011 23:19:53 +0300
Subject: [PATCH] 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/linux-btrfs@vger.kernel.org/msg09302.html

Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
---
 fs/btrfs/extent_io.c |   11 ++++++++++-
 1 files changed, 10 insertions(+), 1 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 20ddb28..786a0f7 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [PATCH v2] Re: btrfs does not work on usermode linux

[Josef Bacik]

On 04/10/2011 04:58 PM, Sergei Trofimovich wrote:
> On Sun, 10 Apr 2011 23:24:03 +0300
> Sergei Trofimovich<slyich@gmail.com>  wrote:
>
>> Fix data corruption caused by memcpy() usage on overlapping data.
>> I've observed it first when found out usermode linux crash on btrfs.
>
> Changes since v1:
>
>>   	else
>>   		src_kaddr = dst_kaddr;
>>
>> +	BUG_ON(abs(src_off - dst_off)<  len);
>>   	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
>
> Too eager BUG_ON. Now used only for src_page == dst_page.
>
>> -	if (dst_offset<  src_offset) {
>> +	if (abs(dst_offset - src_offset)>= len) {
>
> abs() is not a good thing to use un unsigned values. aded helper overlapping_areas.
>

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

[PATCH v3] Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1.1: Type: text/plain, Size: 1707 bytes --]

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

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:

>  	else
>  		src_kaddr = dst_kaddr;
>  
> +	BUG_ON(abs(src_off - dst_off) < len);
>  	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);  

Too eager BUG_ON. Now used only for src_page == dst_page.

> -	if (dst_offset < src_offset) {
> +	if (abs(dst_offset - src_offset) >= len) {  

abs() is not a good thing to use un unsigned values. aded helper overlapping_areas.

On Mon, 11 Apr 2011 11:37:57 -0400
Josef Bacik <josef@redhat.com> wrote:

> +	{
> you will want to turn that into
> 
> if (dst_page != src_page) {

done

> 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,

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

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.2: BUG_ON-0001-btrfs-properly-handle-overlapping-areas-in-memmove_e.patch --]
[-- Type: text/x-patch, Size: 3463 bytes --]

From aaaf03ebcdee3f65e898016b14bc81c66bfdd31c Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <slyfox@gentoo.org>
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/linux-btrfs@vger.kernel.org/msg09302.html

Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
---
 fs/btrfs/extent_io.c |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 20ddb28..10db989 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1.3: WARN_ON-0001-btrfs-properly-handle-overlapping-areas-in-memmove_e.patch --]
[-- Type: text/x-patch, Size: 3464 bytes --]

From 51602c049c4583fc7b1ef454f630138f12dba70e Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <slyfox@gentoo.org>
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/linux-btrfs@vger.kernel.org/msg09302.html

Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>
---
 fs/btrfs/extent_io.c |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 20ddb28..2655aef 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [PATCH v3] Re: btrfs does not work on usermode linux

[Niklas Schnelle]

[-- Attachment #1: Type: text/plain, Size: 1993 bytes --]

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

On Mon, 2011-04-11 at 22:44 +0300, Sergei Trofimovich wrote:
> > Fix data corruption caused by memcpy() usage on overlapping data.
> > I've observed it first when found out usermode linux crash on btrfs.  
> 
> 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:
> 
> >  	else
> >  		src_kaddr = dst_kaddr;
> >  
> > +	BUG_ON(abs(src_off - dst_off) < len);
> >  	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);  
> 
> Too eager BUG_ON. Now used only for src_page == dst_page.
> 
> > -	if (dst_offset < src_offset) {
> > +	if (abs(dst_offset - src_offset) >= len) {  
> 
> abs() is not a good thing to use un unsigned values. aded helper overlapping_areas.
> 
> On Mon, 11 Apr 2011 11:37:57 -0400
> Josef Bacik <josef@redhat.com> wrote:
> 
> > +	{
> > you will want to turn that into
> > 
> > if (dst_page != src_page) {
> 
> done
> 
> > 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,
> 
> 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!
> 


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH v3] Re: btrfs does not work on usermode linux

[Josef Bacik]

On 04/11/2011 03:44 PM, Sergei Trofimovich wrote:
>> Fix data corruption caused by memcpy() usage on overlapping data.
>> I've observed it first when found out usermode linux crash on btrfs.
>
> 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:
>
>>   	else
>>   		src_kaddr = dst_kaddr;
>>
>> +	BUG_ON(abs(src_off - dst_off)<  len);
>>   	memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
>
> Too eager BUG_ON. Now used only for src_page == dst_page.
>
>> -	if (dst_offset<  src_offset) {
>> +	if (abs(dst_offset - src_offset)>= len) {
>
> abs() is not a good thing to use un unsigned values. aded helper overlapping_areas.
>
> On Mon, 11 Apr 2011 11:37:57 -0400
> Josef Bacik<josef@redhat.com>  wrote:
>
>> +	{
>> you will want to turn that into
>>
>> if (dst_page != src_page) {
>
> done
>
>> 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,
>
> 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!
>

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

Reviewed-by: Josef Bacik <josef@redhat.com>

Thanks,

Josef

Re: [PATCH v3] Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1: Type: text/plain, Size: 534 bytes --]

On Mon, 11 Apr 2011 15:50:48 -0400
Josef Bacik <josef@redhat.com> wrote:

> On 04/11/2011 03:44 PM, Sergei Trofimovich wrote:
> >> Fix data corruption caused by memcpy() usage on overlapping data.
> >> I've observed it first when found out usermode linux crash on btrfs.

...

> Fair enough, BUG_ON() it is.  Repost that version and you can add my
> 
> Reviewed-by: Josef Bacik <josef@redhat.com>

Thank you! Added and resent as:
http://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg09357.html

-- 

  Sergei

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [PATCH v3] Re: btrfs does not work on usermode linux

[Chris Mason]

Excerpts from Sergei Trofimovich's message of 2011-04-12 17:23:33 -0400:
> On Mon, 11 Apr 2011 15:50:48 -0400
> Josef Bacik <josef@redhat.com> wrote:
> 
> > On 04/11/2011 03:44 PM, Sergei Trofimovich wrote:
> > >> Fix data corruption caused by memcpy() usage on overlapping data.
> > >> I've observed it first when found out usermode linux crash on btrfs.
> 
> ...
> 
> > Fair enough, BUG_ON() it is.  Repost that version and you can add my
> > 
> > Reviewed-by: Josef Bacik <josef@redhat.com>
> 
> Thank you! Added and resent as:
> http://www.mail-archive.com/linux-btrfs@vger.kernel.org/msg09357.html
> 

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

-chris

Re: [PATCH v3] Re: btrfs does not work on usermode linux

[Sergei Trofimovich]

[-- Attachment #1: Type: text/plain, Size: 385 bytes --]

On Wed, 13 Apr 2011 07:32:59 -0400
Chris Mason <chris.mason@oracle.com> wrote:

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

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

Thank you!

-- 

  Sergei

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 198 bytes --]