[PATCH v5 00/11] kbuild: significantly speed up kernel builds

[PATCH v5 00/11] kbuild: significantly speed up kernel builds

[Lorenzo Stoakes (ARM)]

A typical kernel build consists of a frustratingly large amount of time
spent stuck in single-threaded bottlenecks.

It turns out that there's a lot we can do about this and doing so
significantly impacts kernel build times.

This series makes allmodconfig builds up to 36% faster, incremental builds
up to ~70% faster, and noop builds up to ~90% faster.

Builds are faster across the board on every device I tested.

Machines used for perf testing:

* Threadripper -   x86, AMD Threadripper 9980X, 64 cores, 128 threads
* EPYC         -   x86, 2 socket EPYC 9754, 256 cores, 512 threads
* M2           - arm64, 2022 M2 macbook pro, 8 cores, 8 threads
                        (4 perf, 4 efficiency)

Cutting to the chase:

		== IMPORTANT NOTE on dependencies/build configuration ==

Performance numbers are based on a build which:

* Is based on v7.4-rc1, which contains the first 11 patches of v4 (see
  the Patches section).
* Was measured with these series applied (neither are required, but do
  shift the numbers by a few seconds):
	https://lore.kernel.org/linux-modules/20260731-module_ver_remove-v2-0-c9163858f382@linuxfoundation.org/
	https://lore.kernel.org/all/cover.1788899473.git.jpoimboe@kernel.org/
* Runs `make KRUSTFLAGS=-Zthreads=8 -j $(nproc) ...`.
* Runs with the pigz tool installed locally.

		== allmodconfig FULL build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc       344.2s   278.6s    -65.6s (-19%)
Threadripper, clang     342.6s   266.8s    -75.8s (-22%)
EPYC, gcc               188.0s   121.1s    -66.9s (-36%)
EPYC, clang             259.5s   184.6s    -74.9s (-29%)

		== allmodconfig INCREMENTAL build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc        40.1s    15.4s    -24.7s (-62%)
Threadripper, clang      40.3s    15.6s    -24.8s (-61%)
EPYC, gcc                70.9s    24.3s    -46.6s (-66%)
EPYC, clang              70.4s    24.3s    -46.1s (-65%)

		== allmodconfig NO-OP build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc        15.3s     1.4s    -13.9s (-91%)
Threadripper, clang      16.2s     1.8s    -14.4s (-89%)
EPYC, gcc                30.6s     1.5s    -29.1s (-95%)
EPYC, clang              32.3s     2.2s    -30.1s (-93%)

		== defconfig FULL build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc        32.5s    26.3s     -6.1s (-19%)
Threadripper, clang      34.5s    27.2s     -7.3s (-21%)
EPYC, gcc                28.7s    20.6s     -8.1s (-28%)
EPYC, clang              39.8s    32.2s     -7.6s (-19%)
M2, gcc			564.7s   512.1s    -52.6s (-9%)
M2, clang		615.1s   564.1s    -51.0s (-8%)

		== defconfig INCREMENTAL build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc        11.2s     6.0s     -5.3s (-47%)
Threadripper, clang      11.3s     5.4s     -5.9s (-52%)
EPYC, gcc                18.6s     9.2s     -9.4s (-51%)
EPYC, clang              19.6s     8.6s    -11.0s (-56%)
M2, gcc                  18.0s     9.9s     -8.1s (-45%)
M2, clang                18.1s     8.2s     -9.9s (-55%)

		== defconfig NO-OP build ==

                        before    after     delta
                      ----------------------------------
Threadripper, gcc         1.1s    0.60s    -0.50s (-45%)
Threadripper, clang       1.3s    0.66s    -0.63s (-49%)
EPYC, gcc                 1.7s    0.66s     -1.0s (-61%)
EPYC, clang               2.0s    0.80s     -1.2s (-60%)
M2, gcc                   6.4s     1.7s     -4.7s (-74%)
M2, clang                 7.1s     1.7s     -5.4s (-76%)

Further performance numbers are provided for each commit giving a sense of
what each contributes to the final result.

			== Testing ==

Beyond x86, allmodconfig was built with the series for arm64, arm, riscv,
powerpc64, s390 and loongarch, and for arm64, arm, s390 and loongarch the
System.map is identical to what the previous shell mksysmap produces for
the same vmlinux.

Also tested were parisc64 and m68k build as far as mainline lets them
(a driver's static assertion and an undefined-symbol check on parisc, gcc
16 internal compiler errors on m68k, none of it from this series).

Kernels for x86, arm64, arm, riscv, loongarch, powerpc64, s390, m68k and
parisc64 all boot under qemu, every text symbol of System.map is in
/proc/kallsyms at the relocated address, and a module loads and unloads.
The s390, arm and loongarch kernels also pass the kallsyms selftest.

An x86 kernel with CONFIG_MODVERSIONS, CONFIG_EXTENDED_MODVERSIONS and
CONFIG_MODULE_SRCVERSION_ALL boots, loads and unloads modules. External
modules build against both in-tree and O= builds, and every commit builds
on x86 defconfig.

Build times are the best of several runs, no unexpected errors or
warnings were seen.

While some aspects of the build process have been changed, all tooling
should function identically to before.

			== LLM usage ==

An LLM was used to first determine where the bottlenecks were then to
figure out how to improve them.

It generated a lot of code, much of it hideous.

I extensively audited and rewrote a lot of it, and heavily edited commit
messages, the cover letter and comments.

The LLM has also orchestrated build runs, testing, debugging and analysis.

I have manually checked for correctness in both build and running kernels
generated with this series applied.

Performance improvements were also verified manually.

Since an LLM was used extensively, each commit carries an Assisted-by tag.

			== What was changed? ==

Fundamentally the series improves build times by parallelising
single-threaded tasks as much as possible and improving the efficiency of
code used in the build process.

kbuild, kallsyms, modpost, objtool, mksysmap and the rust build system were
all updated as part of this change.

Nothing too controversial was included. There are further improvements that
could be made, but they would either by very invasive (large scale C header
changes) or generate diminishing returns.

                        == Patches ==

Patches marked [upstream] are already in v7.4-rc1.

   kbuild:           [upstream] Make .modinfo an INFO section.

   kallsyms:         [upstream] Some efficiency improvements through use of a
                     cache.

   sorttable:        [upstream] Parse nm output correctly, for the next patch.

   kbuild:           [upstream] Don't sort nm output unnecessarily, do not
                     include relocations in the kallsyms trial links.

   elf-parse:        [upstream] Section flags, symbol binding and a read-only
                     mapping, for the next patch.

   kallsyms:         [upstream] Don't use nm, read the ELF symbol table
                     directly.

   kbuild (1, 2):    Implement a cache to track objects, check dependency
                     timestamps more efficiently.

   kbuild:           [upstream] Move the toolchain checks into their own
                     Kconfig file.

   kbuild:           [upstream] Probe compiler, linker flags once at top of
                     build.

   modpost (3):      Improve performance through use of a cache.

   modules (4, 5):   Emit module descriptors as assembly (*.mod.S) rather
                     than C (*.mod.c), reducing CPU seconds taken by 10x to
                     perform the task. Also shard module finalisation
                     rather than running 10's of thousands of tiny runs.

   objtool (6-9):    Replace reloc hash with a per-section index, size
                     the instruction hash to the code rather than hard-code
                     it, and decode large objects over multiple threads.

   rust (10, 11):    Set correct dependencies and build crates in parallel
                     with C code, retaining the requirement that rust/
                     crates are built first.

   kbuild:           [upstream] Default to using a parallel implementation of
                     gzip (pigz) if available on the system.

---
v5:
* Rebased onto v7.4-rc1, which contains the cc-option-str series, so that
  is no longer a separate prerequisite.
* Dropped the first 11 patches of v4, taken by Nathan for 7.4-rc1.
* Dropped the Assisted-by: tags, as the kernel no longer uses them.
* Updated 3/11 (was 13/22) to keep the section mismatch cache in struct
  elf_info, alongside the existing symsearch cache, as per Petr.
* Updated 3/11 (was 13/22) to name the destination section index
  to_secndx in the cache helpers, as per Petr.
* Updated 3/11 (was 13/22) to take the elf_info first in
  get_section_mismatch() like the rest of modpost, as per Petr.
* Updated 4/11 (was 14/22) to fold the ksymtab string and flag emitters
  into add_asm_ksymtab(), as per Petr.
* Updated 4/11 (was 14/22) to inline export_is_kept() at its only call
  site, as per Petr.
* Updated 4/11 (was 14/22) to drop a const qualifier on a local, as per
  Petr.
* Updated 4/11 (was 14/22) so the extended version name loop uses
  skip_unversioned() rather than repeating its condition, as per Petr.
* Updated 4/11 (was 14/22) to shorten the module-offsets.c comment, as per
  Petr.
* Updated 4/11 (was 14/22) to remove the now unused MODULE_ARCH_INIT from
  include/linux/module.h and m68k, as per Petr.

v4:
* Added tags, thanks everybody!
* Fixed broken m2 numbers in cover letter as per Linus.
* Rebased onto 36d4a11b56aa as per Nathan, see
  https://git.kernel.org/pub/scm/linux/kernel/git/kbuild/linux.git/commit/?id=36d4a11b56aa
* Also rebased onto the cc-option-str series at
  https://lore.kernel.org/linux-kbuild/20260919005923.i.879-kees@kernel.org/
  as per Kees (impacts 12/22).
* Updated cover letter to declare these dependencies.
* Updated 1/22 to use /dev/null for objcopy output file, as per Kees.
* Updated 1/22 so the .modinfo dump no longer picks up the arch's image
  OBJCOPYFLAGS, as per Nicolas.
* Updated 2/22 to define NR_TOKENS for token count as per Kees.
* Updated 2/22 to Use ARRAY_SIZE() for token_profit iteration in
  find_best_token() as per Kees.
* Updated 2/22 to restore erroneously deleted comments as per Kees.
* Added 4/22, fixing an already-existing sorttable bug that didn't matter
  before but which the next patch can trigger in a problematic way, as
  vaguely kinda-reported by Sashiko (incorrect analysis, but right to query
  sorttable).
* Updated 6/22 to add a comment noting that --emit-relocs comes from
  link-vmlinux.sh, as per Kees.
* Updated 7/22 to provide elf_open_ro()/elf_close() and struct elf_file, as
  per Kees.
* Updated 7/22 to also handle the section 0 overflow case (SHN_XINDEX, zero
  e_shnum) in elf_open_ro() matching what sorttable does.
* Updated 8/22 to lay out omit tables one entry per line, resurrecting
  comments from the old mksysmap script, as per Kees.
* Updated 8/22 to add sysmap_omit_patterns[] rather than open-coding, as
  per Kees.
* Updated 8/22 to check ferror() before closing System.map output,
  as per Kees.
* Updated 8/22 to grow the kallsyms table by doubling rather than in fixed
  steps, as per Kees.
* Updated 8/22 to use the elf_file helper in elf-parse rather than
  open-coding it, as per Kees.
* Updated 9/22 to reword the commit message to say the object state is
  calculated rather than cached, as per Kees + Nicolas.
* Updated 10/22 to zero depcheck's dependency entries on allocation, as per
  Kees.
* Updated 10/22 to never treat targets in the dependency list as fresh, so
  that objects including a header regenerated in the same make run are
  rebuilt in the same run, as per Kees.
* Updated 10/22 so depcheck is not run for a non-existent directory/one
  that doesn't have .cmd files. Came up in a private tree kernel robot run
  for sh allnoconfig, as per kernel robot.
* Updated 11/22 to put the toolchain Kconfig entries in
  scripts/Kconfig.toolchain as per Kees, Nathan + Nicolas.
* Updated 11/22 to add scripts/Kconfig.toolchain to the KCONFIG entry in
  MAINTAINERS.
* Updated 12/22 to use Kees's new [cc, ld]-option-str functionality as per
  Kees and Nathan.
* Updated 12/22 to check negative options using the positive form, as gcc
  accepts unknown -Wno-xxx options without complaint, only warning later in
  the build. Came up in a private tree kernel robot run for arc, parisc
  randconfig's. As per kernel robot.
* Updated 14/22 to emit each export's ksymtab entry and CRC in one walk, as
  per Petr.
* Updated 14/22 to fold extended version emitters into one function, as per
  Petr.
* Updated 14/22 to fold dependency collection into add_asm_depends(), as
  per Petr.
* Updated 14/22 to add a weak __this_module symbol to module-common.c so
  debug info continues to be provided for it, as per Petr.
* Updated 17/22 to split the DWARF skipping in objtool into its own commit,
  as per Josh.
* Updated 17/22 to index out-of-order relocations over a sorted order
  rather than doing a linear scan, as per Josh.
