| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <lorwo3ywutxq5fr2xd22kzp5k4opnpn6md7zz2yl672tyovavu@ahxyf34v75hx>
Date: Wed, 3 Dec 2025 18:47:27 -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 08:11:54PM +0100, Ingo Molnar wrote:
> * Josh Poimboeuf <jpoimboe@...nel.org> wrote:
> > 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.
>
> I'm not against recursion for branches at all, I just suggest
> to change the order of how the recursion is fed: instead of parsing
> the two instruction streams of a branch point in this order:
>
> verify target recursively
> verify next instruction
>
> (Which is arguably the simplest.)
>
> I suggest the following recursion pattern:
>
> verify a batch of serial sequence of instruction(s) and save conditional branch targets (if any)
> verify saved branch targets, recursively
>
> This change to the recursion pattern should make a very large
> impact on max recursion depth, in addition to substantially better
> cache locality.
I implemented this (see below) and it seems to work ok. But it still
has some issues:
1) For each deferred branch, the 320-byte insn_state needs to be saved.
I suspect most of the savings in stack memory usage will just get
relocated to the heap.
2) It effectively breaks the objtool --backtrace option, which can be
useful to see which sequence of branches led to a certain state.
3) It's just kind of ugly compared to the elegance of the current
depth-first recursion (though I'm sure there are more elegant ways to
do a breadth-first traversal).
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 3f7999317f4d..d4f1d89c6ba6 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -27,6 +27,13 @@
#include <linux/static_call_types.h>
#include <linux/string.h>
+struct deferred_jump {
+ struct instruction *src;
+ struct instruction *dest;
+ struct insn_state state;
+ struct deferred_jump *next;
+};
+
static unsigned long nr_cfi, nr_cfi_reused, nr_cfi_cache;
static struct cfi_init_state initial_func_cfi;
@@ -3697,7 +3704,7 @@ static int do_validate_branch(struct objtool_file *file, struct symbol *func,
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,
- bool *dead_end)
+ bool *dead_end, struct instruction **defer_jump)
{
char *alt_name __maybe_unused = NULL;
struct alternative *alt;
@@ -3709,6 +3716,7 @@ static int validate_insn(struct objtool_file *file, struct symbol *func,
* ends, i.e. validate_branch() has reached the end of the branch.
*/
*dead_end = true;
+ *defer_jump = NULL;
visited = VISITED_BRANCH << statep->uaccess;
if (insn->visited & VISITED_BRANCH_MASK) {
@@ -3838,15 +3846,21 @@ static int validate_insn(struct objtool_file *file, struct symbol *func,
return ret;
} else if (insn->jump_dest) {
- if (insn->type == INSN_JUMP_UNCONDITIONAL)
+ if (insn->type == INSN_JUMP_UNCONDITIONAL) {
TRACE_INSN(insn, "unconditional jump");
- else
- TRACE_INSN(insn, "jump taken");
- ret = validate_branch(file, func, insn->jump_dest, *statep);
- if (ret) {
- BT_INSN(insn, "(branch)");
- return ret;
+ ret = validate_branch(file, func, insn->jump_dest, *statep);
+ if (ret) {
+ BT_INSN(insn, "(branch)");
+ return ret;
+ }
+ } else {
+ /*
+ * Do all fallthrough paths first, deferring
+ * conditional jumps to the end to minimize
+ * objtool stack recursion.
+ */
+ *defer_jump = insn->jump_dest;
}
}
@@ -3959,14 +3973,17 @@ static int validate_insn(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)
{
+ struct deferred_jump *deferred_list = NULL, *deferred, *tmp;
struct instruction *next_insn, *prev_insn = NULL;
bool dead_end;
- int ret;
+ int ret = 0;
if (func && func->ignore)
return 0;
do {
+ struct instruction *defer_jump;
+
insn->trace = 0;
next_insn = next_insn_to_validate(file, insn);
@@ -3976,20 +3993,20 @@ static int do_validate_branch(struct objtool_file *file, struct symbol *func,
if (func && insn_func(insn) && func != insn_func(insn)->pfunc) {
/* Ignore KCFI type preambles, which always fall through */
if (is_prefix_func(func))
- return 0;
+ break;
if (file->ignore_unreachables)
- return 0;
+ break;
WARN("%s() falls through to next function %s()",
func->name, insn_func(insn)->name);
func->warned = 1;
-
- return 1;
+ ret = 1;
+ goto cleanup;
}
ret = validate_insn(file, func, insn, &state, prev_insn, next_insn,
- &dead_end);
+ &dead_end, &defer_jump);
if (!insn->trace) {
if (ret)
@@ -3998,16 +4015,34 @@ static int do_validate_branch(struct objtool_file *file, struct symbol *func,
TRACE_INSN(insn, NULL);
}
+ if (ret)
+ goto cleanup;
+
+ if (defer_jump) {
+ deferred = malloc(sizeof(*deferred));
+ if (!deferred) {
+ ERROR_GLIBC("malloc");
+ ret = 1;
+ goto cleanup;
+ }
+ deferred->src = insn;
+ deferred->dest = defer_jump;
+ deferred->state = state;
+ deferred->next = deferred_list;
+ deferred_list = deferred;
+ }
+
if (!dead_end && !next_insn) {
if (state.cfi.cfa.base == CFI_UNDEFINED)
- return 0;
+ break;
if (file->ignore_unreachables)
- return 0;
+ break;
WARN("%s%sunexpected end of section %s",
func ? func->name : "", func ? "(): " : "",
insn->sec->name);
- return 1;
+ ret = 1;
+ goto cleanup;
}
prev_insn = insn;
@@ -4015,6 +4050,20 @@ static int do_validate_branch(struct objtool_file *file, struct symbol *func,
} while (!dead_end);
+ for (deferred = deferred_list; deferred; deferred = deferred->next) {
+ ret = validate_branch(file, func, deferred->dest, deferred->state);
+ if (ret) {
+ BT_INSN(deferred->src, "(branch)");
+ break;
+ }
+ }
+
+cleanup:
+ for (deferred = deferred_list; deferred; deferred = tmp) {
+ tmp = deferred->next;
+ free(deferred);
+ }
+
return ret;
}
Powered by blists - more mailing lists