Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Разрешение имён и статические библиотеки

senior~180 мин

открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

Разрешение имён и статические библиотеки

В прошлом уроке мы открыли объектный файл и нашли в нём таблицу символов: список имён, которые модуль определяет, и имён, которые он хочет получить снаружи. Сегодня смотрим, что компоновщик с этими списками делает. Задача звучит просто: каждой ссылке найти ровно одно определение. Сложности начинаются, когда определений два, когда определение лежит в библиотеке и когда библиотек несколько и они зависят друг от друга. Мы воспроизведём три классических бага, которые из этого вырастают, в том числе тихую порчу соседней переменной, посмотрим, какие из них возможны в Zig, соберём статическую библиотеку руками и через build.zig, сломаем сборку неправильным порядком файлов. А потом напишем первую половину собственного компоновщика: zt ld научится читать архивы и разрешать имена.

Цели урока

Отличать сильное определение от слабого и от COMMON по выводу nm и readelf, и знать, откуда каждое берётся в C и в Zig.
Применять три правила выбора между одноимёнными определениями и воспроизвести баги, к которым ведут второе и третье.
Объяснить, что изменил ключ -fno-common, почему он стал умолчанием в GCC 10 и Clang 11 и почему на macOS старое поведение живо до сих пор.
Делать слабое определение в Zig через @export с .linkage = .weak и слабую ссылку через @extern, и знать ловушку с проверкой на null в Zig 0.16.
Понимать, что такое архив .a, собирать его через ar и через build.zig, и видеть, почему единица выбора из архива это объектник, а не функция.
Прогонять в голове алгоритм с множествами E, U и D, предсказывать по нему ошибку от неправильного порядка файлов и чинить циклические зависимости.
Знать, чем ld.lld отличается от GNU ld в работе с архивами и почему командная строка, которая собирается у тебя, может упасть у коллеги.
Написать разрешение имён в zt ld: читатель формата ar, три множества, три правила и две ошибки своими словами.

Идея: у каждого имени ровно один хозяин

Компоновщик получает на вход несколько перемещаемых объектных файлов. В каждом лежит таблица символов, и в уроке про ELF мы разделили её записи на три сорта. Локальные имена (static в C, обычные fn и var без export в Zig) видны только внутри модуля. С ними компоновщику делать нечего: компилятор уже проследил, что у каждого локального имени одно определение, и дал ему привязку LOCAL. Глобальные имена бывают определёнными в этом модуле и неопределёнными, с секцией UND.

Вся работа этапа, который книга называет разрешением символов, идёт над глобальными именами. Компилятор, встретив имя, которого в модуле нет, не ругается. Он верит, что определение найдётся где-то ещё, заводит в таблице запись с UND и оставляет в коде дырку под адрес. Дальше три возможных исхода:

определение нашлось ровно одно, ссылка привязана, все довольны;
определения нет нигде, и компоновщик печатает то самое undefined reference, которое ты видел десятки раз;
определений несколько, и надо решать, какое брать.

Третий случай самый интересный, с него и начнём. Одно замечание наперёд. Сообщение компоновщика говорит на языке имён из таблицы символов, а не на языке исходника. Если в C++ перегруженная функция Foo::bar(int) не нашлась, ты увидишь в ошибке _ZN3Foo3barEi: компилятор закодировал класс и типы аргументов в имя, потому что компоновщик перегрузок не понимает, ему нужны разные строки. Zig и C имена не искажают: export fn addvec попадает в таблицу как addvec. А вот имена без export Zig пишет с именем модуля, vector.addvec, мы такие сегодня увидим.

Сильные, слабые и COMMON

Каждому глобальному определению компилятор приписывает силу. В книге сортов два.

Сильное: функции и инициализированные глобальные переменные.
Слабое: неинициализированные глобальные переменные.

Откуда взялось второе? В C строка int x; на уровне файла это не определение, а пробное определение. Старые компиляторы Unix шли дальше стандарта и разрешали ставить int x; в нескольких файлах сразу, как в Фортране с его блоками COMMON. Чтобы это работало, компилятор не клал такую переменную в .bss, а заводил символ с особым номером секции COMMON: “места пока нет, выдели его сам, а если кто-то определил имя по-настоящему, возьми то”. Это мы видели в уроке 42 как псевдосекцию.

В сегодняшнем ELF сортов на деле три, и nm показывает их разными буквами:

Буква `nm`	Привязка и секция	Откуда берётся	Сила
`T`, `D`, `B`	`GLOBAL`, обычная секция	функция, переменная с инициализатором; в Zig любой `export`	сильное
`C`	`GLOBAL`, секция `COM`	`int x;` в C при `-fcommon`	слабее сильного
`W`, `V`	`WEAK`	`__attribute__((weak))` в C, `.linkage = .weak` в Zig	слабее сильного

Книга про привязку WEAK молчит и называет слабыми только COMMON. Правила от этого не меняются, но механизмы разные, и мы разберём оба.

Посмотрим на COMMON живьём. Один и тот же файл, собранный двумя способами:

/* bar3.c */
int x;

void f(void) {
    x = 15212;
}

$ gcc -fcommon -c bar3.c -o bar3c.o
$ gcc -c bar3.c -o bar3n.o
$ nm bar3c.o bar3n.o

bar3c.o:
0000000000000000 T f
0000000000000004 C x

bar3n.o:
0000000000000000 T f
0000000000000000 B x

Снято в контейнере debian:bookworm, linux/amd64, GCC 12.2 и binutils 2.40; все выводы GNU-инструментов в этом уроке оттуда. С ключом -fcommon переменная получила букву C, и в колонке адреса у неё стоит не адрес, а размер и выравнивание: четыре. Без ключа это обычное B, сильное определение в .bss. Второй вариант и есть умолчание с GCC 10 (2020 год) и Clang 11. До этого тридцать лет умолчанием был первый, и вся глава книги написана про него.

Три правила

Когда у имени несколько определений, компоновщик Unix решает так.

Два сильных определения одного имени запрещены.
Одно сильное и сколько угодно слабых: берётся сильное.
Только слабые: берётся любое из них.

Поиграй с правилами, прежде чем мы начнём ломать настоящие программы. В лаборатории два модуля на Zig и три имени. Переключай у каждого имени сорт объявления и тип, смотри на вердикт компоновщика и на раскладку памяти внизу.

Пройди по сценариям из списка. Обрати внимание на третий, “ловушка i32 против f64”: компоновщик сообщает, что всё в порядке, и именно это плохая новость. К нему мы придём через три демонстрации.

Правило 1: два сильных

/* foo1.c */
int main(void) {
    return 0;
}

/* bar1.c */
int main(void) {
    return 0;
}

$ gcc foo1.c bar1.c -o g1
/usr/bin/ld: /tmp/ccj2aTnh.o: in function `main':
bar1.c:(.text+0x0): multiple definition of `main'; /tmp/ccGilgx9.o:foo1.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status

То же через zig cc, у которого внутри не GNU ld, а ld.lld из LLVM:

$ zig cc -target x86_64-linux-musl foo1.c bar1.c -o p1
ld.lld: error: duplicate symbol: main
>>> defined at foo1.c:2
>>>            foo1.o:(main)
>>> defined at bar1.c:2
>>>            bar1.o:(.text+0x0)

Два компоновщика, два текста, смысл один. Запомни оба: multiple definition of это GNU, duplicate symbol это LLVM и macOS. Оба называют оба файла, и это важно. Когда мы будем писать свою ошибку в zt ld, сделаем так же: сообщение “имя определено дважды” без имён файлов бесполезно.

Это хорошая ошибка. Она громкая, она на этапе сборки, она показывает пальцем. Следующие две не такие.

Правило 2: сильное побеждает молча

/* foo3.c */
#include <stdio.h>

void f(void);

int x = 15213;

int main(void) {
    f();
    printf("x = %d\n", x);
    return 0;
}

Второй файл это bar3.c, который мы уже видели: в нём int x; без инициализатора и функция f, которая пишет в x число 15212. Автор bar3.c мог быть уверен, что x это его личная переменная. Собираем по-старому:

$ gcc -fcommon foo3.c bar3.c -o g3 && ./g3
x = 15212

Ни ошибки, ни предупреждения. В foo3.o определение сильное (D), в bar3.o это COMMON, по второму правилу взято сильное, и обе единицы трансляции теперь делят одну переменную. Функция f из чужого модуля поменяла x в main, и в исходнике foo3.c нет ни одной строчки, по которой это можно заподозрить. В программе на двух файлах это смешно, в программе на двух тысячах такое ищут днями: переменная с коротким именем вроде count, buf или debug внезапно меняет значение, хотя её никто не трогает.

Теперь без ключа, как собирает современный компилятор:

$ gcc foo3.c bar3.c -o g3n
/usr/bin/ld: /tmp/cclOmBZF.o:(.bss+0x0): multiple definition of `x'; /tmp/ccc2Xibu.o:(.data+0x0): first defined here
collect2: error: ld returned 1 exit status

int x; стал сильным определением в .bss, сработало правило 1, тихий баг превратился в громкий. Вот и весь смысл -fno-common: пробных определений с точки зрения компоновщика больше нет. Платой стали старые программы, у которых int x; стоял прямо в заголовке без extern. Каждый файл, включивший такой заголовок, получал своё COMMON-определение, компоновщик сливал их в одно, и всё работало. После перехода на GCC 10 такие проекты разом перестали собираться, и если ты когда-нибудь будешь оживлять код из девяностых, первой ошибкой почти наверняка увидишь именно эту. Правильное лечение: extern int x; в заголовке и одно int x; в одном .c. Неправильное, но быстрое: вернуть -fcommon.

Правило 3: любое из слабых

/* foo4.c */
#include <stdio.h>

void f(void);

int x;

int main(void) {
    x = 15213;
    f();
    printf("x = %d\n", x);
    return 0;
}

/* bar4.c */
int x;

void f(void) {
    x = 15212;
}

$ gcc -fcommon -Wl,--warn-common foo4.c bar4.c -o g4 && ./g4
/usr/bin/ld: /tmp/ccyT26cx.o and /tmp/ccR6kyQW.o: warning: multiple common of `x'
x = 15212

Оба определения COMMON, компоновщик выбрал одно, переменная опять общая. Предупреждение появилось только потому, что мы попросили его ключом --warn-common; без ключа тишина. “Любое” в формулировке правила не значит “случайное”: GNU ld и ld.lld из двух COMMON берут то, что больше по размеру, а при равных размерах первое по командной строке. Так будет поступать и наш zt ld. Но полагаться на это в программе нельзя, порядок файлов в сборке меняется от любого рефакторинга.

