coff: track globals in contiguous array to allow for tombstones

1 files changed, 76 insertions, 41 deletions

diff --git a/src/link/Coff.zig b/src/link/Coff.zig
index cd529ddab0..2abfc78d1e 100644
--- a/src/link/Coff.zig
+++ b/src/link/Coff.zig
@@ -53,10 +53,12 @@ reloc_section_index: ?u16 = null,
 idata_section_index: ?u16 = null,
 
 locals: std.ArrayListUnmanaged(coff.Symbol) = .{},
-globals: std.StringArrayHashMapUnmanaged(SymbolWithLoc) = .{},
+globals: std.ArrayListUnmanaged(SymbolWithLoc) = .{},
+resolver: std.StringHashMapUnmanaged(u32) = .{},
 unresolved: std.AutoArrayHashMapUnmanaged(u32, bool) = .{},
 
 locals_free_list: std.ArrayListUnmanaged(u32) = .{},
+globals_free_list: std.ArrayListUnmanaged(u32) = .{},
 
 strtab: StringTable(.strtab) = .{},
 strtab_offset: ?u32 = null,
@@ -292,11 +294,15 @@ pub fn deinit(self: *Coff) void {
     self.managed_atoms.deinit(gpa);
 
     self.locals.deinit(gpa);
+    self.globals.deinit(gpa);
 
-    for (self.globals.keys()) |key| {
-        gpa.free(key);
+    {
+        var it = self.resolver.keyIterator();
+        while (it.next()) |key_ptr| {
+            gpa.free(key_ptr.*);
+        }
+        self.resolver.deinit(gpa);
     }
-    self.globals.deinit(gpa);
 
     self.unresolved.deinit(gpa);
     self.locals_free_list.deinit(gpa);
@@ -651,6 +657,30 @@ fn allocateSymbol(self: *Coff) !u32 {
     return index;
 }
 
+fn allocateGlobal(self: *Coff) !u32 {
+    const gpa = self.base.allocator;
+    try self.globals.ensureUnusedCapacity(gpa, 1);
+
+    const index = blk: {
+        if (self.globals_free_list.popOrNull()) |index| {
+            log.debug("  (reusing global index {d})", .{index});
+            break :blk index;
+        } else {
+            log.debug("  (allocating global index {d})", .{self.globals.items.len});
+            const index = @intCast(u32, self.globals.items.len);
+            _ = self.globals.addOneAssumeCapacity();
+            break :blk index;
+        }
+    };
+
+    self.globals.items[index] = .{
+        .sym_index = 0,
+        .file = null,
+    };
+
+    return index;
+}
+
 pub fn allocateGotEntry(self: *Coff, target: SymbolWithLoc) !u32 {
     const gpa = self.base.allocator;
     try self.got_entries.ensureUnusedCapacity(gpa, 1);
@@ -1340,7 +1370,7 @@ pub fn deleteExport(self: *Coff, exp: Export) void {
     const sym = self.getSymbolPtr(sym_loc);
     const sym_name = self.getSymbolName(sym_loc);
     log.debug("deleting export '{s}'", .{sym_name});
-    assert(sym.storage_class == .EXTERNAL);
+    assert(sym.storage_class == .EXTERNAL and sym.section_number != .UNDEFINED);
     sym.* = .{
         .name = [_]u8{0} ** 8,
         .value = 0,
@@ -1351,33 +1381,38 @@ pub fn deleteExport(self: *Coff, exp: Export) void {
     };
     self.locals_free_list.append(gpa, sym_index) catch {};
 
-    if (self.globals.get(sym_name)) |global| blk: {
-        if (global.sym_index != sym_index) break :blk;
-        if (global.file != null) break :blk;
-        const kv = self.globals.fetchSwapRemove(sym_name);
-        gpa.free(kv.?.key);
+    if (self.resolver.fetchRemove(sym_name)) |entry| {
+        defer gpa.free(entry.key);
+        self.globals_free_list.append(gpa, entry.value) catch {};
+        self.globals.items[entry.value] = .{
+            .sym_index = 0,
+            .file = null,
+        };
     }
 }
 
 fn resolveGlobalSymbol(self: *Coff, current: SymbolWithLoc) !void {
     const gpa = self.base.allocator;
     const sym = self.getSymbol(current);
-    _ = sym;
     const sym_name = self.getSymbolName(current);
 
-    const name = try gpa.dupe(u8, sym_name);
-    const global_index = @intCast(u32, self.globals.values().len);
-    _ = global_index;
-    const gop = try self.globals.getOrPut(gpa, name);
-    defer if (gop.found_existing) gpa.free(name);
-
-    if (!gop.found_existing) {
-        gop.value_ptr.* = current;
-        // TODO undef + tentative
+    const global_index = self.resolver.get(sym_name) orelse {
+        const name = try gpa.dupe(u8, sym_name);
+        const global_index = try self.allocateGlobal();
+        self.globals.items[global_index] = current;
+        try self.resolver.putNoClobber(gpa, name, global_index);
+        if (sym.section_number == .UNDEFINED) {
+            try self.unresolved.putNoClobber(gpa, global_index, false);
+        }
         return;
-    }
+    };
 
     log.debug("TODO finish resolveGlobalSymbols implementation", .{});
+
+    if (sym.section_number == .UNDEFINED) return;
+
+    _ = self.unresolved.swapRemove(global_index);
+    self.globals.items[global_index] = current;
 }
 
 pub fn flush(self: *Coff, comp: *Compilation, prog_node: *std.Progress.Node) !void {
@@ -1415,7 +1450,7 @@ pub fn flushModule(self: *Coff, comp: *Compilation, prog_node: *std.Progress.Nod
 
     while (self.unresolved.popOrNull()) |entry| {
         assert(entry.value); // We only expect imports generated by the incremental linker for now.
-        const global = self.globals.values()[entry.key];
+        const global = self.globals.items[entry.key];
         if (self.imports_table.contains(global)) continue;
 
         _ = try self.allocateImportEntry(global);
@@ -1481,24 +1516,22 @@ pub fn getDeclVAddr(
 }
 
 pub fn getGlobalSymbol(self: *Coff, name: []const u8) !u32 {
-    const gpa = self.base.allocator;
-    const sym_name = try gpa.dupe(u8, name);
-    const global_index = @intCast(u32, self.globals.values().len);
-    const gop = try self.globals.getOrPut(gpa, sym_name);
-    defer if (gop.found_existing) gpa.free(sym_name);
-
-    if (gop.found_existing) {
-        // TODO audit this: can we ever reference anything from outside the Zig module?
-        assert(gop.value_ptr.file == null);
-        return gop.value_ptr.sym_index;
+    if (self.resolver.get(name)) |global_index| {
+        return self.globals.items[global_index].sym_index;
     }
 
+    const gpa = self.base.allocator;
     const sym_index = try self.allocateSymbol();
+    const global_index = try self.allocateGlobal();
     const sym_loc = SymbolWithLoc{ .sym_index = sym_index, .file = null };
+    self.globals.items[global_index] = sym_loc;
+
+    const sym_name = try gpa.dupe(u8, name);
     const sym = self.getSymbolPtr(sym_loc);
     try self.setSymbolName(sym, sym_name);
     sym.storage_class = .EXTERNAL;
-    gop.value_ptr.* = sym_loc;
+
+    try self.resolver.putNoClobber(gpa, sym_name, global_index);
     try self.unresolved.putNoClobber(gpa, global_index, true);
 
     return sym_index;
@@ -1607,14 +1640,15 @@ fn writeBaseRelocations(self: *Coff) !void {
 }
 
 fn writeImportTable(self: *Coff) !void {
+    if (self.idata_section_index == null) return;
+
     const gpa = self.base.allocator;
 
     const section = self.sections.get(self.idata_section_index.?);
+    const last_atom = section.last_atom orelse return;
+
     const iat_rva = section.header.virtual_address;
-    const iat_size = blk: {
-        const last_atom = section.last_atom.?;
-        break :blk last_atom.getSymbol(self).value + last_atom.size * 2 - iat_rva; // account for sentinel zero pointer
-    };
+    const iat_size = last_atom.getSymbol(self).value + last_atom.size * 2 - iat_rva; // account for sentinel zero pointer
 
     const dll_name = "KERNEL32.dll";
 
@@ -1975,7 +2009,8 @@ inline fn getSizeOfImage(self: Coff) u32 {
 /// Returns symbol location corresponding to the set entrypoint (if any).
 pub fn getEntryPoint(self: Coff) ?SymbolWithLoc {
     const entry_name = self.base.options.entry orelse "wWinMainCRTStartup"; // TODO this is incomplete
-    return self.globals.get(entry_name);
+    const global_index = self.resolver.get(entry_name) orelse return null;
+    return self.globals.items[global_index];
 }
 
 /// Returns pointer-to-symbol described by `sym_with_loc` descriptor.
@@ -2100,9 +2135,9 @@ fn logSymtab(self: *Coff) void {
     }
 
     log.debug("globals table:", .{});
-    for (self.globals.keys()) |name, id| {
-        const value = self.globals.values()[id];
-        log.debug("  {s} => %{d} in object({?d})", .{ name, value.sym_index, value.file });
+    for (self.globals.items) |sym_loc| {
+        const sym_name = self.getSymbolName(sym_loc);
+        log.debug("  {s} => %{d} in object({?d})", .{ sym_name, sym_loc.sym_index, sym_loc.file });
     }
 
     log.debug("GOT entries:", .{});