Load libraries in breadth-first order

  This patch fixes the problem with symbol search order
  for dlsym(RTLD_DEFAULT/RTLD_NEXT, .) by loading libraries
  and ld_preloads in correct order.

Bug: https://code.google.com/p/android/issues/detail?id=74255
Change-Id: If1ba5c807322409faa914e27ecb675e2c4541f0d
Attempt: 2
diff --git a/tests/Android.mk b/tests/Android.mk
index 3bd4ec0..49efdad 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -114,6 +114,7 @@
     system_properties_test.cpp \
     time_test.cpp \
     uchar_test.cpp \
+    uniqueptr_test.cpp \
     unistd_test.cpp \
     wchar_test.cpp \
 
diff --git a/tests/dlfcn_test.cpp b/tests/dlfcn_test.cpp
index 1613ee8..3568f8f 100644
--- a/tests/dlfcn_test.cpp
+++ b/tests/dlfcn_test.cpp
@@ -158,6 +158,55 @@
   ASSERT_EQ(1, fn());
 }
 
+TEST(dlfcn, dlopen_check_order) {
+  // Here is how the test library and its dt_needed
+  // libraries are arranged
+  //
+  //  libtest_check_order.so
+  //  |
+  //  +-> libtest_check_order_1_left.so
+  //  |   |
+  //  |   +-> libtest_check_order_a.so
+  //  |   |
+  //  |   +-> libtest_check_order_b.so
+  //  |
+  //  +-> libtest_check_order_2_right.so
+  //  |   |
+  //  |   +-> libtest_check_order_d.so
+  //  |       |
+  //  |       +-> libtest_check_order_b.so
+  //  |
+  //  +-> libtest_check_order_3_c.so
+  //
+  //  load order should be (1, 2, 3, a, b, d)
+  //
+  // get_answer() is defined in (2, 3, a, b, c)
+  // get_answer2() is defined in (b, d)
+  void* sym = dlsym(RTLD_DEFAULT, "dlopen_test_get_answer");
+  ASSERT_TRUE(sym == nullptr);
+  void* handle = dlopen("libtest_check_order.so", RTLD_NOW);
+  ASSERT_TRUE(handle != nullptr);
+  typedef int (*fn_t) (void);
+  fn_t fn, fn2;
+  fn = reinterpret_cast<fn_t>(dlsym(RTLD_DEFAULT, "dlopen_test_get_answer"));
+  ASSERT_TRUE(fn != NULL);
+  fn2 = reinterpret_cast<fn_t>(dlsym(RTLD_DEFAULT, "dlopen_test_get_answer2"));
+  ASSERT_TRUE(fn2 != NULL);
+
+  ASSERT_EQ(42, fn());
+  ASSERT_EQ(43, fn2());
+  dlclose(handle);
+}
+
+// libtest_with_dependency_loop.so -> libtest_with_dependency_loop_a.so ->
+// libtest_with_dependency_loop_b.so -> libtest_with_dependency_loop_c.so ->
+// libtest_with_dependency_loop_a.so
+TEST(dlfcn, dlopen_check_loop) {
+  void* handle = dlopen("libtest_with_dependency_loop.so", RTLD_NOW);
+  ASSERT_TRUE(handle == NULL);
+  ASSERT_STREQ("dlopen failed: recursive link to \"libtest_with_dependency_loop_a.so\"", dlerror());
+}
+
 TEST(dlfcn, dlopen_failure) {
   void* self = dlopen("/does/not/exist", RTLD_NOW);
   ASSERT_TRUE(self == NULL);
diff --git a/tests/libs/Android.mk b/tests/libs/Android.mk
index dc38ae5..be6565b 100644
--- a/tests/libs/Android.mk
+++ b/tests/libs/Android.mk
@@ -103,6 +103,160 @@
 include $(TEST_PATH)/Android.build.mk
 
 # -----------------------------------------------------------------------------
+# Libraries used by dlfcn tests to verify correct load order:
+# libtest_check_order_2_right.so
+# -----------------------------------------------------------------------------
+libtest_check_order_2_right_src_files := \
+    dlopen_testlib_answer.cpp
+
+libtest_check_order_2_right_cflags := -D__ANSWER=42
+module := libtest_check_order_2_right
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order_a.so
+# -----------------------------------------------------------------------------
+libtest_check_order_a_src_files := \
+    dlopen_testlib_answer.cpp
+
+libtest_check_order_a_cflags := -D__ANSWER=1
+module := libtest_check_order_a
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order_b.so
+# -----------------------------------------------------------------------------
+libtest_check_order_b_src_files := \
+    dlopen_testlib_answer.cpp
+
+libtest_check_order_b_cflags := -D__ANSWER=2 -D__ANSWER2=43
+module := libtest_check_order_b
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order_c.so
+# -----------------------------------------------------------------------------
+libtest_check_order_3_c_src_files := \
+    dlopen_testlib_answer.cpp
+
+libtest_check_order_3_c_cflags := -D__ANSWER=3
+module := libtest_check_order_3_c
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order_d.so
+# -----------------------------------------------------------------------------
+libtest_check_order_d_src_files := \
+   dlopen_testlib_answer.cpp
+
+libtest_check_order_d_shared_libraries := libtest_check_order_b
+libtest_check_order_d_cflags := -D__ANSWER=4 -D__ANSWER2=4
+module := libtest_check_order_d
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order_left.so
+# -----------------------------------------------------------------------------
+libtest_check_order_1_left_src_files := \
+    empty.cpp
+
+libtest_check_order_1_left_shared_libraries := libtest_check_order_a libtest_check_order_b
+
+module := libtest_check_order_1_left
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_check_order.so
+# -----------------------------------------------------------------------------
+libtest_check_order_src_files := \
+    empty.cpp
+
+libtest_check_order_shared_libraries := libtest_check_order_1_left \
+  libtest_check_order_2_right libtest_check_order_3_c
+
+module := libtest_check_order
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# Library with dependency loop used by dlfcn tests
+#
+# libtest_with_dependency_loop -> a -> b -> c -> a
+# -----------------------------------------------------------------------------
+libtest_with_dependency_loop_src_files := empty.cpp
+
+libtest_with_dependency_loop_shared_libraries := \
+    libtest_with_dependency_loop_a
+
+module := libtest_with_dependency_loop
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_with_dependency_loop_a.so
+# -----------------------------------------------------------------------------
+libtest_with_dependency_loop_a_src_files := empty.cpp
+
+libtest_with_dependency_loop_a_shared_libraries := \
+    libtest_with_dependency_loop_b_tmp
+
+module := libtest_with_dependency_loop_a
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_with_dependency_loop_b.so
+#
+# this is temporary placeholder - will be removed
+# -----------------------------------------------------------------------------
+libtest_with_dependency_loop_b_tmp_src_files := empty.cpp
+libtest_with_dependency_loop_b_tmp_ldflags := -Wl,-soname=libtest_with_dependency_loop_b.so
+
+module := libtest_with_dependency_loop_b_tmp
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_with_dependency_loop_b.so
+# -----------------------------------------------------------------------------
+libtest_with_dependency_loop_b_src_files := empty.cpp
+libtest_with_dependency_loop_b_shared_libraries := libtest_with_dependency_loop_c
+
+module := libtest_with_dependency_loop_b
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
+# libtest_with_dependency_loop_c.so
+# -----------------------------------------------------------------------------
+libtest_with_dependency_loop_c_src_files := empty.cpp
+
+libtest_with_dependency_loop_c_shared_libraries := \
+    libtest_with_dependency_loop_a
+
+module := libtest_with_dependency_loop_c
+build_type := target
+build_target := SHARED_LIBRARY
+include $(TEST_PATH)/Android.build.mk
+
+# -----------------------------------------------------------------------------
 # libtest_relo_check_dt_needed_order.so
 # |
 # +-> libtest_relo_check_dt_needed_order_1.so
diff --git a/tests/libs/dlopen_testlib_answer.cpp b/tests/libs/dlopen_testlib_answer.cpp
new file mode 100644
index 0000000..a4d7504
--- /dev/null
+++ b/tests/libs/dlopen_testlib_answer.cpp
@@ -0,0 +1,25 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+extern "C" int dlopen_test_get_answer() {
+  return __ANSWER;
+}
+
+#ifdef __ANSWER2
+extern "C" int dlopen_test_get_answer2() {
+  return __ANSWER2;
+}
+#endif
diff --git a/tests/uniqueptr_test.cpp b/tests/uniqueptr_test.cpp
new file mode 100644
index 0000000..4b6608a
--- /dev/null
+++ b/tests/uniqueptr_test.cpp
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2014 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.
+ */
+
+#include <gtest/gtest.h>
+
+#include <private/UniquePtr.h>
+
+static int cCount = 0;
+struct C {
+  C() { ++cCount; }
+  ~C() { --cCount; }
+};
+
+static bool freed = false;
+struct Freer {
+  void operator() (int* p) {
+    ASSERT_EQ(123, *p);
+    free(p);
+    freed = true;
+  }
+};
+
+TEST(UniquePtr, smoke) {
+  //
+  // UniquePtr<T> tests...
+  //
+
+  // Can we free a single object?
+  {
+    UniquePtr<C> c(new C);
+    ASSERT_TRUE(cCount == 1);
+  }
+  ASSERT_TRUE(cCount == 0);
+  // Does release work?
+  C* rawC;
+  {
+      UniquePtr<C> c(new C);
+      ASSERT_TRUE(cCount == 1);
+      rawC = c.release();
+  }
+  ASSERT_TRUE(cCount == 1);
+  delete rawC;
+  // Does reset work?
+  {
+      UniquePtr<C> c(new C);
+      ASSERT_TRUE(cCount == 1);
+      c.reset(new C);
+      ASSERT_TRUE(cCount == 1);
+  }
+  ASSERT_TRUE(cCount == 0);
+
+  //
+  // UniquePtr<T[]> tests...
+  //
+
+  // Can we free an array?
+  {
+      UniquePtr<C[]> cs(new C[4]);
+      ASSERT_TRUE(cCount == 4);
+  }
+  ASSERT_TRUE(cCount == 0);
+  // Does release work?
+  {
+      UniquePtr<C[]> c(new C[4]);
+      ASSERT_TRUE(cCount == 4);
+      rawC = c.release();
+  }
+  ASSERT_TRUE(cCount == 4);
+  delete[] rawC;
+  // Does reset work?
+  {
+      UniquePtr<C[]> c(new C[4]);
+      ASSERT_TRUE(cCount == 4);
+      c.reset(new C[2]);
+      ASSERT_TRUE(cCount == 2);
+  }
+  ASSERT_TRUE(cCount == 0);
+
+  //
+  // Custom deleter tests...
+  //
+  ASSERT_TRUE(!freed);
+  {
+      UniquePtr<int, Freer> i(reinterpret_cast<int*>(malloc(sizeof(int))));
+      *i = 123;
+  }
+  ASSERT_TRUE(freed);
+}