Ловушка: компоновщик не знает типов

Правила 2 и 3 становятся по-настоящему опасными, когда у одноимённых определений разные типы. В таблице символов типа C нет. Есть имя, секция, смещение и размер, причём размер компоновщик для выбора не использует. Значит, сверить int x с double x ему просто нечем.

/* foo5.c */
#include <stdio.h>

void f(void);

int x = 15213;
int y = 15212;

int main(void) {
    f();
    printf("x = 0x%x y = 0x%x\n", x, y);
    return 0;
}

/* bar5.c */
double x;

void f(void) {
    x = -0.0;
}

$ gcc -fcommon foo5.c bar5.c -o g5 && ./g5
/usr/bin/ld: warning: alignment 4 of symbol `x' in /tmp/ccg7WlGM.o is smaller than 8 in /tmp/ccgFkfPF.o
x = 0x0 y = 0x80000000

В y никто не писал. Разберём, что произошло, по байтам. Сильное определение x из foo5.o занимает четыре байта в .data, сразу за ним лежат четыре байта y:

$ nm -n g5 | grep -w '[xy]'
0000000000004018 D x
000000000000401c D y

Функция f скомпилирована в убеждении, что x это double, восемь байтов. Минус ноль в формате IEEE 754 из урока про числа с плавающей точкой это один знаковый бит и все остальные нули: 0x8000000000000000. Запись восьми байтов little endian по адресу x кладёт младшие четыре нулевых байта в x и старшие 0x80000000 в y. Машина сделала ровно то, что ей сказали.

GNU ld в этот раз хотя бы предупредил, и то случайно: он заметил не разницу типов, а разницу выравниваний, четыре против восьми. Поменяй double на long long с тем же выравниванием на какой-нибудь другой платформе или int на float, и предупреждения не будет. ld.lld на том же примере молчит совсем:

$ zig cc -target x86_64-linux-musl -fcommon foo5.c bar5.c -o p5 && ./p5
x = 0x0 y = 0x80000000

Книга советует в таких случаях собирать с ключом вроде -fno-common и превращать предупреждения компоновщика в ошибки. С 2020 года первую половину совета компиляторы выполняют за тебя.

На macOS. Здесь тридцать лет ещё не кончились. У Apple clang для целей Darwin умолчание по-прежнему -fcommon: на macOS 26 с Apple clang 21 пример foo3.c bar3.c собирается без единого ключа и печатает x = 15212, а foo5.c bar5.c портит y, причём компоновщик Apple не предупреждает и о выравнивании. В выводе nm -m такая переменная помечена словом (common). Формат объектников тут Mach-O, а не ELF, имена в таблице получают подчёркивание спереди (_x, _main), ошибка первого правила выглядит как duplicate symbol '_main' in: с двумя файлами ниже. Ещё одно отличие понадобится во второй половине урока: компоновщик Apple, как и ld.lld, не зависит от порядка архивов в командной строке. Всё остальное, включая сам формат ar, совпадает. Если хочешь на Маке поведение как на Linux, добавляй -fno-common сам или собирай через zig cc -target x86_64-linux-musl и запускай в контейнере, как делаем мы.

Что на месте этих багов делает Zig

Пройдём по тем же трём правилам с объектниками, собранными из Zig.

COMMON в Zig нет. У языка нет пробных определений: export var x: i32 = undefined; это полноценное определение, и в таблицу символов оно идёт как B, в .bss. Проверим:

export var x: i32 = undefined;
var hidden: i32 = 0;
export fn touch() void {
    hidden += 1;
}

$ zig build-obj uninit.zig -target x86_64-linux -O ReleaseSmall
$ nm uninit.o
0000000000000000 T touch
0000000000000004 B x

Буквы C нет, hidden без export в глобальные имена не попал вовсе. Значит, баги правил 2 и 3 в их классическом виде, через забытый инициализатор, на Zig не написать. Два модуля с export var x дают ошибку первого правила:

export var x: i32 = 0;

export fn f() void {
    x = 15212;
}

$ zig build-obj bar_dup.zig -target x86_64-linux -O ReleaseSmall
$ zig build-exe main5.zig bar_dup.o -target x86_64-linux
error: duplicate symbol definition: x
    note: defined by main5.o
    note: defined by bar_dup.o
$ zig build-exe main5.zig bar_dup.o -target x86_64-linux -O ReleaseSmall
error: ld.lld: duplicate symbol: x
    note: defined at bar_dup
    note:            bar_dup.o:(x)
    note: defined at main5
    note:            zdups_zcu.o:(.data+0x0)

Текстов опять два, и оба от Zig. В режиме Debug для x86-64 Linux версия 0.16 компонует собственным компоновщиком, написанным на Zig, и первое сообщение его. В режимах с оптимизацией работу делает ld.lld, и сообщение уже знакомое. Файл main5.zig покажу чуть ниже.

Внутри одной программы на Zig вопрос не возникает. Когда модули связаны через @import, компилятор видит их все сразу, имена живут в пространствах имён файлов, и два var x в двух файлах это просто a.x и b.x. До компоновщика дело не доходит, потому что вся программа на Zig это одна единица компиляции и один объектник. Три правила вступают в игру только на границе, которую ты провёл сам словом export.

А вот ловушка с типами никуда не делась. Граница между объектниками в Zig такая же слепая, как в C, потому что типов в ELF нет. Вот обещанный main5.zig и его сосед:

const std = @import("std");

extern fn f() void;

export var x: i32 = 15213;
export var y: i32 = 15212;

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    f();
    try out.print("x = 0x{x} y = 0x{x}\n", .{ x, @as(u32, @bitCast(y)) });
    try out.flush();
}

// Компилятор верит этой строке на слово: сверить её не с чем.
extern var x: f64;

export fn f() void {
    x = -0.0;
}

$ zig build-obj bar5.zig -target x86_64-linux -O ReleaseSmall
$ zig build-exe main5.zig bar5.o -target x86_64-linux -O ReleaseFast -fno-strip
$ ./main5
x = 0x0 y = 0x80000000
$ nm -n main5 | grep -w '[xy]'
0000000001077488 D x
000000000107748c D y

Тот же результат, что в C, и ни одного предупреждения. extern var x: f64 это обещание, которое ты даёшь компилятору, и проверить его некому. Любопытная деталь: в режиме Debug тот же пример печатает y = 0x3b6c, то есть y цел. Дело не в защите, а в раскладке: бэкенд Debug в 0.16 положил x и y с шагом шестнадцать байтов, и лишние четыре байта записи упали в пустоту между ними. Баг на месте, он просто не виден, и проявится в тот день, когда ты включишь оптимизацию. Это хороший пример того, почему “у меня в отладочной сборке работает” ничего не доказывает.

Защита тут одна, и она организационная: описание внешнего имени должно существовать в одном экземпляре. В C это заголовок, который включают и тот, кто определяет, и тот, кто пользуется. В Zig, если обе стороны написаны на Zig, это @import вместо пары export и extern. Если одна из сторон на C, описание берётся из заголовка через b.addTranslateC, как мы делали в уроке про build.zig и C, а не переписывается руками.

Слабое определение: `linkage = .weak`

Привязка WEAK это слабость по заказу. Библиотека даёт реализацию по умолчанию и разрешает приложению подменить её, просто определив то же имя обычным образом. Так устроены обработчики прерываний в прошивках микроконтроллеров (таблица векторов ссылается на слабые заглушки, твой обработчик их перекрывает), malloc во многих libc, функции compiler-rt. В C это __attribute__((weak)), в Zig опция встроенной функции @export:

//! Библиотека с запасным вариантом: слабое определение `log_level`.

fn defaultLevel() callconv(.c) u8 {
    return 1;
}

comptime {
    @export(&defaultLevel, .{ .name = "log_level", .linkage = .weak });
}

Слово export перед fn всегда даёт сильное определение, поэтому для слабого приходится звать @export явно, из блока comptime. Первый аргумент это указатель на то, что экспортируем, второй это std.builtin.ExportOptions: имя в таблице символов и linkage, у которого четыре значения, .internal, .strong, .weak и .link_once. Функции нужно соглашение о вызовах C, иначе Zig экспортировать её откажется.

//! Приложение даёт своё, сильное определение того же имени.

export fn log_level() u8 {
    return 3;
}

$ nm logger.o override.o

logger.o:
0000000000000000 W log_level
0000000000000000 t logger.defaultLevel

override.o:
0000000000000000 T log_level
0000000000000000 t override.log_level

Буква W это и есть слабое определение. Рядом маленькой t видны локальные имена с префиксом модуля, про которые я говорил в начале.

Слабая ссылка: `@extern`

У слабости есть вторая сторона. Слабым может быть не определение, а ссылка: “если такое имя есть, дай адрес, если нет, дай ноль и не ругайся”. Так программа спрашивает у компоновщика, подключили ли к ней необязательную часть.

const std = @import("std");

extern fn log_level() u8;

// Слабая ссылка. Со слабой привязкой @extern возвращает необязательный
// указатель: если `on_start` никто не определил, компоновщик впишет ноль.
const on_start = @extern(*const fn () callconv(.c) void, .{ .name = "on_start", .linkage = .weak });

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    try out.print("log_level = {d}\n", .{log_level()});
    // Адрес узнаёт только компоновщик, поэтому сравниваем его с нулём
    // в рантайме. Проверку `if (on_start) |hook|` Zig 0.16 сворачивает
    // при компиляции в "не null", и вызов уходит по нулевому адресу.
    if (@intFromPtr(on_start) != 0) {
        on_start.?();
        try out.writeAll("on_start вызван\n");
    } else {
        try out.writeAll("on_start никто не определил\n");
    }
    try out.flush();
}

Собираем два раза: только с библиотекой, потом с библиотекой, сильным log_level и файлом hook.zig из одной строки export fn on_start() void {}.

$ zig build-exe app.zig logger.o -target x86_64-linux -O ReleaseSafe -fno-strip
$ ./app
log_level = 1
on_start никто не определил

$ zig build-exe app.zig logger.o override.o hook.o -target x86_64-linux -O ReleaseSafe -fno-strip
$ ./app
log_level = 3
on_start вызван

$ readelf -s app | grep -w 'on_start\|log_level'      # первая сборка
   912: 0000000001025640     8 FUNC    WEAK   DEFAULT    4 log_level
   913: 0000000000000000     0 NOTYPE  WEAK   DEFAULT  UND on_start

В первой сборке сработало третье правило (слабое определение единственное), во второй второе (сильное победило), и порядок файлов в командной строке на исход не влияет. Последняя строка readelf показывает слабую ссылку, пережившую компоновку: секция UND, адрес ноль, ошибки нет.

Две ловушки, обе настоящие, обе сняты на Zig 0.16.0.

Первая описана в комментарии. Естественная запись if (on_start) |hook| hook(); компилируется, но проверка в ней выполняется на этапе компиляции: для Zig указатель на объявление заведомо не null. В машинном коде остаётся безусловный call по адресу ноль, и программа без hook.o падает с Segmentation fault at address 0x0. Я посмотрел в LLVM IR: сравнение появляется только после @intFromPtr. Стандартная библиотека сама пишет if (opt_init_array_start) |...| в std/start.zig, и ей это сходит с рук лишь потому, что __init_array_start компоновщик определяет всегда.

Вторая: собственный компоновщик Zig, который работает в Debug, слабых ссылок пока не понимает и отвечает error: undefined symbol: on_start. Поэтому в командах выше стоит -O ReleaseSafe, с ним компонует ld.lld.

Если проверка “есть ли обработчик” нужна тебе в программе целиком на Zig, всё это лишнее: @hasDecl(root, "on_start") решает ту же задачу при компиляции, с типами и без компоновщика. Слабые имена это инструмент для границы с чужим кодом.

Статические библиотеки

До сих пор на входе компоновщика были только .o. Представь, что так оно и есть, и подумай, как раздать программистам стандартную библиотеку C, в которой больше тысячи функций.

Один большой libc.o? Тогда в каждую программу, которой нужен один strlen, попадёт вся библиотека. Статический hello весил бы мегабайты, и каждая правка одной функции требовала бы пересобирать объектник целиком. Тысяча отдельных файлов strlen.o, printf.o, atoi.o? Тогда программист должен перечислить в командной строке ровно те, что нужны, включая те, которые нужны им самим. Ошибёшься в одну сторону, получишь undefined reference, в другую, лишний код. Встроить функции в компилятор, как делал Паскаль? Тогда любое изменение библиотеки это новая версия компилятора.

Статическая библиотека это компромисс между первым и вторым вариантом. Функции компилируются по одной на объектник, объектники складываются в один файл, архив, а компоновщик сам выбирает из архива только нужные. В командной строке одно имя, в бинарнике только то, чем программа пользуется.

Соберём библиотеку из книги. Две функции, каждая в своём файле:

/* addvec.c */
int addcnt = 0;

void addvec(int *x, int *y, int *z, int n) {
    addcnt++;
    for (int i = 0; i < n; i++)
        z[i] = x[i] + y[i];
}

/* multvec.c */
int multcnt = 0;

void multvec(int *x, int *y, int *z, int n) {
    multcnt++;
    for (int i = 0; i < n; i++)
        z[i] = x[i] * y[i];
}

/* vector.h */
void addvec(int *x, int *y, int *z, int n);
void multvec(int *x, int *y, int *z, int n);

/* main2.c */
#include <stdio.h>
#include "vector.h"

int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];

int main(void) {
    addvec(x, y, z, 2);
    printf("z = [%d %d]\n", z[0], z[1]);
    return 0;
}

$ gcc -c addvec.c multvec.c main2.c
$ ar rcs libvector.a addvec.o multvec.o
$ ar t libvector.a
addvec.o
multvec.o
$ ls -l addvec.o multvec.o libvector.a
-rw-r--r-- 1 root root 1368 Sep 21 06:34 addvec.o
-rw-r--r-- 1 root root 2990 Sep 21 06:34 libvector.a
-rw-r--r-- 1 root root 1384 Sep 21 06:34 multvec.o
$ nm libvector.a

addvec.o:
0000000000000000 B addcnt
0000000000000000 T addvec

multvec.o:
0000000000000000 B multcnt
0000000000000000 T multvec

Ключи ar: r вставить с заменой, c создать архив без вопросов, s записать в начало индекс имён. Арифметика размеров честная: 1368 плюс 1384 это 2752, остальные 238 байтов это подпись, два заголовка участников по шестьдесят байтов и индекс. Никакого сжатия, никакой структуры: nm просто идёт по участникам и печатает таблицу каждого. Формат мы разберём до байта, когда будем писать читатель.

Теперь компонуем. Ключ -static просит полностью статический бинарник, чтобы и libc пришла из архива libc.a.

$ gcc -static -o prog2c main2.o ./libvector.a
$ ./prog2c
z = [4 6]
$ nm prog2c | grep -w 'addvec\|multvec\|addcnt\|multcnt'
00000000004a62f8 B addcnt
000000000040166a T addvec

В бинарнике есть addvec и его счётчик, а multvec нет: main2.o на него не ссылался, и участник multvec.o остался в архиве. GNU ld умеет рассказать, кого и зачем он взял, ключом -M:

$ gcc -static -Wl,-M -o prog2c main2.o ./libvector.a | head -6
Archive member included to satisfy reference by file (symbol)

./libvector.a(addvec.o)       main2.o (addvec)
/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/libc.a(libc-start.o)
                              /usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/crt1.o (__libc_start_main)
/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/libc.a(check_fds.o)

Читается так: участник addvec.o из libvector.a включён, потому что main2.o сослался на addvec. Ниже та же история про libc.a: стартовый файл crt1.o позвал __libc_start_main, тот потянул check_fds.o, и так далее по цепочке. Запись libvector.a(addvec.o) общепринятая, наш zt ld будет называть участников так же.

Обычно путь к библиотеке не пишут целиком. Ключ -lvector значит “найди libvector.a или libvector.so в каталогах поиска”, ключ -L. добавляет к ним текущий каталог: gcc -static -o prog2l main2.o -L. -lvector. Для алгоритма это та же самая командная строка, -l всего лишь сокращение имени файла.

Статическая библиотека в `build.zig`

В Zig архив собирает система сборки. В уроке 6 мы уже строили граф из модулей и программ, библиотека добавляется в него одним узлом.

//! Библиотека libvector: две функции с интерфейсом C.

export var addcnt: i32 = 0;
export var multcnt: i32 = 0;

export fn addvec(x: [*]const i32, y: [*]const i32, z: [*]i32, n: usize) void {
    addcnt += 1;
    for (0..n) |i| z[i] = x[i] + y[i];
}

export fn multvec(x: [*]const i32, y: [*]const i32, z: [*]i32, n: usize) void {
    multcnt += 1;
    for (0..n) |i| z[i] = x[i] * y[i];
}

const std = @import("std");

extern fn addvec(x: [*]const i32, y: [*]const i32, z: [*]i32, n: usize) void;

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    const x = [_]i32{ 1, 2 };
    const y = [_]i32{ 3, 4 };
    var z: [2]i32 = undefined;
    addvec(&x, &y, &z, z.len);

    try out.print("z = [{d} {d}]\n", .{ z[0], z[1] });
    try out.flush();
}

const std = @import("std");

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    // Статическая библиотека: на выходе zig-out/lib/libvector.a.
    const vector = b.addLibrary(.{
        .name = "vector",
        .linkage = .static,
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/vector.zig"),
            .target = target,
            .optimize = optimize,
        }),
    });
    b.installArtifact(vector);

    const exe = b.addExecutable(.{
        .name = "prog",
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/main.zig"),
            .target = target,
            .optimize = optimize,
        }),
    });
    // Порядок в командной строке компоновщика система сборки выводит
    // из графа зависимостей сама: библиотека встанет после того, кто её зовёт.
    exe.root_module.linkLibrary(vector);
    b.installArtifact(exe);
}

$ zig build -Dtarget=x86_64-linux -Doptimize=ReleaseFast
$ ls -l zig-out/lib
-rw-r--r--  1 bondiano  wheel  6926 Sep 21 13:36 libvector.a
$ zig ar t zig-out/lib/libvector.a
.zig-cache/o/ad33bd38471a70b27394bdbbe0bbcf40/libvector_zcu.o
$ ./zig-out/bin/prog
z = [4 6]
$ nm zig-out/bin/prog | grep -w 'addvec\|multvec\|addcnt\|multcnt'
0000000001087104 B addcnt
0000000001074f40 T addvec
0000000001087100 B multcnt
0000000001074e90 T multvec

zig ar это тот же llvm-ar, он идёт в поставке Zig, ставить binutils не нужно. А теперь посмотри на вывод внимательно, в нём два сюрприза.

В архиве один участник, libvector_zcu.o. Буквы zcu значат Zig compilation unit: модуль Zig со всем, что он импортирует, компилируется в один объектник, и дробить его по функциям компилятор не будет. Отсюда второй сюрприз: multvec и multcnt попали в программу, хотя их никто не зовёт. Компоновщик выбирает из архива объектники, а не функции. В C это свойство прятали дисциплиной “одна функция, один файл”, на которой держится вся libc.a. У Zig библиотека из одного модуля приходит целиком или не приходит вовсе.

Что с этим делать? Если обе стороны на Zig, статическая библиотека не нужна: подключай код модулем через @import, компилятор увидит всю программу и выбросит неиспользуемое сам, ещё до компоновщика. Архив из Zig нужен тогда, когда библиотеку будет звать C или другой язык. Хочешь при этом мелкую нарезку, заведи несколько addLibrary или несколько объектников через b.addObject и сложи их в один архив.

И обрати внимание на комментарий над linkLibrary. Ты описал зависимость “программе нужна библиотека”, а не место файла в командной строке. Почему это заметное облегчение, станет ясно через пять минут.

Алгоритм: три множества и один проход

Как именно компоновщик выбирает участников? Он читает командную строку слева направо, ровно один раз, и ведёт три множества.

E: объектники, которые войдут в исполняемый файл.
U: имена, на которые уже кто-то сослался, а определения пока не было.
D: имена, у которых определение уже есть.

В начале все три пусты. Для очередного файла f из командной строки:

если f это объектник, он идёт в E без условий, его определения переходят в D (и вычёркиваются из U, если там были), его неопределённые имена добавляются в U, если их ещё нет в D;
если f это архив, компоновщик перебирает участников. Участник m, который определяет хоть одно имя из U, добавляется в E, и с ним поступают как с объектником: обновляют U и D. Перебор повторяется, пока за круг в E попадает хотя бы один участник, потому что взятый участник сам может сослаться на соседа по архиву. Когда круг прошёл впустую, про остальных участников этого архива компоновщик забывает навсегда.

Когда файлы кончились, U обязано быть пустым. Если нет, каждое оставшееся имя это undefined reference. Если пусто, компоновщик переходит ко второму этапу, перемещению, и это уже следующий урок.

Прогоним руками gcc -static main2.o ./libvector.a. Драйвер gcc дописывает в командную строку своё: в начало стартовый файл crt1.o, в конец libc.a. Стартовые файлы для краткости опустим.

Шаг	Файл	E	U	D
0		пусто	пусто	пусто
1	`main2.o`	`main2.o`	`addvec`, `printf`	`main`, `x`, `y`, `z`
2	`libvector.a`	плюс `addvec.o`	`printf`	плюс `addvec`, `addcnt`
3	`libc.a`	плюс `printf.o` и те, кого он потянул	пусто	плюс `printf` и остальные

На шаге 2 участник multvec.o ничего из U не определяет и в E не попадает. Алгоритм простой и быстрый: один проход, каждый архив открывается один раз. Придуман он был в те времена, когда перечитать библиотеку с ленты было дорого. Платим мы за эту простоту до сих пор.

Порядок в командной строке

Поменяем два файла местами.

$ gcc -static -o bad ./libvector.a main2.o
/usr/bin/ld: main2.o: in function `main':
main2.c:(.text+0x28): undefined reference to `addvec'
collect2: error: ld returned 1 exit status

Библиотека на месте, addvec в ней есть, nm его показывает. А компоновщик говорит, что определения нет. Прогони алгоритм: когда очередь дошла до libvector.a, множество U было пустым, ни один участник не подошёл, архив закрыт. Потом пришёл main2.o, добавил addvec в U, и закрыть его уже некому. Сообщение об ошибке при этом ни словом не намекает на порядок. Это одна из самых частых причин, по которым люди часами смотрят в Makefile: “я же подключил библиотеку”.

Отсюда правило: библиотеки ставят в конец командной строки, после всех объектников. Если библиотеки независимы друг от друга, этого хватает. Если нет, порядок нужен и между ними: тот, кто пользуется, стоит левее того, кем пользуются. Пусть foo.o зовёт функцию из libx.a, а та зовёт функцию из liby.a. Тогда годится только foo.o libx.a liby.a.

Вот головоломка на это правило. Перетаскивай файлы в командной строке и смотри, как меняются E, U и D после каждого из них. Начни со сценария “libvector.a main.o libc.a” и почини его, потом переходи к зависимым библиотекам.

Циклические зависимости

Бывает, что правильного порядка нет. Сделаем две библиотеки, которые нужны друг другу.

/* fx.c, уйдёт в libx.a */
int gy(int v);

int fx(int v) {
    return gy(v) + 1;
}

/* hx.c, тоже в libx.a */
int hx(int v) {
    return v * 2;
}

/* gy.c, уйдёт в liby.a */
int hx(int v);

int gy(int v) {
    return hx(v) + 10;
}

/* cyc.c */
#include <stdio.h>

int fx(int v);

int main(void) {
    printf("%d\n", fx(5));
    return 0;
}

main зовёт fx из libx.a, тот зовёт gy из liby.a, а тот возвращается в libx.a за hx.

$ gcc -c fx.c hx.c gy.c cyc.c
$ ar rcs libx.a fx.o hx.o
$ ar rcs liby.a gy.o
$ gcc -static -o cyc cyc.o libx.a liby.a
/usr/bin/ld: liby.a(gy.o): in function `gy':
gy.c:(.text+0x11): undefined reference to `hx'
collect2: error: ld returned 1 exit status
$ gcc -static -o cyc cyc.o liby.a libx.a
/usr/bin/ld: libx.a(fx.o): in function `fx':
fx.c:(.text+0x11): undefined reference to `gy'
collect2: error: ld returned 1 exit status

Оба порядка ломаются, и по сообщениям видно, как именно. В первом случае из libx.a взят только fx.o, потому что на тот момент hx никому не был нужен; liby.a дал gy.o, тот попросил hx, но libx.a уже закрыт. Во втором случае liby.a просмотрен, когда в U был один fx, и не дал ничего.

Лекарств три.

$ gcc -static -o cyc cyc.o libx.a liby.a libx.a && ./cyc
21
$ gcc -static -o cyc cyc.o -Wl,--start-group libx.a liby.a -Wl,--end-group && ./cyc
21

Первое из книги: повторить библиотеку в командной строке. Второй проход по libx.a застанет hx в U и возьмёт hx.o. Выглядит как опечатка, но это законный приём, и в старых Makefile ты встретишь -lfoo -lbar -lfoo именно поэтому. Второе: скобки --start-group и --end-group, между которыми GNU ld ходит по архивам кругами, пока находит что-то новое. Это удобнее, но медленнее на больших библиотеках, и man ld честно об этом предупреждает. Третье лекарство лучшее: слить две библиотеки, которые не могут жить друг без друга, в одну. Внутри одного архива алгоритм и так ходит кругами.

Есть и противоположный инструмент, про который книга не пишет. Иногда участник нужен, хотя на него никто не ссылается: например, он регистрирует себя в таблице плагинов через конструктор. Алгоритм E/U/D такого участника не возьмёт никогда. Ключ --whole-archive перед именем архива велит включить всех участников без разбора, --no-whole-archive возвращает обычное поведение для следующих файлов.

А `ld.lld` так не делает

Теперь неожиданное. Повторим оба неправильных порядка через zig cc:

$ zig cc -target x86_64-linux-musl -o bad libvector.a main2.o && ./bad
z = [4 6]
$ zig cc -target x86_64-linux-musl -o cyc cyc.o libx.a liby.a && ./cyc
21

Собралось и работает. ld.lld устроен иначе: встретив архив, он запоминает все имена, которые в нём определены, и если позже появляется ссылка на такое имя, возвращается в архив и достаёт участника. Проход по-прежнему один, но множество “где что можно найти” живёт до конца. Так же ведут себя компоновщик Apple и mold. Авторы lld описывают это как сознательное отступление от традиции Unix: порядок архивов не должен ломать сборку.

Звучит как чистое улучшение, и для тебя лично так и есть. Проблема в переносимости: командная строка, которая годами собиралась через lld или на Маке, упадёт с undefined reference, как только кто-то соберёт проект обычным GNU ld, например в дистрибутивном пакете. У lld на этот случай есть ключ --warn-backrefs: он находит места, где GNU ld споткнулся бы.

$ zig ld.lld --warn-backrefs -o wb start.o libx.a liby.a
ld.lld: warning: backward reference detected: hx in liby.a(gy.o) refers to libx.a(hx.o)

Здесь start.o это крошечный _start, который зовёт fx, чтобы не тащить libc, а объектники собраны с -O1 -ffreestanding. Предупреждение называет ровно ту ссылку назад, на которой выше упал GNU ld. Через zig cc -Wl,--warn-backrefs этот ключ в 0.16 не проходит (unsupported linker arg), поэтому ld.lld вызван напрямую.

Слабое в объектнике против сильного в архиве

У правил силы есть тонкость, которая видна только вместе с архивами. Заведём слабый addvec, который заполняет результат семёрками, и поставим его перед библиотекой с настоящим, сильным:

/* weakvec.c */
__attribute__((weak)) void addvec(int *x, int *y, int *z, int n) {
    for (int i = 0; i < n; i++)
        z[i] = 7;
}

$ gcc -static -o w1 main2.o weakvec.o ./libvector.a && ./w1
z = [7 7]
$ gcc -static -o w2 main2.o weakvec.o addvec.o && ./w2
z = [4 6]

Во второй команде сильное определение пришло объектником, оба попали в E, и второе правило сработало как положено. В первой победило слабое. Противоречия нет: слабое определение из weakvec.o вычеркнуло addvec из U, и когда очередь дошла до архива, открытых ссылок не осталось, участник addvec.o в E не попал. Правила силы выбирают только среди тех, кто уже в E, а архив даёт участника только под открытую ссылку. ld.lld здесь ведёт себя так же, я проверил: z = [7 7]. Запомни этот случай, наш zt ld закрепит его тестом.

Проект zt: компоновщик, шаг первый

Пора открыть чёрный ящик. В прошлом уроке zt научился читать ELF: у нас есть elf.File.parse, таблица символов elf.SymbolTable с полем first_global, методы symbol.isUndefined() и symbol.binding(), константа elf.format.shn_common. Этого достаточно, чтобы написать первую половину компоновщика, разрешение имён. Готового файла на выходе сегодня не будет: размещать секции и вписывать адреса мы научимся в следующем уроке. Зато zt ld уже сможет сказать про любую командную строку, соберётся ли она, какие участники архивов попадут в бинарник и откуда будет взято каждое имя. И объяснит обе главные ошибки по-русски.

План шага:

src/link/archive.zig: читатель формата ar;
src/link/resolve.zig: множества E, U, D, сила определений, три правила, две ошибки;
src/ld.zig: вход в компоновщик и отчёт о разрешении;
src/main.zig: подкоманда ld, а zt nm начинает понимать архивы;
tests/step_43.zig и одна новая фикстура, libvector.a.

Формат ar до байта

Посмотрим на архив своим же инструментом из урока 6. Фикстуры addvec.o и multvec.o лежат в fixtures/link/ с прошлого урока, сложим их в библиотеку:

$ zig ar rcs fixtures/link/libvector.a fixtures/link/addvec.o fixtures/link/multvec.o
$ zig build run -- hexdump fixtures/link/libvector.a | head -12
00000000  21 3c 61 72 63 68 3e 0a 2f 20 20 20 20 20 20 20  |!<arch>./       |
00000010  20 20 20 20 20 20 20 20 30 20 20 20 20 20 20 20  |        0       |
00000020  20 20 20 20 30 20 20 20 20 20 30 20 20 20 20 20  |    0     0     |
00000030  30 20 20 20 20 20 20 20 35 30 20 20 20 20 20 20  |0       50      |
00000040  20 20 60 0a 00 00 00 04 00 00 00 76 00 00 00 76  |  `........v...v|
00000050  00 00 05 1a 00 00 05 1a 61 64 64 76 65 63 00 61  |........addvec.a|
00000060  64 64 63 6e 74 00 6d 75 6c 74 76 65 63 00 6d 75  |ddcnt.multvec.mu|
00000070  6c 74 63 6e 74 00 61 64 64 76 65 63 2e 6f 2f 20  |ltcnt.addvec.o/ |
00000080  20 20 20 20 20 20 30 20 20 20 20 20 20 20 20 20  |      0         |
00000090  20 20 30 20 20 20 20 20 30 20 20 20 20 20 36 34  |  0     0     64|
000000a0  34 20 20 20 20 20 31 31 32 38 20 20 20 20 20 20  |4     1128      |
000000b0  60 0a 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00  |`..ELF..........|

Формат старше ELF лет на двадцать, и это видно: он почти целиком текстовый.

Первые восемь байтов это подпись !<arch> и перевод строки.
Дальше идут участники. У каждого заголовок ровно на шестьдесят байтов, все поля это текст, добитый пробелами: имя (16 байтов), время изменения (12), владелец (6), группа (6), права в восьмеричном виде (8), размер содержимого в десятичном (10) и два байта конца заголовка, обратная кавычка и перевод строки. llvm-ar по умолчанию пишет время и владельцев нулями, чтобы одинаковые входы давали побайтно одинаковый архив.
За заголовком лежит содержимое, столько байтов, сколько сказано в поле размера. Если размер нечётный, после содержимого стоит один байт добивки: заголовки выровнены на два.

Первый участник в дампе носит имя /, и его размер 50. Это не объектник, а индекс: четыре байта big endian с числом имён (00 00 00 04), затем по четыре байта на смещение участника, который имя определяет (0x76 дважды и 0x51a дважды), затем сами имена через нулевой байт. Индекс пишет ключ s у ar, и настоящие компоновщики смотрят только в него, чтобы не разбирать каждого участника. Мы поступим проще и честнее для учебного проекта: индекс пропустим и спросим у каждого участника его собственную таблицу символов, читатель ELF у нас уже есть. На библиотеке из тысячи объектников это было бы медленно, на наших незаметно.

По смещению 0x76 начинается заголовок участника addvec.o/. Косая черта закрывает имя: так формат GNU разрешает пробелы в именах. Размер 1128 совпадает с размером addvec.o на диске, и сразу после обратной кавычки видна подпись 7f 45 4c 46, начало обычного ELF. Архив и правда всего лишь объектники подряд.

Остаётся одна деталь: в поле имени шестнадцать байтов, а файлы бывают длиннее. Тогда в архиве появляется ещё один служебный участник с именем //, в нём длинные имена лежат подряд, а в заголовке объектника вместо имени стоит / и десятичное смещение в этой таблице, например /12.

//! Читатель статических библиотек, формат `ar`.
//!
//! Архив `.a` это объектники, сложенные в один файл подряд. В начале стоит
//! подпись `!<arch>\n`, дальше у каждого участника текстовый заголовок на
//! шестьдесят байтов и за ним содержимое. Числа в заголовке записаны
//! десятичными цифрами с пробелами, потому что формат старше самого ELF.

const std = @import("std");

pub const magic = "!<arch>\n";

pub const Error = error{ NotArchive, BadArchive };

/// Расположение полей заголовка участника. Все поля это текст.
const header_size = 60;
const name_field = 0;
const name_length = 16;
const size_field = 48;
const size_length = 10;
const end_field = 58;
const end_marker = "`\n";

