linker: add experimental support for SHT_RELR sections.

This change adds experimental support for SHT_RELR sections, proposed
here: https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg

Definitions for the new ELF section type and dynamic array tags, as well
as the encoding used in the new section are all under discussion and are
subject to change. Use with caution!

Bug: None
Test: Built image for marlin, flashed on device, ran arm and
      aarch64 binaries containing '.relr.dyn' sections.

Change-Id: I2953ae932d3c42ae394e71f8fa058013758a1778
diff --git a/libc/include/elf.h b/libc/include/elf.h
index 37450b2..bda11f5 100644
--- a/libc/include/elf.h
+++ b/libc/include/elf.h
@@ -194,6 +194,14 @@
   Elf64_Word vna_next;
 } Elf64_Vernaux;
 
+/* Relocation table entry for relative (in section of type SHT_RELR).  */
+typedef Elf32_Word Elf32_Relr;
+typedef Elf64_Xword Elf64_Relr;
+#define ELF32_R_JUMP(val) ((val) >> 24)
+#define ELF32_R_BITS(val) ((val) & 0xffffff)
+#define ELF64_R_JUMP(val) ((val) >> 56)
+#define ELF64_R_BITS(val) ((val) & 0xffffffffffffff)
+
 /* http://www.sco.com/developers/gabi/latest/ch5.dynamic.html */
 #define DF_ORIGIN     0x00000001
 #define DF_SYMBOLIC   0x00000002
@@ -242,6 +250,13 @@
 #define DT_PREINIT_ARRAY 32
 #define DT_PREINIT_ARRAYSZ 33
 
+/* Experimental support for SHT_RELR sections. For details, see proposal
+   at https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg */
+#define DT_RELR 0x6fffe000
+#define DT_RELRSZ 0x6fffe001
+#define DT_RELRENT 0x6fffe003
+#define DT_RELRCOUNT 0x6fffe005
+
 /* Android compressed rel/rela sections */
 #define DT_ANDROID_REL (DT_LOOS + 2)
 #define DT_ANDROID_RELSZ (DT_LOOS + 3)
@@ -494,6 +509,10 @@
 #define SHT_LOOS 0x60000000
 #define SHT_HIOS 0x6fffffff
 
+/* Experimental support for SHT_RELR sections. For details, see proposal
+   at https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg */
+#define SHT_RELR 0x6fffff00
+
 /* http://www.sco.com/developers/gabi/latest/ch4.symtab.html */
 #define STN_UNDEF 0
 
diff --git a/linker/linker.cpp b/linker/linker.cpp
index 317fdff..abcff2a 100644
--- a/linker/linker.cpp
+++ b/linker/linker.cpp
@@ -2595,6 +2595,35 @@
   return true;
 }
 
+// Process relocations in SHT_RELR section (experimental).
+// See the original proposal for details of the encoding:
+// - https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg
+bool soinfo::relocate_relr() {
+  ElfW(Relr)* begin = relr_;
+  ElfW(Relr)* end = relr_ + relr_count_;
+
+  ElfW(Addr) offset = 0;
+  for (ElfW(Relr)* current = begin; current < end; ++current) {
+    ElfW(Addr) jump = ELFW(R_JUMP)(*current);
+    ElfW(Addr) bits = ELFW(R_BITS)(*current);
+    offset += jump * sizeof(ElfW(Addr));
+    if (jump == 0) {
+      ++current;
+      offset = *current;
+    }
+    ElfW(Addr) r_offset = offset;
+    for (; bits != 0; bits >>= 1) {
+      if ((bits&1) != 0) {
+        ElfW(Addr) reloc = static_cast<ElfW(Addr)>(r_offset + load_bias);
+        ElfW(Addr) addend = *reinterpret_cast<ElfW(Addr)*>(reloc);
+        *reinterpret_cast<ElfW(Addr)*>(reloc) = (load_bias + addend);
+      }
+      r_offset += sizeof(ElfW(Addr));
+    }
+  }
+  return true;
+}
+
 #if !defined(__mips__)
 #if defined(USE_RELA)
 static ElfW(Addr) get_addend(ElfW(Rela)* rela, ElfW(Addr) reloc_addr __unused) {
@@ -3151,7 +3180,7 @@
         }
         break;
 
