[glibc/maskray/relr] elf: Support DT_RELR relative relocation format [BZ #27924]

[Fangrui Song <maskray@sourceware.org>]

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=57cb96ba7369984df7ef24c1a108af26eb03c9a6

commit 57cb96ba7369984df7ef24c1a108af26eb03c9a6
Author: Fangrui Song <maskray@google.com>
Date:   Thu Oct 7 23:56:39 2021 -0700

    elf: Support DT_RELR relative relocation format [BZ #27924]
    
    PIC objects (especially PIE and symbolic 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 welcomed by many parties
    (including Solaris). This packed format can typically save 95% dynamic
    relocation section size for PIE. The vaddr size of a PIE can be 10% smaller.
    
    * Chrome OS folks have carried a local patch for a while (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 DT_RELR.
    * 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
    
    I believe upstream glibc should support DT_RELR to benefit all Linux
    distributions.
    
    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
    
    I wish that GNU ld and gold maintainers can implement the feature as well :)
    
    This patch is simpler than Chrome OS's glibc patch and makes ELF_DYNAMIC_DO_RELR
    available to all ports.
    
    I have adjusted aclocal.m4, otherwise it thinks ld.lld doesn't support
    --pack-dyn-relocs=relr just because ld.lld -v --help doesn't contain the literal
    string.
    
        % ld.lld -v --help | grep pack-dyn-relocs
        --pack-dyn-relocs=[none,android,relr,android+relr]
    
    (`$gnu_ld` is a lie: both gold and ld.lld's "User-Agent:" strings contain
    "GNU" and therefore make gnu_ld=true.)
    
    Tested on aarch64 and x86_64.

Diff:
---
 aclocal.m4             |  19 ++++-----
 configure              | 107 +++++++++++++++++++++++++++++--------------------
 configure.ac           |   4 ++
 elf/Makefile           |   4 ++
 elf/dynamic-link.h     |  28 +++++++++++++
 elf/elf.h              |  13 +++++-
 elf/get-dynamic-info.h |   3 ++
 elf/tst-relr.c         |  20 +++++++++
 8 files changed, 141 insertions(+), 57 deletions(-)

diff --git a/aclocal.m4 b/aclocal.m4
index c195c4db56..65a12df047 100644
--- a/aclocal.m4
+++ b/aclocal.m4
@@ -224,20 +224,17 @@ AC_DEFUN([LIBC_LINKER_FEATURE],
 [AC_MSG_CHECKING([for linker that supports $1])
 libc_linker_feature=no
 if test x"$gnu_ld" = x"yes"; then
-  libc_linker_check=`$LD -v --help 2>/dev/null | grep "\$1"`
-  if test -n "$libc_linker_check"; then
-    cat > conftest.c <<EOF
+  cat > conftest.c <<EOF
 int _start (void) { return 42; }
 EOF
-    if AC_TRY_COMMAND([${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
-				$2 -nostdlib -nostartfiles
-				-fPIC -shared -o conftest.so conftest.c
-				1>&AS_MESSAGE_LOG_FD])
-    then
-      libc_linker_feature=yes
-    fi
-    rm -f conftest*
+  if AC_TRY_COMMAND([${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    $2 -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&AS_MESSAGE_LOG_FD])
+  then
+    libc_linker_feature=yes
   fi
+  rm -f conftest*
 fi
 if test $libc_linker_feature = yes; then
   $3
diff --git a/configure b/configure
index 39d75eb4ed..fdab6a97ef 100755
--- a/configure
+++ b/configure
@@ -5979,25 +5979,22 @@ fi
 $as_echo_n "checking for linker that supports -z execstack... " >&6; }
 libc_linker_feature=no
 if test x"$gnu_ld" = x"yes"; then
-  libc_linker_check=`$LD -v --help 2>/dev/null | grep "\-z execstack"`
-  if test -n "$libc_linker_check"; then
-    cat > conftest.c <<EOF
+  cat > conftest.c <<EOF
 int _start (void) { return 42; }
 EOF
-    if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
-				-Wl,-z,execstack -nostdlib -nostartfiles
-				-fPIC -shared -o conftest.so conftest.c
-				1>&5'
+  if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    -Wl,-z,execstack -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&5'
   { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
   (eval $ac_try) 2>&5
   ac_status=$?
   $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
   test $ac_status = 0; }; }
-    then
-      libc_linker_feature=yes
-    fi
-    rm -f conftest*
+  then
+    libc_linker_feature=yes
   fi
+  rm -f conftest*
 fi
 if test $libc_linker_feature = yes; then
   libc_cv_z_execstack=yes
@@ -6012,25 +6009,22 @@ $as_echo "$libc_linker_feature" >&6; }
 $as_echo_n "checking for linker that supports -z start-stop-gc... " >&6; }
 libc_linker_feature=no
 if test x"$gnu_ld" = x"yes"; then
-  libc_linker_check=`$LD -v --help 2>/dev/null | grep "\-z start-stop-gc"`
-  if test -n "$libc_linker_check"; then
-    cat > conftest.c <<EOF
+  cat > conftest.c <<EOF
 int _start (void) { return 42; }
 EOF
-    if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
-				-Wl,-z,start-stop-gc -nostdlib -nostartfiles
-				-fPIC -shared -o conftest.so conftest.c
-				1>&5'
+  if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    -Wl,-z,start-stop-gc -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&5'
   { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
   (eval $ac_try) 2>&5
   ac_status=$?
   $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
   test $ac_status = 0; }; }
-    then
-      libc_linker_feature=yes
-    fi
-    rm -f conftest*
+  then
+    libc_linker_feature=yes
   fi
+  rm -f conftest*
 fi
 if test $libc_linker_feature = yes; then
   libc_cv_z_start_stop_gc=yes
@@ -6046,25 +6040,22 @@ have-z-start-stop-gc = $libc_cv_z_start_stop_gc"
 $as_echo_n "checking for linker that supports --depaudit... " >&6; }
 libc_linker_feature=no
 if test x"$gnu_ld" = x"yes"; then
-  libc_linker_check=`$LD -v --help 2>/dev/null | grep "\--depaudit"`
-  if test -n "$libc_linker_check"; then
-    cat > conftest.c <<EOF
+  cat > conftest.c <<EOF
 int _start (void) { return 42; }
 EOF
-    if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
-				-Wl,--depaudit,x -nostdlib -nostartfiles
-				-fPIC -shared -o conftest.so conftest.c
-				1>&5'
+  if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    -Wl,--depaudit,x -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&5'
   { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
   (eval $ac_try) 2>&5
   ac_status=$?
   $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
   test $ac_status = 0; }; }
