[RFC] Emit relocation failure statistics

Subprojects LLD
1

Hi!

We are currently facing relocation overflow failures at Meta.
I’ve started the Massive Binary working group alongside @aeubanks to redesign a new code-model to address a lot of the challenges we have faced with the current available options.

( [RFC] Forming a Massive Binaries Working Group in LLD )

I wanted to better understand globally what the different relocation failures we are facing.
We have some simple parsing from the output (slightly patched to be a bit more ergonomic) to categorize the relocation failure types however we limit lld error messages to 100

ld.lld: error: too many errors emitted, stopping now (use --error-limit=0 to see all errors)
clang++: error: linker command failed with exit code 1 (use -v to see invocation)

We’ve done this to help reduce the amount of bytes we send to various logging platforms however now I lose visibility into the complete view of all the various relocations I would have faced since often the first 100 are occupied by a single type (i.e. gcc_except_table → data)

I would like to propose an option for LLD to emit a structured file with enough information for us to categorize all the failures (could be scoped to relocation failures to start).

Here is a proposed schema merely to demonstrate the type of data I am looking to surface.

{
  "version": "1.0",
  "build_context": {
    "target_triple": "x86_64-unknown-linux-gnu",
    "linker_version": "LLD 19.0.0",
    "command_line_args": ["-flavor", "gnu", "-o", "bin/huge_app", "..."],
    "total_errors_encountered": 14208
  },
  "relocation_summary": {
    "total_overflows": 14195,
    "unique_overflow_types": 3
  },
  "failures": [
    {
      "reloc_type_id": "R_X86_64_PC32",
      "reloc_type_name": "R_X86_64_PC32",
      "count": 12450,
      "description": "32-bit PC-relative relocation overflow",
      "section_pair": {
        "source_section": ".gcc_except_table",
        "target_section": ".text"
      },
      "overflow_characteristics": {
        "max_negative_displacement": -34359738368,
        "max_positive_displacement": 4294967296,
        "reloc_limit_bits": 32,
        "is_signed": true
      },
      "samples": [
        {
          "source_file": "path/to/folly/experimental/huge_file.cpp.o",
          "source_symbol": "void folly::detail::complex_template_instantiation<int>()",
          "source_offset": "0x00001a4c",
          "target_symbol": "typeinfo for std::exception",
          "target_section": ".rodata",
          "calculated_displacement": -34359738368
        }
      ]
    },
    {
      "reloc_type_id": "R_AARCH64_CALL26",
      "reloc_type_name": "R_AARCH64_CALL26",
      "count": 1745,
      "description": "26-bit branch instruction offset out of range (+/-128MB)",
      "section_pair": {
        "source_section": ".text",
        "target_section": ".text"
      },
      "overflow_characteristics": {
        "max_positive_displacement": 157286400,
        "reloc_limit_bits": 26,
        "is_signed": true
      },
      "samples": [
        {
          "source_file": "path/to/engine/core.cpp.o",
          "source_symbol": "engine::run_main_loop()",
          "source_offset": "0x0004f210",
          "target_symbol": "fbcode::logging::log_verbose_impl()",
          "target_section": ".text",
          "calculated_displacement": 157286400
        }
      ]
    }
  ]
}
2

Some early thoughts based on some prior experience.

AFAIK lld always outputs errors to stderr. A simpler option that may get you closer, and could be done independently is a command-line option to redirect errors to a named output file, or perhaps a name derived from the output filename. That may be enough to allow all of the lld errors to be output, without swamping a log file. Arm’s proprietary linker had a --errors=err.txt which was useful, although sometimes confusing when the link failed but there was no visible error message on the terminal.

I recommend starting with the failed relocations. Arm’s proprietary linker had an internal trace option that would output details of each relocation, and on what I would consider large (tens of megabytes), the output was overwhelmingly large. Often I only wanted to see the one or two failing cases in millions of relocations. I also think that the amount of changes to LLD that would be needed to output all relocations would be disproportionately large compared to just the errors.

