From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A742429C326 for ; Wed, 3 Dec 2025 09:25:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764753939; cv=none; b=oxRpXPHeX4CG4Daqpg32NjNw7qNZZ+DdEGA/Ev2yXTinM6Ps6aRwXeKdZRabUR9Y1vwR+eoNcmgiadK+NHZWAwq8Rmpafkhg3Y9bZeS93Y+QOrmZvYDCt6IG0A8KUp5uShV1o3ga8HIclaFB/e1IEXXbVtXooiMTOT93EJ+geUU= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764753939; c=relaxed/simple; bh=wwfE+alUqJ9ZoNjTBjoMsLW+Ca5xtdiSMhZAzZCp1QE=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=CqVMmzsVeAp1AYt4r1mguTJYds0STEuonNGVPfe1R7nPUg7TMNfBhu7q/CxXSQeMtzGU/uyDBnp5mP8SxK6xZAfie3nN0aVpfCLyTokHVg11yfeMViRdG8+tCXSgT5K/iTIejT0LcYPey7hsZiGhC1gN8GbgYxE3/6+AKLvydXM= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=Fx6HtaUK; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="Fx6HtaUK" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 51B7FC4CEFB; Wed, 3 Dec 2025 09:25:37 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1764753939; bh=wwfE+alUqJ9ZoNjTBjoMsLW+Ca5xtdiSMhZAzZCp1QE=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Fx6HtaUKqcWaPyzYg5VjlCakcgjrstG2BtTbQrB3TRwWraghv4qRAVoBpavuOrIqu k59REY5NNNNKFTmDvPhv+7oClLFsA8a/QXDXR2RP1W9yInOk0CYbAdQF3vclQh7Szr eq1wSHNOfVcH2IAtn8fghhj2BJeyUZmUbk2OibJ8/QzCMlCMz5pm4u9Dy6HmamYd13 0VUGoFNfNoK3Rpy8QXgfSc1O+/18q61BmrVPw8dj4TOejyJGHvCGnR+RJ/yb18/zU/ GPY+uMDoSfLuMFf/vDGGBkALzeletwZUVwB+66GqorWX63PL/Ks+GDH+h0NnReN7Ua W5mrRwzZ1n78g== Date: Wed, 3 Dec 2025 10:25:34 +0100 From: Ingo Molnar To: Josh Poimboeuf Cc: x86@kernel.org, linux-kernel@vger.kernel.org, Nathan Chancellor , Peter Zijlstra , Alexandre Chartre , David Laight , Linus Torvalds Subject: Re: [PATCH] objtool: Fix stack overflow in validate_branch() Message-ID: References: <21bb161c23ca0d8c942a960505c0d327ca2dc7dc.1764691895.git.jpoimboe@kernel.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: * Josh Poimboeuf wrote: > On Tue, Dec 02, 2025 at 05:20:22PM +0100, Ingo Molnar wrote: > > > > * Josh Poimboeuf 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 ... 1a0a80: qla83xx_fw_dump+0x1a1c0 jne 0x1c56b7 ... 1a0ab6: qla83xx_fw_dump+0x1a1f6 jne 0x1c56d5 ... 1a0aec: qla83xx_fw_dump+0x1a22c jne 0x1c56f2 ====> [1] [2] ==> 1a0af2: qla83xx_fw_dump+0x1a232 mov %r12d,0x1ed4(%rbp) ... 1a0b22: qla83xx_fw_dump+0x1a262 jne 0x1c5710 ... 1a0b58: qla83xx_fw_dump+0x1a298 jne 0x1c572d ... 1a0b91: qla83xx_fw_dump+0x1a2d1 jne 0x1c574b ... 1a0bc7: qla83xx_fw_dump+0x1a307 jne 0x1c5768 ... 1a0bfd: qla83xx_fw_dump+0x1a33d jne 0x1c5786 ... 1a0c33: qla83xx_fw_dump+0x1a373 jne 0x1c57a3 ... 1a0c69: qla83xx_fw_dump+0x1a3a9 jne 0x1c57c1 ... 1a0c9f: qla83xx_fw_dump+0x1a3df jne 0x1c57de ... 1a0cd5: qla83xx_fw_dump+0x1a415 jne 0x1c57fc ... 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 =============+ 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 =============' 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