-    then
-      libc_linker_feature=yes
-    fi
-    rm -f conftest*
+  then
+    libc_linker_feature=yes
   fi
+  rm -f conftest*
 fi
 if test $libc_linker_feature = yes; then
   libc_cv_depaudit=yes
@@ -6076,29 +6067,57 @@ $as_echo "$libc_linker_feature" >&6; }
 config_vars="$config_vars
 have-depaudit = $libc_cv_depaudit"
 
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for linker that supports --pack-dyn-relocs=relr" >&5
+$as_echo_n "checking for linker that supports --pack-dyn-relocs=relr... " >&6; }
+libc_linker_feature=no
+if test x"$gnu_ld" = x"yes"; then
+  cat > conftest.c <<EOF
+int _start (void) { return 42; }
+EOF
+  if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    -Wl,--pack-dyn-relocs=relr -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&5'
+  { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
+  (eval $ac_try) 2>&5
+  ac_status=$?
+  $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
+  test $ac_status = 0; }; }
+  then
+    libc_linker_feature=yes
+  fi
+  rm -f conftest*
+fi
+if test $libc_linker_feature = yes; then
+  libc_cv_relr=yes
+else
+  libc_cv_relr=no
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $libc_linker_feature" >&5
+$as_echo "$libc_linker_feature" >&6; }
+config_vars="$config_vars
+have-relr = $libc_cv_relr"
+
 { $as_echo "$as_me:${as_lineno-$LINENO}: checking for linker that supports --no-dynamic-linker" >&5
 $as_echo_n "checking for linker that supports --no-dynamic-linker... " >&6; }
 libc_linker_feature=no
 if test x"$gnu_ld" = x"yes"; then
-  libc_linker_check=`$LD -v --help 2>/dev/null | grep "\--no-dynamic-linker"`
-  if test -n "$libc_linker_check"; then
-    cat > conftest.c <<EOF
+  cat > conftest.c <<EOF
 int _start (void) { return 42; }
 EOF