pub const Member = struct {
    name: []const u8,
    data: []const u8,
};

pub fn isArchive(bytes: []const u8) bool {
    return std.mem.startsWith(u8, bytes, magic);
}

/// Обходит участников архива по порядку. Служебные участники (таблица
/// символов `/` и таблица длинных имён `//`) наружу не отдаются.
pub const Iterator = struct {
    bytes: []const u8,
    offset: usize = magic.len,
    /// Имена длиннее пятнадцати знаков лежат в участнике `//`,
    /// а в заголовке вместо имени стоит `/смещение`.
    long_names: []const u8 = "",

    pub fn init(bytes: []const u8) Error!Iterator {
        if (!isArchive(bytes)) return error.NotArchive;
        return .{ .bytes = bytes };
    }

    pub fn next(iterator: *Iterator) Error!?Member {
        while (iterator.offset < iterator.bytes.len) {
            const header_end = iterator.offset + header_size;
            if (header_end > iterator.bytes.len) return error.BadArchive;
            const header = iterator.bytes[iterator.offset..header_end];
            if (!std.mem.eql(u8, header[end_field..][0..2], end_marker)) return error.BadArchive;

            const size_text = std.mem.trim(u8, header[size_field..][0..size_length], " ");
            const size = std.fmt.parseInt(usize, size_text, 10) catch return error.BadArchive;
            if (header_end + size > iterator.bytes.len) return error.BadArchive;
            const data = iterator.bytes[header_end..][0..size];

            // Участники выровнены на два байта: после нечётного размера идёт добивка.
            iterator.offset = header_end + size + (size & 1);

            const raw_name = std.mem.trimEnd(u8, header[name_field..][0..name_length], " ");
            if (std.mem.eql(u8, raw_name, "/")) continue;
            if (std.mem.eql(u8, raw_name, "//")) {
                iterator.long_names = data;
                continue;
            }
            return .{ .name = try iterator.memberName(raw_name), .data = data };
        }
        return null;
    }

    fn memberName(iterator: Iterator, raw: []const u8) Error![]const u8 {
        // Короткое имя записано как `addvec.o/`, длинное как `/12`.
        if (raw.len > 1 and raw[0] == '/') {
            const offset = std.fmt.parseInt(usize, raw[1..], 10) catch return error.BadArchive;
            if (offset >= iterator.long_names.len) return error.BadArchive;
            const rest = iterator.long_names[offset..];
            const end = std.mem.indexOfAny(u8, rest, "/\n") orelse rest.len;
            return rest[0..end];
        }
        return std.mem.trimEnd(u8, raw, "/");
    }
};

