[Bug dynamic-link/31541] New: rtld: Support DT_CREL relocation format

[Bug dynamic-link/31541] New: rtld: Support DT_CREL relocation format

[i at maskray dot me]

https://sourceware.org/bugzilla/show_bug.cgi?id=31541

            Bug ID: 31541
           Summary: rtld: Support DT_CREL relocation format
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: dynamic-link
          Assignee: unassigned at sourceware dot org
          Reporter: i at maskray dot me
  Target Milestone: ---

After relative relocations switch to RELR, some programs (especially DSOs)
still contain large non-relative dynamic relocations.
Here is a one-liner to dump the relative relocation and non-relative relocation
sizes for each shared object in a system library directory:

    ruby -e 'Dir.glob("/usr/lib/x86_64-linux-gnu/*.so.*").each{|f| next if
File.symlink?(f) || `file #{f}`!~/shared object/; s=`readelf -Wr #{f}`.lines;
nr=s.count{|x|x=~/R_/&&x !~/_RELATIVE/}*24; r=s.count{|x|x=~/_RELATIVE/}*24;
s=File.size(f); puts "#{f}\t#{s}\t#{r} (#{(r*100.0/s).round(2)}%)\t#{nr}
(#{(nr*100.0/s).round(2)}%)" }'

    file                                                    size    relative   
    non-relative

    /usr/lib/x86_64-linux-gnu/libgnomekbdui.so.8.0.0        100512  312 (0.31%)
    8448 (8.4%)
    /usr/lib/x86_64-linux-gnu/libgrlnet-0.3.so.0.316.0      38912   72 (0.19%) 
    3984 (10.24%)
    /usr/lib/x86_64-linux-gnu/libgrlpls-0.3.so.0.316.0      34816   72 (0.21%) 
    3144 (9.03%)
    /usr/lib/x86_64-linux-gnu/libgrpc++_reflection.so.1.51.1        332416  312
(0.09%)     27048 (8.14%)
    /usr/lib/x86_64-linux-gnu/libgrpcpp_channelz.so.1.51.1  639400  480 (0.08%)
    54936 (8.59%)
    /usr/lib/x86_64-linux-gnu/libgtkmm-3.0.so.1.1.0 6011056 127800 (2.13%) 
1609176 (26.77%)
    /usr/lib/x86_64-linux-gnu/libgtkmm-4.0.so.0.0.0 4933664 149664 (3.03%) 
508680 (10.31%)
    /usr/lib/x86_64-linux-gnu/libical_cxx.so.3.0.17 153760  72 (0.05%)     
13008 (8.46%)
    /usr/lib/x86_64-linux-gnu/libjacknet.so.0.1.0   125120  2544 (2.03%)   
10080 (8.06%)
    /usr/lib/x86_64-linux-gnu/libjxrglue.so.1.2     139536  384 (0.28%)    
13704 (9.82%)
    /usr/lib/x86_64-linux-gnu/libmplex2-2.1.so.0.0.0        126264  336 (0.27%)
    10440 (8.27%)
    /usr/lib/x86_64-linux-gnu/libmu_scm.so.9.0.0    88776   1032 (1.16%)   
8184 (9.22%)
    /usr/lib/x86_64-linux-gnu/libopencsd_c_api.so.1.4.1     67744   96 (0.14%) 
    8640 (12.75%)
    /usr/lib/x86_64-linux-gnu/libpangomm-1.4.so.1.0.30      210952  720 (0.34%)
    20136 (9.55%)
    /usr/lib/x86_64-linux-gnu/libpangomm-2.48.so.1.0.30     251920  3072
(1.22%)    22608 (8.97%)
    /usr/lib/x86_64-linux-gnu/libpeas-gtk-1.0.so.0.3600.0   55296   72 (0.13%) 
    5112 (9.24%)
    /usr/lib/x86_64-linux-gnu/libpolkit-agent-1.so.0.0.0    47016   216 (0.46%)
    4176 (8.88%)
    /usr/lib/x86_64-linux-gnu/libreadline.so.8.2    354536  8496 (2.4%)    
38232 (10.78%)
    /usr/lib/x86_64-linux-gnu/libtinyxml.so.2.6.2   93344   576 (0.62%)    
7536 (8.07%)
    /usr/lib/x86_64-linux-gnu/libwx_gtk3u_aui-3.2.so.0.2.2  682232  31032
(4.55%)   75576 (11.08%)

https://groups.google.com/g/generic-abi/c/yb0rjw56ORw/m/eiBcYxSfAQAJ is a
generic ABI proposal to introduce a new relocation format CREL.
LLVM proposal:
https://discourse.llvm.org/t/rfc-crel-a-compact-relocation-format-for-elf/77600

My LLVM prototype 
I've implemented `ld.lld -z crel` to replace `.rel[a].dyn` and `.rel[a].plt`
with `.crel.dyn` and `.crel.plt`.

    `DT_CREL` | 38 | `d_ptr` | optional | optional

    * `DT_PLTRELSZ`: This element holds the total size, in bytes, of the
relocation entries associated with the procedure linkage table. If an entry of
type `DT_JMPREL` is present and the `DT_PLTREL` entry value is not `DT_CREL`, a
`DT_PLTRELSZ` must accompany it.
    * `DT_PLTREL`: This member specifies the type of relocation entry to which
the procedure linkage table refers. The `d_val` member holds `DT_REL`,
`DT_RELA`, or `DT_CREL`, as appropriate. All relocations in a procedure linkage
table must use the same relocation type.
    * `DT_CREL` - This element is similar to `DT_RELA`, except its table uses
the CREL format. The relocation count can be inferred from the header.

glibc can implement CREL as a replacement for REL/RELA to make aforementioned
DSOs smaller.

If we aim CREL for replacement, we'd need a new dynamic tag (`DT_CREL`) and
ensure no overlap with `DT_JMPREL`.

(For ET_EXEC executables, glibc `csu/libc-start.c` processes IRELATIVE
relocations in the range `[__rela_iplt_start, __rela_iplt_end)` as REL or RELA
(fixed at build-time through `ELF_MACHINE_IRELA`).
My -z crel implementation keeps IRELATIVE relocations in .rel[a].dyn so that
glibc __rel[a]_iplt_start can keep assuming REL[A].)

---

Here is an extremely simple C decoder implementation for ULEB128 and SLEB128.
The clever use of 64/128 is from Stefan O'Rear.
The return type `uint64_t` can be changed to `size_t` when used in a dynamic
loader.

static uint64_t read_leb128(unsigned char **buf, uint64_t sleb_uleb) {
  uint64_t tmp = 0, shift = 0, byte;
  do {
    byte = *(*buf)++;
    tmp |= (byte - 128*(byte >= sleb_uleb)) << shift;
    shift += 7;
  } while (byte >= 128);
  return tmp;
}

uint64_t read_uleb128(unsigned char **buf) { return read_leb128(buf, 128); }
int64_t read_sleb128(unsigned char **buf) { return read_leb128(buf, 64); }

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug dynamic-link/31541] rtld: Support DT_CREL relocation format

