Private loader doing depth-first search while native is doing breadth-first.

See title. In certain situations, the private loader may fail to find client library dependencies. Here is an example how to reproduce:

lib_test/randomdir/lib2.c

cat lib2.c 
int lib2func() { return 2; }

lib_test/randomdir/lib3.c

cat lib3.c
int lib3func() { return 3; }

lib_test/lib1.c

cat lib1.c
#define LINUX
#define X86_64
#include "dr_api.h"
DR_EXPORT void dr_init(client_id_t id) {}

Compile and construct dependencies in lib_test/randomdir/:

gcc -o libno3.so -shared lib3.c
gcc -o libno2.so -shared -lno3 -L. lib2.c

Compile client and construct dependencies in lib_test/:

gcc -o libno1.so -shared -Lrandomdir/ -I../dynamorio/build/include -Wl,-rpath=/usr/local/google/home/hgreving/lib_test/randomdir/ -lno2 -lno3 lib1.c

Now run in lib_test/:

../dynamorio/build/bin64/drrun -debug -code_api -c libno1.so -- echo Hello World

Leads to error:

Unable to load client library: libno3.so
        Unable to locate library! Try adding path to LD_LIBRARY_PATH.>

The reason for this is that the private loader follows libno2.so's dependency on libno3.so, but libno2.so is missing an rpath to search for it, see above compile cmds. Both adding randomdir to LD_LIBRARY_PATH or rpath to libno2.so works fine. Also the client lib's path is added to the search path, so it works if libno2 and libno3 are in the same path as libno1.

I have not added an example for the native loader here, but doing the same natively, the libraries are found. Using strace you can tell that the libraries are opened in breadth-first order by the loader, so the native loader sees the rpath in libno1, finding libno3.