[ELF] Allow non-bitcode archive with an empty index

[MaskRay]

Summary

When an archive with an empty index contains only bitcode files, it is
handled as a group of lazy (--start-lib) object files. If there is a
non-bitcode file, there will be a diagnostic a la GNU ld.

For some programs, the archive member extraction ratio is high (e.g. for chrome,
79% archive members are extracted according to --print-archive-stats=). Because
symbol interning is cached for ObjFile::parseLazy but not for ArchiveFile,
parsing an archive as a group of --start-lib object files may be faster.

If the linker speculatively creates section representations for archive members,
the archive index will not be used.

If we take the above view, the archive index is essentially useless. If a user
wants a fast build without using --start-lib, they may just build thin archives
without index (ar rcS --thin).

Therefore, I suggest that we no longer treat the code as a hack, instead as a
supported feature. I believe we will do this anyway if we add parallel symbol
interning (parallel symbol interning for lazy object files is simpler than that
for archives).

Ecosystem issues:

• parseLazy actually has nearly the same behavior as ArchiveFile::parse, but the symbol order may be different.
• users may get addicted to the behavior and build archives not working with GNU ld and gold. I think it is easy to rebuild archives to be compatible.

[peter.smith]

I can see that something like this could be valuable for a program using archives for major subsystems, although less well for a set of loosely connected utility routines (C-library). Doing this transparently makes me a little bit nervous for the reasons you suggest in the description.

A couple of alternative suggestions:

