Repository: davidlattimore/wild (rust)

Issue:
Undefined reference error when linking executable depending on shared object with an undefined symbol
Right now, Wild reports any undefined symbol in shared objects when linking an executable. I have found this issue by building LLVM with `-DLLVM_BUILD_LLVM_DYLIB=ON -DLLVM_LINK_LLVM_DYLIB=ON` CMake options:
```
❯ ninja bugpoint
[1/1] Linking CXX executable bin/bugpoint
FAILED: bin/bugpoint
: && /home/mateusz/Projects/wild-proxy/wild-g++ -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wno-missing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wno-maybe-uninitialized -Wno-nonnull -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wno-misleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG -Wl,--color-diagnostics -Wl,--export-dynamic tools/bugpoint/CMakeFiles/bugpoint.dir/BugDriver.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/CrashDebugger.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/ExecutionDriver.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/ExtractFunction.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/FindBugs.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/Miscompilation.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/OptimizerDriver.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/ToolRunner.cpp.o tools/bugpoint/CMakeFiles/bugpoint.dir/bugpoint.cpp.o -o bin/bugpoint  -Wl,-rpath,"\$ORIGIN/../lib:/home/mateusz/Projects/llvm-project/build/lib:"  lib/libLLVM.so.21.0git && :
WARNING: wild: --plugin /usr/lib/gcc/x86_64-pc-linux-gnu/15.1.1/liblto_plugin.so is not yet supported
Error: Failed to activate lib/libLLVM.so.21.0git (2816 (11/0))
  Caused by:
    undefined reference to `history` from lib/libLLVM.so.21.0git (2816 (11/0))

ninja: build stopped: subcommand failed.
```

Some more info about this symbol:
```
❯ ./run-with ~/Projects/wild/target/debug/wild --sym-info history
WARNING: wild: --plugin /usr/lib/gcc/x86_64-pc-linux-gnu/15.1.1/liblto_plugin.so is not yet supported
Global name `history` refers to: None
Definitions / references with name `history`:
  Global Undefined: symbol_id=2945 -> 2945 ABSOLUTE | DYNAMIC | FUNCTION res=[]
    #6 in File #2816 (11/0) ./home/mateusz/Projects/llvm-project/build/lib/libLLVM.so.21.0git (LOADED)
wild: error: Failed to activate ./home/mateusz/Projects/llvm-project/build/lib/libLLVM.so.21.0git (2816 (11/0))
  Caused by:
    undefined reference to `history` from ./home/mateusz/Projects/llvm-project/build/lib/libLLVM.so.21.0git (2816 (11/0))


~/tmp/llvm
❯ readelf -Ws ./home/mateusz/Projects/llvm-project/build/lib/libLLVM.so.21.0git | rg 'history$|Symbol table'
Symbol table '.dynsym' contains 38280 entries:
     6: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND history
Symbol table '.symtab' contains 163860 entries:
```

LD's description of this flag is not very obvious:
> Allows or disallows undefined symbols in shared libraries.

Indeed, sounds like it should prevent any undefined symbols, but digging deeper into `man` there is:
> The default behaviour is to report errors for any undefined symbols referenced in shared libraries if the linker is being used to create an executable

To me, it should not report any undefined symbol, just those the executable would use.

---

Additionally, this flag is completely ignored when creating shared objects, instead it should be disabled for them by default.

Pull request description:
Change behaviour of --no-allow-shlib-undefined to match lld
It turns out that LLD is more relaxed about undefined symbols in shared objects compared to GNU ld. We now hopefully do the same relaxed behaviour as LLD. That is, we only report an error if the shared object has all of its direct dependencies in the link.

Also, change the default back to --no-allow-shlib-undefined.

Fixes #897

Patch:
diff --git a/libwild/src/args.rs b/libwild/src/args.rs
index 4b33731..b88a71f 100644
--- a/libwild/src/args.rs
+++ b/libwild/src/args.rs
@@ -288,8 +288,7 @@ impl Default for Args {
             files_per_group: None,
             exclude_libs: false,
             no_undefined: false,
-            // TODO: Change default to false once #897 is fixed.
-            allow_shlib_undefined: true,
+            allow_shlib_undefined: false,
             should_print_version: false,
             sysroot: None,
             save_dir: Default::default(),
diff --git a/libwild/src/input_data.rs b/libwild/src/input_data.rs
index e1600c2..97ca87e 100644
--- a/libwild/src/input_data.rs
+++ b/libwild/src/input_data.rs
@@ -22,8 +22,10 @@ use foldhash::fast::RandomState;
 use memmap2::Mmap;
 use rayon::iter::IntoParallelRefIterator;
 use rayon::iter::ParallelIterator;
+use std::ffi::OsStr;
 use std::fmt::Display;
 use std::ops::Deref;
+use std::os::unix::ffi::OsStrExt;
 use std::path::Path;
 use std::path::PathBuf;
 use std::time::Duration;
@@ -38,6 +40,10 @@ pub(crate) struct InputData<'data> {
 
     pub(crate) version_script_data: Option<VersionScriptData<'data>>,
     pub(crate) linker_scripts: Vec<InputLinkerScript<'data>>,
+
+    /// Which files we loaded. The keys aren't relevant anymore, but we keep them to avoid
+    /// regenerating the map.
+    path_to_load_index: HashMap<PathBuf, FileLoadIndex>,
 }
 
 pub(crate) struct InputBytes<'data> {
