COMDAT, GROUP, linkonce

19 minintermediateModule 4: Merging and SelectionContinues from obj-pic

19 min · Module 4: Merging and Selection · Intermediate

Why This Matters

Here is a C++ program that is perfectly legal, correct, and which a naive linker refuses to build:

  // comdat_a.cpp                    // comdat_b.cpp

  inline int shared_inline(int x)         inline int shared_inline(int x)
      return x + 1;                            return x + 1;

  int a(int v)                            int b(int v)
      return shared_inline(v);                 return shared_inline(v);

Braces omitted for the width; the two definitions are otherwise identical, which is the entire point of the example.

Two translation units, each with its own copy of shared_inline, each wanting it at a global name. A linker that reports a duplicate symbol is not broken — it is being told the truth about a file format that has no way to say “these two definitions are the same definition.” C++ says they are: an inline function with external linkage may be defined in any number of translation units, and every one of those definitions must be identical. The language has made a promise that the object file has to be able to record, or the toolchain cannot keep it.

Every format here has an answer, and the surprising part is that the three teams put the answer in three completely different places in the file:

  ELF      a whole EXTRA SECTION   (SHT_GROUP), plus a weak symbol
  COFF     a FLAG on an existing section (IMAGE_SCN_LNK_COMDAT), plus a
           selection policy and a content checksum in the symbol table
  Mach-O   NO SECTION MECHANISM AT ALL -- one bit in the symbol table
           (N_WEAK_DEF) and an ordinary .text

That last one is the finding, and it runs against the name you already know. There is no linkonce section type in Mach-O. Modern clang does not emit one, and the term does not appear in LLVM's own Mach-O format definitions at all — which is checkable, and the check is in the exercise below. The mechanism is a symbol-table bit. Three teams, one problem, and the answer that survived is the one that needed the least new machinery.

A Simple Model

Before the three mechanisms, the decisions they all encode, because a linker has to make four separate decisions and the formats differ on which of them the file records and which the linker infers.

GIVEN two definitions of symbol S, one from each of two objects Q0 IS THERE EVEN A DEFINITION TO MERGE? If the symbol is UNDEFINED in the object there is nothing to merge, and a group would have nothing to own. This is the C inline trap, and it is the most common reason a learner expects a COMDAT and finds none. Q1 WHICH DEFINITION WINS? Only one copy may survive. ELF and Mach-O answer this the same way -- it does not matter, because the definitions are required to be identical. COFF goes further and records a SELECTION policy explicitly. Q2 HOW DO I KNOW THEY ARE THE SAME DEFINITION? The hard one. The three formats answer it three different ways, or do not answer it at all. ELF nobody checks. The name is the claim. COFF a 32-bit CHECKSUM of the section contents. Mach-O nobody checks. The name is the claim. Q3 WHICH BYTES SURVIVE? The winner's, and every relocation against the loser has to be re-pointed. Same in all three.

Mark the model as a model. The four decisions are real, but no format states them as a checklist. ELF's group section records Q0 implicitly (a group with one member section and a weak symbol) and Q1 as a flag bit. COFF records all four explicitly, in three different fields, across two different tables. Mach-O records only Q0 and Q1, and leaves Q2 entirely to the language lawyer.

The Actual Detail

ELF: a group is its own section, and the name is the signature

