Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 7 Feb 2019 11:54:47 -0500
From: Rich Felker <>
Subject: Re: dlsym(handle) may search in unrelated libraries

On Thu, Feb 07, 2019 at 06:33:27AM +0100, Markus Wichmann wrote:
> On Thu, Feb 07, 2019 at 12:23:06AM +0300, Alexey Izbyshev wrote:
> > On 2019-02-06 23:25, Markus Wichmann wrote:
> > > Right you are. It took me a while to understand what the deps array was
> > > even for (since musl's dlclose() doesn't do anything, tracking
> > > dependencies is mostly pointless), but I found it is needed for lazy
> > > relocation processing. So it is necessary for all libs opened by
> > > dlopen() directly to contain a list of all their dependencies. All the
> > > other libs can have an empty list.
> > 
> > Actually, dso->deps is used in dlsym(handle) because it must use the
> > dependency order for symbol search, so it's incorrect to have deps empty for
> > "all the other" libs. Consider the following modification of my previous
> > example:
> > 
> > $ cat bazdep.c
> > int bazdep = 1;
> > extern int bazdepdep;
> > int *p = &bazdepdep;
> > $ cat bazdepdep.c
> > int bazdepdep = 2;
> > $ cat main.c
> > #include <dlfcn.h>
> > #include <stdio.h>
> > 
> > int main(void) {
> >   if (!dlopen("", RTLD_NOW|RTLD_LOCAL))
> >     return 1;
> >   if (!dlopen("", RTLD_NOW|RTLD_LOCAL))
> >     return 1;
> >   void *h = dlopen("", RTLD_NOW|RTLD_LOCAL);
> >   printf("%p\n", dlsym(h, "bar"));
> >   printf("%p\n", dlsym(h, "bazdepdep"));
> > }
> > 
> > The correct output is zero in the first line and some non-zero address in
> > the second. Vanilla musl 1.1.21 prints two non-zero addresses. But with your
> > patch the output is two zeros because dlsym() can't search in dependencies
> > of "" anymore.
> > 
> > Alexey
> OK, so life just got more interesting. I gather the deps handling was
> always incorrect.
> 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.
> I guess the hope was that this situation never arrises. So how do we fix
> this?
> I think the easiest is probably going to be to patch up load_deps, but
> avoiding recursion is going to be the fun part. My plan is to make
> dso->deps contain all direct and indirect dependencies (which is what
> the code seems to depend on, anyway). This is going to consume more
> memory, but we are talking a few pointers, and we are dealing with
> shared libs, anyway.

Yes, it needs to contain all direct and indirect dependencies, in the
correct order. Right now I think it incorrectly contains a superset of
that. Is that your assessment of the situation too?

> 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.

It's not; it's breadth-first. The definition of "dependency order"
used for dlsym is here:

    "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."

However, a depth-first list of dependencies is also needed to solve
the longstanding ctor-order issue discussed in several past threads
(which I can look up if search doesn't turn them up for you). This is
not a requirement of POSIX (which doesn't even have ctors), but it's a
reasonable expectation we currently get wrong and I think it might be
specified in ELF or some related sysv "standards".

I'm not sure if it makes sense to build both of these lists at the
same time. We currently try to avoid allocating dependency lists for
libraries loaded at startup in order not to allocate and setup data
that might never be used, defering until if/when dlopen is called on
them. I've wanted to do the ctor order walk without allocating a
dependency list, but I don't know a good way to do so. Note that the
code that runs ctors cannot allocate because, at the time it runs,
dlopen has already "committed" the load and can't back it out. It has
to have all resources it needs for the walk precommitted.

Since the beginning of a list of breadth-first dependencies is just
the direct dependencies, if we recorded the number of direct
dependencies for each dso, the breadth-first lists could be used to
perform a depth-first walk to run ctors; this can be made
non-recursive, at the cost of quadratic time but with trivially-tiny
constant factor, by simply restarting at the root of the tree after
each node and finding the deepest not-yet-constructed dso. This
suggests always allocating the breadth-first dependency lists might be
a good idea. That "feels" unfortunate since in principle they can get
large, but it's only going to be large for ridiculous bloatware with
hundreds of libraries, in which case these dependency lists are very
small on a relative scale.

> It would make the most sense, anyway
> (if, from the point of view of a user a library contains all the symbols
> of its dependencies, then those dependencies must also contain all the
> symbols of their dependencies). So with the following dependency tree:
> liba->libb->libc
>     `>libx->liby
> the handle for liba would list libc before libx.
> Easiest implementation is probably still going to be recursive. Let's
> hope the dependency trees don't get too wild.

I don't think recursive can be done safely since you don't have a
small bound on levels of recursion. It could be done with an explicit
stack in allocated storage though, since the operation has to allocate
memory anyway and has to fail if allocation fails.


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.