There has been some discussion, particularly in the embedded systems working group, about machine readable map files (-Map=map.txt). With the thought of JSON output that could be translated to GNU map file syntax so that BFD and lld map files could be compared. No one has yet stepped forward to implement it yet. I mention it here as one of the design decisions is whether all of the output went to one file, or whether it could all be independently redirected to a different file. Relocation failures could in theory be part of the same machine readable output, or it could be independent.

Looking at the contents of the sample schema, it looks like most of the information can be obtained by recording information from the existing elf::reportRangeError() and processing the output later. I recommend not including static information that can be derived from the ABI documents for the processor, I expect a small number of relocations causing most of the failures and these would be well known.

3

I don’t think this is warranted in this current form.

The error cap isn’t a property of lld. You can raise --error-limit=.
The content is already there too. elf::reportRangeError has quite detailed information.

What’s actually being proposed a second serializatin of data lld already produces, in a format that doesn’t match lld’s existing machine-readable outputs (-Map, --why-extract=, etc).

Must of the schema is also not data at all : triple, linker version, argv, static ABI table, … These are completely disregard binary utility conventions…

If the real complaint is that the message text doesn’t fit well with your internal system, I’m not sure the generality of the feature - and keeping it downstream is easier for you.

4

Must of the schema is also not data at all : triple, linker version, argv, static ABI table, … These are completely disregard binary utility conventions…

I don’t want to hyper-focus on the example JSON I gave; that was just a quick mock-up. The point however was to expose all failures in a compressed file, effectively statistics.

It’s not very unheard of to have tools emit statistics for errors to be more machine readable.

When building massive binaries, the number of relocation errors we can run into is massive as well, so piping that all downstream via logs is a lot of unnecessary memory, time and cost which is why we have it disabled :frowning:

5

Yes, this was what I thought was implied but maybe not.
Some new flag --emit-relocation-failures , --emit-failures or w/e
I had something similar in-mind via [lld][ELF] Add --print-relax-stats= to emit linker relaxation statistics by fzakaria · Pull Request #193631 · llvm/llvm-project · GitHub which was to expose the relaxation statistics.

I think mapping to a separate file makes sense. It could also follow on Clang’s -fdiagnostics-format to support multiple format types if we wanted.

Should I put more into a more-fleshed out RFC ?
I could design the flag and a minimal schema focused on relocation errors.

6

Should I put more into a more-fleshed out RFC ?
I could design the flag and a minimal schema focused on relocation errors.

If it is as simple as just optionally redirecting the existing errors, or maybe just the relocation error messages as they are Today to a file, then I think a PR will be sufficient as most of the discussion will be about the details.

Changing the diagnostic format is probably best done in an RFC, as that is a lot more work that could be wasted if there are objections.

7

The existing errors as they occur now redirected to a file can happen with pipes?
(Unless I misunderstood what you mean)

I would like to propose an aggregate view of these existing errors.
At a minimum something like (not verbatim but to the same effect):

 {
      "reloc_type_name": "R_X86_64_PC32",
      "count": 12450,
      "section_pair": {
        "source_section": ".gcc_except_table",
        "target_section": ".text"
      },
}

This would give us a very good grasp of the shape of the problem and severity.
For instance, if we have many text -> text then only thunks will help.

8

It is definitely possible to redirect the errors using pipes. The reason I mentioned a command-line option was that it could fit better in an existing build system, particularly if there were multiple links. For example for each -o filename.so there could be filename.so.linkerr that could be collected.

I may have misunderstood your original post.

Looking at the “samples” section made it look like the output would be considerably larger than just increasing the error limit and collecting all the relocation error messages. I had assumed that it was just overloading the build log, which often is many megabytes long already was the problem.

If there is only a entry for each pair of output sections then that would produce a lot smaller output.

