Elf Dynamic Loader Symbol Lookup Ordering

ELF Dynamic loader symbol lookup ordering

Per my understanding, each executable object has its own "lookup scope":

• The main executable is usually the first object in the "global" lookup scope. This means that symbols defined in the main executable would override those in dependent shared libraries. Shared objects that are added using the LD_PRELOAD facility are added to the global lookup scope, right after the main executable.
• However, if the shared object being loaded uses the DF_SYMBOLIC flag, then symbol references that originate within that object will look for definitions within the object before searching in the global lookup scope.
• Shared objects opened using dlopen() may have their own dependencies. If the RTLD_GLOBAL flag was not set during the call to dlopen(), these dependencies are added to the lookup scope for that object, but do not affect the global lookup scope. If the RTLD_GLOBAL flag was passed to dlopen(), then the shared object (and its dependencies) will be added to the "global" lookup scope, changing the behavior of subsequent symbol lookups.

Ulrich Drepper's guide "How to Write Shared Libraries" is recommended reading on this topic.

Order of symbol lookup in .so dependency graph

Dynamic linking is specified in the ELF specfication. (Note that there are some really old PDFs and Postscript files floating around, but those are generally very outdated.) Symbol lookup is described in section Shared Object Dependencies:

When resolving symbolic references, the dynamic linker examines the symbol tables with a breadth-first search. That is, it first looks at the symbol table of the executable program itself, then at the symbol tables of the DT_NEEDED entries (in order), and then at the second level DT_NEEDED entries, and so on.

(There are various extensions which alter this behavior. The ELF specification itself defines the DF_SYMBOLIC flag.)

This means that your question cannot be answered because your graph does not show the main executable, and it is unclear in which order multiple dependencies are searched (top-to-bottom or bottom-to-top).

Whether the lookup order matches the object loading order is implementation-defined because merely loading an object (without executing its initialization functions) is not something that has an observable effect according to the ELF specification.

Initialization order (the order in which initialization functions are executed) is less constrained than symbol lookup order because the order of DT_NEEDED entries does not matter to that. So in theory, it is possible that an implementation loads an initializes d.so before b.so, but the symbols from b.so interpose that of d.so because it comes first in the symbol search order (due to the way the DT_NEEDED entries are ordered).

How does dynamic linker know which library to search for a symbol?

dlopen can't (nor can anything else) change the definition of (global) symbols already present at the time of the call. It can only make available new ones that did not exist before.

The (sloppy) formalization of this is in the specification for dlopen:

Symbols introduced into the process image through calls to dlopen() may be used in relocation activities. Symbols so introduced may duplicate symbols already defined by the program or previous dlopen() operations. To resolve the ambiguities such a situation might present, the resolution of a symbol reference to symbol definition is based on a symbol resolution order. Two such resolution orders are defined: load order and dependency order. Load order establishes an ordering among symbol definitions, such that the first definition loaded (including definitions from the process image file and any dependent executable object files loaded with it) has priority over executable object files added later (by dlopen()). Load ordering is used in relocation processing. Dependency ordering uses a breadth-first order starting with a given executable object file, then all of its dependencies, then any dependents of those, iterating until all dependencies are satisfied. With the exception of the global symbol table handle obtained via a dlopen() operation with a null pointer as the file argument, dependency ordering is used by the dlsym() function. Load ordering is used in dlsym() operations upon the global symbol table handle.

Note that LD_PRELOAD is nonstandard functionality and thus not described here, but on implementations that offer it, LD_PRELOAD acts with load order after the main program but before any shared libraries loaded as dependencies.

Resolving symbols differently in different dynamically loaded objects

Unfortunately there is no way to tweak symbol resolution at per-library level so there is not easy way to achieve this.

If foo is actually implemented in main executable (not just copy-relocated to it) there's nothing you can do because symbols from main executables get the highest priority during resolution (unless you are ok with ultimately hacky runtime-patching of GOT which you aren't).

But if

• foo is implemented in c.so
• and you are desperate enough

you could do the following:

• get return address inside interceptor in a.so (use __builtin_return_address)
• match it against boundaries of b.so (can be obtained from /proc/self/maps)
• depending on result, either do special processing (if caller is in b.so) or forward call to RTLD_NEXT

