link.Elf: eliminate an O(N^2) algorithm in flush()

Make shared_objects a StringArrayHashMap so that deduping does not
need to happen in flush. That deduping code also was using an O(N^2)
algorithm, which is not allowed in this codebase. There is another
violation of this rule in resolveSymbols but this commit does not
address it.

This required reworking shared object parsing, breaking it into
independent components so that we could access soname earlier.

Shared object parsing had a few problems that I noticed and fixed in
this commit:
* Many instances of incorrect use of align(1).
* `shnum * @sizeOf(elf.Elf64_Shdr)` can overflow based on user data.
* `@divExact` can cause illegal behavior based on user data.
* Strange versyms logic that wasn't present in mold nor lld. The logic
  was not commented and there is no git blame information in ziglang/zig
  nor kubkon/zld. I changed it to match mold and lld instead.
* Use of ArrayList for slices of memory that are never resized.
* finding DT_VERDEFNUM in a different loop than finding DT_SONAME.
  Ultimately I think we should follow mold's lead and ignore this
  integer, relying on null termination instead.
* Doing logic based on VER_FLG_BASE rather than ignoring it like mold
  and LLD do. No comment explaining why the behavior is different.
* Mutating the original ELF symbols rather than only storing the mangled
  name on the new Symbol struct.

I noticed something that I didn't try to address in this commit: Symbol
stores a lot of redundant information that is already present in the ELF
symbols. I suspect that the codebase could benefit from reworking Symbol
to not store redundant information.

Additionally:
* Add some type safety to std.elf.
* Eliminate 1-3 file system reads for determining the kind of input
  files, by taking advantage of file name extension and handling error
  codes properly.
* Move more error handling methods to link.Diags and make them
  infallible and thread-safe
* Make the data dependencies obvious in the parameters of
  parseSharedObject. It's now clear that the first two steps (Header and
  Parsed) can be done during the main Compilation pipeline, rather than
  waiting for flush().

1 files changed, 83 insertions, 27 deletions

