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

On Thu, Jul 30, 2026 at 9:32=E2=80=AFPM Wang Jianjian wrote:
>
> syzbot reported a warning on nilfs_btree_assign:
> WARNING: fs/nilfs2/btree.c:2302 at nilfs_btree_assign+0x983/0xbe0 fs/nilf=
s2/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, 13963797672755=
9/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 a=
nd assigns
> a new blocknr for the index block, it searches the btree with key=3D0 and=
 min level=3D2,
> and apparently returns ENOENT.
>
> Therefore, we should perform more checks on the btree nodes and return ea=
rly.
>
> 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 =3D btree->b_inode;
> +       __u64 key1, key2;
> +       int i, ncmax;
> +
>         if (unlikely(nilfs_btree_node_get_level(node) !=3D level)) {
>                 dump_stack();
> -               nilfs_crit(btree->b_inode->i_sb,
> +               nilfs_crit(inode->i_sb,
>                            "btree level mismatch (ino=3D%llu): %d !=3D %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 =3D 1; i < nilfs_btree_node_get_nchildren(node); i++) {
> +               key1 =3D nilfs_btree_node_get_key(node, i);
> +               key2 =3D nilfs_btree_node_get_key(node, i - 1);
> +
> +               if (key1 <=3D key2) {
> +                       nilfs_crit(inode->i_sb,
> +                                  "btree node(ino=3D%llu) level=3D%d key=
 not sorted: %d/%llu <=3D %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 =3D nilfs_btree_get_node(=
btree, path, level + 1, &ncmax);
> +
> +               key1 =3D nilfs_btree_node_get_key(parent, path[level + 1]=
.bp_index);
> +               key2 =3D nilfs_btree_node_get_key(node, 0);
> +               if (key1 !=3D key2) {
> +                       nilfs_crit(inode->i_sb,
> +                                  "btree node(ino=3D%llu) level=3D%d key=
=3D%llu not equal to parent's key=3D%llu",
> +                                  inode->i_ino, level, key2, key1);
> +                       return 1;
> +               }
> +       }
> +
>         return 0;
>  }
>
> @@ -582,7 +612,7 @@ static int nilfs_btree_do_lookup(const struct nilfs_b=
map *btree,
>                         return ret;
>
>                 node =3D 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 =3D nilfs_btree_node_lookup(node, key, &ind=
ex);
> @@ -630,7 +660,7 @@ static int nilfs_btree_do_lookup_last(const struct ni=
lfs_bmap *btree,
>                 if (ret < 0)
>                         return ret;
>                 node =3D 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 =3D nilfs_btree_node_get_nchildren(node) - 1;
>                 ptr =3D nilfs_btree_node_get_ptr(node, index, ncmax);
> --
> 2.34.1

Hi, Wang Jianjian.

Thank you for proposing the patch.

Your patch checks for key consistency within B-tree nodes; however,
since this check is performed inside nilfs_btree_bad_node() - which is
called during every B-tree search - it imposes unnecessary overhead.

Could you please move the check to nilfs_btree_broken_node_block() instead?
That function performs the check only once when the B-tree node block is lo=
aded.

By leveraging the BH_nilfs_checked flag on the buffer head, once the
check is performed, it prevents redundant checks as long as the buffer
remains in the cache.

If a node becomes corrupted after being loaded into memory, that
indicates a bug in the B-tree implementation itself; therefore,
checking it on every lookup is unnecessary.

Note that nilfs_btree_get_block() does not currently take a path
argument, but how about passing the parent node's key to it for
checking purposes?

Also, regarding the check for whether keys in the B-tree node are
sorted: instead of calling nilfs_btree_node_get_key() for both keys in
each iteration, could you reuse the value of the previous key?

While the compiler might optimize this, failing to reuse a variable
that has already been accessed feels a bit counterintuitive.

One more minor point: since the conditions like "if (key1 <=3D key2)" is
an exceptional error case, please wrap it with the unlikely() macro.

Could you please revise your implementation based on these comments?

Thank you.
Ryusuke Konishi