This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by MaskRay on Aug 27 2020, 9:57 PM.

Diff Detail

Event Timeline

MaskRay created this revision.Aug 27 2020, 9:57 PM
MaskRay requested review of this revision.Aug 27 2020, 9:57 PM
MaskRay added a comment.EditedAug 27 2020, 10:24 PM

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

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."

@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.

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!

@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).

--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 added a comment.EditedAug 28 2020, 11:30 AM

--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).

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 added a comment.Sep 1 2020, 1:01 AM

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 updated this revision to Diff 289198.Sep 1 2020, 9:32 AM

traditional linker -> single pass linker such as GNU ld

Add a note about intended omitted dependency

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

thakis added a comment.Sep 3 2020, 1:12 PM

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.

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 added a comment.Sep 4 2020, 3:14 AM

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 updated this revision to Diff 290548.Sep 8 2020, 11:39 AM
MaskRay marked 5 inline comments as done.

Incorporate feedback

MaskRay retitled this revision from [ELF] Add documentation for --warn-backrefs: a layering check tool to [ELF] Add documentation for --warn-backrefs: a GNU ld compatibility checking tool (and lesser of layering detection).Sep 8 2020, 11:40 AM

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

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.

This revision was not accepted when it landed; it landed in state Needs Review.Sep 14 2020, 12:31 PM
This revision was automatically updated to reflect the committed changes.