Support DT_RUNPATH in the linker.

Only $ORIGIN substitution is supported, but not linux-specific $LIB
or $PLATFORM.

Change-Id: I5814a016c7c91afba080230a547a863686e7c2b9
diff --git a/linker/linker.cpp b/linker/linker.cpp
index 115de5c..6232ddc 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -97,6 +97,14 @@
 
 __LIBC_HIDDEN__ abort_msg_t* g_abort_message = nullptr; // For debuggerd.
 
+static std::string dirname(const char *path) {
+  const char* last_slash = strrchr(path, '/');
+  if (last_slash == path) return "/";
+  else if (last_slash == nullptr) return ".";
+  else
+    return std::string(path, last_slash - path);
+}
+
 #if STATS
 struct linker_stats_t {
   int count[kRelocMax];
@@ -308,6 +316,38 @@
   parse_path(path, ":", &g_ld_library_paths);
 }
 
+void soinfo::set_dt_runpath(const char* path) {
+  if (!has_min_version(2)) return;
+  parse_path(path, ":", &dt_runpath_);
+
+  std::string origin = dirname(get_realpath());
+  // FIXME: add $LIB and $PLATFORM.
+  std::pair<std::string, std::string> substs[] = {{"ORIGIN", origin}};
+  for (std::string& s : dt_runpath_) {
+    size_t pos = 0;
+    while (pos < s.size()) {
+      pos = s.find("$", pos);
+      if (pos == std::string::npos) break;
+      for (const auto& subst : substs) {
+        const std::string& token = subst.first;
+        const std::string& replacement = subst.second;
+        if (s.substr(pos + 1, token.size()) == token) {
+          s.replace(pos, token.size() + 1, replacement);
+          // -1 to compensate for the ++pos below.
+          pos += replacement.size() - 1;
+          break;
+        } else if (s.substr(pos + 1, token.size() + 2) == "{" + token + "}") {
+          s.replace(pos, token.size() + 3, replacement);
+          pos += replacement.size() - 1;
+          break;
+        }
+      }
+      // Skip $ in case it did not match any of the known substitutions.
+      ++pos;
+    }
+  }
+}
+
 static void parse_LD_PRELOAD(const char* path) {
   // We have historically supported ':' as well as ' ' in LD_PRELOAD.
   parse_path(path, " :", &g_ld_preload_names);
@@ -1161,8 +1201,9 @@
   return -1;
 }
 
