INFO: task hung in hfsplus_write_inode
Subsystems (2)
Dear Linux kernel developers and maintainers,
We are writing to report a task hung issue discovered in the hfsplus subsystem with our modified syzkaller. This issue
is reproducible on the latest version of linux (v7.1, commit 8cd9520d35a6c38db6567e97dd93b1f11f185dc6). Below is the relevant part of the kernel console log formatted by syz-symbolize and our root cause analysis:
---
INFO: task kworker/u10:3:63 blocked for more than 147 seconds.
Not tainted 7.1.0 #2"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/u10:3 state:D
stack:22456 pid:63 tgid:63 ppid:2 task_flags:0x4208060
flags:0x00080000
Workqueue: writeback wb_workfn
(flush-7:4)
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5388 [inline]
__schedule+0x177f/0x56c0 kernel/sched/core.c:7189
__schedule_loop kernel/sched/core.c:7268 [inline]
schedule+0x165/0x360 kernel/sched/core.c:7283
schedule_preempt_disabled+0x13/0x30 kernel/sched/core.c:7340
__mutex_lock_common kernel/locking/mutex.c:726 [inline]
__mutex_lock+0x819/0x1680 kernel/locking/mutex.c:820
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
write_inode fs/fs-writeback.c:1584 [inline]
__writeback_single_inode+0x75a/0x10f0 fs/fs-writeback.c:1827
writeback_sb_inodes+0x913/0x1910 fs/fs-writeback.c:2056
__writeback_inodes_wb+0x111/0x240 fs/fs-writeback.c:2132
wb_writeback+0x43f/0xae0 fs/fs-writeback.c:2243
wb_check_old_data_flush fs/fs-writeback.c:2347 [inline]
wb_do_writeback fs/fs-writeback.c:2400 [inline]
wb_workfn+0xaf2/0xef0 fs/fs-writeback.c:2428
process_one_work kernel/workqueue.c:3314 [inline]
process_scheduled_works+0xb4b/0x1840 kernel/workqueue.c:3397
worker_thread+0xa54/0xfc0 kernel/workqueue.c:3478
kthread+0x38a/0x480 kernel/kthread.c:436
ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158
ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245
</TASK>
INFO: task kworker/u10:7:181 blocked for more than 149 seconds.
Not tainted 7.1.0 #2"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/u10:7 state:D
stack:23848 pid:181 tgid:181 ppid:2 task_flags:0x4208060
flags:0x00080000
Workqueue: writeback wb_workfn
(flush-7:5)
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5388 [inline]
__schedule+0x177f/0x56c0 kernel/sched/core.c:7189
__schedule_loop kernel/sched/core.c:7268 [inline]
schedule+0x165/0x360 kernel/sched/core.c:7283
schedule_preempt_disabled+0x13/0x30 kernel/sched/core.c:7340
__mutex_lock_common kernel/locking/mutex.c:726 [inline]
__mutex_lock+0x819/0x1680 kernel/locking/mutex.c:820
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
write_inode fs/fs-writeback.c:1584 [inline]
__writeback_single_inode+0x75a/0x10f0 fs/fs-writeback.c:1827
writeback_sb_inodes+0x913/0x1910 fs/fs-writeback.c:2056
__writeback_inodes_wb+0x111/0x240 fs/fs-writeback.c:2132
wb_writeback+0x43f/0xae0 fs/fs-writeback.c:2243
wb_check_old_data_flush fs/fs-writeback.c:2347 [inline]
wb_do_writeback fs/fs-writeback.c:2400 [inline]
wb_workfn+0xaf2/0xef0 fs/fs-writeback.c:2428
process_one_work kernel/workqueue.c:3314 [inline]
process_scheduled_works+0xb4b/0x1840 kernel/workqueue.c:3397
worker_thread+0xa54/0xfc0 kernel/workqueue.c:3478
kthread+0x38a/0x480 kernel/kthread.c:436
ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158
ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245
</TASK>
INFO: task kworker/u9:2:202 blocked for more than 150 seconds.
Not tainted 7.1.0 #2"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/u9:2 state:D
stack:22312 pid:202 tgid:202 ppid:2 task_flags:0x4208060
flags:0x00080000
Workqueue: writeback wb_workfn
(flush-7:7)
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5388 [inline]
__schedule+0x177f/0x56c0 kernel/sched/core.c:7189
__schedule_loop kernel/sched/core.c:7268 [inline]
schedule+0x165/0x360 kernel/sched/core.c:7283
schedule_preempt_disabled+0x13/0x30 kernel/sched/core.c:7340
__mutex_lock_common kernel/locking/mutex.c:726 [inline]
__mutex_lock+0x819/0x1680 kernel/locking/mutex.c:820
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
write_inode fs/fs-writeback.c:1584 [inline]
__writeback_single_inode+0x75a/0x10f0 fs/fs-writeback.c:1827
writeback_sb_inodes+0x913/0x1910 fs/fs-writeback.c:2056
__writeback_inodes_wb+0x111/0x240 fs/fs-writeback.c:2132
wb_writeback+0x43f/0xae0 fs/fs-writeback.c:2243
wb_check_old_data_flush fs/fs-writeback.c:2347 [inline]
wb_do_writeback fs/fs-writeback.c:2400 [inline]
wb_workfn+0xaf2/0xef0 fs/fs-writeback.c:2428
process_one_work kernel/workqueue.c:3314 [inline]
process_scheduled_works+0xb4b/0x1840 kernel/workqueue.c:3397
worker_thread+0xa54/0xfc0 kernel/workqueue.c:3478
kthread+0x38a/0x480 kernel/kthread.c:436
ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158
ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245
</TASK>
INFO: task kworker/u9:3:609 blocked for more than 150 seconds.
Not tainted 7.1.0 #2
"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/u9:3 state:D stack:24344 pid:609 tgid:609 ppid:2
task_flags:0x4208060 flags:0x00080000
Workqueue: writeback wb_workfn (flush-7:0)
Call Trace:
<TASK>
context_switch kernel/sched/core.c:5388 [inline]
__schedule+0x177f/0x56c0 kernel/sched/core.c:7189
__schedule_loop kernel/sched/core.c:7268 [inline]
schedule+0x165/0x360 kernel/sched/core.c:7283
schedule_preempt_disabled+0x13/0x30 kernel/sched/core.c:7340
__mutex_lock_common kernel/locking/mutex.c:726 [inline]
__mutex_lock+0x819/0x1680 kernel/locking/mutex.c:820
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
write_inode fs/fs-writeback.c:1584 [inline]
__writeback_single_inode+0x75a/0x10f0 fs/fs-writeback.c:1827
writeback_sb_inodes+0x913/0x1910 fs/fs-writeback.c:2056
__writeback_inodes_wb+0x111/0x240 fs/fs-writeback.c:2132
wb_writeback+0x43f/0xae0 fs/fs-writeback.c:2243
wb_check_old_data_flush fs/fs-writeback.c:2347 [inline]
wb_do_writeback fs/fs-writeback.c:2400 [inline]
wb_workfn+0xaf2/0xef0 fs/fs-writeback.c:2428
process_one_work kernel/workqueue.c:3314 [inline]
process_scheduled_works+0xb4b/0x1840 kernel/workqueue.c:3397
worker_thread+0xa54/0xfc0 kernel/workqueue.c:3478
kthread+0x38a/0x480 kernel/kthread.c:436
ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158
ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245
</TASK>
INFO: task kworker/u9:5:1845 blocked for more than 151 seconds.
Not tainted 7.1.0 #2"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/u9:5 state:D
stack:26024 pid:1845 tgid:1845 ppid:2 task_flags:0x4208060
flags:0x00080000
Workqueue: writeback wb_workfn (flush-7:2) Call Trace: <TASK> context_switch kernel/sched/core.c:5388 [inline] __schedule+0x177f/0x56c0 kernel/sched/core.c:7189 __schedule_loop kernel/sched/core.c:7268 [inline] schedule+0x165/0x360 kernel/sched/core.c:7283 schedule_preempt_disabled+0x13/0x30 kernel/sched/core.c:7340 __mutex_lock_common kernel/locking/mutex.c:726 [inline] __mutex_lock+0x819/0x1680 kernel/locking/mutex.c:820 hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline] hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185 write_inode fs/fs-writeback.c:1584 [inline] __writeback_single_inode+0x75a/0x10f0 fs/fs-writeback.c:1827 writeback_sb_inodes+0x913/0x1910 fs/fs-writeback.c:2056 __writeback_inodes_wb+0x111/0x240 fs/fs-writeback.c:2132 wb_writeback+0x43f/0xae0 fs/fs-writeback.c:2243 wb_check_old_data_flush fs/fs-writeback.c:2347 [inline] wb_do_writeback fs/fs-writeback.c:2400 [inline] wb_workfn+0xaf2/0xef0 fs/fs-writeback.c:2428 process_one_work kernel/workqueue.c:3314 [inline] process_scheduled_works+0xb4b/0x1840 kernel/workqueue.c:3397 worker_thread+0xa54/0xfc0 kernel/workqueue.c:3478 kthread+0x38a/0x480 kernel/kthread.c:436 ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158 ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245 </TASK> Showing all locks held in the system: 2 locks held by kworker/0:1/10: #0:
ffff88802b83b0e0 (&rq->__lock
){-.-.}-{2:2}
, at: raw_spin_rq_lock_nested+0x31/0x150 kernel/sched/core.c:652
#1:ffff88802b824588
(psi_seq
){-.-.}-{0:0}
, at: psi_task_switch+0x53/0x880 kernel/sched/psi.c:933
4 locks held by kworker/u9:0/26:
#0:ffff888041ec7940
(
(wq_completion)writeback
){+.+.}-{0:0}
, at: process_one_work kernel/workqueue.c:3289 [inline]
, at: process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1:ffffc900004dfc40
(
(work_completion)(&(&wb->dwork)->work)
){+.+.}-{0:0}
, at: process_one_work kernel/workqueue.c:3290 [inline]
, at: process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2:ffff8880213180d8
(&type->s_umount_key
#54
){.+.+}-{4:4}
, at: super_trylock_shared+0x20/0xf0 fs/super.c:565
#3:ffff88802a52c0a8
(&tree->tree_lock
){+.+.}-{4:4}
, at: hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
, at: hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u9:1/34:
#0:ffff888041ec7940
(
(wq_completion)writeback
){+.+.}-{0:0}
, at: process_one_work kernel/workqueue.c:3289 [inline]
, at: process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1:ffffc9000056fc40
(
(work_completion)(&(&wb->dwork)->work)
){+.+.}-{0:0}, at: process_one_work kernel/workqueue.c:3290 [inline] ){+.+.}-{0:0}, at: process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff88804746e0d8
(&type->s_umount_key
#54
){.+.+}-{4:4}
, at: super_trylock_shared+0x20/0xf0 fs/super.c:565
#3:ffff88801ff680a8
(&tree->tree_lock
){+.+.}-{4:4}
, at: hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
, at: hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
1 lock held by khungtaskd/35:
#0:ffffffff8e55cce0
(rcu_read_lock
){....}-{1:3}
, at: rcu_lock_acquire include/linux/rcupdate.h:300 [inline]
, at: rcu_read_lock include/linux/rcupdate.h:838 [inline]
, at: debug_show_all_locks+0x2e/0x180 kernel/locking/lockdep.c:6775 4 locks held by kworker/u10:2/41:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}
, at: process_one_work kernel/workqueue.c:3289 [inline]
, at: process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1:ffffc900005dfc40
(
(work_completion)(&(&wb->dwork)->work)
){+.+.}-{0:0}, at: process_one_work kernel/workqueue.c:3290 [inline] ){+.+.}-{0:0}, at: process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff88804e05c0d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff888046b200a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff888046b200a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u10:3/63:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3289 [inline]
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1: ffffc90001087c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3290 [inline]
#1: ffffc90001087c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff88804f1aa0d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff888040ff20a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff888040ff20a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u10:7/181:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3289 [inline]
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1: ffffc900022f7c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3290 [inline]
#1: ffffc900022f7c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff8880476b00d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff88804f3ca0a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff88804f3ca0a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u9:2/202:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3289 [inline]
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1: ffffc900023a7c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3290 [inline]
#1: ffffc900023a7c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff8880259480d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff888020e000a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff888020e000a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u9:3/609:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3289 [inline]
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1: ffffc90003907c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3290 [inline]
#1: ffffc90003907c40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff888024b6c0d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff88801e4060a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff88801e4060a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
4 locks held by kworker/u9:5/1845:
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3289 [inline]
#0: ffff888041ec7940 ((wq_completion)writeback){+.+.}-{0:0}, at:
process_scheduled_works+0xa23/0x1840 kernel/workqueue.c:3397
#1: ffffc9000932fc40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_one_work kernel/workqueue.c:3290 [inline]
#1: ffffc9000932fc40
((work_completion)(&(&wb->dwork)->work)){+.+.}-{0:0}, at:
process_scheduled_works+0xa5e/0x1840 kernel/workqueue.c:3397
#2: ffff888024c000d8 (&type->s_umount_key#54){.+.+}-{4:4}, at:
super_trylock_shared+0x20/0xf0 fs/super.c:565
#3: ffff88802353a0a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_system_write_inode fs/hfsplus/super.c:156 [inline]
#3: ffff88802353a0a8 (&tree->tree_lock){+.+.}-{4:4}, at:
hfsplus_write_inode+0x54a/0x760 fs/hfsplus/super.c:185
6 locks held by syz-executor300/9385:
6 locks held by syz-executor300/9386:
7 locks held by syz-executor300/9389:
6 locks held by syz-executor300/9394:
6 locks held by syz-executor300/9399:
6 locks held by syz-executor300/9393:
6 locks held by syz-executor300/9398:
6 locks held by syz-executor300/9400:=============================================
NMI backtrace for cpu 1
CPU: 1 UID: 0 PID: 35 Comm: khungtaskd Not tainted 7.1.0 #2 PREEMPT(full) Hardware name: QEMU Ubuntu 24.04 PC v2 (i440FX + PIIX, arch_caps fix, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 Call Trace: <TASK> __dump_stack lib/dump_stack.c:94 [inline] dump_stack_lvl+0x10e/0x190 lib/dump_stack.c:120 nmi_cpu_backtrace+0x274/0x2d0 lib/nmi_backtrace.c:113 nmi_trigger_cpumask_backtrace+0x17a/0x300 lib/nmi_backtrace.c:62 trigger_all_cpu_backtrace include/linux/nmi.h:162 [inline] __sys_info lib/sys_info.c:157 [inline] sys_info+0x135/0x170 lib/sys_info.c:165 check_hung_uninterruptible_tasks kernel/hung_task.c:353 [inline] watchdog+0xfdf/0x1040 kernel/hung_task.c:561 kthread+0x38a/0x480 kernel/kthread.c:436 ret_from_fork+0x509/0xb70 arch/x86/kernel/process.c:158 ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245 </TASK> Sending NMI from CPU 1 to CPUs 0: NMI backtrace for cpu 0 CPU: 0 UID: 0 PID: 9389 Comm: syz-executor300 Not tainted 7.1.0 #2 PREEMPT(full) Hardware name: QEMU Ubuntu 24.04 PC v2 (i440FX + PIIX, arch_caps fix, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014 RIP: 0010:console_trylock_spinning kernel/printk/printk.c:2028 [inline] RIP: 0010:vprintk_emit+0x2f4/0x550 kernel/printk/printk.c:2478 Code: 43 8e 31 f6 31 d2 31 c9 41 b8 01 00 00 00 45 31 c9 53 e8 9f ec fc ff 48 83 c4 08 80 3d 84 e7 6a 18 00 0f 84 8b 00 00 00 f3 90 <80> 3d 75 e7 6a 18 00 0f 84 83 00 00 00 e8 1a f0 20 00 eb ea e8 13 RSP: 0018:ffffc9001104f520 EFLAGS: 00000093 RAX: ffffffff819a4dd6 RBX: ffffffff819a4d95 RCX: ffff888020565dc0 RDX: 0000000000000000 RSI: ffffffff8dd27add RDI: ffffffff8c089460 RBP: ffffc9001104f5d0 R08: 0000000000080000 R09: 0000000000000000 R10: 0000000000000000 R11: ffffffff819a4d95 R12: 0000000000000065 R13: 0000000000000000 R14: 0000000000000200 R15: ffffffff8bc7ef20 FS: 00007f8333f8a6c0(0000) GS:ffff8880988c3000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 00007f56f3c2c008 CR3: 00000000221af000 CR4: 0000000000752ef0 PKRU: 55555554 Call Trace: <TASK> _printk+0xcf/0x120 kernel/printk/printk.c:2504 hfsplus_bnode_read_u16 fs/hfsplus/bnode.c:60 [inline] hfsplus_bnode_dump+0x16b/0xa00 fs/hfsplus/bnode.c:362 hfsplus_brec_remove+0x61c/0x700 fs/hfsplus/brec.c:229 __hfsplus_delete_attr+0x1d4/0x400 fs/hfsplus/attributes.c:339 hfsplus_delete_all_attrs+0x1a8/0x330 fs/hfsplus/attributes.c:444 hfsplus_delete_cat+0x967/0xe50 fs/hfsplus/catalog.c:427 hfsplus_unlink+0x33f/0x910 fs/hfsplus/dir.c:406 vfs_unlink+0x272/0x6d0 fs/namei.c:5508 filename_unlinkat+0x3be/0x5f0 fs/namei.c:5578 __do_sys_unlinkat fs/namei.c:5607 [inline] __se_sys_unlinkat+0x83/0x1a0 fs/namei.c:5599 do_syscall_x64 arch/x86/entry/syscall_64.c:63 [inline] do_syscall_64+0x184/0x5c0 arch/x86/entry/syscall_64.c:94 entry_SYSCALL_64_after_hwframe+0x77/0x7f RIP: 0033:0x7f8333fbe15d Code: b3 66 2e 0f 1f 84 00 00 00 00 00 66 90 f3 0f 1e fa 48 89 f8 48
89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 b8 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007f8333f8a208 EFLAGS: 00000246 ORIG_RAX: 0000000000000107
RAX: ffffffffffffffda RBX: 00007f833406ad48 RCX: 00007f8333fbe15d
RDX: 0000000000000000 RSI: 00002000000002c0 RDI: 00000000ffffff9c
RBP: 00007f833406ad40 R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000246 R12: 0030656c69662f2e
R13: 0000200000000000 R14: 0073756c70736668 R15: 0000200000000600
</TASK>
---
Following is our root cause analysis, the analysis was assisted with LLM, but may not be entirely accurate:
The root cause of this issue is that the crafted image corrupts HFS+ B-tree node record offset table. The node descriptor can contain an on-disk num_recs value that does not fit in the node, and some record offsets can point backwards or into the offset table itself. Several HFS+ B-tree helpers trust these values too much.
Specifically:
1. hfs_bnode_dump() iterates over the on-disk record count without first checking whether (num_recs + 1) * sizeof(__be16) can fit after the node descriptor. With a corrupt count, the local off value can become negative and is then passed to hfs_bnode_read_u16(), whose offset argument is unsigned. This produces very large offsets and repeatedly prints messages like:
hfsplus: requested invalid offset: NODE: id 1, type 0xff, height 1, node_size 8192, offset 4294962872
2. hfs_brec_lenoff() computes the record length as next_off - off without validating them. On corrupt metadata this can underflow or describe data that overlaps the offset table.
3. hfs_brec_keylen(), __hfs_brec_find(), hfs_brec_goto() and hfs_brec_remove() can continue after an invalid/empty record description, which lets the unlink path reach the bad dump/remove logic.
As a result, the unlink path can spend a long time printing invalid-offset errors while operating under HFS+ B-tree locks. Other writeback workers then block on &tree->tree_lock, and the hung-task issue is triggered.
One potential fix is to reject malformed B-tree nodes and records earlier:
- validate num_recs against the node size before walking the record offset table;
- reject record offsets that are unordered, unaligned, outside the node, or overlapping the offset table;
- stop B-tree search/goto/remove paths when record length or key length is invalid;
- avoid decrementing an already-zero leaf count on malformed nodes.
With the following patch, the reproducer no longer triggers the hfsplus: requested invalid offset printk flood or the hung task issue.
```
diff --git a/fs/hfsplus/bfind.c b/fs/hfsplus/bfind.c
index 9a55fa6d5294..6ecb7e0442a0 100644
--- a/fs/hfsplus/bfind.c
+++ b/fs/hfsplus/bfind.c
@@ -112,11 +112,13 @@ int __hfs_brec_find(struct hfs_bnode *bnode,
struct hfs_find_data *fd,
b = 0;
e = bnode->num_recs - 1;
res = -ENOENT;
+ if (!bnode->num_recs)
+ return res;
do {
rec = (e + b) / 2;
len = hfs_brec_lenoff(bnode, rec, &off);
keylen = hfs_brec_keylen(bnode, rec);
- if (keylen == 0) {
+ if (!len || !keylen || keylen >= len) {
res = -EINVAL;
goto fail;
}
@@ -130,7 +132,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode,
struct hfs_find_data *fd,
if (rec != e && e >= 0) {
len = hfs_brec_lenoff(bnode, e, &off);
keylen = hfs_brec_keylen(bnode, e);
- if (keylen == 0) {
+ if (!len || !keylen || keylen >= len) {
res = -EINVAL;
goto fail;
}
@@ -232,6 +234,10 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
bnode = fd->bnode;
tree = bnode->tree;
+ if (!bnode->num_recs) {
+ res = -ENOENT;
+ goto out;
+ }
if (cnt < 0) {
cnt = -cnt;
@@ -274,7 +280,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len = hfs_brec_lenoff(bnode, fd->record, &off);
keylen = hfs_brec_keylen(bnode, fd->record);
- if (keylen == 0) {
+ if (!len || !keylen || keylen >= len) {
res = -EINVAL;
goto out;
}
diff --git a/fs/hfsplus/bnode.c b/fs/hfsplus/bnode.c
index f8b5a8ae58ff..03fda4c17d84 100644
--- a/fs/hfsplus/bnode.c
+++ b/fs/hfsplus/bnode.c
@@ -350,15 +350,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)
struct hfs_bnode_desc desc;
__be32 cnid;
int i, off, key_off;
+ u16 num_recs;
hfs_dbg("node %d\n", node->this);
hfs_bnode_read(node, &desc, 0, sizeof(desc));
+ num_recs = be16_to_cpu(desc.num_recs);
hfs_dbg("next %d, prev %d, type %d, height %d, num_recs %d\n",
be32_to_cpu(desc.next), be32_to_cpu(desc.prev),
- desc.type, desc.height, be16_to_cpu(desc.num_recs));
+ desc.type, desc.height, num_recs);
+
+ if (!hfs_bnode_num_recs_valid(node, num_recs)) {
+ hfs_dbg("invalid num_recs %u\n", num_recs);
+ return;
+ }
off = node->tree->node_size - 2;
- for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--) {
+ for (i = num_recs; i >= 0; off -= 2, i--) {
key_off = hfs_bnode_read_u16(node, off);
hfs_dbg(" key_off %d", key_off);
if (i && node->type == HFS_NODE_INDEX) {
@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree
*tree, u32 num)
goto node_error;
}
+ if (!hfs_bnode_num_recs_valid(node, node->num_recs))
+ goto node_error;
+
rec_off = tree->node_size - 2;
off = hfs_bnode_read_u16(node, rec_off);
if (off != sizeof(struct hfs_bnode_desc))
@@ -588,6 +598,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree
*tree, u32 num)
next_off = hfs_bnode_read_u16(node, rec_off);
if (next_off <= off ||
next_off > tree->node_size ||
+ next_off > rec_off ||
next_off & 1)
goto node_error;
entry_size = next_off - off;
diff --git a/fs/hfsplus/brec.c b/fs/hfsplus/brec.c
index e3df89284079..1b0053453a24 100644
--- a/fs/hfsplus/brec.c
+++ b/fs/hfsplus/brec.c
@@ -21,11 +21,26 @@ u16 hfs_brec_lenoff(struct hfs_bnode *node, u16
rec, u16 *off)
{
__be16 retval[2];
u16 dataoff;
+ u16 next_off;
+
+ if (rec >= node->num_recs ||
+ !hfs_bnode_num_recs_valid(node, node->num_recs)) {
+ *off = 0;
+ return 0;
+ }
dataoff = node->tree->node_size - (rec + 2) * 2;
hfs_bnode_read(node, retval, dataoff, 4);
*off = be16_to_cpu(retval[1]);
- return be16_to_cpu(retval[0]) - *off;
+ next_off = be16_to_cpu(retval[0]);
+ if (*off < sizeof(struct hfs_bnode_desc) ||
+ *off & 1 ||
+ next_off <= *off ||
+ next_off > node->tree->node_size ||
+ next_off > dataoff ||
+ next_off & 1)
+ return 0;
+ return next_off - *off;
}
/* Get the length of the key from a keyed record */
@@ -35,6 +50,9 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
return 0;
+ if (rec >= node->num_recs ||
+ !hfs_bnode_num_recs_valid(node, node->num_recs))
+ return 0;
if ((node->type == HFS_NODE_INDEX) &&
!(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
@@ -43,7 +61,7 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
} else {
recoff = hfs_bnode_read_u16(node,
node->tree->node_size - (rec + 1) * 2);
- if (!recoff)
+ if (recoff < sizeof(struct hfs_bnode_desc) || recoff & 1)
return 0;
if (recoff > node->tree->node_size - 2) {
pr_err("recoff %d too large\n", recoff);
@@ -185,10 +203,17 @@ int hfs_brec_remove(struct hfs_find_data *fd)
tree = fd->tree;
node = fd->bnode;
again:
+ if (fd->record < 0 ||
+ fd->record >= node->num_recs ||
+ !hfs_bnode_num_recs_valid(node, node->num_recs))
+ return -EIO;
+
rec_off = tree->node_size - (fd->record + 2) * 2;
end_off = tree->node_size - (node->num_recs + 1) * 2;
if (node->type == HFS_NODE_LEAF) {
+ if (!tree->leaf_count)
+ return -EIO;
tree->leaf_count--;
mark_inode_dirty(tree->inode);
}
diff --git a/fs/hfsplus/hfsplus_fs.h b/fs/hfsplus/hfsplus_fs.h
index 3545b8dbf11c..5710add1650a 100644
--- a/fs/hfsplus/hfsplus_fs.h
+++ b/fs/hfsplus/hfsplus_fs.h
@@ -590,6 +590,24 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off)
return is_valid;
}
+static inline
+bool hfs_bnode_num_recs_valid(struct hfs_bnode *node, u16 num_recs)
+{
+ u32 node_size;
+ u32 offs_size;
+
+ if (!node || !node->tree)
+ return false;
+
+ node_size = node->tree->node_size;
+ if (node_size < sizeof(struct hfs_bnode_desc) + sizeof(__be16))
+ return false;
+
+ offs_size = ((u32)num_recs + 1) * sizeof(__be16);
+
+ return offs_size <= node_size - sizeof(struct hfs_bnode_desc);
+}
+
static inline
u32 check_and_correct_requested_length(struct hfs_bnode *node, u32
off, u32 len)
{
```If this solution is acceptable, we are happy to submit a patch.
The kernel console output, kernel config, syzkaller reproducer, and C reproducer are also available at google drive:
https://drive.google.com/drive/folders/1jxQNoUg-phb14qPT6DnfC433dkkRwznj?usp=sharing
Please let me know if any further information is required.
Best Regards,
Jiaming Zhang
Quoted 4 lines · Jiaming Zhang
Dear Linux kernel developers and maintainers,
We are writing to report a task hung issue discovered in the hfsplus subsystem with our modified syzkaller. This issue
Do not try to be syzbot. You are not good at it. Please get your syzkaller modifications upstream and then let syzbot take care of the rest.
Viacheslav Dubeyko
maintainerQuoted 1 line · Jiaming Zhang
<skipped>
Quoted 3 lines
If this solution is acceptable, we are happy to submit a patch.
If you believe that you have a fix of the issue, then, please, send the formal patch for review.
Thanks,
Slava.
PATCH 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Reject corrupted B-tree metadata earlier: validate num_recs against the node size before walking the record offset table, reject record offsets that are unordered, unaligned, outside the node, or overlapping the offset table, stop B-tree record walkers on invalid records, and avoid decrementing an already-zero leaf_count.
--- fs/hfsplus/bfind.c | 12 +++++++++--- fs/hfsplus/bnode.c | 15 +++++++++++++-- fs/hfsplus/brec.c | 35 ++++++++++++++++++++++++++++++----- fs/hfsplus/hfsplus_fs.h | 18 ++++++++++++++++++ 4 files changed, 70 insertions(+), 10 deletions(-)
fs/hfsplus/bfind.c +9 -3
@@ -112,11 +112,13 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, b =0 ; e = bnode->num_recs -1 ; res = -ENOENT ; +if (!bnode->num_recs) +return res; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (!keylen || keylen >= len) { res = -EINVAL; goto fail; }
@@ -130,7 +132,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,if (rec != e && e >=0 ) { len =hfs_brec_lenoff (bnode, e, &off); keylen =hfs_brec_keylen (bnode, e); -if (keylen ==0 ) { +if (!keylen || keylen >= len) { res = -EINVAL ; goto fail; }
@@ -232,6 +234,10 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) bnode = fd->bnode; tree = bnode->tree; +if (!bnode->num_recs) { + res = -ENOENT ; + goto out; + }if (cnt <0 ) { cnt = -cnt;
@@ -274,7 +280,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) len =hfs_brec_lenoff (bnode, fd->record, &off); keylen =hfs_brec_keylen (bnode, fd->record); -if (keylen ==0 ) { +if (!keylen || keylen >= len) { res = -EINVAL ; goto out; }
fs/hfsplus/bnode.c +13 -2
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs =be16_to_cpu (desc.num_recs);hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), - desc.type, desc.height,be16_to_cpu (desc.num_recs)); + desc.type, desc.height, num_recs); + +if (!hfs_bnode_num_recs_valid (node, num_recs)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; } +if (!hfs_bnode_num_recs_valid (node, node->num_recs)) + goto node_error; + rec_off = tree->node_size -2 ; off =hfs_bnode_read_u16 (node, rec_off);if (off !=sizeof (struct hfs_bnode_desc ))
@@ -588,6 +598,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) next_off =hfs_bnode_read_u16 (node, rec_off);if (next_off <= off || next_off > tree->node_size || + next_off > rec_off || next_off &1 ) goto node_error; entry_size = next_off - off;
fs/hfsplus/brec.c +30 -5
@@ -20,12 +20,27 @@ static int hfs_btree_inc_height(struct hfs_btree *);u16 hfs_brec_lenoff (struct hfs_bnode *node,u16 rec,u16 *off) {__be16 retval[2 ]; -u16 dataoff; +u16 data_off; +u16 next_off; - dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (rec >= node->num_recs || + !hfs_bnode_num_recs_valid (node, node->num_recs)) { + *off =0 ; +return 0 ; + } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 ); *off =be16_to_cpu (retval[1 ]); -return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (*off <sizeof (struct hfs_bnode_desc ) || + *off &1 || + next_off <= *off || + next_off > node->tree->node_size || + next_off > data_off || + next_off &1 ) +return 0 ; +return next_off - *off; }/* Get the length of the key from a keyed record */
@@ -35,6 +50,9 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)if (node->type !=HFS_NODE_INDEX && node->type !=HFS_NODE_LEAF )return 0 ; +if (rec >= node->num_recs || + !hfs_bnode_num_recs_valid (node, node->num_recs)) +return 0 ; if ((node->type == HFS_NODE_INDEX) && !(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
@@ -43,7 +61,7 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) }else { recoff =hfs_bnode_read_u16 (node, node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) +if (recoff <sizeof (struct hfs_bnode_desc ) || recoff &1 )return 0 ;if (recoff > node->tree->node_size -2 ) {pr_err ("recoff %d too large\n" , recoff);
@@ -185,10 +203,17 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode; again: +if (fd->record <0 || + fd->record >= node->num_recs || + !hfs_bnode_num_recs_valid (node, node->num_recs)) +return -EIO ; + rec_off = tree->node_size - (fd->record +2 ) *2 ; end_off = tree->node_size - (node->num_recs +1 ) *2 ;if (node->type ==HFS_NODE_LEAF ) { +if (!tree->leaf_count) +return -EIO ; tree->leaf_count--;mark_inode_dirty (tree->inode); }
fs/hfsplus/hfsplus_fs.h +18 -0
@@ -587,6 +587,24 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off)return is_valid; } +static inline +bool hfs_bnode_num_recs_valid (struct hfs_bnode *node,u16 num_recs) +{ +u32 node_size; +u32 offs_size; + +if (!node || !node->tree) +return false; + + node_size = node->tree->node_size; +if (node_size <sizeof (struct hfs_bnode_desc ) +sizeof (__be16)) +return false; + + offs_size = ((u32 )num_recs +1 ) *sizeof (__be16); + +return offs_size <= node_size -sizeof (struct hfs_bnode_desc ); +} +static inline u32 check_and_correct_requested_length (struct hfs_bnode *node,u32 off,u32 len) {
Signature · 1 line
2.43.0
Viacheslav Dubeyko
maintainerRe: [PATCH] hfsplus: validate B-tree record offset table
Quoted 51 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor
may contain a record count that does not fit in the node, and record offsets may
be unordered, unaligned, outside the node, or point into the offset table
itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly
callhfs_bnode_read_u16()with invalid offsets while holding the HFS+ B-tree
lock, producing a flood of "requested invalid offset" messages. Other writeback
workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Reject corrupted B-tree metadata earlier: validate
num_recsagainst the node
size before walking the record offset table, reject record offsets that are
unordered, unaligned, outside the node, or overlapping the offset table, stop
B-tree record walkers on invalid records, and avoid decrementing an already-zeroleaf_count.Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
fs/hfsplus/bfind.c | 12 +++++++++--- fs/hfsplus/bnode.c | 15 +++++++++++++-- fs/hfsplus/brec.c | 35 ++++++++++++++++++++++++++++++-----fs/hfsplus/hfsplus_fs.h| 18 ++++++++++++++++++4 files changed, 70 insertions(+), 10 deletions(-)fs/hfsplus/bfind.c +0
-0
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, · line 116
Quoted 5 lines
fs/hfsplus/bfind.c +1
-0@@ -112,11 +112,13 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, b = 0; e = bnode->num_recs - 1; res = -ENOENT; +if (!bnode->num_recs)
Do you mean bnode->num_recs == 0?
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, · line 116
Quoted 1 line
fs/hfsplus/bfind.c +1
-0+return res;
In majority of cases, we check fd->record:
__hfs_brec_find(parent, fd, hfs_find_rec_by_key); if (fd->record < 0) return -ENOENT;
So, this is not completely correct to simply return error because, we do not check the returned error code.
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, · line 121
Quoted 6 lines
fs/hfsplus/bfind.c +1
-1do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (!keylen || keylen >= len) {
I really dislike this !keylen pattern is used not for pointer. Should we expect that that keylen == len? Then, we could use keylen != len here.
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, · line 136
Quoted 10 lines
fs/hfsplus/bfind.c +0
-0res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +1
-1@@ -130,7 +132,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (!keylen || keylen >= len) {
Ditto.
fs/hfsplus/bfind.c int hfs_brec_goto(struct hfs_find_data *fd, int cnt) · line 237
Quoted 9 lines
fs/hfsplus/bfind.c +0
-0res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +0
-0@@ -232,6 +234,10 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
bnode =fd->bnode;
tree =bnode->tree;fs/hfsplus/bfind.c +1
-0+if (!bnode->num_recs) {
I dislike this !bnode->num_recs.
fs/hfsplus/bfind.c
Quoted 13 lines
fs/hfsplus/bfind.c +3
-0+ res = -ENOENT ; + goto out; + }
if (cnt < 0) {
cnt = -cnt;fs/hfsplus/bfind.c +0
-0@@ -274,7 +280,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +1
-1-if (keylen ==0 ) { +if (!keylen || keylen >= len) {
Ditto.
Quoted 67 lines
res =
-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs =be16_to_cpu (desc.num_recs);hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev),fs/hfsplus/bnode.c +6
-1- desc.type, desc.height, be16_to_cpu(desc.num_recs)); + desc.type, desc.height, num_recs); + +if (!hfs_bnode_num_recs_valid (node, num_recs)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + }
off =node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; }fs/hfsplus/bnode.c +3
-0+if (!hfs_bnode_num_recs_valid (node, node->num_recs)) + goto node_error; +
rec_off=tree->node_size- 2;
off =hfs_bnode_read_u16(node, rec_off);
if (off !=sizeof(struct hfs_bnode_desc))fs/hfsplus/bnode.c +0
-0@@ -588,6 +598,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) next_off = hfs_bnode_read_u16(node, rec_off);if (
next_off<= off ||
next_off>tree->node_size||fs/hfsplus/bnode.c +1
-0+ next_off > rec_off ||
next_off& 1)
gotonode_error;
entry_size=next_off- off;fs/hfsplus/brec.c +2
-1@@ -20,12 +20,27 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off;
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 27
Quoted 4 lines
fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (rec >= node->num_recs || + !hfs_bnode_num_recs_valid (node, node->num_recs)) {
Ditto. We need static inline function for such check that can be reused in multiple places.
Quoted 7 lines
fs/hfsplus/brec.c +6
-0+ *off =0 ; +return 0 ; + } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 41
Quoted 8 lines
fs/hfsplus/brec.c +7
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (*off <sizeof (struct hfs_bnode_desc ) || + *off &1 || + next_off <= *off || + next_off > node->tree->node_size || + next_off > data_off || + next_off &1 )
It looks like a static inline function for the check. I dislike such multi-line check logic.
fs/hfsplus/brec.c u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) · line 54
Quoted 13 lines
fs/hfsplus/brec.c +2
-0+return 0 ; +return next_off - *off;}
/* Get the length of the key from a keyed record */fs/hfsplus/brec.c +0
-0@@ -35,6 +50,9 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (rec >= node->num_recs || + !hfs_bnode_num_recs_valid (node, node->num_recs))
Ditto.
fs/hfsplus/brec.c u16 hfs_brec_keylen(struct hfs_bnode *node, u16 · line 66
Quoted 12 lines
fs/hfsplus/brec.c +1
-0+return 0 ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) &&fs/hfsplus/brec.c +1
-1@@ -43,7 +61,7 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec) } else { recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); -if (!recoff) +if (recoff <sizeof (struct hfs_bnode_desc ) || recoff &1 )
I don't quite follow what this check means. Could we rework it somehow?
fs/hfsplus/brec.c int hfs_brec_remove(struct hfs_find_data *fd) · line 207
Quoted 9 lines
fs/hfsplus/brec.c +0
-0return 0;if (recoff >
node->tree->node_size- 2) {pr_err("recoff %d too large\n", recoff);fs/hfsplus/brec.c +0
-0@@ -185,10 +203,17 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode;again:
fs/hfsplus/brec.c +2
-0+ if (fd->record < 0 || + fd->record >= node->num_recs ||
I think it makes sense to call hfs_bnode_num_recs_valid() before checking fd->record.
fs/hfsplus/brec.c
Quoted 1 line
fs/hfsplus/brec.c +1
-0+ !hfs_bnode_num_recs_valid(node, node->num_recs))
It looks like method of fd->record. I suggest to introduce static inline method of fd->record. Could we reuse this method for another cases?
fs/hfsplus/brec.c int hfs_brec_remove(struct hfs_find_data *fd) · line 215
Quoted 7 lines
fs/hfsplus/brec.c +2
-0+return -EIO ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +1
-0+if (!tree->leaf_count)
Ditto. I dislike this !tree->leaf_count pattern.
Quoted 13 lines
fs/hfsplus/brec.c +1
-0+return -EIO ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,24 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 591
Quoted 2 lines
fs/hfsplus/hfsplus_fs.h +2
-0+static inline +bool hfs_bnode_num_recs_valid (struct hfs_bnode *node,u16 num_recs)
What the point to provide num_recs? You can access it by node-
Quoted 11 lines
num_recs.fs/hfsplus/hfsplus_fs.h +9
-0+{ + u32 node_size; + u32 offs_size; + + if (!node || !node->tree) + return false; + + node_size = node->tree->node_size; + if (node_size < sizeof(struct hfs_bnode_desc) +
Quoted 1 line
sizeof(__be16))
You use sizeof(__be16) several times. Also, nobody can follow why you need to make this addition. So, you need to introduce the local variable with good name.
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 603
Quoted 3 lines
fs/hfsplus/hfsplus_fs.h +3
-0+return false; + + offs_size = ((u32 )num_recs +1 ) *sizeof (__be16);
Ditto.
Quoted 3 lines
fs/hfsplus/hfsplus_fs.h +2
-0+ + return offs_size <= node_size - sizeof(struct
hfs_bnode_desc);
It cannot cover all potential corruptions. Because, offs_size could be smaller one but still to overlap with node's content.
Thanks,
Slava.
Quoted 6 lines
fs/hfsplus/hfsplus_fs.h +2
-0+} +static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
v2 cover hfsplus: validate B-tree record offset table
Hi Viacheslav,
Thanks for the review.
This v2 addresses your comments on the first version.
hfs_bnode_num_recs_valid() takes only struct hfs_bnode and uses node->num_recs directly. I also introduce local variables around the record offset table size, hope this make the calculation easy to understand.
The repeated record index checks are now moved into hfs_brec_record_valid(), and the record offset checks are moved into hfs_brec_range_valid(). The range helper checks offset order, alignment, node bounds, and that record data does not overlap the record offset table.
I also make fd->record and related fields invalid when __hfs_brec_find() failed, and change hfs_brec_keylen() to use hfs_brec_lenoff() for the validated record start.
Note that I kept the key length check as "keylen == 0 || keylen >= len". I think the length returned by hfs_brec_lenoff() is one record in a B-tree node, and keylen is the key portion, the remaining bytes are the record payload. If I am right, "keylen == len" would mean an empty payload and should be rejected, right?
Changes since v1:
- Use explicit zero comparisons for integer fields.
- Only use node as parameter of hfs_bnode_num_recs_valid().
- Add hfs_brec_record_valid() for record index validation.
- Add hfs_brec_range_valid() for per-record offset validation.
- Reject record ranges that overlap the record offset table.
- Preserve invalid fd fields when __hfs_brec_find() fails.
- Change hfs_brec_keylen() to reuse hfs_brec_lenoff().
Jiaming Zhang (1):
hfsplus: validate B-tree record offset table
fs/hfsplus/bfind.c | 27 ++++++++++++++++-- fs/hfsplus/bnode.c | 16 ++++++++--- fs/hfsplus/brec.c | 37 +++++++++++++++--------- fs/hfsplus/hfsplus_fs.h | 62 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 122 insertions(+), 20 deletions(-)
Signature · 1 line
2.43.0
PATCH v2 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Reject corrupted B-tree metadata earlier: validate num_recs against the node size before walking the record offset table, reject record offsets that are unordered, unaligned, outside the node, or overlapping the offset table, stop B-tree record walkers on invalid records, and avoid decrementing an already-zero leaf_count.
--- fs/hfsplus/bfind.c | 27 ++++++++++++++++-- fs/hfsplus/bnode.c | 16 ++++++++--- fs/hfsplus/brec.c | 37 +++++++++++++++--------- fs/hfsplus/hfsplus_fs.h | 62 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 122 insertions(+), 20 deletions(-)
fs/hfsplus/bfind.c +24 -3
@@ -108,15 +108,28 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,int b, e;int res; + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +BUG_ON (!rec_found); +if (!hfs_bnode_num_recs_valid (bnode)) { + res = -EIO ; + goto fail; + } + b =0 ; e = bnode->num_recs -1 ; res = -ENOENT ; +if (bnode->num_recs ==0 ) + goto fail; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (keylen == 0 || keylen >= len) { res = -EINVAL; goto fail; }
@@ -130,7 +143,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,if (rec != e && e >=0 ) { len =hfs_brec_lenoff (bnode, e, &off); keylen =hfs_brec_keylen (bnode, e); -if (keylen ==0 ) { +if (keylen ==0 || keylen >= len) { res = -EINVAL ; goto fail; }
@@ -232,6 +245,14 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) bnode = fd->bnode; tree = bnode->tree; +if (!hfs_bnode_num_recs_valid (bnode)) { + res = -EIO ; + goto out; + } +if (bnode->num_recs ==0 ) { + res = -ENOENT ; + goto out; + }if (cnt <0 ) { cnt = -cnt;
@@ -274,7 +295,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) len =hfs_brec_lenoff (bnode, fd->record, &off); keylen =hfs_brec_keylen (bnode, fd->record); -if (keylen ==0 ) { +if (keylen ==0 || keylen >= len) { res = -EINVAL ; goto out; }
fs/hfsplus/bnode.c +12 -4
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs = node->num_recs;hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), desc.type, desc.height,be16_to_cpu (desc.num_recs)); +if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } + off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; } +if (!hfs_bnode_num_recs_valid (node)) + goto node_error; + rec_off = tree->node_size -2 ; off =hfs_bnode_read_u16 (node, rec_off);if (off !=sizeof (struct hfs_bnode_desc ))
@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)for (i =1 ; i <= node->num_recs; off = next_off, i++) { rec_off -=2 ; next_off =hfs_bnode_read_u16 (node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off &1 ) +if (!hfs_brec_range_valid (node, off, next_off, rec_off)) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX &&
fs/hfsplus/brec.c +24 -13
@@ -20,38 +20,44 @@ static int hfs_btree_inc_height(struct hfs_btree *);u16 hfs_brec_lenoff (struct hfs_bnode *node,u16 rec,u16 *off) {__be16 retval[2 ]; -u16 dataoff; +u16 data_off; +u16 next_off; - dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (!hfs_brec_record_valid (node, rec)) { + *off =0 ; +return 0 ; + } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 ); *off =be16_to_cpu (retval[1 ]); -return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (!hfs_brec_range_valid (node, *off, next_off, data_off)) +return 0 ; +return next_off - *off; }/* Get the length of the key from a keyed record */ u16 hfs_brec_keylen (struct hfs_bnode *node,u16 rec) { -u16 retval, recoff; +u16 retval, recoff, len;if (node->type !=HFS_NODE_INDEX && node->type !=HFS_NODE_LEAF )return 0 ; +if (!hfs_brec_record_valid (node, rec)) +return 0 ;if ((node->type ==HFS_NODE_INDEX ) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS ) && (node->tree->cnid !=HFSPLUS_ATTR_CNID )) { retval = node->tree->max_key_len +2 ; }else { - recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); + len =hfs_brec_lenoff (node, rec, &recoff); +if (len ==0 )return 0 ; - } retval =hfs_bnode_read_u16 (node, recoff) +2 ; -if (retval > node->tree->max_key_len +2 ) { +if (retval >= len || retval > node->tree->max_key_len +2 ) {pr_err ("keylen %d too large\n" , retval); retval =0 ;
@@ -185,10 +191,15 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode; again: +if (!hfs_brec_record_valid (node, fd->record)) +return -EIO ; + rec_off = tree->node_size - (fd->record +2 ) *2 ; end_off = tree->node_size - (node->num_recs +1 ) *2 ;if (node->type ==HFS_NODE_LEAF ) { +if (tree->leaf_count ==0 ) +return -EIO ; tree->leaf_count--;mark_inode_dirty (tree->inode); }
fs/hfsplus/hfsplus_fs.h +62 -0
68 lines not on this page · raw message
Signature · 1 line
2.43.0
Viacheslav Dubeyko
maintainerRe: [PATCH v2 1/1] hfsplus: validate B-tree record offset table
Quoted 52 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may
contain a record count that does not fit in the node, and record offsets may be
unordered, unaligned, outside the node, or point into the offset table itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that overlaps
the offset table. This can make the unlink/writeback path repeatedly callhfs_bnode_read_u16()with invalid offsets while holding the HFS+ B- tree lock,
producing a flood of "requested invalid offset" messages. Other writeback workers
then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Reject corrupted B-tree metadata earlier: validate
num_recsagainst the node size
before walking the record offset table, reject record offsets that are unordered,
unaligned, outside the node, or overlapping the offset table, stop B- tree record
walkers on invalid records, and avoid decrementing an already-zeroleaf_count.Closes:
https://lore.kernel.org/lkml/[email protected]/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
fs/hfsplus/bfind.c | 27 ++++++++++++++++-- fs/hfsplus/bnode.c | 16 ++++++++--- fs/hfsplus/brec.c | 37 +++++++++++++++---------fs/hfsplus/hfsplus_fs.h| 62
+++++++++++++++++++++++++++++++++++++++++4 files changed, 122 insertions(+), 20 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -108,15 +108,28 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, int b, e; int res;
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, · line 115
Quoted 5 lines
fs/hfsplus/bfind.c +5
-0+ fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ;
It looks like static inline function that needs to be re-used everywhere. And, first of all, it should be called hfs_find_init(). Do we really need to call this initialization somewhere else? Do you think that hfs_find_init() if not enough?
fs/hfsplus/bfind.c
Quoted 4 lines
+
BUG_ON(!rec_found);fs/hfsplus/bfind.c +2
-0+if (!hfs_bnode_num_recs_valid (bnode)) { + res = -EIO ;
Are you sure that it should -EIO but not -ENOENT? Is hfs_brec_find() ready to process -EIO? There are multiple __hfs_brec_find() calls that never analyze the return error code. Are we OK with that?
fs/hfsplus/bfind.c
Quoted 1 line
fs/hfsplus/bfind.c +1
-0+ goto fail;
OK. I see. You need this initialization because you are going to fail case.
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, · line 127
Quoted 7 lines
fs/hfsplus/bfind.c +2
-0+ } +b = 0;
e =bnode->num_recs- 1;
res =-ENOENT;fs/hfsplus/bfind.c +2
-0+if (bnode->num_recs ==0 ) + goto fail;
Are you sure that we should go to fail? Why should we change the logic here? I think we can continue the logic even if bnode->num_recs == 0.
fs/hfsplus/bfind.c
Quoted 6 lines
do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off); keylen =hfs_brec_keylen(bnode, rec);fs/hfsplus/bfind.c +1
-1-if (keylen ==0 ) { +if (keylen ==0 || keylen >= len) {
Are you sure that keylen == len is invalid case? What is wrong with equality?
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, · line 147
Quoted 10 lines
res =
-EINVAL;
goto fail;
}fs/hfsplus/bfind.c +1
-1@@ -130,7 +143,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (keylen ==0 || keylen >= len) {
Ditto. What is wrong with equality?
Quoted 8 lines
fs/hfsplus/bfind.c +0
-0res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +0
-0@@ -232,6 +245,14 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
bnode =fd->bnode;
tree =bnode->tree;
fs/hfsplus/bfind.c int hfs_brec_goto(struct hfs_find_data *fd, int cnt) · line 255
Quoted 8 lines
fs/hfsplus/bfind.c +8
-0+if (!hfs_bnode_num_recs_valid (bnode)) { + res = -EIO ; + goto out; + } +if (bnode->num_recs ==0 ) { + res = -ENOENT ; + goto out; + }
I am not completely sure that it is proper place for these checks. Because, we could work with multiple nodes in this method.
fs/hfsplus/bfind.c
Quoted 10 lines
if (cnt < 0) {
cnt = -cnt;fs/hfsplus/bfind.c +0
-0@@ -274,7 +295,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +1
-1-if (keylen ==0 ) { +if (keylen ==0 || keylen >= len) {
Ditto. What is wrong with equality?
Quoted 147 lines
res =
-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; }fs/hfsplus/bnode.c +3
-0+if (!hfs_bnode_num_recs_valid (node)) + goto node_error; +
rec_off=tree->node_size- 2;
off =hfs_bnode_read_u16(node, rec_off);
if (off !=sizeof(struct hfs_bnode_desc))fs/hfsplus/bnode.c +1
-3@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (!hfs_brec_range_valid (node, off, next_off, rec_off)) goto node_error;
entry_size=next_off- off; if (node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +2
-1@@ -20,38 +20,44 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off;fs/hfsplus/brec.c +7
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (!hfs_brec_record_valid (node, rec)) { + *off =0 ; +return 0 ; + } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +4
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (!hfs_brec_range_valid (node, *off, next_off, data_off)) +return 0 ; +return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (!hfs_brec_record_valid (node, rec)) +return 0 ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +2
-6- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); + len =hfs_brec_lenoff (node, rec, &recoff); +if (len ==0 )return 0;
fs/hfsplus/brec.c +0
-1- }
retval =hfs_bnode_read_u16(node, recoff)+ 2;fs/hfsplus/brec.c +1
-1-if (retval > node->tree->max_key_len +2 ) { + if (retval >= len || retval > node->tree-Quoted 1 line
max_key_len+ 2) {
pr_err("keylen %d too large\n", retval); retval = 0;fs/hfsplus/brec.c +0
-0@@ -185,10 +191,15 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode;again:
fs/hfsplus/brec.c +3
-0+if (!hfs_brec_record_valid (node, fd->record)) +return -EIO ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EIO ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,68 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 594
Quoted 5 lines
fs/hfsplus/hfsplus_fs.h +5
-0+static inline +bool hfs_bnode_num_recs_valid (struct hfs_bnode *node) +{ +u32 node_size; +u32 rec_off_size;
u32 rec_size = sizeof(__be16);
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 596
Quoted 2 lines
fs/hfsplus/hfsplus_fs.h +2
-0+u32 rec_off_tab_size; +u32 rec_area_size;
Why not?
u32 table_size;
u32 area_size;
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 602
Quoted 6 lines
fs/hfsplus/hfsplus_fs.h +6
-0+ +if (!node || !node->tree) +return false; + + node_size = node->tree->node_size; + rec_off_size =sizeof (__be16);
We don't need it here.
Quoted 2 lines
fs/hfsplus/hfsplus_fs.h +1
-0+ if (node_size < sizeof(struct hfs_bnode_desc) +
rec_off_size)
Do you really need to add the rec_off_size? Because, you subtract only sizeof(struct hfs_bnode_desc).
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 606
Quoted 3 lines
fs/hfsplus/hfsplus_fs.h +3
-0+return false; + + rec_area_size = node_size -sizeof (struct hfs_bnode_desc );
You reuse sizeof(struct hfs_bnode_desc). We need local variable instead.
Quoted 19 lines
fs/hfsplus/hfsplus_fs.h +18
-0+ rec_off_tab_size = ((u32 )node->num_recs +1 ) * rec_off_size; + +return rec_off_tab_size <= rec_area_size; +} + +static inline +bool hfs_brec_record_valid (struct hfs_bnode *node,int record) +{ +if (!hfs_bnode_num_recs_valid (node)) +return false; +if (record <0 ) +return false; + +return record < node->num_recs; +} + +static inline +bool hfs_brec_range_valid(struct hfs_bnode *node, u16 off, u16
next_off,
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 627
Quoted 3 lines
fs/hfsplus/hfsplus_fs.h +3
-0+ u16 rec_off) +{ +u32 rec_off_size;
u32 rec_size = sizeof(__be16);
fs/hfsplus/hfsplus_fs.h
Quoted 1 line
fs/hfsplus/hfsplus_fs.h +1
-0+u32 rec_off_tab_size;
table_size
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 629
Quoted 1 line
fs/hfsplus/hfsplus_fs.h +1
-0+u32 rec_off_tab_start;
table_start
Thanks,
Slava.
Quoted 27 lines
fs/hfsplus/hfsplus_fs.h +16
-0+ +if (!node || !node->tree) +return false; + +if (off <sizeof (struct hfs_bnode_desc ) || (off &1 )) +return false; + +if (next_off <= off || + next_off > node->tree->node_size || + next_off > rec_off || + (next_off &1 )) +return false; + + rec_off_size =sizeof (__be16); + rec_off_tab_size = ((u32 )node->num_recs +1 ) * rec_off_size; + rec_off_tab_start = node->tree->node_size -
rec_off_tab_size;fs/hfsplus/hfsplus_fs.h +6
-0+if (next_off > rec_off_tab_start) +return false; + +return true; +} +static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
PATCH v3 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Validate num_recs against the node size before walking the record offset table. Reject record ranges that are unordered, unaligned, outside the node, or overlapping the offset table. Reject invalid record indexes before reading their offset entries, and avoid decrementing an already-zero leaf_count.
---
Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in __hfs_brec_find().
- Move find cursor reset into hfs_find_reset() and call it from hfs_find_init() and hfs_brec_find().
- Rename helper-local variables as suggested.
fs/hfsplus/bfind.c | 13 ++++---- fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 35 +++++++++++++------- fs/hfsplus/hfsplus_fs.h | 72 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 113 insertions(+), 23 deletions(-)
fs/hfsplus/bfind.c +6 -7
@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) fd->tree = tree; fd->bnode =NULL ; +hfs_find_reset (fd); ptr =kzalloc (tree->max_key_len *2 +4 ,GFP_KERNEL );if (!ptr)return -ENOMEM ;
@@ -106,12 +107,14 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,u16 off, len, keylen;int rec;int b, e; -int res; +int res = -ENOENT ;BUG_ON (!rec_found); +if (!hfs_bnode_num_recs_valid (bnode)) + goto fail; + b =0 ; e = bnode->num_recs -1 ; - res = -ENOENT ; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off);
@@ -158,11 +161,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)__be32 data;int height, res; - fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_reset (fd); tree = fd->tree;if (fd->bnode)
fs/hfsplus/bnode.c +12 -4
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs = node->num_recs;hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), desc.type, desc.height,be16_to_cpu (desc.num_recs)); +if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } + off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; } +if (!hfs_bnode_num_recs_valid (node)) + goto node_error; + rec_off = tree->node_size -2 ; off =hfs_bnode_read_u16 (node, rec_off);if (off !=sizeof (struct hfs_bnode_desc ))
@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)for (i =1 ; i <= node->num_recs; off = next_off, i++) { rec_off -=2 ; next_off =hfs_bnode_read_u16 (node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off &1 ) +if (!hfs_brec_range_valid (node, off, next_off, rec_off)) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX &&
fs/hfsplus/brec.c +23 -12
@@ -20,35 +20,41 @@ static int hfs_btree_inc_height(struct hfs_btree *);u16 hfs_brec_lenoff (struct hfs_bnode *node,u16 rec,u16 *off) {__be16 retval[2 ]; -u16 dataoff; +u16 data_off; +u16 next_off; - dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (!hfs_brec_record_valid (node, rec)) { + *off =0 ; +return 0 ; + } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 ); *off =be16_to_cpu (retval[1 ]); -return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (!hfs_brec_range_valid (node, *off, next_off, data_off)) +return 0 ; +return next_off - *off; }/* Get the length of the key from a keyed record */ u16 hfs_brec_keylen (struct hfs_bnode *node,u16 rec) { -u16 retval, recoff; +u16 retval, recoff, len;if (node->type !=HFS_NODE_INDEX && node->type !=HFS_NODE_LEAF )return 0 ; +if (!hfs_brec_record_valid (node, rec)) +return 0 ;if ((node->type ==HFS_NODE_INDEX ) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS ) && (node->tree->cnid !=HFSPLUS_ATTR_CNID )) { retval = node->tree->max_key_len +2 ; }else { - recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); + len =hfs_brec_lenoff (node, rec, &recoff); +if (len ==0 )return 0 ; - } retval =hfs_bnode_read_u16 (node, recoff) +2 ;if (retval > node->tree->max_key_len +2 ) {
@@ -185,10 +191,15 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode; again: +if (!hfs_brec_record_valid (node, fd->record)) +return -EIO ; + rec_off = tree->node_size - (fd->record +2 ) *2 ; end_off = tree->node_size - (node->num_recs +1 ) *2 ;if (node->type ==HFS_NODE_LEAF ) { +if (tree->leaf_count ==0 ) +return -EIO ; tree->leaf_count--;mark_inode_dirty (tree->inode); }
fs/hfsplus/hfsplus_fs.h +72 -0
78 lines not on this page · raw message
Signature · 1 line
2.43.0
Viacheslav Dubeyko
maintainerRe: [PATCH v3] hfsplus: validate B-tree record offset table
Quoted 60 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor
may contain a record count that does not fit in the node, and record offsets may
be unordered, unaligned, outside the node, or point into the offset table
itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly
callhfs_bnode_read_u16()with invalid offsets while holding the HFS+ B-tree
lock, producing a flood of "requested invalid offset" messages. Other writeback
workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset table.
Reject record ranges that are unordered, unaligned, outside the node, or
overlapping the offset table. Reject invalid record indexes before reading their
offset entries, and avoid decrementing an already-zeroleaf_count.Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 13 ++++---- fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 35 +++++++++++++-------
fs/hfsplus/hfsplus_fs.h| 72
+++++++++++++++++++++++++++++++++++++++++4 files changed, 113 insertions(+), 23 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
fd->tree= tree;
fd->bnode= NULL;
fs/hfsplus/bfind.c
Quoted 1 line
fs/hfsplus/bfind.c +1
-0+hfs_find_reset (fd);
The hfs_find_reset() sounds weird. We are trying to initialize the result section of the b-tree search data structure. So, hfs_find_result_init() sounds like more proper name, for my taste.
Quoted 12 lines
ptr =
kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); if (!ptr)
return-ENOMEM;fs/hfsplus/bfind.c +1
-1@@ -106,12 +107,14 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen; int rec; int b, e; -int res; +int res = -ENOENT ;
BUG_ON(!rec_found);
fs/hfsplus/bfind.c int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, · line 114
Quoted 2 lines
fs/hfsplus/bfind.c +2
-0+if (!hfs_bnode_num_recs_valid (bnode)) + goto fail;
Are you sure that we don't need to call the hfs_find_reset() here? Because, __hfs_brec_find() could be called not only from hfs_brec_find() context.
Quoted 12 lines
+
b = 0;
e =bnode->num_recs- 1;fs/hfsplus/bfind.c +0
-1- res = -ENOENT ;do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off);fs/hfsplus/bfind.c +0
-0@@ -158,11 +161,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) __be32 data; int height, res;
fs/hfsplus/bfind.c int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) · line 164
Quoted 6 lines
fs/hfsplus/bfind.c +1
-5- fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_reset (fd);
Ditto.
Quoted 38 lines
tree =fd->tree;
if (fd->bnode)fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) goto node_error; }
fs/hfsplus/bnode.c struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) · line 590
Quoted 2 lines
fs/hfsplus/bnode.c +2
-0+if (!hfs_bnode_num_recs_valid (node)) + goto node_error;
We assign the num_recs value here [1]:
node->prev = be32_to_cpu(desc->prev); node->next = be32_to_cpu(desc->next); node->num_recs = be16_to_cpu(desc->num_recs); node->type = desc->type; node->height = desc->height;
I think that it is better place for the check.
Quoted 5 lines
+
rec_off=tree->node_size- 2;
off =hfs_bnode_read_u16(node, rec_off);
if (off !=sizeof(struct hfs_bnode_desc))
fs/hfsplus/bnode.c struct hfs_bnode *hfs_bnode_find(struct hfs_btree · line 601
Quoted 9 lines
fs/hfsplus/bnode.c +1
-3@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (!hfs_brec_range_valid (node, off, next_off, rec_off))
Please, see my comment below.
Quoted 16 lines
fs/hfsplus/bnode.c +0
-0goto node_error;
entry_size=next_off- off; if (node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +2
-1@@ -20,35 +20,41 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off;
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 27
Quoted 4 lines
fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); +if (!hfs_brec_record_valid (node, rec)) { + *off =0 ;
Are you sure that assigning 0 is correct? We will assign fd->keyoffset = off. What if fd->keyoffset is used in the case of error? Maybe U16_MAX will be better?
fs/hfsplus/brec.c
Quoted 1 line
fs/hfsplus/brec.c +1
-0+return 0 ;
Ditto. Are you sure that 0 is a safe value? Maybe U16_MAX will be better?
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 36
Quoted 9 lines
fs/hfsplus/brec.c +4
-0+ } + + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +3
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (!hfs_brec_range_valid (node, *off, next_off, data_off)) +return 0 ;
Ditto.
Quoted 12 lines
fs/hfsplus/brec.c +1
-0+return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 48
Quoted 2 lines
fs/hfsplus/brec.c +2
-0+if (!hfs_brec_record_valid (node, rec)) +return 0 ;
Ditto.
fs/hfsplus/brec.c static int hfs_btree_inc_height(struct hfs_btree *); · line 55
Quoted 13 lines
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +1
-6- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); + len =hfs_brec_lenoff (node, rec, &recoff);
Ditto.
fs/hfsplus/brec.c
Quoted 12 lines
fs/hfsplus/brec.c +1
-0+if (len ==0 )return 0;
fs/hfsplus/brec.c +0
-1- }
retval =hfs_bnode_read_u16(node, recoff)+ 2; if (retval >node->tree->max_key_len+ 2) {fs/hfsplus/brec.c +0
-0@@ -185,10 +191,15 @@ int hfs_brec_remove(struct hfs_find_data *fd) tree = fd->tree; node = fd->bnode;again:
fs/hfsplus/brec.c +2
-0+if (!hfs_brec_record_valid (node, fd->record)) +return -EIO ;
We check the fd->record. If this value is incorrect, then it's internal logic error but not -EIO error code.
fs/hfsplus/brec.c int hfs_brec_remove(struct hfs_find_data *fd) · line 202
Quoted 7 lines
+
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EIO ;
Ditto.
Quoted 48 lines
tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,78 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }fs/hfsplus/hfsplus_fs.h +35
-0+static inline +bool hfs_bnode_num_recs_valid (struct hfs_bnode *node) +{ +u32 node_size; +u32 table_size; +u32 area_size; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return false; + + node_size = node->tree->node_size; +if (node_size < desc_size) +return false; + + area_size = node_size - desc_size; + table_size = ((u32 )node->num_recs +1 ) * rec_size; + +return table_size <= area_size; +} + +static inline +bool hfs_brec_record_valid (struct hfs_bnode *node,int record) +{ +if (!hfs_bnode_num_recs_valid (node)) +return false; +if (record <0 ) +return false; + +return record < node->num_recs; +} + +static inline +bool hfs_brec_range_valid(struct hfs_bnode *node, u16 off, u16
next_off,
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 625
Quoted 1 line
fs/hfsplus/hfsplus_fs.h +1
-0+ u16 rec_off)
We are checking not range but neighboring items. So, I cannot agree with hfs_brec_range_valid() name because there are no range here in the check.
Quoted 18 lines
fs/hfsplus/hfsplus_fs.h +18
-0+{ +u32 table_size; +u32 table_start; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return false; + +if (off < desc_size || (off &1 )) +return false; + +if (next_off <= off || + next_off > node->tree->node_size || + next_off > rec_off || + (next_off &1 )) +return false; +
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 653
Quoted 10 lines
fs/hfsplus/hfsplus_fs.h +10
-0+ table_size = ((u32 )node->num_recs +1 ) * rec_size; + table_start = node->tree->node_size - table_size; +if (next_off > table_start) +return false; + +return true; +} + +static inline +void hfs_find_reset (struct hfs_find_data *fd)
Please, see my comment above.
Thanks,
Slava.
Quoted 8 lines
fs/hfsplus/hfsplus_fs.h +8
-0+{ + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +} +
Quoted 4 lines
static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/bnode.c#L559
PATCH v4 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Validate num_recs against the node size before walking the record offset table. Reject record ranges that are unordered, unaligned, outside the node, or overlapping the offset table. Reject invalid record indexes before reading their offset entries, and avoid decrementing an already-zero leaf_count.
---
Changes in v4:
- Rename hfs_find_reset() to hfs_find_result_init().
- Reset find result fields in __hfs_brec_find().
- Move num_recs validation next to descriptor field initialization.
- Rename hfs_brec_range_valid() to hfs_brec_offpair_valid().
- Use U16_MAX for invalid offset/len/keylen sentinels and update callers.
- Add hfs_brec_len_valid() to check validity of len/keylen.
- Handle invalid B-tree map record lengths in hfs_bmap_get_map_page() and hfs_bmap_free().
- Return -EINVAL instead of -EIO for invalid remove cursor/leaf_count state.
Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in __hfs_brec_find().
- Move find cursor reset into hfs_find_reset() and call it from hfs_find_init() and hfs_brec_find().
- Rename helper-local variables as suggested.
fs/hfsplus/bfind.c | 21 +++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 43 ++++++++++++++-------- fs/hfsplus/btree.c | 11 ++++++ fs/hfsplus/hfsplus_fs.h | 79 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 142 insertions(+), 28 deletions(-)
fs/hfsplus/bfind.c +11 -10
@@ -9,6 +9,7 @@* Search routines for btrees */ +#include <linux/limits.h> #include <linux/slab.h> #include "hfsplus_fs.h"
@@ -18,6 +19,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) fd->tree = tree; fd->bnode =NULL ; +hfs_find_result_init (fd); ptr =kzalloc (tree->max_key_len *2 +4 ,GFP_KERNEL );if (!ptr)return -ENOMEM ;
@@ -106,17 +108,20 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,u16 off, len, keylen;int rec;int b, e; -int res; +int res = -ENOENT ;BUG_ON (!rec_found); +hfs_find_result_init (fd); +if (!hfs_bnode_num_recs_valid (bnode)) + goto fail; + b =0 ; e = bnode->num_recs -1 ; - res = -ENOENT ; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (!hfs_brec_len_valid(len) || !hfs_brec_len_valid(keylen)) { res = -EINVAL; goto fail; }
@@ -130,7 +135,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,if (rec != e && e >=0 ) { len =hfs_brec_lenoff (bnode, e, &off); keylen =hfs_brec_keylen (bnode, e); -if (keylen ==0 ) { +if (!hfs_brec_len_valid (keylen) || !hfs_brec_len_valid (len)) { res = -EINVAL ; goto fail; }
@@ -158,11 +163,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)__be32 data;int height, res; - fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd); tree = fd->tree;if (fd->bnode)
@@ -274,7 +275,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) len =hfs_brec_lenoff (bnode, fd->record, &off); keylen =hfs_brec_keylen (bnode, fd->record); -if (keylen ==0 ) { +if (!hfs_brec_len_valid (len) || !hfs_brec_len_valid (keylen)) { res = -EINVAL ; goto out; }
fs/hfsplus/bnode.c +12 -4
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs = node->num_recs;hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), desc.type, desc.height,be16_to_cpu (desc.num_recs)); +if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } + off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height;kunmap_local (desc); +if (!hfs_bnode_num_recs_valid (node)) + goto node_error; +switch (node->type) {case HFS_NODE_HEADER :case HFS_NODE_MAP :
@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)for (i =1 ; i <= node->num_recs; off = next_off, i++) { rec_off -=2 ; next_off =hfs_bnode_read_u16 (node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off &1 ) +if (!hfs_brec_offpair_valid (node, off, next_off, rec_off)) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX &&
fs/hfsplus/brec.c +29 -14
86 lines not on this page · raw message
fs/hfsplus/btree.c +11 -0
@@ -12,6 +12,7 @@#include <linux/slab.h> #include <linux/pagemap.h> #include <linux/log2.h> +#include <linux/limits.h> #include "hfsplus_fs.h" #include "hfsplus_raw.h"
@@ -168,6 +169,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, } ctx->len =hfs_brec_lenoff (node, rec_idx, &off16); +if (ctx->len ==U16_MAX ) +return ERR_PTR (-EINVAL );if (!ctx->len)return ERR_PTR (-ENOENT );
@@ -622,6 +625,10 @@ void hfs_bmap_free(struct hfs_bnode *node)if (IS_ERR (node))return ; len =hfs_brec_lenoff (node,2 , &off); +if (!hfs_brec_len_valid (len)) { +hfs_bnode_put (node); +return ; + }while (nidx >= len *8 ) {u32 i;
@@ -648,6 +655,10 @@ void hfs_bmap_free(struct hfs_bnode *node)return ; } len =hfs_brec_lenoff (node,0 , &off); +if (!hfs_brec_len_valid (len)) { +hfs_bnode_put (node); +return ; + } } res =hfs_bmap_clear_bit (node, nidx);
fs/hfsplus/hfsplus_fs.h +79 -0
91 lines not on this page · raw message
Signature · 1 line
2.43.0
Viacheslav Dubeyko
maintainerRe: [PATCH v4] hfsplus: validate B-tree record offset table
fs/hfsplus/brec.c int hfs_brec_remove(struct hfs_find_data *fd)
Quoted 278 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor
may contain a record count that does not fit in the node, and record offsets may
be unordered, unaligned, outside the node, or point into the offset table
itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly
callhfs_bnode_read_u16()with invalid offsets while holding the HFS+ B-tree
lock, producing a flood of "requested invalid offset" messages. Other writeback
workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset table.
Reject record ranges that are unordered, unaligned, outside the node, or
overlapping the offset table. Reject invalid record indexes before reading their
offset entries, and avoid decrementing an already-zeroleaf_count.
---
Changes in v4:
- Renamehfs_find_reset()tohfs_find_result_init().
- Reset find result fields in__hfs_brec_find().
- Movenum_recsvalidation next to descriptor field initialization.
- Renamehfs_brec_range_valid()tohfs_brec_offpair_valid().
- UseU16_MAXfor invalid offset/len/keylen sentinels and update callers.
- Addhfs_brec_len_valid()to check validity of len/keylen.
- Handle invalid B-tree map record lengths inhfs_bmap_get_map_page()andhfs_bmap_free().
- Return-EINVALinstead of-EIOfor invalid remove cursor/leaf_count state.Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 21 +++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 43 ++++++++++++++-------- fs/hfsplus/btree.c | 11 ++++++
fs/hfsplus/hfsplus_fs.h| 79
+++++++++++++++++++++++++++++++++++++++++5 files changed, 142 insertions(+), 28 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -9,6 +9,7 @@* Search routines for btrees */
+#include <linux/limits.h>
#include <linux/slab.h>
#include "hfsplus_fs.h"fs/hfsplus/bfind.c +0
-0@@ -18,6 +19,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
fd->tree= tree;
fd->bnode= NULL;fs/hfsplus/bfind.c +1
-0+hfs_find_result_init (fd);ptr =
kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); if (!ptr)
return-ENOMEM;fs/hfsplus/bfind.c +1
-1@@ -106,17 +108,20 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen; int rec; int b, e; -int res; +int res = -ENOENT ;
BUG_ON(!rec_found);fs/hfsplus/bfind.c +4
-0+hfs_find_result_init (fd); +if (!hfs_bnode_num_recs_valid (bnode)) + goto fail; +b = 0;
e =bnode->num_recs- 1;fs/hfsplus/bfind.c +0
-1- res = -ENOENT ;do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off); keylen =hfs_brec_keylen(bnode, rec);fs/hfsplus/bfind.c +1
-1-if (keylen ==0 ) { + if (!hfs_brec_len_valid(len) ||!hfs_brec_len_valid(keylen)) {
res =-EINVAL;
goto fail;
}fs/hfsplus/bfind.c +1
-1@@ -130,7 +135,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (!hfs_brec_len_valid (keylen) || !hfs_brec_len_valid (len)) { res = -EINVAL;goto fail;
}fs/hfsplus/bfind.c +0
-0@@ -158,11 +163,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) __be32 data; int height, res;fs/hfsplus/bfind.c +1
-5- fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd);
tree =fd->tree;
if (fd->bnode)fs/hfsplus/bfind.c +0
-0@@ -274,7 +275,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +1
-1-if (keylen ==0 ) { +if (!hfs_brec_len_valid (len) || !hfs_brec_len_valid (keylen)){
res =-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (!hfs_bnode_num_recs_valid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height; kunmap_local(desc);fs/hfsplus/bnode.c +3
-0+if (!hfs_bnode_num_recs_valid (node)) + goto node_error; +switch (
node->type) {
caseHFS_NODE_HEADER:
caseHFS_NODE_MAP:fs/hfsplus/bnode.c +1
-3@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (!hfs_brec_offpair_valid (node, off, next_off, rec_off)) goto node_error;
entry_size=next_off- off; if (node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +0
-0@@ -9,6 +9,8 @@* Handle individual btree records */ fs/hfsplus/brec.c +2
-0+#include <linux/limits.h> +#include "
hfsplus_fs.h"
#include "hfsplus_raw.h"fs/hfsplus/brec.c +7
-1@@ -20,41 +22,49 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off; + +if (!hfs_brec_record_valid (node, rec)) { + *off =U16_MAX ; +return U16_MAX ; + }fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +2
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (!hfs_brec_offpair_valid (node, *off, next_off, data_off)){
fs/hfsplus/brec.c +4
-0+ *off =U16_MAX ; +return U16_MAX ; + } +return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (!hfs_brec_record_valid (node, rec)) +return U16_MAX ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +3
-8- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); -return 0 ; - } + len =hfs_brec_lenoff (node, rec, &recoff); +if (!hfs_brec_len_valid (len)) +return len;
retval =hfs_bnode_read_u16(node, recoff)+ 2; if (retval >node->tree->max_key_len+ 2) {pr_err("keylen %d too large\n", retval);fs/hfsplus/brec.c +1
-1- retval =0 ; + retval =U16_MAX ;}
}
return retval;fs/hfsplus/brec.c +0
-0@@ -185,10 +195,15 @@ int hfs_brec_remove(struct hfs_find_data *fd)
We call __hfs_brec_find() in several places [1 - 4]. Do we need to check the returned error code for [1] case? We need to check the returned error code for [2,3] cases. Do we need to check the returned error code for [4] case?
Quoted 34 lines
fs/hfsplus/brec.c +0
-0tree = fd->tree; node = fd->bnode;again:
fs/hfsplus/brec.c +3
-0+if (!hfs_brec_record_valid (node, fd->record)) +return -EINVAL ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EINVAL ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/btree.c +1
-0@@ -12,6 +12,7 @@ #include <linux/slab.h> #include <linux/pagemap.h> #include <linux/log2.h> +#include <linux/limits.h>
#include "hfsplus_fs.h"
#include "hfsplus_raw.h"fs/hfsplus/btree.c +0
-0@@ -168,6 +169,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, }
ctx->len=hfs_brec_lenoff(node, rec_idx, &off16);fs/hfsplus/btree.c +2
-0+if (ctx->len ==U16_MAX ) +return ERR_PTR (-EINVAL );
Quoted 2 lines
if (!ctx->len)
returnERR_PTR(-ENOENT);
Why not hfs_brec_len_valid() for both checks?
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 628
Quoted 6 lines
fs/hfsplus/btree.c +1
-0@@ -622,6 +625,10 @@ void hfs_bmap_free(struct hfs_bnode *node) if (IS_ERR(node)) return; len = hfs_brec_lenoff(node, 2, &off); +if (!hfs_brec_len_valid (len)) {
As far as I can see, you check as len as off everywhere. But why not here?
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 658
Quoted 11 lines
fs/hfsplus/btree.c +3
-0+hfs_bnode_put (node); +return ; + } while (nidx >= len * 8) { u32 i;fs/hfsplus/btree.c +1
-0@@ -648,6 +655,10 @@ void hfs_bmap_free(struct hfs_bnode *node) return; } len = hfs_brec_lenoff(node, 0, &off); +if (!hfs_brec_len_valid (len)) {
Ditto.
Quoted 23 lines
fs/hfsplus/btree.c +3
-0+hfs_bnode_put (node); +return ; + } }
res =hfs_bmap_clear_bit(node, nidx);fs/hfsplus/hfsplus_fs.h +1
-0@@ -16,6 +16,7 @@ #include <linux/buffer_head.h> #include <linux/blkdev.h> #include <linux/fs_context.h> +#include <linux/limits.h> #include "hfsplus_raw.h"
/* Runtime config options */fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +588,84 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 592
Quoted 2 lines
fs/hfsplus/hfsplus_fs.h +2
-0+static inline +bool hfs_bnode_num_recs_valid (struct hfs_bnode *node)
I prefer invalid check for all cases because it is safe to state that value is invalid. Because, validity check requires more precise calculation.
Quoted 12 lines
fs/hfsplus/hfsplus_fs.h +12
-0+{ +u32 node_size; +u32 table_size; +u32 area_size; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return false; + + node_size = node->tree->node_size; +if (node_size < desc_size)
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 614
Quoted 10 lines
fs/hfsplus/hfsplus_fs.h +10
-0+return false; + + area_size = node_size - desc_size; + table_size = ((u32 )node->num_recs +1 ) * rec_size; + +return table_size <= area_size; +} + +static inline +bool hfs_brec_record_valid (struct hfs_bnode *node,int record)
Ditto. The invalidity check is more safe statement.
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 626
Quoted 13 lines
fs/hfsplus/hfsplus_fs.h +11
-0+{ +if (!hfs_bnode_num_recs_valid (node)) +return false; +if (record <0 ) +return false; + +return record < node->num_recs; +} + +static inline +bool hfs_brec_offpair_valid(struct hfs_bnode *node, u16 off, u16
next_off,fs/hfsplus/hfsplus_fs.h +1
-0+ u16 rec_off)
Ditto. The invalidity check is more safe statement.
I am slightly confused by argument names. What is the difference between off, next_off, and rec_off? We need to have more clear names here.
The hfs_brec_offpair_valid() name sounds really weird. I believe that you simply check the off value. Am I correct? So, it means that you don't check the pair. You check only one item but not two or three ones.
Quoted 20 lines
fs/hfsplus/hfsplus_fs.h +20
-0+{ +u32 table_size; +u32 table_start; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return false; + +if (off < desc_size || (off &1 )) +return false; + +if (next_off <= off || + next_off > node->tree->node_size || + next_off > rec_off || + (next_off & 1)) +return false; + + table_size = ((u32 )node->num_recs +1 ) * rec_size; + table_start = node->tree->node_size - table_size;
fs/hfsplus/hfsplus_fs.h bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) · line 656
Quoted 10 lines
fs/hfsplus/hfsplus_fs.h +10
-0+if (next_off > table_start) +return false; + +return true; +} + +static inline +bool hfs_brec_len_valid (u16 len) +{ +return len !=U16_MAX && len !=0 ;
Frankly speaking, I believe that it could be better to check the len with the node_size but not U16_MAX. Does it makes sense to you?
Moreover, the comparison with 0 and U16_MAX cannot guarantee that len is valid. If len is 0 or bigger that node_size, then it is definitely invalid length. It will be better to name the method as hfs_brec_len_invalid(). Oppositely, hfs_brec_len_valid() requires more precise check.
Thanks,
Slava.
Quoted 12 lines
fs/hfsplus/hfsplus_fs.h +12
-0+} + +static inline +void hfs_find_result_init (struct hfs_find_data *fd) +{ + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +} +
Quoted 4 lines
static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449
PATCH v5 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Validate num_recs against the node size before walking the record offset table. Reject record ranges that are unordered, unaligned, outside the node, or overlapping the offset table. Reject invalid record indexes before reading their offset entries, and avoid decrementing an already-zero leaf_count.
---
Changes in v5:
- Switch helpers to invalid checker and invert callers.
- hfs_brec_offsets_invalid(): Drop the redundant offset-table argument since it is already covered by the offset-table overlap check and take just the two neighboring record offsets (off and next_off).
- hfs_brec_len_invalid(): reject a length against node_size.
- Use hfs_brec_len_invalid() for both length checks in hfs_bmap_get_map_page().
- Validate the record offset in hfs_bmap_free().
- Check the __hfs_brec_find() return code in [2] and [3]. [1] and [4] call it to find the insertion slot for a new index key after a split, -ENOENT is one of expected, even -EINVAL the following hfs_brec_insert() just inserts at slot 0 of a node already validated by hfs_bnode_find(), so it stays in-bounds and cannot trigger the invalid-offset flood. Hence no check was added.
[1] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449
Changes in v4:
- Rename hfs_find_reset() to hfs_find_result_init().
- Reset find result fields in __hfs_brec_find().
- Move num_recs validation next to descriptor field initialization.
- Rename hfs_brec_range_valid() to hfs_brec_offpair_valid().
- Use U16_MAX for invalid offset/len/keylen sentinels and update callers.
- Add hfs_brec_len_valid() to check validity of len/keylen.
- Handle invalid B-tree map record lengths in hfs_bmap_get_map_page() and hfs_bmap_free().
- Return -EINVAL instead of -EIO for invalid remove cursor/leaf_count state.
Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in __hfs_brec_find().
- Move find cursor reset into hfs_find_reset() and call it from hfs_find_init() and hfs_brec_find().
- Rename helper-local variables as suggested.
fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 14 ++++++-- fs/hfsplus/hfsplus_fs.h | 79 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 153 insertions(+), 32 deletions(-)
fs/hfsplus/bfind.c +13 -10
@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) fd->tree = tree; fd->bnode =NULL ; +hfs_find_result_init (fd); ptr =kzalloc (tree->max_key_len *2 +4 ,GFP_KERNEL );if (!ptr)return -ENOMEM ;
@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,u16 off, len, keylen;int rec;int b, e; -int res; +int res = -ENOENT ;BUG_ON (!rec_found); +hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; + b =0 ; e = bnode->num_recs -1 ; - res = -ENOENT ; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (hfs_brec_len_invalid(bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) { res = -EINVAL; goto fail; }
@@ -130,7 +135,8 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,if (rec != e && e >=0 ) { len =hfs_brec_lenoff (bnode, e, &off); keylen =hfs_brec_keylen (bnode, e); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, keylen) || +hfs_brec_len_invalid (bnode, len)) { res = -EINVAL ; goto fail; }
@@ -158,11 +164,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)__be32 data;int height, res; - fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd); tree = fd->tree;if (fd->bnode)
@@ -274,7 +276,8 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) len =hfs_brec_lenoff (bnode, fd->record, &off); keylen =hfs_brec_keylen (bnode, fd->record); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || +hfs_brec_len_invalid (bnode, keylen)) { res = -EINVAL ; goto out; }
fs/hfsplus/bnode.c +12 -4
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs = node->num_recs;hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), desc.type, desc.height,be16_to_cpu (desc.num_recs)); +if (hfs_bnode_num_recs_invalid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } + off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height;kunmap_local (desc); +if (hfs_bnode_num_recs_invalid (node)) + goto node_error; +switch (node->type) {case HFS_NODE_HEADER :case HFS_NODE_MAP :
@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)for (i =1 ; i <= node->num_recs; off = next_off, i++) { rec_off -=2 ; next_off =hfs_bnode_read_u16 (node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off &1 ) +if (hfs_brec_offsets_invalid (node, off, next_off)) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX &&
fs/hfsplus/brec.c +37 -16
118 lines not on this page · raw message
fs/hfsplus/btree.c +12 -2
@@ -168,8 +168,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, } ctx->len =hfs_brec_lenoff (node, rec_idx, &off16); -if (!ctx->len) -return ERR_PTR (-ENOENT ); +if (hfs_brec_len_invalid (node, ctx->len)) +return ERR_PTR (-EINVAL );if (!is_bnode_offset_valid (node, off16))return ERR_PTR (-EIO );
@@ -622,6 +622,11 @@ void hfs_bmap_free(struct hfs_bnode *node)if (IS_ERR (node))return ; len =hfs_brec_lenoff (node,2 , &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid (node, off)) { +hfs_bnode_put (node); +return ; + }while (nidx >= len *8 ) {u32 i;
@@ -648,6 +653,11 @@ void hfs_bmap_free(struct hfs_bnode *node)return ; } len =hfs_brec_lenoff (node,0 , &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid (node, off)) { +hfs_bnode_put (node); +return ; + } } res =hfs_bmap_clear_bit (node, nidx);
fs/hfsplus/hfsplus_fs.h +79 -0
85 lines not on this page · raw message
Signature · 1 line
2.43.0
Viacheslav Dubeyko
maintainerRe: [PATCH v5] hfsplus: validate B-tree record offset table
Quoted 373 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and
record offsets may be unordered, unaligned, outside the node, or point into
the offset table itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly callhfs_bnode_read_u16()with invalid offsets while holding the
HFS+ B-tree lock, producing a flood of "requested invalid offset" messages.
Other writeback workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset
table. Reject record ranges that are unordered, unaligned, outside the
node, or overlapping the offset table. Reject invalid record indexes before
reading their offset entries, and avoid decrementing an already-zeroleaf_count.Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
Changes in v5:
- Switch helpers to invalid checker and invert callers.
-hfs_brec_offsets_invalid(): Drop the redundant offset-table argument
since it is already covered by the offset-table overlap check and take
just the two neighboring record offsets (off andnext_off).
-hfs_brec_len_invalid(): reject a length againstnode_size.
- Usehfs_brec_len_invalid()for both length checks inhfs_bmap_get_map_page().
- Validate the record offset inhfs_bmap_free().
- Check the__hfs_brec_find()return code in [2] and [3]. [1] and [4] call
it to find the insertion slot for a new index key after a split, - ENOENT is
one of expected, even-EINVALthe followinghfs_brec_insert()just inserts
at slot 0 of a node already validated byhfs_bnode_find(), so it stays
in-bounds and cannot trigger the invalid-offset flood. Hence no check was
added.[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449Changes in v4:
- Renamehfs_find_reset()tohfs_find_result_init().
- Reset find result fields in__hfs_brec_find().
- Movenum_recsvalidation next to descriptor field initialization.
- Renamehfs_brec_range_valid()tohfs_brec_offpair_valid().
- UseU16_MAXfor invalid offset/len/keylen sentinels and update callers.
- Addhfs_brec_len_valid()to check validity of len/keylen.
- Handle invalid B-tree map record lengths inhfs_bmap_get_map_page()andhfs_bmap_free().
- Return-EINVALinstead of-EIOfor invalid remove cursor/leaf_count state.Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 14 ++++++--
fs/hfsplus/hfsplus_fs.h| 79
+++++++++++++++++++++++++++++++++++++++++5 files changed, 153 insertions(+), 32 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
fd->tree= tree;
fd->bnode= NULL;fs/hfsplus/bfind.c +1
-0+hfs_find_result_init (fd);ptr =
kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); if (!ptr)
return-ENOMEM;fs/hfsplus/bfind.c +1
-1@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen; int rec; int b, e; -int res; +int res = -ENOENT ;
BUG_ON(!rec_found);fs/hfsplus/bfind.c +4
-0+hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; +b = 0;
e =bnode->num_recs- 1;fs/hfsplus/bfind.c +0
-1- res = -ENOENT ;do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off); keylen =hfs_brec_keylen(bnode, rec);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {res =
-EINVAL;
goto fail;
}fs/hfsplus/bfind.c +2
-1@@ -130,7 +135,8 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, keylen) || + hfs_brec_len_invalid(bnode, len)) { res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +0
-0@@ -158,11 +164,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) __be32 data; int height, res;fs/hfsplus/bfind.c +1
-5- fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd);
tree =fd->tree;
if (fd->bnode)fs/hfsplus/bfind.c +0
-0@@ -274,7 +276,8 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {res =
-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (hfs_bnode_num_recs_invalid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height; kunmap_local(desc);fs/hfsplus/bnode.c +3
-0+if (hfs_bnode_num_recs_invalid (node)) + goto node_error; +switch (
node->type) {
caseHFS_NODE_HEADER:
caseHFS_NODE_MAP:fs/hfsplus/bnode.c +1
-3@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (hfs_brec_offsets_invalid (node, off, next_off)) goto node_error; entry_size = next_off - off;if (
node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +0
-0@@ -9,6 +9,8 @@* Handle individual btree records */ fs/hfsplus/brec.c +2
-0+#include <linux/limits.h> +#include "
hfsplus_fs.h"
#include "hfsplus_raw.h"fs/hfsplus/brec.c +7
-1@@ -20,41 +22,49 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off; + +if (hfs_brec_record_invalid (node, rec)) { + *off =U16_MAX ; +return U16_MAX ; + }fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +6
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (hfs_brec_offsets_invalid (node, *off, next_off)) { + *off =U16_MAX ; +return U16_MAX ; + } +return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (hfs_brec_record_invalid (node, rec)) +return U16_MAX ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +3
-8- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); -return 0 ; - } + len =hfs_brec_lenoff (node, rec, &recoff); +if (hfs_brec_len_invalid (node, len)) +return len;
retval =hfs_bnode_read_u16(node, recoff)+ 2; if (retval >node->tree->max_key_len+ 2) {pr_err("keylen %d too large\n", retval);fs/hfsplus/brec.c +1
-1- retval =0 ; + retval =U16_MAX ;}
}
return retval;fs/hfsplus/brec.c +1
-0@@ -181,14 +191,20 @@ int hfs_brec_remove(struct hfs_find_data *fd) struct hfs_btree *tree; struct hfs_bnode *node, *parent; int end_off, rec_off, data_off, size; +int res;
tree =fd->tree;
node =fd->bnode;
again:fs/hfsplus/brec.c +3
-0+if (hfs_brec_record_invalid (node, fd->record)) +return -EINVAL ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EINVAL ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/brec.c +0
-0@@ -205,7 +221,9 @@ int hfs_brec_remove(struct hfs_find_data *fd) hfs_bnode_put(node); node = fd->bnode = parent;fs/hfsplus/brec.c +1
-1-__hfs_brec_find (node, fd, hfs_find_rec_by_key); + res = __hfs_brec_find(node, fd,
hfs_find_rec_by_key);fs/hfsplus/brec.c +2
-0+if (res && res != -ENOENT ) +return res;goto again;
}
hfs_bnode_write_u16(node,fs/hfsplus/brec.c +1
-0@@ -368,6 +386,7 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) int newkeylen, diff; int rec, rec_off, end_rec_off; int start_off, end_off; +int res;
tree =fd->tree;
node =fd->bnode;fs/hfsplus/brec.c +3
-1@@ -379,7 +398,9 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) parent = hfs_bnode_find(tree, node->parent); if (IS_ERR(parent)) return PTR_ERR(parent); -__hfs_brec_find (parent, fd, hfs_find_rec_by_key); + res =__hfs_brec_find (parent, fd, hfs_find_rec_by_key); +if (res && res != -ENOENT ) +return res; if (fd->record < 0) return -ENOENT;
hfs_bnode_dump(parent);fs/hfsplus/btree.c +0
-0@@ -168,8 +168,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, }
ctx->len=hfs_brec_lenoff(node, rec_idx, &off16);fs/hfsplus/btree.c +2
-2-if (!ctx->len) -return ERR_PTR (-ENOENT ); +if (hfs_brec_len_invalid (node, ctx->len)) +return ERR_PTR (-EINVAL );
if (!is_bnode_offset_valid(node, off16))
returnERR_PTR(-EIO);
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 626
Quoted 5 lines
fs/hfsplus/btree.c +2
-0@@ -622,6 +622,11 @@ void hfs_bmap_free(struct hfs_bnode *node) if (IS_ERR(node)) return; len = hfs_brec_lenoff(node, 2, &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid(node, off)) {
If I am correct, the off value is never used. So, I think that this check is not necessary here. Am I right?
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 627
Quoted 1 line
fs/hfsplus/btree.c +1
-0+hfs_bnode_put (node);
I think we cannot keep silence here. I believe that we should have the error message for this case. Do you agree?
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 657
Quoted 11 lines
fs/hfsplus/btree.c +2
-0+return ; + } while (nidx >= len * 8) { u32 i;fs/hfsplus/btree.c +2
-0@@ -648,6 +653,11 @@ void hfs_bmap_free(struct hfs_bnode *node) return; } len = hfs_brec_lenoff(node, 0, &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid(node, off)) {
Ditto.
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 658
Quoted 1 line
fs/hfsplus/btree.c +1
-0+hfs_bnode_put (node);
Ditto.
Quoted 94 lines
fs/hfsplus/btree.c +2
-0+return ; + } }
res =hfs_bmap_clear_bit(node, nidx);fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,85 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }fs/hfsplus/hfsplus_fs.h +35
-0+static inline +bool hfs_bnode_num_recs_invalid (struct hfs_bnode *node) +{ +u32 node_size; +u32 table_size; +u32 area_size; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + + node_size = node->tree->node_size; +if (node_size < desc_size) +return true; + + area_size = node_size - desc_size; + table_size = ((u32 )node->num_recs +1 ) * rec_size; + +return table_size > area_size; +} + +static inline +bool hfs_brec_record_invalid (struct hfs_bnode *node,int record) +{ +if (hfs_bnode_num_recs_invalid (node)) +return true; +if (record <0 ) +return true; + +return record >= node->num_recs; +} + +static inline +bool hfs_brec_offsets_invalid(struct hfs_bnode *node, u16 off, u16
next_off)fs/hfsplus/hfsplus_fs.h +44
-0+{ +u32 table_size; +u32 table_start; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + +if (off < desc_size || (off &1 )) +return true; + +if (next_off <= off || + next_off > node->tree->node_size || + (next_off & 1)) +return true; + + table_size = ((u32 )node->num_recs +1 ) * rec_size; + table_start = node->tree->node_size - table_size; +if (next_off > table_start) +return true; + +return false; +} + +static inline +bool hfs_brec_len_invalid (struct hfs_bnode *node,u16 len) +{ +if (!node || !node->tree) +return true; + +return len ==0 || len > node->tree->node_size; +} + +static inline +void hfs_find_result_init (struct hfs_find_data *fd) +{ + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +} +
Quoted 4 lines
static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
Mostly, I don't see the critical issues in the patch. But some minor corrections are necessary. Meanwhile, let me run xfstests for the patch.
Thanks,
Slava.
Viacheslav Dubeyko
maintainerRe: [PATCH v5] hfsplus: validate B-tree record offset table
Quoted 518 lines · Viacheslav Dubeyko
Quoted 390 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node,
and
record offsets may be unordered, unaligned, outside the node, or point into
the offset table itself.Several B-tree helpers consume these on-disk fields before validating
them:hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range
that
overlaps the offset table. This can make the unlink/writeback path repeatedly callhfs_bnode_read_u16()with invalid offsets while holding the
HFS+ B-tree lock, producing a flood of "requested invalid offset" messages.
Other writeback workers then block ontree->tree_lockand the system
reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset
table. Reject record ranges that are unordered, unaligned, outside the
node, or overlapping the offset table. Reject invalid record indexes
before
reading their offset entries, and avoid decrementing an already- zeroleaf_count.Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
Changes in v5:
- Switch helpers to invalid checker and invert callers.
-hfs_brec_offsets_invalid(): Drop the redundant offset-table argument
since it is already covered by the offset-table overlap check and take
just the two neighboring record offsets (off andnext_off).
-hfs_brec_len_invalid(): reject a length againstnode_size.
- Usehfs_brec_len_invalid()for both length checks inhfs_bmap_get_map_page().
- Validate the record offset inhfs_bmap_free().
- Check the__hfs_brec_find()return code in [2] and [3]. [1] and
[4]
call
it to find the insertion slot for a new index key after a split, -
ENOENT is
one of expected, even-EINVALthe followinghfs_brec_insert()just
inserts
at slot 0 of a node already validated byhfs_bnode_find(), so it stays
in-bounds and cannot trigger the invalid-offset flood. Hence no check was
added.[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449Changes in v4:
- Renamehfs_find_reset()tohfs_find_result_init().
- Reset find result fields in__hfs_brec_find().
- Movenum_recsvalidation next to descriptor field initialization.
- Renamehfs_brec_range_valid()tohfs_brec_offpair_valid().
- UseU16_MAXfor invalid offset/len/keylen sentinels and update callers.
- Addhfs_brec_len_valid()to check validity of len/keylen.
- Handle invalid B-tree map record lengths inhfs_bmap_get_map_page()
andhfs_bmap_free().
- Return-EINVALinstead of-EIOfor invalid remove cursor/leaf_count
state.Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 14 ++++++--
fs/hfsplus/hfsplus_fs.h| 79
+++++++++++++++++++++++++++++++++++++++++5 files changed, 153 insertions(+), 32 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
fd->tree= tree;
fd->bnode= NULL;fs/hfsplus/bfind.c +1
-0+hfs_find_result_init (fd);ptr =
kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); if (!ptr)
return-ENOMEM;fs/hfsplus/bfind.c +1
-1@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen; int rec; int b, e; -int res; +int res = -ENOENT ;
BUG_ON(!rec_found);fs/hfsplus/bfind.c +4
-0+hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; +b = 0;
e =bnode->num_recs- 1;fs/hfsplus/bfind.c +0
-1- res = -ENOENT ;do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off); keylen =hfs_brec_keylen(bnode, rec);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {res =
-EINVAL;
goto fail;
}fs/hfsplus/bfind.c +2
-1@@ -130,7 +135,8 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, keylen) || + hfs_brec_len_invalid(bnode, len)) { res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +0
-0@@ -158,11 +164,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) __be32 data; int height, res;fs/hfsplus/bfind.c +1
-5- fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd);
tree =fd->tree;
if (fd->bnode)fs/hfsplus/bfind.c +0
-0@@ -274,7 +276,8 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {res =
-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (hfs_bnode_num_recs_invalid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1- for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--)
{fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct
hfs_btree
*tree, u32 num)
node->height=desc->height;
kunmap_local(desc);fs/hfsplus/bnode.c +3
-0+if (hfs_bnode_num_recs_invalid (node)) + goto node_error; +switch (
node->type) {
caseHFS_NODE_HEADER:
caseHFS_NODE_MAP:fs/hfsplus/bnode.c +0
-0@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct
hfs_btree
*tree, u32 num)
for (i = 1; i <=node->num_recs; off =next_off, i++) {rec_off-= 2;
next_off=hfs_bnode_read_u16(node, rec_off);fs/hfsplus/bnode.c +1
-3-if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (hfs_brec_offsets_invalid (node, off, next_off))goto
node_error;entry_size=next_off- off; if (node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +0
-0@@ -9,6 +9,8 @@* Handle individual btree records */ fs/hfsplus/brec.c +2
-0+#include <linux/limits.h> +#include "
hfsplus_fs.h"
#include "hfsplus_raw.h"fs/hfsplus/brec.c +0
-0@@ -20,41 +22,49 @@ static int hfs_btree_inc_height(struct
hfs_btree
*);
u16hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off){
__be16retval[2];fs/hfsplus/brec.c +7
-1-u16 dataoff; +u16 data_off; +u16 next_off; + +if (hfs_brec_record_invalid (node, rec)) { + *off =U16_MAX ; +return U16_MAX ; + }fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +6
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (hfs_brec_offsets_invalid (node, *off, next_off)) { + *off =U16_MAX ; +return U16_MAX ; + } +return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (hfs_brec_record_invalid (node, rec)) +return U16_MAX ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +3
-8- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); -return 0 ; - } + len =hfs_brec_lenoff (node, rec, &recoff); +if (hfs_brec_len_invalid (node, len)) +return len;
retval =hfs_bnode_read_u16(node, recoff)+ 2; if (retval >node->tree->max_key_len+ 2) {pr_err("keylen %d too large\n", retval);fs/hfsplus/brec.c +1
-1- retval =0 ; + retval =U16_MAX ;}
}
return retval;fs/hfsplus/brec.c +1
-0@@ -181,14 +191,20 @@ int hfs_brec_remove(struct hfs_find_data *fd) struct hfs_btree *tree; struct hfs_bnode *node, *parent; int end_off, rec_off, data_off, size; +int res;
tree =fd->tree;
node =fd->bnode;
again:fs/hfsplus/brec.c +3
-0+if (hfs_brec_record_invalid (node, fd->record)) +return -EINVAL ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EINVAL ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/brec.c +0
-0@@ -205,7 +221,9 @@ int hfs_brec_remove(struct hfs_find_data *fd) hfs_bnode_put(node); node = fd->bnode = parent;fs/hfsplus/brec.c +1
-1-__hfs_brec_find (node, fd, hfs_find_rec_by_key); + res = __hfs_brec_find(node, fd,
hfs_find_rec_by_key);fs/hfsplus/brec.c +2
-0+if (res && res != -ENOENT ) +return res;goto again;
}
hfs_bnode_write_u16(node,fs/hfsplus/brec.c +1
-0@@ -368,6 +386,7 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) int newkeylen, diff; int rec, rec_off, end_rec_off; int start_off, end_off; +int res;
tree =fd->tree;
node =fd->bnode;fs/hfsplus/brec.c +3
-1@@ -379,7 +398,9 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) parent = hfs_bnode_find(tree, node->parent); if (IS_ERR(parent)) return PTR_ERR(parent); -__hfs_brec_find (parent, fd, hfs_find_rec_by_key); + res =__hfs_brec_find (parent, fd, hfs_find_rec_by_key); +if (res && res != -ENOENT ) +return res; if (fd->record < 0) return -ENOENT;
hfs_bnode_dump(parent);fs/hfsplus/btree.c +0
-0@@ -168,8 +168,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, }
ctx->len=hfs_brec_lenoff(node, rec_idx, &off16);fs/hfsplus/btree.c +2
-2-if (!ctx->len) -return ERR_PTR (-ENOENT ); +if (hfs_brec_len_invalid (node, ctx->len)) +return ERR_PTR (-EINVAL );
if (!is_bnode_offset_valid(node, off16))
returnERR_PTR(-EIO);fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 626
Quoted 5 lines
fs/hfsplus/btree.c +2
-0@@ -622,6 +622,11 @@ void hfs_bmap_free(struct hfs_bnode *node) if (IS_ERR(node)) return; len = hfs_brec_lenoff(node, 2, &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid(node, off)) {If I am correct, the off value is never used. So, I think that this check is not necessary here. Am I right?
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 627
Quoted 1 line
fs/hfsplus/btree.c +1
-0+hfs_bnode_put (node);I think we cannot keep silence here. I believe that we should have the
error message for this case. Do you agree?fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 657
Quoted 11 lines
fs/hfsplus/btree.c +2
-0+return ; + } while (nidx >= len * 8) { u32 i;fs/hfsplus/btree.c +2
-0@@ -648,6 +653,11 @@ void hfs_bmap_free(struct hfs_bnode *node) return; } len = hfs_brec_lenoff(node, 0, &off); +if (hfs_brec_len_invalid (node, len) || + !is_bnode_offset_valid(node, off)) {Ditto.
fs/hfsplus/btree.c void hfs_bmap_free(struct hfs_bnode *node) · line 658
Quoted 1 line
fs/hfsplus/btree.c +1
-0+hfs_bnode_put (node);Ditto.
Quoted 94 lines
fs/hfsplus/btree.c +2
-0+return ; + } }
res =hfs_bmap_clear_bit(node, nidx);fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,85 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }fs/hfsplus/hfsplus_fs.h +35
-0+static inline +bool hfs_bnode_num_recs_invalid (struct hfs_bnode *node) +{ +u32 node_size; +u32 table_size; +u32 area_size; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + + node_size = node->tree->node_size; +if (node_size < desc_size) +return true; + + area_size = node_size - desc_size; + table_size = ((u32 )node->num_recs +1 ) * rec_size; + +return table_size > area_size; +} + +static inline +bool hfs_brec_record_invalid (struct hfs_bnode *node,int record) +{ +if (hfs_bnode_num_recs_invalid (node)) +return true; +if (record <0 ) +return true; + +return record >= node->num_recs; +} + +static inline +bool hfs_brec_offsets_invalid(struct hfs_bnode *node, u16 off, u16
next_off)fs/hfsplus/hfsplus_fs.h +44
-0+{ +u32 table_size; +u32 table_start; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + +if (off < desc_size || (off &1 )) +return true; + +if (next_off <= off || + next_off > node->tree->node_size || + (next_off & 1)) +return true; + + table_size = ((u32 )node->num_recs +1 ) * rec_size; + table_start = node->tree->node_size - table_size; +if (next_off > table_start) +return true; + +return false; +} + +static inline +bool hfs_brec_len_invalid (struct hfs_bnode *node,u16 len) +{ +if (!node || !node->tree) +return true; + +return len ==0 || len > node->tree->node_size; +} + +static inline +void hfs_find_result_init (struct hfs_find_data *fd) +{ + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +} +
Quoted 10 lines
Quoted 4 lines
static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{Mostly, I don't see the critical issues in the patch. But some minor corrections are necessary. Meanwhile, let me run xfstests for the patch.
The xfstests run was successful. The patch hasn't revealed any new issues. Please, rework the patch as requested.
Thanks,
Slava.
PATCH v6 1/1 hfsplus: validate B-tree record offset table
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and record offsets may be unordered, unaligned, outside the node, or point into the offset table itself.
Several B-tree helpers consume these on-disk fields before validating them:hfs_bnode_dump() can walk past the offset table when num_recs is corrupted, hfs_brec_lenoff() can produce an underflowed length or a record range that overlaps the offset table. This can make the unlink/writeback path repeatedly call hfs_bnode_read_u16() with invalid offsets while holding the HFS+ B-tree lock, producing a flood of "requested invalid offset" messages. Other writeback workers then block on tree->tree_lock and the system reports tasks hung in hfsplus_write_inode().
Validate num_recs against the node size before walking the record offset table. Reject record ranges that are unordered, unaligned, outside the node, or overlapping the offset table. Reject invalid record indexes before reading their offset entries, and avoid decrementing an already-zero leaf_count.
---
Changes in v6:
- hfs_bmap_free(): Drop offset checks and print error message when B-tree map record length is invalid.
Changes in v5:
- Switch helpers to invalid checker and invert callers.
- hfs_brec_offsets_invalid(): Drop the redundant offset-table argument since it is already covered by the offset-table overlap check and take just the two neighboring record offsets (off and next_off).
- hfs_brec_len_invalid(): reject a length against node_size.
- Use hfs_brec_len_invalid() for both length checks in hfs_bmap_get_map_page().
- Validate the record offset in hfs_bmap_free().
- Check the __hfs_brec_find() return code in [2] and [3]. [1] and [4] call it to find the insertion slot for a new index key after a split, -ENOENT is one of expected, even -EINVAL the following hfs_brec_insert() just inserts at slot 0 of a node already validated by hfs_bnode_find(), so it stays in-bounds and cannot trigger the invalid-offset flood. Hence no check was added.
[1] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4] https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449
Changes in v4:
- Rename hfs_find_reset() to hfs_find_result_init().
- Reset find result fields in __hfs_brec_find().
- Move num_recs validation next to descriptor field initialization.
- Rename hfs_brec_range_valid() to hfs_brec_offpair_valid().
- Use U16_MAX for invalid offset/len/keylen sentinels and update callers.
- Add hfs_brec_len_valid() to check validity of len/keylen.
- Handle invalid B-tree map record lengths in hfs_bmap_get_map_page() and hfs_bmap_free().
- Return -EINVAL instead of -EIO for invalid remove cursor/leaf_count state.
Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in __hfs_brec_find().
- Move find cursor reset into hfs_find_reset() and call it from hfs_find_init() and hfs_brec_find().
- Rename helper-local variables as suggested.
fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 16 +++++++-- fs/hfsplus/hfsplus_fs.h | 79 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 155 insertions(+), 32 deletions(-)
fs/hfsplus/bfind.c +13 -10
@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) fd->tree = tree; fd->bnode =NULL ; +hfs_find_result_init (fd); ptr =kzalloc (tree->max_key_len *2 +4 ,GFP_KERNEL );if (!ptr)return -ENOMEM ;
@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,u16 off, len, keylen;int rec;int b, e; -int res; +int res = -ENOENT ;BUG_ON (!rec_found); +hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; + b =0 ; e = bnode->num_recs -1 ; - res = -ENOENT ; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (hfs_brec_len_invalid(bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) { res = -EINVAL; goto fail; }
@@ -130,7 +135,8 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,if (rec != e && e >=0 ) { len =hfs_brec_lenoff (bnode, e, &off); keylen =hfs_brec_keylen (bnode, e); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, keylen) || +hfs_brec_len_invalid (bnode, len)) { res = -EINVAL ; goto fail; }
@@ -158,11 +164,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)__be32 data;int height, res; - fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd); tree = fd->tree;if (fd->bnode)
@@ -274,7 +276,8 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt) len =hfs_brec_lenoff (bnode, fd->record, &off); keylen =hfs_brec_keylen (bnode, fd->record); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || +hfs_brec_len_invalid (bnode, keylen)) { res = -EINVAL ; goto out; }
fs/hfsplus/bnode.c +12 -4
@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)struct hfs_bnode_desc desc;__be32 cnid;int i, off, key_off; +u16 num_recs;hfs_dbg ("node %d\n" , node->this);hfs_bnode_read (node, &desc,0 ,sizeof (desc)); + num_recs = node->num_recs;hfs_dbg ("next %d, prev %d, type %d, height %d, num_recs %d\n" ,be32_to_cpu (desc.next),be32_to_cpu (desc.prev), desc.type, desc.height,be16_to_cpu (desc.num_recs)); +if (hfs_bnode_num_recs_invalid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } + off = node->tree->node_size -2 ; -for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--) { +for (i = num_recs; i >=0 ; off -=2 , i--) { key_off =hfs_bnode_read_u16 (node, off);hfs_dbg (" key_off %d" , key_off);if (i && node->type ==HFS_NODE_INDEX ) {
@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height;kunmap_local (desc); +if (hfs_bnode_num_recs_invalid (node)) + goto node_error; +switch (node->type) {case HFS_NODE_HEADER :case HFS_NODE_MAP :
@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num)for (i =1 ; i <= node->num_recs; off = next_off, i++) { rec_off -=2 ; next_off =hfs_bnode_read_u16 (node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off &1 ) +if (hfs_brec_offsets_invalid (node, off, next_off)) goto node_error; entry_size = next_off - off; if (node->type != HFS_NODE_INDEX &&
fs/hfsplus/brec.c +37 -16
118 lines not on this page · raw message
fs/hfsplus/btree.c +14 -2
@@ -168,8 +168,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, } ctx->len =hfs_brec_lenoff (node, rec_idx, &off16); -if (!ctx->len) -return ERR_PTR (-ENOENT ); +if (hfs_brec_len_invalid (node, ctx->len)) +return ERR_PTR (-EINVAL );if (!is_bnode_offset_valid (node, off16))return ERR_PTR (-EIO );
@@ -622,6 +622,12 @@ void hfs_bmap_free(struct hfs_bnode *node)if (IS_ERR (node))return ; len =hfs_brec_lenoff (node,2 , &off); +if (hfs_brec_len_invalid (node, len)) { +pr_err ("invalid bmap record length: node %u, len %u\n" , + node->this, len); +hfs_bnode_put (node); +return ; + }while (nidx >= len *8 ) {u32 i;
@@ -648,6 +654,12 @@ void hfs_bmap_free(struct hfs_bnode *node)return ; } len =hfs_brec_lenoff (node,0 , &off); +if (hfs_brec_len_invalid (node, len)) { +pr_err ("invalid bmap record length: node %u, len %u\n" , + node->this, len); +hfs_bnode_put (node); +return ; + } } res =hfs_bmap_clear_bit (node, nidx);
fs/hfsplus/hfsplus_fs.h +79 -0
85 lines not on this page · raw message
Signature · 1 line
2.43.0
Re: [PATCH v6] hfsplus: validate B-tree record offset table
Quoted 136 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and
record offsets may be unordered, unaligned, outside the node, or point into
the offset table itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly callhfs_bnode_read_u16()with invalid offsets while holding the
HFS+ B-tree lock, producing a flood of "requested invalid offset" messages.
Other writeback workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset
table. Reject record ranges that are unordered, unaligned, outside the
node, or overlapping the offset table. Reject invalid record indexes before
reading their offset entries, and avoid decrementing an already-zeroleaf_count.Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
Changes in v6:
-hfs_bmap_free(): Drop offset checks and print error message when B- tree
map record length is invalid.Changes in v5:
- Switch helpers to invalid checker and invert callers.
-hfs_brec_offsets_invalid(): Drop the redundant offset-table argument
since it is already covered by the offset-table overlap check and take
just the two neighboring record offsets (off andnext_off).
-hfs_brec_len_invalid(): reject a length againstnode_size.
- Usehfs_brec_len_invalid()for both length checks inhfs_bmap_get_map_page().
- Validate the record offset inhfs_bmap_free().
- Check the__hfs_brec_find()return code in [2] and [3]. [1] and [4] call
it to find the insertion slot for a new index key after a split, - ENOENT is
one of expected, even-EINVALthe followinghfs_brec_insert()just inserts
at slot 0 of a node already validated byhfs_bnode_find(), so it stays
in-bounds and cannot trigger the invalid-offset flood. Hence no check was
added.[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449Changes in v4:
- Renamehfs_find_reset()tohfs_find_result_init().
- Reset find result fields in__hfs_brec_find().
- Movenum_recsvalidation next to descriptor field initialization.
- Renamehfs_brec_range_valid()tohfs_brec_offpair_valid().
- UseU16_MAXfor invalid offset/len/keylen sentinels and update callers.
- Addhfs_brec_len_valid()to check validity of len/keylen.
- Handle invalid B-tree map record lengths inhfs_bmap_get_map_page()andhfs_bmap_free().
- Return-EINVALinstead of-EIOfor invalid remove cursor/leaf_count state.Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 16 +++++++--
fs/hfsplus/hfsplus_fs.h| 79
+++++++++++++++++++++++++++++++++++++++++5 files changed, 155 insertions(+), 32 deletions(-)fs/hfsplus/bfind.c +0
-0@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
fd->tree= tree;
fd->bnode= NULL;fs/hfsplus/bfind.c +1
-0+hfs_find_result_init (fd);ptr =
kzalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); if (!ptr)
return-ENOMEM;fs/hfsplus/bfind.c +1
-1@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen; int rec; int b, e; -int res; +int res = -ENOENT ;
BUG_ON(!rec_found);fs/hfsplus/bfind.c +4
-0+hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; +b = 0;
e =bnode->num_recs- 1;fs/hfsplus/bfind.c +0
-1- res = -ENOENT ;do {
rec = (e + b) / 2;
len =hfs_brec_lenoff(bnode, rec, &off); keylen =hfs_brec_keylen(bnode, rec);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {
Quoted 3 lines
res =
-EINVAL;
goto fail;
}
I've realized that we have additional issue in HFS+ logic. Potentially, keylen and len could be not invalid but we could have negative value later in the logic:
done:
fd->record = e; fd->keyoffset = off; fd->keylength = keylen; fd->entryoffset = off + keylen; fd->entrylength = len - keylen; <-- negative value here.
The negative value of fd->entrylength is checked in multiple places. However, there is extents tree logic that has no such check [1]:
static int __hfsplus_ext_write_extent(struct inode *inode,
struct hfs_find_data *fd)
{
<skipped>
} else {
if (res)
return res;
hfs_bnode_write(fd->bnode, hip->cached_extents,
fd->entryoffset, fd->entrylength);
hip->extent_state &= ~HFSPLUS_EXT_DIRTY;
}<skipped>
}
Could you please double check my conclusion? We can fix the issue in another patch. Could you please fix the issue?
Quoted 355 lines
fs/hfsplus/bfind.c +2
-1@@ -130,7 +135,8 @@ int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, if (rec != e && e >= 0) { len = hfs_brec_lenoff(bnode, e, &off); keylen = hfs_brec_keylen(bnode, e); -if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, keylen) || + hfs_brec_len_invalid(bnode, len)) { res = -EINVAL; goto fail;}
fs/hfsplus/bfind.c +0
-0@@ -158,11 +164,7 @@ int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) __be32 data; int height, res;fs/hfsplus/bfind.c +1
-5- fd->record =-1 ; - fd->keyoffset =-1 ; - fd->keylength =-1 ; - fd->entryoffset =-1 ; - fd->entrylength =-1 ; +hfs_find_result_init (fd);
tree =fd->tree;
if (fd->bnode)fs/hfsplus/bfind.c +0
-0@@ -274,7 +276,8 @@ int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
len =hfs_brec_lenoff(bnode, fd->record, &off); keylen =hfs_brec_keylen(bnode, fd->record);fs/hfsplus/bfind.c +2
-1-if (keylen ==0 ) { +if (hfs_brec_len_invalid (bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) {res =
-EINVAL;
goto out;
}fs/hfsplus/bnode.c +1
-0@@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node) struct hfs_bnode_desc desc; __be32 cnid; int i, off, key_off; +u16 num_recs;
hfs_dbg("node %d\n", node->this);hfs_bnode_read(node, &desc, 0, sizeof(desc));fs/hfsplus/bnode.c +1
-0+ num_recs = node->num_recs;hfs_dbg("next %d, prev %d, type %d, height %d,
num_recs%d\n",
be32_to_cpu(desc.next),be32_to_cpu(desc.prev), desc.type, desc.height,be16_to_cpu(desc.num_recs));fs/hfsplus/bnode.c +5
-0+if (hfs_bnode_num_recs_invalid (node)) { +hfs_dbg ("invalid num_recs %u\n" , num_recs); +return ; + } +off =
node->tree->node_size- 2;fs/hfsplus/bnode.c +0
-1-for (i =be16_to_cpu (desc.num_recs); i >=0 ; off -=2 , i--){
fs/hfsplus/bnode.c +1
-0+for (i = num_recs; i >=0 ; off -=2 , i--) {
key_off=hfs_bnode_read_u16(node, off);hfs_dbg(" key_off %d", key_off); if (i &&node->type==HFS_NODE_INDEX) {fs/hfsplus/bnode.c +0
-0@@ -561,6 +568,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) node->height = desc->height; kunmap_local(desc);fs/hfsplus/bnode.c +3
-0+if (hfs_bnode_num_recs_invalid (node)) + goto node_error; +switch (
node->type) {
caseHFS_NODE_HEADER:
caseHFS_NODE_MAP:fs/hfsplus/bnode.c +1
-3@@ -586,9 +596,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num) for (i = 1; i <= node->num_recs; off = next_off, i++) { rec_off -= 2; next_off = hfs_bnode_read_u16(node, rec_off); -if (next_off <= off || - next_off > tree->node_size || - next_off & 1) +if (hfs_brec_offsets_invalid (node, off, next_off)) goto node_error; entry_size = next_off - off;if (
node->type!=HFS_NODE_INDEX&&fs/hfsplus/brec.c +0
-0@@ -9,6 +9,8 @@* Handle individual btree records */ fs/hfsplus/brec.c +2
-0+#include <linux/limits.h> +#include "
hfsplus_fs.h"
#include "hfsplus_raw.h"fs/hfsplus/brec.c +7
-1@@ -20,41 +22,49 @@ static int hfs_btree_inc_height(struct hfs_btree *); u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off) { __be16 retval[2]; -u16 dataoff; +u16 data_off; +u16 next_off; + +if (hfs_brec_record_invalid (node, rec)) { + *off =U16_MAX ; +return U16_MAX ; + }fs/hfsplus/brec.c +2
-2- dataoff = node->tree->node_size - (rec +2 ) *2 ; -hfs_bnode_read (node, retval, dataoff,4 ); + data_off = node->tree->node_size - (rec +2 ) *2 ; +hfs_bnode_read (node, retval, data_off,4 );*off =
be16_to_cpu(retval[1]);fs/hfsplus/brec.c +6
-1-return be16_to_cpu (retval[0 ]) - *off; + next_off =be16_to_cpu (retval[0 ]); +if (hfs_brec_offsets_invalid (node, *off, next_off)) { + *off =U16_MAX ; +return U16_MAX ; + } +return next_off - *off;}
/* Get the length of the key from a keyed record */ u16hfs_brec_keylen(struct hfs_bnode *node, u16 rec){fs/hfsplus/brec.c +1
-1-u16 retval, recoff; +u16 retval, recoff, len;
if (node->type!=HFS_NODE_INDEX&&node->type!=HFS_NODE_LEAF)
return 0;fs/hfsplus/brec.c +2
-0+if (hfs_brec_record_invalid (node, rec)) +return U16_MAX ;
if ((node->type==HFS_NODE_INDEX) && !(node->tree->attributes &HFS_TREE_VARIDXKEYS) && (node->tree->cnid!=HFSPLUS_ATTR_CNID)) { retval =node->tree->max_key_len+ 2; } else {fs/hfsplus/brec.c +3
-8- recoff =hfs_bnode_read_u16 (node, - node->tree->node_size - (rec +1 ) *2 ); -if (!recoff) -return 0 ; -if (recoff > node->tree->node_size -2 ) { -pr_err ("recoff %d too large\n" , recoff); -return 0 ; - } + len =hfs_brec_lenoff (node, rec, &recoff); +if (hfs_brec_len_invalid (node, len)) +return len;
retval =hfs_bnode_read_u16(node, recoff)+ 2; if (retval >node->tree->max_key_len+ 2) {pr_err("keylen %d too large\n", retval);fs/hfsplus/brec.c +1
-1- retval =0 ; + retval =U16_MAX ;}
}
return retval;fs/hfsplus/brec.c +1
-0@@ -181,14 +191,20 @@ int hfs_brec_remove(struct hfs_find_data *fd) struct hfs_btree *tree; struct hfs_bnode *node, *parent; int end_off, rec_off, data_off, size; +int res;
tree =fd->tree;
node =fd->bnode;
again:fs/hfsplus/brec.c +3
-0+if (hfs_brec_record_invalid (node, fd->record)) +return -EINVAL ; +
rec_off=tree->node_size- (fd->record+ 2) * 2;end_off=tree->node_size- (node->num_recs+ 1) * 2;
if (node->type==HFS_NODE_LEAF) {fs/hfsplus/brec.c +2
-0+if (tree->leaf_count ==0 ) +return -EINVAL ;tree->leaf_count--;
mark_inode_dirty(tree->inode);
}fs/hfsplus/brec.c +0
-0@@ -205,7 +221,9 @@ int hfs_brec_remove(struct hfs_find_data *fd) hfs_bnode_put(node); node = fd->bnode = parent;fs/hfsplus/brec.c +1
-1-__hfs_brec_find (node, fd, hfs_find_rec_by_key); + res = __hfs_brec_find(node, fd,
hfs_find_rec_by_key);fs/hfsplus/brec.c +2
-0+if (res && res != -ENOENT ) +return res;goto again;
}
hfs_bnode_write_u16(node,fs/hfsplus/brec.c +1
-0@@ -368,6 +386,7 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) int newkeylen, diff; int rec, rec_off, end_rec_off; int start_off, end_off; +int res;
tree =fd->tree;
node =fd->bnode;fs/hfsplus/brec.c +3
-1@@ -379,7 +398,9 @@ static int hfs_brec_update_parent(struct hfs_find_data *fd) parent = hfs_bnode_find(tree, node->parent); if (IS_ERR(parent)) return PTR_ERR(parent); -__hfs_brec_find (parent, fd, hfs_find_rec_by_key); + res =__hfs_brec_find (parent, fd, hfs_find_rec_by_key); +if (res && res != -ENOENT ) +return res; if (fd->record < 0) return -ENOENT;
hfs_bnode_dump(parent);fs/hfsplus/btree.c +0
-0@@ -168,8 +168,8 @@ static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, }
ctx->len=hfs_brec_lenoff(node, rec_idx, &off16);fs/hfsplus/btree.c +2
-2-if (!ctx->len) -return ERR_PTR (-ENOENT ); +if (hfs_brec_len_invalid (node, ctx->len)) +return ERR_PTR (-EINVAL );
if (!is_bnode_offset_valid(node, off16))
returnERR_PTR(-EIO);fs/hfsplus/btree.c +6
-0@@ -622,6 +622,12 @@ void hfs_bmap_free(struct hfs_bnode *node) if (IS_ERR(node)) return; len = hfs_brec_lenoff(node, 2, &off); +if (hfs_brec_len_invalid (node, len)) { + pr_err("invalid bmap record length: node %u, len %u\n", + node->this, len); +hfs_bnode_put (node); +return ; + } while (nidx >= len * 8) { u32 i;fs/hfsplus/btree.c +6
-0@@ -648,6 +654,12 @@ void hfs_bmap_free(struct hfs_bnode *node) return; } len = hfs_brec_lenoff(node, 0, &off); +if (hfs_brec_len_invalid (node, len)) { + pr_err("invalid bmap record length: node %u, len %u\n", + node->this, len); +hfs_bnode_put (node); +return ; + } }
res =hfs_bmap_clear_bit(node, nidx);fs/hfsplus/hfsplus_fs.h +0
-0@@ -587,6 +587,85 @@ bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off) return is_valid; }fs/hfsplus/hfsplus_fs.h +35
-0+static inline +bool hfs_bnode_num_recs_invalid (struct hfs_bnode *node) +{ +u32 node_size; +u32 table_size; +u32 area_size; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + + node_size = node->tree->node_size; +if (node_size < desc_size) +return true; + + area_size = node_size - desc_size; + table_size = ((u32 )node->num_recs +1 ) * rec_size; + +return table_size > area_size; +} + +static inline +bool hfs_brec_record_invalid (struct hfs_bnode *node,int record) +{ +if (hfs_bnode_num_recs_invalid (node)) +return true; +if (record <0 ) +return true; + +return record >= node->num_recs; +} + +static inline +bool hfs_brec_offsets_invalid(struct hfs_bnode *node, u16 off, u16
next_off)fs/hfsplus/hfsplus_fs.h +44
-0+{ +u32 table_size; +u32 table_start; +u32 rec_size =sizeof (__be16); +u32 desc_size =sizeof (struct hfs_bnode_desc ); + +if (!node || !node->tree) +return true; + +if (off < desc_size || (off &1 )) +return true; + +if (next_off <= off || + next_off > node->tree->node_size || + (next_off & 1)) +return true; + + table_size = ((u32 )node->num_recs +1 ) * rec_size; + table_start = node->tree->node_size - table_size; +if (next_off > table_start) +return true; + +return false; +} + +static inline +bool hfs_brec_len_invalid (struct hfs_bnode *node,u16 len) +{ +if (!node || !node->tree) +return true; + +return len ==0 || len > node->tree->node_size; +} + +static inline +void hfs_find_result_init (struct hfs_find_data *fd) +{ + fd->record =-1 ; + fd->keyoffset =-1 ; + fd->keylength =-1 ; + fd->entryoffset =-1 ; + fd->entrylength =-1 ; +} +
Quoted 4 lines
static inline
u32check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
{
Looks good.
[1]
https://elixir.bootlin.com/linux/v7.2-rc6/source/fs/hfsplus/extents.c#L113
Thanks,
Slava.
Re: [PATCH v6] hfsplus: validate B-tree record offset table
Quoted 170 lines · Viacheslav Dubeyko <[email protected]> 于2026年8月8日周六 08:49写道:
Quoted 138 lines · Jiaming Zhang
A crafted HFS+ image can contain a corrupted B-tree node. The node descriptor may contain a record count that does not fit in the node, and
record offsets may be unordered, unaligned, outside the node, or point into
the offset table itself.Several B-tree helpers consume these on-disk fields before validating them:
hfs_bnode_dump()can walk past the offset table whennum_recsis corrupted,hfs_brec_lenoff()can produce an underflowed length or a record range that
overlaps the offset table. This can make the unlink/writeback path repeatedly callhfs_bnode_read_u16()with invalid offsets while holding the
HFS+ B-tree lock, producing a flood of "requested invalid offset" messages.
Other writeback workers then block ontree->tree_lockand the system reports tasks hung inhfsplus_write_inode().Validate
num_recsagainst the node size before walking the record offset
table. Reject record ranges that are unordered, unaligned, outside the
node, or overlapping the offset table. Reject invalid record indexes before
reading their offset entries, and avoid decrementing an already-zeroleaf_count.Closes:
https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@mail.gmail.com/Assisted-by Codex:gpt-5.5-xhighSigned-off-by Jiaming Zhang <[email protected]>---
Changes in v6:
-hfs_bmap_free(): Drop offset checks and print error message when B- tree
map record length is invalid.Changes in v5:
- Switch helpers to invalid checker and invert callers.
-hfs_brec_offsets_invalid(): Drop the redundant offset-table argument
since it is already covered by the offset-table overlap check and
take
just the two neighboring record offsets (off andnext_off).
-hfs_brec_len_invalid(): reject a length againstnode_size.
- Usehfs_brec_len_invalid()for both length checks inhfs_bmap_get_map_page().
- Validate the record offset inhfs_bmap_free().
- Check the__hfs_brec_find()return code in [2] and [3]. [1] and [4] call
it to find the insertion slot for a new index key after a split, -
ENOENT is
one of expected, even-EINVALthe followinghfs_brec_insert()just
inserts
at slot 0 of a node already validated byhfs_bnode_find(), so it
stays
in-bounds and cannot trigger the invalid-offset flood. Hence no
check was
added.[1]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L160
[2]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L208
[3]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L382
[4]
https://elixir.bootlin.com/linux/v7.2-rc3/source/fs/hfsplus/brec.c#L449Changes in v4:
- Renamehfs_find_reset()tohfs_find_result_init().
- Reset find result fields in__hfs_brec_find().
- Movenum_recsvalidation next to descriptor field initialization.
- Renamehfs_brec_range_valid()tohfs_brec_offpair_valid().
- UseU16_MAXfor invalid offset/len/keylen sentinels and update callers.
- Addhfs_brec_len_valid()to check validity of len/keylen.
- Handle invalid B-tree map record lengths inhfs_bmap_get_map_page()andhfs_bmap_free().
- Return-EINVALinstead of-EIOfor invalid remove cursor/leaf_count state.Changes in v3:
- Drop the keylen == len check.
- Drop the explicit zero-record check in__hfs_brec_find().
- Move find cursor reset intohfs_find_reset()and call it fromhfs_find_init()andhfs_brec_find().
- Rename helper-local variables as suggested.fs/hfsplus/bfind.c | 23 ++++++------ fs/hfsplus/bnode.c | 16 ++++++--- fs/hfsplus/brec.c | 53 ++++++++++++++++++--------- fs/hfsplus/btree.c | 16 +++++++-- fs/hfsplus/hfsplus_fs.h | 79 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 155 insertions(+), 32 deletions(-)fs/hfsplus/bfind.c +1
-0@@ -18,6 +18,7 @@ int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) fd->tree = tree; fd->bnode =NULL ; +hfs_find_result_init (fd); ptr =kzalloc (tree->max_key_len *2 +4 ,GFP_KERNEL );if (!ptr)return -ENOMEM;fs/hfsplus/bfind.c +7
-3@@ -106,17 +107,21 @@ int __hfs_brec_find(struct hfs_bnode *bnode,struct hfs_find_data *fd, u16 off, len, keylen;int rec;int b, e; -int res; +int res = -ENOENT ;BUG_ON (!rec_found); +hfs_find_result_init (fd); +if (hfs_bnode_num_recs_invalid (bnode)) + goto fail; + b =0 ; e = bnode->num_recs -1 ; - res = -ENOENT ; do { rec = (e + b) / 2; len = hfs_brec_lenoff(bnode, rec, &off); keylen = hfs_brec_keylen(bnode, rec); - if (keylen == 0) { + if (hfs_brec_len_invalid(bnode, len) || + hfs_brec_len_invalid(bnode, keylen)) { res = -EINVAL; goto fail;Quoted 1 line
}I've realized that we have additional issue in HFS+ logic. Potentially, keylen and len could be not invalid but we could have negative value later in the logic:
done:
fd->record = e; fd->keyoffset = off; fd->keylength = keylen; fd->entryoffset = off + keylen; fd->entrylength = len - keylen; <-- negative value here.The negative value of
fd->entrylengthis checked in multiple places. However, there is extents tree logic that has no such check [1]:static int __hfsplus_ext_write_extent(struct inode *inode,
structhfs_find_data*fd)
{
<skipped>} else { if (res) return res; hfs_bnode_write(fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength); hip->extent_state &= ~HFSPLUS_EXT_DIRTY; }
Quoted 6 lines
<skipped>
}Could you please double check my conclusion? We can fix the issue in another patch. Could you please fix the issue?
I agree with your conclusion. A crafted image can keep both len and keylen valid but make fd->entrylength negative (i.e. keylen > len), which may lead to out-of-bound read and kernel memory leaking.
To fix this issue, we can check validity of fd->entrylength in __hfsplus_ext_write_extent() like the check in __hfsplus_ext_read_extent(). For example:
fs/hfsplus/extents.c +2 -0
@@ -110,6 +110,8 @@ static int __hfsplus_ext_write_extent(struct inode *inode, }else {if (res)return res; +if (fd->entrylength !=sizeof (hfsplus_extent_rec)) +return -EIO ;hfs_bnode_write (fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength); hip->extent_state &= ~HFSPLUS_EXT_DIRTY ;
Do you think this fix is acceptable? If so, I'm happy to send another patch.
Best Regards,
Jiaming Zhang
Viacheslav Dubeyko
maintainerRe: [PATCH v6] hfsplus: validate B-tree record offset table
Quoted 1 line · Jiaming Zhang
Quoted 1 line
<skipped>
Quoted 61 lines
Quoted 30 lines
I've realized that we have additional issue in HFS+ logic. Potentially,
keylen and len could be not invalid but we could have negative value
later in the logic:done:
fd->record= e;
fd->keyoffset= off;
fd->keylength= keylen;
fd->entryoffset= off + keylen;fd->entrylength= len - keylen; <-- negative value here.The negative value of
fd->entrylengthis checked in multiple places.
However, there is extents tree logic that has no such check [1]:static int
__hfsplus_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
{
<skipped>} else {
if (res)
return res;hfs_bnode_write(fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength);hip->extent_state&= ~HFSPLUS_EXT_DIRTY; }Quoted 7 lines
<skipped>
}Could you please double check my conclusion? We can fix the issue in
another patch. Could you please fix the issue?I agree with your conclusion. A crafted image can keep both len and keylen valid but make
fd->entrylengthnegative (i.e. keylen > len), which may lead to out-of-bound read and kernel memory leaking.To fix this issue, we can check validity of
fd->entrylengthin__hfsplus_ext_write_extent()like the check in__hfsplus_ext_read_extent(). For example:fs/hfsplus/extents.c +2
-0@@ -110,6 +110,8 @@ static int __hfsplus_ext_write_extent(structinode *inode, } else { if (res) return res; + if (fd->entrylength != sizeof(hfsplus_extent_rec)) + return -EIO; hfs_bnode_write(fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength);
hip->extent_state&= ~HFSPLUS_EXT_DIRTY;
Quoted 3 lines
Do you think this fix is acceptable? If so, I'm happy to send another patch.
As far as I can see, the fix makes sense.
Thanks,
Slava.
PATCH 1/1 hfsplus: validate extent record length before writing it back
__hfsplus_ext_write_extent() writes the cached extent record back into a B-tree node using fd->entrylength as the length, and fd->entrylength is derived in __hfs_brec_find() from two on-disk values:
fd->entrylength = len - keylen;
A crafted image can keep both len and keylen valid but make fd->entrylength negative (keylen > len). __hfsplus_ext_write_extent() doesn't check fd->entrylength before consuming it, and hfs_bnode_write() takes the length as u32, so the negative value turns into a huge one. The copy then reads data past the end of hip->cached_extents, which is only sizeof(hfsplus_extent_rec) bytes long, and leaks kernel memory into the image.
Reject an fd->entrylength that does not match sizeof(hfsplus_extent_rec) in __hfsplus_ext_write_extent(), mirroring the check already performed in __hfsplus_ext_read_extent().
--- fs/hfsplus/extents.c | 2 ++ 1 file changed, 2 insertions(+)
fs/hfsplus/extents.c +2 -0
@@ -110,6 +110,8 @@ static int __hfsplus_ext_write_extent(struct inode *inode, }else {if (res)return res; +if (fd->entrylength !=sizeof (hfsplus_extent_rec)) +return -EIO ;hfs_bnode_write (fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength); hip->extent_state &= ~HFSPLUS_EXT_DIRTY ;
Signature · 1 line
2.43.0
Re: [PATCH] hfsplus: validate extent record length before writing it back
Quoted 46 lines · Jiaming Zhang
__hfsplus_ext_write_extent()writes the cached extent record back into a
B-tree node usingfd->entrylengthas the length, andfd->entrylengthis
derived in__hfs_brec_find()from two on-disk values:fd->entrylength = len - keylen;A crafted image can keep both len and keylen valid but make fd-
Quoted 1 line
entrylength
negative (keylen > len).
__hfsplus_ext_write_extent()doesn't checkfd->entrylengthbefore consuming it, andhfs_bnode_write()takes the length
as u32, so the negative value turns into a huge one. The copy then reads
data past the end ofhip->cached_extents, which is onlysizeof(hfsplus_extent_rec)bytes long, and leaks kernel memory into the
image.Reject an
fd->entrylengththat does not matchsizeof(hfsplus_extent_rec)in__hfsplus_ext_write_extent(), mirroring the check already performed in__hfsplus_ext_read_extent().Link:
https://lore.kernel.org/lkml/[email protected]/Signed-off-by Jiaming Zhang <[email protected]>---
fs/hfsplus/extents.c | 2 ++1 file changed, 2 insertions(+)fs/hfsplus/extents.c +2
-0@@ -110,6 +110,8 @@ static int __hfsplus_ext_write_extent(structinode *inode, } else { if (res) return res; +if (fd->entrylength !=sizeof (hfsplus_extent_rec)) +return -EIO ; hfs_bnode_write(fd->bnode, hip->cached_extents, fd->entryoffset, fd->entrylength);
Quoted 1 line
hip->extent_state&= ~HFSPLUS_EXT_DIRTY;
Looks good.
Thanks,
Slava.