Integer underflow in ctree.c

PATCH In review Sandino Araico Sánchez 3 participants 5 messages Jun 19, 2015 – Jul 20, 2015 Btrfs file system

lore

Share & tools

lore

Sandino Araico Sánchez

author

2015-06-19 16:31 UTC #0 lore raw

PATCH 1/1 Integer underflow in ctree.c

:btrfs check crashed while trying to fix my corrupted filesystem.

btrfs check --repair /dev/sdd3
enabling repair mode
Checking filesystem on /dev/sdd3
UUID: 58222ebc-79ca-4dc4-891f-129aae342313
checking extents
bad key ordering 0 1
bad block 3535142326272
Errors found in extent allocation tree or chunk allocation Fixed 0 roots.
checking free space cache
cache and super generation don't match, space cache will be invalidated checking fs roots
bad key ordering 0 1
bad key ordering 0 1
The following tree block(s) is corrupted in tree 814:

        tree block bytenr: 3535142346752, level: 0, node key:

(1270098042880, 168, 4096)
Try to repair the btree for root 814
Segmentation fault

What I found on the gdb backtrace:

(gdb) bt
#0Â 0x00006fc5cb578411 in ?? ()
#1Â 0x000009d5fe028bab in memmove_extent_buffer (dst=0x9d76942cf30, dst_offset=1586, src_offset=1619, len=141733920735) at extent_io.c:880 #2Â 0x000009d5fe002e1b in btrfs_del_ptr (trans=0x9d7669ec990, root=0x9d7648891c0, path=0x9d7669f69f0, level=0, slot=45) at ctree.c:2592 #3Â 0x000009d5fdfd467a in repair_btree (root=0x9d7648891c0, corrupt_blocks=0x70f1b0905030) at cmds-check.c:3267
#4Â 0x000009d5fdfd4e40 in check_fs_root (root=0x9d7648891c0, root_cache=0x70f1b0905380, wc=0x70f1b0905240) at cmds-check.c:3422 #5Â 0x000009d5fdfd52e6 in check_fs_roots (root=0x9d5ffdf0d10, root_cache=0x70f1b0905380) at cmds-check.c:3523
#6Â 0x000009d5fdfe4ce6 in cmd_check (argc=1, argv=0x70f1b0905560) at cmds-check.c:9470
#7Â 0x000009d5fdfad8a1 in main (argc=3, argv=0x70f1b0905560) at btrfs.c:245 (gdb) select-frame 2
(gdb) info locals
parent = 0x9d76942cf30
nritems = 45
ret = 0
__func__ = "btrfs_del_ptr"

function btrfs_del_ptr parameter is called with slot=45
and in line 2590Â btrfs_header_nritems(parent) returns 45 for variable nritems;

in line 2596 the result of (nritems - slot - 1) equals to 0x00000000 - 1 and memmove_extent_buffer gets called with a huge value for parameter len.

After the patch btrfs check is not crashing anymore.

Signature · 2 lines

Sandino Araico SÃ¡nchez 
http://sandino.net

ctree.c +1 -1

diff -uri btrfs-progs-v4.0.1.orig/ctree.c btrfs-progs-v4.0.1/ctree.c
@@ -2588,7 +2588,7 @@
 	int ret = 0;
 
 	nritems = btrfs_header_nritems(parent);