ca_elf.o has a section called .group. All eight bytes of it:

  Hex dump of section '.group':
    0x00000000 01000000 05000000                   ........

  +0  flags     u32   0x00000001   GRP_COMDAT
  +4  shndx     u32   0x00000005   section 5 is a member

  and readelf renders the whole structure:
    COMDAT group section [4] `.group' [_Z13shared_inlinei] contains 1 sections:
       [Index]    Name
       [    5]   .text._Z13shared_inlinei

Three things to notice, and the third is the one that matters most.

The signature is the symbol name._Z13shared_inlinei is the Itanium C++ mangling of shared_inline(int) — _Z, then 13 for the length, then the characters. Nothing else in the group identifies it. The group section has no name of its own that means anything; the symbol is the key.
The member section is named after the signature too..text._Z13shared_inlinei. So the key appears twice, in two tables, and both had better agree — which is a real invariant a validator can check for free.
The member carries the G group flag, and the symbol is demoted to WEAK. From the symbol table:

       Num:    Value          Size Type    Bind   Vis      Ndx Name
         3: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 .text._Z13shared_inlinei
         5: 0000000000000000     4 FUNC    WEAK   DEFAULT    5 _Z13shared_inlinei

So ELF answers the “which wins” question by demoting the symbol to STB_WEAK. That is the whole trick, and it is worth noticing that it is the same mechanismthe next-but-one concept covers for ordinary weak symbols. COMDAT is not a fourth weak-symbol design; it is weak symbols plus a section, so a linker can throw away the section and everything in it. That is the reason the body has to be in its own section: without a section boundary, a linker cannot discard it.

COFF: a flag, a duplicate name, a policy and a checksum

ca_coff.o has six sections, and two of them are named .text:

  Number: 1   Name: .text   RawDataSize: 5   Characteristics 0x60500020
  Number: 4   Name: .text   RawDataSize: 4   Characteristics 0x60501020
                                                        ^^^^^^^^
                        the difference is 0x1000 = IMAGE_SCN_LNK_COMDAT

And the COMDAT section's own bytes are 8d 41 01 c3 — the same four bytes as in the other object. But the interesting data is not in the section header. It is in the symbol table's auxiliary record:

  ca_coff.o: COMDAT aux: Length=4  nrel=0  Checksum=0x751D2B5A  Number=4  Selection=2
  cb_coff.o: COMDAT aux: Length=4  nrel=0  Checksum=0x751D2B5A  Number=4  Selection=2

  Selection 2 = IMAGE_COMDAT_SELECT_ANY
  "any of these copies will do"

So COFF's answer is scattered across three fields in two tables, and every one of them is doing something the other two formats do not do:

IMAGE_SCN_LNK_COMDAT in the section header — the flag that says “this section is discardable.” ELF expresses the same idea with the G flag, so this one is a tie.
Selection in the aux record — the policy. This is the part ELF and Mach-O simply do not have.SELECT_ANY means any copy will do; SELECT_NODUPLICATES means “only discard this if there is an identical one elsewhere”; SELECT_ASSOCIATIVE means “discard me together with the section named in the next field.” A linker therefore has three policies available and the producer gets to choose, which is strictly more expressive than picking one for everybody.
Checksum in the aux record — the only mechanism among the three formats that attempts Q2 at all. Both objects here hash to 0x751D2B5A, which is what makes the merge safe. And it is advisory, which matters enormously.

The checksum is not an integrity check, and treating it as one is how you ship a miscompilation. The COFF course measured this: changing one character of an inline function's body makes the checksum differ, and GNU ld in PE mode discards the differing copy anyway, with no diagnostic. The result is a program that returns the wrong answer. So the honest statement is that COFF gives a linker the information to notice a disagreement and does not oblige it to act on that information — a real improvement over having nothing, and not the guarantee the word “checksum” suggests. ELF and Mach-O do not even have that much, and the language's promise that the definitions are identical is what makes the gap tolerable.

Mach-O: one bit, and no section at all

Here is the surprise. ca_macho.o has two sections — __text and __eh_frame. There is no __text member section, no linkonce section, no group. Both functions sit in the ordinary __text:

  __text       seg=__TEXT  addr=0x0000 size=0x0019 off=0x0180 flags=0x80000400
  __eh_frame   seg=__TEXT  addr=0x0020 size=0x0068 off=0x01a0 flags=0x6800000b

  and the symbol table:
    [0] __Z13shared_inlinei  n_type=0x0f  sect=1  n_desc=0x0080  value=0x10
                             N_EXT  N_SECT  N_WEAK_DEF
    [1] __Z1ai               n_type=0x0f  sect=1  n_desc=0x0000  value=0x00
                             N_EXT  N_SECT

n_desc = 0x0080 is N_WEAK_DEF, and that is the entire mechanism. The symbol is a weak definition in a normal code section. A Mach-O linker resolving two weak definitions of the same name picks one, exactly as it does for any other weak symbol, and needs to know nothing about sections.

Confirm the absence rather than taking it on trust:

  $ grep -i "linkonce" /usr/lib/llvm-21/include/llvm/BinaryFormat/MachO.h
  (no output)

  $ clang -target x86_64-apple-macosx -O1 -fno-inline -c comdat_a.cpp
  $ llvm-nm-21 ca_macho.o
  0000000000000010 T __Z13shared_inlinei        'T', not 't', and no section
  0000000000000000 T __Z1ai

So the honest comparison is this, and it is the most useful thing in the concept:

answer lives ELF a whole new section type ----------------- ------------------------------------------- where it lives ELF the section header table COFF the section header + the symbol table Mach-O nowhere -- a bit in a symbol cost of the mechanism ELF +1 section per group, +1 symbol COFF +1 section, +1 aux record Mach-O +0 sections, +0 aux records, 1 bit can it detect that two copies disagree? ELF no COFF yes, but the linker need not care Mach-O no

Mach-O is the cheapest answer and it is also the one that makes the compiler work hardest, because the linker cannot throw away a section it was never given — so the compiler must be certain the body is emitted identically everywhere, or must accept that a discarded weak symbol leaves dead bytes behind. The weak-symbol concept measures exactly what that costs, and it is a real cost.

Does It Actually Work?

All of the above is structure. The thing that matters is the behaviour, so here it is — the C++ pair and the counterfactual side by side, same machine, same linker:

  $ ld -r ca_elf.o cb_elf.o -o merged.o
  (silent)

  $ readelf -gW merged.o
  COMDAT group section [1] `.group' [_Z13shared_inlinei] contains 1 sections:
       [    7]   .text._Z13shared_inlinei

  $ llvm-nm-21 merged.o
  0000000000000000 W _Z13shared_inlinei     still WEAK, now in the merged file
  0000000000000000 T _Z1ai
  0000000000000010 T _Z1bi

  ONE copy of the body survived.

