[ELF] Add documentation for --warn-backrefs: a GNU ld compatibility checking tool (and lesser of layering detection)

[MaskRay]

I wonder whether we can make --warn-backrefs the default in the next release (of course we should give folks time as many are probably running --fatal-warnings and their projects may have fallout after the migration from Gold to LLD). https://lists.llvm.org/pipermail/llvm-dev/2020-August/144634.html

[amccarth]

Is there a more specific term than "traditional linker"?

I understand that LLD's search strategy is uncommon among linkers in the Posix (and/or ELF?) realm, but it's not uncommon in other linkers, even very old ones. For example, the VMS (now OpenVMS) linker has used LLD's strategy by default for many decades. (It does allow opting in to the more restrictive search.) LLD's approach matches Microsoft's link.exe. I can't be sure, but I don't recall the so-called traditional behavior from linkers from other vendors of Windows, DOS, or CP/M linkers.

I have no objection to turning the warning on in appropriate contexts or with the argument that it helps to ensure good layering. I'm just quibbling over the term "traditional."

[manojgupta]

@MaskRay Is there a global option to disable e.g --no-warn-backrefs . It is not easy for us to add -warn-backrefs-exclude=<glob> individually to all packages where we need to suppress the error.

[MaskRay]

In D86762#2244647, @amccarth wrote:

Is there a more specific term than "traditional linker"?

I understand that LLD's search strategy is uncommon among linkers in the Posix (and/or ELF?) realm, but it's not uncommon in other linkers, even very old ones. For example, the VMS (now OpenVMS) linker has used LLD's strategy by default for many decades. (It does allow opting in to the more restrictive search.) LLD's approach matches Microsoft's link.exe. I can't be sure, but I don't recall the so-called traditional behavior from linkers from other vendors of Windows, DOS, or CP/M linkers.

Maybe "traditional ELF linker" or just GNU ld?

I have no objection to turning the warning on in appropriate contexts or with the argument that it helps to ensure good layering. I'm just quibbling over the term "traditional."

Thanks!

In D86762#2244648, @manojgupta wrote:

@MaskRay Is there a global option to disable e.g --no-warn-backrefs . It is not easy for us to add -warn-backrefs-exclude=<glob> individually to all packages where we need to suppress the error.

--warn-backrefs-exclude='*' disables all warnings. We may need --no-warn-backrefs if it is more like the option users want to use. If you are happy to try out, I'd happy to know whether ChromeOS packages have no warnings if --warn-backrefs is added (--fatal-warnings upgrade warnings to errors).

[manojgupta]

--warn-backrefs-exclude='*' disables all warnings. We may need --no-warn-backrefs if it is more like the option users want to use. If you are happy to try out, I'd happy to know whether ChromeOS packages have no warnings if --warn-backrefs is added (--fatal-warnings upgrade warnings to errors).

To me, --no-warn-backrefs is more convenient and obvious. Use of "*" in a compiler or linker option can be problematic because of potential expansion of "*" by shell/tools especially when the option goes through multiple layers of tools.
And yes, we can definitely test on Chrome OS if making it default with fatal errors causes a problem for us.

[MaskRay]

In D86762#2244878, @manojgupta wrote:

--warn-backrefs-exclude='*' disables all warnings. We may need --no-warn-backrefs if it is more like the option users want to use. If you are happy to try out, I'd happy to know whether ChromeOS packages have no warnings if --warn-backrefs is added (--fatal-warnings upgrade warnings to errors).

To me, --no-warn-backrefs is more convenient and obvious. Use of "*" in a compiler or linker option can be problematic because of potential expansion of "*" by shell/tools especially when the option goes through multiple layers of tools.
And yes, we can definitely test on Chrome OS if making it default with fatal errors causes a problem for us.

dblaikie asked "Would you like to conduct the conversation here, or on the review thread?"

We can move the "can we make --warn-backrefs default" discussions to https://lists.llvm.org/pipermail/llvm-dev/2020-August/144634.html

