Skip to contentSkip to conversation

btrfs-progs: Fix slot >= nritems

PATCH Applied Philipp Hahn 3 participants 6 messages May 15, 2017 – Aug 2, 2017 Btrfs file system

lore
Share & tools
lore

Philipp Hahn

author
#0 lore raw

PATCH v2 1/1 btrfs-progs: Fix slot >= nritems

Running "btrfsck --repair /dev/sdd2" crashed as it can happen in (corrupted) file systems, that slot > nritems:

Quoted 42 lines

(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
Quoted 4 lines

#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 <[email protected]>
---
 ctree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)
ctree.c +6 -4
index 02c7180..798bde9 100644
@@ -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),
Signature · 1 line
2.11.0
Applied
#1 lore raw
Quoted 53 lines · Philipp Hahn

Running "btrfsck --repair /dev/sdd2" crashed as it can happen in (corrupted) file systems, that slot > nritems:

Quoted 42 lines

(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
Quoted 4 lines

#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.

Quoted 7 lines

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 <[email protected]>

Applied, thanks.

author
#2 lore raw

cover More nritems range checking

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(-)
Signature · 1 line
2.11.0
author
#3 lore raw

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

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

Quoted 6 lines

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 <[email protected]>
---
 ctree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
ctree.c +2 -2
index 798bde9..201f671 100644
@@ -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) +
Signature · 1 line
2.11.0
author
#4 lore raw

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

In reply to 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 *:)

Quoted 12 lines

(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]);

Quoted 8 lines

(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 <[email protected]>
---
 ctree.c | 9 +++++----
 1 file changed, 5 insertions(+), 4 deletions(-)
ctree.c +5 -4
index 201f671..c5af7f6 100644
@@ -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);
Signature · 1 line
2.11.0
#5 lore raw

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

In reply to Philipp Hahn

Hello,

Am 02.06.2017 um 12:08 schrieb Philipp Hahn:

Quoted 11 lines

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.)

Quoted 6 lines

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