elf: Support DT_RELR relative relocation format [BZ #27924]

PIE and shared objects usually have many relative relocations. In
2017/2018, SHT_RELR/DT_RELR was proposed on
https://groups.google.com/g/generic-abi/c/bX460iggiKg/m/GxjM0L-PBAAJ
("Proposal for a new section type SHT_RELR") and is a pre-standard. RELR
usually takes 3% or smaller space than R_*_RELATIVE relocations. The
virtual memory size of a mostly statically linked PIE is typically 5~10%
smaller.

---

Notes I will not include in the submitted commit:

Available on https://sourceware.org/git/?p=glibc.git;a=shortlog;h=refs/heads/maskray/relr

"pre-standard": even Solaris folks are happy with the refined generic-abi
proposal. Cary Coutant will apply the change
https://sourceware.org/pipermail/libc-alpha/2021-October/131781.html

This patch is simpler than Chrome OS's glibc patch and makes ELF_DYNAMIC_DO_RELR
available to all ports. I don't think the current glibc implementation
supports ia64 in an ELFCLASS32 container. That said, the style I used is
works with an ELFCLASS32 container for 64-bit machine if ElfW(Addr) is
64-bit.

* Chrome OS folks have carried a local patch since 2018 (latest version:
  https://chromium.googlesource.com/chromiumos/overlays/chromiumos-overlay/+/refs/heads/main/sys-libs/glibc/files/local/glibc-2.32).
  I.e. this feature has been battle tested.
* Android bionic supports 2018 and switched to DT_RELR==36 in 2020.
* The Linux kernel has supported CONFIG_RELR since 2019-08
  (https://git.kernel.org/linus/5cf896fb6be3effd9aea455b22213e27be8bdb1d).
* A musl patch (by me) exists but is not applied:
  https://www.openwall.com/lists/musl/2019/03/06/3
* rtld-elf from FreeBSD 14 will support DT_RELR.

I believe upstream glibc should support DT_RELR to benefit all Linux
distributions. I filed some feature requests to get their attention:

* Gentoo: https://bugs.gentoo.org/818376
* Arch Linux: https://bugs.archlinux.org/task/72433
* Debian https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=996598
* Fedora https://bugzilla.redhat.com/show_bug.cgi?id=2014699

As of linker support (to the best of my knowledge):

* LLD support DT_RELR.
* https://chromium.googlesource.com/chromiumos/overlays/chromiumos-overlay/+/refs/heads/main/sys-devel/binutils/files/
  has a gold patch.
* GNU ld feature request https://sourceware.org/bugzilla/show_bug.cgi?id=27923

Changes from the original patch:

1. Check the linker option, -z pack-relative-relocs, which add a
GLIBC_ABI_DT_RELR symbol version dependency on the shared C library if
it provides a GLIBC_2.XX symbol version.
2. Change make variale to have-dt-relr.
3. Rename tst-relr-no-pie to tst-relr-pie for --disable-default-pie.
4. Use TEST_VERIFY in tst-relr.c.
5. Add the check-tst-relr-pie.out test to check for linker generated
libc.so version dependency on GLIBC_ABI_DT_RELR.
6. Move ELF_DYNAMIC_DO_RELR before ELF_DYNAMIC_DO_REL.

1 files changed, 34 insertions, 0 deletions

diff --git a/elf/dynamic-link.h b/elf/dynamic-link.h
index 25dd7ca4f2..019088f248 100644
--- a/elf/dynamic-link.h
+++ b/elf/dynamic-link.h
@@ -146,12 +146,46 @@ elf_machine_lazy_rel (struct link_map *map, struct r_scope_elem *scope[],
 #  define ELF_DYNAMIC_DO_RELA(map, scope, lazy, skip_ifunc) /* Nothing to do.  */
 # endif
 
+# define ELF_DYNAMIC_DO_RELR(map)					      \
+  do {									      \
+    ElfW(Addr) l_addr = (map)->l_addr, *where = 0;			      \
+    const ElfW(Relr) *r, *end;						      \
+    if ((map)->l_info[DT_RELR] == NULL)					      \
+      break;								      \
+    r = (const ElfW(Relr) *)D_PTR((map), l_info[DT_RELR]);		      \
+    end = (const ElfW(Relr) *)((const char *)r +			      \
+                               (map)->l_info[DT_RELRSZ]->d_un.d_val);	      \
+    for (; r < end; r++)						      \
+      {									      \
+	ElfW(Relr) entry = *r;						      \
+	if ((entry & 1) == 0)						      \
+	  {								      \
+	    where = (ElfW(Addr) *)(l_addr + entry);			      \
+	    *where++ += l_addr;						      \
+	  }								      \
+	else 								      \
+	  {								      \
+	    for (long int i = 0; (entry >>= 1) != 0; i++)		      \
+	      if ((entry & 1) != 0)					      \
+		where[i] += l_addr;					      \
+	    where += CHAR_BIT * sizeof(ElfW(Relr)) - 1;			      \
+	  }								      \
+      }									      \
+  } while (0);
+
 /* This can't just be an inline function because GCC is too dumb
    to inline functions containing inlines themselves.  */
+# ifdef RTLD_BOOTSTRAP
+#  define DO_RTLD_BOOTSTRAP 1
+# else
+#  define DO_RTLD_BOOTSTRAP 0
+# endif
 # define ELF_DYNAMIC_RELOCATE(map, scope, lazy, consider_profile, skip_ifunc) \
   do {									      \
     int edr_lazy = elf_machine_runtime_setup ((map), (scope), (lazy),	      \
 					      (consider_profile));	      \
+    if (((map) != &GL(dl_rtld_map) || DO_RTLD_BOOTSTRAP))		      \
+      ELF_DYNAMIC_DO_RELR (map);					      \
     ELF_DYNAMIC_DO_REL ((map), (scope), edr_lazy, skip_ifunc);		      \
     ELF_DYNAMIC_DO_RELA ((map), (scope), edr_lazy, skip_ifunc);		      \
   } while (0)