This review can be focused on the documentation of the diagnostic (I hope that the option is important enough that it justifies its own page).

[smeenai]

In D86762#2244647, @amccarth wrote:

Is there a more specific term than "traditional linker"?

I understand that LLD's search strategy is uncommon among linkers in the Posix (and/or ELF?) realm, but it's not uncommon in other linkers, even very old ones. For example, the VMS (now OpenVMS) linker has used LLD's strategy by default for many decades. (It does allow opting in to the more restrictive search.) LLD's approach matches Microsoft's link.exe. I can't be sure, but I don't recall the so-called traditional behavior from linkers from other vendors of Windows, DOS, or CP/M linkers.

I have no objection to turning the warning on in appropriate contexts or with the argument that it helps to ensure good layering. I'm just quibbling over the term "traditional."

I can't speak to VMS, but both link.exe and ld64 (Apple's linker) have subtle differences from LLD's behavior (and you can craft examples that show the differences). For link.exe, quoting the documentation:

Object files on the command line are processed in the order they appear on the command line. Libraries are searched in command line order as well, with the following caveat: Symbols that are unresolved when bringing in an object file from a library are searched for in that library first, and then the following libraries from the command line and /DEFAULTLIB (Specify Default Library) directives, and then to any libraries at the beginning of the command line.

ld64 fetches symbols from archives that appear on the command line before the objects that reference the symbol (like LLD, and unlike a traditional Unix linker), but if an archive and an object file define the same symbol, it always prefers the object file (whereas LLD will prefer whichever appears first on the command line).

[psmith]

I had a look in Levine's Linkers and Loaders book to see if I could find any source for back-references, all I could find was in 6.4 "Not all linkers do this; many just make a single sequential pass over the directory and miss any backwards depedencies from a file to another file earlier in the library. Tools like tsort and lorder can minimize the difficulty of using single-pass linkers but it's not uncommon for programmers to explicitly list the same library several times on the linker command line to force multiple passes and thus finally resolve all symbols."

Perhaps "Single pass linker's such as GNU ld" instead of traditional linkers.

As another data point. Arm's proprietary linker (over 20 years old now) follows the LLD conventions as well, although that isn't a traditional Unix linker. My understanding is that being single pass allowed the memory used for an archive to be discarded immediately after finishing processing. This is not a concern today.

[MaskRay]

traditional linker -> single pass linker such as GNU ld

Add a note about intended omitted dependency

[MaskRay]

@psmith @grimar What do you think of the wording?

[thakis]

I don't think this should become the default.

• It's weird semantics that are an implementation artifact of bfd ld. ld64 and link.exe (and lld-link) don't have this requirement, and this is a usability win.

• It doesn't help much with layering since it only enforces that the library order on the link command is in some linear embedding of the topological walk of the dependency dag, which isn't all that useful. Layering checks want to look at the real build graph, so the linker is the wrong place for this.

[MaskRay]

In D86762#2255290, @thakis wrote:

I don't think this should become the default.

• It's weird semantics that are an implementation artifact of bfd ld. ld64 and link.exe (and lld-link) don't have this requirement, and this is a usability win.

• It doesn't help much with layering since it only enforces that the library order on the link command is in some linear embedding of the topological walk of the dependency dag, which isn't all that useful. Layering checks want to look at the real build graph, so the linker is the wrong place for this.

Discussed with thakis offline, forwarded previous discussions to thakis, and CCed thakis in my latest reply to https://lists.llvm.org/pipermail/llvm-dev/2020-September/144825.html

This patch focuses on the documentation. The "enabling by default" discussion should go to the llvm-dev thread.

[psmith]

I've put some comments, mostly concentrating on the early part. I've not had a chance to go through the examples at the bottom in detail. I can't spot anything obviously wrong though.

lld/docs/ELF/warn_backrefs.rst

5

