Message-ID: <7i2v6lkl7pd2jzk57omos6pqkgwooewrrztsvi5weibvod2f5b@3mkwqwzslyl4>
Date: Wed, 3 Dec 2025 10:54:17 -0800
From: Josh Poimboeuf <jpoimboe@...nel.org>
To: Ingo Molnar <mingo@...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()

On Wed, Dec 03, 2025 at 10:25:34AM +0100, Ingo Molnar wrote:
> * 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.

Is that number of loops or total stack frames?  With an allmodconfig
kernel and clang 20.1.8 I'm getting a max recursion depth of 7,165 loops
(not frames).  See the below patch for how I measured that.

> 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% ...

You may be underestimating the amount of memory usage objtool needs.
Running objtool on that binary with "/usr/bin/time -v" shows the maximum
resident set size is 140M.  So the stack usage of 5.5MB is only about
4.4% of the total memory usage.

Keep in mind this is a worst case function for objtool: KASAN with tons
of memory accesses.  The vast majority of functions won't come anywhere
near that level of recursion.

> 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.)

Objtool tracks a considerable amount of state across branches.  The
recursion works well for keeping that state at hand.  So there is a
certain level of dependency there which I have a feeling might be
difficult to extricate.  I haven't really looked at it though.

Here's how I measured the 7,000+ loops:

diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 3f7999317f4d..da9c43d84ddc 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -3694,6 +3694,8 @@ static int validate_branch(struct objtool_file *file, struct symbol *func,
 static int do_validate_branch(struct objtool_file *file, struct symbol *func,
 			      struct instruction *insn, struct insn_state state);
 
+int recurse_depth, max_recurse_depth;
+
 static int validate_insn(struct objtool_file *file, struct symbol *func,
 			 struct instruction *insn, struct insn_state *statep,
 			 struct instruction *prev_insn, struct instruction *next_insn,
@@ -3843,11 +3845,18 @@ static int validate_insn(struct objtool_file *file, struct symbol *func,
 			else
 				TRACE_INSN(insn, "jump taken");
 
+			recurse_depth++;
+
+			if (recurse_depth > max_recurse_depth)
+				max_recurse_depth = recurse_depth;
+
 			ret = validate_branch(file, func, insn->jump_dest, *statep);
 			if (ret) {
 				BT_INSN(insn, "(branch)");
 				return ret;
 			}
+
+			recurse_depth--;
 		}
 
 		if (insn->type == INSN_JUMP_UNCONDITIONAL)
@@ -5067,6 +5076,8 @@ int check(struct objtool_file *file)
 		printf("nr_cfi_cache: %ld\n", nr_cfi_cache);
 	}
 
+	WARN("max_recurse_depth = %d", max_recurse_depth);
+
 out:
 	if (ret || warnings) {
 		if (opts.werror && warnings)

Powered by blists - more mailing lists