Saturday, 30 June 2012

Interpreting readelf -r, in this case R_X86_64_PC32

Having just put the monster Relocations, Relocations blog-post to bed, at one point I caught myself trying to compute a relocation from the information given by readelf -r. It turns out that it's a bit confusing, and not at all clear how you get from the readelf output to addresses and offsets. So, I've put together the following shared library in the hope that we can walk through that process. The source looks like this:
--------------------------[ libreloc.s ]--------------------------
.section .rodata
        .short 0x00                          # Just some padding between Lhello and the .rodata
        .byte 0x00                           #    section start
        .type Lhello, STT_OBJECT
Lhello:
        .asciz "Hello!"

.section .data
        .short 0x00                          # Just some padding between Lgoodbye and the .data 
        .byte 0x00                           #    section start
        .type Lgoodbye, STT_OBJECT
Lgoodbye:
        .asciz "Goodbye!"

.section .text
        .globl someRelocations
        .type someRelocations, STT_FUNC
someRelocations:
        leaq Lhello(%rip), %rdi              # Store the address of Lhello in RDI
        call puts@PLT                        # Call puts
        leaq Lgoodbye(%rip), %rdi            # Store the address of Lgoobye in RDI
        call puts@PLT                        # Call puts
        ret
-------------------------------8<-------------------------------
So what does it do? Not much, is the answer: it contains two C-strings and a function to print them to stdout. One of the strings is stored in read-only memory, while the other is writable. The output of the someRelocations function is:
Hello!
Goodbye!
Simple stuff. It's worth noting that the symbols Lhello and Lgoodbye are local to the library (in the sense that they aren't declared global) and they are addressed using PC-relative addressing, which doesn't use the indirection of the Global Offset Table.

Let's start with readelf -r then:
$ readelf -rW libreloc.o

Relocation section '.rela.text' at offset 0x420 contains 4 entries:
    Offset             Info             Type               Symbol's Value  Symbol's Name + Addend
0000000000000003  0000000400000002 R_X86_64_PC32          0000000000000000 .rodata - 1
0000000000000008  0000000900000004 R_X86_64_PLT32         0000000000000000 puts - 4
000000000000000f  0000000200000002 R_X86_64_PC32          0000000000000000 .data - 1
0000000000000014  0000000900000004 R_X86_64_PLT32         0000000000000000 puts - 4

This is the symbol table for the libreloc.o object file:
$ readelf -sW libreloc.o

Symbol table '.symtab' contains 10 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 SECTION LOCAL  DEFAULT    1
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    4
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     5: 0000000000000003     0 OBJECT  LOCAL  DEFAULT    5 Lhello
     6: 0000000000000003     0 OBJECT  LOCAL  DEFAULT    3 Lgoodbye
     7: 0000000000000000     0 FUNC    GLOBAL DEFAULT    1 someRelocations
     8: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
     9: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND puts

And finally, here are the sections present in the object file:
$ readelf -SW libreloc.o
There are 9 section headers, starting at offset 0xb0:

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            0000000000000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        0000000000000000 000040 000019 00  AX  0   0  4
  [ 2] .rela.text        RELA            0000000000000000 000420 000060 18      7   1  8
  [ 3] .data             PROGBITS        0000000000000000 00005c 00000c 00  WA  0   0  4
  [ 4] .bss              NOBITS          0000000000000000 000068 000000 00  WA  0   0  4
  [ 5] .rodata           PROGBITS        0000000000000000 000068 00000a 00   A  0   0  1
  [ 6] .shstrtab         STRTAB          0000000000000000 000072 000039 00      0   0  1
  [ 7] .symtab           SYMTAB          0000000000000000 0002f0 0000f0 18      8   7  8
  [ 8] .strtab           STRTAB          0000000000000000 0003e0 00003c 00      0   0  1
Right, so where am I going with this? Well, let's consider the readelf-r:Info column output to start with. The man page for elf describes the following struct for relocations contained in a section of type RELA (e.g. the .rela.text section):
typedef struct {
    Elf64_Addr r_offset;
    uint64_t   r_info;
    int64_t    r_addend;
} Elf64_Rela;
It continues to say that the r_info member encodes "both the symbol table index with respect to which the relocation must be made and the type of relocation to apply" and that these values can be decoded by "applying ELF[32|64]_R_TYPE or ELF[32|64]_R_SYM, respectively, to the entry's r_info member."

ELF64_R_TYPE and ELF64_R_SYM are macros defined in linux/elf.h:
#define ELF64_R_SYM(i)                  ((i) >> 32)
#define ELF64_R_TYPE(i)                 ((i) & 0xffffffff)
This means that bits 32:63, i.e. the most significant uint32_t in r_info, encode the symbol table index.

Or put another way we can say that:
a) the relocation at offset 0x03 from the start of the .text section should reference the address of symbol number 4 (a section), which is itself at offset 0x00 from the start of section 5, the .rodata section, and that an addend of -1 should be applied to it. Similarly,
b) the relocation at offset 0x0f from the start of the .text section should reference the address of symbol number 2 (a section), which is itself at offset 0x00 from the start of section 3, the .data section, and that an addend of -1 should be applied to it.

The output of readelf -r is quite confusing. The first two columns describe two of the three struct members, but omit the addend; it then decodes the type (the ELF64_R_TYPE), the symbol offset and symbol name (the ELF64_R_SYM) before finally printing the addend. IMHO, slightly less than ideal.

We can derive this data ourselves by joining across the three tables above:
(readelf -r:Info[SYM]) -> (readelf -s:Num <==> readelf -s:Ndx) -> (readelf -S:Nr)
Following this for Lhello(%rip), we can substitute the following:
Info[SYM]     Num   Ndx      Nr
        4 -> (4   :   5) -> (5:.rodata)