I think it would be better to separate out LLD's library search order from BFD as this information would be useful independently of --warn-backrefs.

We could also start with a very quick summary:

--warn-backrefs gives a warning when an undefined symbol reference is resolved by a definition in a library to the left of it on the command line.

For this section (apologies for the rewrite) I suggest something like:

A linker such as GNU ld makes a single pass over the input files from left to right maintaining the set of undefined symbol references from the files loaded so far. When encountering a library or an object file surrounded by `--start-lib and --end-lib` that library will be searched for resolving symbol definitions; this may result in input files being loaded, updating the set of undefined symbol references. When all resolving definitions have been loaded from the library the linker moves on the next file and will not return to it. This means that if an input file to the right of a library cannot have an undefined symbol resolved by a library to the left of it. For example:

ld def.a ref.o

Will result in an `undefined reference error. If there are no cyclic references between libraries the libraries can be ordered in such a way that there are no backward references. If there are cyclic references then the --start-group and --end-group` options can be used, or the same library can be placed on the command line.

LLD remembers the symbol table of libraries that it has previously seen, so if there is a reference from an Input file to the right of a library, LLD will still search that library for a resolving definition for any undefined references. This means that a library only needs to be included once on the command line and the `--start-group and --end-group` options are redundant.

A consequence of the differing library searching semantics is that the same linker command line can result in different outcomes. A link may succeed with LLD that will fail with GNU ld, or even worse both links succeed but they have selected different objects from different libraries that both define the same symbols.

