`decodeRelaEntries` sometimes returns fewer relocations than `readelf -r`

RyanGlScott commented 1 year ago

While adding a test case for #35, I discovered that elf-edit's decodeRelaEntries function will return different results for PPC32 binaries versus PPC64 binaries. To pick a concrete example, let's look at this simple C program:

int main(void) {
  return 0;
}

I used a musl-based PPC32 cross-compiler (obtained from here) and a PPC64 cross-compiler (obtained from here) to compile this program into a PPC32 binary named ppc32-relocs.elf and a PPC64 binary named ppc64-relocs.elf, respectively. I can use readelf -r to determine the relocations contained in each binary's RELA relocation table:

$ readelf -r ppc32-relocs.elf 

Relocation section '.rela.dyn' at offset 0x2ec contains 17 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
0001fecc  00000016 R_PPC_RELATIVE               5d0
0001fed0  00000016 R_PPC_RELATIVE               54c
0001fed4  00000016 R_PPC_RELATIVE               6d0
0001fed8  00000016 R_PPC_RELATIVE               3e8
0001fedc  00000016 R_PPC_RELATIVE               61c
0001fee0  00000016 R_PPC_RELATIVE               20014
0001fee8  00000016 R_PPC_RELATIVE               20014
0001fef0  00000016 R_PPC_RELATIVE               20014
0001fef8  00000016 R_PPC_RELATIVE               20010
0001ff00  00000016 R_PPC_RELATIVE               734
0001ff08  00000016 R_PPC_RELATIVE               20018
00020010  00000016 R_PPC_RELATIVE               20010
0001fee4  00000501 R_PPC_ADDR32      00000000   _ITM_deregisterTM[...] + 0
0001feec  00000401 R_PPC_ADDR32      00000000   _ITM_registerTMCl[...] + 0
0001fef4  00000201 R_PPC_ADDR32      00000000   __cxa_finalize + 0
0001fefc  00000301 R_PPC_ADDR32      00000000   __deregister_fram[...] + 0
0001ff04  00000701 R_PPC_ADDR32      00000000   __register_frame_info + 0

Relocation section '.rela.plt' at offset 0x3b8 contains 4 entries:
 Offset     Info    Type            Sym.Value  Sym. Name + Addend
00020000  00000215 R_PPC_JMP_SLOT    00000000   __cxa_finalize + 0
00020004  00000315 R_PPC_JMP_SLOT    00000000   __deregister_fram[...] + 0
00020008  00000615 R_PPC_JMP_SLOT    00000000   __libc_start_main + 0
0002000c  00000715 R_PPC_JMP_SLOT    00000000   __register_frame_info + 0

$ readelf -r ppc64-relocs.elf 

Relocation section '.rela.dyn' at offset 0x430 contains 8 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
00000001fd10  000000000016 R_PPC64_RELATIVE                     7f0
00000001fd18  000000000016 R_PPC64_RELATIVE                     760
000000020030  000000000016 R_PPC64_RELATIVE                     20030
00000001ff08  000600000026 R_PPC64_ADDR64    0000000000000000 _ITM_deregisterTM[...] + 0
00000001ff10  000500000026 R_PPC64_ADDR64    0000000000000000 _ITM_registerTMCl[...] + 0
00000001ff18  000300000026 R_PPC64_ADDR64    0000000000000000 __cxa_finalize + 0
00000001ff20  000400000026 R_PPC64_ADDR64    0000000000000000 __deregister_fram[...] + 0
00000001ff28  000800000026 R_PPC64_ADDR64    0000000000000000 __register_frame_info + 0

Relocation section '.rela.plt' at offset 0x4f0 contains 4 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000020010  000300000015 R_PPC64_JMP_SLOT  0000000000000000 __cxa_finalize + 0
000000020018  000400000015 R_PPC64_JMP_SLOT  0000000000000000 __deregister_fram[...] + 0
000000020020  000700000015 R_PPC64_JMP_SLOT  0000000000000000 __libc_start_main + 0
000000020028  000800000015 R_PPC64_JMP_SLOT  0000000000000000 __register_frame_info + 0

Note that each binaries' RELA relocation table is divided into two sections, .rela.dyn and .rela.plt. This will be important later.

If I use elf-edit's decodeRelaEntries function on ppc32-relocs.elf, it will return all of the relocations that readelf -r reports. On the other hand, if I use decodeRelaEntries on ppc64-relocs.elf, it will only report a subset of the relocations:

[ (0x000000000001fd10, R_PPC64_RELATIVE)
, (0x000000000001fd18, R_PPC64_RELATIVE)
, (0x0000000000020030, R_PPC64_RELATIVE)
, (0x000000000001ff08, R_PPC64_ADDR64)
, (0x000000000001ff10, R_PPC64_ADDR64)
, (0x000000000001ff18, R_PPC64_ADDR64)
, (0x000000000001ff20, R_PPC64_ADDR64)
, (0x000000000001ff28, R_PPC64_ADDR64)
]

Notably, all of the R_PPC64_JMP_SLOT relocations (contained exclusively within the .rela.plt section) are absent!

The reason this happens is because each binary prescribes different semantics to the RELASZ tag. For example, let's look out the readelf -d ppc32-relocs.elf tag:

$ readelf -d ppc32-relocs.elf 

Dynamic section at offset 0xff0c contains 25 entries:
  Tag        Type                         Name/Value
 0x00000001 (NEEDED)                     Shared library: [libc.so]
 0x0000000c (INIT)                       0x3e8
 0x0000000d (FINI)                       0x6d0
 0x00000019 (INIT_ARRAY)                 0x1fecc
 0x0000001b (INIT_ARRAYSZ)               4 (bytes)
 0x0000001a (FINI_ARRAY)                 0x1fed0
 0x0000001c (FINI_ARRAYSZ)               4 (bytes)
 0x00000004 (HASH)                       0x150
 0x6ffffef5 (GNU_HASH)                   0x18c
 0x00000005 (STRTAB)                     0x250
 0x00000006 (SYMTAB)                     0x1b0
 0x0000000a (STRSZ)                      154 (bytes)
 0x0000000b (SYMENT)                     16 (bytes)
 0x00000015 (DEBUG)                      0x0
 0x00000003 (PLTGOT)                     0x20000
 0x00000002 (PLTRELSZ)                   48 (bytes)
 0x00000014 (PLTREL)                     RELA
 0x00000017 (JMPREL)                     0x3b8
 0x00000007 (RELA)                       0x2ec
 0x00000008 (RELASZ)                     252 (bytes)
 0x00000009 (RELAENT)                    12 (bytes)
 0x70000000 (PPC_GOT)                    0x1fff4
 0x6ffffffb (FLAGS_1)                    Flags: PIE
 0x6ffffff9 (RELACOUNT)                  12
 0x00000000 (NULL)                       0x0

elf-edit determines what part of the binary corresponds to the RELA relocation table by:

Jumping to the address denoted by RELA (0x2ec), and
Reading a number of bytes equal to RELASZ (252)

In the ppc32-relocs.txt example, this works beautifully. There are 17 entries in the .rela.dyn section and 4 entries in the .rela.plt section for a total of 21 entries overall in the relocation table. RELAENT tells us that each entry is 12 bytes in size, and 21 * 12 = 252, which is exactly the value of RELASZ.

Things get stranger with ppc64-relocs.elf, however:

$ readelf -d ppc64-relocs.elf 

Dynamic section at offset 0xfd20 contains 26 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libc.so]
 0x000000000000000c (INIT)               0x550
 0x000000000000000d (FINI)               0x8c4
 0x0000000000000019 (INIT_ARRAY)         0x1fd10
 0x000000000000001b (INIT_ARRAYSZ)       8 (bytes)
 0x000000000000001a (FINI_ARRAY)         0x1fd18
 0x000000000000001c (FINI_ARRAYSZ)       8 (bytes)
 0x0000000000000004 (HASH)               0x220
 0x000000006ffffef5 (GNU_HASH)           0x260
 0x0000000000000005 (STRTAB)             0x390
 0x0000000000000006 (SYMTAB)             0x288
 0x000000000000000a (STRSZ)              154 (bytes)
 0x000000000000000b (SYMENT)             24 (bytes)
 0x0000000000000015 (DEBUG)              0x0
 0x0000000000000003 (PLTGOT)             0x20000
 0x0000000000000002 (PLTRELSZ)           96 (bytes)
 0x0000000000000014 (PLTREL)             RELA
 0x0000000000000017 (JMPREL)             0x4f0
 0x0000000070000000 (PPC64_GLINK)        0x894
 0x0000000070000003 (PPC64_OPT)          0x0
 0x0000000000000007 (RELA)               0x430
 0x0000000000000008 (RELASZ)             192 (bytes)
 0x0000000000000009 (RELAENT)            24 (bytes)
 0x000000006ffffffb (FLAGS_1)            Flags: PIE
 0x000000006ffffff9 (RELACOUNT)          3
 0x0000000000000000 (NULL)               0x0