Could introduce something like --start-lib --end-lib to treat archives in this way (regardless of whether they have an index or not. Something like --start-as-lazy archive1.a archive2.a --end-as-lazy. That would permit people to get the potential speed boost while being under control, their archives (with indexes) will still work on linkers that don't support the option.

Another option would be to enable the behaviour change via the command-line. At least people would then know that they would be doing something speciall
--archive-no-index-as-lazy=<archive type> where <archive type> is one of:

• none. All archives without an index get an error message.
• bitcode. All bitcode archives without an index are treated as a lazy archive. This is the default.
• all. All archives without an index are treated as a lazy archive.

[bd1976llvm]

Another advantage is that this behaviour allows users to "repair" archives with incomplete symbol tables by stripping the symbol table (maybe someone has added both ET_RELs and bitcode objects to the same archive with an ar which ignored the bitcocde symbols).

We have had a similar behaviour on PlayStation in our proprietary linker for many years without any reported problems. Given that, I think that we could enable this behaviour by default and add a command line option to revert to the current behaviour (--emulate-gnu-ld) to handle corner cases.

[sbc100]

In D117284#3243218, @bd1976llvm wrote:

Another advantage is that this behaviour allows users to "repair" archives with incomplete symbol tables by stripping the symbol table (maybe someone has added both ET_RELs and bitcode objects to the same archive with an ar which ignored the bitcocde symbols).

Isn't it already trivial to "repair" such libraries by running ranlib on them?

[bd1976llvm]

In D117284#3243370, @sbc100 wrote:

In D117284#3243218, @bd1976llvm wrote:

Another advantage is that this behaviour allows users to "repair" archives with incomplete symbol tables by stripping the symbol table (maybe someone has added both ET_RELs and bitcode objects to the same archive with an ar which ignored the bitcocde symbols).

Isn't it already trivial to "repair" such libraries by running ranlib on them?

True. This has proved useful in the past in my world of proprietary toolchains - but in opensource if you have access to LLD then you also also have access to a ranlib that is aware of all the same file formats that LLD supports.

[MaskRay]

add a diagnostic for non-ET_REL-non-bitcode

[MaskRay]

In D117284#3243073, @peter.smith wrote:

I can see that something like this could be valuable for a program using archives for major subsystems, although less well for a set of loosely connected utility routines (C-library). Doing this transparently makes me a little bit nervous for the reasons you suggest in the description.

Thanks for the comments. For the less well part, if the user cares about GNU ld compatibility, I think it's pretty straightforward to detect the problem (GNU ld does not link) and fix it by running ranlib.

A couple of alternative suggestions:

Could introduce something like --start-lib --end-lib to treat archives in this way (regardless of whether they have an index or not. Something like --start-as-lazy archive1.a archive2.a --end-as-lazy. That would permit people to get the potential speed boost while being under control, their archives (with indexes) will still work on linkers that don't support the option.

Another option would be to enable the behaviour change via the command-line. At least people would then know that they would be doing something speciall
--archive-no-index-as-lazy=<archive type> where <archive type> is one of:

• none. All archives without an index get an error message.
• bitcode. All bitcode archives without an index are treated as a lazy archive. This is the default.
• all. All archives without an index are treated as a lazy archive.

I imagine that we will introduce an option to treat all archives as a group of lazy files, maybe --archive-handling=<type> where <type> is one of:

• default: with index: traditional behavior, without index: a group of lazy object files
• lazy: a group of lazy object files ignoring the index

An option specifically for archives without an index seems to do too much.

I think it is good for ld.lld to influence the ecosystem in good directions. Normally we tend to be strict. For this archive case, if the traditional index constraint may not be useful and isn't difficult to repair (ranlib), I think losing some strictness is fine.
The patch also improves consistency. ET_REL files should not be handled differently than LLVM bitcode files.

[ikudrin]

LGTM.

The change looks safe. If it eventually helps us to move towards a parallel reading of input files, I am in favor of it.

lld/test/ELF/lto/archive-no-index.ll

27

31–32

There is only one error message in the test now, so the prefix can be just ERR.

[MaskRay]

update test

[MaskRay]

@peter.smith What's your opinion?

I have a longer write-up on https://maskray.me/blog/2022-01-16-archives-and-start-lib

[peter.smith]

No objections. Reading your blog post and my copy of Linkers and Loaders it does seem that early linkers would handle archives with indexes, it just seems like indexes were ubiquitous when GNU ld were written. So it does seem like rejecting archives without an index is a property of the implentation of GNU ld rather than something that should be relied upon.

[bd1976llvm]

In D117284#3254734, @peter.smith wrote:

No objections. Reading your blog post and my copy of Linkers and Loaders it does seem that early linkers would handle archives with indexes, it just seems like indexes were ubiquitous when GNU ld were written. So it does seem like rejecting archives without an index is a property of the implentation of GNU ld rather than something that should be relied upon.

I'm in favour of this change but I think it is quite easy to make the argument both ways. Links which rely on complex GNU archive symbol resolution behaviour could be easily be broken - so insisting that archives have symbol tables makes sense for GNU linkers.

Rant: Archives are now terrible!

• The format is very old and as pointed out in the description here the index is not efficient.
• Low utilisation archives + complex GNU archive symbol resolution rules make implementing any sort of parallel scanning difficult.
• It's also not true to say that thin archives can always be a replacement as thin archives are not suitable for distribution.

LLD's simplified archive semantics are a good improvement though :)

lld/ELF/Driver.cpp

if (inWholeArchive) {
       for (const auto &p : getArchiveMembers(mbref))
         files.push_back(createObjectFile(p.first, path, p.second));
       return;
     }
 
     std::unique_ptr<Archive> file =
         CHECK(Archive::create(mbref), path + ": failed to parse archive");
 
-    // If an archive file has no symbol table, it is likely that a user
-    // is attempting LTO and using a default ar command that doesn't
-    // understand the LLVM bitcode file. It is a pretty common error, so
-    // we'll handle it as if it had a symbol table.
+    // If an archive file has no symbol table, it may be intentional (used as a
+    // group of lazy object files where the symbol table is not useful), or the
+    // user is attempting LTO and using a default ar command that doesn't
+    // understand the LLVM bitcode file. Treat the archive as a group of lazy
+    // object files.
     if (!file->isEmpty() && !file->hasSymbolTable()) {
-      // Check if all members are bitcode files. If not, ignore, which is the
-      // default action without the LTO hack described above.
       for (const std::pair<MemoryBufferRef, uint64_t> &p :
-           getArchiveMembers(mbref))
-        if (identify_magic(p.first.getBuffer()) != file_magic::bitcode) {
-          error(path + ": archive has no index; run ranlib to add one");
-          return;
-        }
-
-      for (const std::pair<MemoryBufferRef, uint64_t> &p :
-           getArchiveMembers(mbref))
+           getArchiveMembers(mbref)) {
+        auto magic = identify_magic(p.first.getBuffer());
+        if (magic == file_magic::bitcode ||
+            magic == file_magic::elf_relocatable)
           files.push_back(createLazyFile(p.first, path, p.second));
+        else
+          error(path + ": archive member '" + p.first.getBufferIdentifier() +
+                "' is neither ET_REL nor LLVM bitcode");
+      }
       return;
     }
 
     // Handle the regular case.
     files.push_back(make<ArchiveFile>(std::move(file)));
     return;
   }
   case file_magic::elf_shared_object:

lld/test/ELF/archive-no-index.s

 # REQUIRES: x86
 # Tests error on archive file without a symbol table
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux -o %t.o %s
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux -o %t.archive.o %S/Inputs/archive.s
 # RUN: rm -f %t.a
 # RUN: llvm-ar crS %t.a %t.archive.o
 
-# RUN: not ld.lld -o /dev/null %t.o %t.a 2>&1 | FileCheck %s
+# RUN: ld.lld %t.o %t.a -o /dev/null 2>&1 | count 0
+
+# RUN: ld.lld -shared %t.archive.o -o %t.so
+# RUN: llvm-ar crS %t.a %t.so
+# RUN: not ld.lld %t.o %t.a --noinhibit-exec -o /dev/null 2>&1 | FileCheck %s --check-prefix=ERR
+
+# ERR: error: {{.*}}.a: archive member '{{.*}}.so' is neither ET_REL nor LLVM bitcode
 
 .globl _start
 _start:
-
-# CHECK: error: {{.*}}.a: archive has no index; run ranlib to add one

lld/test/ELF/lto/archive-no-index.ll

 ; REQUIRES: x86
-; Tests that we accept an archive file without symbol table
-; if all the member files are bitcode files.
+; Tests that we accept an archive file without symbol table.
 
 ; RUN: llvm-as -o %t1.o %s
 ; RUN: llvm-as -o %t2.o %S/Inputs/archive.ll
 
 ; RUN: rm -f %t1.a %t2.a
 ; RUN: llvm-ar crS %t1.a %t2.o
 ; RUN: llvm-ar crs %t2.a %t2.o
 
 ; RUN: ld.lld -o %t -emain %t1.o %t1.a
 ; RUN: ld.lld -o %t -emain %t1.o %t2.a
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @f()
 
 define i32 @main() {
   call void @f()
   ret i32 0
 }
 
 ; RUN: echo 'f:' | llvm-mc -triple=x86_64-pc-linux -filetype=obj - -o %t3.o
 ; RUN: rm -f %t3.a
 ; RUN: llvm-ar crS %t3.a %t3.o
-; RUN: not ld.lld -o /dev/null -emain %t1.o %t3.a 2>&1 | FileCheck -check-prefix=ERR1 %s
-; ERR1: error: {{.*}}.a: archive has no index; run ranlib to add one
+; RUN: not ld.lld -o %t -emain %t1.o %t3.a 2>&1 | FileCheck --check-prefix=ERR2 %s
 
 ; RUN: rm -f %t4.a
 ; RUN: llvm-ar cr %t4.a
 ; RUN: not ld.lld -o /dev/null -emain %t1.o %t4.a 2>&1 | FileCheck -check-prefix=ERR2 %s
 ; ERR2: error: undefined symbol: f