Cache the dont_correlate() result once per symbol at the start of
correlate_symbols().  This reduces klp diff time on an arm64 LTO
vmlinux.o from 2m51s to 35s.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

Only create prefix symbols for functions that have
__patchable_function_entries entries, since those are the only C
functions where prefix NOPs are intentional.

This both simplifies the detection and makes it more accurate.

Note that assembly functions using SYM_TYPED_FUNC_START() can also have
prefixed NOPs, but that macro already creates their __cfi_ symbols.

Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

With CFI+CALL_PADDING, Clang places .Ltmp labels at the start of the NOP
padding (offset 5) between the __cfi_ prefix and the function entry
point.  get_func_prefix() only checks the immediately previous symbol,
so the intervening .Ltmp label causes it to miss the __cfi_ prefix
symbol.

This results in klp-diff not cloning the kCFI type hash into the
livepatch module, causing a CFI failure at module load when calling
callback functions through indirect calls:

  CFI failure at __klp_enable_patch+0xab/0x140
    (target: pre_patch_callback+0x0/0x80 [livepatch_combined];
     expected type: 0xde073954)

Instead of walking backward through the section's symbol list, just use
find_func_containing() for the byte before the function.  This works now
that __cfi_ symbols are being grown by objtool to fill the padding.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

For all CONFIG_CFI+CONFIG_CALL_PADDING configs, for C functions, the
__cfi_ symbols only cover the 5-byte kCFI type hash.  After that there
also N bytes of NOP padding between the hash and the function entry
which aren't associated with any symbol.

The NOPs can be replaced with actual code at runtime.  Without a symbol,
unwinders and tooling have no way of knowing where those bytes belong.

Grow the existing __cfi_* symbols to fill that gap.

Note that assembly functions with SYM_TYPED_FUNC_START() aren't affected
by this issue, their __cfi_ symbols also cover the padding.

Also, CONFIG_PREFIX_SYMBOLS has no reason to exist: CONFIG_CALL_PADDING
is what causes the compiler to emit NOP padding before function entry
(via -fpatchable-function-entry), so it's the right condition for
creating prefix symbols.

Remove CONFIG_PREFIX_SYMBOLS, as it's no longer needed.  Simplify the
LONGEST_SYM_KUNIT_TEST dependency accordingly.  Rework objtool's
arguments a bit to handle the variety of prefix/cfi-related cases.

Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

When computing klp checksums, instructions with non-relocated jump/call
destination offsets are problematic because the offset values can change
when surrounding code has moved, causing the function to be incorrectly
marked as changed.

Specifically, that includes jumps from alternatives to the end of the
alternative, which from objtool's perspective are jumps to the end of
the alternative instruction block in the original function.

Note that 'jump_dest' jumps don't include sibling calls (those use
call_dest), nor do they include jumps to/from .cold sub functions (those
are cross-section and need a reloc).

Fix it by hashing the opcode bytes (excluding the immediate operand)
along with a position-independent representation of the destination.
For calls, use the function name, and for jumps, use the destination's
offset within its function.

[Note the "9 bit hole" comment was wrong: it has been 8 bits since
commit 70589843b36f ("objtool: Add option to trace function validation")
added the 'trace' field.  Adding the 4-bit 'immediate_len' field now
leaves a 4-bit hole.]

Fixes: 0d83da43b1e1 ("objtool/klp: Add --checksum option to generate per-function checksums")
Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

Alternative replacement instructions awkwardly have insn->sym set to the
function they get patched to rather than the symbol (or rather lack
thereof) they belong to in the file.

This makes it difficult to know where a given instruction actually
lives.

Add a new insn_sym() helper which preserves the existing semantic of
insn->sym.  Rename insn->sym to insn->_sym, which contains the actual
ELF binary symbol (or NULL, for alternative replacements) an instruction
lives in.

The private insn->_sym value will be needed for a subsequent patch.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

Add debugging messages to show how duplicate symbols get correlated, and
split the --debug feature into --debug-correlate and --debug-clone.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

Rewrite the symbol correlation code, using a tiered list of
deterministic strategies in a loop.  For duplicately named symbols, each
tier applies a filter with the goal of finding a 1:1 deterministic
correlation between the original and patched version of the symbol.

The three matching strategies are:

  find_twin(): A funnel of progressively tighter filters.  Candidates
  with the same demangled name are counted at four levels: name, scope
  (local-vs-global), file (strict file association), and checksum
  (unchanged functions).  The widest level that yields a 1:1 match wins,
  narrower levels are only tried when the wider level is ambiguous.

  find_twin_suffixed(): Uses already-correlated LLVM symbol pairs to map
  .llvm.<hash> suffixes from orig to patched.  Because all promoted
  symbols from the same TU share the same hash, one correlated pair
  seeds the mapping for the entire TU.

  find_twin_positional(): Last resort, matches symbols by position among
  same-named candidates, similar to livepatch sympos.  Used for data
  objects like __quirk variables where no deterministic filter can
  distinguish the candidates.

Overall this works much better than the existing algorithm, particularly
with LTO kernels.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

Start checksumming data objects in preparation for revamping the
correlation algorithm.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>

The checksum functionality has been moved to "objtool klp checksum"
which is now used by klp-build.  Remove the now-dead --checksum and
--debug-checksum options from the default objtool command.

Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Josh Poimboeuf <jpoimboe@kernel.org>