Message-ID: <aTACDiRkMp_FzTX2@gmail.com>
Date: Wed, 3 Dec 2025 10:25:34 +0100
From: Ingo Molnar <mingo@...nel.org>
To: Josh Poimboeuf <jpoimboe@...nel.org>
Cc: x86@...nel.org, linux-kernel@...r.kernel.org,
	Nathan Chancellor <nathan@...nel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	Alexandre Chartre <alexandre.chartre@...cle.com>,
	David Laight <david.laight.linux@...il.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Re: [PATCH] objtool: Fix stack overflow in validate_branch()

* Josh Poimboeuf <jpoimboe@...nel.org> wrote:

> On Tue, Dec 02, 2025 at 05:20:22PM +0100, Ingo Molnar wrote:
> >
> > * Josh Poimboeuf <jpoimboe@...nel.org> wrote:
> >
> > > On an allmodconfig kernel compiled with Clang, objtool is
> > > segfaulting in drivers/scsi/qla2xxx/qla2xxx.o due to a stack
> > > overflow in validate_branch().
> > >
> > > Due in part to KASAN being enabled, the qla2xxx code has a large
> > > number of conditional jumps, causing objtool to go quite deep in
> > > its recursion.
> > >
> > > By far the biggest offender of stack usage is the recently added
> > > 'prev_state' stack variable in validate_insn(), coming in at 328
> > > bytes.
> >
> > That's weird - how can a user-space tool run into stack limits, are
> > they set particularly conservatively?
>
> On my Fedora system, "ulimit -s" is 8MB.  You'd think that would be
> enough :-)
>
> In this case, objtool had over 20,000 stack frames caused by
> recursively following over 7,000(!) conditional jumps in a single
> function.

BTW., I just instrumented it, and it's even worse: on current upstream,
the allmodconfig qla2xxx.o code built with clang-20.1.8 has a worst-case
recursion depth of 50,944 (!), for the qla83xx_fw_dump() function.

That function has 69,817 instructions and 14,645 branches.

BTW., beyond the better handling of the crash itself, we should IMO step
back and question whether a recursion depth of 50,000 is really necessary
and justified.

AFAICS the deep recursions mostly come from parsing long,
repetitive sequences of KASAN instrumentation intermixed with
conditional branches, such as:

	...
	1a0a4a:  qla83xx_fw_dump+0x1a18a                                jne    0x1c569a <qla83xx_fw_dump+0x3edda>
	...
	1a0a80:  qla83xx_fw_dump+0x1a1c0                                jne    0x1c56b7 <qla83xx_fw_dump+0x3edf7>
	...
	1a0ab6:  qla83xx_fw_dump+0x1a1f6                                jne    0x1c56d5 <qla83xx_fw_dump+0x3ee15>
	...
	1a0aec:  qla83xx_fw_dump+0x1a22c                                jne    0x1c56f2 <qla83xx_fw_dump+0x3ee32> ====> [1]
[2] ==>	1a0af2:  qla83xx_fw_dump+0x1a232                                mov    %r12d,0x1ed4(%rbp)
	...
	1a0b22:  qla83xx_fw_dump+0x1a262                                jne    0x1c5710 <qla83xx_fw_dump+0x3ee50>
	...
	1a0b58:  qla83xx_fw_dump+0x1a298                                jne    0x1c572d <qla83xx_fw_dump+0x3ee6d>
	...
	1a0b91:  qla83xx_fw_dump+0x1a2d1                                jne    0x1c574b <qla83xx_fw_dump+0x3ee8b>
	...
	1a0bc7:  qla83xx_fw_dump+0x1a307                                jne    0x1c5768 <qla83xx_fw_dump+0x3eea8>
	...
	1a0bfd:  qla83xx_fw_dump+0x1a33d                                jne    0x1c5786 <qla83xx_fw_dump+0x3eec6>
	...
	1a0c33:  qla83xx_fw_dump+0x1a373                                jne    0x1c57a3 <qla83xx_fw_dump+0x3eee3>
	...
	1a0c69:  qla83xx_fw_dump+0x1a3a9                                jne    0x1c57c1 <qla83xx_fw_dump+0x3ef01>
	...
	1a0c9f:  qla83xx_fw_dump+0x1a3df                                jne    0x1c57de <qla83xx_fw_dump+0x3ef1e>
	...
	1a0cd5:  qla83xx_fw_dump+0x1a415                                jne    0x1c57fc <qla83xx_fw_dump+0x3ef3c>
	...

Where each conditional jump target has a short, site specific trampoline:

[1] ==>	1c56f2:  qla83xx_fw_dump+0x3ee32                                mov    %r15d,%ecx
	1c56f5:  qla83xx_fw_dump+0x3ee35                                and    $0x7,%cl                                        [2]
	1c56f8:  qla83xx_fw_dump+0x3ee38                                add    $0x3,%cl                                         A
	1c56fb:  qla83xx_fw_dump+0x3ee3b                                cmp    %al,%cl                                          |
	1c56fd:  qla83xx_fw_dump+0x3ee3d                                jl     0x1a0af2 <qla83xx_fw_dump+0x1a232>  =============+
	1c5703:  qla83xx_fw_dump+0x3ee43                                mov    %r15,%rdi                                        |
	1c5706:  qla83xx_fw_dump+0x3ee46                                call   0x1c570b <__asan_report_store4_noabort>          |
	1c570b:  qla83xx_fw_dump+0x3ee4b                                jmp    0x1a0af2 <qla83xx_fw_dump+0x1a232>  ============='

Where objtool recurses into validate_insn() on every new branch
instruction found, due to:

  tools/objtool/check.c:validate_insn():

	...
        case INSN_JUMP_CONDITIONAL:
        case INSN_JUMP_UNCONDITIONAL:
        ...

                        ret = validate_branch(file, func, insn->jump_dest, *statep);
	...

While this flow and default parsing logic is correct and is guaranteed
to cover every instruction of a function eventually, it has several
disadvantages:

 - Note how it recurses deeper and deeper as it first parses the [1]
   conditional branch, then goes back with another new recursion via the
   [2] conditional branch in the trampoline.

 - It splits validation into two long passes, one where it sparsely
   skips forward thousands of times in the 1c56f2 trampoline range,
   then when finally the last branch is parsed, it returns and
   starts parsing the 'holes' in the trampoline area *in reverse*.

 - The stack footprint is ~5.5MB on my system, and the stack usage is
   disadvantageous as execution yo-yos up and down this large stack and
   moves parts of it in/out of the L1 data cache. qla2xxx.o is large at
   13MB, and the +5.5MB recursion stack footprint baloons its working
   set by at least +40% ...

I'm quite certain that this kind of 'sparse' instruction decoding where
objtool is merrily chasing and recursing after branches increases dcache
footprint unnecessarily and slows down overall execution, especially
with larger object files.

Ie. this looks like a self-inflicted wound by objtool.

One relatively simple method to 'straighten out' the parsing flow would
be to add an internal 'branch queue' with a limited size of say 16 or 32
entries, and defer the parsing of these branch targets and continue with
the next instruction, until one of these conditions is true:

  - 'branch queue' is full

  - JMP, CALL, RET or any other branching/trapping instruction is found

  - already validated instruction is found

  - end of symbol/section/file/etc.

At which point the current 'branch queue' is flushed. (It might even be
implemented as a branch-target stack, which may have a bit better
locality.)

I bet such an approach that does straight-line instruction parsing would
reduce the worst-case recursion depth to well below 100, from today's
50,000+, and might measurably speed up objtool as well as a side effect ...

Thoughts?

	Ingo

Powered by blists - more mailing lists