The previous concept said the scope is a breadth-first walk and moved on. That is the right level of confidence for most readers and the wrong one for anyone who writes a linker, because the order is the only thing that makes interposition predictable. So here it is, measured.
$ for f in order libd2.so libb.so liba.so libdeep.so; do
printf " %-11s " $f
readelf -dW $f | sed -n 's/.*(NEEDED).*\[\(.*\)\]/[\1]/p' | tr '\n' ' '
echo
done
order [libd2.so] [libdeep.so] [libb.so] [liba.so] [libc.so.6]
libd2.so [libdeep.so] [libc.so.6]
libb.so [liba.so] [libc.so.6]
liba.so [libc.so.6]
libdeep.so [libc.so.6]
A tree with two branches. order needs libd2.so and libb.so; the first needs libdeep.so, the second needs liba.so; all three need libc. Two plausible orders exist and only one of them is correct.
Both orders, written out, so the difference is visible rather than argued.
The two differ in where liba.so lands relative to libb.so — and that is not a cosmetic difference.liba.so is a dependency oflibb.so. Breadth-first puts it immediately after its parent, which reads as “children come right after the thing that needed them”. Depth-first finishes the whole first branch before starting the second, which spreads a parent and its child across the list with unrelated objects between them.
Why the second is wrong is a single sentence:
And that is the real reason the order is specified rather than left to the implementation. It is not tidiness. It is that the loader must be able to say “everything at depth n is mapped and relocated before I start depth n+1”, and it can only do that if it knows the order.
The loader’s own load order, which is the measurement:
$ LD_DEBUG=libs ./order 2>&1 | sed 's/^ *[0-9]*:\t*//' \
| grep "find library" | sed 's/; searching.*//'
find library=libd2.so [0]
find library=libdeep.so [0]
find library=libb.so [0]
find library=liba.so [0]
find library=libc.so.6 [0]
libdeep.so is loaded second, not fourth. It is a transitive dependency — nothing on the command line or in order’s own DT_NEEDED names it — and breadth-first still pulls it up to position 2 because it is a direct child of libd2.so. A depth-first walk would have loaded liba.so at position 3, because it would have finished libdeep.so’s subtree first.
And the artifact’s answer, computed from the files with no loader involved, is the same list:
$ python3 dynscope.py scope ./order
0 depth=0 order 0 exported
1 depth=1 libd2.so 0 exported
2 depth=1 libdeep.so 1 exported
3 depth=1 libb.so 1 exported
4 depth=1 liba.so 1 exported (+1 more)
5 depth=1 libc.so.6 3164 exported (+4 more)
6 depth=2 ld-linux-x86-64.so.2 38 exported
Same order, and the depth column makes the structure explicit: four objects at depth 1 and one at depth 2. The (+1 more) and (+4 more) are the deduplication, and they are the reason libc.so.6 appears once despite five objects needing it.
Now make the order matter, because an observation that changes nothing is not worth much. liba.so is needed by both order and libb.so, so it is at position 4 — after libb.so. Put a second definition of the same symbol in libb.so and watch which one wins:
$ cat shim.c
int lib_value(void){ return 999; } /* a DIFFERENT lib_value */
$ clang -fPIC -shared -Wl,-rpath,'$ORIGIN' -o libshim.so shim.c -L. -la
$ readelf -dW libshim.so | sed -n 's/.*(NEEDED).*\[\(.*\)\]/ libshim NEEDED \1/p'
libshim NEEDED liba.so
Now the scope of order gains libshim.so, and where it lands relative to liba.so decides the answer. That is the mechanism by which link order in a build system becomes run-time behaviour in a program, and it is why the position of a -l on a command line is not a style question. Two builds, same flags, different order:
$ clang -o order_shim order.c -L. -lshim -ld2 -ldeep -lb -la -Wl,-rpath,'$ORIGIN'
$ clang -o order_shim2 order.c -L. -ld2 -ldeep -lb -lshim -la -Wl,-rpath,'$ORIGIN'
$ for f in order_shim order_shim2; do
printf " %-12s " $f
readelf -dW $f | sed -n 's/.*(NEEDED).*\[\(.*\)\]/[]/p' | grep -v libc | tr '\n' ' '
echo
done
order_shim [libshim.so] [libd2.so] [libdeep.so] [libb.so] [liba.so]
order_shim2 [libd2.so] [libdeep.so] [libb.so] [libshim.so] [liba.so]
DT_NEEDED order follows the link line order, exactly. The first build lists libshim.so first and the second lists it fourth, and in both the shim wins — but look at the margin: three positions in the first build, one in the second. Move -la up one place and liba.so wins instead. Nothing about the program changed; the two definitions of lib_value exchanged places in a list, and that is the entire difference between the two binaries’ behaviour.
And a correction worth making, because the first draft of this page told a tidier and wrong story: it claimed that --as-needed dropped liba.so from the second build’s DT_NEEDED. It did not — liba.so is in both lists. The real mechanism is the direct one above, and it is a better lesson precisely because there is nothing hidden: the order on the command line is the order in the file, and the order in the file is the order in the scope.
The case where getting this wrong produces a bug that is nearly impossible to diagnose, because the program works on the machine that built it.
the situation: two libraries, both exporting
`format_error', and both needed by your program.
order.o -> libnew.so (exports format_error, version 2)
libold.so (exports format_error, version 1)
link with: -lnew -lold
DT_NEEDED becomes [libnew.so] [libold.so]
the scope gets libnew.so at 1 and libold.so at 2
and libnew WINS for every reference, including
references made from inside libold.
now reverse the link order by accident -- a
Makefile change, a dependency reordering, a
-Wl,--as-needed interaction -- and libold wins.
no diagnostic, no warning, and the program now
formats errors the old way forever.
The two programs are the same source, the same objects, and the same compiler flags. The only difference is the order two flags appear in, and it propagates into a behavioural difference that no test of the code would catch — because the code is identical.
This is why the symbol-resolution course spent a concept on link order for archives. That was the link-time version of this: which objects get pulled in. This is the run-time version: which definition of a duplicated symbol wins, and therefore whether the duplication is even a problem. They are the same concern at two different times, and the mechanism is order both times.
And the case where the order is forced on you regardless — a cycle:
liba.so needs libb.so libb.so needs liba.so the graph has a cycle. breadth-first handles it for free: when the walk reaches liba.so the second time, it is already in the list, so it is skipped. the cycle costs nothing and produces no special case in the code. a recursive descent would recurse forever without an explicit "in progress" marker. THAT is the other reason the queue is the right shape: it makes cycle detection a membership test rather than a stack-depth guard.
Deduplication is cycle detection. They look like two requirements and they are the same line of code, which is a satisfying example of a specification that got tighter rather than more complicated.
$ cd courses/dyn/assets/samples $ ./build_samples.sh 2>&2 | sed -n '/D3/,/D4/p' $ python3 crosscheck.py 2>&2 | sed -n '/\\[3\\]/,/\\[4\\]/p' $ python3 dynscope.py scope ./order
Then break the order deliberately and find out what it costs:
1. Reverse the link line for `order`: -lb -ld2
instead of -ld2 -lb. Does the SCOPE change? (The
set does not. The ORDER does.) Which object moved?
2. Write the depth-first version of build_scope() in
dynscope.py -- a recursive descent, about six lines
-- and run both against ./order. They will disagree.
Print both and look at where liba.so lands. (This is
the exercise: you will have written the wrong
algorithm on purpose and seen exactly why it is
wrong.)
3. Build a cycle: make liba.so need libb.so as well.
Does breadth-first survive it? What would a
recursive version do without a marker?
4. Now the one that matters. Take the shim from the
previous section, and link the program both ways.
Find a symbol both libraries export, and use
LD_DEBUG=bindings to prove which one won in each
build. The program text is identical; only the
order differs.
5. Count: for ./order, how many objects does the
graph reach, and how many are in the scope? The
difference is deduplication. Now make the graph
deep rather than wide and watch the number grow.
Exercise 2 is the one worth the twenty minutes, and it is the reason this concept exists rather than being a footnote in the first one. Writing the depth-first version yourself, seeing it disagree, and being able to say why is the difference between having read a specification and having internalised it. Six lines of recursion versus a six-line queue, and the queue is right for a reason that turns out to be two reasons at once: ordering, and cycle detection for free.
Exercise 4 is the practical one, and it is the mechanism behind a class of bug that is genuinely hard: the same source producing different behaviour because the build system changed. If you have ever had a working library stop working after an unrelated dependency bump, this is usually what happened, and now you can name the mechanism and predict which build wins.
This closes module 1. The Global Scope gave the algorithm and Interposition showed its sharpest consequence. This one supplies the one thing that makes both of them predictable rather than surprising: an order that is specified, and that you can compute before running anything. Without it, “the executable wins” is a fact you memorise; with it, you can derive where any symbol ends up.
The connection to the symbol-resolution course’s link-order concept is the strongest in the course, and it is worth naming as a pair rather than two separate lessons. That concept found that MA.a MB.a links while MB.a MA.a fails, and that GNU ld’s archive resolution is a fixed-point iteration rather than a single pass. That is the link-time question — which objects end up in the output. This is the run-time question — which of the objects that got in wins a duplicated symbol. Both are decided by order, both are silent when wrong, and the reason the first is more widely known is only that a link failure is louder than a behavioural difference.
The third connection is to a course you finished long ago, and it is a nice loop. One Relocation, or Two found that AArch64 needs two relocations per reference, 4 bytes apart, and concluded that a tool must process relocations as a set with an ordering constraint rather than as a flat list — because a half-applied pair is still a valid instruction pointing at the wrong place. This concept is the same requirement one level up. A loader that processes its objects in the wrong order produces a fully-applied but wrong set, which is exactly the same class of silent failure, and the specification that prevents it is the one on this page.
Forward into the building module, the order is about which object wins, and the next three concepts are about whether an object is in the running at all. Building a Library covers what a .so is made of. Hiding Things, and the Trap covers deciding what goes in .dynsym, which decides what is a candidate for the search. One Instruction Called -Bsymbolic covers opting out of the search from the other side. All three are about shrinking or pinning the set of candidates; this module was about the order they are searched in.
And the connection that motivates the artifact, which is where the course is going. A scope you can compute means a resolver you can write, and Rebuilding the Scope Yourself writes one in about two hundred lines: read the DT_NEEDED lists, walk them breadth-first, read each .dynsym, take the first match, and then check every answer against LD_DEBUG=bindings. The loader is not a black box at this point, and the last concept proves it by rebuilding it.