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>

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>

Move the checksum functionality out of the main objtool command into a
new "objtool klp checksum" subcommand.

This has the benefit of making the code (and the patch generation
process itself) more modular.

For bisectability, both "objtool --checksum" and "objtool klp checksum"
work for now.  The former will be removed after klp-build has been
converted to use the new subcommand.

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

Add an is_cold_func() helper.  No functional changes intended.

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

Clang generates anonymous data sections named .data..Lanon.<hash>.
These need section-symbol references in the same way as .data..Lubsan
(GCC) and .data..L__unnamed_ (Clang UBSAN) sections.  Without this,
convert_reloc_sym() fails when processing relocations that reference
these sections.

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

Use the section symbol's index instead of the old symbol's index when
updating the ELF relocation entry in convert_reloc_sym_to_secsym().

Found by Sashiko review.

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

Clang aggregates UBSAN type descriptors into shared anonymous
.data..L__unnamed_* sections.  This data is used by UBSAN trap handlers.

When a changed function has an UBSAN bounds check, klp-diff clones the
entire UBSAN data section associated with the TU.  Relocations within
the cloned section that reference named rodata objects in .rodata.cst*
(like 'exponent', 'pirq_ali_set.irqmap') become KLP relocations because
those objects now get correlated.

That results in a .klp.rela.vmlinux..data section which can easily have
thousands of KLP relocs, most of which are completely superfluous, used
by functions which aren't cloned to the patch module.

The .rodata.cst* sections are SHF_MERGE constant pool sections
containing small fixed-size data (lookup tables, bitmasks) that is only
read by value.  Pointer identity is never relevant for these objects, so
correlating them is unnecessary.

Exclude .rodata.cst* objects from correlation so they get cloned as
local data instead of generating KLP relocations.

It might be possible to someday treat UBSAN data sections as special
sections, and only extract the few needed entries.  But this works for
now.

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

klp-diff treats all rodata as uncorrelated, so any reference to it uses
a duplicated copy rather than using a KLP reloc.

For the contents of the data itself, a duplicated copy is fine.
However, pointer comparisons (e.g., f->f_op == &foo_ops) are broken.

Fix it by correlating non-anonymous rodata objects.

Also, use a new find_symbol_containing_inclusive() helper for matching
the end of a symbol so bounds calculations don't get broken, for the
case where an array or other symbol's ending address is used as part of
a bounds calculation.

While these are really two distinct changes, they need to be done in the
same patch so as to avoid introducing bisection regressions.

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