Here is a shared library calling a function it does not define. It is not a mistake, not an optimisation, and not a portability hack — it is what shared libraries are:
/* lib.c -> liba.so */
int lib_value(void){ return 1; }
/* mid.c -> libb.so, which NEEDS liba.so */
extern int lib_value(void);
int mid_value(void){ return lib_value() + 10; }
/* main.c -> prog, which needs both */
extern int lib_value(void);
extern int mid_value(void);
int main(void){ printf(" %d %d\n", lib_value(), mid_value()); return 0; }
libb.so has a reference to a symbol it does not contain. The linker cannot resolve it — the answer is in another file. Something has to answer it, and that something is the loader, and the way it decides is the subject of this course.
And here is the thing that makes this teachable: the loader will tell you what it decided.
$ LD_DEBUG=bindings ./prog 2>&1 | grep lib_value binding file ./prog [0] to .../liba.so [0]: normal symbol `lib_value' binding file .../libb.so [0] to .../liba.so [0]: normal symbol `lib_value'
One line per binding, naming the object that wanted the symbol and the object that supplied it. Everything in this course is either that output or a file that output predicts — which means the whole subject can be measured rather than described.
The scope, stated so precisely that you can implement it in an afternoon. Because you will, in the last concept.
That is the entire mechanism of dynamic linking, and it is about fifteen lines of C. The ELF course described the load sequence and the search paths; this is the other half. Search paths answer “where do I look for libfoo.so”. The scope answers “I have found four files that could supply this name — which one?” Those are different questions, and the second one is where all the behaviour lives.
The graph makes it a real structure rather than a list, so the walk order matters:
Build the graph, then watch the loader walk it. First the DT_NEEDED lists, which are the only thing the scope is built from:
$ for f in liba.so libb.so prog; do
printf " %-9s " $f
readelf -dW $f | sed -n 's/.*(NEEDED).*\[\(.*\)\]/[\1]/p' | tr '\n' ' '
echo
done
liba.so [libc.so.6]
libb.so [liba.so] [libc.so.6]
prog [libb.so] [liba.so] [libc.so.6]
Three facts in three lines. Every object needs libc, so libc would be reached three times. liba.so is reached from both prog and libb.so. And the executable lists liba.soexplicitly, which is a consequence of the link line rather than of the dependency graph — and the reason is worth knowing, because it is a very common link failure:
$ clang -o prog main.c -L. -lb -Wl,-rpath,'$ORIGIN' ld.bfd: prog: undefined reference to `lib_value' ld.bfd: ./liba.so: error adding symbols: DSO missing from command line $ clang -o prog main.c -L. -lb -la -Wl,-rpath,'$ORIGIN' # note the -la
--as-needed is on by default on this toolchain, and it drops a library from DT_NEEDED if nothing needed it at the moment the linker saw it. -lb is read before anything has referenced liba's symbols, so it is dropped, and then the reference to lib_value has nowhere to go. The fix is to list -la too. This is not a linker bug; it is an optimisation that changes the file, and the linker scripts course already taught that DT_NEEDED is a list the script does not control.
Now the scope itself, from the artifact rather than from the loader:
$ python3 dynscope.py scope ./prog
The global scope of ./prog
0 depth=0 prog 0 exported
1 depth=1 libb.so 1 exported
2 depth=1 liba.so 1 exported (+1 more)
3 depth=1 libc.so.6 3164 exported (+2 more)
4 depth=2 ld-linux-x86-64.so.2 38 exported
Five objects, not nine. The graph has nine edges and the naive answer would list libc three times and liba twice. The (+1 more) and (+2 more) annotations are the deduplication being visible: liba.so was also needed by libb.so, libc by all three, and neither is a second object. An object appears in the scope once, at the position where it was first reached.
And the loader agrees, which is the check that matters:
$ LD_DEBUG=libs ./prog 2>&1 | grep "find library" find library=libb.so [0]; searching find library=liba.so [0]; searching find library=libc.so.6 [0]; searching find library=ld-linux-x86-64.so.2 [0]; searching
Same four, same order, computed two completely different ways — one from the loader’s own walk and one by reading the files. That agreement is the proof that the scope is not a secret, and it is why the last concept of this course is a two-hundred-line program rather than a page of theory.
Why a list would be wrong, demonstrated with a program that breaks under one. Here is a scope built by naive recursive descent instead of a queue:
WRONG (recursive) RIGHT (a queue) prog prog +-- libb.so +-- libb.so | +-- liba.so <- 3rd | +-- liba.so <- 3rd | +-- libc <- 4th | +-- libc <- 4th +-- liba.so <- 5th, AGAIN +-- liba.so already seen +-- libc <- 6th, AGAIN +-- libc already seen both "work". but the wrong one re-resolves libc.so.6 at position 6, and a symbol defined in libc would then have TWO chances to win depending on which libc you found. the two versions can differ -- and they do, on a machine with more than one libc in the search path.
That is the concrete reason the order is specified rather than left to the implementation. The Relocations course ended with an applier that had a build_layout() function and a comment saying that deciding the layout was “a different program with a much harder problem”. This is that program. The scope is fifteen lines; agreeing with the loader about every symbol in a large program is the hard part, and it is hard precisely because the order has to be right or every answer is wrong in a way nothing reports.
Two details that are easy to get wrong and that the artifact had to be taught by its own bugs:
1. DEDUPLICATE BY PATH, NOT BY NAME.
a DT_NEEDED entry is a NAME. the scope holds PATHS.
comparing the name against the list of paths never matches, and
libc.so.6 enters the scope three times. (dynscope.py did exactly
this on its first run.)
2. THE EXECUTABLE IS NOT IN ITS OWN DT_NEEDED.
there is no DT_NEEDED that says "prog". it is scope[0] because it
is scope[0], and that is the whole reason an executable can
interpose on a library.
And the honest limit of the model, which is that it explains which object wins and not everything about how. Versioned symbols add a second dimension — a name plus a version — and the symbol-resolution course measured the tables that make that work. Undefined-weak symbols have their own rule, and so do IFUNC resolvers, which are a function that decides which function you get. First match in scope order is the rule; the corner cases are refinements of it, not replacements.
$ cd courses/dyn/assets/samples $ ./build_samples.sh 2>&2 | sed -n '/D1/,/D2/p' $ python3 crosscheck.py 2>&2 | sed -n '/\\[1\\]/,/\\[2\\]/p' $ python3 dynscope.py scope ./prog
Then build a scope and check your prediction against the loader:
1. Make libb.so ALSO need libd2.so. Predict the
scope of prog before you run it. Then run
dynscope.py scope and LD_DEBUG=libs and see whether
the prediction was right. (The interesting question
is where liba.so lands, not whether it is present.)
2. Add the same library twice on the link line:
-la ... -la. How many times is it in DT_NEEDED? How
many times in the scope? (--as-needed will collapse
the second, which is its job.)
3. Delete the -la from the link line and get the DSO
error. Then find out WHERE --as-needed is decided:
is it the linker, or the compiler? (It is a linker
default, and you can see it with
-Wl,--no-as-needed.)
4. Now build the scope WITHOUT dynscope.py, using
readelf -dW and a shell loop. You should get the
same list. This is the exercise: if you can do it
with readelf and grep, you understand the scope.
5. Make a library that needs a library that does not
exist. What does dynscope.py print, and what does
the real loader do? (They are NOT the same, and
finding out how they differ is the point.)
Exercise 4 is the one that matters, because it is the difference between reading about a data structure and having one. Twenty lines of shell using readelf -dW will produce the scope, because the scope is not a hidden thing — it is a breadth-first walk of a list you can print. Every course in this collection that has handed you a structure has eventually let you rebuild it; this is the one that takes fifteen lines, and the reason it is worth a course rather than a paragraph is everything else that hangs off it.
Exercise 5 is where the artifact is honest about its limits. dynscope.py prints NOT FOUND and carries on, because a missing transitive dependency is recoverable — you can still resolve what you can. The real loader treats a missing DT_NEEDED as fatal and refuses to start. Being more robust than the thing you are modelling is a design decision, not a bug, and it is the kind of thing you should notice and decide rather than inherit.
This is the first concept, and it is the one the other nine depend on. Every mechanism in dynamic linking is a variation on “search the scope in order and take the first match”. Interposition is the executable being first. -Bsymbolic is removing entries from the search. Versioning is a second key in the same search. Lazy binding is deciding when to run it. dlopen is appending to the list. There is no second idea.
The connection to the ELF course's loader concept is the difference between the two halves of the same subject, and it is worth stating precisely because the earlier course could not. That concept gave the load sequence and the search paths: map the DT_NEEDED libraries, then relocate, then call init functions, then jump to e_entry. It could say which files get loaded and never which one wins, because answering that needs the scope, and the scope needs the deduplicated breadth-first walk — which is this concept. Search paths and the scope are the two halves of “dynamic symbol resolution”, and only the second one has behaviour in it.
The second connection is to the symbol-resolution course's algorithm concept, and it is the sharpest comparison in the collection. That course traced a link-time pass that is demand-driven and left-to-right, and found that the same archive in a different order links or fails to link. The runtime pass is the same shape with one crucial difference: it cannot fail. A linker that cannot find a symbol reports an error; a loader that cannot find one either has it in the scope already (because the executable would not have started) or the reference was never reached. That is why the loader’s search order is specified rather than left free in the way a linker’s mostly is — the search must agree with itself, not merely succeed.
Forward within the module, the two consequences named in the model are the next two concepts, in order. Interposition takes consequence 1 — the executable is first — and shows that it reaches inside libraries, which is the single most surprising measured fact in the course. Breadth-First, and Why It Matters takes consequence 2 and shows that depth-first would produce a different, wrong answer.
And the connection into the artifact, which is the last concept and the reason this course exists. Rebuilding the Scope Yourself is this concept implemented: read DT_NEEDED, walk it breadth-first, read each .dynsym, take the first match, and then check the answer against LD_DEBUG=bindings. A loader is not mysterious; it is a graph walk over files you can print, and the exercise is to do it before believing that.