title: Processing ELF relocations - understanding the relocs, symbols, section data, and how they work together
body: <p><strong>TL;DR</strong></p>
  
  <p>I tried to make this a short question but it's a complicated problem so it ended up being long.  If you can answer any part of this or give any suggestions or tips or resources or anything at all, it would be extremely helpful (even if you don't directly solve all my issues).  I'm banging my head against the wall right now.  :)</p>
  
  <p>Here are the specific issues I am having.  Read on below for more information.</p>
  
  <ul>
  <li>I'm looking for guidance on how to process relocation entries and update the unresolved symbols in the section data.  I simply don't understand what to do with all the information I've pulled from the relocations and the sections, etc.</li>
  <li>I'm also hoping to understand just what is going on when the linker encounters relocations.  Trying to correctly implement the relocation equations and use all the correct values in the correct way is incredibly challenging.</li>
  <li>When I encounter op codes and addresses and symbols, etc, I need to understand what to do with them.  I feel like I am missing some steps.</li>
  <li>I feel like I don't have a good grasp on how the symbol table entries interact with the relocations.  How should I use the symbol's binding, visibility, value, and size information?</li>
  <li>Lastly, when I output my file with the resolved data and new relocation entries used by the executable, the data is all incorrect.  I'm not sure how to follow all the relocations and provide all the information necessary.  What is the executable expecting from me?</li>
  </ul>
  
  <hr>
  
  <p><strong>My approach so far</strong></p>
  
  <p>I am trying to create a relocation file in a specific [undocumented] proprietary format that is heavily based on ELF.  I have written a tool that takes an ELF file and a partially linked file (PLF) and processes them to output the fully resolved rel file.  This rel file is used to load/unload data as needed in order to save memory.  The platform is a 32bit PPC.  One wrinkle is that tool is written for Windows in c#, but the data is intended for the PPC, so there are fun endian issues and the like to watch out for.</p>
  
  <p>I've been trying to understand how relocations are handled when used to resolve unresolved symbols and so on.  What I've done so far is to copy the relevant sections from the PLF and then for each corresponding .rela section, I parse the entries and attempt to fix up the section data and generate new relocation entries as needed.  But this is where my difficulty is.  I'm way out of my element here and this sort of thing seems to typically be done by linkers and loaders so there's not a lot of good examples to draw upon.  But I have found a few that have been of help, including <a href="http://llvm.org/docs/doxygen/html/RuntimeDyldELF_8cpp_source.html" rel="noreferrer">THIS ONE</a>.</p>
  
  <p>So what is happening is:</p>
  
  <ol>
  <li>Copy section data from PLF to be used for rel file.  I'm only interested in the .init (no data), .text, .ctors, .dtors, .rodata, .data, .bss (no data), and another custom section we are using.</li>
  <li>Iterate over the .rela sections in the PLF and read in the Elf32_Rela entries.</li>
  <li>For each entry, I pull out the r_offset, r_info, and r_addend fields and extract the relevant info from r_info (the symbol and the reloc type).</li>
  <li>From the PLF's symbol table, I can get the symbolOffset, the symbolSection, and the symbolValue.</li>
  <li>From the ELF, I get the symbolSection's load address.</li>
  <li>I compute int localAddress = ( .relaSection.Offset + r_offset ).</li>
  <li>I get the uint relocValue from the symbolSection's contents at r_offset.</li>
  <li>Now I have all the info I need so I do a switch on the reloc type and process the data.  These are the types I support:<br>
      R_PPC_NONE<br>
      R_PPC_ADDR32<br>
      R_PPC_ADDR24<br>
      R_PPC_ADDR16<br>
      R_PPC_ADDR16_LO<br>
      R_PPC_ADDR16_HI<br>
      R_PPC_ADDR16_HA<br>
      R_PPC_ADDR14<br>
      R_PPC_ADDR14_BRTAKEN<br>
      R_PPC_ADDR14_BRNTAKEN<br>
      R_PPC_REL24<br>
      R_PPC_REL14<br>
      R_PPC_REL14_BRTAKEN<br>
      R_PPC_REL14_BRNTAKEN<br></li>
  <li>Now what??  I need to update the section data and build companion relocation entries.  But I don't understand what is necessary to do and how to do it.</li>
  </ol>
  
  <p>The whole reason I'm doing this is because there is an old obsolete unsupported tool that does not support using custom sections, which is a key requirement for this project (for memory reasons).  We have a custom section that contains a bunch of initialization code (totaling about a meg) that we want to unload after start up.  The existing tool just ignores all the data in that section.</p>
  
  <p>So while making our own tool that does support custom sections is ideal, if there are any bright ideas for another way to achieve this goal, I'm all ears!  We've floated around an idea of using the .dtor section for our data since it's nearly empty anyway.  But this is messy and might not work anyway if it prevents a clean shutdown.</p>
  
  <hr>
  
  <p><strong>Relocations plus example code</strong></p>
  
  <p>When I process the relocations, I'm working off of the equations and information found in the ABI docs <a href="https://www.power.org/wp-content/uploads/2012/07/Power-Arch-32-bit-ABI-supp-1.0-Embedded.pdf" rel="noreferrer">HERE</a> (around section 4.13, page 80ish) as well as a number of other code examples and blog posts I've dug up.  But it's all so confusing and not really spelled out and all the code I've found does things a little differently.</p>
  
  <p>For example, </p>
  
  <ul>
  <li>R_PPC_ADDR16_LO --> half16:  #lo(S + A)</li>
  <li>R_PPC_ADDR14_BRTAKEN --> low14*:  (S + A) >> 2</li>
  <li>etc</li>
  </ul>
  
  <p>So when I see this kind of code, how do I decipher it?</p>
  
  <p>Here's one example (from <a href="http://llvm.org/docs/doxygen/html/RuntimeDyldELF_8cpp_source.html" rel="noreferrer">this source</a>)</p>
  
  <pre><code>case ELF::R_PPC64_ADDR14 : {
      assert(((Value + Addend) &amp; 3) == 0);
      // Preserve the AA/LK bits in the branch instruction
      uint8_t aalk = *(LocalAddress+3);
      writeInt16BE(LocalAddress + 2, (aalk &amp; 3) | ((Value + Addend) &amp; 0xfffc));
  } break;
  
  case ELF::R_PPC64_REL24 : {
      uint64_t FinalAddress = (Section.LoadAddress + Offset);
      int32_t delta = static_cast&lt;int32_t&gt;(Value - FinalAddress + Addend);
      if (SignExtend32&lt;24&gt;(delta) != delta)
          llvm_unreachable("Relocation R_PPC64_REL24 overflow");
      // Generates a 'bl &lt;address&gt;' instruction
      writeInt32BE(LocalAddress, 0x48000001 | (delta &amp; 0x03FFFFFC));
  } break;
  </code></pre>
  
  <p>Here's some from another example (<a href="http://people.freebsd.org/~grehan/elf_machdep.c" rel="noreferrer">here</a>)</p>
  
  <pre><code>case R_PPC_ADDR32: /* word32 S + A */
      addr = elf_lookup(lf, symidx, 1);
      if (addr == 0)
          return -1;
      addr += addend;
      *where = addr;
      break;
  
  case R_PPC_ADDR16_LO: /* #lo(S) */
      if (addend != 0) {
          addr = relocbase + addend;
      } else {
          addr = elf_lookup(lf, symidx, 1);
          if (addr == 0)
              return -1;
      }
      *hwhere = addr &amp; 0xffff;
      break;
  
  case R_PPC_ADDR16_HA: /* #ha(S) */
      if (addend != 0) {
          addr = relocbase + addend;
      } else {
          addr = elf_lookup(lf, symidx, 1);
          if (addr == 0)
              return -1;
      }
      *hwhere = ((addr &gt;&gt; 16) + ((addr &amp; 0x8000) ? 1 : 0)) &amp; 0xffff;
      break;
  </code></pre>
  
  <p>And one other example (<a href="https://source.ridgerun.net/svn/leopardboarddm365/sdk/trunk/fs/apps/prelink-0.3.3.1/src/src/arch-ppc.c" rel="noreferrer">from here</a>)</p>
  
  <pre><code>case R_PPC_ADDR16_HA:
      write_be16 (dso, rela-&gt;r_offset, (value + 0x8000) &gt;&gt; 16);
      break;
  case R_PPC_ADDR24:
      write_be32 (dso, rela-&gt;r_offset, (value &amp; 0x03fffffc) | (read_ube32 (dso, rela-&gt;r_offset) &amp; 0xfc000003));
      break;
  case R_PPC_ADDR14:
      write_be32 (dso, rela-&gt;r_offset, (value &amp; 0xfffc) | (read_ube32 (dso, rela-&gt;r_offset) &amp; 0xffff0003));
      break;
  case R_PPC_ADDR14_BRTAKEN:
  case R_PPC_ADDR14_BRNTAKEN:
      write_be32 (dso, rela-&gt;r_offset, (value &amp; 0xfffc)
                                      | (read_ube32 (dso, rela-&gt;r_offset) &amp; 0xffdf0003)
                                      | ((((GELF_R_TYPE (rela-&gt;r_info) == R_PPC_ADDR14_BRTAKEN) &lt;&lt; 21)
                                      ^ (value &gt;&gt; 10)) &amp; 0x00200000));
      break;
  case R_PPC_REL24:
      write_be32 (dso, rela-&gt;r_offset, ((value - rela-&gt;r_offset) &amp; 0x03fffffc) | (read_ube32 (dso, rela-&gt;r_offset) &amp; 0xfc000003));
      break;
  case R_PPC_REL32:
      write_be32 (dso, rela-&gt;r_offset, value - rela-&gt;r_offset);
      break;
  </code></pre>
  
  <p>I really want to understand the magic these guys are doing here and why their code doesn't always look the same.  I think some of the code is making assumptions that the data was already properly masked (for branches, etc), and some of the code is not.  But I don't understand any of this at all.</p>
  
  <hr>
  
  <p><strong>Following the symbols/data/relocations, etc</strong></p>
  
  <p>When I look at the data in a hexeditor, I see a bunch of "48 00 00 01" all over.  I've figured out that this is an opcode and needs to be updated with relocation information (this specifically is for 'bl' branch and link), yet my tool doesn't operate on the vast majority of them and the ones that I do update have the wrong values in them (compared to an example made by an obsolete tool).  Clearly I am missing some part of the process.</p>
  
  <p>In addition to the section data, there are additional relocation entries that need to be added to the end of the rel file.  These consist of internal and external relocations but I haven't figured out much at all about these yet.  (what's the difference between the two and when do you use one or the other?)</p>
  
  <p>If you look near the end of <a href="http://llvm.org/docs/doxygen/html/RuntimeDyldELF_8cpp_source.html" rel="noreferrer">this file</a> at the function <code>RuntimeDyldELF::processRelocationRef</code>, you'll see some Relocation Entries being created.  They also make stub functions.  I suspect this is the missing link for me, but it's as clear as mud and I'm not following it even a little bit.</p>
  
  <p>When I output the symbols in each relocation entry, they each have a binding/visibility [Global/Weak/Local] [Function/Object] and a value, a size, and a section.  I know the section is where the symbol is located, and the value is the offset to the symbol in that section (or is it the virtual address?).  The size is the size of the symbol, but is this important?  Maybe the global/weak/local is useful for determining if it's an internal or external relocation?</p>
  
  <p>Maybe this relocation table I'm talking about creating is actually a symbol table for my rel file?  Maybe this table updates the symbol value from being a virtual address to being a section offset (since that's what the value is in relocatable files and the symbol table in the PLF is basically in an executable)?</p>
  
  <hr>
  
  <p><strong>Some resources:</strong></p>
  
  <ol>
  <li>blog on relocations: <a href="http://eli.thegreenplace.net/2011/08/25/load-time-relocation-of-shared-libraries/" rel="noreferrer">http://eli.thegreenplace.net/2011/08/25/load-time-relocation-of-shared-libraries/</a></li>
  <li>mentions opcodes at the end: <a href="http://wiki.netbsd.org/examples/elf_executables_for_powerpc/" rel="noreferrer">http://wiki.netbsd.org/examples/elf_executables_for_powerpc/</a></li>
  <li>my related unanswered question: <a href="https://stackoverflow.com/questions/16577473/elf-relocation-reverse-engineering">ELF Relocation reverse engineering</a></li>
  </ol>
  
  <hr>
  
  <p>Whew!  That's a beast of a question.  Congrats if you made it this far.  :)  Thanks in advance for any help you can give me.</p>