[lld][coff] undefined symbols from lazy-loaded archives

[glandium]

STR:

• Download https://drive.google.com/file/d/1HhG-LO4MU1GGOLstHlFBi7rOrwKfNDbZ/view?usp=sharing
• Unpack the archive and enter the repro directory.
• Run lld-link @response.txt

Expected result:

• Linkage fails because of a missing file (-reproduce didn't store the manifest file, you may want to edit the response file to remove the manifest-related flags, in which case the expected result is a successful link)

Actual result:

lld-link: error: undefined symbol: __declspec(dllimport) _wassert
>>> referenced by /tmp/g/third_party/rust/whatsys/c/windows.c:38
>>>               libwhatsys-f4cc7b72e53ee839.rlib(db3b6bfb95261072-windows.o):(get_os_release)

lld-link: error: undefined symbol: __declspec(dllimport) wcscpy
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:4238
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_fopen)

lld-link: error: undefined symbol: __declspec(dllimport) _aligned_malloc
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:9324
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_env_copyfd1)

lld-link: error: undefined symbol: __declspec(dllimport) _aligned_free
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:9425
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_env_copyfd1)

What happens is that the symbols, by the time resolveRemainingUndefines is called, are still undefined, but isLazy() is true for them, and resolveRemainingUndefines doesn't handle that case.

A crude retry, like the following, works around the issue:

diff --git a/lld/COFF/Driver.cpp b/lld/COFF/Driver.cpp
index 3ef9fa3f65c6..46307a386328 100644
--- a/lld/COFF/Driver.cpp
+++ b/lld/COFF/Driver.cpp
@@ -2595,6 +2595,8 @@ void LinkerDriver::linkerMain(ArrayRef<const char *> argsArr) {
 
   // Resolve remaining undefined symbols and warn about imported locals.
   ctx.symtab.resolveRemainingUndefines();
+  run();
+  ctx.symtab.resolveRemainingUndefines();
   if (errorCount())
     return;
 
diff --git a/lld/COFF/SymbolTable.cpp b/lld/COFF/SymbolTable.cpp
index bb7583bb9a7d..5301a7af9c92 100644
--- a/lld/COFF/SymbolTable.cpp
+++ b/lld/COFF/SymbolTable.cpp
@@ -501,6 +501,10 @@ void SymbolTable::resolveRemainingUndefines() {
     // This odd rule is for compatibility with MSVC linker.
     if (name.starts_with("__imp_")) {
       Symbol *imp = find(name.substr(strlen("__imp_")));
+      if (imp && imp->isLazy()) {
+        forceLazy(imp);
+        continue;
+      }
       if (imp && isa<Defined>(imp)) {
         auto *d = cast<Defined>(imp);
         replaceSymbol<DefinedLocalImport>(sym, ctx, name, d);

But somehow, there is some non-determinism, as when running the command repeatedly, sometimes, it fails with strdup marked as undefined symbol.

Cc: @mstorsjo

[llvmbot]

@llvm/issue-subscribers-lld-coff

Author: Mike Hommey (glandium)

STR: - Download https://drive.google.com/file/d/1HhG-LO4MU1GGOLstHlFBi7rOrwKfNDbZ/view?usp=sharing - Unpack the archive and enter the `repro` directory. - Run `lld-link @response.txt`

Expected result:

• Linkage fails because of a missing file (-reproduce didn't store the manifest file, you may want to edit the response file to remove the manifest-related flags, in which case the expected result is a successful link)

Actual result:

lld-link: error: undefined symbol: __declspec(dllimport) _wassert
>>> referenced by /tmp/g/third_party/rust/whatsys/c/windows.c:38
>>>               libwhatsys-f4cc7b72e53ee839.rlib(db3b6bfb95261072-windows.o):(get_os_release)

lld-link: error: undefined symbol: __declspec(dllimport) wcscpy
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:4238
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_fopen)

lld-link: error: undefined symbol: __declspec(dllimport) _aligned_malloc
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:9324
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_env_copyfd1)

lld-link: error: undefined symbol: __declspec(dllimport) _aligned_free
>>> referenced by /tmp/g/third_party/rust/lmdb-rkv-sys/lmdb/libraries/liblmdb/mdb.c:9425
>>>               liblmdb_sys-564cd906496499b4.rlib(7b4e66c3aa61e8a8-mdb.o):(mdb_env_copyfd1)

What happens is that the symbols, by the time resolveRemainingUndefines is called, are still undefined, but isLazy() is true for them, and resolveRemainingUndefines doesn't handle that case.

A crude retry, like the following, works around the issue:

diff --git a/lld/COFF/Driver.cpp b/lld/COFF/Driver.cpp
index 3ef9fa3f65c6..46307a386328 100644
--- a/lld/COFF/Driver.cpp
+++ b/lld/COFF/Driver.cpp
@@ -2595,6 +2595,8 @@ void LinkerDriver::linkerMain(ArrayRef<const char *> argsArr) {
 
   // Resolve remaining undefined symbols and warn about imported locals.
   ctx.symtab.resolveRemainingUndefines();
+  run();
+  ctx.symtab.resolveRemainingUndefines();
   if (errorCount())
     return;
 
diff --git a/lld/COFF/SymbolTable.cpp b/lld/COFF/SymbolTable.cpp
index bb7583bb9a7d..5301a7af9c92 100644
--- a/lld/COFF/SymbolTable.cpp
+++ b/lld/COFF/SymbolTable.cpp
@@ -501,6 +501,10 @@ void SymbolTable::resolveRemainingUndefines() {
     // This odd rule is for compatibility with MSVC linker.
     if (name.starts_with("__imp_")) {
       Symbol *imp = find(name.substr(strlen("__imp_")));
+      if (imp && imp->isLazy()) {
+        forceLazy(imp);
+        continue;
+      }
       if (imp && isa<Defined>(imp)) {
         auto *d = cast<Defined>(imp);
         replaceSymbol<DefinedLocalImport>(sym, ctx, name, d);

But somehow, there is some non-determinism, as when running the command repeatedly, sometimes, it fails with strdup marked as undefined symbol.

Cc: @mstorsjo

[mstorsjo]

Thanks, I can reproduce this. As additional context - I can reproduce the nondeterminism on Linux. (Some underlying details about how files are loaded in LLD differ between Linux and Windows, where they are loaded asynchronously on Windows, but that doesn't seem to play any role here.)

I wonder if #85290 makes any difference here - although I doubt it.

[glandium]

I wonder if #85290 makes any difference here - although I doubt it.

It doesn't, but interestingly it makes strdup sometimes appear as undefined symbol, while it never happens with an unpatched tree.

[aganea]

I wonder if #85290 makes any difference here - although I doubt it.

It doesn't, but interestingly it makes strdup sometimes appear as undefined symbol, while it never happens with an unpatched tree.

Yeah I’ve noticed that with a recent Unreal Engine build. I’ll fix it.

[mstorsjo]

I wonder if #85290 makes any difference here - although I doubt it.

It doesn't, but interestingly it makes strdup sometimes appear as undefined symbol, while it never happens with an unpatched tree.

Wasn’t that part of the original behavior too? From your original issue description:

But somehow, there is some non-determinism, as when running the command repeatedly, sometimes, it fails with strdup marked as undefined symbol.

[glandium]

No, I never got strdup as undefined symbol before applying my patch.

[mstorsjo]

No, I never got strdup as undefined symbol before applying my patch.

Ah, I misunderstood - that was after applying your patch - I see. FWIW, I did see strdup as undefined symbol, occasionally, with an unpatched build.

[glandium]

Maybe I didn't try hard enough. Maybe the patch makes it more likely, too.

[glandium]

@mstorsjo Ignoring the strdup issue, do you think the crude retry patch from the report is good enough as a start?

[mstorsjo]

@mstorsjo Ignoring the strdup issue, do you think the crude retry patch from the report is good enough as a start?

Well it looks, as you say, a bit crude.

In one sense, this looks pretty much like what we do in loadMinGWSymbols() - where we scan for things that we may need to pull in, and do another run() before doing the final resolveRemainingUndefines().

So in one sense, it feels like a case where it's a tradeoff between always doing two passes through the symbols, or only doing it when we have a reason to believe we might need another round - and how costly is it to guess whether we need to make another round?

Or should we make resolveRemainingUndefines() return a value to indicate whether we need to pull in more object files and retry?

[glandium]

The indeterminism of the error for strdup is due to the differing order of iteration of the symMap between runs. Replacing the llvm::DenseMap with a llvm::MapVector makes the order deterministic and makes the error happen reliably every time on my machine.