rtld: Support DT_RELR relative relocation format

PIE and shared objects usually have many relative relocations. In
2017/2018, a compact relative relocation format 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.

ld.lld --pack-dyn-relocs=relr emits RELR relocations. DT_RELR has been
adopted by Android bionic, Linux kernel's arm64 port, Chrome OS (patched
glibc).

This patch adds DT_RELR support to FreeBSD rtld-elf.

MFC after:	1 week
Differential Revision:	https://reviews.freebsd.org/D32524

2 files changed, 38 insertions, 0 deletions

diff --git a/libexec/rtld-elf/rtld.c b/libexec/rtld-elf/rtld.c
index 6c304f98253a..d598bb044f8e 100644
--- a/libexec/rtld-elf/rtld.c
+++ b/libexec/rtld-elf/rtld.c
@@ -1255,6 +1255,18 @@ digest_dynamic1(Obj_Entry *obj, int early, const Elf_Dyn **dyn_rpath,
 	    assert(dynp->d_un.d_val == sizeof(Elf_Rela));
 	    break;
 
+	case DT_RELR:
+	    obj->relr = (const Elf_Relr *)(obj->relocbase + dynp->d_un.d_ptr);
+	    break;
+
+	case DT_RELRSZ:
+	    obj->relrsize = dynp->d_un.d_val;
+	    break;
+
+	case DT_RELRENT:
+	    assert(dynp->d_un.d_val == sizeof(Elf_Relr));
+	    break;
+
 	case DT_PLTREL:
 	    plttype = dynp->d_un.d_val;
 	    assert(dynp->d_un.d_val == DT_REL || plttype == DT_RELA);
@@ -3148,6 +3160,29 @@ reloc_textrel_prot(Obj_Entry *obj, bool before)
 	return (0);
 }
 
+/* Process RELR relative relocations. */
+static void
+reloc_relr(Obj_Entry *obj)
+{
+	const Elf_Relr *relr, *relrlim;
+	Elf_Addr *where;
+
+	relrlim = (const Elf_Relr *)((const char *)obj->relr + obj->relrsize);
+	for (relr = obj->relr; relr < relrlim; relr++) {
+	    Elf_Relr entry = *relr;
+
+	    if ((entry & 1) == 0) {
+		where = (Elf_Addr *)(obj->relocbase + entry);
+		*where++ += (Elf_Addr)obj->relocbase;
+	    } else {
+		for (long i = 0; (entry >>= 1) != 0; i++)
+		    if ((entry & 1) != 0)
+			where[i] += (Elf_Addr)obj->relocbase;
+		where += CHAR_BIT * sizeof(Elf_Relr) - 1;
+	    }
+	}
+}
+
 /*
  * Relocate single object.
  * Returns 0 on success, or -1 on failure.
@@ -3174,6 +3209,7 @@ relocate_object(Obj_Entry *obj, bool bind_now, Obj_Entry *rtldobj,
 	/* Process the non-PLT non-IFUNC relocations. */
 	if (reloc_non_plt(obj, rtldobj, flags, lockstate))
 		return (-1);
+	reloc_relr(obj);
 
 	/* Re-protected the text segment. */
 	if (obj->textrel && reloc_textrel_prot(obj, false) != 0)
diff --git a/libexec/rtld-elf/rtld.h b/libexec/rtld-elf/rtld.h
index 060b83b2cdad..b216e80115bc 100644
--- a/libexec/rtld-elf/rtld.h
+++ b/libexec/rtld-elf/rtld.h
@@ -174,6 +174,8 @@ typedef struct Struct_Obj_Entry {
     unsigned long relsize;	/* Size in bytes of relocation info */
     const Elf_Rela *rela;	/* Relocation entries with addend */
     unsigned long relasize;	/* Size in bytes of addend relocation info */
+    const Elf_Relr *relr;	/* RELR relocation entries */
+    unsigned long relrsize;	/* Size in bytes of RELR relocations */
     const Elf_Rel *pltrel;	/* PLT relocation entries */
     unsigned long pltrelsize;	/* Size in bytes of PLT relocation info */
     const Elf_Rela *pltrela;	/* PLT relocation entries with addend */