-static int open_library_on_ld_library_path(const char* name, off64_t* file_offset) {
-  for (const auto& path_str : g_ld_library_paths) {
+static int open_library_on_paths(const char* name, off64_t* file_offset,
+                                 const std::vector<std::string>& paths) {
+  for (const auto& path_str : paths) {
     char buf[512];
     const char* const path = path_str.c_str();
     if (!format_path(buf, sizeof(buf), path, name)) {
@@ -1189,7 +1230,7 @@
   return -1;
 }
 
-static int open_library(const char* name, off64_t* file_offset) {
+static int open_library(const char* name, soinfo *needed_by, off64_t* file_offset) {
   TRACE("[ opening %s ]", name);
 
   // If the name contains a slash, we should attempt to open it directly and not search the paths.
@@ -1209,7 +1250,10 @@
   }
 
   // Otherwise we try LD_LIBRARY_PATH first, and fall back to the built-in well known paths.
-  int fd = open_library_on_ld_library_path(name, file_offset);
+  int fd = open_library_on_paths(name, file_offset, g_ld_library_paths);
+  if (fd == -1 && needed_by) {
+    fd = open_library_on_paths(name, file_offset, needed_by->get_dt_runpath());
+  }
   if (fd == -1) {
     fd = open_library_on_default_path(name, file_offset);
   }
@@ -1319,8 +1363,8 @@
   return si;
 }
 
-static soinfo* load_library(LoadTaskList& load_tasks,
-                            const char* name, int rtld_flags,
+static soinfo* load_library(LoadTaskList& load_tasks, const char* name,
+                            soinfo* needed_by, int rtld_flags,
                             const android_dlextinfo* extinfo) {
   if (extinfo != nullptr && (extinfo->flags & ANDROID_DLEXT_USE_LIBRARY_FD) != 0) {
     off64_t file_offset = 0;
@@ -1332,7 +1376,7 @@
 
   // Open the file.
   off64_t file_offset;
-  int fd = open_library(name, &file_offset);
+  int fd = open_library(name, needed_by, &file_offset);
   if (fd == -1) {
     DL_ERR("library \"%s\" not found", name);
     return nullptr;
@@ -1358,14 +1402,15 @@
 }
 
 static soinfo* find_library_internal(LoadTaskList& load_tasks, const char* name,
-                                     int rtld_flags, const android_dlextinfo* extinfo) {
+                                     soinfo* needed_by, int rtld_flags,
+                                     const android_dlextinfo* extinfo) {
   soinfo* si = find_loaded_library_by_soname(name);
 
   // Library might still be loaded, the accurate detection
   // of this fact is done by load_library.
   if (si == nullptr) {
     TRACE("[ '%s' has not been found by soname.  Trying harder...]", name);
-    si = load_library(load_tasks, name, rtld_flags, extinfo);
+    si = load_library(load_tasks, name, needed_by, rtld_flags, extinfo);
   }
 
   return si;
@@ -1434,13 +1479,13 @@
   // Step 1: load and pre-link all DT_NEEDED libraries in breadth first order.
   for (LoadTask::unique_ptr task(load_tasks.pop_front());
       task.get() != nullptr; task.reset(load_tasks.pop_front())) {
-    soinfo* si = find_library_internal(load_tasks, task->get_name(), rtld_flags, extinfo);
+    soinfo* needed_by = task->get_needed_by();
+    soinfo* si = find_library_internal(load_tasks, task->get_name(), needed_by,
+                                       rtld_flags, extinfo);
     if (si == nullptr) {
       return false;
     }
 
-    soinfo* needed_by = task->get_needed_by();
-
     if (needed_by != nullptr) {
       needed_by->add_child(si);
     }
@@ -2337,6 +2382,16 @@
   return g_empty_list;
 }
 
+static std::vector<std::string> g_empty_runpath;
+
+const std::vector<std::string>& soinfo::get_dt_runpath() const {
+  if (has_min_version(2)) {
+    return dt_runpath_;
+  }
+
+  return g_empty_runpath;
+}
+
 ElfW(Addr) soinfo::resolve_symbol_address(const ElfW(Sym)* s) const {
   if (ELF_ST_TYPE(s->st_info) == STT_GNU_IFUNC) {
     return call_ifunc_resolver(s->st_value + load_bias);
@@ -2833,6 +2888,10 @@
         verneed_cnt_ = d->d_un.d_val;
         break;
 
+      case DT_RUNPATH:
+        // this is parsed after we have strtab initialized (see below).
+        break;
+
       default:
         if (!relocating_linker) {
           DL_WARN("%s: unused DT entry: type %p arg %p", get_realpath(),
@@ -2866,12 +2925,17 @@
 
   // second pass - parse entries relying on strtab
   for (ElfW(Dyn)* d = dynamic; d->d_tag != DT_NULL; ++d) {
-    if (d->d_tag == DT_SONAME) {
-      soname_ = get_string(d->d_un.d_val);
+    switch (d->d_tag) {
+      case DT_SONAME:
+        soname_ = get_string(d->d_un.d_val);
 #if defined(__work_around_b_19059885__)
-      strlcpy(old_name_, soname_, sizeof(old_name_));
+        strlcpy(old_name_, soname_, sizeof(old_name_));
 #endif
-      break;
+        break;
+      case DT_RUNPATH:
+        // FIXME: $LIB, $PLATFORM unsupported.
+        set_dt_runpath(get_string(d->d_un.d_val));
+        break;
     }
   }
 
diff --git a/linker/linker.h b/linker/linker.h
index 6042cb8..b64f42c 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -336,6 +336,8 @@
 
   uint32_t get_target_sdk_version() const;
 
+  const std::vector<std::string>& get_dt_runpath() const;
+
  private:
   bool elf_lookup(SymbolName& symbol_name, const version_info* vi, uint32_t* symbol_index) const;
   ElfW(Sym)* elf_addr_lookup(const void* addr);
@@ -397,6 +399,9 @@
 
   uint32_t target_sdk_version_;
 
+  void set_dt_runpath(const char *);
+  std::vector<std::string> dt_runpath_;
+
   friend soinfo* get_libdl_info();
 };
 
diff --git a/tests/Android.build.mk b/tests/Android.build.mk
index 5b2b417..6d4faa9 100644
--- a/tests/Android.build.mk
+++ b/tests/Android.build.mk
@@ -48,6 +48,10 @@
     LOCAL_MULTILIB := $($(module)_multilib)
 endif
 
+ifneq ($($(module)_relative_path),)
+    LOCAL_MODULE_RELATIVE_PATH := $($(module)_relative_path)
+endif
+
 LOCAL_CFLAGS := \
     $(common_cflags) \
     $($(module)_cflags) \
diff --git a/tests/dlfcn_test.cpp b/tests/dlfcn_test.cpp
index 3c9b8e3..1c01c62 100644
--- a/tests/dlfcn_test.cpp
+++ b/tests/dlfcn_test.cpp
@@ -1062,3 +1062,17 @@
 extern "C" int version_zero_function2() {
   return 0;
 }
+
+TEST(dlfcn, dt_runpath) {
+  void* handle = dlopen("libtest_dt_runpath_d.so", RTLD_NOW);
+  ASSERT_TRUE(handle != nullptr) << dlerror();
+
+  typedef void *(* dlopen_b_fn)();
+  dlopen_b_fn fn = (dlopen_b_fn)dlsym(handle, "dlopen_b");
+  ASSERT_TRUE(fn != nullptr) << dlerror();
+
+  void *p = fn();
+  ASSERT_TRUE(p == nullptr);
+
+  dlclose(handle);
+}
diff --git a/tests/libs/Android.build.dt_runpath.mk b/tests/libs/Android.build.dt_runpath.mk
new file mode 100644
index 0000000..e9b5265
--- /dev/null
+++ b/tests/libs/Android.build.dt_runpath.mk
@@ -0,0 +1,66 @@
+#
+# Copyright (C) 2012 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+# -----------------------------------------------------------------------------
+# Libraries used by dt_runpath tests.
+# -----------------------------------------------------------------------------
+
+# A leaf library in a non-standard directory.
+libtest_dt_runpath_a_src_files := \
+    empty.cpp
+
+libtest_dt_runpath_a_relative_path := dt_runpath_a
+module := libtest_dt_runpath_a
+include $(LOCAL_PATH)/Android.build.testlib.mk
+
+# Depends on library A with a DT_RUNPATH
+libtest_dt_runpath_b_src_files := \
+    empty.cpp
+
+libtest_dt_runpath_b_shared_libraries := libtest_dt_runpath_a
+libtest_dt_runpath_b_ldflags := -Wl,--rpath,\$${ORIGIN}/../dt_runpath_a
+libtest_dt_runpath_b_relative_path := dt_runpath_b_c_x
+module := libtest_dt_runpath_b
+include $(LOCAL_PATH)/Android.build.testlib.mk
+
+# Depends on library A with an incorrect DT_RUNPATH. This does not matter
+# because B is the first in the D (below) dependency order, and library A
+# is already loaded using the correct DT_RUNPATH from library B.
+libtest_dt_runpath_c_src_files := \
+    empty.cpp
+
+libtest_dt_runpath_c_shared_libraries := libtest_dt_runpath_a
+libtest_dt_runpath_c_ldflags := -Wl,--rpath,\$${ORIGIN}/invalid_dt_runpath
+libtest_dt_runpath_c_relative_path := dt_runpath_b_c_x
+module := libtest_dt_runpath_c
+include $(LOCAL_PATH)/Android.build.testlib.mk
+
+# D depends on B and C with DT_RUNPATH.
+libtest_dt_runpath_d_src_files := \
+    dlopen_b.cpp
+
+libtest_dt_runpath_d_shared_libraries := libtest_dt_runpath_b libtest_dt_runpath_c
+libtest_dt_runpath_d_ldflags := -Wl,--rpath,\$${ORIGIN}/dt_runpath_b_c_x
+module := libtest_dt_runpath_d
+include $(LOCAL_PATH)/Android.build.testlib.mk
+
+# A leaf library in a directory library D has DT_RUNPATH for.
+libtest_dt_runpath_x_src_files := \
+    empty.cpp
+
+libtest_dt_runpath_x_relative_path := dt_runpath_b_c_x
+module := libtest_dt_runpath_x
+include $(LOCAL_PATH)/Android.build.testlib.mk
diff --git a/tests/libs/Android.mk b/tests/libs/Android.mk
index a5ef622..662aeef 100644
--- a/tests/libs/Android.mk
+++ b/tests/libs/Android.mk
@@ -20,6 +20,7 @@
 common_cppflags += -std=gnu++11
 common_additional_dependencies := \
     $(LOCAL_PATH)/Android.mk \
+    $(LOCAL_PATH)/Android.build.dt_runpath.mk \
     $(LOCAL_PATH)/Android.build.dlext_testzip.mk \
     $(LOCAL_PATH)/Android.build.dlopen_2_parents_reloc.mk \
     $(LOCAL_PATH)/Android.build.dlopen_check_order_dlsym.mk \
@@ -180,6 +181,11 @@
 include $(LOCAL_PATH)/Android.build.testlib.mk
 
 # -----------------------------------------------------------------------------
+# Build DT_RUNPATH test helper libraries
+# -----------------------------------------------------------------------------
+include $(LOCAL_PATH)/Android.build.dt_runpath.mk
+
+# -----------------------------------------------------------------------------
 # Build library with two parents
 # -----------------------------------------------------------------------------
 include $(LOCAL_PATH)/Android.build.dlopen_2_parents_reloc.mk
diff --git a/tests/libs/dlopen_b.cpp b/tests/libs/dlopen_b.cpp
new file mode 100644
index 0000000..34f2881
--- /dev/null
+++ b/tests/libs/dlopen_b.cpp
@@ -0,0 +1,7 @@
+#include <dlfcn.h>
+extern "C" void *dlopen_b() {
+  // This is not supposed to succeed. Even though this library has DT_RUNPATH
+  // for libtest_dt_runpath_x.so, it is not taked into account for dlopen.
+  void *handle = dlopen("libtest_dt_runpath_x.so", RTLD_NOW);
+  return handle;
+}