@@ -232,12 +238,12 @@ impl<'data> InputData<'data> {
             inputs: Vec::new(),
             linker_scripts: Vec::new(),
             version_script_data,
+            path_to_load_index: temporary_state.path_to_load_index,
         };
 
         inputs.extract_all(&mut temporary_state.files)?;
 
-        args.save_dir
-            .finish(temporary_state.path_to_load_index.keys())?;
+        args.save_dir.finish(inputs.path_to_load_index.keys())?;
 
         Ok(inputs)
     }
@@ -324,6 +330,11 @@ impl<'data> InputData<'data> {
 
         Ok(())
     }
+
+    pub(crate) fn has_file(&self, name: &'data [u8]) -> bool {
+        self.path_to_load_index
+            .contains_key(Path::new(OsStr::from_bytes(name)))
+    }
 }
 
 fn process_linker_script<'data>(
diff --git a/libwild/src/layout.rs b/libwild/src/layout.rs
index b470dd3..7673001 100644
--- a/libwild/src/layout.rs
+++ b/libwild/src/layout.rs
@@ -30,6 +30,7 @@ use crate::error::Error;
 use crate::error::Result;
 use crate::file_writer;
 use crate::input_data::FileId;
+use crate::input_data::InputData;
 use crate::input_data::InputRef;
 use crate::input_data::PRELUDE_FILE_ID;
 use crate::layout_rules::SectionKind;
@@ -128,6 +129,7 @@ pub fn compute<'data, A: Arch>(
     resolved: ResolutionOutputs<'data>,
     mut output_sections: OutputSections<'data>,
     output: &mut file_writer::Output,
+    input_data: &InputData<'data>,
 ) -> Result<Layout<'data>> {
     let ResolutionOutputs {
         groups,
@@ -146,6 +148,7 @@ pub fn compute<'data, A: Arch>(
         &output_sections,
         &symbol_resolution_flags,
         &merged_strings,
+        input_data,
     )?;
 
     let mut group_states = gc_outputs.group_states;
@@ -1631,6 +1634,8 @@ struct GraphResources<'data, 'scope> {
     /// section gets referenced. The sections here will only be those that are eligible for having
     /// __start_ / __stop_ symbols. i.e. sections that don't start their names with a ".".
     start_stop_sections: OutputSectionMap<SegQueue<SectionLoadRequest>>,
+
+    input_data: &'scope InputData<'data>,
 }
 
 struct FinaliseLayoutResources<'scope, 'data> {
@@ -2250,6 +2255,7 @@ fn find_required_sections<'data, A: Arch>(
     output_sections: &OutputSections<'data>,
     symbol_resolution_flags: &[AtomicResolutionFlags],
     merged_strings: &OutputSectionMap<MergedStringsSection<'data>>,
+    input_data: &InputData<'data>,
 ) -> Result<GcOutputs<'data>> {
     let num_workers = groups_in.len();
     let (worker_slots, groups) = create_worker_slots(groups_in, output_sections, symbol_db);
@@ -2272,6 +2278,7 @@ fn find_required_sections<'data, A: Arch>(
         has_static_tls: AtomicBool::new(false),
         uses_tlsld: AtomicBool::new(false),
         start_stop_sections: output_sections.new_section_map(),
+        input_data,
     };
     let resources_ref = &resources;
 