-    if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
-				-Wl,--no-dynamic-linker -nostdlib -nostartfiles
-				-fPIC -shared -o conftest.so conftest.c
-				1>&5'
+  if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS $LDFLAGS $no_ssp
+		    -Wl,--no-dynamic-linker -nostdlib -nostartfiles
+		    -fPIC -shared -o conftest.so conftest.c
+		    1>&5'
   { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
   (eval $ac_try) 2>&5
   ac_status=$?
   $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
   test $ac_status = 0; }; }
-    then
-      libc_linker_feature=yes
-    fi
-    rm -f conftest*
+  then
+    libc_linker_feature=yes
   fi
+  rm -f conftest*
 fi
 if test $libc_linker_feature = yes; then
   libc_cv_no_dynamic_linker=yes
diff --git a/configure.ac b/configure.ac
index 00f49f09f7..96110f9d7d 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1354,6 +1354,10 @@ LIBC_LINKER_FEATURE([--depaudit], [-Wl,--depaudit,x],
 		    [libc_cv_depaudit=yes], [libc_cv_depaudit=no])
 LIBC_CONFIG_VAR([have-depaudit], [$libc_cv_depaudit])
 
+LIBC_LINKER_FEATURE([--pack-dyn-relocs=relr], [-Wl,--pack-dyn-relocs=relr],
+		    [libc_cv_relr=yes], [libc_cv_relr=no])
+LIBC_CONFIG_VAR([have-relr], [$libc_cv_relr])
+
 LIBC_LINKER_FEATURE([--no-dynamic-linker],
 		    [-Wl,--no-dynamic-linker],
 		    [libc_cv_no_dynamic_linker=yes],
diff --git a/elf/Makefile b/elf/Makefile
index 26986c0692..e7c3f3404b 100644
--- a/elf/Makefile
+++ b/elf/Makefile
@@ -241,6 +241,10 @@ endif
 ifeq ($(have-depaudit),yes)
 tests += tst-audit14 tst-audit15 tst-audit16
 endif
+ifeq ($(have-relr),yes)
+tests += tst-relr
+LDFLAGS-tst-relr += -Wl,--pack-dyn-relocs=relr
+endif
 endif
 tests += $(tests-execstack-$(have-z-execstack))
 ifeq ($(run-built-tests),yes)
diff --git a/elf/dynamic-link.h b/elf/dynamic-link.h
index 7cc3021164..ce8d628ca1 100644
--- a/elf/dynamic-link.h
+++ b/elf/dynamic-link.h
@@ -192,6 +192,33 @@ 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, base = 0, start;			      \
+    const ElfW(Relr) *r = 0, *end = 0;					      \
+    if (!(map)->l_info[DT_RELR])					      \
+      break;								      \
+    start = D_PTR((map), l_info[DT_RELR]);				      \
+    r = (const ElfW(Relr) *)start;					      \
+    end = (const ElfW(Relr) *)(start + (map)->l_info[DT_RELRSZ]->d_un.d_val); \
+    for (; r < end; ++r) {						      \
+      ElfW(Relr) entry = *r;						      \
+      if ((entry & 1) == 0) {						      \
+	*((ElfW(Addr) *)(l_addr + entry)) += l_addr;			      \
+	base = entry + sizeof(ElfW(Addr));				      \
+	continue;							      \
+      }									      \
+      ElfW(Addr) offset = base;						      \
+      do {								      \
+	entry >>= 1;							      \
+	if ((entry & 1) != 0)						      \
+	  *((ElfW(Addr) *)(l_addr + offset)) += l_addr;			      \
+	offset += sizeof(ElfW(Addr));					      \
+      } while (entry != 0);						      \
+      base += (8 * sizeof(ElfW(Relr)) - 1) * sizeof(ElfW(Addr));	      \
+    }									      \
+  } while (0);
+
 /* This can't just be an inline function because GCC is too dumb
    to inline functions containing inlines themselves.  */
 # define ELF_DYNAMIC_RELOCATE(map, scope, lazy, consider_profile, skip_ifunc) \
@@ -200,6 +227,7 @@ elf_machine_lazy_rel (struct link_map *map, struct r_scope_elem *scope[],
 					      (consider_profile));	      \
     ELF_DYNAMIC_DO_REL ((map), (scope), edr_lazy, skip_ifunc);		      \
     ELF_DYNAMIC_DO_RELA ((map), (scope), edr_lazy, skip_ifunc);		      \