-      // ignored (see DT_RELCOUNT comments for details)
+      // Ignored (see DT_RELCOUNT comments for details).
       case DT_RELACOUNT:
         break;
 
@@ -3212,6 +3241,25 @@
         return false;
 
 #endif
+      case DT_RELR:
+        relr_ = reinterpret_cast<ElfW(Relr)*>(load_bias + d->d_un.d_ptr);
+        break;
+
+      case DT_RELRSZ:
+        relr_count_ = d->d_un.d_val / sizeof(ElfW(Relr));
+        break;
+
+      case DT_RELRENT:
+        if (d->d_un.d_val != sizeof(ElfW(Relr))) {
+          DL_ERR("invalid DT_RELRENT: %zd", static_cast<size_t>(d->d_un.d_val));
+          return false;
+        }
+        break;
+
+      // Ignored (see DT_RELCOUNT comments for details).
+      case DT_RELRCOUNT:
+        break;
+
       case DT_INIT:
         init_func_ = reinterpret_cast<linker_ctor_function_t>(load_bias + d->d_un.d_ptr);
         DEBUG("%s constructors (DT_INIT) found at %p", get_realpath(), init_func_);
@@ -3504,16 +3552,23 @@
     }
   }
 
+  if (relr_ != nullptr) {
+    DEBUG("[ relocating %s relr ]", get_realpath());
+    if (!relocate_relr()) {
+      return false;
+    }
+  }
+
 #if defined(USE_RELA)
   if (rela_ != nullptr) {
-    DEBUG("[ relocating %s ]", get_realpath());
+    DEBUG("[ relocating %s rela ]", get_realpath());
     if (!relocate(version_tracker,
             plain_reloc_iterator(rela_, rela_count_), global_group, local_group)) {
       return false;
     }
   }
   if (plt_rela_ != nullptr) {
-    DEBUG("[ relocating %s plt ]", get_realpath());
+    DEBUG("[ relocating %s plt rela ]", get_realpath());
     if (!relocate(version_tracker,
             plain_reloc_iterator(plt_rela_, plt_rela_count_), global_group, local_group)) {
       return false;
@@ -3521,14 +3576,14 @@
   }
 #else
   if (rel_ != nullptr) {
-    DEBUG("[ relocating %s ]", get_realpath());
+    DEBUG("[ relocating %s rel ]", get_realpath());
     if (!relocate(version_tracker,
             plain_reloc_iterator(rel_, rel_count_), global_group, local_group)) {
       return false;
     }
   }
   if (plt_rel_ != nullptr) {
-    DEBUG("[ relocating %s plt ]", get_realpath());
+    DEBUG("[ relocating %s plt rel ]", get_realpath());
     if (!relocate(version_tracker,
             plain_reloc_iterator(plt_rel_, plt_rel_count_), global_group, local_group)) {
       return false;
diff --git a/linker/linker_soinfo.h b/linker/linker_soinfo.h
index 91118b0..cb607a9 100644
--- a/linker/linker_soinfo.h
+++ b/linker/linker_soinfo.h
@@ -62,7 +62,7 @@
                                          // unset.
 #define FLAG_NEW_SOINFO       0x40000000 // new soinfo format
 
-#define SOINFO_VERSION 3
+#define SOINFO_VERSION 4
 
 typedef void (*linker_dtor_function_t)();
 typedef void (*linker_ctor_function_t)(int, char**, char**);
@@ -309,6 +309,7 @@
   template<typename ElfRelIteratorT>
   bool relocate(const VersionTracker& version_tracker, ElfRelIteratorT&& rel_iterator,
                 const soinfo_list_t& global_group, const soinfo_list_t& local_group);
+  bool relocate_relr();
 
  private:
   // This part of the structure is only available
@@ -365,6 +366,10 @@
   friend soinfo* get_libdl_info(const char* linker_path,
                                 const soinfo& linker_si,
                                 const link_map& linker_map);
+
+  // version >= 4
+  ElfW(Relr)* relr_;
+  size_t relr_count_;
 };
 
 // This function is used by dlvsym() to calculate hash of sym_ver