Here, we have a RELASZ of 192 bytes. There are 8 entries in the .rela.dyn section and 4 entries in the .rela.plt section for a total of 12 entries overall in the relocation table. Moreover, RELAENT is 24 bytes. But note that 12 * 24 = 288, which exceeds the value of RELASZ! In this particular example, RELASZ only covers the size of the .rela.dyn section, and it does not cover anything in the .rela.plt section, which explains why all of the relocations from the .rela.plt section were omitted. (If you add RELASZ with PLTRELSZ, the latter being the size of the .rela.plt section, then you do in fact get 288 bytes.)

What should we do here? The cross-compilers I am using for PPC32 and PPC64 appear to prescribe different semantics to the RELASZ tag, which makes it questionable whether that is a reliable way to gauge the overall size of the RELA relocation table. Perhaps we should instead count the number of table entries and multiply it by RELAENT?

Ptival commented 1 year ago

Reading the ELF spec for DT_RELA/DT_RELASZ, it seems like the interpretation in the 32-bit binary is the expected one? As in, RELASZ should be the sum of sizes of all entries (possibly from multiple sections) that participate in creating the relocation table.

But indeed, if there is a decent way of knowing the number of entries / the relevant sections, we may be able to fix this on the fly, though that's a bit annoying.

RyanGlScott commented 1 year ago

Some searching (see here) suggests that the range of memory [DT_RELA, DT_RELA + DT_RELASZ) and the range [DT_JMPREL, DT_JMPREL + DT_PLTRELSZ) are allowed to overlap, but that isn't guaranteed to be the case. (DT_RELA/DT_RELASZ correspond to the .rela.dyn section, and DT_JMPREL/DT_PLTRELSZ correspond to the .rela.plt section.)

if there is a decent way of knowing the number of entries / the relevant sections

Annoyingly, I'm not sure how you'd even know the number of entries without reading the contents of the table first, which is the very thing that I'm trying to do. I'd have to take a look at how readelf itself does this. If I had to guess, it is likely using the section boundaries of known .rela sections to compute the actual size of the relocation table, but perhaps there is a more direct way to accomplish this.

RyanGlScott commented 8 months ago

Reading the glibc source code reveals a way forward:

/* 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.  */

That is to say, the implementation of dynRelaBuffer must proceed by cases:

If DT_RELA + DT_RELASZ == DT_JMPREL, then DT_JMPREL comes immediately after DT_RELA. Read the range [DT_RELA, DT_JMPREL + DT_PLTRELASZ).
If DT_RELA + DT_RELASZ == DT_JMPREL + DT_PLTRELASZ, then the ranges overlap. Read the range [DT_RELA, DT_RELA + DT_RELASZ).
Otherwise, the two ranges are completely separate with a gap in between them. Read the ranges [DT_RELA, DT_RELA + DT_RELASZ) and [DT_JMPREL, DT_JMPREL + DT_PLTRELSZ) separately, then combine them.

We would need to do something similar in dynRelBuffer as well (but replace "RELA" with "REL").

We should check to see what the behavior of macaw's pltStubSymbols function is after such a change. Currently, it computes PLT stubs returned by dynRelaEntries (which is defined in terms of dynRelaBuffer) and dynPLTRel (which looks in the range [DT_JMPREL, DT_JMPREL + DT_PLTRELSZ)). The code makes the assumption is that these two regions of memory will be disjoint, but because of the overlapping behavior observed above, this is not necessarily the case.

My guess is that pltStubSymbols will continue to work either way because it is computing a Map, and inserting duplicate relocation addresses into the Map isn't observably different from inserting them without duplicates. Nevertheless, we should avoid needlessly inserting duplicate entries if we can, if for no other reason than efficiency.

RyanGlScott commented 3 months ago

See https://github.com/GaloisInc/macaw/issues/416 for a similar issue on the macaw side.

GaloisInc / elf-edit

`decodeRelaEntries` sometimes returns fewer relocations than `readelf -r` #40