+    ELF_DYNAMIC_DO_RELR ((map));					      \
   } while (0)
 
 #endif
diff --git a/elf/elf.h b/elf/elf.h
index 50f87baceb..093d69fd07 100644
--- a/elf/elf.h
+++ b/elf/elf.h
@@ -443,7 +443,8 @@ typedef struct
 #define SHT_PREINIT_ARRAY 16		/* Array of pre-constructors */
 #define SHT_GROUP	  17		/* Section group */
 #define SHT_SYMTAB_SHNDX  18		/* Extended section indices */
-#define	SHT_NUM		  19		/* Number of defined types.  */
+#define SHT_RELR	  19            /* RELR relative relocations */
+#define	SHT_NUM		  20		/* Number of defined types.  */
 #define SHT_LOOS	  0x60000000	/* Start OS-specific.  */
 #define SHT_GNU_ATTRIBUTES 0x6ffffff5	/* Object attributes.  */
 #define SHT_GNU_HASH	  0x6ffffff6	/* GNU-style hash table.  */
@@ -662,6 +663,11 @@ typedef struct
   Elf64_Sxword	r_addend;		/* Addend */
 } Elf64_Rela;
 
+/* RELR relocation table entry */
+
+typedef Elf32_Word	Elf32_Relr;
+typedef Elf64_Xword	Elf64_Relr;
+
 /* How to extract and insert information held in the r_info field.  */
 
 #define ELF32_R_SYM(val)		((val) >> 8)
@@ -887,7 +893,10 @@ typedef struct
 #define DT_PREINIT_ARRAY 32		/* Array with addresses of preinit fct*/
 #define DT_PREINIT_ARRAYSZ 33		/* size in bytes of DT_PREINIT_ARRAY */
 #define DT_SYMTAB_SHNDX	34		/* Address of SYMTAB_SHNDX section */
-#define	DT_NUM		35		/* Number used */
+#define DT_RELRSZ	35
+#define DT_RELR		36
+#define DT_RELRENT	37
+#define	DT_NUM		38		/* Number used */
 #define DT_LOOS		0x6000000d	/* Start of OS-specific */
 #define DT_HIOS		0x6ffff000	/* End of OS-specific */
 #define DT_LOPROC	0x70000000	/* Start of processor-specific */
diff --git a/elf/get-dynamic-info.h b/elf/get-dynamic-info.h
index 15c316b38c..08e3aae68b 100644
--- a/elf/get-dynamic-info.h
+++ b/elf/get-dynamic-info.h
@@ -87,6 +87,7 @@ elf_get_dynamic_info (struct link_map *l)
 # if ! ELF_MACHINE_NO_REL
       ADJUST_DYN_INFO (DT_REL);
 # endif
+      ADJUST_DYN_INFO (DT_RELR);
       ADJUST_DYN_INFO (DT_JMPREL);
       ADJUST_DYN_INFO (VERSYMIDX (DT_VERSYM));
       ADJUST_DYN_INFO (ADDRIDX (DT_GNU_HASH));
@@ -111,6 +112,8 @@ elf_get_dynamic_info (struct link_map *l)
   if (info[DT_REL] != NULL)
     assert (info[DT_RELENT]->d_un.d_val == sizeof (ElfW(Rel)));
 #endif
+  if (info[DT_RELR] != NULL)
+    assert (info[DT_RELRENT]->d_un.d_val == sizeof (ElfW(Relr)));
 #ifdef RTLD_BOOTSTRAP
   /* Only the bind now flags are allowed.  */
   assert (info[VERSYMIDX (DT_FLAGS_1)] == NULL
diff --git a/elf/tst-relr.c b/elf/tst-relr.c
new file mode 100644
index 0000000000..20a1409a6c
--- /dev/null
+++ b/elf/tst-relr.c
@@ -0,0 +1,20 @@
+static int o, x;
+void *arr[] = {
+  &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o, &o,
+  0,
+  &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x, &x,
+};
+
+static int
+do_test (void)
+{
+  for (int i = 0; i < 16; i++)
+    if (arr[i] != &o)
+      return 1;
+  for (int i = 17; i < 33; i++)
+    if (arr[i] != &x)
+      return 1;
+  return 0;
+}
+
+#include <support/test-driver.c>