test "архив из двух участников, у первого нечётный размер" {
    const bytes = magic ++
        "a.o/            0           0     0     644     3         `\n" ++ "abc\n" ++
        "b.o/            0           0     0     644     2         `\n" ++ "de";

    var iterator = try Iterator.init(bytes);
    const first = (try iterator.next()).?;
    try std.testing.expectEqualStrings("a.o", first.name);
    try std.testing.expectEqualStrings("abc", first.data);
    const second = (try iterator.next()).?;
    try std.testing.expectEqualStrings("b.o", second.name);
    try std.testing.expectEqualStrings("de", second.data);
    try std.testing.expectEqual(@as(?Member, null), try iterator.next());
}

test "не архив отвергается" {
    try std.testing.expectError(error.NotArchive, Iterator.init("\x7fELF"));
}

Итератор ничего не копирует: Member.data это срез того же буфера, в который прочитан архив. Память под участников не выделяется, и освобождать нечего. Обрати внимание на size & 1: так добивка до чётного записывается без ветвления.

Множества E, U, D

Теперь сердце шага. Структура Resolver хранит три множества из алгоритма почти буквально: objects это E, undefined это U, defined это D. Для U и D взят std.StringArrayHashMapUnmanaged, хеш-таблица, которая помнит порядок вставки. Порядок нам важен: ошибки должны печататься в том порядке, в каком имена встретились, а не в порядке хешей, иначе тесты на тексты сообщений станут лотереей.