@@ -5254,6 +5261,8 @@ impl<'data> DynamicLayoutState<'data> {
         resources: &GraphResources<'data, '_>,
         queue: &mut LocalWorkQueue,
     ) -> Result {
+        let mut check_undefined_cache = None;
+
         for symbol_id in self.symbol_id_range() {
             let definition_symbol_id = resources.symbol_db.definition(symbol_id);
 
@@ -5263,9 +5272,22 @@ impl<'data> DynamicLayoutState<'data> {
 
             if value_flags.is_dynamic() && value_flags.is_absolute() {
                 // Our shared object references an undefined symbol. Whether that is an error or
-                // not, depends on flags and whether the symbol is weak.
-                let args = resources.symbol_db.args;
-                if !args.allow_shlib_undefined && args.output_kind().is_executable() {
+                // not, depends on flags, whether the symbol is weak and whether all of the shared
+                // object's dependencies are loaded.
+
+                let check_undefined = *check_undefined_cache.get_or_insert_with(|| {
+                    let args = resources.symbol_db.args;
+                    !args.allow_shlib_undefined
+                        && args.output_kind().is_executable()
+                        // Like lld, our behaviour for --no-allow-shlib-undefined is to only report
+                        // errors for shared objects that have all their dependencies in the link.
+                        // This is in contrast to GNU ld which recursively loads all transitive
+                        // dependencies of shared objects and checks our shared object against
+                        // those.
+                        && self.has_complete_deps(resources)
+                });
+
+                if check_undefined {
                     let symbol = self
                         .object
                         .symbol(self.symbol_id_range.id_to_input(symbol_id))?;
@@ -5611,6 +5633,32 @@ impl<'data> DynamicLayoutState<'data> {
             })
             .try_collect()
     }
+
+    /// Return whether all DT_NEEDED entries for this shared object correspond to input files that
+    /// we have loaded.
+    fn has_complete_deps(&self, resources: &GraphResources) -> bool {
+        let Ok(dynamic_tags) = self.object.dynamic_tags() else {
+            return true;
+        };
+
+        let e = LittleEndian;
+        for entry in dynamic_tags {
+            let value = entry.d_val(e);
+            match entry.d_tag(e) as u32 {
+                object::elf::DT_NEEDED => {
+                    let Ok(name) = self.object.symbols.strings().get(value as u32) else {
+                        return false;
+                    };
+                    if !resources.input_data.has_file(name) {
+                        return false;
+                    }
+                }
+                _ => {}
+            }
+        }
+
+        true
+    }
 }
 
 impl<'data> LinkerScriptLayoutState<'data> {
diff --git a/libwild/src/lib.rs b/libwild/src/lib.rs
index d54039d..b8f6e8d 100644
--- a/libwild/src/lib.rs
+++ b/libwild/src/lib.rs
@@ -211,7 +211,13 @@ impl Linker {
             &layout_rules,
         )?;
 
-        let layout = layout::compute::<A>(symbol_db, resolved, output_sections, &mut output)?;
+        let layout = layout::compute::<A>(
+            symbol_db,
+            resolved,
+            output_sections,
+            &mut output,
+            input_data,
+        )?;
 
         output.write(&layout, elf_writer::write::<A>)?;
         diff::maybe_diff()?;


Test patch:
diff --git a/wild/tests/sources/shlib-undefined-2.c b/wild/tests/sources/shlib-undefined-2.c
index 1fdfa43..9dea79c 100644
--- a/wild/tests/sources/shlib-undefined-2.c
+++ b/wild/tests/sources/shlib-undefined-2.c
@@ -1,3 +1,5 @@
+//#Shared:shlib-undefined-3.c
+
 int def1(void);
 int def2(void);
 
diff --git a/wild/tests/sources/shlib-undefined-3.c b/wild/tests/sources/shlib-undefined-3.c
new file mode 100644
index 0000000..b3cde21
--- /dev/null
+++ b/wild/tests/sources/shlib-undefined-3.c
@@ -0,0 +1,3 @@
+int def3(void) {
+    return 0;
+}
diff --git a/wild/tests/sources/shlib-undefined.c b/wild/tests/sources/shlib-undefined.c
index 4b05ac5..7ecc221 100644
--- a/wild/tests/sources/shlib-undefined.c
+++ b/wild/tests/sources/shlib-undefined.c
@@ -1,20 +1,43 @@
 //#AbstractConfig:default
+// We match lld's behaviour, not GNU ld's for --allow-shlib-undefined. That is, we only validate
+// shared object undefined symbols when all of the shared object's direct dependencies are loaded.
+//#EnableLinker:lld
+//#SkipLinker:ld
 //#Object:runtime.c
 //#Mode:dynamic
-//#Shared:shlib-undefined-2.c
 //#DiffIgnore:.dynamic.DT_RELA
 //#DiffIgnore:.dynamic.DT_RELAENT
 //#DiffIgnore:.dynamic.DT_NEEDED
+// Ignore a few things that lld does differently.
+//#DiffIgnore:section.relro_padding
+//#DiffIgnore:section.got.plt.entsize
+//#DiffIgnore:.dynamic.DT_FLAGS_1.NOW
+//#RunEnabled:false
+// Cross doesn't currently support lld and this test doesn't use GNU ld.
+//#Cross:false
 
+// Allow linking against shared object with undefined symbols. We don't run this because the runtime
+// linker would error due to the undefined symbol.
 //#Config:allow:default
+//#Shared:shlib-undefined-2.c
 //#LinkArgs:--allow-shlib-undefined -z now
-//#RunEnabled:false
 
-//#Config:disallow:default
+// This should also succeed to link because our shared object depends on another shared object that
+// we don't have loaded.
+//#Config:disallow-incomplete:default
+//#Shared:shlib-undefined-2.c
+//#LinkArgs:--no-allow-shlib-undefined
+
+// Disallow linking against shared object with undefined symbols. In this variant, the shared object
+// (2) that we depend on has all of its dependencies (3) also loaded.
+//#Config:disallow-complete:default
+//#Shared:shlib-undefined-2.c
+//#Shared:shlib-undefined-3.c
 //#LinkArgs:--no-allow-shlib-undefined
 //#ExpectError:def2
 
 //#Config:shared:default
+//#Shared:shlib-undefined-2.c
 //#LinkArgs:-z now -shared
 //#RunEnabled:false
 // TODO: GNU ld sets the entry to _start even though we're writing a shared object. We probably