Everything so far has assumed a flat list of object files on the command line. Real builds do not do that, and the reason is not tidiness. A C++ program links against thousands of object files and uses a small fraction of them. Hand a linker all three thousand and it drags in megabytes of code that nothing calls, and every one of those extra objects is another chance for a duplicate symbol from a library you did not know was there.
The archive — libfoo.a, and on Windows the same container with a .lib extension — is the format that solves this. And the solution is a single idea: a member of an archive is a unit of inclusion, not a unit of storage. The bytes are all there; the linker is expected to take only the members something actually needs.
Which raises the question this concept exists to answer, and it is a question about algorithms rather than bytes:
And the subtlety that makes it hard: a member you load can introduce a new want. Load mathlib.o because it defines add, and it turns out to call something in strlib.o. So the set of things to load is not known at the start — it is a fixed point, and getting there is the whole algorithm. The previous concept was about which of two definitions survives; this one is about which of three hundred objects is loaded at all, and the two are the same question at different scales.
The container is older than almost everything else in this course and it is worth knowing why. The ar format is a plain sequence of 60-byte ASCII headers, each followed by a blob of bytes. No index of sections, no alignment requirement beyond “members start on even offsets”, and no type field for the contents. It predates ELF, COFF and Mach-O by a decade, and it has never been changed, because it does not need to be — its job is to be a bag of files, and it is a very good bag of files.
"!<arch>\n" 8 bytes, no alignment, no padding
then, repeating:
a 60-byte ASCII header
the member's bytes
one pad byte if the size is ODD
The 60 bytes, from a real file:
offset width field value in libdemo.a's first member
------ ----- ----------- ---------------------------------
0 16 name "/" (the symbol index)
16 12 mtime "0"
28 6 uid "0"
34 6 gid "0"
40 8 mode "0" (OCTAL)
48 10 size "52" (DECIMAL)
58 2 fmag 0x60 0x0a ("`" then newline)
Two details in that table are traps, and both are still live in files produced today:
size is decimal and mode is octal, in the same header, ten bytes apart. That is not a typo in the specification; it is what ar has always done. A reader that parses size as octal turns member 1032 into 564 — and since the reader then seeks to the wrong place, every subsequent member is garbage, not just this one. It fails loudly if you validate, and silently if you do not.libdemo.a's three members are 1032, 1080 and 960 — all even, so no padding appears here — but the rule is unconditional.The fmag field is the container's one integrity check, and it is worth more than it looks. A 60-byte header whose last two bytes are not 0x60 0x0a is not a header, which gives a reader a reliable way to know it has walked off the end — in a format with no table of contents and no total member count.
Opening libdemo.a, the very first member is not an object file at all. It is a symbol index, and it is the only piece of cleverness in the format:
00000008: 2f20 2020 2020 2020 2020 2020 2020 2020 /
00000018: 3020 2020 2020 2020 2020 2020 3020 2020 0 0
00000028: 2020 3020 2020 2020 3020 2020 2020 2020 0 0
00000038: 3532 2020 2020 2020 2020 600a 52 `.
and its 52 bytes of body:
00000044: 0000 0004 0000 0078 0000 0078 0000 04bc .......x...x....
00000054: 0000 0930 6164 6400 6d75 6c00 7374 726c ...0add.mul.strl
00000064: 656e 5f00 6e6f 626f 6479 5f63 616c 6c73 en_.nobody_calls
00000074: 5f6d 6500 _me.
+0 count BE u32 4 BIG-ENDIAN
+4 offset BE u32 0x78 add
+8 offset BE u32 0x78 mul
+12 offset BE u32 0x4bc strlen_
+16 offset BE u32 0x930 nobody_calls_me
+20 names NUL-separated, in the SAME order:
"add\0" "mul\0" "strlen_\0" "nobody_calls_me\0"
So the index is symbol name to the file offset of the member header that defines it. Note that add and mul both point at 0x78: one member, two symbols, one entry in the array each. And note the byte order, because it is the opposite of the object files inside:
0x78000000 and finds nothing. This is a historical fossil — the format's ar roots are from an era when the convention for such tables was network order, and it was never worth breaking. GNU ar also writes a second index, marked by a 0x02 byte, which is little-endian; the COFF course found both in a .lib and confirmed they disagree about the order of the entries as well as the byte order. So the practical rule for a reader is: try big-endian, and fall back.Here is the header of the first real member, at 0x78:
00000078: 6d61 7468 6c69 622e 6f2f 2020 2020 2020 mathlib.o/ 00000088: 3020 2020 2020 2020 2020 2020 3020 2020 0 0 00000098: 2020 3020 2020 2020 3634 3420 2020 2020 0 644 000000a8: 3130 3332 2020 2020 2020 600a 1032 `.
The name is mathlib.o/ — with a trailing slash and nothing after it. That slash is not part of the name, and it is not a long-name reference either. It is a terminator: in this format a trailing / marks where the name ends, and the name is space-padded to 16 bytes. The alternative spelling is /NN, where NN is a decimal offset into a long-name table held in a second special member called //, used for names longer than 15 characters.
So a reader faces a genuine ambiguity: a name starting with / could be a long-name reference, and mathlib.o/ ends in a slash. The disambiguation is that the digits must follow immediately — here they are spaces, so it is a terminator. And the second trap is that NN is decimal: the COFF course's demo.lib had a section named /45, and reading that as hex lands at offset 0x45 = 69, which is in the middle of the symbol names rather than at the start of the long-name string.
None of the above tells you whether any of it works. ld -Map= does, and it prints exactly the decision:
$ ld -o app -Map=app.map app.o libdemo.a $ sed -n '/Archive member included/,/^$/p' app.map Archive member included to satisfy reference by file (symbol) libdemo.a(mathlib.o) app.o (add) libdemo.a(strlib.o) app.o (strlen_)
Two members listed. unused.o is not mentioned anywhere in the map — not as included, not as discarded, not at all. The link succeeded, produced a working binary, and nobody_calls_me is simply not in it. That is the entire point of the format, and it is the reason the map file is such good evidence: it distinguishes not loaded from loaded and thrown away, which look identical in the output binary.
And the same map answers the harder question. libchain.a holds three objects whose dependencies run in the opposite order to their physical arrangement in the archive:
$ ar rcs libchain.a l2.o l3.o l1.o physical order $ ar t libchain.a l2.o l3.o l1.o $ ld -o chain -Map=chain.map main.o libchain.a Archive member included to satisfy reference by file (symbol) libchain.a(l1.o) main.o (level1) libchain.a(l2.o) libchain.a(l1.o) (level2) libchain.a(l3.o) libchain.a(l2.o) (level3)
Read the second column. l2.o was pulled in by a want created by l1.o, which was itself pulled in by a want in main.o. And l1.o is the last member in the file, while l2.o, which it needs, is the first. A single left-to-right pass would visit l2.o while nothing wanted level2 yet, skip it, and then arrive at l1.o too late to go back.
“Linkers read archives backwards” is a thing people say, and it is not what GNU ld does. The way to settle it is to build an archive where a backwards pass also fails, and see whether the link succeeds:
$ ar rcs libfwd.a l2.o l1.o l3.o $ ld -o fwd -Map=fwd.map main.o libfwd.a Archive member included to satisfy reference by file (symbol) libfwd.a(l1.o) main.o (level1) libfwd.a(l2.o) libfwd.a(l1.o) (level2) libfwd.a(l3.o) libfwd.a(l2.o) (level3)
With this order, a forward pass provably cannot work: l2.o is passed before anything wants level2. And a backward pass also cannot work: reading l3.o, l1.o, l2.o, the l1.o pull happens second and wants level2, which is still ahead of the cursor. Both single passes fail, and the link succeeded anyway.
So the algorithm is a fixed-point iteration: repeat the scan until a complete pass loads no new member. The number of passes is bounded by the number of members, so the naive implementation is quadratic, and real linkers use the index plus a worklist to get close to linear. But the correctness point is the one worth keeping, and it is not an optimisation detail: any implementation that assumes one pass in a fixed direction is wrong, and it will be wrong only for archives whose members happen to be in an unlucky order. That is the worst possible failure mode — correct on almost every build you test, wrong on someone else's.
Putting it together, the whole algorithm in one block, with the archive's own data showing where each step gets its information:
Three things in that pseudocode are worth drawing out, because each is a decision a format forced.
First: the index is consulted by name, and the member is only then read. A linker that read every member and discarded the useless ones would get the same answer and be dramatically slower — and would be wrong in one specific case, which the COFF course found: a member with no external symbols cannot appear in the index at all, so an index-driven linker will never load it, and a linker that reads everything will load it and may report duplicate definitions that the index-driven linker never sees. The index is not an optimisation; it is a semantic commitment about which members are eligible.
Second: the index maps one name to one offset, and that is a claim the linker trusts. Here the claim is checkable, and the course checks it. Each member's own ELF symbol table independently lists what it defines, so the index can be cross-verified against the members — and the two agree:
index says member at that offset defines ------------------- ----------------------------------------- add -> 0x78 0x78 mathlib.o [3] add GLOBAL mul -> 0x78 0x78 mathlib.o [4] mul GLOBAL strlen_ -> 0x4bc 0x4bc strlib.o [3] strlen_ GLOBAL nobody_calls_me -> 0x930 0x930 unused.o [3] nobody_calls_me GLOBAL
Two independent records of the same fact, so the index is verifiable without trusting the tool that wrote it. That is the property that makes an archive auditable at all, and it is the same property the verification concept is built on. Run python3 ardec.py libdemo.a to see the whole thing decoded field by field.
Third: the “already loaded, skip” case is not an optimisation either.add and mul both map to 0x78. A linker that loaded a member per symbol would put mathlib.o in the output twice, and the second copy's symbols would collide with the first's — producing a multiple definition error for a library that is perfectly fine. Which is the whole reason the index maps to a member rather than to a symbol.
$ cd courses/obj/assets/samples
$ python3 ardec.py libdemo.a # decode every field, written from the spec
$ ar t libdemo.a ; xxd -l 128 libdemo.a
$ ld -o /tmp/app -Map=/tmp/app.map app.o libdemo.a && grep -A4 'Archive member' /tmp/app.maplibdemo.a entirely by hand before running the tool. Read the 8-byte magic, the 60-byte index header, and the 52 index bytes; confirm the count is big-endian by re-reading the first four bytes; then find each member header and read its decimal size. Verify the sizes add up — 8 + 60 + 52 + (60 + 1032) + (60 + 1080) + (60 + 960) = 3372, which is the file's exact size. That arithmetic is the format's only structural integrity check, and it is worth doing once by hand.libdemo.a, and in the first member header change 52 to 040. Run ardec.py on the result. The first member's body will be 40 bytes instead of 52, the next header read will start 12 bytes early, fmag will not be 0x60 0x0a, and the walk will stop — if you implemented the fmag check. If you did not, it will keep printing garbage. This is the best possible demonstration that an integrity check in an ASCII header is worth more than it appears.l2, l1, l3 where a forward pass fails and l3, l1, l2 where a backward pass fails. Link all four and confirm all four succeed with identical output. Then, to make the point sharp, write a deliberately single-pass-forward linker over the index and show that it fails on one of the four orders and succeeds on the others. A bug that only reproduces on unlucky input is the kind that reaches production.static int helper(void) returning 1, and nothing else — nothing with external linkage — put it in an archive, and look at the index. It will not appear. Then work out the consequence: main cannot call it, so nothing is broken, and that is exactly why the index may leave it out. The index lists what the outside world is allowed to ask for, not what is in the bag..lib. The COFF course's ar_decode.py and demo.lib are in the COFF samples. Run it and find both index members. Confirm the byte order differs between them, and that the entry order differs too — one is link order, the other sorted. Then decide which one your reader should use, and write down the fallback rule you would implement if the first guess is wrong.app.o against libdemo.a and against the three objects directly, and compare the sizes of the .text sections in the map file. Then check that the unreferenced member really is absent by searching the output for nobody_calls_me in both the symbol table and the raw bytes. An archive that appears to work but quietly included everything would show up here and nowhere else.Without looking back: a linker reads an archive's symbol index, finds that a member defines a wanted symbol, and loads it. That member's own undefined references are then resolved against the same index, which pulls in a second member, and so on. Someone tells you that “linkers read archives backwards so that this works.” What is wrong with that explanation, and what is the correct one?
You are writing a linker and you have implemented archive resolution as a single forward pass over the index: for each symbol in your current set of undefined references, look it up, and if its member is not loaded, load it and add that member's undefined references to the set. It works on every library you have tested, and on your own machine it never fails. A user's build fails with undefined reference to 'level3' from a member that is demonstrably present in the archive and listed in its index. What is wrong, what would have made the bug appear in your own testing, and what is the smallest change that fixes it without making the common case slower?
The general habit: if the body of your loop modifies the collection you are looping over, you have written a fixed point and must iterate to one. And if a bug never reproduces locally, suspect that your inputs are ordered the way your algorithm happens to require.
An archive is a container format, and this is the first one in the course, so it is worth noticing what it shares with the three object formats and what it does not. It shares their central idea — a container with a table of contents and no schema — and it differs in having almost no structure at all. No section table, no symbol table of its own, no alignment rules, no versioning. Where Names Live found three strategies for storing a name; the archive picks the crudest possible one, a 16-byte space-padded ASCII field, because a member's name is not something anything has to look up efficiently — only the index is looked up, and the index stores offsets, not names.
The connection to Symbol Tables, Compared is the strongest one, and it is about a distinction people rarely make. An object's symbol table answers two different questions: what does this file define, and what does this file want? The archive's index answers only the first, and only for symbols that are externally visible. That is why a static function never appears in an index, and it is a genuinely different notion of “symbol” from the one an object file's STB_LOCAL entries represent. A linker resolves against the union of undefined references and index entries; an archive is a filter applied to the first before it is used to answer the second.
The fixed-point algorithm connects to A Hole and a Record in a way worth stating, because it reframes the archive. An unresolved hole does not stay a hole when the link ends — it becomes an error. So the linker must, at the end, be certain that no wanted symbol is satisfiable, and the archive index is how it establishes that without reading every member. The index is therefore not a cache; it is the evidence for a negative conclusion. If a name is in no index and not defined by any object on the command line, it is genuinely unresolvable — and a linker that skipped unread members could not draw that conclusion, which is why the index's coverage is semantic rather than incidental.
On the correctness side there is a security consequence that connects to the PE course, and it is the reason archives are a recurring source of real bugs. Which members get loaded depends on the order, the index, and the set of undefined symbols at the time each archive is considered — so changing the order of libraries on a link line can change which code is in the binary, with no error and often no obvious symptom. That is a supply-chain surface, not just a build nuisance: it is why reproducible builds fix library order, and why --start-group/--end-group and --as-needed exist. An archive makes the linker's output depend on a piece of data — the index — that a reader is very likely to regenerate rather than verify.
And the COFF archives connection is the payoff of the whole course's cross-format method. A Windows .lib is the same container, with the same !<arch>\n magic, the same 60-byte headers, the same // long-name table, and two different symbol indexes instead of one. Which means everything in this concept applies to PE linking unchanged, and it is the clearest demonstration in the collection that a container format outlives the object formats it carries.
Next: the last of the three selection mechanisms, and the one with the smallest file footprint — because unlike an archive, a weak symbol costs one bit and is always available.