//! Первая половина компоновщика: разрешение имён.
//!
//! Алгоритм из учебника. Компоновщик идёт по командной строке слева направо
//! и держит три множества:
//!   E  объектники, которые войдут в бинарник;
//!   U  имена, на которые кто-то сослался, а определения ещё не было;
//!   D  имена, у которых определение уже есть.
//! Объектник попадает в E всегда. Архив просматривается участник за
//! участником, и в E идёт только тот, кто определяет что-нибудь из U.
//! Отсюда знаменитое правило: библиотеки пишут в конце командной строки.
//! В конце U обязано быть пустым.

const std = @import("std");

const archive = @import("archive.zig");
const elf = @import("../elf.zig");

/// Файл из командной строки: объектник или архив, уже прочитанный в память.
pub const Input = struct {
    name: []const u8,
    bytes: []const u8,
};

/// Объектник из множества E.
pub const Object = struct {
    /// `main.o` или `libvector.a(addvec.o)`: так его называют сообщения.
    name: []const u8,
    file: elf.File,
    symbols: elf.SymbolTable,
};

/// Сила определения. Чем больше число, тем сильнее.
pub const Strength = enum(u8) {
    /// STB_WEAK: «возьми меня, если никого лучше не найдётся».
    weak,
    /// COMMON: неинициализированная глобальная переменная старого C.
    /// Места под неё ещё нет, его выделит компоновщик в `.bss`.
    common,
    /// Обычное определение функции или переменной.
    strong,

    pub fn of(symbol: elf.Symbol) Strength {
        if (symbol.shndx == elf.format.shn_common) return .common;
        return if (symbol.binding() == .weak) .weak else .strong;
    }
};

pub const Definition = struct {
    /// Номер объектника в E, который имя определил.
    object: u32,
    symbol: elf.Symbol,
    strength: Strength,
};

/// Кто и как сослался на имя, у которого пока нет определения.
const Reference = struct {
    from: []const u8,
    /// Слабая ссылка не обязана разрешиться: её адресом станет ноль.
    weak: bool,
};