diff --git a/src/link.zig b/src/link.zig
index ebfee34c4b..7280ce3df7 100644
--- a/src/link.zig
+++ b/src/link.zig
@@ -207,23 +207,19 @@ pub const Diags = struct {
     pub fn addError(diags: *Diags, comptime format: []const u8, args: anytype) void {
         @branchHint(.cold);
         const gpa = diags.gpa;
+        const eu_main_msg = std.fmt.allocPrint(gpa, format, args);
         diags.mutex.lock();
         defer diags.mutex.unlock();
-        diags.msgs.ensureUnusedCapacity(gpa, 1) catch |err| switch (err) {
-            error.OutOfMemory => {
-                diags.flags.alloc_failure_occurred = true;
-                return;
-            },
-        };
-        const err_msg: Msg = .{
-            .msg = std.fmt.allocPrint(gpa, format, args) catch |err| switch (err) {
-                error.OutOfMemory => {
-                    diags.flags.alloc_failure_occurred = true;
-                    return;
-                },
-            },
+        addErrorLockedFallible(diags, eu_main_msg) catch |err| switch (err) {
+            error.OutOfMemory => diags.setAllocFailureLocked(),
         };
-        diags.msgs.appendAssumeCapacity(err_msg);
+    }
+
+    fn addErrorLockedFallible(diags: *Diags, eu_main_msg: Allocator.Error![]u8) Allocator.Error!void {
+        const gpa = diags.gpa;
+        const main_msg = try eu_main_msg;
+        errdefer gpa.free(main_msg);
+        try diags.msgs.append(gpa, .{ .msg = main_msg });
     }
 
     pub fn addErrorWithNotes(diags: *Diags, note_count: usize) error{OutOfMemory}!ErrorWithNotes {
@@ -242,7 +238,7 @@ pub const Diags = struct {
         const err = diags.msgs.addOneAssumeCapacity();
         err.* = .{
             .msg = undefined,
-            .notes = try gpa.alloc(Diags.Msg, note_count),
+            .notes = try gpa.alloc(Msg, note_count),
         };
         return .{
             .diags = diags,
@@ -250,34 +246,93 @@ pub const Diags = struct {
         };
     }
 
-    pub fn reportMissingLibraryError(
+    pub fn addMissingLibraryError(
         diags: *Diags,
         checked_paths: []const []const u8,
         comptime format: []const u8,
         args: anytype,
-    ) error{OutOfMemory}!void {
+    ) void {
         @branchHint(.cold);
-        var err = try diags.addErrorWithNotes(checked_paths.len);
-        try err.addMsg(format, args);
-        for (checked_paths) |path| {
-            try err.addNote("tried {s}", .{path});
+        const gpa = diags.gpa;
+        const eu_main_msg = std.fmt.allocPrint(gpa, format, args);
+        diags.mutex.lock();
+        defer diags.mutex.unlock();
+        addMissingLibraryErrorLockedFallible(diags, checked_paths, eu_main_msg) catch |err| switch (err) {
+            error.OutOfMemory => diags.setAllocFailureLocked(),
+        };
+    }
+
+    fn addMissingLibraryErrorLockedFallible(
+        diags: *Diags,
+        checked_paths: []const []const u8,
+        eu_main_msg: Allocator.Error![]u8,
+    ) Allocator.Error!void {
+        const gpa = diags.gpa;
+        const main_msg = try eu_main_msg;
+        errdefer gpa.free(main_msg);
+        try diags.msgs.ensureUnusedCapacity(gpa, 1);
+        const notes = try gpa.alloc(Msg, checked_paths.len);
+        errdefer gpa.free(notes);
+        for (checked_paths, notes) |path, *note| {
+            note.* = .{ .msg = try std.fmt.allocPrint(gpa, "tried {s}", .{path}) };
         }
+        diags.msgs.appendAssumeCapacity(.{
+            .msg = main_msg,
+            .notes = notes,
+        });
+    }
+
+    pub fn addParseError(
+        diags: *Diags,
+        path: Path,
+        comptime format: []const u8,
+        args: anytype,
+    ) void {
+        @branchHint(.cold);
+        const gpa = diags.gpa;
+        const eu_main_msg = std.fmt.allocPrint(gpa, format, args);
+        diags.mutex.lock();
+        defer diags.mutex.unlock();
+        addParseErrorLockedFallible(diags, path, eu_main_msg) catch |err| switch (err) {
+            error.OutOfMemory => diags.setAllocFailureLocked(),
+        };
     }
 
-    pub fn reportParseError(
+    fn addParseErrorLockedFallible(diags: *Diags, path: Path, m: Allocator.Error![]u8) Allocator.Error!void {
+        const gpa = diags.gpa;
+        const main_msg = try m;
+        errdefer gpa.free(main_msg);
+        try diags.msgs.ensureUnusedCapacity(gpa, 1);
+        const note = try std.fmt.allocPrint(gpa, "while parsing {}", .{path});
+        errdefer gpa.free(note);
+        const notes = try gpa.create([1]Msg);
+        errdefer gpa.destroy(notes);
+        notes.* = .{.{ .msg = note }};
+        diags.msgs.appendAssumeCapacity(.{
+            .msg = main_msg,
+            .notes = notes,
+        });
+    }
+
+    pub fn failParse(
         diags: *Diags,
         path: Path,
         comptime format: []const u8,
         args: anytype,
-    ) error{OutOfMemory}!void {
+    ) error{LinkFailure} {
         @branchHint(.cold);
-        var err = try diags.addErrorWithNotes(1);
-        try err.addMsg(format, args);
-        try err.addNote("while parsing {}", .{path});
+        addParseError(diags, path, format, args);
+        return error.LinkFailure;
     }
 
     pub fn setAllocFailure(diags: *Diags) void {
         @branchHint(.cold);
+        diags.mutex.lock();
+        defer diags.mutex.unlock();
+        setAllocFailureLocked(diags);
+    }
+
+    fn setAllocFailureLocked(diags: *Diags) void {
         log.debug("memory allocation failure", .{});
         diags.flags.alloc_failure_occurred = true;
     }
@@ -727,7 +782,8 @@ pub const File = struct {
         FailedToEmit,
         FileSystem,
         FilesOpenedWithWrongFlags,
-        /// Indicates an error will be present in `Compilation.link_errors`.
+        /// Deprecated. Use `LinkFailure` instead.
+        /// Formerly used to indicate an error will be present in `Compilation.link_errors`.
         FlushFailure,
         /// Indicates an error will be present in `Compilation.link_errors`.
         LinkFailure,