[PATCH 1/2] nilfs: enhance btree node keys check

syzbot reported a warning on nilfs_btree_assign:
WARNING: fs/nilfs2/btree.c:2302 at nilfs_btree_assign+0x983/0xbe0 fs/nilfs2/btree.c:2302,

Analysis found that a corrupted file has the following btree layout:
Level2(key/ptr): [ 256/15 ]
Level1(key/ptr): [ 0/8, 1/9, 0/10, 3/11, 4/12, 5/13, 6/14, 139637976727559/16, 0/17 ]

The test truncated the file to 2 bytes, which partially zeroes the first block and
adds the file to the dirty list. When the segment constructor writes it and assigns
a new blocknr for the index block, it searches the btree with key=0 and min level=2,
and apparently returns ENOENT.

Therefore, we should perform more checks on the btree nodes and return early.

Signed-off-by: Wang Jianjian <[email protected]>
---
 fs/nilfs2/btree.c | 40 +++++++++++++++++++++++++++++++++++-----
 1 file changed, 35 insertions(+), 5 deletions(-)

diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c
index 64d5f7c5ab44..8b164e13663f 100644
--- a/fs/nilfs2/btree.c
+++ b/fs/nilfs2/btree.c
@@ -448,16 +448,46 @@ nilfs_btree_get_node(const struct nilfs_bmap *btree,
 }
 
 static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
+				const struct nilfs_btree_path *path,
 				struct nilfs_btree_node *node, int level)
 {
+	struct inode *inode = btree->b_inode;
+	__u64 key1, key2;
+	int i, ncmax;
+
 	if (unlikely(nilfs_btree_node_get_level(node) != level)) {
 		dump_stack();
-		nilfs_crit(btree->b_inode->i_sb,
+		nilfs_crit(inode->i_sb,
 			   "btree level mismatch (ino=%llu): %d != %d",
-			   btree->b_inode->i_ino,
-			   nilfs_btree_node_get_level(node), level);
+			   inode->i_ino, nilfs_btree_node_get_level(node), level);
 		return 1;
 	}
+
+	for (i = 1; i < nilfs_btree_node_get_nchildren(node); i++) {
+		key1 = nilfs_btree_node_get_key(node, i);
+		key2 = nilfs_btree_node_get_key(node, i - 1);
+
+		if (key1 <= key2) {
+			nilfs_crit(inode->i_sb,
+				   "btree node(ino=%llu) level=%d key not sorted: %d/%llu <= %d/%llu",
+					inode->i_ino, level, i, key1, i - 1, key2);
+			return 1;
+		}
+	}
+
+	if (level < nilfs_btree_height(btree) - 1) {
+		struct nilfs_btree_node *parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
+
+		key1 = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
+		key2 = nilfs_btree_node_get_key(node, 0);
+		if (key1 != key2) {
+			nilfs_crit(inode->i_sb,
+				   "btree node(ino=%llu) level=%d key=%llu not equal to parent's key=%llu",
+				   inode->i_ino, level, key2, key1);
+			return 1;
+		}
+	}
+
 	return 0;
 }
 
@@ -582,7 +612,7 @@ static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
 			return ret;
 
 		node = nilfs_btree_get_nonroot_node(path, level);
-		if (nilfs_btree_bad_node(btree, node, level))
+		if (nilfs_btree_bad_node(btree, path, node, level))
 			return -EINVAL;
 		if (!found)
 			found = nilfs_btree_node_lookup(node, key, &index);
@@ -630,7 +660,7 @@ static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
 		if (ret < 0)
 			return ret;
 		node = nilfs_btree_get_nonroot_node(path, level);
-		if (nilfs_btree_bad_node(btree, node, level))
+		if (nilfs_btree_bad_node(btree, path, node, level))
 			return -EINVAL;
 		index = nilfs_btree_node_get_nchildren(node) - 1;
 		ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
-- 
2.34.1