pub const Resolver = struct {
    /// Всё, что компоновщик выделяет, живёт до конца компоновки,
    /// поэтому память берём из арены и по отдельности не освобождаем.
    arena: std.mem.Allocator,
    objects: std.ArrayList(Object) = .empty,
    undefined: std.StringArrayHashMapUnmanaged(Reference) = .empty,
    defined: std.StringArrayHashMapUnmanaged(Definition) = .empty,
    /// Сообщения об ошибках. Копим все, а не падаем на первой.
    diagnostics: std.ArrayList([]const u8) = .empty,

    pub fn init(arena: std.mem.Allocator) Resolver {
        return .{ .arena = arena };
    }

    /// Очередной файл командной строки.
    pub fn addInput(resolver: *Resolver, input: Input) !void {
        if (archive.isArchive(input.bytes)) {
            try resolver.addArchive(input);
        } else {
            try resolver.addObject(input.name, input.bytes);
        }
    }

    /// Объектник идёт в E без условий, а его имена обновляют U и D.
    pub fn addObject(resolver: *Resolver, name: []const u8, bytes: []const u8) !void {
        const file = try elf.File.parse(bytes);
        const symbols = try elf.SymbolTable.find(file, .symtab);
        const object_index: u32 = @intCast(resolver.objects.items.len);
        try resolver.objects.append(resolver.arena, .{ .name = name, .file = file, .symbols = symbols });

        // Локальные символы стоят в таблице первыми и в разрешении не участвуют.
        var index = symbols.first_global;
        while (index < symbols.count()) : (index += 1) {
            const symbol = try symbols.get(index);
            const symbol_name = symbols.name(symbol);
            if (symbol.isUndefined()) {
                try resolver.reference(symbol_name, name, symbol.binding() == .weak);
            } else {
                try resolver.define(symbol_name, .{
                    .object = object_index,
                    .symbol = symbol,
                    .strength = .of(symbol),
                });
            }
        }
    }

    /// Архив просматриваем кругами: участник, взятый в E, сам может сослаться
    /// на соседа по архиву, который на прошлом круге был не нужен.
    fn addArchive(resolver: *Resolver, input: Input) !void {
        var taken: std.AutoArrayHashMapUnmanaged(usize, void) = .empty;

        var changed = true;
        while (changed) {
            changed = false;
            var members = try archive.Iterator.init(input.bytes);
            var number: usize = 0;
            while (try members.next()) |member| : (number += 1) {
                if (taken.contains(number)) continue;
                if (!try resolver.definesWanted(member.data)) continue;

                const name = try std.fmt.allocPrint(resolver.arena, "{s}({s})", .{ input.name, member.name });
                try resolver.addObject(name, member.data);
                try taken.put(resolver.arena, number, {});
                changed = true;
            }
        }
    }

    /// Определяет ли объектник хоть одно имя из U.
    fn definesWanted(resolver: *Resolver, bytes: []const u8) !bool {
        const file = try elf.File.parse(bytes);
        const symbols = try elf.SymbolTable.find(file, .symtab);

        var index = symbols.first_global;
        while (index < symbols.count()) : (index += 1) {
            const symbol = try symbols.get(index);
            // COMMON участника из архива не вытягивает: так ведёт себя и GNU ld.
            if (symbol.isUndefined() or symbol.shndx == elf.format.shn_common) continue;
            if (resolver.undefined.contains(symbols.name(symbol))) return true;
        }
        return false;
    }

    fn reference(resolver: *Resolver, name: []const u8, from: []const u8, weak: bool) !void {
        if (resolver.defined.contains(name)) return;
        const entry = try resolver.undefined.getOrPut(resolver.arena, name);
        if (!entry.found_existing) {
            entry.value_ptr.* = .{ .from = from, .weak = weak };
        } else if (!weak) {
            // Хватит одной обычной ссылки, чтобы имя стало обязательным.
            entry.value_ptr.weak = false;
        }
    }

    /// Три правила выбора между определениями одного имени:
    /// два сильных это ошибка; сильное побеждает слабое и COMMON;
    /// из равных по силе остаётся первое, а из двух COMMON большее.
    fn define(resolver: *Resolver, name: []const u8, new: Definition) !void {
        _ = resolver.undefined.orderedRemove(name);

        const entry = try resolver.defined.getOrPut(resolver.arena, name);
        if (!entry.found_existing) {
            entry.value_ptr.* = new;
            return;
        }

        const old = entry.value_ptr.*;
        if (old.strength == .strong and new.strength == .strong) {
            try resolver.report("повторное определение {s}: сначала в {s}, потом в {s}", .{
                name,
                resolver.objects.items[old.object].name,
                resolver.objects.items[new.object].name,
            });
            return;
        }

        const new_wins = @intFromEnum(new.strength) > @intFromEnum(old.strength) or
            (new.strength == .common and old.strength == .common and new.symbol.size > old.symbol.size);
        if (new_wins) entry.value_ptr.* = new;
    }

    /// Итог разрешения: всё, что осталось в U без слабой ссылки, это ошибка.
    pub fn finish(resolver: *Resolver) !void {
        var iterator = resolver.undefined.iterator();
        while (iterator.next()) |entry| {
            if (entry.value_ptr.weak) continue;
            try resolver.report("неразрешённая ссылка на {s} из {s}", .{ entry.key_ptr.*, entry.value_ptr.from });
        }
    }

    pub fn failed(resolver: Resolver) bool {
        return resolver.diagnostics.items.len > 0;
    }

    fn report(resolver: *Resolver, comptime fmt: []const u8, args: anytype) !void {
        const text = try std.fmt.allocPrint(resolver.arena, fmt, args);
        try resolver.diagnostics.append(resolver.arena, text);
    }
};

/// Разрешение имён для целой командной строки.
pub fn resolve(arena: std.mem.Allocator, inputs: []const Input) !Resolver {
    var resolver: Resolver = .init(arena);
    for (inputs) |input| try resolver.addInput(input);
    try resolver.finish();
    return resolver;
}

test "сила определения читается из символа" {
    const strong: elf.Symbol = .{ .name = 0, .info = 0x12, .other = 0, .shndx = 1, .value = 0, .size = 0 };
    const weak: elf.Symbol = .{ .name = 0, .info = 0x22, .other = 0, .shndx = 1, .value = 0, .size = 0 };
    const common: elf.Symbol = .{ .name = 0, .info = 0x11, .other = 0, .shndx = elf.format.shn_common, .value = 8, .size = 8 };
    try std.testing.expectEqual(Strength.strong, Strength.of(strong));
    try std.testing.expectEqual(Strength.weak, Strength.of(weak));
    try std.testing.expectEqual(Strength.common, Strength.of(common));
}

Пройдём по решениям, которые здесь приняты.

Сила это перечисление с порядком. Strength объявлен как enum(u8) со значениями по возрастанию силы, и выбор победителя сводится к сравнению чисел. Между COMMON и слабым выбирается COMMON: так поступает GNU ld, и так проще объяснить (COMMON хотя бы настоящая переменная, а слабое определение просит заменить себя при первой возможности).

Три правила живут в одной функции. define сначала вычёркивает имя из U, потом смотрит, было ли оно в D. Два сильных дают сообщение с обоими файлами, по образцу GNU ld и lld, только по-русски: повторное определение addvec: сначала в addvec.o, потом в copy.o. В остальных случаях новое определение вытесняет старое, только если оно строго сильнее, либо оба COMMON и новое больше. При равной силе остаётся первое: это наше “любое” из третьего правила.

Ошибки копятся, а не обрывают работу. report складывает строки в diagnostics, и компоновка идёт дальше. Настоящие компоновщики делают так же: если в программе пять неразрешённых имён, ты хочешь увидеть все пять за один запуск, а не чинить по одному.

Архив просматривается кругами. addArchive повторяет обход, пока за круг взят хоть один участник, в точности как в алгоритме. definesWanted отвечает на вопрос “определяет ли участник что-нибудь из U”, и COMMON-символ для этого не годится: пробное определение не повод тащить объектник из библиотеки. После возврата из addArchive про архив никто не помнит, поэтому наш zt ld зависит от порядка файлов так же, как GNU ld. Это сознательный выбор: мы воспроизводим алгоритм книги, чтобы увидеть знаменитую ошибку своими глазами.

Слабая ссылка не ошибка. В U рядом с именем лежит, кто сослался первым (это пойдёт в текст ошибки) и была ли ссылка слабой. Одна обычная ссылка делает имя обязательным. В finish всё, что осталось в U и не слабое, превращается в неразрешённая ссылка на addvec из main.o.

Память из арены. Компоновщик это программа, которая всё выделяет, ничего не освобождает и завершается. Арена из урока про аллокаторы подходит идеально: ни одного deinit у множеств, один arena.deinit() снаружи.

Вход в компоновщик

//! `zt ld`: статический компоновщик для x86-64 Linux, первая половина.
//!
//! Пока он умеет только разрешение имён:
//!   link/archive.zig   читает статические библиотеки;
//!   link/resolve.zig   решает, какие объектники берём и какое определение у имени.
//! Размещение секций и перемещения придут следующим шагом, поэтому готового
//! файла ещё нет, а `image` всегда `null`.

const std = @import("std");

pub const archive = @import("link/archive.zig");
pub const resolve = @import("link/resolve.zig");

pub const Input = resolve.Input;

pub const Result = struct {
    /// Готовый исполняемый файл. На этом шаге его ещё некому собрать.
    image: ?[]const u8,
    /// Сообщения об ошибках, по строке на каждую.
    diagnostics: []const []const u8,
    resolver: resolve.Resolver,
};

/// Компонует файлы в порядке командной строки. Вся память берётся из арены:
/// результат живёт, пока жива она.
pub fn link(arena: std.mem.Allocator, inputs: []const Input) !Result {
    var resolver = try resolve.resolve(arena, inputs);

    if (!resolver.defined.contains("_start")) {
        try resolver.diagnostics.append(arena, "нет точки входа: никто не определил _start");
    }
    return .{ .image = null, .diagnostics = resolver.diagnostics.items, .resolver = resolver };
}

/// Отчёт о разрешении имён: кто вошёл в E и откуда взято каждое имя из D.
pub fn report(out: *std.Io.Writer, resolver: resolve.Resolver) !void {
    try out.writeAll("E, объектники в бинарнике:\n");
    for (resolver.objects.items) |object| try out.print("  {s}\n", .{object.name});

    try out.writeAll("D, откуда взято имя:\n");
    var iterator = resolver.defined.iterator();
    while (iterator.next()) |entry| {
        const definition = entry.value_ptr.*;
        try out.print("  {s:<16} {s:<7} {s}\n", .{
            entry.key_ptr.*,
            @tagName(definition.strength),
            resolver.objects.items[definition.object].name,
        });
    }
}

test {
    std.testing.refAllDecls(@This());
}

link уже имеет форму, которая останется до конца проекта: на входе файлы в порядке командной строки, на выходе образ или список ошибок. Поле image пока всегда null, его наполнит следующий шаг. Проверка точки входа стоит здесь, а не в resolve, потому что _start это требование к исполняемому файлу, а не к разрешению имён. Наши фикстуры собраны без libc: main.o сам определяет _start, зовёт run и выходит системным вызовом exit, как мы делали в уроке про голое железо.

Функция report временная, но полезная: она печатает E и D, то есть ровно тот ответ, ради которого шаг написан.

В src/root.zig добавляется одна строка рядом с остальными инструментами:

pub const ld = @import("ld.zig");

В build.zig число 43 дописывается в список шагов: const project_steps = [_]u8{ 6, 7, 9, 10, 11, 12, 42, 43 };.

Подкоманда `ld` и `zt nm` по архиву

