[PATCHv2] btrfs-progs: Fix slot >= nritems

[PATCHv2] btrfs-progs: Fix slot >= nritems

[Philipp Hahn]

Running "btrfsck --repair /dev/sdd2" crashed as it can happen in
(corrupted) file systems, that slot > nritems:
> (gdb) bt full
> #0  0x00007ffff7020e71 in __memmove_sse2_unaligned_erms () from /lib/x86_64-linux-gnu/libc.so.6
> #1  0x0000000000438764 in btrfs_del_ptr (trans=<optimized out>, root=0x6e4fe0, path=0x1d17880, level=0, slot=7)
>     at ctree.c:2611
>         parent = 0xcd96980
>         nritems = <optimized out>
>         __func__ = "btrfs_del_ptr"
> #2  0x0000000000421b15 in repair_btree (corrupt_blocks=<optimized out>, root=<optimized out>) at cmds-check.c:3539
>         key = {objectid = 77990592512, type = 168 '\250', offset = 16384}
>         trans = 0x8f48c0
>         path = 0x1d17880
>         level = 0
> #3  check_fs_root (wc=<optimized out>, root_cache=<optimized out>, root=<optimized out>) at cmds-check.c:3703
>         corrupt = 0x1d17880
>         corrupt_blocks = {root = {rb_node = 0x6e80c60}}
>         path = {nodes = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, slots = {0, 0, 0, 0, 0, 0, 0, 0}, locks = {0, 0,
>             0, 0, 0, 0, 0, 0}, reada = 0, lowest_level = 0, search_for_split = 0, skip_check_block = 0}
>         nrefs = {bytenr = {271663104, 271646720, 560021504, 0, 0, 0, 0, 0}, refs = {1, 1, 1, 0, 0, 0, 0, 0}}
>         wret = 215575372
>         root_node = {cache = {rb_node = {__rb_parent_color = 0, rb_right = 0x0, rb_left = 0x0}, objectid = 0,
>             start = 0, size = 0}, root_cache = {root = {rb_node = 0x0}}, inode_cache = {root = {
>               rb_node = 0x781c80}}, current = 0x819530, refs = 0}
>         status = 215575372
>         rec = 0x1
> #4  check_fs_roots (root_cache=0xcd96b6d, root=<optimized out>) at cmds-check.c:3809
>         path = {nodes = {0x6eed90, 0x6a2f40, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, slots = {18, 2, 0, 0, 0, 0, 0, 0},
>           locks = {0, 0, 0, 0, 0, 0, 0, 0}, reada = 0, lowest_level = 0, search_for_split = 0,
>           skip_check_block = 0}
>         key = {objectid = 323, type = 132 '\204', offset = 18446744073709551615}
>         wc = {shared = {root = {rb_node = 0x0}}, nodes = {0x0, 0x0, 0x7fffffffe428, 0x0, 0x0, 0x0, 0x0, 0x0},
>           active_node = 2, root_level = 2}
>         leaf = 0x6e4fe0
>         tmp_root = 0x6e4fe0
> #5  0x00000000004287c3 in cmd_check (argc=215575372, argv=0x1d17880) at cmds-check.c:11521
>         root_cache = {root = {rb_node = 0x98c2940}}
>         info = 0x6927b0
>         bytenr = 6891440
>         tree_root_bytenr = 0
>         uuidbuf = "f65ff1a1-76ef-456e-beb5-c6c3841e7534"
>         num = 215575372
>         readonly = 218080104
>         qgroups_repaired = 0
> #6  0x000000000040a41f in main (argc=3, argv=0x7fffffffebe8) at btrfs.c:243
>         cmd = 0x689868
>         bname = <optimized out>
>         ret = <optimized out>

in that case the count of remaining items (nritems - slot - 1) gets
negative. That is then casted to (unsigned long len), which leads to the
observed crash.

Change the tests before the move to handle only the non-corrupted case,
were slow < nritems.

This does not fix the corruption, but allows btrfsck to finish without
crashing.

Signed-off-by: Philipp Hahn <hahn@univention.de>
---
 ctree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/ctree.c b/ctree.c
index 02c7180..798bde9 100644
--- a/ctree.c
+++ b/ctree.c
@@ -1487,7 +1487,8 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
 		BUG();
 	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
 		BUG();
-	if (slot != nritems) {
+	if (slot < nritems) {
+		/* shift the items */
 		memmove_extent_buffer(lower,
 			      btrfs_node_key_ptr_offset(slot + 1),
 			      btrfs_node_key_ptr_offset(slot),
@@ -2249,7 +2250,7 @@ split:
 
 	nritems = btrfs_header_nritems(leaf);
 
-	if (slot != nritems) {
+	if (slot < nritems) {
 		/* shift the items */
 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
 			      btrfs_item_nr_offset(slot),
@@ -2500,7 +2501,7 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
 	slot = path->slots[0];
 	BUG_ON(slot < 0);
 
-	if (slot != nritems) {
+	if (slot < nritems) {
 		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
 
 		if (old_data < data_end) {
@@ -2603,7 +2604,8 @@ int btrfs_del_ptr(struct btrfs_root *root, struct btrfs_path *path,
 	int ret = 0;
 
 	nritems = btrfs_header_nritems(parent);
-	if (slot != nritems -1) {
+	if (slot < nritems -1) {
+		/* shift the items */
 		memmove_extent_buffer(parent,
 			      btrfs_node_key_ptr_offset(slot),
 			      btrfs_node_key_ptr_offset(slot + 1),
-- 
2.11.0

Re: [PATCHv2] btrfs-progs: Fix slot >= nritems

[David Sterba]

On Mon, May 15, 2017 at 07:00:23PM +0200, Philipp Hahn wrote:
> Running "btrfsck --repair /dev/sdd2" crashed as it can happen in
> (corrupted) file systems, that slot > nritems:
> > (gdb) bt full
> > #0  0x00007ffff7020e71 in __memmove_sse2_unaligned_erms () from /lib/x86_64-linux-gnu/libc.so.6
> > #1  0x0000000000438764 in btrfs_del_ptr (trans=<optimized out>, root=0x6e4fe0, path=0x1d17880, level=0, slot=7)
> >     at ctree.c:2611
> >         parent = 0xcd96980
> >         nritems = <optimized out>
> >         __func__ = "btrfs_del_ptr"
> > #2  0x0000000000421b15 in repair_btree (corrupt_blocks=<optimized out>, root=<optimized out>) at cmds-check.c:3539
> >         key = {objectid = 77990592512, type = 168 '\250', offset = 16384}
> >         trans = 0x8f48c0
> >         path = 0x1d17880
> >         level = 0
> > #3  check_fs_root (wc=<optimized out>, root_cache=<optimized out>, root=<optimized out>) at cmds-check.c:3703
> >         corrupt = 0x1d17880
> >         corrupt_blocks = {root = {rb_node = 0x6e80c60}}
> >         path = {nodes = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, slots = {0, 0, 0, 0, 0, 0, 0, 0}, locks = {0, 0,
> >             0, 0, 0, 0, 0, 0}, reada = 0, lowest_level = 0, search_for_split = 0, skip_check_block = 0}
> >         nrefs = {bytenr = {271663104, 271646720, 560021504, 0, 0, 0, 0, 0}, refs = {1, 1, 1, 0, 0, 0, 0, 0}}
> >         wret = 215575372
> >         root_node = {cache = {rb_node = {__rb_parent_color = 0, rb_right = 0x0, rb_left = 0x0}, objectid = 0,
> >             start = 0, size = 0}, root_cache = {root = {rb_node = 0x0}}, inode_cache = {root = {
> >               rb_node = 0x781c80}}, current = 0x819530, refs = 0}
> >         status = 215575372
> >         rec = 0x1
> > #4  check_fs_roots (root_cache=0xcd96b6d, root=<optimized out>) at cmds-check.c:3809
> >         path = {nodes = {0x6eed90, 0x6a2f40, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, slots = {18, 2, 0, 0, 0, 0, 0, 0},
> >           locks = {0, 0, 0, 0, 0, 0, 0, 0}, reada = 0, lowest_level = 0, search_for_split = 0,
> >           skip_check_block = 0}
> >         key = {objectid = 323, type = 132 '\204', offset = 18446744073709551615}
> >         wc = {shared = {root = {rb_node = 0x0}}, nodes = {0x0, 0x0, 0x7fffffffe428, 0x0, 0x0, 0x0, 0x0, 0x0},
> >           active_node = 2, root_level = 2}
> >         leaf = 0x6e4fe0
> >         tmp_root = 0x6e4fe0
> > #5  0x00000000004287c3 in cmd_check (argc=215575372, argv=0x1d17880) at cmds-check.c:11521
> >         root_cache = {root = {rb_node = 0x98c2940}}
> >         info = 0x6927b0
> >         bytenr = 6891440
> >         tree_root_bytenr = 0
> >         uuidbuf = "f65ff1a1-76ef-456e-beb5-c6c3841e7534"
> >         num = 215575372
> >         readonly = 218080104
> >         qgroups_repaired = 0
> > #6  0x000000000040a41f in main (argc=3, argv=0x7fffffffebe8) at btrfs.c:243
> >         cmd = 0x689868
> >         bname = <optimized out>
> >         ret = <optimized out>
> 
> in that case the count of remaining items (nritems - slot - 1) gets
> negative. That is then casted to (unsigned long len), which leads to the
> observed crash.
> 
> Change the tests before the move to handle only the non-corrupted case,
> were slow < nritems.
> 
> This does not fix the corruption, but allows btrfsck to finish without
> crashing.
> 
> Signed-off-by: Philipp Hahn <hahn@univention.de>

Applied, thanks.

[PATCH 0/2] More nritems range checking

[Philipp Hahn]

Hi,

thank you for applying my last patch, but regarding my corrputed file system I
found two other cases were btrfs crashes:
- btrfs_del_items() was overlooked by me
- deleting from an empty node

Find attached two patches to improve that.
Please check the second patch hunk 2, as I'm unsure if "mid == nritems" is valid.

(If someone can give me a hand on how to get my FS fixed again, I would
appreciate that.)

Philipp Hahn (2):
  btrfs-progs: Check slot + nr >= nritems overflow
  btrfs-progs: Check nritems under-/overflow

 ctree.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

-- 
2.11.0

[PATCH 1/2] btrfs-progs: Check slot + nr >= nritems overflow

[Philipp Hahn]

711a0b48683b71d61caffbd67a90ec8db5412675 is incomplete and missed the
case in btrfs_del_ptr(), where multiple items are removed.

> Running "btrfsck --repair /dev/sdd2" crashed as it can happen in
> (corrupted) file systems, that slot > nritems.
> ...
> in that case the count of remaining items (nritems - slot - nr) gets
> negative. That is then casted to (unsigned long len), which leads to the
> observed crash.

Change the tests before the move to handle only the non-corrupted case,
were slot + nr < nritems.

This does not fix the corruption, but allows btrfsck to finish without
crashing.

Signed-off-by: Philipp Hahn <hahn@univention.de>
---
 ctree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/ctree.c b/ctree.c
index 798bde9..201f671 100644
--- a/ctree.c
+++ b/ctree.c
@@ -2656,7 +2656,7 @@ static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
 }
 
 /*
- * delete the item at the leaf level in path.  If that empties
+ * delete 'nr' items at the leaf level in path.  If that empties
  * the leaf, remove it from the tree
  */
 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
@@ -2679,7 +2679,7 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 
 	nritems = btrfs_header_nritems(leaf);
 
-	if (slot + nr != nritems) {
+	if (slot + nr < nritems) {
 		int data_end = leaf_data_end(root, leaf);
 
 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
-- 
2.11.0

[PATCH 2/2] btrfs-progs: Check nritems under-/overflow

[Philipp Hahn]

711a0b48683b71d61caffbd67a90ec8db5412675 is incomplete and missed some
cases, where 'nritems' is outside its valid range, e.g.
- insert_ptr(): inserting into an already full node
- copy_for_split(): splitting more items than contained
- btrfs_del_ptr(): deleting one item from an already empty node (*)
- btrfs_del_items(): deleting more items than contained.

Use BUG_ON() checks to get more useful error messages in case those
cases happen.

(Here is the debug data from my corrupted file system triggering *:)
> (gdb) bt
> #3  btrfs_del_ptr (root=root@entry=0x6fcfa0, path=path@entry=0x7fffffffd7d0, level=level@entry=0, slot=<optimized out>) at ctree.c:2607
> #4  0x00000000004516a1 in repair_btree (corrupt_blocks=0x7fffffffd970, root=0x6fcfa0) at cmds-check.c:3847
> #5  check_fs_root (root=root@entry=0x6fcfa0, root_cache=root_cache@entry=0x7fffffffde60, wc=wc@entry=0x7fffffffdbb0) at cmds-check.c:4009
> #6  0x000000000045da04 in check_fs_roots (root_cache=0x7fffffffde60, root=0x6e2770) at cmds-check.c:4115
> #7  cmd_check (argc=<optimized out>, argv=<optimized out>) at cmds-check.c:13079
> #8  0x000000000040aae9 in main (argc=4, argv=0x7fffffffdfa8) at btrfs.c:302

> (gdb) frame 4
> #4  0x00000000004516a1 in repair_btree (corrupt_blocks=0x7fffffffd970, root=0x6fcfa0) at cmds-check.c:3847
> 3847                    ret = btrfs_del_ptr(root, &path, level, path.slots[level]);

> (gdb) info locals
> corrupt = 0x52b2dd0
> key = {objectid = 78229979136, type = 168 '\250', offset = 16384}
> ret = <optimized out>
> trans = 0x8f0ac0
> path = {nodes = {0xd8ac7d0, 0xd8ccc50, 0x6bf010, 0x0, 0x0, 0x0, 0x0, 0x0}, slots = {0, 417, 232, 0, 0, 0, 0, 0}, reada = 0 '\000', lowest_level = 0 '\000', search_for_split = 0 '\000', skip_check_block = 0 '\000'}
> cache = 0x52b2dd0
> level = 0

Signed-off-by: Philipp Hahn <hahn@univention.de>
---
 ctree.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/ctree.c b/ctree.c
index 201f671..c5af7f6 100644
--- a/ctree.c
+++ b/ctree.c
@@ -1485,8 +1485,7 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
 	nritems = btrfs_header_nritems(lower);
 	if (slot > nritems)
 		BUG();
-	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
-		BUG();
+	BUG_ON(nritems >= BTRFS_NODEPTRS_PER_BLOCK(root));
 	if (slot < nritems) {
 		/* shift the items */
 		memmove_extent_buffer(lower,
@@ -1967,7 +1966,8 @@ static noinline int copy_for_split(struct btrfs_trans_handle *trans,
 	int wret;
 	struct btrfs_disk_key disk_key;
 
-	nritems = nritems - mid;
+	BUG_ON(mid > nritems);
+	nritems -= mid;
 	btrfs_set_header_nritems(right, nritems);
 	data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
 
@@ -2604,6 +2604,7 @@ int btrfs_del_ptr(struct btrfs_root *root, struct btrfs_path *path,
 	int ret = 0;
 
 	nritems = btrfs_header_nritems(parent);
+	BUG_ON(nritems == 0);
 	if (slot < nritems -1) {
 		/* shift the items */
 		memmove_extent_buffer(parent,
@@ -2678,7 +2679,7 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		dsize += btrfs_item_size_nr(leaf, slot + i);
 
 	nritems = btrfs_header_nritems(leaf);
-
+	BUG_ON(nritems < nr);
 	if (slot + nr < nritems) {
 		int data_end = leaf_data_end(root, leaf);
 
-- 
2.11.0

Re: [PATCH 0/2] More nritems range checking

[Philipp Hahn]

Hello,

Am 02.06.2017 um 12:08 schrieb Philipp Hahn:
> thank you for applying my last patch, but regarding my corrputed file system I
> found two other cases were btrfs crashes:
> - btrfs_del_items() was overlooked by me
> - deleting from an empty node
> 
> Find attached two patches to improve that.
> Please check the second patch hunk 2, as I'm unsure if "mid == nritems" is valid.
> 
> (If someone can give me a hand on how to get my FS fixed again, I would
> appreciate that.)
> 
> Philipp Hahn (2):
>   btrfs-progs: Check slot + nr >= nritems overflow
>   btrfs-progs: Check nritems under-/overflow
> 
>  ctree.c | 13 +++++++------
>  1 file changed, 7 insertions(+), 6 deletions(-)

Ping?

Philipp