and for Lgoodbye(%rip):
Info[SYM]     Num   Ndx      Nr
        2 -> (2   :   3) -> (3:.data)

Calculating the relocation target
Let's consider the relocation-type now. In both cases this is 0x02 (the least significant uint32_t of r_info), which according to the ABI (and readelf) is a relocation of type R_X86_64_PC32. You can find this in table 4.10 of the ABIPDF or as an excerpt in my Relocations, Relocations post. Type 2 is described as follows:
Name            Value   Field   Calculation
R_X86_64_PC32   2       word32  S+A-P
Where:
A: Represents the addend used to compute the value of the relocatable field.
P: Represents the place (section offset or address) of the storage unit being relocated (computed using r_offset).
S: Represents the value of the symbol whose index resides in the relocation entry.

Right, so:
S(Lhello) = offset(.rodata)
A(Lhello) = -1
P(Lhello) = offset(.text) + 3
Hence,
S+A-P = offset(.rodata) + (-1) - (offset(.text)+3).

Even though the memory offsets will change as soon as the linker has run, we can still run this relocation-function on the offsets present in the object file to find the eventual target. For the object file, then, we get the following:

S+A-P = offset(.rodata) + (-1) - (offset(.text)+3) = 0x68 - 1 - (0x40 + 3) = 0x24

There's no easy way of validating this number other than to run the function in reverse, since an objdump of the .o file only shows zeroes for the argument to leaq. However, even running it in reverse is tricky, since the location at which the relocation needs to be written is not the same value which will be in %rip when the offset Lhello(%rip) is calculated. The value in %rip is the address of the following instruction. Given that it is a word32 relocation, we need to add 4 to the relocation-site offset to balance the equation:

offset(.text) + reloc_site_offset + sizeof(word32) + 0x24 = 0x40 + 3 + 4 + 0x24 = 0x6b

If we then run hexdump on that offset:
$ hexdump -vCs 0x6b -n 7 libreloc.o
0000006b  48 65 6c 6c 6f 21 00                              |Hello!.|
00000072
we see that we've got the right address. If you remember, we added three bytes of junk-padding at the start of the .rodata (and .data) sections, and we have an addend of -1 because of the instruction-pointer adjustment: since the instruction-pointer will be 4 bytes higher than the relocation site (sizeof(word32)) when the instruction is executed, the relocation has to allow for that. Had we not had three bytes of junk in front of our data we would have had an addend of -4, which explains where the -1 comes from:
sizeof(junk) - sizeof(word32) = 3 - 4 = -1.

Here's a way to visualise what's happening: the relocation describes the relocation site and an offset – and the fact that the offset apparently references "thin air" is only rendered meaningful once the instruction-pointer offest is applied:



What about the virtual memory addresses?
Trying to emulate the linker and calculate the eventual virtual memory offsets is much harder to do as the linker (necessarily) moves the symbols around. However, while we can find out the result of the relocation simply by using objdump on the shared library, let's see how we fare with just a few more pieces of information.

Here's the cut-down output of readelf -S when run against the shared library:
$ readelf -SW libreloc.so 
There are 28 section headers, starting at offset 0x1128:

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
...
  [12] .text             PROGBITS        0000000000000500 000500 000128 00  AX  0   0 16
...
  [14] .rodata           PROGBITS        0000000000000636 000636 00000a 00   A  0   0  1
...
  [22] .data             PROGBITS        0000000000201010 001010 000014 00  WA  0   0  8

If we push some numbers through the relocation function now, we get the following:

S+A-P = offset(.rodata) + (-1) - (offset(.text)+3) = 0x636 -1 -(0x500+3) = 0x132

But wait! The linker adds loads of code to the .text section. What if the someRelocations function is no longer at offset 0x00 from .text? Let's see:
$ readelf -sW libreloc.so
Symbol table '.dynsym' contains 12 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
...
     7: 00000000000005cc     0 FUNC    GLOBAL DEFAULT   12 someRelocations
...
So our initial calculation is wrong; let's try again:

S+A-P = offset(.rodata) + (-1) - (offset(someRelocations)+3) = 0x636 -1 -(0x5cc+3) = 0x66

Shall we check to see if we're right, viewers? Of course we shall:
00000000000005cc <someRelocations>:
 5cc:   48 8d 3d 66 00 00 00    lea    0x66(%rip),%rdi        # 639 <Lhello>
 5d3:   e8 00 ff ff ff          callq  4d8 <puts@plt>
And let's repeat for Lgoodbye(%rip):

S+A-P = offset(.data) + (-1) - (offset(someRelocations)+0x0f) = 0x201010 -1 -(0x5cc+0x0f) = 0x200a34

And let's verify that:
 5d8:   48 8d 3d 3c 0a 20 00    lea    0x200a3c(%rip),%rdi    # 20101b <Lgoodbye>
 5df:   e8 f4 fe ff ff          callq  4d8 <puts@plt>
NUTS. That's not right. What's going on? Well, if we look into the .data section's contents, we can see that the linker has introduced another quad-word of data at the start (which contains its virtual memory offset):
$ hexdump -vCs 0x1010 -n $((16#14)) libreloc.so 
00001010  10 10 20 00 00 00 00 00  00 00 00 47 6f 6f 64 62  |.. ........Goodb|
00001020  79 65 21 00                                       |ye!.            |
00001024
So if we allow for that and add 8 bytes onto 0x200a34, we arrive at the correct offset of 0x200a3c. So, it's clear that it's much harder to try to emulate the linker's calculations since we're not privy to what it's changed. Also bear in mind also that this was an incredibly simple example. Attempting this with larger libraries may be as easy as allowing for an additional 8 bytes at the start of the .data section, but somehow, I doubt it.

No comments:

Post a Comment