Re: dlsym(handle) may search in unrelated libraries

[Alexey Izbyshev <izbyshev@ispras.ru>]

On 2/7/19 8:33 AM, Markus Wichmann wrote:
> Let's consider the original code. liba depends on libb, which depends on
> libc. dlopen("liba") returns a handle with libb and libc in the deps,
> but libb->deps == 0. If we now call dlopen("libb"), that does the right
> thing, but only because libb happens to be the last lib in the chain. If
> we'd have loaded libx, liby, and libz before trying libb, it would add
> all the symbols of libs x, y, and z to the libb handle.

Your description almost captures the problem, but is imprecise in the 
last part: "it would add all the symbols of libs x, y, and z to the libb 
handle". load_deps() looks only at DT_NEEDED entries of libraries it 
iterates over, so, for example, if libx depends on both liby and libz, 
then liby and libz (but not libx) would be added to deps of libb.

Moreover, consider the following dependency hierarchy (loaded on 
dlopen("liba")):
liba
   libb
   libd
     libe

In this case, even dlopen("libb") wouldn't do the right thing because 
load_deps() would find libe in DT_NEEDED of libd and add it to deps of libb.
> 
> As you said, order is important. What is the correct order, depth-first
> or breadth-first? I think it should be depth-first, but lack any
> authoritative knowledge on this.
dlsym(handle) uses so-called "dependency order"[1], which is 
breadth-first[2]. This is what musl current does in cases when 
load_deps() is called on a real first load of a library (so that 
everything that's further in the dso list are implicitly loaded 
dependencies of this library).

So with the following dependency tree:
> 
> liba->libb->libc
>      `>libx->liby
> 
> the handle for liba would list libc before libx.
> 
The correct order is what load_deps() does currently: liba libb libx 
libc liby

 > Easiest implementation is probably still going to be recursive. Let's
hope the dependency trees don't get too wild.

I think the easiest way is simply to modify load_deps() to always 
traverse DT_NEEDED in breadth-first order without relying on the dso 
list in the outer loop. load_deps() already effectively maintains a 
queue (deps) that can be used for BFS, so no recursion is needed.
> 
> I'll look into it after work.
> 
Thanks for following this up, Markus!

[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/dlsym.html
[2] http://pubs.opengroup.org/onlinepubs/9699919799/functions/dlopen.html

Alexey