[alice at ayaya dot dev]

https://sourceware.org/bugzilla/show_bug.cgi?id=31541

alice <alice at ayaya dot dev> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |alice at ayaya dot dev

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug dynamic-link/31541] rtld: Support DT_CREL relocation format

[i at maskray dot me]

https://sourceware.org/bugzilla/show_bug.cgi?id=31541

--- Comment #1 from Fangrui Song <i at maskray dot me> ---
Stefan O'Rear has developed a musl patch for quantitative assessment
https://0x0.st/XsrV.diff 

> This resolves DT_CREL relocations in dynamically linked executables and
shared libraries, and for non-relative relocations in the dyanmic linker
and static PIE. It does not support DT_CREL for relative relocations in
static PIE and the dynamic linker itself; if DT_CREL is used in static
PIE or the dynamic linker, DT_RELR must also be used.

I've checked lib/libc.so size w/ and w/o CREL support.

* (w/o CREL support) orig: 782064; relr: 780504
* (w/ CREL support) orig: 782736; relr: 781184; relr+crel: 780704

In an x86-64 `-O2` build, CREL support linked with `-z pack-relative-relocs -z
crel` increases the size of `libc.so` by just 200 bytes (0.0256%) compared to a
non-CREL build with `-z pack-relative-relocs`.

---

In glibc, elf/dynamic-link.h ELF_DYNAMIC_RELOCATE has extra complexity because
DT_JMPREL processing is wired into DT_REL/DT_RELA. This is related to the
SPARC:

  /* On some machines, notably SPARC, DT_REL* includes DT_JMPREL in its
     range.  Note that according to the ELF spec, this is completely legal!

     We are guaranteed that we have one of three situations.  Either DT_JMPREL
     comes immediately after DT_REL*, or there is overlap and DT_JMPREL
     consumes precisely the very end of the DT_REL*, or DT_JMPREL and DT_REL*
     are completely separate and there is a gap between them.  */

If this is untangled, CREL support can probably be straightforwardly added.

Since libc.so.6, libpthread.so.0, etc have many non-relative relocations. I
believe RELR+CREL built glibc would be smaller without CREL support :)

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug dynamic-link/31541] rtld: Support DT_CREL relocation format

[sam at gentoo dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=31541

Sam James <sam at gentoo dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sam at gentoo dot org

-- 
You are receiving this mail because:
You are on the CC list for the bug.