Skip to contentSkip to conversation

btrfs: treat empty left leaf as corruption in push_leaf_left()

PATCH In review ZhengYuan Huang 2 participants 3 messages Apr 9 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 btrfs: treat empty left leaf as corruption in push_leaf_left()

[BUG]
A corrupted tree can leave a non-root leaf with 0 items linked from its parent. When btrfs_del_items() later tries to rebalance a right leaf into that left sibling, push_leaf_left() passes the empty leaf down and we hit:

kernel BUG at fs/btrfs/ctree.c:3388!

Oops: invalid opcode: 0000 [#1] SMP KASAN NOPTI
RIP: 0010:__push_leaf_left+0x11f8/0x1610 fs/btrfs/ctree.c:3388
Code: ff48c1ea 03803c02 000f85bd 00000048
Call Trace:
 push_leaf_left+0x3b3/0x540 fs/btrfs/ctree.c:3511
 btrfs_del_items+0x74d/0xf10 fs/btrfs/ctree.c:4541
 btrfs_del_csums+0x44d/0xa50 fs/btrfs/file-item.c:969
 do_free_extent_accounting fs/btrfs/extent-tree.c:2984 [inline]
 __btrfs_free_extent.isra.0+0xded/0x41d0 fs/btrfs/extent-tree.c:3372
 run_delayed_data_ref fs/btrfs/extent-tree.c:1599 [inline]
 run_one_delayed_ref fs/btrfs/extent-tree.c:1779 [inline]
 btrfs_run_delayed_refs_for_head fs/btrfs/extent-tree.c:1972 [inline]
 __btrfs_run_delayed_refs+0x86e/0x39a0 fs/btrfs/extent-tree.c:2047
 btrfs_run_delayed_refs+0x181/0x420 fs/btrfs/extent-tree.c:2159
 btrfs_commit_transaction+0xc9b/0x3d90 fs/btrfs/transaction.c:2211
 btrfs_sync_fs+0xf0/0x630 fs/btrfs/super.c:1057
 sync_fs_one_sb fs/sync.c:84 [inline]
 sync_fs_one_sb+0xf4/0x140 fs/sync.c:80
 __iterate_supers+0x1be/0x290 fs/super.c:923
 iterate_supers+0x24/0x40 fs/super.c:938
 ksys_sync+0xb4/0x160 fs/sync.c:104
 __do_sys_sync+0x13/0x20 fs/sync.c:113
 ...

[CAUSE]
push_leaf_left() only checks how much free space the left sibling has. An empty leaf has maximum free space, so it passes that test. The sibling key validation also skips empty leaves because there are no keys to compare, allowing the empty leaf to reach __push_leaf_left().

[FIX]
Detect an empty left sibling leaf in push_leaf_left() and treat it as tree corruption. Abort the transaction with -EUCLEAN before modifying either leaf, which avoids the BUG_ON() and matches how other unexpected btree states are handled in btrfs.

Fixes 87b29b208c6c ("Btrfs: properly check free space for tree balancing")
---
 fs/btrfs/ctree.c | 9 +++++++++
 1 file changed, 9 insertions(+)
fs/btrfs/ctree.c +9 -0
index 561658aca018..625aa2ab4c5b 100644
@@ -3486,6 +3486,15 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 		return PTR_ERR(left);
 
 	btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
+	/* An empty non-root leaf means the tree is corrupted. */
+	if (unlikely(btrfs_header_nritems(left) == 0)) {
+		btrfs_crit(left->fs_info,
+			   "empty left leaf at bytenr %llu while pushing from right leaf %llu",
+			   left->start, right->start);
+		ret = -EUCLEAN;
+		btrfs_abort_transaction(trans, ret);
+		goto out;
+	}
 
 	free_space = btrfs_leaf_free_space(left);
 	if (free_space < data_size) {
Signature · 1 line
2.43.0
#1 lore raw
Quoted 55 lines · ZhengYuan Huang

[BUG]
A corrupted tree can leave a non-root leaf with 0 items linked from its parent. When btrfs_del_items() later tries to rebalance a right leaf into that left sibling, push_leaf_left() passes the empty leaf down and we hit:

kernel BUG at fs/btrfs/ctree.c:3388!

Oops: invalid opcode: 0000 [#1] SMP KASAN NOPTI
RIP: 0010:__push_leaf_left+0x11f8/0x1610 fs/btrfs/ctree.c:3388
Code: ff48c1ea 03803c02 000f85bd 00000048
Call Trace:
  push_leaf_left+0x3b3/0x540 fs/btrfs/ctree.c:3511
  btrfs_del_items+0x74d/0xf10 fs/btrfs/ctree.c:4541
  btrfs_del_csums+0x44d/0xa50 fs/btrfs/file-item.c:969
  do_free_extent_accounting fs/btrfs/extent-tree.c:2984 [inline]
  __btrfs_free_extent.isra.0+0xded/0x41d0 fs/btrfs/extent-tree.c:3372
  run_delayed_data_ref fs/btrfs/extent-tree.c:1599 [inline]
  run_one_delayed_ref fs/btrfs/extent-tree.c:1779 [inline]
  btrfs_run_delayed_refs_for_head fs/btrfs/extent-tree.c:1972 [inline]
  __btrfs_run_delayed_refs+0x86e/0x39a0 fs/btrfs/extent-tree.c:2047
  btrfs_run_delayed_refs+0x181/0x420 fs/btrfs/extent-tree.c:2159
  btrfs_commit_transaction+0xc9b/0x3d90 fs/btrfs/transaction.c:2211
  btrfs_sync_fs+0xf0/0x630 fs/btrfs/super.c:1057
  sync_fs_one_sb fs/sync.c:84 [inline]
  sync_fs_one_sb+0xf4/0x140 fs/sync.c:80
  __iterate_supers+0x1be/0x290 fs/super.c:923
  iterate_supers+0x24/0x40 fs/super.c:938
  ksys_sync+0xb4/0x160 fs/sync.c:104
  __do_sys_sync+0x13/0x20 fs/sync.c:113
  ...

[CAUSE]
push_leaf_left() only checks how much free space the left sibling has. An empty leaf has maximum free space, so it passes that test. The sibling key validation also skips empty leaves because there are no keys to compare, allowing the empty leaf to reach __push_leaf_left().

[FIX]
Detect an empty left sibling leaf in push_leaf_left() and treat it as tree corruption. Abort the transaction with -EUCLEAN before modifying either leaf, which avoids the BUG_ON() and matches how other unexpected btree states are handled in btrfs.

Fixes 87b29b208c6c ("Btrfs: properly check free space for tree balancing")
---
  fs/btrfs/ctree.c | 9 +++++++++
  1 file changed, 9 insertions(+)
fs/btrfs/ctree.c +0 -0
index 561658aca018..625aa2ab4c5b 100644
@@ -3486,6 +3486,15 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
  		return PTR_ERR(left);
 

fs/btrfs/ctree.c static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root · line 3497

Quoted 10 lines
fs/btrfs/ctree.c +9 -0
  	btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
+	/* An empty non-root leaf means the tree is corrupted. */
+	if (unlikely(btrfs_header_nritems(left) == 0)) {
+		btrfs_crit(left->fs_info,
+			   "empty left leaf at bytenr %llu while pushing from right leaf %llu",
+			   left->start, right->start);
+		ret = -EUCLEAN;
+		btrfs_abort_transaction(trans, ret);
+		goto out;
+	}

I think the timing is too late, and if there is an non-root empty leaf but we never modified it, kernel will not detect it.

I'd recommend to reject such empty leaves at btrfs_validate_extent_buffer(), if we have check->has_first_key, then the leaf should not be empty.

Thanks,
Qu

Quoted 3 lines
fs/btrfs/ctree.c +0 -0
  	free_space = btrfs_leaf_free_space(left);
  	if (free_space < data_size) {
#2 lore raw
Quoted 12 lines · Qu Wenruo

I think the timing is too late, and if there is an non-root empty leaf but we never modified it, kernel will not detect it.

I'd recommend to reject such empty leaves at btrfs_validate_extent_buffer(), if we have check->has_first_key, then the leaf should not be empty.

Thanks,
Qu

Quoted 3 lines
      free_space = btrfs_leaf_free_space(left);
      if (free_space < data_size) {

Thanks for your suggestion. That makes sense.

I will send a v2 patch incorporating this change.

Thanks,
ZhengYuan Huang