I think it would be useful to make a specific RFC. In particular I think it would need to answer:

  • Does it need information that can’t be derived from unlimited error messages and the output of -Map?
  • Is the unlimited error message output after some kind of redirection to a separate file too big to process?
  • Is this likely to be information needed over time? It looks like a useful analysis for designing a large code-model, however once the code-model is designed and implemented, will anyone need this?

In the general case I’m in favour of outputing more lower-level diagnostics in a machine readable format that is easy to post-process. That lets more people do their own specific analysis. I think there can be scope to hard-code an analysis in LLD, but it would need to be widely applicable.

9

I will work on a general RFC but I thought it would help to give some numbers on how much output is given for a large binary – I think @MaskRay this might help to shed light on the magnitude.

When linking a “massive binary” (i.e. .text > 2GiB) we have millions of relocations.

I did an audit on a random failing binary I found and set --error-limit=0 to see how much data we would produce

In this binary here are ~95,000 total failing relocations (after GC and discarding sections).

lld-21 produces entries like so:

ld.lld: error: buck-out/v2/art/fbcode/koski/functions_contrib/df4ai/__cmsl_data_fm_laser_inject__/09eb4f47f6ece734/__stripped__/CmslDataFmLaserInject.cpp.pic.stripped.o:(.gcc_except_table._ZZN8examples5vecto4bits10forEachBitIZNS0_4exec7EvalCtx22applyToSelectedNoThrowIZNKS3_21SimpleFunctionAdapterINS0_4core9UDFHolderINS_5alpha5ml4op12_GLOBAL__N_122GenericFeatureColumnXXINS3_10VectorExecELb1EEESD_NS0_3MapIiNS0_5ArrayIlEEEENS0_15ConstantCheckerIJlNS0_7VarcharESK_EEEJlSK_SK_EEEE8applyUdf
IZNKSN_7iterateIJNS3_16FlatVectorReaderIlEENS3_20ConstantVectorReaderISK_EENSQ_ISK_EEEEEvRNSN_12ApplyContextEDpRT_EUlRT_RT0_T1_E_EEvSW_S10_EUlS10_E_ZN
KSO_IS15_EEvSW_S10_EUlS10_E0_EEvRKNS0_17SelectivityVectorES10_S12_EUlS10_E_EEvPKmiibS10_ENKUlimE_clEim+0x74): relocation R_X86_64_PC32 out of range: 4636074732 is not in [-2147483648, 2147483647]; references section '.data'

This produces a stderr logstream of ~55MiB which is pretty significant given the number of builds we run and which are failing per minute.

I believe that size alone is enough to warrant a top-level statistics file, however we have some “improved” output to the error messaging already for relocation overflow based on internal feedback (we’ve tried to upstream some of this however it was rejected but it’s been a big help to us internally).

A sample output for each relocation overflow for us looks like (anonymized):

Our more verbose relocation overflow erorr messaging 
=============================================================================
                           RELOCATION OVERFLOW DETAILS