В src/main.zig три правки. В текст usage добавь строки zt nm <файл или архив> (вместо прежней про nm) и zt ld <файл.o или архив.a>.... В цепочку разбора подкоманд в run добавь ветку:

    } else if (std.mem.eql(u8, command, "ld")) {
        try cmdLd(init, gpa, out, rest);

И замени cmdNm на новую версию, а рядом положи cmdLd:

fn cmdNm(
    init: std.process.Init,
    gpa: std.mem.Allocator,
    out: *std.Io.Writer,
    args: []const []const u8,
) !void {
    if (args.len != 1) return fail(out, "zt nm: нужен ровно один файл\n");
    const bytes = try std.Io.Dir.cwd().readFileAlloc(init.io, args[0], gpa, file_limit);

    // У архива печатаем таблицу каждого участника под его именем.
    if (zt.ld.archive.isArchive(bytes)) {
        var members = try zt.ld.archive.Iterator.init(bytes);
        while (try members.next()) |member| {
            try out.print("\n{s}:\n", .{member.name});
            try zt.nm.print(gpa, out, try parseElf(out, "nm", member.name, member.data));
        }
        return;
    }
    try zt.nm.print(gpa, out, try parseElf(out, "nm", args[0], bytes));
}

fn cmdLd(
    init: std.process.Init,
    gpa: std.mem.Allocator,
    out: *std.Io.Writer,
    args: []const []const u8,
) !void {
    var inputs: std.ArrayList(zt.ld.Input) = .empty;

    for (args) |arg| {
        if (std.mem.startsWith(u8, arg, "-")) {
            try out.print("zt ld: неизвестный флаг {s}\n", .{arg});
            return error.BadUsage;
        }
        // Порядок файлов важен, поэтому читаем и складываем как написано.
        const bytes = try std.Io.Dir.cwd().readFileAlloc(init.io, arg, gpa, file_limit);
        try inputs.append(gpa, .{ .name = arg, .bytes = bytes });
    }
    if (inputs.items.len == 0) return fail(out, "zt ld: нечего компоновать\n");

    const result = zt.ld.link(gpa, inputs.items) catch |err| {
        try out.print("zt ld: входной файл не читается как объектник ELF64 ({t})\n", .{err});
        return error.BadUsage;
    };
    if (result.diagnostics.len > 0) {
        for (result.diagnostics) |line| try out.print("zt ld: {s}\n", .{line});
        // Код 1, как у настоящего ld: ошибка во входных файлах, а не в ключах.
        try out.flush();
        std.process.exit(1);
    }
    try zt.ld.report(out, result.resolver);
}

zt nm теперь повторяет формат настоящего nm для архивов: пустая строка, имя участника с двоеточием, таблица. cmdLd читает файлы в том порядке, в каком они написаны, и этот порядок больше нигде не теряется. Код выхода при ошибках компоновки равен единице, как у GNU ld: двойка у нас занята под ошибки в ключах.

Запускаем

$ zig build run -- nm fixtures/link/libvector.a

addvec.o:
0000000000000000 B addcnt
0000000000000000 T addvec

multvec.o:
0000000000000000 B multcnt
0000000000000000 T multvec

$ zig build run -- ld fixtures/link/main.o fixtures/link/libvector.a
E, объектники в бинарнике:
  fixtures/link/main.o
  fixtures/link/libvector.a(addvec.o)
D, откуда взято имя:
  run              strong  fixtures/link/main.o
  _start           strong  fixtures/link/main.o
  addvec           strong  fixtures/link/libvector.a(addvec.o)
  addcnt           strong  fixtures/link/libvector.a(addvec.o)

Из архива взят один участник из двух, multvec в D нет. Теперь та самая ошибка порядка, наконец-то с нашей стороны:

$ zig build run -- ld fixtures/link/libvector.a fixtures/link/main.o
zt ld: неразрешённая ссылка на addvec из fixtures/link/main.o
$ echo $?
1

Повторное определение. Копия addvec.o под другим именем даёт два сильных определения сразу двух имён, и печатаются обе ошибки:

$ cp fixtures/link/addvec.o /tmp/copy43.o
$ zig build run -- ld fixtures/link/main.o fixtures/link/addvec.o /tmp/copy43.o
zt ld: повторное определение addvec: сначала в fixtures/link/addvec.o, потом в /tmp/copy43.o
zt ld: повторное определение addcnt: сначала в fixtures/link/addvec.o, потом в /tmp/copy43.o

Слабое определение. Фикстура weak.o из прошлого урока собрана из того самого @export с .linkage = .weak, и её addvec заполняет результат семёрками. Рядом с сильным объектником она проигрывает, перед архивом выигрывает, в точности как weakvec.c у GNU ld:

$ zig build run -- ld fixtures/link/main.o fixtures/link/weak.o fixtures/link/addvec.o
E, объектники в бинарнике:
  fixtures/link/main.o
  fixtures/link/weak.o
  fixtures/link/addvec.o
D, откуда взято имя:
  run              strong  fixtures/link/main.o
  _start           strong  fixtures/link/main.o
  addvec           strong  fixtures/link/addvec.o
  addcnt           strong  fixtures/link/addvec.o

$ zig build run -- ld fixtures/link/main.o fixtures/link/weak.o fixtures/link/libvector.a
E, объектники в бинарнике:
  fixtures/link/main.o
  fixtures/link/weak.o
D, откуда взято имя:
  run              strong  fixtures/link/main.o
  _start           strong  fixtures/link/main.o
  addvec           weak    fixtures/link/weak.o

Заметь в первом выводе: weak.o остался в E, хотя его addvec проиграл. Объектник из командной строки входит в бинарник целиком, и код проигравшего определения будет лежать в .text мёртвым грузом. И последнее, COMMON. Zig его не порождает, поэтому фикстура common.o объявляет символ ассемблерной директивой .comm shared_counter,8,8:

$ zig build run -- ld fixtures/link/main.o fixtures/link/addvec.o fixtures/link/common.o
...
  shared_counter   common  fixtures/link/common.o
  bump             strong  fixtures/link/common.o

Тесты шага

Тесты работают с теми же фикстурами через @embedFile, файловая система им не нужна. В fixtures/root.zig к структуре link из прошлого урока добавляются две строки: сам архив и эталонный вывод llvm-nm по нему (сними его любым nm в контейнере и положи рядом).

pub const libvector = @embedFile("link/libvector.a");
pub const libvector_nm = @embedFile("link/libvector.nm.txt");

//! Шаг 43: `zt ld`, разрешение имён. Архивы `.a`, множества E, U и D,
//! сильные и слабые определения, COMMON и две главные ошибки компоновки.

const std = @import("std");

const fixtures = @import("fixtures");
const zt = @import("zt");

const resolve = zt.ld.resolve;
const Input = zt.ld.Input;

const main_o: Input = .{ .name = "main.o", .bytes = fixtures.link.main.bytes };
const addvec_o: Input = .{ .name = "addvec.o", .bytes = fixtures.link.addvec.bytes };
const weak_o: Input = .{ .name = "weak.o", .bytes = fixtures.link.weak.bytes };
const common_o: Input = .{ .name = "common.o", .bytes = fixtures.link.common.bytes };
const libvector_a: Input = .{ .name = "libvector.a", .bytes = fixtures.link.libvector };

test "архив это объектники подряд" {
    var members = try zt.ld.archive.Iterator.init(fixtures.link.libvector);
    const first = (try members.next()).?;
    try std.testing.expectEqualStrings("addvec.o", first.name);
    try std.testing.expectEqualSlices(u8, fixtures.link.addvec.bytes, first.data);
    const second = (try members.next()).?;
    try std.testing.expectEqualStrings("multvec.o", second.name);
    try std.testing.expectEqual(@as(?zt.ld.archive.Member, null), try members.next());
}

test "nm по архиву совпадает с эталоном" {
    const gpa = std.testing.allocator;
    var out: std.Io.Writer.Allocating = .init(gpa);
    defer out.deinit();

    var members = try zt.ld.archive.Iterator.init(fixtures.link.libvector);
    while (try members.next()) |member| {
        try out.writer.print("\n{s}:\n", .{member.name});
        try zt.nm.print(gpa, &out.writer, try zt.elf.File.parse(member.data));
    }
    try std.testing.expectEqualStrings(fixtures.link.libvector_nm, out.written());
}

test "два объектника: U пустеет, D знает все имена" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, addvec_o });
    try std.testing.expect(!resolver.failed());
    try std.testing.expectEqual(@as(usize, 2), resolver.objects.items.len);
    try std.testing.expectEqual(@as(usize, 0), resolver.undefined.count());

    for ([_][]const u8{ "_start", "run", "addvec", "addcnt" }) |name| {
        try std.testing.expect(resolver.defined.contains(name));
    }
    // addvec определён во втором объектнике командной строки.
    try std.testing.expectEqual(@as(u32, 1), resolver.defined.get("addvec").?.object);
}

test "из архива берётся только нужный участник" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, libvector_a });
    try std.testing.expect(!resolver.failed());
    try std.testing.expectEqual(@as(usize, 2), resolver.objects.items.len);
    try std.testing.expectEqualStrings("libvector.a(addvec.o)", resolver.objects.items[1].name);
    // multvec никто не звал, и его в бинарнике не будет.
    try std.testing.expect(!resolver.defined.contains("multvec"));
}

test "архив раньше объектника: неразрешённая ссылка" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    // Когда компоновщик смотрел архив, U было пустым, и он ничего не взял.
    const resolver = try resolve.resolve(arena.allocator(), &.{ libvector_a, main_o });
    try std.testing.expect(resolver.failed());
    try std.testing.expectEqual(@as(usize, 1), resolver.diagnostics.items.len);
    try std.testing.expectEqualStrings(
        "неразрешённая ссылка на addvec из main.o",
        resolver.diagnostics.items[0],
    );
}

test "два сильных определения: ошибка с обоими именами файлов" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const copy: Input = .{ .name = "copy.o", .bytes = fixtures.link.addvec.bytes };
    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, addvec_o, copy });
    try std.testing.expect(resolver.failed());
    try std.testing.expectEqualStrings(
        "повторное определение addvec: сначала в addvec.o, потом в copy.o",
        resolver.diagnostics.items[0],
    );
    try std.testing.expectEqualStrings(
        "повторное определение addcnt: сначала в addvec.o, потом в copy.o",
        resolver.diagnostics.items[1],
    );
}

test "сильное побеждает слабое в любом порядке" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const weak_first = try resolve.resolve(arena.allocator(), &.{ main_o, weak_o, addvec_o });
    try std.testing.expect(!weak_first.failed());
    try std.testing.expectEqual(resolve.Strength.strong, weak_first.defined.get("addvec").?.strength);
    try std.testing.expectEqualStrings("addvec.o", weak_first.objects.items[weak_first.defined.get("addvec").?.object].name);

    const strong_first = try resolve.resolve(arena.allocator(), &.{ main_o, addvec_o, weak_o });
    try std.testing.expect(!strong_first.failed());
    try std.testing.expectEqualStrings("addvec.o", strong_first.objects.items[strong_first.defined.get("addvec").?.object].name);
}

test "слабое определение годится, когда сильного нет" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, weak_o });
    try std.testing.expect(!resolver.failed());
    try std.testing.expectEqual(resolve.Strength.weak, resolver.defined.get("addvec").?.strength);
}