The `warn-backrefs option provides information that helps identify cases where LLD and GNU ld library selection may differ.

17

can identify an invocation that may be incompatible with GNU ld:

28

The `--warn-backrefs` option can also provide a check to enforce a topological order of libraries, which can be useful to detect layering violations.

49

This breaks the motivation of splitting `B, C and A` into separate libraries

67

Although not important, it may be worth avoiding the first person "I" in documentation.

Perhaps. "There is a variant of the (Rare) `A.a B A2.so` case that looks like a library sandwich.

[MaskRay]

Incorporate feedback

[psmith]

Thanks for the update I'm happy with the edits.

[MaskRay]

In D86762#2264210, @psmith wrote:

Thanks for the update I'm happy with the edits.

Thanks for your thorough review and rewrite. I will push this documentation change next week.

lld/docs/ELF/warn_backrefs.rst

+--warn-backrefs
+===============
+
+``--warn-backrefs`` gives a warning when an undefined symbol reference is
+resolved by a definition in an archive to the left of it on the command line.
+
+A linker such as GNU ld makes a single pass over the input files from left to
+right maintaining the set of undefined symbol references from the files loaded
+so far. When encountering an archive or an object file surrounded by
+``--start-lib`` and ``--end-lib`` that archive will be searched for resolving
+symbol definitions; this may result in input files being loaded, updating the
+set of undefined symbol references. When all resolving definitions have been
+loaded from the archive, the linker moves on the next file and will not return
+to it.  This means that if an input file to the right of a archive cannot have
+an undefined symbol resolved by a archive to the left of it. For example:
+
+    ld def.a ref.o
+
+will result in an ``undefined reference`` error. If there are no cyclic
+references, the archives can be ordered in such a way that there are no
+backward references. If there are cyclic references then the ``--start-group``
+and ``--end-group`` options can be used, or the same archive can be placed on
+the command line twice.
+
+LLD remembers the symbol table of archives that it has previously seen, so if
+there is a reference from an input file to the right of an archive, LLD will
+still search that archive for resolving any undefined references. This means
+that an archive only needs to be included once on the command line and the
+``--start-group`` and ``--end-group`` options are redundant.
+
+A consequence of the differing archive searching semantics is that the same
+linker command line can result in different outcomes. A link may succeed with
+LLD that will fail with GNU ld, or even worse both links succeed but they have
+selected different objects from different archives that both define the same
+symbols.
+
+The ``warn-backrefs`` option provides information that helps identify cases
+where LLD and GNU ld archive selection may differ.
+
+    % ld.lld --warn-backrefs ... -lB -lA
+    ld.lld: warning: backward reference detected: system in A.a(a.o) refers to B.a(b.o)
+
+    % ld.lld --warn-backrefs ... --start-lib B/b.o --end-lib --start-lib A/a.o --end-lib
+    ld.lld: warning: backward reference detected: system in A/a.o refers to B/b.o
+
+    # To suppress the warning, you can specify --warn-backrefs-exclude=<glob> to match B/b.o or B.a(b.o)
+
+The ``--warn-backrefs`` option can also provide a check to enforce a
+topological order of archives, which can be useful to detect layering
+violations (albeit unable to catch all cases). There are two cases where GNU ld
+will result in an ``undefined reference`` error:
+
+* If adding the dependency does not form a cycle: conceptually ``A`` is higher
+  level library while ``B`` is at a lower level. When you are developing an
+  application ``P`` which depends on ``A``, but does not directly depend on
+  ``B``, your link may fail surprisingly with ``undefined symbol:
+  symbol_defined_in_B`` if the used/linked part of ``A`` happens to need some
+  components of ``B``. It is inappropriate for ``P`` to add a dependency on
+  ``B`` since ``P`` does not use ``B`` directly.
+* If adding the dependency forms a cycle, e.g. ``B->C->A ~> B``. ``A``
+  is supposed to be at the lowest level while ``B`` is supposed to be at the
+  highest level. When you are developing ``C_test`` testing ``C``, your link may
+  fail surprisingly with ``undefined symbol`` if there is somehow a dependency on
+  some components of ``B``. You could fix the issue by adding the missing
+  dependency (``B``), however, then every test (``A_test``, ``B_test``,
+  ``C_test``) will link against every library. This breaks the motivation
+  of splitting ``B``, ``C`` and ``A`` into separate libraries and makes binaries
+  unnecessarily large. Moreover, the layering violation makes lower-level
+  libraries (e.g. ``A``) vulnerable to changes to higher-level libraries (e.g.
+  ``B``, ``C``).
+
+Resolution:
+
+* Add a dependency from ``A`` to ``B``.
+* The reference may be unintended and can be removed.
+* The dependency may be intentionally omitted because there are multiple
+  libraries like ``B``.  Consider linking ``B`` with object semantics by
+  surrounding it with ``--whole-archive`` and ``--no-whole-archive``.
+* In the case of circular dependency, sometimes merging the libraries are the best.
+
+There are two cases like a library sandwich where GNU ld will select a
+different object.
+
+* ``A.a B A2.so``: ``A.a`` may be used as an interceptor (e.g. it provides some
+  optimized libc functions and ``A2`` is libc).  ``B`` does not need to know
+  about ``A.a``, and ``A.a`` may be pulled into the link by other part of the
+  program. For linker portability, consider ``--whole-archive`` and
+  ``--no-whole-archive``.
+
+* ``A.a B A2.a``: similar to the above case but ``--warn-backrefs`` does not
+  flag the problem, because ``A2.a`` may be a replicate of ``A.a``, which is
+  redundant but benign. In some cases ``A.a`` and ``B`` should be surrounded by
+  a pair of ``--start-group`` and ``--end-group``. This is especially common
+  among system libraries (e.g.  ``-lc __isnanl references -lm``, ``-lc
+  _IO_funlockfile references -lpthread``, ``-lc __gcc_personality_v0 references
+  -lgcc_eh``, and ``-lpthread _Unwind_GetCFA references -lunwind``).
+
+  In C++, this is likely an ODR violation. We probably need a dedicated option
+  for ODR detection.

lld/docs/index.rst

.. toctree::
    NewLLD
    AtomLLD
    WebAssembly
    windows_support
    missingkeyfunction
    Partitions
    ReleaseNotes
    ELF/linker_script
+   ELF/warn_backrefs