And the counterfactual — the same two translation units, the same collision, but with a plain (non-inline) function, so there is no group:

  $ ld -r dup_a.o dup_b.o -o dup_merged.o
  ld.bfd: dup_b.o: in function `collide':
  dup_b.c:(.text+0x0): multiple definition of `collide';
      dup_a.o:dup_a.c:(.text+0x0): first defined here
  exit status 1

So the mechanism is not decorative: it is the difference between a legal C++ program that links and a hard error. Worth pausing on the error message, though, because it names the reason precisely. multiple definition — not duplicate symbol. The linker is not confused about the symbol; it has found two definitions and has been given no information authorising it to discard one. The group is precisely that authorisation, and it is 8 bytes wide.

A Real Example

Now the part that catches people, and the reason this concept is in the course's “Merging and Selection” module rather than somewhere more comfortable. Write the same function four ways in C and see which ones produce a group:

  source                          nm says        group?  two TUs link?
  -------------------------------  -------------  -------  ----------------
  inline int f(int x) ...        U f            NO      n/a: nothing exists
                                    (C99: no
                                     definition)

  static inline int f(int x) ...   t f            NO      n/a: private to
                                    (local text)            one file

  inline int f(int x) ...
  extern int f(int x);              T f            NO      FAILS:
  (the C89 idiom)                                  (global)  multiple definition
                                                                of `f'

  inline int f(int x) ...        T f + WEAK     YES     links silently
  (C++, external linkage)          + SHT_GROUP

Read the third row carefully, because it is the whole point of the concept. In C, the standard's inline/extern inline/static inline rule means that inline alone provides no external definition, so adding an extern declaration is how you get one. And having got one, you have no mechanism to merge it with another translation unit's — because the merge is a C++ language feature and C never got one.

Measured, on the same machine:

  $ ld -r ce_a.o ce_b.o -o ce_merged.o
  ld.bfd: ce_b.o: in function `f_e':
  ce_b.c:(.text+0x0): multiple definition of `f_e'; ...

  $ ld -r ca_elf.o cb_elf.o -o cxx_merged.o
  (silent)

So the rule, stated once: a COMDAT group exists only for a symbol with external linkage that more than one translation unit is allowed to define. C's static inline is private, so there is nothing to merge. C's plain inline provides no definition at all, so there is nothing to own. C's inline + extern does have a definition, but C does not license the duplication, so a collision is the correct answer. C++'s inline has an external definition and licenses the duplication, which is exactly the situation a group exists to resolve.

The first row is the one that costs people an afternoon. Plain C inline produces an undefined symbol — U f — and the error you get is undefined reference to 'f', pointing at a function that is right there in the source, on the line above. Nothing in the object file hints that a definition was expected and omitted; the file faithfully records the C semantics, which is that there is none. The rule to remember: in C, inline without an extern declaration means “do not emit a definition”; in C++ it means “emit one, and let the linker merge the copies.” One keyword, two languages, opposite meanings, and the object file is the only place the difference is visible.

Try It Yourself

$ cd courses/obj/assets/samples
$ readelf -gW ca_elf.o ; readelf -x .group ca_elf.o
$ llvm-readobj-21 --sections ca_coff.o | grep -B4 LNK_COMDAT
$ llvm-nm-21 ca_macho.o ; grep -i linkonce /usr/lib/llvm-21/include/llvm/BinaryFormat/MachO.h

Build the four C variants yourself and read all three formats for each. Write inline, static inline, inline + extern, and the C++ version. For each, run llvm-nm-21 and readelf -gW. Fill in the table above from your own output rather than from this page — and notice that the group appears for exactly one of the four, and that the reason is a linkage question, not an optimisation one.
Prove the absence claims rather than believing them.grep -i linkonce in LLVM's MachO.h returns nothing. Then check what is there: N_WEAK_DEF is 0x80 and N_WEAK_REF is 0x40. Find the bit in ca_macho.o's n_desc yourself and confirm it is 0x80. A claim of absence is only worth as much as the check that established it, and this one takes ten seconds.
Change one character of the inline body and re-measure the checksum. Edit comdat_b.cpp so the two bodies differ, rebuild, and read the COMDAT Checksum from both aux records. They will differ, and the ELF and Mach-O files will show you nothing at all — no group change, no symbol change. Then link the two COFF objects with ld -m i386pe and see whether the linker cares. This is the experiment that separates “has a checksum” from “checks the checksum”.
Test SELECT_NODUPLICATES against SELECT_ANY. Hand-edit the Selection byte in a copy of ca_coff.o from 2 to 1, fix the Checksum field to match whatever the file now contains, and link. Work out what “only discard this if an identical one exists” means for an object that is the only definition in the link — the answer is that the copy must be kept, and the SELECT_ANY version would have let it be thrown away. This is the clearest demonstration in the course that these fields are load-bearing rather than decorative.
Look for the group in a real binary rather than a synthetic one. Link a C++ program against libstdc++ and run readelf -gW on the result. Count the groups, and then check what the linker did with them — the groups survive into an executable, because a fully linked image may still be fed to another linker, and the GRP_COMDAT flag is what tells it they are still discardable.
Answer the “what is this for a linker author” question. You must handle a group, a COMDAT section, and a weak symbol. Write the three-line pseudocode for each and compare. Then decide which of the three needs the most machinery — and check your answer against the table at the end of the REALITY unit, because the intuition that the section-based mechanisms are heavier is right, and knowing why is the point.

Check Your Understanding

Without looking back: a Mach-O object and an ELF object both contain two translation units' copies of the same C++ inline function, and both link silently. The ELF object has an extra section in its section header table that the Mach-O object does not have, and yet the Mach-O one is the smaller and simpler mechanism. What does ELF's extra section buy that Mach-O's symbol bit does not, and what does it cost?

Apply It

You are writing a linker for ELF, COFF and Mach-O. You have implemented symbol resolution: strong beats weak, a strong definition beats a weak one, two strong definitions are an error. Everything works. Then a C++ program fails to link, and the error is multiple definition of '_Z10cxx_inlinei' — between two objects that both came from clang, on the same machine, from the same source pattern. Your symbol resolution is not wrong. What is it missing, and what is the smallest change that makes it correct without regressing the cases that already work?

The general habit: when two definitions of a symbol are allowed to coexist, ask separately which one wins and what happens to the loser. The format records the first explicitly and the second structurally — and the second is where dead code comes from.

Connect

This is the clearest case in the course of an essential idea being reinvented independently, and it is worth connecting to One Source, Three Formats, which proposed the triangulation test: compile the same thing three ways and see what stays constant, because the constants are the essentials and the differences are the accidents. This is that test returning a positive result. The constant is: two objects that each define the same external symbol, where the language has promised the definitions are identical. The accidents are: a group section, a section flag, a symbol bit, three different names for the concept, and a checksum that only one of the three formats bothers with.

The connection to the weak-symbol concept is immediate and load-bearing. ELF implements a COMDAT group by demoting the symbol to STB_WEAK and putting the body in its own section — so the group is weak symbols plus a discard boundary, and Mach-O's N_WEAK_DEF is the same answer with the boundary omitted. The two concepts are one mechanism at two levels, and the reason they are separate concepts is that the boundary has consequences: a weak definition that loses is re-pointed, and a group member that loses is removed. That concept measures the difference, including the fact that GNU ld leaves the losing weak body in the section as unowned dead bytes.

The COFF checksum connects to the PE course and to a security property rather than a correctness one. A COMDAT section that is silently discarded when it should have been kept is a compiler-emitted miscompilation with no diagnostic — and the COFF course reproduced exactly that, with a function returning the wrong constant and no warning. The general lesson is one the formats teach repeatedly: an advisory integrity field is worse than none, because it converts an undetectable failure into a detectable one that the toolchain then chooses to ignore. That is the same shape as the ELF TYPE flag's overflow check, which exists so a linker can fail loudly, and the same shape as the JVM attribute mechanism's design rule of letting a reader skip rather than misread.

The C-versus-C++ finding connects back to COMMON and the ABI Break, and the connection is sharper than it first appears. Both mechanisms exist because C lets a symbol's storage or definition be decided somewhere other than where it is written — COMMON because the definition might be in another object, COMDAT because it might be in this object but also in another. And in both cases the C language specified the rule and the object format had to invent a way to record it. The COMMON story ended in the GCC 9 to 10 break, because the format recorded a decision each side made locally and nothing said the two decisions were incompatible. COMDAT's story ended better, because the C++ standard said the definitions are identical — so the format could record the promise and the linker could act on it. Same problem, opposite outcomes, and the difference was whether the language had done its job first. That is a genuinely useful thing to carry out of a format course and into any design work.

And the archive concept that follows is the same question one level up. A group answers “which of these two definitions survives”; an archive answers “which of these three objects is loaded at all.” Both are selection decisions, both are made by the linker, and both have a failure mode that looks like success: a group that discards the wrong copy, and an archive that pulls in a member nothing needed. The next concept is about the second, and the two make a natural pair because they share the property that the default is conservative and the linker is the only thing that can be smarter — and the format's job is to give it the information to be smarter with.