test "слабое определение участника архива не вытесняет уже найденное" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    // weak.o закрыл ссылку на addvec, U опустело, и архив остался нетронутым.
    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, weak_o, libvector_a });
    try std.testing.expect(!resolver.failed());
    try std.testing.expectEqual(@as(usize, 2), resolver.objects.items.len);
    try std.testing.expectEqual(resolve.Strength.weak, resolver.defined.get("addvec").?.strength);
}

test "COMMON попадает в D со своей силой" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const resolver = try resolve.resolve(arena.allocator(), &.{ main_o, addvec_o, common_o });
    try std.testing.expect(!resolver.failed());
    const counter = resolver.defined.get("shared_counter").?;
    try std.testing.expectEqual(resolve.Strength.common, counter.strength);
    try std.testing.expectEqual(@as(u64, 8), counter.symbol.size);
}

test "без _start компоновка отказывает" {
    var arena: std.heap.ArenaAllocator = .init(std.testing.allocator);
    defer arena.deinit();

    const result = try zt.ld.link(arena.allocator(), &.{addvec_o});
    try std.testing.expectEqual(@as(?[]const u8, null), result.image);
    try std.testing.expectEqualStrings("нет точки входа: никто не определил _start", result.diagnostics[0]);
}

Посмотри, как тесты названы: каждый это одно утверждение из урока. “Из архива берётся только нужный участник”, “архив раньше объектника: неразрешённая ссылка”, “слабое определение участника архива не вытесняет уже найденное”. Тест на два сильных определения обходится без новой фикстуры: те же байты addvec.o поданы второй раз под именем copy.o. Тексты ошибок сверяются дословно. Это осознанная жёсткость: сообщение об ошибке такой же интерфейс программы, как формат вывода, и случайно испортить его при рефакторинге не должно получаться.

$ zig build test -Dstep=43 --summary all
...
+- run test 11 pass (11 total)
$ zig build test --summary all

Одиннадцать тестов шага зелёные, и вторая команда проверяет, что все прежние шаги тоже. Код шага чистые вычисления над байтами, поэтому тесты одинаково идут на macOS и на Linux, на arm64 и на x86-64: контейнер для них не нужен.

Упражнения

E43.1★

Три пары модулей на C, собранных с -fcommon. Для каждой пары скажи, что сделает компоновщик: ошибка (и по какому правилу), либо из какого модуля возьмётся определение. Запись ССЫЛКА(имя.модуль) -> ОПРЕДЕЛЕНИЕ(имя.модуль) пригодится.

Пара А: в первом модуле int start(void) { ... }, во втором int start; и функция p2, которая читает start. Пара Б: в первом void start(void) { ... }, во втором int start = 1;. Пара В: в первом double speed; и функция a, во втором float speed; и функция b, в третьем int speed = 3;. Потом пересобери мысленно все три пары с -fno-common и скажи, что изменится. Проверь ответы в SymbolResolutionLab, где это возможно, и настоящим gcc.

E43.2★

Пусть a и b это объектники или архивы в текущем каталоге, а запись a -> b значит, что a ссылается на имя, определённое в b. Для каждого случая напиши самую короткую командную строку для GNU ld, с которой всё разрешится:

p.o -> libx.a;
p.o -> libx.a -> liby.a;
p.o -> libx.a -> liby.a, и вдобавок liby.a -> libx.a -> p.o.

В третьем случае объясни, почему p.o повторять не нужно, а libx.a нужно. Проверь все три ответа в LinkOrderPuzzle, подобрав похожий сценарий.

E43.3★★

Возьми пример с порчей y (foo5.c и bar5.c). Почини его тремя способами, не меняя имён переменных: словом static в одном из файлов, заголовком с extern, ключом компилятора. Для каждого способа скажи, какая переменная x теперь у f, своя или общая, и на каком этапе (компиляция, компоновка, никогда) обнаружится несовпадение типов, если оно осталось.

E43.4★★

Собери с -fcommon два файла. В первом void p2(void); int main(void) { p2(); return 0; }. Во втором char main; и функция p2, которая печатает main через printf("0x%x\n", main). Программа соберётся и что-то напечатает. До запуска предскажи, что это за число и откуда оно, потом найди его в выводе objdump -d своей сборки. Почему на машине с другим компилятором или другим уровнем оптимизации число может стать иным? Что скажет компоновщик без -fcommon?

E43.5★★

Для main2.o из урока (или для fixtures/link/main.o, если удобнее) выпиши все записи .symtab, которые участвуют в разрешении имён. Для каждой скажи: определено имя в этом модуле или нет, какая у него сила, в какой секции оно лежит. Отдельно перечисли имена, которые есть в исходнике, но в таблице не участвуют в разрешении, и объясни почему. Проверь себя через zt readelf -s и zt nm.

E43.6★★

Перепиши демонстрацию слабого определения так, чтобы слабой была переменная, а не функция: библиотека даёт log_threshold: u8 = 1 со слабой привязкой, приложение по желанию определяет свою. Покажи через nm, что буква у слабой переменной V, а не W. Потом сделай у приложения log_threshold типа u32 и объясни по раскладке .data, что прочитает библиотека на little endian и что она прочитала бы на big endian.

E43.7★★★

Научи zt ld читать индекс архива, участника с именем /. Формат ты видел в дампе: число имён, смещения участников, имена через ноль, всё big endian. Перепиши definesWanted так, чтобы вопрос “определяет ли кто-нибудь имя из U” решался по индексу, без разбора ELF каждого участника. Подумай, что делать с архивом без индекса (собранным через ar rc без s): GNU ld в этом случае отказывается с советом запустить ranlib. Какое поведение выберешь ты и почему?

E43.8★★★

Сделай в zt ld режим --lld: разрешение имён, не зависящее от порядка архивов. Для этого архив, просмотренный впустую, нельзя забывать: заведи таблицу “имя, архив, участник” и заглядывай в неё каждый раз, когда имя попадает в U. Добавь тест, в котором libvector.a main.o проходит в новом режиме и падает в старом. Потом ответь на вопрос потруднее: может ли одна и та же командная строка собраться в обоих режимах, но дать разные бинарники? Подсказка: вспомни пример со слабым определением в объектнике.

Итоги

Разрешение имён это первая половина работы компоновщика: каждой ссылке на глобальное имя найти ровно одно определение. Локальные имена в этом не участвуют, типов в таблице символов нет.
У определения есть сила. Сильные это функции и инициализированные переменные; слабее них COMMON (пробное определение C при -fcommon) и символы с привязкой WEAK. В nm это буквы T, D, B против C и W, V.
Три правила: два сильных это ошибка, сильное побеждает слабые, из одних слабых берётся любое. Первое правило даёт громкую ошибку, второе и третье молча склеивают переменные разных модулей, а при разных типах портят соседнюю память.
С GCC 10 и Clang 11 умолчанием стал -fno-common, и пробное определение превратилось в сильное. На macOS у Apple clang старое умолчание, и баг воспроизводится без ключей.
В Zig нет COMMON, любой export сильный, а внутри программы на @import компоновщик вообще не нужен. Но пара export и extern с разными типами ломается так же тихо, как в C, причём в Debug это может быть не видно из-за раскладки.
Слабое определение в Zig это @export(&f, .{ .name = "...", .linkage = .weak }), слабая ссылка это @extern с той же опцией. В 0.16 адрес слабой ссылки проверяй через @intFromPtr, а не через if с захватом, и собирай с LLVM.
Статическая библиотека это архив ar: подпись, текстовые заголовки по шестьдесят байтов, объектники подряд. Компоновщик берёт из неё только нужных участников, и единица выбора это объектник. Библиотека из одного модуля Zig это один участник.
Алгоритм E, U, D идёт по командной строке один раз слева направо, поэтому у GNU ld библиотеки стоят в конце, зависимые правее зависящих, а циклы лечатся повтором, --start-group или слиянием библиотек. ld.lld, mold и компоновщик Apple от порядка архивов не зависят; --warn-backrefs находит места, где зависел бы GNU ld.
Слабое определение в объектнике побеждает сильное в архиве правее: архив даёт участника только под открытую ссылку.
zt ld теперь разрешает имена по этому алгоритму и объясняет ошибки своими словами, с обоими файлами в сообщении.

Дальше

У нас есть список объектников, которые войдут в программу, и для каждого имени известно, в каком из них оно определено. Не хватает адресов. В следующем уроке компоновщик разложит секции по памяти, пройдёт по записям перемещений и впишет настоящие числа в дырки, которые оставил компилятор. zt ld получит вторую половину, и программа из main.o и libvector.a впервые запустится и вернёт свои 10. А через урок мы вернёмся к библиотекам с другой стороны: динамическая компоновка откладывает разрешение имён до запуска программы, и те же слабые и сильные определения начинают работать между .so.

домашка

Домашка

Возьми любой старый проект на C (подойдёт исходник утилиты из девяностых) и собери его дважды: с -fcommon и с -fno-common. Выпиши все имена, на которых вторая сборка падает, и для каждого реши, что это было: забытый extern в заголовке или настоящая коллизия двух разных переменных. Проверь себя ключом компоновщика --warn-common.S
Научи свой zt ld ключу -M: для каждого участника архива, попавшего в E, печатай, какой файл и каким именем его вытянул, в том же виде, что у GNU ld. Сверь вывод с gcc -static -Wl,-M на main2.o и libvector.a из урока.S
Добавь в zt ld пару ключей --start-group и --end-group: архивы внутри группы просматриваются по кругу, пока хоть один участник попадает в E. Проверь на libx.a и liby.a из урока и напиши тест, в котором без группы компоновка отказывает, а с группой проходит.S

Разрешение имён и статические библиотеки

Цели урока

Идея: у каждого имени ровно один хозяин

Сильные, слабые и COMMON

Три правила

Правило 1: два сильных

Правило 2: сильное побеждает молча

Правило 3: любое из слабых

Ловушка: компоновщик не знает типов

Что на месте этих багов делает Zig

Слабое определение: linkage = .weak

Слабая ссылка: @extern

Статические библиотеки

Статическая библиотека в build.zig

Алгоритм: три множества и один проход

Порядок в командной строке

Циклические зависимости

А ld.lld так не делает

Слабое в объектнике против сильного в архиве

Проект zt: компоновщик, шаг первый

Формат ar до байта

Множества E, U, D

Вход в компоновщик

Подкоманда ld и zt nm по архиву

Запускаем

Тесты шага

Упражнения

Итоги

Дальше

Слабое определение: `linkage = .weak`

Слабая ссылка: `@extern`

Статическая библиотека в `build.zig`

А `ld.lld` так не делает

Подкоманда `ld` и `zt nm` по архиву