linker: Handle libraries with disjoint mappings correctly.

It's possible and sometimes beneficial for a library to have disjoint mappings
and for other libraries to be mapped into the gap between the mappings using
ANDROID_DLEXT_RESERVED_ADDRESS. See for example the proposal for partitioning
in lld [1].

Because the find_containing_library and do_dl_unwind_find_exidx functions use
a simple bounds check to figure out whether a pointer belongs to a library
they will, given a pointer into a library mapped into the gap of a library
with disjoint mappings, return a pointer to the soinfo for the outer library
instead of the inner one, because the outer library will appear before the
inner one in the solist.

From a user perspective this means that we won't be able to unwind the inner
library's frames on 32-bit ARM with libgcc, dladdr() will return information
for the outer library given a pointer to the inner one and dlopen() et al will
use the linker namespace of the outer library when called from the inner one
(although they will usually be the same).

To make this work correctly, make it so that once find_containing_library
sees a match for the bounds check, it examines the library's PT_LOADs to
make sure that there is a mapping for the given address. This is similar
to how libgcc and libunwind_llvm already handle finding the PT_GNU_EH_FRAME
on non-ARM32 platforms [2,3]. do_dl_unwind_find_exidx is reimplemented in
terms of find_containing_library.

[1] http://lists.llvm.org/pipermail/llvm-dev/2019-February/130583.html
[2] https://github.com/llvm/llvm-project/blob/e739ac0e255597d818c907223034ddf3bc18a593/libunwind/src/AddressSpace.hpp#L523
[3] https://android.googlesource.com/toolchain/gcc/+/master/gcc-4.9/libgcc/unwind-dw2-fde-dip.c#294

Test: /data/nativetest{,64}/bionic-unit-tests/bionic-unit-tests on walleye-userdebug
Change-Id: I368fe6ad3c470b3dff80f7d9b04253566d63a7d2
diff --git a/tests/dlfcn_test.cpp b/tests/dlfcn_test.cpp
index 8a3b6f3..ff5b1a9 100644
--- a/tests/dlfcn_test.cpp
+++ b/tests/dlfcn_test.cpp
@@ -49,6 +49,12 @@
 #pragma clang diagnostic pop
 #endif //  defined(__ANDROID__) && (defined(__arm__) || defined(__i386__))
 
+// Declared manually because the macro definitions in <elf.h> conflict with LLVM headers.
+#ifdef __arm__
+typedef uintptr_t _Unwind_Ptr;
+extern "C" _Unwind_Ptr dl_unwind_find_exidx(_Unwind_Ptr, int*);
+#endif
+
 #define ASSERT_SUBSTR(needle, haystack) \
     ASSERT_PRED_FORMAT2(::testing::IsSubstring, needle, haystack)
 
@@ -1732,4 +1738,28 @@
   ASSERT_TRUE(handle != nullptr) << dlerror();
 }
 
+TEST(dlfcn, segment_gap) {
+  void* handle = dlopen("libsegment_gap_outer.so", RTLD_NOW);
+  ASSERT_TRUE(handle != nullptr) << dlerror();
+
+  auto get_inner = reinterpret_cast<void* (*)()>(dlsym(handle, "get_inner"));
+  void* inner = get_inner();
+  (void)inner;
+
+#if __arm__
+  int count;
+  _Unwind_Ptr outer_exidx = dl_unwind_find_exidx(reinterpret_cast<_Unwind_Ptr>(get_inner), &count);
+  _Unwind_Ptr inner_exidx = dl_unwind_find_exidx(reinterpret_cast<_Unwind_Ptr>(inner), &count);
+  EXPECT_NE(0u, outer_exidx);
+  EXPECT_NE(0u, inner_exidx);
+  EXPECT_NE(inner_exidx, outer_exidx);
+#endif
+
+  Dl_info info;
+  int rc = dladdr(inner, &info);
+  ASSERT_NE(rc, 0);
+
+  EXPECT_NE(nullptr, strstr(info.dli_fname, "libsegment_gap_inner.so"));
+}
+
 #endif