This of course has obvious limitations e.g. won't work if b.so calls function from yet another d.so which then calls foo but it may be enough in many cases. And yes, I've seen this approach deployed in practice.

Are same symbols in different shared libs looked up starting from the root of the symbol namespace always again?

Thus, when a symbol "foo" is looked up, it seems to me that its lookup is deterministically always bound to the same library or executable at runtime.

This view is way oversimplified. There are many complications, such as presence of DT_SYMBOLIC on the referencing DSO, presence of RTLD_LOCAL when defining DSO is loaded (if it's not linked in directly), and I am sure some other complications I am not remembering at the moment.

Does the dynamic linker exploit this and has a "global symbol table" of sorts

GLIBC loader does not do that.

Or will the symbol always be looked up as if this was its first lookup?

Yes. You can observe this with LD_DEBUG=symbols,bindings ./a.out

Linux ELF 32 Bits Loading

As far as the loader is concerned, sections don't matter -- they're ignored. The loader only looks at segments, and each loadable segment of the executable is loaded at the specified address. The loader will then trigger the dynamic linker (if called for in the executable) to deal with shared objects. Generally the symbol and string tables are not in loadable segments, so the loader ignores them.

So answering your questions in turn:

1) The loader ignores the .init and .fini sections. They will generally be part of some loadable segment and the initial code in the exectuable will run the code in the .init section. The dynamic linker will load the segments of shared objects, and call each entry point which will similarly call the .init code which is in some loaded segment

2) The string/symbol tables are only meaningful for linking, not loading. So the dynamic linker will look at them to resolve any relocations and build jump tables

3) Relocations are mostly use for (static) linking -- executables should never have them and they should be rare in shared objects (which are generally built position-independent so none are needed). Some dynamic linkers can't deal with relocation at all (not sure about the normal linux dynamic linker), so they can't load shared objects that still have relocations

4) .hash sections are just an optimization to speed up the lookup of symbols -- rather than doing a linear search through the symbol table for a specific symbol, a .hash section will take you directly to it. You can safely ignore them and do symbol lookups slowly if you prefer.

edit

A short somewhat vague description of what an ELF loader does:

1. Reads the program header of the ELF file

2. Load all the LOAD segments of the file into memory.

3. If there's an INTERP entry in the program header, recursively load that binary

4. call the entry point of the program.

That's pretty much it (there's some extra cruft about setting up the stack, but that's not clearly part of the loader rather than part of process setup before the loader even runs).

For a statically linked executable, there's no INTERP entry, so that's pretty much it. For a dynamically linked executable, the INTERP section will be something like "/lib/ld-linux.so.2" (a string), so the recursive call to the loader will read that binary file, load all the LOAD sections, notice there's no INTERP section (so no further recursive call), call the entry point, and then return (at which point the loader for the base executable will call the entry point of the base execuatable).

Now the dynamic linker is that second executable (/lib/ld-linux.so.2) that got loaded. What it does is go and read the .dynamic section of the original binary. This will tell it a list of shared objects to load, and table (the .plt section -- program load table) to fill in with addresses of specific symbols in those shared objects. So it will load those shared objects, look up the symbols in them, and stick their addresses into that table. Each shared object will have its own .dynamic section which will be recursively dealt with by the dynamic linker. The symbol lookups look at all symbols in all objects loaded so far, so symbols in the main program may 'override' symbols in other shared objects and have their addresses stuck in the .plt for the shared object. After each shared object and all its dependencies have been loaded, the entry point for the shared object is called. If two shared objects depend on each other (which is legal) both will be loaded and have their .plts resolved and then both entry points will be called, but not in any particularly defined order.

Note that in all the above, relocations never come into it. Where relocations might come into things is when a shared object can't be loaded at the (virtual) address specified in the shared object (because something else was already loaded at that address). When that happens, the shared object needs to be relocated to load at a different address, which involves looking at all the relocation entries in the object for things that need to be patched to deal with the relocated addresses.

Finally, a symbol reference only has an offset in the symbol table of the object containing the reference -- the linker needs to look up the symbol name (string) in the symbol tables of all the other objects that have been loaded to figure out what it refers to. Every object has its own symbol table, and those tables aren't combined other than logically. A symbol lookup goes through all the objects that have been loaded so far, lookup up that symbol in each symbol table in turn, looking for an entry that defines the symbol.

---

Related Topics