=============================================================================

  RELOCATION:
          type:   R_X86_64_PC32
          expr:   14
          offset: 1464 (0x000005b8)
          addend: 0 (0x00000000)

  SOURCE:
          object file:    ../abcdef0123456789/__stripped__/generated_kernels_42.cpp.pic.stripped.o
          input section:  .gcc_except_table._ZN7example14KernelLauncher24fused_generated_operationEv
                          (example::KernelLauncher::fused_generated_operation(...))
                  offset in output section: 4211408 (0x004042d0)
                  size:                     1472 (0x000005c0) (1.44 KiB)
                  index in output section:  62041 of 2159000
          output section: .gcc_except_table
                  address:         134667200 (0x0806dbc0)
                  offset in file:  134667200 (0x0806dbc0)
                  size:            104071168 (0x06340000) (99.25 MiB)
          address (PC): 138863704 (0x0846e458)

  TARGET:
          symbol:      <section symbol: .data>
          symbol kind: 1
          symbol VA:   2399827312 (0x8f0a7570)
          object file: ../abcdef0123456789/__stripped__/generated_kernels_42.cpp.pic.stripped.o
          input section:  .data
                  offset in output section: 14192 (0x00003770)
                  size:                     8 (0x00000008) (8 B)
                  index in output section:  1102 of 58320
          output section: .data
                  address:         2399813120 (0x8f0a3e00)
                  offset in file:  2387734016 (0x8e51ee00)
                  size:            5763072 (0x0057f000) (5.50 MiB)

  DISPLACEMENT CALCULATION (PC-relative):
          target VA + addend: 2399827312 (0x8f0a7570)
          source PC:          138863704 (0x0846e458)
          displacement:       2260963608 (0x86c39118) (2.11 GiB)
          max range:          +/- 2147483647 (2.00 GiB)


  Representative memory layout (names and sizes anonymized):

      0x0806dbc0 - .gcc_except_table (~99 MiB)
      0x0846e458 - >>> SOURCE                         ---+
      0x0e400000 - metadata sections                    |
      0x0e500000 - .eh_frame_hdr (~31 MiB)              |
      0x10300000 - .eh_frame (~174 MiB)                 |
      0x1c000000 - registration sections (~13 MiB)      |
      0x1cc00000 - .text (~1.75 GiB)                    |
      0x8c100000 - initialization and PLT sections      |
      0x8c200000 - TLS and array sections               |
      0x8c300000 - .data.rel.ro (~47 MiB)               |
      0x8f020000 - dynamic and GOT sections             |
      0x8f0a3e00 - .data (~5.50 MiB)                    |
      0x8f0a7570 - >>> TARGET                         <--+

      Distance: 2260963608 bytes (2.11 GiB)

  ============================================================================

This output casues the stderr stream for our internal lld to be ~487MiB (~10x)

  • Does it need information that can’t be derived from unlimited error messages and the output of -Map?

Technically no, but we already have to do sub-optimal parsing of raw text when a machine-friendly output would be much simpler.

  • Is the unlimited error message output after some kind of redirection to a separate file too big to process?

Yes, hopefully you concur with the numbers above.

  • Is this likely to be information needed over time? It looks like a useful analysis for designing a large code-model, however once the code-model is designed and implemented, will anyone need this?

I think if we think about extending it to all class of problems the linker might have, then it is useful. The main idea is if we want to link “massive binaries”, it’s worthwhile understanding all the problems hit up-front in a cost-efficient manner.

10

Stating this clearly upfront so you don’t spend a week on a fuller RFC: I don’t support this feature upstream, in this form or in a more fleshed-out one.

My concern isn’t the schema. Fix every field I objected to and the objection stands.

This is a presentation layer. Which fields, how they’re grouped, how samples are chosen, what format they’re in — all of it is determined by what a particular build infrastructure wants to store and query, and every company will want it differently. Your own verbose overflow output shows how far that divergence goes. Once such a file exists upstream, each subsequent request is individually cheap: one more field, one more grouping, another format. lld ends up owning a stable output format indefinitely, for an analysis that is meaningful for one class of binary and, by the working group’s own framing, is supposed to stop being necessary once the code model exists.

Peter asked whether anyone needs this over time. Your answer — that it becomes useful if extended to all classes of linker problems — argues for a larger permanent surface, not a smaller one.

On the numbers: thank you for measuring, but the 487MiB comes from a downstream diagnostic format that was already declined upstream, so 55MiB is the figure that applies here. 55MiB of stderr, on links that are already failing, redirected to a file, is not a case for a new output format. Parsing text is inconvenient; inconvenience in one downstream pipeline doesn’t justify a permanent upstream interface.

I think this belongs downstream, where you can shape it to your infrastructure without constraining everyone else.

11

I understand.

I can see your point of view;
I work on this patch internally for us – I thought to propose it upstream since others might have found the error limit / non-machine readable output a limitation as well.