* Updated 19/22 to rebuild dropped relocation index under a lock as a
  belts+braces measure (contention shouldn't actually happen).
* Updated 21/22 to add rust as a dependency to rustdoc and rusttest, as per
  kernel robot.
* Updated 22/22 (was 20/20) to add pigz to scripts/ver_linux as per Manuel
  (and previously I think Kees suggested it also? :)
https://lore.kernel.org/r/20260923-build-speedup-v4-0-73128809a4a4@kernel.org

v3:
* Rebased on Linus's master branch.
* Fixed link to Josh's series, which was wrongly pointing at a single
  commit as per Andre (off-list).
* Fixed typo in 11/20 (+ fixed a couple more), as per John.
* Hardened depcheck in 9/20 against a .cmd file with an empty name as per
  Sashiko.
* Updated 14/20 so only the top-level make instance builds .module-common.o
  the chunk instances treat it as a plain prerequisite, to prevent a child
  accidentally building it as per Sashiko.
* Updated 15/20 to drop the relocation hash altogether, building one
  section at a time incrementally, falling back to linear scan for anything
  out of order (not sure that'll ever happen though?) as per Josh, Linus.
* Updated 17/20 to limit the parallelisation to the --link step only (in
  practice - objtool's processing of vmlinux.o) + updated commit msg to
  reflect, as per Kees.
* Updated the commit message in 14/20 to give clearer rationales for the
  batching of modfinal instances, as per Kees.
* Dropped what was 18/21 - the rustc front end threading patch, as the
  parallel flag name is still uncertain and a user can set
  KRUSTFLAGS=-Zthreads=8 to get the behaviour without it. Also updated
  cover letter pre-requisite section to mention this, as per Miguel.
* Updated 19/20 (was 20/21) so modules_prepare no longer builds rust/
  when a goal that builds the tree is also given, ensuring duplicate rust/
  builds do not happen, as per Kees.
* Updated 20/20 (was 21/21) to remove the reproducible build doc update,
  as per Kees.
* Updated 20/20 (was 21/21) to have pigz use the make job server and to
  define a specific kernel build variable for this - KPGZIP - also fold
  in a further suggestion which eliminates a wrapper script, as per Kees.
https://lore.kernel.org/r/20260917-build-speedup-v3-0-9ecf4163ff36@kernel.org

v2:
* Rebased on Linus's master branch.
* Removed the first 2 fix patches as they have been taken to upstream in
  commit 281b61d408d4 ("scripts/mksysmap: drop the MODULE_INFO() symbols
  from kallsyms") and commit 59351365ac27 ("scripts/mksysmap: fix escape of
  '$' in the __pi_ pattern") - thanks Nicolas!
* Fixed patch 3/21 (previously 4/23) to check error on close via ferror()
  and fclose() as per David Laight.
* Updated 21/21 to not use threads for modules, only for vmlinux, and
  updated docs to reflect this.
* Dropped patches (as was) 13 and 17 as the equivalent work is being
  performed upstream:
  https://lore.kernel.org/linux-modules/20260731-module_ver_remove-v2-0-c9163858f382@linuxfoundation.org/
* Updated the cover letter to mention the dependency on this series for
  perf numbers.
* Fixed various typos.
* Checked all of the hallucinated sashiko reports. Replied inline to emails
  to keep a record of them but not going to repeat here, unless people want
  a list.
* Fixed up 9/21 (was 11/23) to fix the bit of sashiko's report that wasn't
  hallucinated - check ferror() to bring depcheck in line with fixdep and
  kallsyms.
* Fixed up patch 13/21 (was 15/23) to emit the __this_module fields in
  offset order to handle CONFIG_RANDSTRUCT as per Sashiko.
* Fixed up patch 19/23 (now 17/21) to resolve various races. Sashiko
  hallucinated a lot of the report, and missed some stuff thread sanitizer
  found. Resolve call destinations serially to resolve most of the valid
  stuff and add a lock around pv_ops, and instruction hash freed
  properly. Tested and confirmed resolved locally, as per Sashiko.
* Fixed up patch 20/21 (was 22/23) to only build rust/ when modules_prepare
  is one of several make goals, rather than the only one. This matches the
  rest of the Makefile's behaviour on this and ensures rust components are
  built if multiple build choices are passed to make, as per Sashiko.
* Fixed up patch 5/21 (was 6/23) to test CONFIG_ARCH_VMLINUX_NEEDS_RELOCS
  directly in link-vmlinux.sh rather than plumbing a var through, for a far
  smaller patch as per Nathan.
* Moved patch 1/21 (was 9/23) to the front of the series and dropped two
  comments, as per Nathan, so it can go in ahead of the rest.
* Added patch 10/21 moving the existing toolchain checks out of
  init/Kconfig into init/Kconfig.toolchain, as per Nathan, with 11/21
  adding to it.
* In 11/21 (previously 12/23) Moved -fno-stack-clash-protection back to
  the Makefile to fix an issue with ppc32 as per Nathan.
* Updated patch 15/21 (was 18/23) to drop the dead end cache as Josh has
  one in his noreturn series:
  https://lore.kernel.org/9d4b8ccfed745ac47a954aa2e1de62a85197122d.1788899473.git.jpoimboe@kernel.org
* Also updated patch 15/21 (was 18/23) to hash relocation sections objtool
  creates itself and moved cache-to-hash copy into elf_create_reloc(), as
  per Josh.
* Split the instruction hash sizing out of patch 17/21 (was 19/23) into its
  own patch 16/21, as per Josh.
* Made the rustc parallel front end opt-in in patch 18/21 (was 20/23) via
  KBUILD_RUST_THREADS, as its output is not yet reproducible, and dropped
  the probe for the planned -j flag, as per Björn, Miguel and Nicolas.
* Tested changes to ensure any flagged issues were resolved and that
  nothing broke.
* Did a re-run of profiling numbers to reflect changes and updated cover
  letter and commit messages.
https://lore.kernel.org/r/20260914-build-speedup-v2-0-39817ec5db23@kernel.org

v1:
https://lore.kernel.org/r/20260908-build-speedup-v1-0-5dc1ac01672d@kernel.org

---
Lorenzo Stoakes (ARM) (11):
      kbuild: calculate list, composite object state per object
      kbuild: implement and use depcheck to check dependency timestamps
      modpost: cache section relocation mismatch state
      modpost: emit module descriptors as assembly
      kbuild: batch module finalisation
      objtool: do not hash DWARF relocations
      objtool: cache relocations, do less work, eliminate relocation hash
      objtool: size the instruction hash to the text
      objtool: decode instructions and resolve branch targets in parallel
      rust: make exports.o depend on the headers generated for it
      kbuild: build rust crates in parallel with the rest of the build

 .gitignore                              |   1 +
 Kbuild                                  |   5 +
 Makefile                                |  22 +-
 arch/m68k/include/asm/module.h          |   6 -
 include/linux/module.h                  |   3 -
 include/linux/vermagic.h                |   2 +-
 rust/Makefile                           |   5 +
 scripts/Makefile.build                  |  28 +-
 scripts/Makefile.lib                    |   7 +-
 scripts/Makefile.modfinal               |  40 +-
 scripts/Makefile.modpost                |   2 +-
 scripts/basic/.gitignore                |   1 +
 scripts/basic/Makefile                  |   2 +-
 scripts/basic/depcheck.c                | 481 ++++++++++++++++++++
 scripts/mod/.gitignore                  |   1 +
 scripts/mod/Makefile                    |   8 +
 scripts/mod/modpost.c                   | 649 ++++++++++++++++++++-------
 scripts/mod/modpost.h                   |   8 +
 scripts/mod/module-offsets.c            |  32 ++
 scripts/module-common.c                 |   3 +
 scripts/tags.sh                         |   5 +-
 tools/objtool/Makefile                  |   2 +-
 tools/objtool/check.c                   | 771 ++++++++++++++++++++++++--------
 tools/objtool/elf.c                     | 271 +++++++++--
 tools/objtool/include/objtool/elf.h     |  10 +-
 tools/objtool/include/objtool/objtool.h |   3 +-
 tools/objtool/objtool.c                 |  15 +-
 27 files changed, 1949 insertions(+), 434 deletions(-)
---
base-commit: bc71431221f5ba8bb33918399552636e059c2c45
change-id: 20260904-build-speedup-25e11a00b3d0

Cheers,
-- 
Lorenzo Stoakes (ARM) <ljs@kernel.org>

[PATCH v5 01/11] kbuild: calculate list, composite object state per object

[Lorenzo Stoakes (ARM)]

When each object's command line is expanded, kbuild has to figure out on
multiple occasions whether it's built-in or part of a module and which
composite object it belongs to.

This causes the time spent on each directory in the kernel tree to grow
O(n^2) with its object count, which is especially problematic for instance
in drivers/gpu/drm/amd/amdgpu with 310 objects.

No-op builds (i.e. make -j $(nproc) when nothing has changed) are
particularly impacted by this.

Fix the issue by calculating this data once and looking it up thereafter
instead of recomputing it over and over again.

This has a particularly large impact on allmodconfig builds.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, no-op make, gcc            1.1s     1.1s    -0.02s (-2%)
  x86 defconfig, no-op make, clang          1.3s     1.3s    -0.01s (-1%)
  x86 allmodconfig, no-op make, gcc        15.3s    14.5s    -0.83s (-5%)
  x86 allmodconfig, no-op make, clang      16.2s    15.5s    -0.65s (-4%)
  x86 allmodconfig, touch mm/vma.c, gcc    35.0s    34.3s    -0.77s (-2%)
  x86 allmodconfig, touch mm/vma.c, clang  33.7s    33.2s    -0.51s (-2%)

Reviewed-by: Nicolas Schier <n.schier@fritz.com>
Reviewed-by: Kees Cook <kees@kernel.org>
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 scripts/Makefile.build | 8 ++++++++
 scripts/Makefile.lib   | 7 +++----
 2 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index 6127feb970c6..bbe9555c47a8 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -122,6 +122,14 @@ multi-obj-m	:= $(addprefix $(obj)/, $(multi-obj-m))
 subdir-ym	:= $(addprefix $(obj)/, $(subdir-ym))
 endif
 
+# Cache which list each object is in and which composite objects it belongs to,
+# once per object for $(part-of-builtin), $(part-of-module) and $(modname-multi).
+$(foreach o, $(real-obj-y) $(lib-y), $(eval part-of-builtin_$o := y))
+$(foreach o, $(real-obj-m), $(eval part-of-module_$o := y))
+$(foreach m, $(multi-obj-ym), \
+	$(foreach o, $(call suffix-search, $m, .o, -objs -y -m), \
+		$(eval modname-multi_$o += $(m:.o=))))
+
 ifndef obj
 $(warning kbuild: Makefile.build is included improperly)
 endif
diff --git a/scripts/Makefile.lib b/scripts/Makefile.lib
index 19e96b30a122..8936925d4d50 100644
--- a/scripts/Makefile.lib
+++ b/scripts/Makefile.lib
@@ -2,8 +2,7 @@
 
 # Finds the multi-part object the current object will be linked into.
 # If the object belongs to two or more multi-part objects, list them all.
-modname-multi = $(sort $(foreach m,$(multi-obj-ym),\
-		$(if $(filter $*.o, $(call suffix-search, $m, .o, -objs -y -m)),$(m:.o=))))
+modname-multi = $(sort $(modname-multi_$*.o))
 
 __modname = $(or $(modname-multi),$(basetarget))
 
@@ -149,8 +148,8 @@ endif
 # If $(is-kernel-object) is 'y', this object will be linked to vmlinux or modules
 is-kernel-object = $(or $(part-of-builtin),$(part-of-module))
 
-part-of-builtin = $(if $(filter $(basename $@).o, $(real-obj-y) $(lib-y)),y)
-part-of-module = $(if $(filter $(basename $@).o, $(real-obj-m)),y)
+part-of-builtin = $(part-of-builtin_$(basename $@).o)
+part-of-module = $(part-of-module_$(basename $@).o)
 quiet_modtag = $(if $(part-of-module),[M],   )
 
 modkern_cflags =                                          \

-- 
2.56.0

[PATCH v5 02/11] kbuild: implement and use depcheck to check dependency timestamps

[Lorenzo Stoakes (ARM)]

Each object's .cmd file lists its header dependencies, which often
consists of over a thousand dependencies.

When little has changed in the tree, this is what make spends most of its
time doing, spending over a second, single-threaded when parsing larger
directory trees.

It performs considerably more work that is actually necessary to get the
job done.

This can be done faster in C, so implement scripts/basic/depcheck to do so.

It does as little work as possible, reading the .cmd files from a
directory's targets and running stat on each dependency only a single time.

It generates a fragment holding only the saved command line for a target
whose dependencies all exist and are older than it, and the entire .cmd
file for any other.

A dependency that is also a target of the same directory (e.g. header
generated by an if_changed rule) may get remade later in the same make run,
so do not treat a target as fresh.

That way, Makefile.build simply includes the fragment and the amount of
work make has to do is significantly reduced when there is not much work to
do.

If the operation fails, kbuild falls back to using .cmd files.

The result is exactly the same as before.

For drivers/gpu/drm/amd/amdgpu in an allmodconfig tree the fragment is a
fifth of the size of the .cmd files, make reads it in 10ms instead of
380ms, and the instance goes from 2.2s to 0.4s.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, no-op make, gcc            1.1s    0.78s    -0.30s (-28%)
  x86 defconfig, no-op make, clang          1.3s    0.94s    -0.34s (-27%)
  x86 allmodconfig, no-op make, gcc        14.5s    12.9s     -1.6s (-11%)
  x86 allmodconfig, no-op make, clang      15.5s    14.2s     -1.3s (-9%)
  x86 allmodconfig, touch mm/vma.c, gcc    34.3s    33.9s    -0.33s (-1%)
  x86 allmodconfig, touch mm/vma.c, clang  33.2s    32.2s    -0.98s (-3%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 Makefile                 |   1 +
 scripts/Makefile.build   |  15 +-
 scripts/basic/.gitignore |   1 +
 scripts/basic/Makefile   |   2 +-
 scripts/basic/depcheck.c | 481 +++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 498 insertions(+), 2 deletions(-)

diff --git a/Makefile b/Makefile
index f895752d4b05..d92a5d78b465 100644
--- a/Makefile
+++ b/Makefile
@@ -2252,6 +2252,7 @@ clean: $(clean-dirs)
 	$(call cmd,rmfiles)
 	@find . $(RCS_FIND_IGNORE) \
 		\( -name '*.[aios]' -o -name '*.rsi' -o -name '*.ko' -o -name '.*.cmd' \
+		-o -name '.depcheck.mk' -o -name '.depcheck.mk.tmp' \
 		-o -name '*.ko.*' -o -name '*.o.thinlto.bc' \
 		-o -name '*.dtb' -o -name '*.dtbo' \
 		-o -name '*.dtb.S' -o -name '*.dtbo.S' \
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index bbe9555c47a8..7b652f169a8f 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -613,7 +613,20 @@ $(obj)/: $(if $(KBUILD_BUILTIN), $(targets-for-builtin)) \
 
 existing-targets := $(wildcard $(sort $(targets)))
 
--include $(foreach f,$(existing-targets),$(dir $(f)).$(notdir $(f)).cmd)
+cmd-files := $(wildcard $(foreach f,$(existing-targets),$(dir $(f)).$(notdir $(f)).cmd))
+
+# depcheck checks timestamps first and outputs only saved command lines of
+# up-to-date targets, falling back to .cmd files if it fails. A directory
+# whose targets all lie elsewhere may not exist in the output tree.
+depcheck := $(wildcard $(objtree)/scripts/basic/depcheck)
+
+ifneq ($(and $(depcheck),$(cmd-files),$(wildcard $(obj))),)
+ifeq ($(shell $(depcheck) $(obj)/.depcheck.mk $(cmd-files) && echo ok),ok)
+cmd-files := $(obj)/.depcheck.mk
+endif
+endif
+
+-include $(cmd-files)
 
 # Create directories for object files if they do not exist
 obj-dirs := $(sort $(patsubst %/,%, $(dir $(targets))))
diff --git a/scripts/basic/.gitignore b/scripts/basic/.gitignore
index 07c195f605a1..761ee14f9477 100644
--- a/scripts/basic/.gitignore
+++ b/scripts/basic/.gitignore
@@ -1,3 +1,4 @@
 # SPDX-License-Identifier: GPL-2.0-only
+/depcheck
 /fixdep
 /randstruct.seed
diff --git a/scripts/basic/Makefile b/scripts/basic/Makefile
index fb8e2c38fbc7..ff98780e474d 100644
--- a/scripts/basic/Makefile
+++ b/scripts/basic/Makefile
@@ -2,7 +2,7 @@
 #
 # fixdep: used to generate dependency information during build process
 
-hostprogs-always-y	+= fixdep
+hostprogs-always-y	+= fixdep depcheck
 
 # randstruct: the seed is needed before building the gcc-plugin or
 # before running a Clang kernel build.
diff --git a/scripts/basic/depcheck.c b/scripts/basic/depcheck.c
new file mode 100644
index 000000000000..119075353f3b
--- /dev/null
+++ b/scripts/basic/depcheck.c
@@ -0,0 +1,481 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * depcheck - check the dependency timestamps of a directory's targets so that
+ * make reads only what it needs from their .cmd files.
+ *
+ * fixdep writes a .cmd file as:
+ *
+ *	savedcmd_dir/foo.o := <command line>
+ *
+ *	source_dir/foo.o := dir/foo.c
+ *
+ *	deps_dir/foo.o := \
+ *	  include/linux/bar.h \
+ *	    $(wildcard include/config/BAZ) \
+ *
+ *	dir/foo.o: $(deps_dir/foo.o)
+ *
+ *	$(deps_dir/foo.o):
+ *
+ * and kbuild may append rules of its own after that, such as one making the
+ * target depend on objtool.
+ *
+ * For a target that exists and is newer than every dependency listed, make can
+ * have nothing to do with the list, so it is left out and only what precedes
+ * and follows it is passed on; for anything else the .cmd file is passed on in
+ * full.
+ *
+ * Usage: depcheck <output> <.cmd files...>
+ *
+ * The output is a makefile fragment to include in place of the .cmd files; a
+ * non-zero exit status means the caller should include those instead.
+ */
+#include <limits.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <time.h>
+#include <unistd.h>
+
+#include <hash.h>
+#include <hashtable.h>
+#include <xalloc.h>
+
+/* What fixdep writes, see above. */
+#define DEPS_PREFIX		"deps_"
+#define DEPS_RULE_PREFIX	"$(" DEPS_PREFIX
+#define RULE_SUFFIX		":"
+#define LINE_CONTINUATION	" \\"
+#define WILDCARD_OPEN		"$(wildcard "
+#define WILDCARD_CLOSE		")"
+#define CMD_SUFFIX		".cmd"
+
+/* A line of a .cmd file, without its newline. */
+struct line {
+	const char *text;
+	size_t len;
+};
+
+static bool is_blank(char chr)
+{
+	return chr == ' ' || chr == '\t';
+}
+
+static bool str_ends_with(const char *str, const char *suffix)
+{
+	const size_t len = strlen(str), suffix_len = strlen(suffix);
+
+	return len >= suffix_len && !strcmp(str + len - suffix_len, suffix);
+}
+
+static bool line_starts_with(const struct line *line, const char *prefix)
+{
+	const size_t len = strlen(prefix);
+
+	return line->len >= len && !memcmp(line->text, prefix, len);
+}
+
+static bool line_ends_with(const struct line *line, const char *suffix)
+{
+	const size_t len = strlen(suffix);
+
+	return line->len >= len &&
+	       !memcmp(line->text + line->len - len, suffix, len);
+}
+
+static bool line_is_blank(const struct line *line)
+{
+	size_t i;
+
+	for (i = 0; i < line->len; i++)
+		if (!is_blank(line->text[i]))
+			return false;
+
+	return true;
+}
+
+/* Whether the line ends in " \", continuing the list on the next line. */
+static bool line_is_continued(const struct line *line)
+{
+	return line_ends_with(line, LINE_CONTINUATION);
+}
+
+static void line_strip_continuation(struct line *line)
+{
+	if (line_is_continued(line))
+		line->len -= strlen(LINE_CONTINUATION);
+}
+
+static void line_trim(struct line *line)
+{
+	while (line->len && is_blank(line->text[0])) {
+		line->text++;
+		line->len--;
+	}
+	while (line->len && is_blank(line->text[line->len - 1]))
+		line->len--;
+}
+
+/* Take the next line out of [*pos, end); false once there are none left. */
+static bool next_line(const char **pos, const char *end, struct line *line)
+{
+	const char *newline;
+
+	if (*pos >= end)
+		return false;
+
+	newline = memchr(*pos, '\n', end - *pos);
+	line->text = *pos;
+	line->len = (newline ? newline : end) - *pos;
+	*pos = newline ? newline + 1 : end;
+
+	return true;
+}
+
+/* Describes a dependency file. */
+struct dep {
+	struct hlist_node hnode;
+	struct timespec mtime;
+	bool exists;
+	char path[];
+};
+
+static HASHTABLE_DEFINE(dep_table, 1U << 16);
+
+/* The targets of this run's .cmd files: anything make may remake this time. */
+struct target {
+	struct hlist_node hnode;
+	char path[];
+};
+
+static HASHTABLE_DEFINE(target_table, 1U << 12);
+
+static void add_target(const char *path)
+{
+	struct target *target = xmalloc(sizeof(*target) + strlen(path) + 1);
+
+	strcpy(target->path, path);
+	hash_add(target_table, &target->hnode, hash_str(path));
+}
+
+static bool is_target(const char *path)
+{
+	const unsigned int key = hash_str(path);
+	struct target *target;
+
+	hash_for_each_possible(target_table, target, hnode, key) {
+		if (!strcmp(target->path, path))
+			return true;
+	}
+
+	return false;
+}
+
+static const struct dep *lookup_dep(const char *path)
+{
+	const unsigned int key = hash_str(path);
+	struct dep *dep;
+	struct stat st;
+
+	hash_for_each_possible(dep_table, dep, hnode, key) {
+		if (!strcmp(dep->path, path))
+			return dep;
+	}
+
+	dep = xcalloc(1, sizeof(*dep) + strlen(path) + 1);
+	strcpy(dep->path, path);
+	dep->exists = !stat(path, &st);
+	if (dep->exists)
+		dep->mtime = st.st_mtim;
+	hash_add(dep_table, &dep->hnode, key);
+
+	return dep;
+}
+
+/* Strictly newer, as make compares timestamps. */
+static bool newer(const struct timespec *time_a, const struct timespec *time_b)
+{
+	if (time_a->tv_sec != time_b->tv_sec)
+		return time_a->tv_sec > time_b->tv_sec;
+
+	return time_a->tv_nsec > time_b->tv_nsec;
+}
+
+/*
+ * $(wildcard include/config/FOO) is a prerequisite only while FOO is set:
+ * unwrap it and say that it is optional.
+ */
+static bool line_unwrap_wildcard(struct line *line)
+{
+	if (!line_starts_with(line, WILDCARD_OPEN) ||
+	    !line_ends_with(line, WILDCARD_CLOSE))
+		return false;
+
+	line->text += strlen(WILDCARD_OPEN);
+	line->len -= strlen(WILDCARD_OPEN) + strlen(WILDCARD_CLOSE);
+
+	return true;
+}
+
+/* fixdep doubles '$' and escapes '#' in a path: undo that into path[]. */
+static bool unescape_path(const struct line *line, char *path, size_t size)
+{
+	size_t i, out_len = 0;
+
+	if (line->len >= size)
+		return false;
+
+	for (i = 0; i < line->len; i++) {
+		const char chr = line->text[i];
+		const char next_chr = i + 1 < line->len ? line->text[i + 1] : '\0';
+
+		if ((chr == '$' && next_chr == '$') || (chr == '\\' && next_chr == '#'))
+			i++;
+		path[out_len++] = line->text[i];
+	}
+	path[out_len] = '\0';
+
+	return true;
+}
+
+/* Is the path contained in line older than the target? */
+static bool dep_is_fresh(struct line line, const struct timespec *target)
+{
+	char path[PATH_MAX];
+	const struct dep *dep;
+	bool optional;
+
+	line_strip_continuation(&line);
+	line_trim(&line);
+	if (!line.len)
+		return false;
+
+	optional = line_unwrap_wildcard(&line);
+	if (!line.len || !unescape_path(&line, path, sizeof(path)))
+		return false;
+
+	/* A target can get 'remade' so its timestamp is meaningless. */
+	if (is_target(path))
+		return false;
+
+	dep = lookup_dep(path);
+	if (!dep->exists)
+		return optional;
+
+	return !newer(&dep->mtime, target);
+}
+
+/*
+ * Parse a dependency list which consists of one file per line and determine if
+ * all dependencies are 'fresh', i.e. older than the target.
+ */
+static bool deps_are_fresh(const char *pos, const char *end,
+			   const struct timespec *target)
+{
+	struct line line;
+
+	while (next_line(&pos, end, &line)) {
+		if (line_is_blank(&line))
+			return true;
+		if (!dep_is_fresh(line, target))
+			return false;
+		if (!line_is_continued(&line))
+			return true;
+	}
+
+	return true;
+}
+
+/*
+ * Find the "deps_" line in the input.
+ *
+ * On success returns true and *deps_off is set to its offset and *list is set
+ * to the list's own lines start or NULL if the line is not continued.
+ *
+ * Otherwise returns false if the prefix cannot be found.
+ */
+static bool find_deps(const char *buf, size_t len, size_t *deps_off,
+		      const char **list)
+{
+	const char *pos = buf, *end = buf + len;
+	struct line line;
+
+	while (next_line(&pos, end, &line)) {
+		if (!line_starts_with(&line, DEPS_PREFIX))
+			continue;
+
+		*deps_off = line.text - buf;
+		*list = line_is_continued(&line) ? pos : NULL;
+		return true;
+	}
+
+	return false;
+}
+
+/*
+ * Is this the target of a .cmd file, i.e. 'dir/.name.cmd names dir/name.'?
+ */
+static bool target_of(const char *cmd_path, char *target, size_t size)
+{
+	const char *slash = strrchr(cmd_path, '/');
+	const char *base = slash ? slash + 1 : cmd_path;
+	const size_t dir_len = base - cmd_path;
+	const size_t affix_len = strlen(".") + strlen(CMD_SUFFIX);
+	const size_t base_len = strlen(base);
+
+	if (base[0] != '.' || !str_ends_with(base, CMD_SUFFIX) ||
+	    base_len <= affix_len)
+		return false;
+
+	return snprintf(target, size, "%.*s%.*s", (int)dir_len, cmd_path,
+			(int)(base_len - affix_len), base + 1) < (int)size;
+}
+
+/*
+ * Does the .cmd file's target exists and is it newer than everything in its
+ * dependency list?
+ *
+ * Returns true if so and sets *deps_off to the start of the list, otherwise
+ * returns false.
+ */
+static bool target_is_fresh(const char *cmd_path, const char *buf, size_t len,
+			    size_t *deps_off)
+{
+	char target[PATH_MAX];
+	struct stat st;
+	const char *list;
+
+	if (!target_of(cmd_path, target, sizeof(target)) || stat(target, &st))
+		return false;
+	if (!find_deps(buf, len, deps_off, &list))
+		return false;
+	if (!list)
+		return true;
+
+	return deps_are_fresh(list, buf + len, &st.st_mtim);
+}
+
+static char *read_file(const char *path, size_t *len)
+{
+	FILE *file = fopen(path, "r");
+	struct stat st;
+	char *buf;
+	size_t nr_read = 0;
+
+	if (!file)
+		return NULL;
+	if (fstat(fileno(file), &st)) {
+		fclose(file);
+		return NULL;
+	}
+
+	buf = xmalloc(st.st_size + 1);
+	while (nr_read < (size_t)st.st_size) {
+		const size_t chunk = fread(buf + nr_read, 1, st.st_size - nr_read, file);
+
+		if (!chunk)
+			break;
+		nr_read += chunk;
+	}
+	fclose(file);
+
+	buf[nr_read] = '\0';
+	*len = nr_read;
+	return buf;
+}
+
+/*
+ * Find the end of the dependency block: the offset just past its closing
+ * "$(deps_x):" line. Anything after that was appended by kbuild and is not for
+ * us to judge. Returns len if the line cannot be found.
+ */
+static size_t deps_block_end(const char *buf, size_t len, size_t deps_off)
+{
+	const char *pos = buf + deps_off, *end = buf + len;
+	struct line line;
+
+	while (next_line(&pos, end, &line)) {
+		if (line_starts_with(&line, DEPS_RULE_PREFIX) &&
+		    line_ends_with(&line, RULE_SUFFIX))
+			return pos - buf;
+	}
+
+	return len;
+}
+
+/* The target is fresh: pass on everything but the dependency block. */
+static void write_without_deps(FILE *out, const char *buf, size_t len,
+			       size_t deps_off)
+{
+	const size_t tail_off = deps_block_end(buf, len, deps_off);
+
+	fwrite(buf, 1, deps_off, out);
+	fputc('\n', out);
+	fwrite(buf + tail_off, 1, len - tail_off, out);
+}
+
+/*
+ * Generate a fragment for make from one .cmd file - without the dependency
+ * block if the target is fresh, otherwise all of it.
+ */
+static void process(FILE *out, const char *cmd_path)
+{
+	size_t len, deps_off;
+	char *buf;
+
+	buf = read_file(cmd_path, &len);
+	if (!buf)
+		return;
+
+	if (target_is_fresh(cmd_path, buf, len, &deps_off))
+		write_without_deps(out, buf, len, deps_off);
+	else
+		fwrite(buf, 1, len, out);
+
+	free(buf);
+}
+
+int main(int argc, char **argv)
+{
+	char tmp_path[PATH_MAX];
+	FILE *out;
+	int i;
+
+	if (argc < 2) {
+		fprintf(stderr, "usage: %s <output> <.cmd files...>\n", argv[0]);
+		return 1;
+	}
+
+	if (snprintf(tmp_path, sizeof(tmp_path), "%s.tmp", argv[1]) >=
+	    (int)sizeof(tmp_path)) {
+		fprintf(stderr, "%s: path too long\n", argv[1]);
+		return 1;
+	}
+
+	out = fopen(tmp_path, "w");
+	if (!out) {
+		perror(tmp_path);
+		return 1;
+	}
+
+	for (i = 2; i < argc; i++) {
+		char target[PATH_MAX];
+
+		if (target_of(argv[i], target, sizeof(target)))
+			add_target(target);
+	}
+
+	for (i = 2; i < argc; i++)
+		process(out, argv[i]);
+
+	/* Write errors are latched in the stream, so one check at the end covers them all. */
+	if (ferror(out) || fclose(out) || rename(tmp_path, argv[1])) {
+		perror(argv[1]);
+		unlink(tmp_path);
+		return 1;
+	}
+
+	return 0;
+}

-- 
2.56.0

[PATCH v5 03/11] modpost: cache section relocation mismatch state

[Lorenzo Stoakes (ARM)]

For every relocation modpost invokes check_section_mismatch() to determine
whether there is any kind of mismatch between the source and destination,
and if so which classification applies.

Each time it does this it invokes section_mismatch() which iterates
through the sectioncheck[] array every time it's called.

When walked a relocation section the source is fixed and there aren't many
targets, so the same names are looked up over and over again.

Therefore cache not only mismatch categorisation but also whether a
mismatch even exists for a given section and look up the sections in the
cache.

Special indices (undefined, absolute, common) take the uncached path as
before.

This results in very significant speed ups for allmodconfig incremental
builds.

modpost is on the serial tail of every build that links vmlinux.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, touch mm/vma.c, gcc        8.5s     8.3s    -0.14s (-2%)
  x86 defconfig, touch mm/vma.c, clang      7.7s     7.6s    -0.13s (-2%)
  x86 allmodconfig, touch mm/vma.c, gcc    33.9s    29.4s     -4.5s (-13%)
  x86 allmodconfig, touch mm/vma.c, clang  31.9s    27.9s     -4.0s (-13%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 scripts/mod/modpost.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++--
 scripts/mod/modpost.h |  8 +++++++
 2 files changed, 67 insertions(+), 2 deletions(-)

diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index 75374c64b8cc..83caf29b4bf2 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -1155,12 +1155,62 @@ static void check_export_symbol(struct module *mod, struct elf_info *elf,
 			 name);
 }
 
+static void init_mismatch_cache(struct elf_info *elf)
+{
+	elf->mismatch_cache = xcalloc(elf->num_sections,
+				      sizeof(*elf->mismatch_cache));
+}
+
+static void reset_mismatch_cache(struct elf_info *elf)
+{
+	memset(elf->mismatch_cache, 0,
+	       elf->num_sections * sizeof(*elf->mismatch_cache));
+}
+
+static void free_mismatch_cache(struct elf_info *elf)
+{
+	free(elf->mismatch_cache);
+	elf->mismatch_cache = NULL;
+}
+
+static const struct sectioncheck
+*cache_mismatch(const struct elf_info *elf, unsigned int to_secndx,
+		const struct sectioncheck *mismatch)
+{
+	if (!mismatch) {
+		elf->mismatch_cache[to_secndx] = -1;
+		return NULL;
+	}
+
+	elf->mismatch_cache[to_secndx] = (mismatch - sectioncheck) + 1;
+	return mismatch;
+}
+
+static const struct sectioncheck *get_section_mismatch(const struct elf_info *elf,
+		const char *fromsec, unsigned int to_secndx)
+{
+	int cached;
+
+	if (to_secndx >= elf->num_sections)
+		return section_mismatch(fromsec, sec_name(elf, to_secndx));
+
+	cached = elf->mismatch_cache[to_secndx];
+	if (cached < 0)
+		return NULL;
+	if (cached > 0)
+		return &sectioncheck[cached - 1];
+
+	return cache_mismatch(elf, to_secndx,
+			      section_mismatch(fromsec, sec_name(elf, to_secndx)));
+}
+
 static void check_section_mismatch(struct module *mod, struct elf_info *elf,
 				   Elf_Sym *sym,
 				   unsigned int fsecndx, const char *fromsec,
 				   Elf_Addr faddr, Elf_Addr taddr)
 {
-	const char *tosec = sec_name(elf, get_secindex(elf, sym));
+	unsigned int to_secndx = get_secindex(elf, sym);
+	const char *tosec = sec_name(elf, to_secndx);
 	const struct sectioncheck *mismatch;
 
 	if (module_enabled && elf->export_symbol_secndx == fsecndx) {
@@ -1168,7 +1218,7 @@ static void check_section_mismatch(struct module *mod, struct elf_info *elf,
 		return;
 	}
 
-	mismatch = section_mismatch(fromsec, tosec);
+	mismatch = get_section_mismatch(elf, fromsec, to_secndx);
 	if (!mismatch)
 		return;
 
@@ -1445,6 +1495,8 @@ static void check_sec_ref(struct module *mod, struct elf_info *elf)
 {
 	int i;
 
+	init_mismatch_cache(elf);
+
 	/* Walk through all sections */
 	for (i = 0; i < elf->num_sections; i++) {
 		Elf_Shdr *sechdr = &elf->sechdrs[i];
@@ -1461,6 +1513,9 @@ static void check_sec_ref(struct module *mod, struct elf_info *elf)
 			if (match(secname, section_white_list))
 				continue;
 
+			/* Reset cache per-section. */
+			reset_mismatch_cache(elf);
+
 			start = sym_get_data_by_offset(elf, i, 0);
 			stop = start + sechdr->sh_size;
 
@@ -1472,6 +1527,8 @@ static void check_sec_ref(struct module *mod, struct elf_info *elf)
 					    start, stop);
 		}
 	}
+
+	free_mismatch_cache(elf);
 }
 
 static char *remove_dot(char *s)
diff --git a/scripts/mod/modpost.h b/scripts/mod/modpost.h
index 666beca685e4..7ba64fd894ef 100644
--- a/scripts/mod/modpost.h
+++ b/scripts/mod/modpost.h
@@ -160,6 +160,14 @@ struct elf_info {
 	Elf32_Word   *symtab_shndx_stop;
 
 	struct symsearch *symsearch;
+
+	/*
+	 * Section mismatch cache, indexed by destination section:
+	 *   0 - uncached.
+	 *  -1 - no mismatch.
+	 *  >0 - mismatch index + 1.
+	 */
+	int *mismatch_cache;
 };
 
 /* Accessor for sym->st_shndx, hides ugliness of "64k sections" */

-- 
2.56.0

[PATCH v5 04/11] modpost: emit module descriptors as assembly

[Lorenzo Stoakes (ARM)]

modpost generates a descriptor for every module in the form of a
<module>.mod.c file with .modinfo strings, the __this_module descriptor,
exported symbol tables and (with CONFIG_MODVERSIONS set), the CRC of
imported symbols.

These files are compiled like any other kernel C file with all of the
-include preamble, as well as including linux/module.h, header dependencies
generated by fixdep of a few hundred headers, an objtool run and if LTO is
being performed, a link is performed to generate native code.

On an x86-64 allmodconfig build 11,189 *.mod.c files are built, each
taking ~0.24s of CPU time to compile, and module finalisation as a whole
6,300 CPU seconds, or 64 seconds of wall time when run over 128 threads.

It also generates ~1.3 GiB of *.mod.o.cmd files that every subsequent build
has to read back.

Avoid all this by emitting the descriptors as assembly instead.

The layout required (size and alignment of struct module, struct
modversion_info, the module's name offsets, init, and exit fields and
whether the architecture uses PREL32 ksymtab references) can all be derived
from scripts/mod/module-offsets.h.

The fields of __this_module are emitted in offset order rather than
declaration order, as CONFIG_RANDSTRUCT shuffles struct module so the name,
init and exit fields can land anywhere.

An assembly file avoids all of the issues previously mentioned so this
conversion results in a very significant performance win on kernel build.

As a consequence of this change, since module-offsets.c includes
linux/module.h, scripts/mod is now built after the generated headers in
prepare0, rather than before.

Also update .gitignore and make clean to handle .mod.S files, but keep
.mod.c files there to ensure that users do not end up with untracked
changes/dirty trees after the change takes effect.

The sections were confirmed to be byte-for-byte identical to the C version
produced - each of .modinfo, .gnu.linkonce.this_module, __ksymtab*,
__ksymtab_strings, __kcrctab*, __kflagstab*, __versions,
__version_ext_crcs, __version_ext_names and their relocations - for all
8,135 modules of a clang allmodconfig build with CONFIG_COMPILE_TEST off
and CONFIG_MODVERSIONS, CONFIG_EXTENDED_MODVERSIONS and
CONFIG_MODULE_SRCVERSION_ALL on, and for a sample built with gcc.

What differs is what the compiler added around them: the __UNIQUE_ID_*
locals, the KASAN constructor for the .mod.c globals, and on x86 a
.note.gnu.property that the linker already drops from any module containing
an assembly file and the loader never reads.

None of these have any impact on the build, however.

The assembly carries no debug information, so in order to keep describing
__this_module in each module's debug information, define it weakly in
module-common.c too, in a section which the module link discards.

Nothing initialises struct module::arch from C any more, so
MODULE_ARCH_INIT is removed from include/linux/module.h and from m68k, the
only architecture that defined it.

x86_64 kernels built with gcc and clang, with CONFIG_MODVERSIONS,
CONFIG_EXTENDED_MODVERSIONS and CONFIG_MODULE_SRCVERSION_ALL, were booted,
every module and an external one loaded and unloaded, and the srcversions
checked against modinfo, i386 and arm64 defconfigs (gcc and clang) and a
ThinLTO build were also built as part of testing.

An x86_64 CONFIG_RANDSTRUCT_FULL build with clang, which places the name
field after init and exit, was checked the same way and produces the same
.gnu.linkonce.this_module sections and relocations as the C version.

On the x86_64 allmodconfig with clang 22, "make modules" with every
*.mod.o and *.ko deleted goes from 64.5s (6,306 CPU-s) to 28.5s (518
CPU-s).

A consequence of this change is that the make jobs are now so small that
make cannot dispatch them quick enough, however the next commit in the
series addresses this issue.

This impacts clean and no-op builds with a large number of modules most
noticeably.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 allmodconfig, no-op make, gcc        12.7s     2.3s    -10.4s (-82%)
  x86 allmodconfig, no-op make, clang      13.9s     2.8s    -11.2s (-80%)
  x86 allmodconfig, clean, gcc            342.6s   306.6s    -36.0s (-11%)
  x86 allmodconfig, clean, clang          340.1s   290.2s    -49.8s (-15%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 .gitignore                     |   1 +
 Makefile                       |   4 +-
 arch/m68k/include/asm/module.h |   6 -
 include/linux/module.h         |   3 -
 include/linux/vermagic.h       |   2 +-
 scripts/Makefile.modfinal      |  10 +-
 scripts/Makefile.modpost       |   2 +-
 scripts/mod/.gitignore         |   1 +
 scripts/mod/Makefile           |   8 +
 scripts/mod/modpost.c          | 588 +++++++++++++++++++++++++++++------------
 scripts/mod/module-offsets.c   |  32 +++
 scripts/module-common.c        |   3 +
 scripts/tags.sh                |   5 +-
 13 files changed, 481 insertions(+), 184 deletions(-)

diff --git a/.gitignore b/.gitignore
index f3efefe2db77..e54400fb781d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -39,6 +39,7 @@
 *.lzo
 *.mod
 *.mod.c
+*.mod.S
 *.o
 *.o.*
 *.patch
diff --git a/Makefile b/Makefile
index d92a5d78b465..7c254b8657a3 100644
--- a/Makefile
+++ b/Makefile
@@ -1413,8 +1413,8 @@ archprepare: outputmakefile archheaders archscripts scripts include/config/kerne
 	include/generated/rustc_cfg remove-stale-files
 
 prepare0: archprepare
-	$(Q)$(MAKE) $(build)=scripts/mod
 	$(Q)$(MAKE) $(build)=. prepare
+	$(Q)$(MAKE) $(build)=scripts/mod
 
 # All the preparing..
 prepare: prepare0
@@ -2259,7 +2259,7 @@ clean: $(clean-dirs)
 		-o -name '*.dt.yaml' -o -name 'dtbs-list' \
 		-o -name '*.dwo' -o -name '*.lst' \
 		-o -name '*.su' -o -name '*.mod' \
-		-o -name '.*.d' -o -name '.*.tmp' -o -name '*.mod.c' \
+		-o -name '.*.d' -o -name '.*.tmp' -o -name '*.mod.c' -o -name '*.mod.S' \
 		-o -name '*.lex.c' -o -name '*.tab.[ch]' \
 		-o -name '*.asn1.[ch]' \
 		-o -name '*.symtypes' -o -name 'modules.order' \
diff --git a/arch/m68k/include/asm/module.h b/arch/m68k/include/asm/module.h
index 36cb06cc03e6..e3af97a4322c 100644
--- a/arch/m68k/include/asm/module.h
+++ b/arch/m68k/include/asm/module.h
@@ -20,12 +20,6 @@ struct mod_arch_specific {
 
 #ifdef CONFIG_MMU
 
-#define MODULE_ARCH_INIT {				\
-	.fixup_start		= __start_fixup,	\
-	.fixup_end		= __stop_fixup,		\
-}
-
-
 #define m68k_fixup(type, addr)			\
 	"	.section \".m68k_fixup\",\"aw\"\n"	\
 	"	.long " #type "," #addr "\n"	\
diff --git a/include/linux/module.h b/include/linux/module.h
index 76f4f3596477..068dfc8f156c 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -582,9 +582,6 @@ struct module {
 	struct _ddebug_info dyndbg_info;
 #endif
 } ____cacheline_aligned __randomize_layout;
-#ifndef MODULE_ARCH_INIT
-#define MODULE_ARCH_INIT {}
-#endif
 
 #ifdef CONFIG_MODULES
 
diff --git a/include/linux/vermagic.h b/include/linux/vermagic.h
index 335c360d4f9b..09f05d02664c 100644
--- a/include/linux/vermagic.h
+++ b/include/linux/vermagic.h
@@ -3,7 +3,7 @@
 #define _LINUX_VERMAGIC_H
 
 #ifndef INCLUDE_VERMAGIC
-#error "This header can be included from kernel/module.c or *.mod.c only"
+#error "This header can be included from kernel/module.c or scripts/module-common.c only"
 #endif
 
 #include <generated/utsrelease.h>
diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
index 01a37ec872b9..75e9effdf02c 100644
--- a/scripts/Makefile.modfinal
+++ b/scripts/Makefile.modfinal
@@ -20,10 +20,14 @@ __modfinal: $(modules:%.o=%.ko)
 modname = $(notdir $(@:.mod.o=))
 part-of-module = y
 GCOV_PROFILE := n
-ccflags-remove-y := $(CC_FLAGS_CFI)
 
-%.mod.o: %.mod.c FORCE
-	$(call if_changed_rule,cc_o_c)
+# modpost lays the <module>.mod.S out completely (write_mod_S_file()), so it
+# needs only the assembler and no dependency tracking.
+quiet_cmd_as_mod_o = AS [M]  $@
+      cmd_as_mod_o = $(CC) $(_a_flags) $(modkern_aflags) -c -o $@ $<
+
+%.mod.o: %.mod.S FORCE
+	$(call if_changed,as_mod_o)
 
 .module-common.o: $(srctree)/scripts/module-common.c FORCE
 	$(call if_changed_rule,cc_o_c)
diff --git a/scripts/Makefile.modpost b/scripts/Makefile.modpost
index d7d45067d08b..eecf5f5c99b4 100644
--- a/scripts/Makefile.modpost
+++ b/scripts/Makefile.modpost
@@ -13,7 +13,7 @@
 # Stage 2 is handled by this file and does the following
 # 1) Find all modules listed in modules.order
 # 2) modpost is then used to
-# 3)  create one <module>.mod.c file per module
+# 3)  create one <module>.mod.S file per module
 # 4)  create one Module.symvers file with CRC for all exported symbols
 
 # Step 3 is used to place certain information in the module's ELF
diff --git a/scripts/mod/.gitignore b/scripts/mod/.gitignore
index 0465ec33c9bf..620ab4362094 100644
--- a/scripts/mod/.gitignore
+++ b/scripts/mod/.gitignore
@@ -1,5 +1,6 @@
 # SPDX-License-Identifier: GPL-2.0-only
 /devicetable-offsets.h
+/module-offsets.h
 /elfconfig.h
 /mk_elfconfig
 /modpost
diff --git a/scripts/mod/Makefile b/scripts/mod/Makefile
index c729bc936bae..fbd5099e0441 100644
--- a/scripts/mod/Makefile
+++ b/scripts/mod/Makefile
@@ -13,10 +13,18 @@ $(obj)/$(devicetable-offsets-file): $(obj)/devicetable-offsets.s FORCE
 
 targets += $(devicetable-offsets-file) devicetable-offsets.s
 
+module-offsets-file := module-offsets.h
+
+$(obj)/$(module-offsets-file): $(obj)/module-offsets.s FORCE
+	$(call filechk,offsets,__MODULE_OFFSETS_H__)
+
+targets += $(module-offsets-file) module-offsets.s
+
 # dependencies on generated files need to be listed explicitly
 
 $(obj)/modpost.o $(obj)/file2alias.o $(obj)/sumversion.o $(obj)/symsearch.o: $(obj)/elfconfig.h
 $(obj)/file2alias.o: $(obj)/$(devicetable-offsets-file)
+$(obj)/modpost.o: $(obj)/$(module-offsets-file)
 
 quiet_cmd_elfconfig = MKELF   $@
       cmd_elfconfig = $(obj)/mk_elfconfig < $< > $@
diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index 83caf29b4bf2..ba3ee96cd5f1 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -26,6 +26,7 @@
 #include <list.h>
 #include <xalloc.h>
 #include "modpost.h"
+#include "module-offsets.h"
 #include "../../include/linux/license.h"
 
 #define MODULE_NS_PREFIX "module:"
@@ -1915,39 +1916,6 @@ static void check_modname_len(struct module *mod)
 		mod_error(mod, "module name is too long\n");
 }
 
-/**
- * Header for the generated file
- **/
-static void add_header(struct buffer *b, struct module *mod)
-{
-	buf_printf(b, "#include <linux/module.h>\n");
-	buf_printf(b, "#include <linux/export-internal.h>\n");
-	buf_printf(b, "#include <linux/compiler.h>\n");
-	buf_printf(b, "\n");
-	buf_printf(b, "MODULE_INFO(name, KBUILD_MODNAME);\n");
-	buf_printf(b, "\n");
-	buf_printf(b, "__visible struct module __this_module\n");
-	buf_printf(b, "__section(\".gnu.linkonce.this_module\") = {\n");
-	buf_printf(b, "\t.name = KBUILD_MODNAME,\n");
-	if (mod->has_init)
-		buf_printf(b, "\t.init = init_module,\n");
-	if (mod->has_cleanup)
-		buf_printf(b, "#ifdef CONFIG_MODULE_UNLOAD\n"
-			      "\t.exit = cleanup_module,\n"
-			      "#endif\n");
-	buf_printf(b, "\t.arch = MODULE_ARCH_INIT,\n");
-	buf_printf(b, "};\n");
-
-	if (!external_module)
-		buf_printf(b, "\nMODULE_INFO(intree, \"Y\");\n");
-
-	if (strstarts(mod->name, "drivers/staging"))
-		buf_printf(b, "\nMODULE_INFO(staging, \"Y\");\n");
-
-	if (strstarts(mod->name, "tools/testing"))
-		buf_printf(b, "\nMODULE_INFO(test, \"Y\");\n");
-}
-
 static void add_exported_symbols(struct buffer *buf, struct module *mod)
 {
 	struct symbol *sym;
@@ -1985,123 +1953,6 @@ static void add_exported_symbols(struct buffer *buf, struct module *mod)
 	}
 }
 
-/**
- * Record CRCs for unresolved symbols, supporting long names
- */
-static void add_extended_versions(struct buffer *b, struct module *mod)
-{
-	struct symbol *s;
-
-	if (!extended_modversions)
-		return;
-
-	buf_printf(b, "\n");
-	buf_printf(b, "static const u32 ____version_ext_crcs[]\n");
-	buf_printf(b, "__used __section(\"__version_ext_crcs\") = {\n");
-	list_for_each_entry(s, &mod->unresolved_symbols, list) {
-		if (!s->module)
-			continue;
-		if (!s->crc_valid) {
-			mod_warn(mod, "symbol '%s' has no CRC!\n", s->name);
-			continue;
-		}
-		buf_printf(b, "\t0x%08x,\n", s->crc);
-	}
-	buf_printf(b, "};\n");
-
-	buf_printf(b, "static const char ____version_ext_names[]\n");
-	buf_printf(b, "__used __section(\"__version_ext_names\") =\n");
-	list_for_each_entry(s, &mod->unresolved_symbols, list) {
-		if (!s->module)
-			continue;
-		if (!s->crc_valid)
-			/*
-			 * We already warned on this when producing the crc
-			 * table.
-			 * We need to skip its name too, as the indexes in
-			 * both tables need to align.
-			 */
-			continue;
-		buf_printf(b, "\t\"%s\\0\"\n", s->name);
-	}
-	buf_printf(b, ";\n");
-}
-
-/**
- * Record CRCs for unresolved symbols
- **/
-static void add_versions(struct buffer *b, struct module *mod)
-{
-	struct symbol *s;
-
-	if (!basic_modversions)
-		return;
-
-	buf_printf(b, "\n");
-	buf_printf(b, "static const struct modversion_info ____versions[]\n");
-	buf_printf(b, "__used __section(\"__versions\") = {\n");
-
-	list_for_each_entry(s, &mod->unresolved_symbols, list) {
-		if (!s->module)
-			continue;
-		if (!s->crc_valid) {
-			mod_warn(mod, "symbol '%s' has no CRC!\n", s->name);
-			continue;
-		}
-		if (strlen(s->name) >= MODULE_NAME_LEN) {
-			if (extended_modversions) {
-				/* this symbol will only be in the extended info */
-				continue;
-			} else {
-				mod_error(mod, "too long symbol '%s'\n", s->name);
-				break;
-			}
-		}
-		buf_printf(b, "\t{ 0x%08x, \"%s\" },\n",
-			   s->crc, s->name);
-	}
-
-	buf_printf(b, "};\n");
-}
-
-static void add_depends(struct buffer *b, struct module *mod)
-{
-	struct symbol *s;
-	int first = 1;
-
-	/* Clear ->seen flag of modules that own symbols needed by this. */
-	list_for_each_entry(s, &mod->unresolved_symbols, list) {
-		if (s->module)
-			s->module->seen = s->module->is_vmlinux;
-	}
-
-	buf_printf(b, "\n");
-	buf_printf(b, "MODULE_INFO(depends, \"");
-	list_for_each_entry(s, &mod->unresolved_symbols, list) {
-		const char *p;
-		if (!s->module)
-			continue;
-
-		if (s->module->seen)
-			continue;
-
-		s->module->seen = true;
-		p = get_basename(s->module->name);
-		buf_printf(b, "%s%s", first ? "" : ",", p);
-		first = 0;
-	}
-	buf_printf(b, "\");\n");
-}
-
-static void add_srcversion(struct buffer *b, struct module *mod)
-{
-	if (mod->srcversion[0]) {
-		buf_printf(b, "\n");
-		buf_printf(b, "MODULE_INFO(srcversion, \"%s\");\n",
-			   mod->srcversion);
-	}
-}
-
 static void write_buf(struct buffer *b, const char *fname)
 {
 	FILE *file;
@@ -2186,30 +2037,434 @@ static void write_vmlinux_export_c_file(struct module *mod)
 	free(buf.p);
 }
 
-/* do sanity checks, and generate *.mod.c file */
-static void write_mod_c_file(struct module *mod)
+#if MOD_SIZEOF_LONG == 8
+#define MOD_PTR_DIRECTIVE	".quad"
+#else
+#define MOD_PTR_DIRECTIVE	".long"
+#endif
+
+/* See KSYM_FUNC() in include/linux/export-internal.h. */
+#if MOD_FUNC_PLABEL
+#define MOD_FUNC_PREFIX		"P%"
+#else
+#define MOD_FUNC_PREFIX		""
+#endif
+
+/* See __KSYM_ALIGN in include/linux/export-internal.h. */
+#if MOD_PREL32_RELOCATIONS || MOD_SIZEOF_LONG == 4
+#define KSYM_ALIGN		4
+#else
+#define KSYM_ALIGN		8
+#endif
+
+/* Append the body of an assembler string literal, escaped as needed. */
+static void buf_escaped(struct buffer *buf, const char *str)
 {
-	struct buffer buf = { };
-	struct module_alias *alias, *next;
-	char fname[PATH_MAX];
-	int ret;
+	unsigned char chr;
 
-	add_header(&buf, mod);
-	add_exported_symbols(&buf, mod);
-	add_versions(&buf, mod);
-	add_extended_versions(&buf, mod);
-	add_depends(&buf, mod);
+	while ((chr = *str++)) {
+		if (chr == '"' || chr == '\\')
+			buf_printf(buf, "\\%c", chr);
+		else if (isprint(chr))
+			buf_printf(buf, "%c", chr);
+		else
+			buf_printf(buf, "\\%03o", chr);
+	}
+}
 
-	buf_printf(&buf, "\n");
+static void buf_asciz(struct buffer *buf, const char *str)
+{
+	buf_printf(buf, "\t.asciz \"");
+	buf_escaped(buf, str);
+	buf_printf(buf, "\"\n");
+}
+
+/* The equivalent of MODULE_INFO(tag, info). */
+static void add_asm_modinfo(struct buffer *buf, const char *tag,
+			    const char *info)
+{
+	buf_printf(buf, "\t.section .modinfo,\"a\",%%progbits\n");
+	buf_printf(buf, "\t.asciz \"%s=", tag);
+	buf_escaped(buf, info);
+	buf_printf(buf, "\"\n");
+}
+
+/* See __KSYM_REF() in include/linux/export-internal.h. */
+static void add_asm_ksym_ref(struct buffer *buf, const char *prefix,
+			     const char *sym)
+{
+#if MOD_PREL32_RELOCATIONS
+	buf_printf(buf, "\t.long %s%s - .\n", prefix, sym);
+#else
+	buf_printf(buf, "\t" MOD_PTR_DIRECTIVE " %s%s\n", prefix, sym);
+#endif
+}
+
+/* The equivalent of KSYMTAB_FUNC()/KSYMTAB_DATA() and SYMBOL_FLAGS(). */
+static void add_asm_ksymtab(struct buffer *buf, const struct symbol *sym)
+{
+	const char *name = sym->name;
+
+	/* The name and namespace strings the entry refers to. */
+	buf_printf(buf, "\t.section \"__ksymtab_strings\",\"aMS\",%%progbits,1\n");
+	buf_printf(buf, "__kstrtab_%s:\n", name);
+	buf_asciz(buf, name);
+	buf_printf(buf, "__kstrtabns_%s:\n", name);
+	buf_asciz(buf, sym->namespace);
+	buf_printf(buf, "\t.previous\n");
+
+	buf_printf(buf, "\t.section \"___ksymtab+%s\", \"a\"\n", name);
+	buf_printf(buf, "\t.balign %d\n", KSYM_ALIGN);
+	buf_printf(buf, "__ksymtab_%s:\n", name);
+	add_asm_ksym_ref(buf, sym->is_func ? MOD_FUNC_PREFIX : "", name);
+	add_asm_ksym_ref(buf, "__kstrtab_", name);
+	add_asm_ksym_ref(buf, "__kstrtabns_", name);
+	buf_printf(buf, "\t.previous\n");
+
+	buf_printf(buf, "\t.section \"___kflagstab+%s\", \"a\"\n", name);
+	buf_printf(buf, "__flags_%s:\n", name);
+	buf_printf(buf, "\t.byte 0x%02x\n", get_symbol_flags(sym));
+	buf_printf(buf, "\t.previous\n");
+}
+
+/* The equivalent of SYMBOL_CRC(). */
+static void add_asm_crc(struct buffer *buf, const struct symbol *sym)
+{
+	buf_printf(buf, "\t.section \"___kcrctab+%s\",\"a\"\n", sym->name);
+	buf_printf(buf, "\t.balign 4\n");
+	buf_printf(buf, "__crc_%s:\n", sym->name);
+	buf_printf(buf, "\t.long 0x%08x\n", sym->crc);
+	buf_printf(buf, "\t.previous\n");
+}
+
+/* The exported symbols and, with modversions, their CRCs. */
+static void add_asm_exported_symbols(struct buffer *buf, struct module *mod)
+{
+	struct symbol *sym;
+
+	list_for_each_entry(sym, &mod->exported_symbols, list) {
+		if (trim_unused_exports && !sym->used)
+			continue;
+
+		add_asm_ksymtab(buf, sym);
+
+		if (!modversions)
+			continue;
+
+		if (!sym->crc_valid)
+			mod_warn(mod, "EXPORT symbol '%s' version generation failed, symbol will not be versioned.\n"
+				 "Is '%s' prototyped in <asm/asm-prototypes.h>?\n",
+				 sym->name, sym->name);
+		add_asm_crc(buf, sym);
+	}
+}
+
+/* Zero fill up to the offset. */
+static void asm_skip_to(struct buffer *buf, unsigned int *pos,
+			unsigned int offset)
+{
+	if (offset < *pos)
+		fatal("__this_module field at offset %u overlaps the previous one\n",
+		      offset);
+	if (offset > *pos)
+		buf_printf(buf, "\t.skip %u\n", offset - *pos);
+
+	*pos = offset;
+}
+
+/* A non-zero field of __this_module: its offset and the name or symbol in it. */
+struct this_module_field {
+	unsigned int offset;
+	bool is_name;
+	const char *value;
+};
+
+#define THIS_MODULE_MAX_FIELDS	5
+
+static int compare_field_offsets(const void *ptr_a, const void *ptr_b)
+{
+	const struct this_module_field *field_a = ptr_a, *field_b = ptr_b;
+
+	if (field_a->offset != field_b->offset)
+		return field_a->offset < field_b->offset ? -1 : 1;
+
+	return 0;
+}
+
+/*
+ * The fields of __this_module which are not zero, in offset order. The order
+ * is only known from module-offsets.h, CONFIG_RANDSTRUCT shuffles struct module.
+ */
+static unsigned int get_this_module_fields(const struct module *mod,
+					   const char *modname,
+					   struct this_module_field *fields)
+{
+	unsigned int nr_fields = 0;
+
+	fields[nr_fields++] = (struct this_module_field)
+		{ MOD_OFF_module_name, true, modname };
+	if (mod->has_init)
+		fields[nr_fields++] = (struct this_module_field)
+			{ MOD_OFF_module_init, false, MOD_FUNC_PREFIX "init_module" };
+#ifdef MOD_OFF_module_exit
+	if (mod->has_cleanup)
+		fields[nr_fields++] = (struct this_module_field)
+			{ MOD_OFF_module_exit, false, MOD_FUNC_PREFIX "cleanup_module" };
+#endif
+#ifdef MOD_OFF_module_arch_fixup_start
+	fields[nr_fields++] = (struct this_module_field)
+		{ MOD_OFF_module_arch_fixup_start, false, "__start_fixup" };
+	fields[nr_fields++] = (struct this_module_field)
+		{ MOD_OFF_module_arch_fixup_end, false, "__stop_fixup" };
+#endif
+	qsort(fields, nr_fields, sizeof(*fields), compare_field_offsets);
+
+	return nr_fields;
+}
+
+/* Emit one field of __this_module, returning its size. */
+static unsigned int add_asm_this_module_field(struct buffer *buf,
+					      const struct this_module_field *field)
+{
+	if (field->is_name) {
+		buf_printf(buf, "\t.ascii \"%s\"\n", field->value);
+		return strlen(field->value);
+	}
+
+	buf_printf(buf, "\t" MOD_PTR_DIRECTIVE " %s\n", field->value);
+	return MOD_SIZEOF_LONG;
+}
+
+/*
+ * The equivalent of:
+ *
+ *	__visible struct module __this_module __section(".gnu.linkonce.this_module")
+ *		= { .name = KBUILD_MODNAME, .init = init_module, .exit = cleanup_module };
+ *
+ * Everything not listed is zero, except the m68k fixup bounds in .arch.
+ */
+static void add_asm_this_module(struct buffer *buf, const struct module *mod,
+				const char *modname)
+{
+	struct this_module_field fields[THIS_MODULE_MAX_FIELDS];
+	unsigned int nr_fields = get_this_module_fields(mod, modname, fields);
+	unsigned int pos = 0, i;
+
+	buf_printf(buf, "\n\t.section .gnu.linkonce.this_module,\"aw\",%%progbits\n");
+	buf_printf(buf, "\t.balign %d\n", MOD_ALIGNOF_struct_module);
+	buf_printf(buf, "\t.globl __this_module\n");
+	buf_printf(buf, "\t.type __this_module, %%object\n");
+	buf_printf(buf, "\t.size __this_module, %d\n", MOD_SIZEOF_struct_module);
+	buf_printf(buf, "__this_module:\n");
+
+	for (i = 0; i < nr_fields; i++) {
+		asm_skip_to(buf, &pos, fields[i].offset);
+		pos += add_asm_this_module_field(buf, &fields[i]);
+	}
+
+	asm_skip_to(buf, &pos, MOD_SIZEOF_struct_module);
+}
+
+/*
+ * An unresolved symbol without a module is not versioned; one without a CRC
+ * cannot be, so warn about it unless the caller already has.
+ */
+static bool skip_unversioned(struct module *mod, const struct symbol *sym,
+			     bool silent)
+{
+	if (!sym->module)
+		return true;
+	if (sym->crc_valid)
+		return false;
+
+	if (!silent)
+		mod_warn(mod, "symbol '%s' has no CRC!\n", sym->name);
+	return true;
+}
+
+/* One struct modversion_info: the CRC, then the name padded to the end. */
+static void add_asm_version(struct buffer *buf, const struct symbol *sym)
+{
+	buf_printf(buf, "\t" MOD_PTR_DIRECTIVE " 0x%08x\n", sym->crc);
+	buf_printf(buf, "\t.ascii \"%s\"\n", sym->name);
+	buf_printf(buf, "\t.skip %zu\n", MOD_SIZEOF_struct_modversion_info -
+		   MOD_OFF_modversion_info_name - strlen(sym->name));
+}
+
+/*
+ * The equivalent of:
+ *
+ *	static const struct modversion_info ____versions[]
+ *	__used __section("__versions") = { { crc, "name" }, ... };
+ *
+ * for unresolved symbols.
+ */
+static void add_asm_versions(struct buffer *buf, struct module *mod)
+{
+	struct symbol *sym;
+
+	if (!basic_modversions)
+		return;
+
+	buf_printf(buf, "\n\t.section __versions,\"a\",%%progbits\n");
+	buf_printf(buf, "\t.balign %d\n", MOD_ALIGNOF_struct_modversion_info);
+	list_for_each_entry(sym, &mod->unresolved_symbols, list) {
+		if (skip_unversioned(mod, sym, false))
+			continue;
+
+		if (strlen(sym->name) >= MOD_NAME_LEN) {
+			/* Only the extended table can hold it. */
+			if (extended_modversions)
+				continue;
+
+			mod_error(mod, "too long symbol '%s'\n", sym->name);
+			break;
+		}
+
+		add_asm_version(buf, sym);
+	}
+}
+
+/*
+ * The equivalent of:
+ *	static const u32 ____version_ext_crcs[] __section("__version_ext_crcs") = { crc, ... };
+ *	static const char ____version_ext_names[] __section("__version_ext_names") = "name\0" ...;
+ *
+ * for unresolved symbols.
+ */
+static void add_asm_extended_versions(struct buffer *buf, struct module *mod)
+{
+	struct symbol *sym;
+
+	if (!extended_modversions)
+		return;
+
+	buf_printf(buf, "\n\t.section __version_ext_crcs,\"a\",%%progbits\n");
+	buf_printf(buf, "\t.balign 4\n");
+	list_for_each_entry(sym, &mod->unresolved_symbols, list) {
+		if (skip_unversioned(mod, sym, false))
+			continue;
+
+		buf_printf(buf, "\t.long 0x%08x\n", sym->crc);
+	}
+
+	/* The names must line up with the CRCs, which already warned. */
+	buf_printf(buf, "\t.section __version_ext_names,\"a\",%%progbits\n");
+	list_for_each_entry(sym, &mod->unresolved_symbols, list) {
+		if (skip_unversioned(mod, sym, true))
+			continue;
+
+		buf_asciz(buf, sym->name);
+	}
+	/* The terminator of the string literal this used to be. */
+	buf_printf(buf, "\t.byte 0\n");
+}
+
+/* MODULE_INFO(depends, ...): the modules this one needs, each once. */
+static void add_asm_depends(struct buffer *buf, struct module *mod)
+{
+	struct buffer deps = { };
+	struct symbol *sym;
+	bool first = true;
+
+	/* Clear ->seen of the modules that own symbols this one needs. */
+	list_for_each_entry(sym, &mod->unresolved_symbols, list) {
+		if (sym->module)
+			sym->module->seen = sym->module->is_vmlinux;
+	}
+
+	list_for_each_entry(sym, &mod->unresolved_symbols, list) {
+		struct module *owner = sym->module;
+
+		if (!owner || owner->seen)
+			continue;
+
+		owner->seen = true;
+		buf_printf(&deps, "%s%s", first ? "" : ",",
+			   get_basename(owner->name));
+		first = false;
+	}
+	buf_write(&deps, "", 1);
+
+	buf_printf(buf, "\n");
+	add_asm_modinfo(buf, "depends", deps.p);
+	free(deps.p);
+}
+
+/*
+ * KBUILD_MODNAME: the basename of the module with '-' and ',' replaced by
+ * '_' (see name-fix in scripts/Makefile.lib).
+ */
+static char *get_kbuild_modname(const struct module *mod)
+{
+	char *name = xstrdup(get_basename(mod->name));
+	char *curr;
+
+	for (curr = name; *curr; curr++) {
+		if (*curr == '-' || *curr == ',')
+			*curr = '_';
+	}
+
+	return name;
+}
+
+/* The module's name, its descriptor, and where it comes from. */
+static void add_asm_header(struct buffer *buf, const struct module *mod,
+			   const char *modname)
+{
+	buf_printf(buf, "/* Generated by modpost, see scripts/Makefile.modfinal */\n\n");
+
+	add_asm_modinfo(buf, "name", modname);
+	add_asm_this_module(buf, mod, modname);
+	buf_printf(buf, "\n");
+
+	if (!external_module)
+		add_asm_modinfo(buf, "intree", "Y");
+	if (strstarts(mod->name, "drivers/staging"))
+		add_asm_modinfo(buf, "staging", "Y");
+	if (strstarts(mod->name, "tools/testing"))
+		add_asm_modinfo(buf, "test", "Y");
+}
+
+static void add_asm_aliases(struct buffer *buf, struct module *mod)
+{
+	struct module_alias *alias, *next;
+
+	buf_printf(buf, "\n");
 	list_for_each_entry_safe(alias, next, &mod->aliases, node) {
-		buf_printf(&buf, "MODULE_ALIAS(\"%s\");\n", alias->str);
+		add_asm_modinfo(buf, "alias", alias->str);
 		list_del(&alias->node);
 		free(alias);
 	}
+}
+
+static void add_asm_srcversion(struct buffer *buf, const struct module *mod)
+{
+	if (!mod->srcversion[0])
+		return;
 
-	add_srcversion(&buf, mod);
+	buf_printf(buf, "\n");
+	add_asm_modinfo(buf, "srcversion", mod->srcversion);
+}
+
+static void write_mod_S_file(struct module *mod)
+{
+	struct buffer buf = { };
+	char fname[PATH_MAX];
+	char *modname = get_kbuild_modname(mod);
+	int ret;
 
-	ret = snprintf(fname, sizeof(fname), "%s.mod.c", mod->name);
+	add_asm_header(&buf, mod, modname);
+	buf_printf(&buf, "\n");
+	add_asm_exported_symbols(&buf, mod);
+	add_asm_versions(&buf, mod);
+	add_asm_extended_versions(&buf, mod);
+	add_asm_depends(&buf, mod);
+	add_asm_aliases(&buf, mod);
+	add_asm_srcversion(&buf, mod);
+	buf_printf(&buf, "\n\t.section .note.GNU-stack,\"\",%%progbits\n");
+
+	ret = snprintf(fname, sizeof(fname), "%s.mod.S", mod->name);
 	if (ret >= sizeof(fname)) {
 		error("%s: too long path was truncated\n", fname);
 		goto free;
@@ -2218,6 +2473,7 @@ static void write_mod_c_file(struct module *mod)
 	write_if_changed(&buf, fname);
 
 free:
+	free(modname);
 	free(buf.p);
 }
 
@@ -2457,7 +2713,7 @@ int main(int argc, char **argv)
 		if (mod->is_vmlinux)
 			write_vmlinux_export_c_file(mod);
 		else
-			write_mod_c_file(mod);
+			write_mod_S_file(mod);
 	}
 
 	if (missing_namespace_deps)
diff --git a/scripts/mod/module-offsets.c b/scripts/mod/module-offsets.c
new file mode 100644
index 000000000000..904f8cad6314
--- /dev/null
+++ b/scripts/mod/module-offsets.c
@@ -0,0 +1,32 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Layout of the structures modpost emits into *.mod.S. */
+#define COMPILE_OFFSETS
+#include <linux/kbuild.h>
+#include <linux/module.h>
+
+int main(void)
+{
+	DEFINE(MOD_SIZEOF_LONG, sizeof(long));
+	DEFINE(MOD_PREL32_RELOCATIONS, IS_ENABLED(CONFIG_HAVE_ARCH_PREL32_RELOCATIONS));
+	DEFINE(MOD_FUNC_PLABEL, IS_ENABLED(CONFIG_PARISC) && IS_ENABLED(CONFIG_64BIT));
+
+	DEFINE(MOD_SIZEOF_struct_module, sizeof(struct module));
+	DEFINE(MOD_ALIGNOF_struct_module, __alignof__(struct module));
+	OFFSET(MOD_OFF_module_name, module, name);
+	OFFSET(MOD_OFF_module_init, module, init);
+#ifdef CONFIG_MODULE_UNLOAD
+	OFFSET(MOD_OFF_module_exit, module, exit);
+#endif
+#if defined(CONFIG_M68K) && defined(CONFIG_MMU)
+	/* The only architecture whose .arch is not all zeroes. */
+	OFFSET(MOD_OFF_module_arch_fixup_start, module, arch.fixup_start);
+	OFFSET(MOD_OFF_module_arch_fixup_end, module, arch.fixup_end);
+#endif
+	DEFINE(MOD_NAME_LEN, MODULE_NAME_LEN);
+
+	DEFINE(MOD_SIZEOF_struct_modversion_info, sizeof(struct modversion_info));
+	DEFINE(MOD_ALIGNOF_struct_modversion_info, __alignof__(struct modversion_info));
+	OFFSET(MOD_OFF_modversion_info_name, modversion_info, name);
+
+	return 0;
+}
diff --git a/scripts/module-common.c b/scripts/module-common.c
index 12fbc6d3aae8..a75533e709fb 100644
--- a/scripts/module-common.c
+++ b/scripts/module-common.c
@@ -20,6 +20,9 @@ BUILD_LTO_INFO;
 
 MODULE_INFO(vermagic, VERMAGIC_STRING);
 
+/* modpost generates assembly so provide for debug info. */
+__weak __section(".discard.this_module") struct module __this_module;
+
 #ifdef CONFIG_MITIGATION_RETPOLINE
 MODULE_INFO(retpoline, "Y");
 #endif
diff --git a/scripts/tags.sh b/scripts/tags.sh
index 41e38df96984..c33d0f58a9d4 100755
--- a/scripts/tags.sh
+++ b/scripts/tags.sh
@@ -14,8 +14,9 @@ fi
 
 # RCS_FIND_IGNORE has escaped ()s -- remove them.
 ignore="$(echo "$RCS_FIND_IGNORE" | sed 's|\\||g' )"
-# tags and cscope files should also ignore MODVERSION *.mod.c files
-ignore="$ignore ( -name *.mod.c ) -prune -o"
+# tags and cscope files should also ignore the modpost-generated *.mod.S files
+# and any *.mod.c left behind from before they were assembly
+ignore="$ignore ( -name *.mod.c -o -name *.mod.S ) -prune -o"
 
 # ignore arbitrary directories
 if [ -n "${IGNORE_DIRS}" ]; then

-- 
2.56.0

[PATCH v5 05/11] kbuild: batch module finalisation

[Lorenzo Stoakes (ARM)]

With the .mod.S change in place, module finalisation on allmodconfig builds
consists of a large number of very short-lived jobs.

For allmodconfig x86-64 this can be on the order of ~22,000 jobs of a few
milliseconds in duration each.

Each job entails processing ~22k .cmd files, so the combination of heavy
overhead and small individual job results in a lot of unnecessary and
repeated work even with all cores being utilised.

The solution is to batch by a number of jobs. Determining which value makes
sense was done empirically.

On a 128-thread threadripper box doing an allmodconfig build, best of
2, *.ko, *.mod.o deleted each time:

    modules per chunk    instances    wall
    -----------------    ---------    ------
                    1        11171    10.22s
                    2         5586     6.72s
                    4         2793     4.97s
                    8         1397     4.26s
                   16          699     4.05s
                   32          350     4.05s
                   64          175     4.07s
                  128           88     4.05s
                  256           44     4.03s
                  512           22     4.18s

Wall time flattens for 16-256 module batches.

A slower/lower core machine will do better with fewer modules-per-batch, a
faster/higher core machine will do better with more modules-per-batch.

Therefore, take the midpoint which works in the most margin in either
direction - 128 modules per batch.

This naturally scales with module count too as the optimum gains are
obtained with higher module count, so fewer batches in this case costs less
overhead.

Each instance holds only its own modules' variables and the top-level one
reads no per-module .cmd files at all, the same rules serve both levels,
and an instance is told its chunk with modfinal-first=<index>.

Only the top-level instance builds .module-common.o, to the chunks it is a
plain prerequisite, so no two instances ever write it.

"make modules" with every *.mod.o and *.ko deleted goes from 28.9s to 15.9s
with clang 22. No-op "make modules" goes from 5.6s to 4.8s, as checking the
22,000 targets is spread over the chunks too.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 allmodconfig, no-op make, gcc         2.3s     1.4s    -0.85s (-38%)
  x86 allmodconfig, no-op make, clang       2.8s     1.8s    -0.94s (-34%)
  x86 allmodconfig, clean, gcc            306.6s   294.1s     -12.6s (-4%)
  x86 allmodconfig, clean, clang          290.2s   283.9s     -6.4s (-2%)

Reviewed-by: Kees Cook <kees@kernel.org>
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 scripts/Makefile.modfinal | 30 +++++++++++++++++++++++++++++-
 1 file changed, 29 insertions(+), 1 deletion(-)

diff --git a/scripts/Makefile.modfinal b/scripts/Makefile.modfinal
index 75e9effdf02c..4d5e6e1a0ff9 100644
--- a/scripts/Makefile.modfinal
+++ b/scripts/Makefile.modfinal
@@ -13,9 +13,30 @@ include $(srctree)/scripts/Makefile.lib
 # find all modules listed in modules.order
 modules := $(call read-file, modules.order)
 
+modfinal-chunk-size := 128
+
+ifdef modfinal-first
+
+# this instance handles the chunk of modules.order starting at $(modfinal-first)
+modules := $(wordlist $(modfinal-first), $(words $(modules)), $(modules))
+modules := $(wordlist 1, $(modfinal-chunk-size), $(modules))
+
 __modfinal: $(modules:%.o=%.ko)
 	@:
 
+else
+
+modfinal-chunks := $(addprefix chunk-, $(shell seq 1 $(modfinal-chunk-size) $(words $(modules))))
+
+PHONY += $(modfinal-chunks)
+$(modfinal-chunks): .module-common.o
+	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.modfinal modfinal-first=$(@:chunk-%=%)
+
+__modfinal: $(modfinal-chunks)
+	@:
+
+endif
+
 # modname and part-of-module are set to make c_flags define proper module flags
 modname = $(notdir $(@:.mod.o=))
 part-of-module = y
@@ -29,8 +50,11 @@ quiet_cmd_as_mod_o = AS [M]  $@
 %.mod.o: %.mod.S FORCE
 	$(call if_changed,as_mod_o)
 
+# Built by the top-level instance alone, the chunks take it as a plain file.
+ifndef modfinal-first
 .module-common.o: $(srctree)/scripts/module-common.c FORCE
 	$(call if_changed_rule,cc_o_c)
+endif
 
 ifneq ($(WARN_ON_UNUSED_TRACEPOINTS),)
 cmd_check_tracepoint = $(objtree)/scripts/tracepoint-update --module $<;
@@ -58,7 +82,11 @@ ifdef CONFIG_DEBUG_INFO_BTF_MODULES
 endif
 	+$(call cmd,check_tracepoint)
 
-targets += $(modules:%.o=%.ko) $(modules:%.o=%.mod.o) .module-common.o
+ifdef modfinal-first
+targets += $(modules:%.o=%.ko) $(modules:%.o=%.mod.o)
+else
+targets += .module-common.o
+endif
 
 # Add FORCE to the prerequisites of a target to force it to be always rebuilt.
 # ---------------------------------------------------------------------------

-- 
2.56.0

[PATCH v5 06/11] objtool: do not hash DWARF relocations

[Lorenzo Stoakes (ARM)]

objtool hashes the relocation of each section so it can find them by
destination, but DWARF sections are never looked up this way, so there is
no reason to hash them.

With CONFIG_DEBUG_INFO_DWARF5 set a defconfig vmlinux.o has ~22 million
relocations, 20.5 million of which are .debug_* sections.

Therefore, don't hash these.

With the same configuration the objtool vmlinux.o link-time run takes ~.5s
less to complete (2.63s -> 2.14s) and ~130 MiB memory to do it.

The output remains unchanged.

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 tools/objtool/elf.c | 32 +++++++++++++++++++++++++-------
 1 file changed, 25 insertions(+), 7 deletions(-)

diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index a791f4ea6ec1..98a110e3e8f5 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -1071,7 +1071,8 @@ struct reloc *elf_init_reloc(struct elf *elf, struct section *rsec,
 	set_reloc_type(elf, reloc, type);
 	set_reloc_addend(elf, reloc, addend);
 
-	elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
+	if (!is_dwarf_section(rsec->base))
+		elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
 	set_sym_next_reloc(reloc, sym->relocs);
 	sym->relocs = reloc;
 
@@ -1125,16 +1126,14 @@ struct reloc *elf_init_reloc_data_sym(struct elf *elf, struct section *sec,
 
 static int read_relocs(struct elf *elf)
 {
-	unsigned long nr_reloc, max_reloc = 0;
+	unsigned long nr_reloc, max_reloc = 0, nr_hashed = 0;
 	struct section *rsec;
 	struct reloc *reloc;
 	unsigned int symndx;
 	struct symbol *sym;
+	bool hashed;
 	int i;
 
-	if (!elf_alloc_hash(reloc, elf->num_relocs))
-		return -1;
-
 	list_for_each_entry(rsec, &elf->sections, list) {
 		if (!is_reloc_sec(rsec))
 			continue;
@@ -1147,6 +1146,23 @@ static int read_relocs(struct elf *elf)
 
 		rsec->base->rsec = rsec;
 
+		/*
+		 * DWARF relocations are never looked up by destination, they
+		 * only need to be on their symbol's list.
+		 */
+		if (!is_dwarf_section(rsec->base))
+			nr_hashed += sec_num_entries(rsec);
+	}
+
+	if (!elf_alloc_hash(reloc, nr_hashed))
+		return -1;
+
+	list_for_each_entry(rsec, &elf->sections, list) {
+		if (!is_reloc_sec(rsec))
+			continue;
+
+		hashed = !is_dwarf_section(rsec->base);
+
 		/* nr_alloc_relocs=0: libelf owns d_buf */
 		rsec->nr_alloc_relocs = 0;
 
@@ -1168,7 +1184,8 @@ static int read_relocs(struct elf *elf)
 				return -1;
 			}
 
-			elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
+			if (hashed)
+				elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
 			set_sym_next_reloc(reloc, sym->relocs);
 			sym->relocs = reloc;
 
@@ -1180,6 +1197,7 @@ static int read_relocs(struct elf *elf)
 	if (opts.stats) {
 		printf("max_reloc: %lu\n", max_reloc);
 		printf("num_relocs: %lu\n", elf->num_relocs);
+		printf("num_relocs_hashed: %lu\n", nr_hashed);
 		printf("reloc_bits: %d\n", elf->reloc_bits);
 	}
 
@@ -1634,7 +1652,7 @@ static int elf_alloc_reloc(struct elf *elf, struct section *rsec)
 
 	memcpy(new_relocs, old_relocs, nr_relocs_old * sizeof(struct reloc));
 
-	for (int i = 0; i < nr_relocs_old; i++) {
+	for (int i = 0; i < nr_relocs_old && !is_dwarf_section(rsec->base); i++) {
 		struct reloc *old = &old_relocs[i];
 		struct reloc *new = &new_relocs[i];
 		u32 key = reloc_hash(old);

-- 
2.56.0

[PATCH v5 07/11] objtool: cache relocations, do less work, eliminate relocation hash

[Lorenzo Stoakes (ARM)]

Instruction relocations are looked up by destination in objtool via a hash
which is keyed on a 16-byte (OFFSET_STRIDE) window within the section being
walked.

It iterates through each 16-byte window, looking up relocations over
several passes, before moving on to the next 16-byte window, caching only
when a relocation is not found saving further lookups in this case.

Improve upon this by introducing a per-section relocation cache storing the
first relocation at or after each 64-byte window of data (an empirically
determined index range), indexed by chunk.

The lookup is implemented an array lookup and touches no shared state, so
can be used from multiple threads.

The index runs over the relocations in offset order. Usually this is how
they are input, however if not, each section is sorted once, storing
their offsets in reloc_order[].

This is done lazily on lookup, so nothing pays the cost that doesn't have
to, and if everything is sorted nothing does.

The output of objtool before and after this change was confirmed to be
byte-for-byte identical both for x86_64 defconfig and allmodconfig with
gcc and clang.

objtool on the gcc allmodconfig vmlinux.o goes from 10.5s to 9.0s, clang
from 9.8s to 8.3s and gcc defconfig from 2.08s to 1.79s, with peak memory
down ~90 MiB on allmodconfig.

Similar performance was also noted on a worst case scenario for unsorted
input (gcc but lld for linking), which confirms that the sorting mechanism
works correctly with little overhead.

objtool on vmlinux.o is on the serial tail of every build that links
vmlinux, no-op builds are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, touch mm/vma.c, gcc        8.3s     8.2s    -0.14s (-2%)
  x86 defconfig, touch mm/vma.c, clang      7.6s     7.3s    -0.25s (-3%)
  x86 defconfig, clean, gcc                28.9s    28.6s    -0.22s (-1%)
  x86 defconfig, clean, clang              29.4s    29.1s    -0.28s (-1%)
  x86 allmodconfig, touch mm/vma.c, gcc    29.4s    28.0s     -1.4s (-5%)
  x86 allmodconfig, touch mm/vma.c, clang  27.9s    26.2s     -1.7s (-6%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 tools/objtool/elf.c                 | 280 ++++++++++++++++++++++++++++--------
 tools/objtool/include/objtool/elf.h |  10 +-
 2 files changed, 221 insertions(+), 69 deletions(-)

diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index 98a110e3e8f5..bd463b5df38c 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -316,35 +316,220 @@ struct symbol *find_global_symbol_by_name(const struct elf *elf, const char *nam
 	return NULL;
 }
 
-/* If there are multiple matches, return the first one in the range */
+static bool is_dwarf_section(struct section *sec)
+{
+	return !strncmp(sec->name, ".debug_", 7);
+}
+
+/* Index the first relocation at or after each 64 byte window of the base. */
+#define RELOC_CACHE_INDEX_SHIFT	6
+
+static unsigned long reloc_cache_index(unsigned long offset)
+{
+	return offset >> RELOC_CACHE_INDEX_SHIFT;
+}
+
+static void reloc_cache_free(struct section *rsec)
+{
+	free(rsec->reloc_cache);
+	free(rsec->reloc_order);
+	rsec->reloc_cache = NULL;
+	rsec->reloc_order = NULL;
+	rsec->nr_cache_windows = 0;
+	rsec->nr_indexed = 0;
+	rsec->sorted = false;
+}
+
+/* The relocation at a position of the section's offset order. */
+static struct reloc *reloc_at(struct section *rsec, unsigned int pos)
+{
+	unsigned int reloc_idx = pos;
+
+	if (rsec->reloc_order)
+		reloc_idx = rsec->reloc_order[pos];
+
+	return &rsec->relocs[reloc_idx];
+}
+
+static bool relocs_in_order(struct section *rsec)
+{
+	const unsigned int nr_relocs = sec_num_entries(rsec);
+	unsigned int i;
+
+	for (i = 1; i < nr_relocs; i++) {
+		struct reloc *prev = &rsec->relocs[i - 1];
+		struct reloc *reloc = &rsec->relocs[i];
+
+		if (reloc_offset(reloc) < reloc_offset(prev))
+			return false;
+	}
+
+	return true;
+}
+
+/* qsort() passes no context, so the relocations being sorted live here. */
+static struct reloc *sort_relocs;
+
+static int compare_reloc_order(const void *a, const void *b)
+{
+	const unsigned int *idx_a = a;
+	const unsigned int *idx_b = b;
+	const unsigned long offset_a = reloc_offset(&sort_relocs[*idx_a]);
+	const unsigned long offset_b = reloc_offset(&sort_relocs[*idx_b]);
+
+	if (offset_a < offset_b)
+		return -1;
+	if (offset_a > offset_b)
+		return 1;
+
+	/* Equal offsets stay in file order. */
+	if (*idx_a < *idx_b)
+		return -1;
+	return 1;
+}
+
+/*
+ * gcc emits the relocations of its jumps in a second pass, so its objects,
+ * and a vmlinux.o lld links from them, are out of order: sort them once.
+ */
+static int reloc_order_build(struct section *rsec)
+{
+	const unsigned int nr_relocs = sec_num_entries(rsec);
+	unsigned int i;
+
+	rsec->reloc_order = malloc(nr_relocs * sizeof(*rsec->reloc_order));
+	if (!rsec->reloc_order) {
+		ERROR_GLIBC("malloc");
+		return -1;
+	}
+
+	for (i = 0; i < nr_relocs; i++)
+		rsec->reloc_order[i] = i;
+
+	sort_relocs = rsec->relocs;
+	qsort(rsec->reloc_order, nr_relocs, sizeof(*rsec->reloc_order),
+	      compare_reloc_order);
+
+	return 0;
+}
+
+/* Grow the index to cover the base section, new windows start past the end. */
+static int reloc_cache_resize(struct section *rsec)
+{
+	const unsigned int nr_windows = reloc_cache_index(sec_size(rsec->base)) + 1;
+	unsigned int *cache;
+
+	if (nr_windows <= rsec->nr_cache_windows)
+		return 0;
+
+	cache = realloc(rsec->reloc_cache, nr_windows * sizeof(*cache));
+	if (!cache) {
+		ERROR_GLIBC("realloc");
+		return -1;
+	}
+
+	while (rsec->nr_cache_windows < nr_windows)
+		cache[rsec->nr_cache_windows++] = rsec->nr_indexed;
+	rsec->reloc_cache = cache;
+
+	return 0;
+}
+
+/*
+ * Index the next relocation. It must follow the previous one in position and
+ * offset, otherwise the index is dropped and the next lookup rebuilds it.
+ */
+static int reloc_cache_add(struct section *rsec, unsigned int pos)
+{
+	struct reloc *reloc = reloc_at(rsec, pos);
+	const unsigned long offset = reloc_offset(reloc);
+	const unsigned long window = reloc_cache_index(offset);
+	unsigned long first_window = 0;
+
+	if (pos != rsec->nr_indexed)
+		goto unsorted;
+
+	if (pos) {
+		struct reloc *prev = reloc_at(rsec, pos - 1);
+		const unsigned long prev_offset = reloc_offset(prev);
+
+		if (offset < prev_offset)
+			goto unsorted;
+		first_window = reloc_cache_index(prev_offset) + 1;
+	}
+
+	if (reloc_cache_resize(rsec))
+		return -1;
+	if (window >= rsec->nr_cache_windows)
+		goto unsorted;
+
+	while (first_window <= window)
+		rsec->reloc_cache[first_window++] = pos;
+	rsec->nr_indexed = pos + 1;
+
+	return 0;
+
+unsorted:
+	reloc_cache_free(rsec);
+	return 0;
+}
+
+static unsigned long num_relocs_sorted;
+
+static int init_reloc_cache(struct section *rsec)
+{
+	const unsigned int nr_relocs = sec_num_entries(rsec);
+	unsigned int pos;
+
+	reloc_cache_free(rsec);
+	if (!relocs_in_order(rsec)) {
+		if (reloc_order_build(rsec))
+			return -1;
+		num_relocs_sorted += nr_relocs;
+	}
+
+	rsec->sorted = true;
+	for (pos = 0; pos < nr_relocs; pos++) {
+		if (reloc_cache_add(rsec, pos))
+			return -1;
+	}
+
+	return 0;
+}
+
+static bool reloc_in_range(struct reloc *reloc, unsigned long offset,
+			   unsigned int len)
+{
+	return reloc_offset(reloc) >= offset && reloc_offset(reloc) < offset + len;
+}
+
+/* If there are multiple matches, return the first one in the range. */
 struct reloc *find_reloc_by_dest_range(const struct elf *elf, struct section *sec,
 				       unsigned long offset, unsigned int len)
 {
-	struct reloc *reloc, *r = NULL;
-	struct section *rsec;
-	unsigned long o;
+	struct section *rsec = sec->rsec;
+	unsigned long cache_idx;
+	unsigned int pos;
 
-	rsec = sec->rsec;
 	if (!rsec)
 		return NULL;
 
-	for_offset_range(o, offset, offset + len) {
-		elf_hash_for_each_possible(elf, reloc, reloc, hash,
-					   sec_offset_hash(rsec, o)) {
-			if (reloc->sec != rsec)
-				continue;
+	if (!rsec->sorted && init_reloc_cache(rsec))
+		exit(1);
 
-			if (reloc_offset(reloc) >= offset &&
-			    reloc_offset(reloc) < offset + len) {
-				if (!r || reloc_offset(reloc) < reloc_offset(r))
-					r = reloc;
-			}
-		}
-		if (r && (reloc_offset(r) & OFFSET_STRIDE_MASK) == o)
-			return r;
+	cache_idx = reloc_cache_index(offset);
+	if (cache_idx >= rsec->nr_cache_windows)
+		return NULL;
+
+	/* The index gives a lower bound, scan on from there. */
+	for (pos = rsec->reloc_cache[cache_idx]; pos < rsec->nr_indexed; pos++) {
+		struct reloc *reloc = reloc_at(rsec, pos);
+
+		if (reloc_offset(reloc) >= offset)
+			return reloc_in_range(reloc, offset, len) ? reloc : NULL;
 	}
 
-	return r;
+	return NULL;
 }
 
 struct reloc *find_reloc_by_dest(const struct elf *elf, struct section *sec, unsigned long offset)
@@ -352,11 +537,6 @@ struct reloc *find_reloc_by_dest(const struct elf *elf, struct section *sec, uns
 	return find_reloc_by_dest_range(elf, sec, offset, 1);
 }
 
-static bool is_dwarf_section(struct section *sec)
-{
-	return !strncmp(sec->name, ".debug_", 7);
-}
-
 static int read_sections(struct elf *elf)
 {
 	Elf_Scn *s = NULL;
@@ -1071,8 +1251,10 @@ struct reloc *elf_init_reloc(struct elf *elf, struct section *rsec,
 	set_reloc_type(elf, reloc, type);
 	set_reloc_addend(elf, reloc, addend);
 
-	if (!is_dwarf_section(rsec->base))
-		elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
+	if (rsec->reloc_order)
+		reloc_cache_free(rsec);
+	else if (rsec->sorted && reloc_cache_add(rsec, reloc_idx))
+		return NULL;
 	set_sym_next_reloc(reloc, sym->relocs);
 	sym->relocs = reloc;
 
@@ -1126,12 +1308,11 @@ struct reloc *elf_init_reloc_data_sym(struct elf *elf, struct section *sec,
 
 static int read_relocs(struct elf *elf)
 {
-	unsigned long nr_reloc, max_reloc = 0, nr_hashed = 0;
+	unsigned long nr_reloc, max_reloc = 0;
 	struct section *rsec;
 	struct reloc *reloc;
 	unsigned int symndx;
 	struct symbol *sym;
-	bool hashed;
 	int i;
 
 	list_for_each_entry(rsec, &elf->sections, list) {
@@ -1146,23 +1327,6 @@ static int read_relocs(struct elf *elf)
 
 		rsec->base->rsec = rsec;
 
-		/*
-		 * DWARF relocations are never looked up by destination, they
-		 * only need to be on their symbol's list.
-		 */
-		if (!is_dwarf_section(rsec->base))
-			nr_hashed += sec_num_entries(rsec);
-	}
-
-	if (!elf_alloc_hash(reloc, nr_hashed))
-		return -1;
-
-	list_for_each_entry(rsec, &elf->sections, list) {
-		if (!is_reloc_sec(rsec))
-			continue;
-
-		hashed = !is_dwarf_section(rsec->base);
-
 		/* nr_alloc_relocs=0: libelf owns d_buf */
 		rsec->nr_alloc_relocs = 0;
 
@@ -1184,21 +1348,24 @@ static int read_relocs(struct elf *elf)
 				return -1;
 			}
 
-			if (hashed)
-				elf_hash_add(reloc, &reloc->hash, reloc_hash(reloc));
 			set_sym_next_reloc(reloc, sym->relocs);
 			sym->relocs = reloc;
 
 			nr_reloc++;
 		}
 		max_reloc = max(max_reloc, nr_reloc);
+
+		/* DWARF relocs are never looked up, so are not worth indexing. */
+		if (is_dwarf_section(rsec->base))
+			continue;
+		if (init_reloc_cache(rsec))
+			return -1;
 	}
 
 	if (opts.stats) {
 		printf("max_reloc: %lu\n", max_reloc);
 		printf("num_relocs: %lu\n", elf->num_relocs);
-		printf("num_relocs_hashed: %lu\n", nr_hashed);
-		printf("reloc_bits: %d\n", elf->reloc_bits);
+		printf("num_relocs_sorted: %lu\n", num_relocs_sorted);
 	}
 
 	return 0;
@@ -1345,8 +1512,7 @@ struct elf *elf_create_file(GElf_Ehdr *ehdr, const char *name)
 	if (!elf_alloc_hash(section,		1000) ||
 	    !elf_alloc_hash(section_name,	1000) ||
 	    !elf_alloc_hash(symbol,		10000) ||
-	    !elf_alloc_hash(symbol_name,	10000) ||
-	    !elf_alloc_hash(reloc,		100000))
+	    !elf_alloc_hash(symbol_name,	10000))
 		return NULL;
 
 	null		= elf_create_section(elf, NULL, 0, 0, SHT_NULL, 0, 0);
@@ -1526,6 +1692,8 @@ struct section *elf_create_section(struct elf *elf, const char *name,
 	sec->sh.sh_type = type;
 	sec->sh.sh_addralign = align;
 	sec->sh.sh_flags = flags;
+	/* Relocations objtool adds are indexed as they come. */
+	sec->sorted = type == SHT_RELA;
 
 	if (name) {
 		sec->name = strdup(name);
@@ -1651,16 +1819,6 @@ static int elf_alloc_reloc(struct elf *elf, struct section *rsec)
 	}
 
 	memcpy(new_relocs, old_relocs, nr_relocs_old * sizeof(struct reloc));
-
-	for (int i = 0; i < nr_relocs_old && !is_dwarf_section(rsec->base); i++) {
-		struct reloc *old = &old_relocs[i];
-		struct reloc *new = &new_relocs[i];
-		u32 key = reloc_hash(old);
-
-		elf_hash_del(reloc, &old->hash, key);
-		elf_hash_add(reloc, &new->hash, key);
-	}
-
 	free(old_relocs);
 done:
 	rsec->relocs = new_relocs;
diff --git a/tools/objtool/include/objtool/elf.h b/tools/objtool/include/objtool/elf.h
index a82517a76a0f..baa4f76b1800 100644
--- a/tools/objtool/include/objtool/elf.h
+++ b/tools/objtool/include/objtool/elf.h
@@ -59,6 +59,8 @@ struct section {
 	const char *name;
 	int idx;
 	bool _changed, text, rodata, noinstr, init, truncate;
+	bool sorted;
+	unsigned int *reloc_cache, *reloc_order, nr_cache_windows, nr_indexed;
 	struct reloc *relocs;
 	unsigned long nr_alloc_relocs;
 	struct section *twin;
@@ -106,7 +108,6 @@ struct symbol {
 };
 
 struct reloc {
-	struct elf_hash_node hash;
 	struct section *sec;
 	struct symbol *sym;
 	unsigned long _sym_next_reloc;
@@ -127,13 +128,11 @@ struct elf {
 	int symbol_name_bits;
 	int section_bits;
 	int section_name_bits;
-	int reloc_bits;
 
 	struct elf_hash_node **symbol_hash;
 	struct elf_hash_node **symbol_name_hash;
 	struct elf_hash_node **section_hash;
 	struct elf_hash_node **section_name_hash;
-	struct elf_hash_node **reloc_hash;
 
 	struct section *section_data;
 	struct symbol *symbol_data;
@@ -575,9 +574,4 @@ static inline u32 sec_offset_hash(struct section *sec, unsigned long offset)
 	return ol;
 }
 
-static inline u32 reloc_hash(struct reloc *reloc)
-{
-	return sec_offset_hash(reloc->sec, reloc_offset(reloc));
-}
-
 #endif /* _OBJTOOL_ELF_H */

-- 
2.56.0

[PATCH v5 08/11] objtool: size the instruction hash to the text

[Lorenzo Stoakes (ARM)]

The instruction hash is a fixed 2^20 buckets, which for an x86-64
allmodconfig vmlinux.o of ~16 million instructions leaves find_insn()
walking chains of four or more entries.

Size it by the amount of text to be decoded instead, at one bucket per
OFFSET_STRIDE window, as sec_offset_hash() keys on those and anything
finer would sit empty.

This gives 2^20 buckets (8 MiB) for a defconfig vmlinux.o and 2^22 (32 MiB)
for allmodconfig, so it is not an egregious use of memory.

The output of objtool before and after this change was confirmed to be
byte-for-byte identical for x86_64 defconfig and allmodconfig.

On a 128-thread machine, objtool on the gcc allmodconfig vmlinux.o goes
from 9.0s to 6.8s. A defconfig vmlinux.o already had 2^20 buckets and is
unchanged.

objtool on vmlinux.o is on the serial tail of every build that links
vmlinux, no-op builds are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 allmodconfig, touch mm/vma.c, gcc    28.0s    25.7s     -2.4s (-8%)
  x86 allmodconfig, touch mm/vma.c, clang  26.2s    24.1s     -2.0s (-8%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 tools/objtool/check.c                   | 58 +++++++++++++++++++++++++++++++--
 tools/objtool/include/objtool/objtool.h |  3 +-
 tools/objtool/objtool.c                 |  1 -
 3 files changed, 58 insertions(+), 4 deletions(-)

diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 931c5c412f15..97250aa36100 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -38,12 +38,22 @@ struct disas_context *objtool_disas_ctx;
 
 size_t sym_name_max_len;
 
+static struct hlist_head *insn_hash_head(struct objtool_file *file,
+					 struct section *sec, unsigned long offset)
+{
+	/* Determine instruction hash based on section index and offset. */
+	const u32 sec_hash = sec_offset_hash(sec, offset);
+	const u32 hash = hash_min(sec_hash, file->insn_hash_bits);
+
+	return &file->insn_hash[hash];
+}
+
 struct instruction *find_insn(struct objtool_file *file,
 			      struct section *sec, unsigned long offset)
 {
 	struct instruction *insn;
 
-	hash_for_each_possible(file->insn_hash, insn, hash, sec_offset_hash(sec, offset)) {
+	hlist_for_each_entry(insn, insn_hash_head(file, sec, offset), hash) {
 		if (insn->sec == sec && insn->offset == offset)
 			return insn;
 	}
@@ -404,6 +414,44 @@ static void *cfi_hash_alloc(unsigned long size)
 static unsigned long nr_insns;
 static unsigned long nr_insns_visited;
 
+/*
+ * sec_offset_hash() keys on OFFSET_STRIDE windows, so the instructions of a
+ * window share a chain and buckets beyond one per window would sit empty.
+ */
+#define INSN_HASH_BYTES_PER_BUCKET	OFFSET_STRIDE
+#define INSN_HASH_MIN_BITS		10
+
+static unsigned long total_text_size(struct objtool_file *file)
+{
+	unsigned long size = 0;
+	struct section *sec;
+
+	for_each_sec(file->elf, sec)
+		if (is_text_sec(sec))
+			size += sec_size(sec);
+
+	return size;
+}
+
+static int alloc_insn_hash(struct objtool_file *file, unsigned long text_size)
+{
+	const unsigned long nr_buckets = text_size / INSN_HASH_BYTES_PER_BUCKET;
+	const int bits = ilog2(nr_buckets);
+
+	file->insn_hash_bits = max(INSN_HASH_MIN_BITS, bits);
+	file->insn_hash = calloc(1UL << file->insn_hash_bits,
+				 sizeof(*file->insn_hash));
+	if (!file->insn_hash) {
+		ERROR_GLIBC("calloc");
+		return -1;
+	}
+
+	if (opts.stats)
+		printf("insn_hash_bits: %d\n", file->insn_hash_bits);
+
+	return 0;
+}
+
 /*
  * Call the arch-specific instruction decoder for all the instructions and add
  * them to the global instruction list.
@@ -415,6 +463,9 @@ static int decode_instructions(struct objtool_file *file)
 	unsigned long offset;
 	struct instruction *insn;
 
+	if (alloc_insn_hash(file, total_text_size(file)))
+		return -1;
+
 	for_each_sec(file->elf, sec) {
 		struct instruction *insns = NULL;
 		u8 prev_len = 0;
@@ -475,7 +526,7 @@ static int decode_instructions(struct objtool_file *file)
 			if (insn->type == INSN_BUG)
 				insn->dead_end = true;
 
-			hash_add(file->insn_hash, &insn->hash, sec_offset_hash(sec, insn->offset));
+			hlist_add_head(&insn->hash, insn_hash_head(file, sec, insn->offset));
 			nr_insns++;
 		}
 
@@ -4803,6 +4854,9 @@ void free_insns(struct objtool_file *file)
 
 	for (chunk = chunks; chunk; chunk = chunk->next)
 		free(chunk->addr);
+
+	free(file->insn_hash);
+	file->insn_hash = NULL;
 }
 
 const char *objtool_disas_insn(struct instruction *insn)
diff --git a/tools/objtool/include/objtool/objtool.h b/tools/objtool/include/objtool/objtool.h
index 6dc12a59ad00..79fe82b7397e 100644
--- a/tools/objtool/include/objtool/objtool.h
+++ b/tools/objtool/include/objtool/objtool.h
@@ -21,7 +21,8 @@ struct pv_state {
 
 struct objtool_file {
 	struct elf *elf;
-	DECLARE_HASHTABLE(insn_hash, 20);
+	struct hlist_head *insn_hash;
+	int insn_hash_bits;
 	struct list_head retpoline_call_list;
 	struct list_head return_thunk_list;
 	struct list_head static_call_list;
diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c
index a4e139dee7e9..71e048f8582a 100644
--- a/tools/objtool/objtool.c
+++ b/tools/objtool/objtool.c
@@ -29,7 +29,6 @@ struct objtool_file *objtool_open_read(const char *filename)
 	if (!file.elf)
 		return NULL;
 
-	hash_init(file.insn_hash);
 	INIT_LIST_HEAD(&file.retpoline_call_list);
 	INIT_LIST_HEAD(&file.return_thunk_list);
 	INIT_LIST_HEAD(&file.static_call_list);

-- 
2.56.0

[PATCH v5 09/11] objtool: decode instructions and resolve branch targets in parallel

[Lorenzo Stoakes (ARM)]

During a kernel build objtool is used to decode vmlinux.o's instructions
and resolve every jump and call destination.

This forms a large part of the work objtool does during the build process,
and it is all done in serial.

Decode these in parallel at a function granularity to speed things up, but
limit this to invocations that pass --link, and only where the there is 8
MiB or more text to justify it.

In practice this limits this to processing vmlinux.o in the kernel build
and modules are processed as they were before.

Only the instruction hash is shared between the threads and nothing is ever
removed from it, so an insertion is a compare-and-swap on the bucket head.

Threading is limited to decoding and the jump pass, so the gain flattens
out at 16 threads and any further threads were found to only add overhead.

When performing an allmodconfig build, the clang invocation of objtool when
processing vmlinux.o took 5.93s on 1 thread, 4.56s on 8, 4.51s on
16 and 4.63s on 128.

Therefore cap the thread count at 16 or the number of CPUs, whichever is
fewer.

Also add the reloc_cache_lock mutex so find_reloc_by_dest_range() sorts
relocations without a risk of a race. In practice no contention should be
possible, but keep the lock as a guarantee of this.

The output of objtool before and after this change was confirmed to be
byte-for-byte identical for x86_64 defconfig and allmodconfig with gcc and
clang, and for a loongarch defconfig, where objtool runs on every object.

On a 128-thread machine, objtool on the clang allmodconfig vmlinux.o goes
from 5.2s to 4.4s (6.5s to 4.4s together with the previous two patches),
and on defconfig from 1.99s to 1.38s.

objtool on vmlinux.o is on the serial tail of every build that links
vmlinux, no-op builds are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, touch mm/vma.c, gcc        8.2s     7.7s    -0.55s (-7%)
  x86 defconfig, touch mm/vma.c, clang      7.3s     6.9s    -0.44s (-6%)
  x86 defconfig, clean, gcc                28.6s    28.2s    -0.47s (-2%)
  x86 defconfig, clean, clang              29.1s    28.7s    -0.45s (-2%)
  x86 allmodconfig, touch mm/vma.c, gcc    25.7s    23.7s     -2.0s (-8%)
  x86 allmodconfig, touch mm/vma.c, clang  24.1s    22.5s     -1.6s (-7%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 tools/objtool/Makefile  |   2 +-
 tools/objtool/check.c   | 717 ++++++++++++++++++++++++++++++++++++------------
 tools/objtool/elf.c     |  15 +-
 tools/objtool/objtool.c |  14 +-
 4 files changed, 559 insertions(+), 189 deletions(-)

diff --git a/tools/objtool/Makefile b/tools/objtool/Makefile
index db99c4759b2c..3ccb1cdc9239 100644
--- a/tools/objtool/Makefile
+++ b/tools/objtool/Makefile
@@ -63,7 +63,7 @@ INCLUDES := -I$(srctree)/tools/include \
 OBJTOOL_CFLAGS  := -std=gnu11 -fomit-frame-pointer -O2 -g $(WARNINGS)	\
 		   $(INCLUDES) $(LIBELF_FLAGS) $(LIBXXHASH_CFLAGS) $(HOSTCFLAGS)
 
-OBJTOOL_LDFLAGS := $(LIBSUBCMD) $(LIBELF_LIBS) $(LIBXXHASH_LIBS) $(HOSTLDFLAGS)
+OBJTOOL_LDFLAGS := $(LIBSUBCMD) $(LIBELF_LIBS) $(LIBXXHASH_LIBS) -lpthread $(HOSTLDFLAGS)
 
 # Allow old libelf to be used:
 elfshdr := $(shell echo '$(pound)include <libelf.h>' | $(HOSTCC) $(OBJTOOL_CFLAGS) -x c -E - 2>/dev/null | grep elf_getshdr)
diff --git a/tools/objtool/check.c b/tools/objtool/check.c
index 97250aa36100..9a56e24eb1e6 100644
--- a/tools/objtool/check.c
+++ b/tools/objtool/check.c
@@ -7,6 +7,9 @@
 #include <fnmatch.h>
 #include <string.h>
 #include <stdlib.h>
+#include <pthread.h>
+#include <stddef.h>
+#include <unistd.h>
 #include <inttypes.h>
 #include <sys/mman.h>
 
@@ -24,6 +27,7 @@
 #include <linux/objtool_types.h>
 #include <linux/hashtable.h>
 #include <linux/kernel.h>
+#include <linux/sizes.h>
 #include <linux/static_call_types.h>
 #include <linux/string.h>
 
@@ -64,14 +68,13 @@ struct instruction *find_insn(struct objtool_file *file,
 struct instruction *next_insn_same_sec(struct objtool_file *file,
 				       struct instruction *insn)
 {
-	if (insn->idx == INSN_CHUNK_MAX)
-		return find_insn(file, insn->sec, insn->offset + insn->len);
+	const unsigned long next_offset = insn->offset + insn->len;
 
-	insn++;
-	if (!insn->len)
-		return NULL;
+	/* A chunk ends at its last slot or an empty one, so look the next up. */
+	if (insn->idx == INSN_CHUNK_MAX || !insn[1].len)
+		return find_insn(file, insn->sec, next_offset);
 
-	return insn;
+	return insn + 1;
 }
 
 struct instruction *next_insn_same_func(struct objtool_file *file,
@@ -414,6 +417,12 @@ static void *cfi_hash_alloc(unsigned long size)
 static unsigned long nr_insns;
 static unsigned long nr_insns_visited;
 
+/* Only the vmlinux.o link, and only if it is this large, runs on several threads. */
+#define DECODE_THREADED_MIN_TEXT	SZ_8M
+/* Only decoding and the branch passes are threaded, so more gains nothing. */
+#define DECODE_MAX_THREADS		16
+#define DECODE_RANGES_PER_THREAD	4
+
 /*
  * sec_offset_hash() keys on OFFSET_STRIDE windows, so the instructions of a
  * window share a chain and buckets beyond one per window would sit empty.
@@ -452,24 +461,350 @@ static int alloc_insn_hash(struct objtool_file *file, unsigned long text_size)
 	return 0;
 }
 
+/* Per-thread state, only instruction hash is shared. */
+struct insn_range {
+	struct section *sec;
+	unsigned long start, end;
+	struct instruction *first, *last;
+	unsigned long nr_insns;
+	int ret;
+
+	/*
+	 * Each thread writes to its own copy of an objtool file, which are
+	 * combined upon completion.
+	 */
+	struct objtool_file shadow;
+};
+
+#define range_for_each_insn(file, range, insn)				\
+	for (insn = (range)->first;					\
+	     insn && insn->offset < (range)->end;			\
+	     insn = next_insn_same_sec(file, insn))
+
+typedef int (*range_fn_t)(struct objtool_file *file, struct insn_range *range);
+
+struct range_work {
+	range_fn_t fn;
+};
+
+static struct insn_range *decode_ranges;
+static unsigned int nr_decode_ranges, next_decode_range, nr_decode_threads;
+
+/* The kernel's try_cmpxchg(); the tools' cmpxchg() is host-arch only. */
+static bool hlist_try_cmpxchg(struct hlist_node **ptr, struct hlist_node **old,
+			      struct hlist_node *new)
+{
+	struct hlist_node *seen = __sync_val_compare_and_swap(ptr, *old, new);
+
+	if (seen == *old)
+		return true;
+
+	*old = seen;
+	return false;
+}
+
+/* Nothing is ever removed, so push onto the bucket as llist_add() does. */
+static void insn_hash_add(struct objtool_file *file, struct instruction *insn)
+{
+	struct hlist_head *head = insn_hash_head(file, insn->sec, insn->offset);
+	struct hlist_node *first = READ_ONCE(head->first);
+
+	insn->hash.pprev = &head->first;
+	do {
+		insn->hash.next = first;
+	} while (!hlist_try_cmpxchg(&head->first, &first, &insn->hash));
+}
+
+/* The slot after prev in its chunk, or the first of a new chunk. */
+static struct instruction *next_insn_slot(struct instruction *prev)
+{
+	struct instruction *insn;
+
+	if (prev && prev->idx < INSN_CHUNK_MAX) {
+		insn = prev + 1;
+		insn->idx = prev->idx + 1;
+		return insn;
+	}
+
+	insn = calloc(INSN_CHUNK_SIZE, sizeof(*insn));
+	if (!insn)
+		ERROR_GLIBC("calloc");
+
+	return insn;
+}
+
+static int decode_range(struct objtool_file *file, struct insn_range *range)
+{
+	struct instruction *insn = NULL;
+	struct section *sec = range->sec;
+	unsigned long offset;
+	u8 prev_len = 0;
+
+	for (offset = range->start; offset < range->end; offset += insn->len) {
+		const unsigned long remaining = sec_size(sec) - offset;
+
+		insn = next_insn_slot(insn);
+		if (!insn)
+			return -1;
+
+		INIT_LIST_HEAD(&insn->call_node);
+		insn->sec = sec;
+		insn->offset = offset;
+		insn->prev_len = prev_len;
+
+		if (arch_decode_instruction(file, sec, offset, remaining, insn))
+			return -1;
+
+		prev_len = insn->len;
+
+		if (insn->type == INSN_BUG)
+			insn->dead_end = true;
+
+		insn_hash_add(file, insn);
+		if (!range->first)
+			range->first = insn;
+		range->nr_insns++;
+	}
+	range->last = insn;
+
+	/* The range ends at a function symbol, so decoding must land on it. */
+	if (offset != range->end) {
+		ERROR("%s: no instruction boundary at %s", sec->name,
+		      offstr(sec, range->end));
+		return -1;
+	}
+
+	return 0;
+}
+
+static int run_threads(void *(*fn)(void *), void *arg, unsigned int nr_threads)
+{
+	unsigned int nr_started, i;
+	pthread_t *threads;
+	int ret = 0;
+
+	if (nr_threads <= 1) {
+		fn(arg);
+		return 0;
+	}
+
+	threads = calloc(nr_threads, sizeof(*threads));
+	if (!threads) {
+		ERROR_GLIBC("calloc");
+		return -1;
+	}
+
+	for (nr_started = 0; nr_started < nr_threads; nr_started++) {
+		if (pthread_create(&threads[nr_started], NULL, fn, arg)) {
+			ERROR_GLIBC("pthread_create");
+			ret = -1;
+			break;
+		}
+	}
+
+	for (i = 0; i < nr_started; i++)
+		pthread_join(threads[i], NULL);
+
+	free(threads);
+	return ret;
+}
+
+/* Hand out the ranges one at a time, or NULL once they are all taken. */
+static struct insn_range *claim_decode_range(void)
+{
+	const unsigned int idx = __sync_fetch_and_add(&next_decode_range, 1);
+
+	return idx < nr_decode_ranges ? &decode_ranges[idx] : NULL;
+}
+
+static void *range_worker(void *arg)
+{
+	const struct range_work *work = arg;
+	struct insn_range *range;
+
+	while ((range = claim_decode_range()))
+		range->ret = work->fn(&range->shadow, range);
+
+	return NULL;
+}
+
+/* The lists in the objtool_file that the passes add instructions to. */
+static const size_t shadow_list_offsets[] = {
+	offsetof(struct objtool_file, retpoline_call_list),
+	offsetof(struct objtool_file, return_thunk_list),
+	offsetof(struct objtool_file, static_call_list),
+	offsetof(struct objtool_file, mcount_loc_list),
+	offsetof(struct objtool_file, endbr_list),
+	offsetof(struct objtool_file, call_list),
+};
+
+static struct list_head *shadow_list(struct objtool_file *file,
+				     unsigned int idx)
+{
+	return (void *)file + shadow_list_offsets[idx];
+}
+
+static void init_range_shadow(struct objtool_file *file,
+			      struct insn_range *range)
+{
+	unsigned int i;
+
+	range->shadow = *file;
+	range->ret = 0;
+	for (i = 0; i < ARRAY_SIZE(shadow_list_offsets); i++)
+		INIT_LIST_HEAD(shadow_list(&range->shadow, i));
+}
+
+/* Joined in range order, which is the order a single walk would produce. */
+static int join_range_shadow(struct objtool_file *file,
+			     struct insn_range *range)
+{
+	unsigned int i;
+
+	for (i = 0; i < ARRAY_SIZE(shadow_list_offsets); i++)
+		list_splice_tail(shadow_list(&range->shadow, i),
+				 shadow_list(file, i));
+
+	return range->ret;
+}
+
+/* Run a pass over the instructions, one range per thread at a time. */
+static int run_insn_ranges(struct objtool_file *file, range_fn_t fn)
+{
+	struct range_work work = { .fn = fn };
+	unsigned int i;
+	int ret = 0;
+
+	for (i = 0; i < nr_decode_ranges; i++)
+		init_range_shadow(file, &decode_ranges[i]);
+	next_decode_range = 0;
+
+	if (run_threads(range_worker, &work, nr_decode_threads))
+		return -1;
+
+	for (i = 0; i < nr_decode_ranges; i++) {
+		if (join_range_shadow(file, &decode_ranges[i]))
+			ret = -1;
+	}
+
+	return ret;
+}
+
+static int add_decode_range(struct section *sec, unsigned long start,
+			    unsigned long end)
+{
+	const size_t size = (nr_decode_ranges + 1) * sizeof(*decode_ranges);
+	struct insn_range *range;
+
+	decode_ranges = realloc(decode_ranges, size);
+	if (!decode_ranges) {
+		ERROR_GLIBC("realloc");
+		return -1;
+	}
+
+	range = &decode_ranges[nr_decode_ranges++];
+	memset(range, 0, sizeof(*range));
+	range->sec = sec;
+	range->start = start;
+	range->end = end;
+
+	return 0;
+}
+
+/* Split a section into ranges of roughly range_size, at function starts. */
+static int add_decode_ranges(struct section *sec, unsigned long range_size)
+{
+	const unsigned long size = sec_size(sec);
+	unsigned long start = 0;
+	struct symbol *sym;
+
+	if (!range_size)
+		return add_decode_range(sec, 0, size);
+
+	sec_for_each_sym(sec, sym) {
+		if (!is_func_sym(sym) || sym->offset <= start ||
+		    sym->offset >= size)
+			continue;
+		if (sym->offset - start < range_size)
+			continue;
+
+		if (add_decode_range(sec, start, sym->offset))
+			return -1;
+		start = sym->offset;
+	}
+
+	return add_decode_range(sec, start, size);
+}
+
+static void free_decode_ranges(void)
+{
+	free(decode_ranges);
+	decode_ranges = NULL;
+	nr_decode_ranges = 0;
+	next_decode_range = 0;
+}
+
+/* A range's first instruction follows the last of the range before it. */
+static void link_decode_ranges(void)
+{
+	unsigned int i;
+
+	for (i = 1; i < nr_decode_ranges; i++) {
+		const struct insn_range *prev = &decode_ranges[i - 1];
+		struct insn_range *range = &decode_ranges[i];
+
+		if (prev->sec != range->sec || !prev->last || !range->first)
+			continue;
+
+		range->first->prev_len = prev->last->len;
+	}
+}
+
+static unsigned int decode_threads(unsigned long text_size)
+{
+	const long nr_cpus = sysconf(_SC_NPROCESSORS_ONLN);
+
+	/* Modules are processed inside the parallel build, on one thread. */
+	if (!opts.link || opts.module)
+		return 1;
+	if (text_size < DECODE_THREADED_MIN_TEXT || nr_cpus < 2)
+		return 1;
+
+	return min_t(unsigned int, nr_cpus, DECODE_MAX_THREADS);
+}
+
+/* Several ranges per thread so uneven ones balance out; 0 means per section. */
+static unsigned long decode_range_size(unsigned long text_size,
+				       unsigned int nr_threads)
+{
+	const unsigned int nr_ranges = nr_threads * DECODE_RANGES_PER_THREAD;
+
+	if (nr_threads <= 1)
+		return 0;
+
+	return text_size / nr_ranges;
+}
+
 /*
  * Call the arch-specific instruction decoder for all the instructions and add
  * them to the global instruction list.
  */
 static int decode_instructions(struct objtool_file *file)
 {
+	const unsigned long text_size = total_text_size(file);
+	unsigned long range_size;
+	struct instruction *insn;
 	struct section *sec;
 	struct symbol *func;
-	unsigned long offset;
-	struct instruction *insn;
+	unsigned int i;
 
-	if (alloc_insn_hash(file, total_text_size(file)))
+	if (alloc_insn_hash(file, text_size))
 		return -1;
 
+	nr_decode_threads = decode_threads(text_size);
+	range_size = decode_range_size(text_size, nr_decode_threads);
+
 	for_each_sec(file->elf, sec) {
-		struct instruction *insns = NULL;
-		u8 prev_len = 0;
-		u8 idx = 0;
 
 		if (!is_text_sec(sec))
 			continue;
@@ -494,41 +829,20 @@ static int decode_instructions(struct objtool_file *file)
 		if (!strcmp(sec->name, ".init.text") && !opts.module)
 			sec->init = true;
 
-		for (offset = 0; offset < sec_size(sec); offset += insn->len) {
-			if (!insns || idx == INSN_CHUNK_MAX) {
-				insns = calloc(INSN_CHUNK_SIZE, sizeof(*insn));
-				if (!insns) {
-					ERROR_GLIBC("calloc");
-					return -1;
-				}
-				idx = 0;
-			} else {
-				idx++;
-			}
-			insn = &insns[idx];
-			insn->idx = idx;
-
-			INIT_LIST_HEAD(&insn->call_node);
-			insn->sec = sec;
-			insn->offset = offset;
-			insn->prev_len = prev_len;
+		if (add_decode_ranges(sec, range_size))
+			return -1;
+	}
 
-			if (arch_decode_instruction(file, sec, offset, sec_size(sec) - offset, insn))
-				return -1;
+	if (run_insn_ranges(file, decode_range))
+		return -1;
 
-			prev_len = insn->len;
+	for (i = 0; i < nr_decode_ranges; i++)
+		nr_insns += decode_ranges[i].nr_insns;
+	link_decode_ranges();
 
-			/*
-			 * By default, "ud2" is a dead end unless otherwise
-			 * annotated, because GCC 7 inserts it for certain
-			 * divide-by-zero cases.
-			 */
-			if (insn->type == INSN_BUG)
-				insn->dead_end = true;
-
-			hlist_add_head(&insn->hash, insn_hash_head(file, sec, insn->offset));
-			nr_insns++;
-		}
+	for_each_sec(file->elf, sec) {
+		if (!is_text_sec(sec))
+			continue;
 
 		sec_for_each_sym(sec, func) {
 			if (!is_notype_sym(func) && !is_func_sym(func))
@@ -1571,133 +1885,147 @@ static bool is_first_func_insn(struct objtool_file *file,
 /*
  * Find the destination instructions for all jumps.
  */
-static int add_jump_destinations(struct objtool_file *file)
+static int add_jump_destination(struct objtool_file *file, struct instruction *insn)
 {
-	struct instruction *insn;
 	struct reloc *reloc;
+	struct symbol *func = insn_func(insn);
+	struct instruction *dest_insn;
+	struct section *dest_sec;
+	struct symbol *dest_sym;
+	unsigned long dest_off;
 
-	for_each_insn(file, insn) {
-		struct symbol *func = insn_func(insn);
-		struct instruction *dest_insn;
-		struct section *dest_sec;
-		struct symbol *dest_sym;
-		unsigned long dest_off;
+	if (!is_static_jump(insn))
+		return 0;
 
-		if (!is_static_jump(insn))
-			continue;
+	if (insn->jump_dest) {
+		/*
+		 * handle_group_alt() may have previously set
+		 * 'jump_dest' for some alternatives.
+		 */
+		return 0;
+	}
 
-		if (insn->jump_dest) {
-			/*
-			 * handle_group_alt() may have previously set
-			 * 'jump_dest' for some alternatives.
-			 */
-			continue;
-		}
+	reloc = insn_reloc(file, insn);
+	if (!reloc) {
+		dest_sec = insn->sec;
+		dest_off = arch_jump_destination(insn);
+		dest_sym = dest_sec->sym;
+	} else {
+		dest_sym = reloc->sym;
+		if (is_undef_sym(dest_sym)) {
+			if (dest_sym->retpoline_thunk) {
+				if (add_retpoline_call(file, insn))
+					return -1;
+				return 0;
+			}
 
-		reloc = insn_reloc(file, insn);
-		if (!reloc) {
-			dest_sec = insn->sec;
-			dest_off = arch_jump_destination(insn);
-			dest_sym = dest_sec->sym;
-		} else {
-			dest_sym = reloc->sym;
-			if (is_undef_sym(dest_sym)) {
-				if (dest_sym->retpoline_thunk) {
-					if (add_retpoline_call(file, insn))
-						return -1;
-					continue;
-				}
+			if (dest_sym->return_thunk) {
+				add_return_call(file, insn, true);
+				return 0;
+			}
 
-				if (dest_sym->return_thunk) {
-					add_return_call(file, insn, true);
-					continue;
-				}
+			/* External symbol */
+			if (func) {
+				/* External sibling call */
+				if (add_call_dest(file, insn, dest_sym, true))
+					return -1;
+				return 0;
+			}
 
-				/* External symbol */
-				if (func) {
-					/* External sibling call */
-					if (add_call_dest(file, insn, dest_sym, true))
-						return -1;
-					continue;
-				}
+			/* Non-func asm code jumping to external symbol */
+			return 0;
+		}
 
-				/* Non-func asm code jumping to external symbol */
-				continue;
-			}
+		dest_sec = dest_sym->sec;
+		dest_off = dest_sym->offset + arch_insn_adjusted_addend(insn, reloc);
+	}
 
-			dest_sec = dest_sym->sec;
-			dest_off = dest_sym->offset + arch_insn_adjusted_addend(insn, reloc);
+	dest_insn = find_insn(file, dest_sec, dest_off);
+	if (!dest_insn) {
+		struct symbol *sym = find_symbol_by_offset(dest_sec, dest_off);
+
+		/*
+		 * retbleed_untrain_ret() jumps to
+		 * __x86_return_thunk(), but objtool can't find
+		 * the thunk's starting RET instruction,
+		 * because the RET is also in the middle of
+		 * another instruction.  Objtool only knows
+		 * about the outer instruction.
+		 */
+		if (sym && sym->embedded_insn) {
+			add_return_call(file, insn, false);
+			return 0;
 		}
 
-		dest_insn = find_insn(file, dest_sec, dest_off);
-		if (!dest_insn) {
-			struct symbol *sym = find_symbol_by_offset(dest_sec, dest_off);
+		/*
+		 * GCOV/KCOV dead code can jump to the end of
+		 * the function/section.
+		 */
+		if (file->ignore_unreachables && func &&
+		    dest_sec == insn->sec &&
+		    dest_off == func->offset + func->len)
+			return 0;
 
-			/*
-			 * retbleed_untrain_ret() jumps to
-			 * __x86_return_thunk(), but objtool can't find
-			 * the thunk's starting RET instruction,
-			 * because the RET is also in the middle of
-			 * another instruction.  Objtool only knows
-			 * about the outer instruction.
-			 */
-			if (sym && sym->embedded_insn) {
-				add_return_call(file, insn, false);
-				continue;
-			}
+		ERROR_INSN(insn, "can't find jump dest instruction at %s",
+			   offstr(dest_sec, dest_off));
+		return -1;
+	}
 
-			/*
-			 * GCOV/KCOV dead code can jump to the end of
-			 * the function/section.
-			 */
-			if (file->ignore_unreachables && func &&
-			    dest_sec == insn->sec &&
-			    dest_off == func->offset + func->len)
-				continue;
+	if (!dest_sym || is_sec_sym(dest_sym)) {
+		dest_sym = insn_sym(dest_insn);
+		if (!dest_sym)
+			goto set_jump_dest;
+	}
 
-			ERROR_INSN(insn, "can't find jump dest instruction at %s",
-				   offstr(dest_sec, dest_off));
+	if (dest_sym->retpoline_thunk && dest_insn->offset == dest_sym->offset) {
+		if (add_retpoline_call(file, insn))
 			return -1;
-		}
+		return 0;
+	}
 
-		if (!dest_sym || is_sec_sym(dest_sym)) {
-			dest_sym = insn_sym(dest_insn);
-			if (!dest_sym)
-				goto set_jump_dest;
-		}
+	if (dest_sym->return_thunk && dest_insn->offset == dest_sym->offset) {
+		add_return_call(file, insn, true);
+		return 0;
+	}
 
-		if (dest_sym->retpoline_thunk && dest_insn->offset == dest_sym->offset) {
-			if (add_retpoline_call(file, insn))
-				return -1;
-			continue;
-		}
+	if (!insn_sym(insn) || insn_sym(insn)->pfunc == dest_sym->pfunc)
+		goto set_jump_dest;
 
-		if (dest_sym->return_thunk && dest_insn->offset == dest_sym->offset) {
-			add_return_call(file, insn, true);
-			continue;
-		}
+	/*
+	 * Internal cross-function jump.
+	 */
 
-		if (!insn_sym(insn) || insn_sym(insn)->pfunc == dest_sym->pfunc)
-			goto set_jump_dest;
+	if (is_first_func_insn(file, dest_insn)) {
+		/* Internal sibling call */
+		if (add_call_dest(file, insn, dest_sym, true))
+			return -1;
+		return 0;
+	}
 
-		/*
-		 * Internal cross-function jump.
-		 */
+set_jump_dest:
+	insn->jump_dest = dest_insn;
 
-		if (is_first_func_insn(file, dest_insn)) {
-			/* Internal sibling call */
-			if (add_call_dest(file, insn, dest_sym, true))
-				return -1;
-			continue;
-		}
+	return 0;
+}
 
-set_jump_dest:
-		insn->jump_dest = dest_insn;
+static int add_jump_destinations_range(struct objtool_file *file,
+				       struct insn_range *range)
+{
+	struct instruction *insn;
+
+	range_for_each_insn(file, range, insn) {
+		if (add_jump_destination(file, insn))
+			return -1;
 	}
 
 	return 0;
 }
 
+static int add_jump_destinations(struct objtool_file *file)
+{
+	return run_insn_ranges(file, add_jump_destinations_range);
+}
+
 static struct symbol *find_call_destination(struct section *sec, unsigned long offset)
 {
 	struct symbol *call_dest;
@@ -1712,59 +2040,82 @@ static struct symbol *find_call_destination(struct section *sec, unsigned long o
 /*
  * Find the destination instructions for all calls.
  */
-static int add_call_destinations(struct objtool_file *file)
+static int add_call_destination(struct objtool_file *file, struct instruction *insn)
 {
-	struct instruction *insn;
 	unsigned long dest_off;
 	struct symbol *dest;
 	struct reloc *reloc;
+	struct symbol *func = insn_func(insn);
 
-	for_each_insn(file, insn) {
-		struct symbol *func = insn_func(insn);
-		if (insn->type != INSN_CALL)
-			continue;
+	if (insn->type != INSN_CALL)
+		return 0;
 
-		reloc = insn_reloc(file, insn);
-		if (!reloc) {
-			dest_off = arch_jump_destination(insn);
-			dest = find_call_destination(insn->sec, dest_off);
+	reloc = insn_reloc(file, insn);
+	if (!reloc) {
+		dest_off = arch_jump_destination(insn);
+		dest = find_call_destination(insn->sec, dest_off);
 
-			if (add_call_dest(file, insn, dest, false))
-				return -1;
+		if (add_call_dest(file, insn, dest, false))
+			return -1;
 
-			if (func && func->ignore)
-				continue;
+		if (func && func->ignore)
+			return 0;
 
-			if (!insn_call_dest(insn)) {
-				ERROR_INSN(insn, "unannotated intra-function call");
-				return -1;
-			}
+		if (!insn_call_dest(insn)) {
+			ERROR_INSN(insn, "unannotated intra-function call");
+			return -1;
+		}
 
-			if (func && !is_func_sym(insn_call_dest(insn))) {
-				ERROR_INSN(insn, "unsupported call to non-function");
-				return -1;
-			}
+		if (func && !is_func_sym(insn_call_dest(insn))) {
+			ERROR_INSN(insn, "unsupported call to non-function");
+			return -1;
+		}
 
-		} else if (is_sec_sym(reloc->sym)) {
-			dest_off = arch_insn_adjusted_addend(insn, reloc);
-			dest = find_call_destination(reloc->sym->sec, dest_off);
-			if (!dest) {
-				ERROR_INSN(insn, "can't find call dest symbol at %s+0x%lx",
-					   reloc->sym->sec->name, dest_off);
-				return -1;
-			}
+	} else if (is_sec_sym(reloc->sym)) {
+		dest_off = arch_insn_adjusted_addend(insn, reloc);
+		dest = find_call_destination(reloc->sym->sec, dest_off);
+		if (!dest) {
+			ERROR_INSN(insn, "can't find call dest symbol at %s+0x%lx",
+				   reloc->sym->sec->name, dest_off);
+			return -1;
+		}
 
-			if (add_call_dest(file, insn, dest, false))
-				return -1;
+		if (add_call_dest(file, insn, dest, false))
+			return -1;
 
-		} else if (reloc->sym->retpoline_thunk) {
-			if (add_retpoline_call(file, insn))
-				return -1;
+	} else if (reloc->sym->retpoline_thunk) {
+		if (add_retpoline_call(file, insn))
+			return -1;
 
-		} else {
-			if (add_call_dest(file, insn, reloc->sym, false))
-				return -1;
-		}
+	} else {
+		if (add_call_dest(file, insn, reloc->sym, false))
+			return -1;
+	}
+
+	return 0;
+}
+
+static int add_call_destinations_range(struct objtool_file *file,
+				       struct insn_range *range)
+{
+	struct instruction *insn;
+
+	range_for_each_insn(file, range, insn) {
+		if (add_call_destination(file, insn))
+			return -1;
+	}
+
+	return 0;
+}
+
+/* Serial: annotating a call site rewrites instructions the dead end walks read. */
+static int add_call_destinations(struct objtool_file *file)
+{
+	unsigned int i;
+
+	for (i = 0; i < nr_decode_ranges; i++) {
+		if (add_call_destinations_range(file, &decode_ranges[i]))
+			return -1;
 	}
 
 	return 0;
@@ -2733,6 +3084,8 @@ int decode_file(struct objtool_file *file)
 	if (read_annotate(file, __annotate_late))
 		return -1;
 
+	free_decode_ranges();
+
 	return 0;
 }
 
diff --git a/tools/objtool/elf.c b/tools/objtool/elf.c
index bd463b5df38c..308877df6ad6 100644
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -16,6 +16,7 @@
 #include <string.h>
 #include <unistd.h>
 #include <errno.h>
+#include <pthread.h>
 #include <ctype.h>
 #include <linux/align.h>
 #include <linux/kernel.h>
@@ -475,6 +476,7 @@ static int reloc_cache_add(struct section *rsec, unsigned int pos)
 }
 
 static unsigned long num_relocs_sorted;
+static pthread_mutex_t reloc_cache_lock = PTHREAD_MUTEX_INITIALIZER;
 
 static int init_reloc_cache(struct section *rsec)
 {
@@ -514,8 +516,17 @@ struct reloc *find_reloc_by_dest_range(const struct elf *elf, struct section *se
 	if (!rsec)
 		return NULL;
 
-	if (!rsec->sorted && init_reloc_cache(rsec))
-		exit(1);
+	/* Decoding looks up from several threads, rebuild an index once. */
+	if (!rsec->sorted) {
+		int ret = 0;
+
+		pthread_mutex_lock(&reloc_cache_lock);
+		if (!rsec->sorted)
+			ret = init_reloc_cache(rsec);
+		pthread_mutex_unlock(&reloc_cache_lock);
+		if (ret)
+			exit(1);
+	}
 
 	cache_idx = reloc_cache_index(offset);
 	if (cache_idx >= rsec->nr_cache_windows)
diff --git a/tools/objtool/objtool.c b/tools/objtool/objtool.c
index 71e048f8582a..f472dfe7a773 100644
--- a/tools/objtool/objtool.c
+++ b/tools/objtool/objtool.c
@@ -8,6 +8,7 @@
 #include <string.h>
 #include <stdlib.h>
 #include <unistd.h>
+#include <pthread.h>
 #include <subcmd/exec-cmd.h>
 #include <subcmd/pager.h>
 #include <linux/kernel.h>
@@ -41,6 +42,8 @@ struct objtool_file *objtool_open_read(const char *filename)
 	return &file;
 }
 
+static pthread_mutex_t pv_ops_lock = PTHREAD_MUTEX_INITIALIZER;
+
 int objtool_pv_add(struct objtool_file *f, int idx, struct symbol *func)
 {
 	if (!opts.noinstr)
@@ -59,12 +62,15 @@ int objtool_pv_add(struct objtool_file *f, int idx, struct symbol *func)
 	    !strcmp(func->name, "_paravirt_ident_64"))
 		return 0;
 
+	pthread_mutex_lock(&pv_ops_lock);
+
 	/* already added this function */
-	if (!list_empty(&func->pv_target))
-		return 0;
+	if (list_empty(&func->pv_target)) {
+		list_add(&func->pv_target, &f->pv_ops[idx].targets);
+		f->pv_ops[idx].clean = false;
+	}
 
-	list_add(&func->pv_target, &f->pv_ops[idx].targets);
-	f->pv_ops[idx].clean = false;
+	pthread_mutex_unlock(&pv_ops_lock);
 	return 0;
 }
 

-- 
2.56.0

[PATCH v5 10/11] rust: make exports.o depend on the headers generated for it

[Lorenzo Stoakes (ARM)]

rust/exports.c includes the exports_*_generated.h listing the symbols of
the core, bindings, kernel and helpers objects, but this is not expressed
in its Makefile.

This worked previously because the headers are always-y targets, and make
prepare built all of the rust crates first, which is an implicit
dependency.

Fix this as it is a dependency of the subsequent commit.

Reviewed-by: Nicolas Schier <n.schier@fritz.com>
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 rust/Makefile | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/rust/Makefile b/rust/Makefile
index 0ac9ab28cc2b..cee016cd8d32 100644
--- a/rust/Makefile
+++ b/rust/Makefile
@@ -728,6 +728,11 @@ endef
 $(obj)/helpers/helpers.o: $(src)/helpers/helpers.c $(recordmcount_source) FORCE
 	+$(call if_changed_rule,rust_cc_library)
 
+# The exported symbol lists are generated from the crates' objects.
+$(obj)/exports.o: $(obj)/exports_core_generated.h \
+    $(obj)/exports_bindings_generated.h $(obj)/exports_kernel_generated.h \
+    $(if $(CONFIG_RUST_INLINE_HELPERS),,$(obj)/exports_helpers_generated.h)
+
 # Disable symbol versioning for exports.o to avoid conflicts with the actual
 # symbol versions generated from Rust objects.
 $(obj)/exports.o: private skip_gendwarfksyms = 1

-- 
2.56.0

[PATCH v5 11/11] kbuild: build rust crates in parallel with the rest of the build

[Lorenzo Stoakes (ARM)]

When CONFIG_RUST is specified make prepare builds all of the rust
components before descending into the tree.

This means nothing can be done until all of these are compiled, resulting
in a stall at the start of every clean CONFIG_RUST build.

This also implicitly slows down every rust-capable LLVM allmodconfig build
as this enables the CONFIG_RUST option.

Fix this by allowing rust crates to be built alongside the C code.

Remove the rust build from the make prepare step, then establish a
dependency between rust code located elsewhere in the tree upon rust
components contained in rust/.

Do this by establishing a top-level list of directories containing rust
code, KBUILD_RUST_DIRS, upon which the dependency is expressed.

Finally, ensure that no rust code is located elsewhere and fail the build
if any is found to ensure that nothing is missed in future.

Care is taken to ensure the rust/ dependency is also established for any
module being built to account for external rust modules which rely upon it,
and that only one rust/ build will be performed at any one time.

External rust modules builds are unaffected - make modules_prepare ...
(where ... are other goals) will build rust/ first.

The rustdoc and rusttest goals invoke rust/ directly rather than via
Kbuild, so build rust/ first there too.

Every Rust and C object was confirmed to be byte-for-byte identical after
this change.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig+RUST, clean                36.5s    32.6s     -3.9s (-11%)
  x86 allmodconfig, clean                 297.0s   278.3s    -18.7s (-6%)

Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
---
 Kbuild                 |  5 +++++
 Makefile               | 17 ++++++++++++++++-
 scripts/Makefile.build |  5 ++++-
 3 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/Kbuild b/Kbuild
index a6a0192dea08..9670556059dd 100644
--- a/Kbuild
+++ b/Kbuild
@@ -115,3 +115,8 @@ obj-$(CONFIG_NET)	+= net/
 obj-y			+= virt/
 obj-y			+= $(ARCH_DRIVERS)
 obj-$(CONFIG_DRM_HEADER_TEST)	+= include/
+
+# Rust code elsewhere in the tree depends upon rust/.
+ifdef CONFIG_RUST
+$(KBUILD_RUST_DIRS): | rust
+endif
diff --git a/Makefile b/Makefile
index 7c254b8657a3..de4cc052af03 100644
--- a/Makefile
+++ b/Makefile
@@ -1416,11 +1416,14 @@ prepare0: archprepare
 	$(Q)$(MAKE) $(build)=. prepare
 	$(Q)$(MAKE) $(build)=scripts/mod
 
+ifdef CONFIG_RUST
+export KBUILD_RUST_DIRS := drivers lib mm samples
+endif
+
 # All the preparing..
 prepare: prepare0
 ifdef CONFIG_RUST
 	+$(Q)$(CONFIG_SHELL) $(srctree)/scripts/rust_is_available.sh
-	$(Q)$(MAKE) $(build)=rust
 endif
 
 PHONY += remove-stale-files
@@ -1767,6 +1770,14 @@ modules: modules_prepare
 # Target to prepare building external modules
 modules_prepare: prepare
 	$(Q)$(MAKE) $(build)=scripts scripts/module.lds
+ifdef CONFIG_RUST
+# Avoid two instances of rust/ being built at any one time.
+ifneq ($(filter modules_prepare,$(MAKECMDGOALS)),)
+ifeq ($(filter all vmlinux modules %Image% dtbs rustdoc rusttest,$(MAKECMDGOALS)),)
+	$(Q)$(MAKE) $(build)=rust
+endif
+endif
+endif
 
 endif # CONFIG_MODULES
 
@@ -2035,13 +2046,17 @@ rustavailable:
 # Documentation target
 #
 # Using the singular to avoid running afoul of `no-dot-config-targets`.
+#
+# rust/ is built alongside the rest of the tree, so must be built first here.
 PHONY += rustdoc
 rustdoc: prepare
+	$(Q)$(MAKE) $(build)=rust
 	$(Q)$(MAKE) $(build)=rust $@
 
 # Testing target
 PHONY += rusttest
 rusttest: prepare
+	$(Q)$(MAKE) $(build)=rust
 	$(Q)$(MAKE) $(build)=rust $@
 
 # Formatting targets
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index 7b652f169a8f..ec4e220d6831 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -381,8 +381,11 @@ quiet_cmd_rustc_o_rs = $(RUSTC_OR_CLIPPY_QUIET) $(quiet_modtag) $@
 		$(cmd_ld_single)) \
 	$(cmd_objtool)
 
+rust-dir-ok = $(or $(KBUILD_EXTMOD),$(filter rust $(KBUILD_RUST_DIRS),$(firstword $(subst /, ,$@))))
+
+# Ensure that any rust code located elsewhere from rust/ is listed in KBUILD_RUST_DIRS.
 define rule_rustc_o_rs
-	$(call cmd_and_fixdep,rustc_o_rs)
+	$(if $(rust-dir-ok),,$(error $@: Rust code in a directory not listed in KBUILD_RUST_DIRS, see the top Makefile))$(call cmd_and_fixdep,rustc_o_rs)
 	$(call cmd,gen_objtooldep)
 endef
 

-- 
2.56.0