-	if (slot != nritems -1) {
+	if (slot < nritems -1) {
 		memmove_extent_buffer(parent,
 			      btrfs_node_key_ptr_offset(slot),
 			      btrfs_node_key_ptr_offset(slot + 1),

David Sterba

2015-07-03 16:51 UTC #1 lore raw

Quoted 46 lines · Sandino Araico Sánchez

:btrfs check crashed while trying to fix my corrupted filesystem.
btrfs check --repair /dev/sdd3
enabling repair mode
Checking filesystem on /dev/sdd3
UUID: 58222ebc-79ca-4dc4-891f-129aae342313
checking extents
bad key ordering 0 1
bad block 3535142326272
Errors found in extent allocation tree or chunk allocation Fixed 0 roots.
checking free space cache
cache and super generation don't match, space cache will be invalidated checking fs roots
bad key ordering 0 1
bad key ordering 0 1
The following tree block(s) is corrupted in tree 814:
        tree block bytenr: 3535142346752, level: 0, node key:
(1270098042880, 168, 4096)
Try to repair the btree for root 814
Segmentation fault
What I found on the gdb backtrace:
(gdb) bt
#0Â 0x00006fc5cb578411 in ?? ()
#1Â 0x000009d5fe028bab in memmove_extent_buffer (dst=0x9d76942cf30, dst_offset=1586, src_offset=1619, len=141733920735) at extent_io.c:880 #2Â 0x000009d5fe002e1b in btrfs_del_ptr (trans=0x9d7669ec990, root=0x9d7648891c0, path=0x9d7669f69f0, level=0, slot=45) at ctree.c:2592 #3Â 0x000009d5fdfd467a in repair_btree (root=0x9d7648891c0, corrupt_blocks=0x70f1b0905030) at cmds-check.c:3267
#4Â 0x000009d5fdfd4e40 in check_fs_root (root=0x9d7648891c0, root_cache=0x70f1b0905380, wc=0x70f1b0905240) at cmds-check.c:3422 #5Â 0x000009d5fdfd52e6 in check_fs_roots (root=0x9d5ffdf0d10, root_cache=0x70f1b0905380) at cmds-check.c:3523
#6Â 0x000009d5fdfe4ce6 in cmd_check (argc=1, argv=0x70f1b0905560) at cmds-check.c:9470
#7Â 0x000009d5fdfad8a1 in main (argc=3, argv=0x70f1b0905560) at btrfs.c:245 (gdb) select-frame 2
(gdb) info locals
parent = 0x9d76942cf30
nritems = 45
ret = 0
__func__ = "btrfs_del_ptr"

Quoted 6 lines

function btrfs_del_ptr parameter is called with slot=45
and in line 2590Â btrfs_header_nritems(parent) returns 45 for variable nritems;
in line 2596 the result of (nritems - slot - 1) equals to 0x00000000 - 1 and memmove_extent_buffer gets called with a huge value for parameter len.

Very useful, thanks.

The repair mode tries to remove the corrupted leaves, added in commit 1581d7e5db9278a3aef5ff88301a9866b57cd5ad, but seems that it needs more sanity checking before it actuall tyres to call btrfs_del_ptr.

ctree.c line 2591

Quoted 9 lines

After the patch btrfs check is not crashing anymore.

ctree.c +1 -1

@@ -2588,7 +2588,7 @@
 	int ret = 0;
 
 	nritems = btrfs_header_nritems(parent);
-	if (slot != nritems -1) {
+	if (slot < nritems -1) {

Though this helped, I think that passing slot == nritems is wrong and should be caught up the callstack. I've CCed Qu, maybe he has some insights.

Quoted 4 lines

ctree.c +0 -0

 		memmove_extent_buffer(parent,
 			      btrfs_node_key_ptr_offset(slot),
 			      btrfs_node_key_ptr_offset(slot + 1),

Qu Wenruo

2015-07-07 08:38 UTC #2 lore raw

Thanks for the report, Sandino,
and the CC from David.

I'll double check my codes to see if there is any similar problems.

The fix looks good so far.
If it has no problem, I'll resend the fix, keeping the author as Sandino.

Thanks,
Qu

David Sterba wrote on 2015/07/03 18:51 +0200:

Quoted 79 lines · Sandino Araico Sánchez

Quoted 46 lines
:btrfs check crashed while trying to fix my corrupted filesystem.
btrfs check --repair /dev/sdd3
enabling repair mode
Checking filesystem on /dev/sdd3
UUID: 58222ebc-79ca-4dc4-891f-129aae342313
checking extents
bad key ordering 0 1
bad block 3535142326272
Errors found in extent allocation tree or chunk allocation Fixed 0 roots.
checking free space cache
cache and super generation don't match, space cache will be invalidated checking fs roots
bad key ordering 0 1
bad key ordering 0 1
The following tree block(s) is corrupted in tree 814:
         tree block bytenr: 3535142346752, level: 0, node key:
(1270098042880, 168, 4096)
Try to repair the btree for root 814
Segmentation fault
What I found on the gdb backtrace:
(gdb) bt
#0Â 0x00006fc5cb578411 in ?? ()
#1Â 0x000009d5fe028bab in memmove_extent_buffer (dst=0x9d76942cf30, dst_offset=1586, src_offset=1619, len=141733920735) at extent_io.c:880 #2Â 0x000009d5fe002e1b in btrfs_del_ptr (trans=0x9d7669ec990, root=0x9d7648891c0, path=0x9d7669f69f0, level=0, slot=45) at ctree.c:2592 #3Â 0x000009d5fdfd467a in repair_btree (root=0x9d7648891c0, corrupt_blocks=0x70f1b0905030) at cmds-check.c:3267
#4Â 0x000009d5fdfd4e40 in check_fs_root (root=0x9d7648891c0, root_cache=0x70f1b0905380, wc=0x70f1b0905240) at cmds-check.c:3422 #5Â 0x000009d5fdfd52e6 in check_fs_roots (root=0x9d5ffdf0d10, root_cache=0x70f1b0905380) at cmds-check.c:3523
#6Â 0x000009d5fdfe4ce6 in cmd_check (argc=1, argv=0x70f1b0905560) at cmds-check.c:9470
#7Â 0x000009d5fdfad8a1 in main (argc=3, argv=0x70f1b0905560) at btrfs.c:245 (gdb) select-frame 2
(gdb) info locals
parent = 0x9d76942cf30
nritems = 45
ret = 0
__func__ = "btrfs_del_ptr"
Quoted 6 lines
function btrfs_del_ptr parameter is called with slot=45
and in line 2590Â btrfs_header_nritems(parent) returns 45 for variable nritems;
in line 2596 the result of (nritems - slot - 1) equals to 0x00000000 - 1 and memmove_extent_buffer gets called with a huge value for parameter len.
Very useful, thanks.
The repair mode tries to remove the corrupted leaves, added in commit 1581d7e5db9278a3aef5ff88301a9866b57cd5ad, but seems that it needs more sanity checking before it actuall tyres to call btrfs_del_ptr.
ctree.c line 2591
Quoted 9 lines
After the patch btrfs check is not crashing anymore.
ctree.c +1 -1
@@ -2588,7 +2588,7 @@
  	int ret = 0;
 
  	nritems = btrfs_header_nritems(parent);
-	if (slot != nritems -1) {
+	if (slot < nritems -1) {
Though this helped, I think that passing slot == nritems is wrong and should be caught up the callstack. I've CCed Qu, maybe he has some insights.
Quoted 4 lines
ctree.c +0 -0
  		memmove_extent_buffer(parent,
  			      btrfs_node_key_ptr_offset(slot),
  			      btrfs_node_key_ptr_offset(slot + 1),

Qu Wenruo

2015-07-07 09:14 UTC #3 lore raw

In reply to Sandino Araico Sánchez

Sandino Araico Sánchez wrote on 2015/06/19 11:31 -0500:

Quoted 46 lines

:btrfs check crashed while trying to fix my corrupted filesystem.
btrfs check --repair /dev/sdd3
enabling repair mode
Checking filesystem on /dev/sdd3
UUID: 58222ebc-79ca-4dc4-891f-129aae342313
checking extents
bad key ordering 0 1
bad block 3535142326272
Errors found in extent allocation tree or chunk allocation Fixed 0 roots.
checking free space cache
cache and super generation don't match, space cache will be invalidated checking fs roots
bad key ordering 0 1
bad key ordering 0 1
The following tree block(s) is corrupted in tree 814:
         tree block bytenr: 3535142346752, level: 0, node key:
(1270098042880, 168, 4096)
Try to repair the btree for root 814
Segmentation fault
What I found on the gdb backtrace:
(gdb) bt
#0Â 0x00006fc5cb578411 in ?? ()
#1Â 0x000009d5fe028bab in memmove_extent_buffer (dst=0x9d76942cf30, dst_offset=1586, src_offset=1619, len=141733920735) at extent_io.c:880 #2Â 0x000009d5fe002e1b in btrfs_del_ptr (trans=0x9d7669ec990, root=0x9d7648891c0, path=0x9d7669f69f0, level=0, slot=45) at ctree.c:2592 #3Â 0x000009d5fdfd467a in repair_btree (root=0x9d7648891c0, corrupt_blocks=0x70f1b0905030) at cmds-check.c:3267
#4Â 0x000009d5fdfd4e40 in check_fs_root (root=0x9d7648891c0, root_cache=0x70f1b0905380, wc=0x70f1b0905240) at cmds-check.c:3422 #5Â 0x000009d5fdfd52e6 in check_fs_roots (root=0x9d5ffdf0d10, root_cache=0x70f1b0905380) at cmds-check.c:3523
#6Â 0x000009d5fdfe4ce6 in cmd_check (argc=1, argv=0x70f1b0905560) at cmds-check.c:9470
#7Â 0x000009d5fdfad8a1 in main (argc=3, argv=0x70f1b0905560) at btrfs.c:245 (gdb) select-frame 2
(gdb) info locals
parent = 0x9d76942cf30
nritems = 45
ret = 0
__func__ = "btrfs_del_ptr"

Quoted 9 lines

function btrfs_del_ptr parameter is called with slot=45
and in line 2590Â btrfs_header_nritems(parent) returns 45 for variable nritems;
in line 2596 the result of (nritems - slot - 1) equals to 0x00000000 - 1 and memmove_extent_buffer gets called with a huge value for parameter len.
After the patch btrfs check is not crashing anymore.

The root problem seems not here.
Would you please show the "level" variant in frame 3?

Or, btrfs-debug-tree with its error output please.
As for such problem we can't use btrfs-image do dump the metadata.

The problem here, is why btrfs_search_slot will return the pointer to
the last *non-exist* slot.
Normally, it means btrfs_search_slot can't find the exact item, and the result slot is where new key should be inserted into.

I'm afraid the level things is corrupted...

Thanks,
Qu

Sandino Araico Sánchez

author

2015-07-20 04:39 UTC #4 lore raw

Quoted 69 lines · Qu Wenruo

Sandino Araico Sánchez wrote on 2015/06/19 11:31 -0500:
Quoted 52 lines
:btrfs check crashed while trying to fix my corrupted filesystem.
btrfs check --repair /dev/sdd3
enabling repair mode
Checking filesystem on /dev/sdd3
UUID: 58222ebc-79ca-4dc4-891f-129aae342313
checking extents
bad key ordering 0 1
bad block 3535142326272
Errors found in extent allocation tree or chunk allocation Fixed 0 roots.
checking free space cache
cache and super generation don't match, space cache will be invalidated checking fs roots
bad key ordering 0 1
bad key ordering 0 1
The following tree block(s) is corrupted in tree 814:
         tree block bytenr: 3535142346752, level: 0, node key:
(1270098042880, 168, 4096)
Try to repair the btree for root 814
Segmentation fault
What I found on the gdb backtrace:
(gdb) bt
#0Â 0x00006fc5cb578411 in ?? ()
#1Â 0x000009d5fe028bab in memmove_extent_buffer (dst=0x9d76942cf30, dst_offset=1586, src_offset=1619, len=141733920735) at extent_io.c:880 #2Â 0x000009d5fe002e1b in btrfs_del_ptr (trans=0x9d7669ec990, root=0x9d7648891c0, path=0x9d7669f69f0, level=0, slot=45) at ctree.c:2592
#3Â 0x000009d5fdfd467a in repair_btree (root=0x9d7648891c0, corrupt_blocks=0x70f1b0905030) at cmds-check.c:3267
#4Â 0x000009d5fdfd4e40 in check_fs_root (root=0x9d7648891c0, root_cache=0x70f1b0905380, wc=0x70f1b0905240) at cmds-check.c:3422 #5Â 0x000009d5fdfd52e6 in check_fs_roots (root=0x9d5ffdf0d10, root_cache=0x70f1b0905380) at cmds-check.c:3523
#6Â 0x000009d5fdfe4ce6 in cmd_check (argc=1, argv=0x70f1b0905560) at cmds-check.c:9470
#7Â 0x000009d5fdfad8a1 in main (argc=3, argv=0x70f1b0905560) at btrfs.c:245
(gdb) select-frame 2
(gdb) info locals
parent = 0x9d76942cf30
nritems = 45
ret = 0
__func__ = "btrfs_del_ptr"
function btrfs_del_ptr parameter is called with slot=45
and in line 2590Â btrfs_header_nritems(parent) returns 45 for variable nritems;
Quoted 6 lines
in line 2596 the result of (nritems - slot - 1) equals to 0x00000000 - 1 and memmove_extent_buffer gets called with a huge value for parameter len.
After the patch btrfs check is not crashing anymore.
The root problem seems not here.
Would you please show the "level" variant in frame 3?
Or, btrfs-debug-tree with its error output please.
As for such problem we can't use btrfs-image do dump the metadata.

Quoted 6 lines

The problem here, is why btrfs_search_slot will return the pointer to the last *non-exist* slot.
Normally, it means btrfs_search_slot can't find the exact item, and the result slot is where new key should be inserted into.
I'm afraid the level things is corrupted...

It's a corrupted filesystem. I tried to fix it but I was unsuccessful. I patched another integer underflow but forgot to send the patch to the list and now btrfs-progs has changed to 4.1. I have attached the patch to this e-mail in case you might find it useful.

After this patch the btrfs check process did not crash anymore but now it loops indefinitely... I spent about a week messing with code in repair_btree() trying to force deletion of the corrupted blocks but I didn't succeed; it kept looping in check_fs_roots() between ret = check_fs_root() and goto again; I stoped trying but the filesystem is still corrupt so I can give it another try.

I will do another btrfs check with btrfs-progs 4.1 and I will send you btrfs-debug-tree output.

Quoted 9 lines

Thanks,
Qu

Signature · 3 lines

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

Signature · 2 lines

Sandino Araico Sánchez 
http://sandino.net

ctree.c +9 -7

diff -uriN btrfs-progs-v4.0.1.orig/ctree.c btrfs-progs-v4.0.1/ctree.c
@@ -2588,14 +2588,16 @@
 	int ret = 0;
 
 	nritems = btrfs_header_nritems(parent);
-	if (slot != nritems -1) {
-		memmove_extent_buffer(parent,
-			      btrfs_node_key_ptr_offset(slot),
-			      btrfs_node_key_ptr_offset(slot + 1),
-			      sizeof(struct btrfs_key_ptr) *
-			      (nritems - slot - 1));
+	if (nritems > 0) {
+		if (slot < nritems -1) {
+			memmove_extent_buffer(parent,
+					 btrfs_node_key_ptr_offset(slot),
+					 btrfs_node_key_ptr_offset(slot + 1),
+					 sizeof(struct btrfs_key_ptr) *
+					 (nritems - slot - 1));
+		}
+		nritems--;
 	}
-	nritems--;
 	btrfs_set_header_nritems(parent, nritems);
 	if (nritems == 0 && parent == root->node) {
 		BUG_ON(btrfs_header_level(root->node) != 1);