ELF: Add support for emitting dynamic relocations in the Android relocation packing format.

[pcc]

Summary

The Android relocation packing format is a more compact
format for dynamic relocations in executables and DSOs
that is based on delta encoding and SLEBs. An overview
of the format can be found in the Android source code:
https://android.googlesource.com/platform/bionic/+/refs/heads/master/tools/relocation_packer/src/delta_encoder.h

This patch implements relocation packing using that format.

This implementation uses a more intelligent algorithm for compressing
relative relocations than Android's own relocation packer. As a
result it can generally create smaller relocation sections than
that packer. If I link Chromium for Android targeting ARM32 I get a
.rel.dyn of size 174693 bytes, as compared to 371832 bytes with gold
and the Android packer.

Depends on D34692

[peter.smith]

I think that this is worthwhile putting into the linker as relocations can be sorted to optimise packing and make it easier to account for address changes to the rest of the ELF file.

Some overall thoughts and suggestions:

• Is it likely that other packing formats may come along? In this case we may be better to have an interface like --relocation-packing=(none | android | ... )
• It would be good to have a tool to expand and display textually the packed relocations, for example llvm-objdump -r could naturally display the packed relocation sections as if they were normal relocations.
• Is it worth adding an option to sort the relocations for packing, but not do the packing. This would make it easier to write tests, for example we could check that the relocations were sorted in the order that we would expect, with a suitable tool to unpack the encoded form into human readable text we could also check the encoding process. A secondary benefit would be that people using an external relocation packer could still benefit from the sorting.

lld/ELF/Options.td

15 ↗

(On Diff #119733)

Would it be better to have --pack-dyn-relocs=<packing format>. Where we have none or Android as the initial parameters. I'm just thinking of other OSs or even Android having more than one format.

lld/ELF/SyntheticSections.cpp

1109 ↗

(On Diff #119733)

Just checking to see if the new line was intentional? I've no objections to adding it.

1246 ↗

(On Diff #119733)

I think that this is converting DynamicReloc to an ELFT::Rela? Would it be better to use a more specific name?

1251 ↗

(On Diff #119733)

I don't think that this comment reads well and I'm not sure I understand it? I know it is just a move from another section but is it worth fixing it up?

1319 ↗

(On Diff #119733)

In the final version I think it will be worth expanding the necessary details inline. I'm thinking of the stability of the link here. It also doesn't mention the LEB encoding either.

1330 ↗

(On Diff #119733)

I guess this is some kind of header?

1340 ↗

(On Diff #119733)

Is it worth using similarly structured names for the two partitions, for example RelativeRelocs and NonRelativeRelocs?

1353 ↗

(On Diff #119733)

Is it worth moving the sort to just before the OtherRelocs are processed (near the end of the function)?

1355 ↗

(On Diff #119733)

The -zcombreloc sorting order tries to order relocations by the destination symbol first so that the dynamic loader (at least on Linux) can reuse the symbol lookup result. Is there a trade off between packing efficiency and load time here? This may be handled differently by the Android dynamic linker?

1364 ↗

(On Diff #119733)

Is it worth having a similarly structured name such as UngroupedRelatives and GroupedRelatives?

1369 ↗

(On Diff #119733)

I found rewriting this as *I - *(I - 1) == Config->Wordsize made it easier to understand, but this may not be universal.

1375 ↗

(On Diff #119733)

Should J have a type of size_t?

lld/ELF/SyntheticSections.h

405 ↗

(On Diff #119733)

Is it worth having Packed as part of the name, either PackedRelocationSection or the slightly overlong AndroidPackedRelocationSection. I think it will make it more obvious what the section does from the name.

lld/ELF/Writer.cpp

1381 ↗

(On Diff #119733)

Do we need a call to Script->assignAddresses() before updateAllocSize()? I'm thinking of the case where createThunks() affects the r_offsets in RelaDyn->updateAllocSize() that affects the size of RelaDyn, that affects the addresses in Thunks. I think that for correctness this all works out as we can't exit the loop unless there are no changes, but it may take longer to converge in some situations.

llvm/include/llvm/BinaryFormat/ELF.h

733 ↗

(On Diff #119733)

Would be good to have a reference to where these are defined (public specification?), similarly for the DT tags.

[pcc]

In D39152#903029, @peter.smith wrote:

I think that this is worthwhile putting into the linker as relocations can be sorted to optimise packing and make it easier to account for address changes to the rest of the ELF file.

Some overall thoughts and suggestions:

• Is it likely that other packing formats may come along? In this case we may be better to have an interface like --relocation-packing=(none | android | ... )

I think that makes sense. There's been some talk of a new packing format on the gnu-gabi lists, so it would be good to be able to accommodate whatever comes out of that.

• It would be good to have a tool to expand and display textually the packed relocations, for example llvm-objdump -r could naturally display the packed relocation sections as if they were normal relocations.

Right, I was planning to teach llvm-objdump about this format as part of writing the test cases for this patch.

• Is it worth adding an option to sort the relocations for packing, but not do the packing. This would make it easier to write tests, for example we could check that the relocations were sorted in the order that we would expect, with a suitable tool to unpack the encoded form into human readable text we could also check the encoding process. A secondary benefit would be that people using an external relocation packer could still benefit from the sorting.

It doesn't really seem worth it to me, as long as we have llvm-objdump support for testing purposes. I also don't see much value in making the output compatible with external relocation packers, as that cannot be done soundly in general.

lld/ELF/Options.td

15 ↗

(On Diff #119733)

Will do.

lld/ELF/SyntheticSections.cpp

1109 ↗

(On Diff #119733)

No, I'll remove it.

1246 ↗

(On Diff #119733)

encodeDynamicReloc maybe?

1251 ↗

(On Diff #119733)

I don't understand it either :)

I'll see if I can figure out what it is trying to say and fix it.

1319 ↗

(On Diff #119733)

That makes sense. I'll try to write something up.

1330 ↗

(On Diff #119733)

Right.

1340 ↗

(On Diff #119733)

Makes sense, I'll do that.

1353 ↗

(On Diff #119733)

Sounds fine to me.

1355 ↗

(On Diff #119733)

The Android dynamic loader doesn't appear to have any optimization for this case. It looks like it just performs a symbol lookup for each relocation.

https://android.googlesource.com/platform/bionic/+/refs/heads/master/linker/linker.cpp#2507

1364 ↗

(On Diff #119733)

I kind of prefer the name RelativeGroups over GroupedRelatives because the latter implies that the vector contains relocations as opposed to groups, when in fact it contains groups. But I don't feel too strongly about it.

1369 ↗

(On Diff #119733)

I found the form I wrote it in easier to understand, but again don't feel too strongly about it.

1375 ↗

(On Diff #119733)

It probably doesn't matter because J can never be larger than 7.

lld/ELF/SyntheticSections.h

405 ↗

(On Diff #119733)

AndroidPacked seems fine to me.

lld/ELF/Writer.cpp

1381 ↗

(On Diff #119733)

That wouldn't seem to be a concern for REL (because of delta encoding, the section (in general) will only contain relative offsets within the r/w segment (with one exception for the initial delta into the r/w segment), and r/w won't contain anything whose size will change, so I'd expect there to be at most two convergent steps), but it may be a concern for RELA (because it will also end up containing deltas within text and other sections). I'll have to experiment with this once I have RELA implemented.

llvm/include/llvm/BinaryFormat/ELF.h

733 ↗

(On Diff #119733)

I haven't seen them formally defined anywhere. Probably the best we can do is link to the Android source code.

[pcc]

• Address review comments

[peter.smith]

Thanks for the update, I don't have any particularly strong views about the detailed comments so unless anyone else strongly agrees, I'm happy to keep with what you have. I don't have any further suggestions at the moment.

[pcc]

• Add rela support
• Add test
• Use correct sh_link value in section header

[ruiu]

lld/ELF/Config.h

167 ↗

(On Diff #120307)

Can this just be a boolean flag AndroidPackDynRelocs?

lld/ELF/SyntheticSections.cpp

1245 ↗

(On Diff #120307)

I first thought that "*" is to emphasize a word and a closing "*" were missing.

1357 ↗

(On Diff #120307)

I'd also mention that how many bytes could be saved by this encoding compared to the default dynamic relocation table to give an insight why this format was invented and is used.

1379 ↗

(On Diff #120307)

I believe you can use Rel.Type insetad of R.getType(Config->IsMips64EL).

1486 ↗

(On Diff #120307)

This needs comment.

lld/ELF/SyntheticSections.h

415 ↗

(On Diff #120307)

std::copy should work, but for consistency with other writeTo functions, memcpy would be better.

lld/ELF/Writer.cpp

373–374 ↗

(On Diff #120307)

What's wrong with doing this for packed relocations?

[pcc]

• Address review comments

lld/ELF/Config.h

167 ↗

(On Diff #120307)

It can for now, I suppose.

lld/ELF/SyntheticSections.cpp

1245 ↗

(On Diff #120307)

Note that this is just moving code around (see line 1287 in the old code). But seems reasonable to change it to R_*_RELATIVE.

1379 ↗

(On Diff #120307)

I don't think that will work because the type is stored in the r_info field.

lld/ELF/Writer.cpp

373–374 ↗

(On Diff #120307)

That would cause a section type mismatch. I've added a comment with a few more details.

[ruiu]

lld/ELF/SyntheticSections.cpp

1342 ↗

(On Diff #120351)

That is huge savings! I'd put commas to the numbers because at first it looked like a reduction from 29 to 17. :)

[pcc]

• Add commas

[grimar]

Minor nits.

lld/ELF/Driver.cpp

768 ↗

(On Diff #120353)

Since you always initialize Config->AndroidPackDynRelocs to false, this could be:

StringRef S = Arg->getValue();
if (S == "android")
  Config->AndroidPackDynRelocs = true;
if (S != "none")
  error("unknown -pack-dyn-relocs format: " + S);

lld/ELF/SyntheticSections.cpp

1378 ↗

(On Diff #120353)

Perhaps instead of clear and push_backs better would be to

RelocData = {'A', 'P', 'S', '2'};

?

[ruiu]

LGTM

[pcc]

• Simplify

[grimar]

In D39152#908640, @pcc wrote:

• Simplify

Thanks !

lld/trunk/ELF/Config.h

struct Configuration {
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> SymbolOrderingFile;
   std::vector<llvm::StringRef> Undefined;
   std::vector<SymbolVersion> DynamicList;
   std::vector<SymbolVersion> VersionScriptGlobals;
   std::vector<SymbolVersion> VersionScriptLocals;
   std::vector<uint8_t> BuildIdVector;
   bool AllowMultipleDefinition;
+  bool AndroidPackDynRelocs = false;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
   bool CompressDebugSections;
   bool DefineCommon;
   bool Demangle = true;
   bool DisableVerify;
   bool EhFrameHdr;

lld/trunk/ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   // .text segments are writable. Today, the option is still in use to
   // create special-purpose programs such as boot loaders. It doesn't
   // make sense to create PT_GNU_RELRO for such executables.
   if (Config->Omagic)
     Config->ZRelro = false;
 
   std::tie(Config->BuildId, Config->BuildIdVector) = getBuildId(Args);
 
+  if (auto *Arg = Args.getLastArg(OPT_pack_dyn_relocs_eq)) {
+    StringRef S = Arg->getValue();
+    if (S == "android")
+      Config->AndroidPackDynRelocs = true;
+    else if (S != "none")
+      error("unknown -pack-dyn-relocs format: " + S);
+  }
+
   if (auto *Arg = Args.getLastArg(OPT_symbol_ordering_file))
     if (Optional<MemoryBufferRef> Buffer = readFile(Arg->getValue()))
       Config->SymbolOrderingFile = getLines(*Buffer);
 
   // If --retain-symbol-file is used, we'll keep only the symbols listed in
   // the file and discard all others.
   if (auto *Arg = Args.getLastArg(OPT_retain_symbols_file)) {
     Config->DefaultSymbolVersion = VER_NDX_LOCAL;

lld/trunk/ELF/Options.td

def oformat: Separate<["--"], "oformat">, MetaVarName<"<format>">,
   HelpText<"Specify the binary format for the output object file">;
 
 def omagic: Flag<["--"], "omagic">, MetaVarName<"<magic>">,
   HelpText<"Set the text and data sections to be readable and writable">;
 
 defm orphan_handling: Eq<"orphan-handling">, 
   HelpText<"Control how orphan sections are handled when linker script used">;
 
+def pack_dyn_relocs_eq: J<"pack-dyn-relocs=">, MetaVarName<"<format>">,
+  HelpText<"Pack dynamic relocations in the given format (none or android)">;
+
 def pie: F<"pie">, HelpText<"Create a position independent executable">;
 
 def print_gc_sections: F<"print-gc-sections">,
   HelpText<"List removed unused sections">;
 
 def print_map: F<"print-map">,
   HelpText<"Print a link map to the standard output">;
 

lld/trunk/ELF/SyntheticSections.h

public:
   }
 
   virtual ~SyntheticSection() = default;
   virtual void writeTo(uint8_t *Buf) = 0;
   virtual size_t getSize() const = 0;
   virtual void finalizeContents() {}
   // If the section has the SHF_ALLOC flag and the size may be changed if
   // thunks are added, update the section size.
-  virtual void updateAllocSize() {}
+  virtual bool updateAllocSize() { return false; }
   // If any additional finalization of contents are needed post thunk creation.
   virtual void postThunkContents() {}
   virtual bool empty() const { return false; }
   uint64_t getVA() const;
 
   static bool classof(const SectionBase *D) {
     return D->kind() == InputSectionBase::Synthetic;
   }
private:
   uint64_t Size;
 };
 
 class MipsGotSection final : public SyntheticSection {
 public:
   MipsGotSection();
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override { return Size; }
-  void updateAllocSize() override;
+  bool updateAllocSize() override;
   void finalizeContents() override;
   bool empty() const override;
   void addEntry(SymbolBody &Sym, int64_t Addend, RelExpr Expr);
   bool addDynTlsEntry(SymbolBody &Sym);
   bool addTlsIndex();
   uint64_t getPageEntryOffset(const SymbolBody &B, int64_t Addend) const;
   uint64_t getBodyEntryOffset(const SymbolBody &B, int64_t Addend) const;
   uint64_t getGlobalDynOffset(const SymbolBody &B) const;
public:
   size_t getSize() const override { return Size; }
 
 private:
   void addEntries();
   void add(Entry E) { Entries.push_back(E); }
   uint64_t Size = 0;
 };
 
-template <class ELFT> class RelocationSection final : public SyntheticSection {
+class RelocationBaseSection : public SyntheticSection {
+public:
+  RelocationBaseSection(StringRef Name, uint32_t Type, int32_t DynamicTag,
+                        int32_t SizeDynamicTag);
+  void addReloc(const DynamicReloc &Reloc);
+  bool empty() const override { return Relocs.empty(); }
+  size_t getSize() const override { return Relocs.size() * this->Entsize; }
+  size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
+  void finalizeContents() override;
+  int32_t DynamicTag, SizeDynamicTag;
+
+protected:
+  std::vector<DynamicReloc> Relocs;
+  size_t NumRelativeRelocs = 0;
+};
+
+template <class ELFT>
+class RelocationSection final : public RelocationBaseSection {
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
 
 public:
   RelocationSection(StringRef Name, bool Sort);
-  void addReloc(const DynamicReloc &Reloc);
   unsigned getRelocOffset();
-  void finalizeContents() override;
   void writeTo(uint8_t *Buf) override;
-  bool empty() const override { return Relocs.empty(); }
-  size_t getSize() const override { return Relocs.size() * this->Entsize; }
-  size_t getRelativeRelocCount() const { return NumRelativeRelocs; }
 
 private:
   bool Sort;
-  size_t NumRelativeRelocs = 0;
-  std::vector<DynamicReloc> Relocs;
+};
+
+template <class ELFT>
+class AndroidPackedRelocationSection final : public RelocationBaseSection {
+  typedef typename ELFT::Rel Elf_Rel;
+  typedef typename ELFT::Rela Elf_Rela;
+
+public:
+  AndroidPackedRelocationSection(StringRef Name);
+
+  bool updateAllocSize() override;
+  size_t getSize() const override { return RelocData.size(); }
+  void writeTo(uint8_t *Buf) override {
+    memcpy(Buf, RelocData.data(), RelocData.size());
+  }
+
+private:
+  SmallVector<char, 0> RelocData;
 };
 
 struct SymbolTableEntry {
   SymbolBody *Symbol;
   size_t StrTabOffset;
 };
 
 class SymbolTableBaseSection : public SyntheticSection {
struct InX {
   static PltSection *Plt;
   static PltSection *Iplt;
   static StringTableSection *ShStrTab;
   static StringTableSection *StrTab;
   static SymbolTableBaseSection *SymTab;
 };
 
 template <class ELFT> struct In {
-  static RelocationSection<ELFT> *RelaDyn;
+  static RelocationBaseSection *RelaDyn;
   static RelocationSection<ELFT> *RelaPlt;
   static RelocationSection<ELFT> *RelaIplt;
   static VersionDefinitionSection<ELFT> *VerDef;
   static VersionTableSection<ELFT> *VerSym;
   static VersionNeedSection<ELFT> *VerNeed;
 };
 
-template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaDyn;
+template <class ELFT> RelocationBaseSection *In<ELFT>::RelaDyn;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaPlt;
 template <class ELFT> RelocationSection<ELFT> *In<ELFT>::RelaIplt;
 template <class ELFT> VersionDefinitionSection<ELFT> *In<ELFT>::VerDef;
 template <class ELFT> VersionTableSection<ELFT> *In<ELFT>::VerSym;
 template <class ELFT> VersionNeedSection<ELFT> *In<ELFT>::VerNeed;
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/SyntheticSections.cpp

 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
 #include "llvm/Object/Decompressor.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Support/LEB128.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/xxhash.h"
 #include <cstdlib>
 #include <thread>
 
 using namespace llvm;

 
 unsigned MipsGotSection::getLocalEntriesNum() const {
   return HeaderEntriesNum + PageEntriesNum + LocalEntries.size() +
          LocalEntries32.size();
 }
 
 void MipsGotSection::finalizeContents() { updateAllocSize(); }
 
-void MipsGotSection::updateAllocSize() {
+bool MipsGotSection::updateAllocSize() {
   PageEntriesNum = 0;
   for (std::pair<const OutputSection *, size_t> &P : PageIndexMap) {
     // For each output section referenced by GOT page relocations calculate
     // and save into PageIndexMap an upper bound of MIPS GOT entries required
     // to store page addresses of local symbols. We assume the worst case -
     // each 64kb page of the output section has at least one GOT relocation
     // against it. And take in account the case when the section intersects
     // page boundaries.
     P.second = PageEntriesNum;
     PageEntriesNum += getMipsPageCount(P.first->Size);
   }
   Size = (getLocalEntriesNum() + GlobalEntries.size() + TlsEntries.size()) *
          Config->Wordsize;
+  return false;
 }
 
 bool MipsGotSection::empty() const {
   // We add the .got section to the result for dynamic MIPS target because
   // its address and properties are mentioned in the .dynamic section.
   return Config->Relocatable;
 }
 

 
 // Add remaining entries to complete .dynamic contents.
 template <class ELFT> void DynamicSection<ELFT>::finalizeContents() {
   if (this->Size)
     return; // Already finalized.
 
   this->Link = InX::DynStrTab->getParent()->SectionIndex;
   if (In<ELFT>::RelaDyn->getParent() && !In<ELFT>::RelaDyn->empty()) {
-    bool IsRela = Config->IsRela;
-    add({IsRela ? DT_RELA : DT_REL, In<ELFT>::RelaDyn});
-    add({IsRela ? DT_RELASZ : DT_RELSZ, In<ELFT>::RelaDyn->getParent(),
+    add({In<ELFT>::RelaDyn->DynamicTag, In<ELFT>::RelaDyn});
+    add({In<ELFT>::RelaDyn->SizeDynamicTag, In<ELFT>::RelaDyn->getParent(),
          Entry::SecSize});
+
+    bool IsRela = Config->IsRela;
     add({IsRela ? DT_RELAENT : DT_RELENT,
          uint64_t(IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel))});
 
     // MIPS dynamic loader does not support RELCOUNT tag.
     // The problem is in the tight relation between dynamic
     // relocations and GOT. So do not emit this tag on MIPS.
     if (Config->EMachine != EM_MIPS) {
       size_t NumRelativeRels = In<ELFT>::RelaDyn->getRelativeRelocCount();

 }
 
 uint32_t DynamicReloc::getSymIndex() const {
   if (Sym && !UseSymVA)
     return Sym->DynsymIndex;
   return 0;
 }
 
-template <class ELFT>
-RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
-    : SyntheticSection(SHF_ALLOC, Config->IsRela ? SHT_RELA : SHT_REL,
-                       Config->Wordsize, Name),
-      Sort(Sort) {
-  this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
-}
+RelocationBaseSection::RelocationBaseSection(StringRef Name, uint32_t Type,
+                                             int32_t DynamicTag,
+                                             int32_t SizeDynamicTag)
+    : SyntheticSection(SHF_ALLOC, Type, Config->Wordsize, Name),
+      DynamicTag(DynamicTag), SizeDynamicTag(SizeDynamicTag) {}
 
-template <class ELFT>
-void RelocationSection<ELFT>::addReloc(const DynamicReloc &Reloc) {
+void RelocationBaseSection::addReloc(const DynamicReloc &Reloc) {
   if (Reloc.Type == Target->RelativeRel)
     ++NumRelativeRelocs;
   Relocs.push_back(Reloc);
 }
 
+void RelocationBaseSection::finalizeContents() {
+  // If all relocations are R_*_RELATIVE they don't refer to any
+  // dynamic symbol and we don't need a dynamic symbol table. If that
+  // is the case, just use 0 as the link.
+  this->Link = InX::DynSymTab ? InX::DynSymTab->getParent()->SectionIndex : 0;
+
+  // Set required output section properties.
+  getParent()->Link = this->Link;
+}
+
+template <class ELFT>
+static void encodeDynamicReloc(typename ELFT::Rela *P,
+                               const DynamicReloc &Rel) {
+  if (Config->IsRela)
+    P->r_addend = Rel.getAddend();
+  P->r_offset = Rel.getOffset();
+  if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot)
+    // The MIPS GOT section contains dynamic relocations that correspond to TLS
+    // entries. These entries are placed after the global and local sections of
+    // the GOT. At the point when we create these relocations, the size of the
+    // global and local sections is unknown, so the offset that we store in the
+    // TLS entry's DynamicReloc is relative to the start of the TLS section of
+    // the GOT, rather than being relative to the start of the GOT. This line of
+    // code adds the size of the global and local sections to the virtual
+    // address computed by getOffset() in order to adjust it into the TLS
+    // section.
+    P->r_offset += InX::MipsGot->getTlsOffset();
+  P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL);
+}
+
+template <class ELFT>
+RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
+    : RelocationBaseSection(Name, Config->IsRela ? SHT_RELA : SHT_REL,
+                            Config->IsRela ? DT_RELA : DT_REL,
+                            Config->IsRela ? DT_RELASZ : DT_RELSZ),
+      Sort(Sort) {
+  this->Entsize = Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
+}
+
 template <class ELFT, class RelTy>
 static bool compRelocations(const RelTy &A, const RelTy &B) {
   bool AIsRel = A.getType(Config->IsMips64EL) == Target->RelativeRel;
   bool BIsRel = B.getType(Config->IsMips64EL) == Target->RelativeRel;
   if (AIsRel != BIsRel)
     return AIsRel;
 
   return A.getSymbol(Config->IsMips64EL) < B.getSymbol(Config->IsMips64EL);
 }
 
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
   uint8_t *BufBegin = Buf;
   for (const DynamicReloc &Rel : Relocs) {
-    auto *P = reinterpret_cast<Elf_Rela *>(Buf);
+    encodeDynamicReloc<ELFT>(reinterpret_cast<Elf_Rela *>(Buf), Rel);
     Buf += Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
-
-    if (Config->IsRela)
-      P->r_addend = Rel.getAddend();
-    P->r_offset = Rel.getOffset();
-    if (Config->EMachine == EM_MIPS && Rel.getInputSec() == InX::MipsGot)
-      // Dynamic relocation against MIPS GOT section make deal TLS entries
-      // allocated in the end of the GOT. We need to adjust the offset to take
-      // in account 'local' and 'global' GOT entries.
-      P->r_offset += InX::MipsGot->getTlsOffset();
-    P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->IsMips64EL);
   }
 
   if (Sort) {
     if (Config->IsRela)
       std::stable_sort((Elf_Rela *)BufBegin,
                        (Elf_Rela *)BufBegin + Relocs.size(),
                        compRelocations<ELFT, Elf_Rela>);
     else
       std::stable_sort((Elf_Rel *)BufBegin, (Elf_Rel *)BufBegin + Relocs.size(),
                        compRelocations<ELFT, Elf_Rel>);
   }
 }
 
 template <class ELFT> unsigned RelocationSection<ELFT>::getRelocOffset() {
   return this->Entsize * Relocs.size();
 }
 
-template <class ELFT> void RelocationSection<ELFT>::finalizeContents() {
-  // If all relocations are *RELATIVE they don't refer to any
-  // dynamic symbol and we don't need a dynamic symbol table. If that
-  // is the case, just use 0 as the link.
-  this->Link = InX::DynSymTab ? InX::DynSymTab->getParent()->SectionIndex : 0;
+template <class ELFT>
+AndroidPackedRelocationSection<ELFT>::AndroidPackedRelocationSection(
+    StringRef Name)
+    : RelocationBaseSection(
+          Name, Config->IsRela ? SHT_ANDROID_RELA : SHT_ANDROID_REL,
+          Config->IsRela ? DT_ANDROID_RELA : DT_ANDROID_REL,
+          Config->IsRela ? DT_ANDROID_RELASZ : DT_ANDROID_RELSZ) {
+  this->Entsize = 1;
+}
 
-  // Set required output section properties.
-  getParent()->Link = this->Link;
+template <class ELFT>
+bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
+  // This function computes the contents of an Android-format packed relocation
+  // section.
+  //
+  // This format compresses relocations by using relocation groups to factor out
+  // fields that are common between relocations and storing deltas from previous
+  // relocations in SLEB128 format (which has a short representation for small
+  // numbers). A good example of a relocation type with common fields is
+  // R_*_RELATIVE, which is normally used to represent function pointers in
+  // vtables. In the REL format, each relative relocation has the same r_info
+  // field, and is only different from other relative relocations in terms of
+  // the r_offset field. By sorting relocations by offset, grouping them by
+  // r_info and representing each relocation with only the delta from the
+  // previous offset, each 8-byte relocation can be compressed to as little as 1
+  // byte (or less with run-length encoding). This relocation packer was able to
+  // reduce the size of the relocation section in an Android Chromium DSO from
+  // 2,911,184 bytes to 174,693 bytes, or 6% of the original size.
+  //
+  // A relocation section consists of a header containing the literal bytes
+  // 'APS2' followed by a sequence of SLEB128-encoded integers. The first two
+  // elements are the total number of relocations in the section and an initial
+  // r_offset value. The remaining elements define a sequence of relocation
+  // groups. Each relocation group starts with a header consisting of the
+  // following elements:
+  //
+  // - the number of relocations in the relocation group
+  // - flags for the relocation group
+  // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is set) the r_offset delta
+  //   for each relocation in the group.
+  // - (if RELOCATION_GROUPED_BY_INFO_FLAG is set) the value of the r_info
+  //   field for each relocation in the group.
+  // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG and
+  //   RELOCATION_GROUPED_BY_ADDEND_FLAG are set) the r_addend delta for
+  //   each relocation in the group.
+  //
+  // Following the relocation group header are descriptions of each of the
+  // relocations in the group. They consist of the following elements:
+  //
+  // - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is not set) the r_offset
+  //   delta for this relocation.
+  // - (if RELOCATION_GROUPED_BY_INFO_FLAG is not set) the value of the r_info
+  //   field for this relocation.
+  // - (if RELOCATION_GROUP_HAS_ADDEND_FLAG is set and
+  //   RELOCATION_GROUPED_BY_ADDEND_FLAG is not set) the r_addend delta for
+  //   this relocation.
+
+  size_t OldSize = RelocData.size();
+
+  RelocData = {'A', 'P', 'S', '2'};
+  raw_svector_ostream OS(RelocData);
+
+  // The format header includes the number of relocations and the initial
+  // offset (we set this to zero because the first relocation group will
+  // perform the initial adjustment).
+  encodeSLEB128(Relocs.size(), OS);
+  encodeSLEB128(0, OS);
+
+  std::vector<Elf_Rela> Relatives, NonRelatives;
+
+  for (const DynamicReloc &Rel : Relocs) {
+    Elf_Rela R;
+    encodeDynamicReloc<ELFT>(&R, Rel);
+
+    if (R.getType(Config->IsMips64EL) == Target->RelativeRel)
+      Relatives.push_back(R);
+    else
+      NonRelatives.push_back(R);
+  }
+
+  std::sort(Relatives.begin(), Relatives.end(),
+            [](const Elf_Rel &A, const Elf_Rel &B) {
+              return A.r_offset < B.r_offset;
+            });
+
+  // Try to find groups of relative relocations which are spaced one word
+  // apart from one another. These generally correspond to vtable entries. The
+  // format allows these groups to be encoded using a sort of run-length
+  // encoding, but each group will cost 7 bytes in addition to the offset from
+  // the previous group, so it is only profitable to do this for groups of
+  // size 8 or larger.
+  std::vector<Elf_Rela> UngroupedRelatives;
+  std::vector<std::vector<Elf_Rela>> RelativeGroups;
+  for (auto I = Relatives.begin(), E = Relatives.end(); I != E;) {
+    std::vector<Elf_Rela> Group;
+    do {
+      Group.push_back(*I++);
+    } while (I != E && (I - 1)->r_offset + Config->Wordsize == I->r_offset);
+
+    if (Group.size() < 8)
+      UngroupedRelatives.insert(UngroupedRelatives.end(), Group.begin(),
+                                Group.end());
+    else
+      RelativeGroups.emplace_back(std::move(Group));
+  }
+
+  unsigned HasAddendIfRela =
+      Config->IsRela ? RELOCATION_GROUP_HAS_ADDEND_FLAG : 0;
+
+  uint64_t Offset = 0;
+  uint64_t Addend = 0;
+
+  // Emit the run-length encoding for the groups of adjacent relative
+  // relocations. Each group is represented using two groups in the packed
+  // format. The first is used to set the current offset to the start of the
+  // group (and also encodes the first relocation), and the second encodes the
+  // remaining relocations.
+  for (std::vector<Elf_Rela> &G : RelativeGroups) {
+    // The first relocation in the group.
+    encodeSLEB128(1, OS);
+    encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
+                      RELOCATION_GROUPED_BY_INFO_FLAG | HasAddendIfRela,
+                  OS);
+    encodeSLEB128(G[0].r_offset - Offset, OS);
+    encodeSLEB128(Target->RelativeRel, OS);
+    if (Config->IsRela) {
+      encodeSLEB128(G[0].r_addend - Addend, OS);
+      Addend = G[0].r_addend;
+    }
+
+    // The remaining relocations.
+    encodeSLEB128(G.size() - 1, OS);
+    encodeSLEB128(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
+                      RELOCATION_GROUPED_BY_INFO_FLAG | HasAddendIfRela,
+                  OS);
+    encodeSLEB128(Config->Wordsize, OS);
+    encodeSLEB128(Target->RelativeRel, OS);
+    if (Config->IsRela) {
+      for (auto I = G.begin() + 1, E = G.end(); I != E; ++I) {
+        encodeSLEB128(I->r_addend - Addend, OS);
+        Addend = I->r_addend;
+      }
+    }
+
+    Offset = G.back().r_offset;
+  }
+
+  // Now the ungrouped relatives.
+  if (!UngroupedRelatives.empty()) {
+    encodeSLEB128(UngroupedRelatives.size(), OS);
+    encodeSLEB128(RELOCATION_GROUPED_BY_INFO_FLAG | HasAddendIfRela, OS);
+    encodeSLEB128(Target->RelativeRel, OS);
+    for (Elf_Rela &R : UngroupedRelatives) {
+      encodeSLEB128(R.r_offset - Offset, OS);
+      Offset = R.r_offset;
+      if (Config->IsRela) {
+        encodeSLEB128(R.r_addend - Addend, OS);
+        Addend = R.r_addend;
+      }
+    }
+  }
+
+  // Finally the non-relative relocations.
+  std::sort(NonRelatives.begin(), NonRelatives.end(),
+            [](const Elf_Rela &A, const Elf_Rela &B) {
+              return A.r_offset < B.r_offset;
+            });
+  if (!NonRelatives.empty()) {
+    encodeSLEB128(NonRelatives.size(), OS);
+    encodeSLEB128(HasAddendIfRela, OS);
+    for (Elf_Rela &R : NonRelatives) {
+      encodeSLEB128(R.r_offset - Offset, OS);
+      Offset = R.r_offset;
+      encodeSLEB128(R.r_info, OS);
+      if (Config->IsRela) {
+        encodeSLEB128(R.r_addend - Addend, OS);
+        Addend = R.r_addend;
+      }
+    }
+  }
+
+  // Returns whether the section size changed. We need to keep recomputing both
+  // section layout and the contents of this section until the size converges
+  // because changing this section's size can affect section layout, which in
+  // turn can affect the sizes of the LEB-encoded integers stored in this
+  // section.
+  return RelocData.size() != OldSize;
 }
 
 SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &StrTabSec)
     : SyntheticSection(StrTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,
                        StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
                        Config->Wordsize,
                        StrTabSec.isDynamic() ? ".dynsym" : ".symtab"),
       StrTabSec(StrTabSec) {}

 template class elf::DynamicSection<ELF64LE>;
 template class elf::DynamicSection<ELF64BE>;
 
 template class elf::RelocationSection<ELF32LE>;
 template class elf::RelocationSection<ELF32BE>;
 template class elf::RelocationSection<ELF64LE>;
 template class elf::RelocationSection<ELF64BE>;
 
+template class elf::AndroidPackedRelocationSection<ELF32LE>;
+template class elf::AndroidPackedRelocationSection<ELF32BE>;
+template class elf::AndroidPackedRelocationSection<ELF64LE>;
+template class elf::AndroidPackedRelocationSection<ELF64BE>;
+
 template class elf::SymbolTableSection<ELF32LE>;
 template class elf::SymbolTableSection<ELF32BE>;
 template class elf::SymbolTableSection<ELF64LE>;
 template class elf::SymbolTableSection<ELF64BE>;
 
 template class elf::VersionTableSection<ELF32LE>;
 template class elf::VersionTableSection<ELF32BE>;
 template class elf::VersionTableSection<ELF64LE>;

lld/trunk/ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::createSyntheticSections() {
   // Initialize all pointers with NULL. This is needed because
   // you can call lld::elf::main more than once as a library.
   memset(&Out::First, 0, sizeof(Out));
 
   auto Add = [](InputSectionBase *Sec) { InputSections.push_back(Sec); };
 
   InX::DynStrTab = make<StringTableSection>(".dynstr", true);
   InX::Dynamic = make<DynamicSection<ELFT>>();
+  if (Config->AndroidPackDynRelocs) {
+    In<ELFT>::RelaDyn = make<AndroidPackedRelocationSection<ELFT>>(
+        Config->IsRela ? ".rela.dyn" : ".rel.dyn");
+  } else {
     In<ELFT>::RelaDyn = make<RelocationSection<ELFT>>(
         Config->IsRela ? ".rela.dyn" : ".rel.dyn", Config->ZCombreloc);
+  }
   InX::ShStrTab = make<StringTableSection>(".shstrtab", false);
 
   Out::ElfHeader = make<OutputSection>("", 0, SHF_ALLOC);
   Out::ElfHeader->Size = sizeof(Elf_Ehdr);
   Out::ProgramHeaders = make<OutputSection>("", 0, SHF_ALLOC);
   Out::ProgramHeaders->Alignment = Config->Wordsize;
 
   if (needsInterpSection()) {
template <class ELFT> void Writer<ELFT>::createSyntheticSections() {
 
   // We always need to add rel[a].plt to output if it has entries.
   // Even for static linking it can contain R_[*]_IRELATIVE relocations.
   In<ELFT>::RelaPlt = make<RelocationSection<ELFT>>(
       Config->IsRela ? ".rela.plt" : ".rel.plt", false /*Sort*/);
   Add(In<ELFT>::RelaPlt);
 
   // The RelaIplt immediately follows .rel.plt (.rel.dyn for ARM) to ensure
-  // that the IRelative relocations are processed last by the dynamic loader
+  // that the IRelative relocations are processed last by the dynamic loader.
+  // We cannot place the iplt section in .rel.dyn when Android relocation
+  // packing is enabled because that would cause a section type mismatch.
+  // However, because the Android dynamic loader reads .rel.plt after .rel.dyn,
+  // we can get the desired behaviour by placing the iplt section in .rel.plt.
   In<ELFT>::RelaIplt = make<RelocationSection<ELFT>>(
-      (Config->EMachine == EM_ARM) ? ".rel.dyn" : In<ELFT>::RelaPlt->Name,
+      (Config->EMachine == EM_ARM && !Config->AndroidPackDynRelocs)
+          ? ".rel.dyn"
+          : In<ELFT>::RelaPlt->Name,
       false /*Sort*/);
   Add(In<ELFT>::RelaIplt);
 
   InX::Plt = make<PltSection>(Target->PltHeaderSize);
   Add(InX::Plt);
   InX::Iplt = make<PltSection>(0);
   Add(InX::Iplt);
 
applySynthetic({InX::DynSymTab,     InX::Bss,          InX::BssRelRo,
                  [](SyntheticSection *SS) { SS->finalizeContents(); });
 
   if (!Script->HasSectionsCommand && !Config->Relocatable)
     fixSectionAlignments();
 
   // Some architectures use small displacements for jump instructions.
   // It is linker's responsibility to create thunks containing long
   // jump instructions if jump targets are too far. Create thunks.
-  if (Target->NeedsThunks) {
+  if (Target->NeedsThunks || Config->AndroidPackDynRelocs) {
     ThunkCreator TC;
+    bool Changed;
+    do {
       Script->assignAddresses();
-    while (TC.createThunks(OutputSections)) {
-      applySynthetic({InX::MipsGot},
-                     [](SyntheticSection *SS) { SS->updateAllocSize(); });
-      Script->assignAddresses();
-    }
+      Changed = false;
+      if (Target->NeedsThunks)
+        Changed |= TC.createThunks(OutputSections);
+      if (InX::MipsGot)
+        InX::MipsGot->updateAllocSize();
+      Changed |= In<ELFT>::RelaDyn->updateAllocSize();
+    } while (Changed);
   }
 
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
 

lld/trunk/test/ELF/pack-dyn-relocs.s

+// REQUIRES: arm, aarch64
+
+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %p/Inputs/arm-shared.s -o %t.a32.so.o
+// RUN: ld.lld -shared %t.a32.so.o -o %t.a32.so
+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t.a32
+// RUN: ld.lld -pie --pack-dyn-relocs=none %t.a32 %t.a32.so -o %t2.a32
+// RUN: llvm-readobj -relocations %t2.a32 | FileCheck --check-prefix=UNPACKED32 %s
+// RUN: ld.lld -pie --pack-dyn-relocs=android %t.a32 %t.a32.so -o %t3.a32
+// RUN: llvm-readobj -s -dynamic-table %t3.a32 | FileCheck --check-prefix=PACKED32-HEADERS %s
+// RUN: llvm-readobj -relocations %t3.a32 | FileCheck --check-prefix=PACKED32 %s
+
+// Unpacked should have the relative relocations in their natural order.
+// UNPACKED32:          0x1000 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1004 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1008 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x100C R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1010 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1014 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1018 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x101C R_ARM_RELATIVE - 0x0
+
+// UNPACKED32-NEXT:     0x1024 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1028 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x102C R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1030 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1034 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1038 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x103C R_ARM_RELATIVE - 0x0
+
+// UNPACKED32-NEXT:     0x1044 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1048 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x104C R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1050 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1054 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1058 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x105C R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1060 R_ARM_RELATIVE - 0x0
+// UNPACKED32-NEXT:     0x1064 R_ARM_RELATIVE - 0x0
+
+// UNPACKED32-NEXT:     0x1020 R_ARM_ABS32 bar2 0x0
+// UNPACKED32-NEXT:     0x1040 R_ARM_ABS32 zed2 0x0
+
+// PACKED32-HEADERS:       Index: 1
+// PACKED32-HEADERS-NEXT:  Name: .dynsym
+
+// PACKED32-HEADERS:       Name: .rel.dyn
+// PACKED32-HEADERS-NEXT:  Type: SHT_ANDROID_REL
+// PACKED32-HEADERS-NEXT:  Flags [ (0x2)
+// PACKED32-HEADERS-NEXT:    SHF_ALLOC (0x2)
+// PACKED32-HEADERS-NEXT:  ]
+// PACKED32-HEADERS-NEXT:  Address: [[ADDR:.*]]
+// PACKED32-HEADERS-NEXT:  Offset: [[ADDR]]
+// PACKED32-HEADERS-NEXT:  Size: [[SIZE:.*]]
+// PACKED32-HEADERS-NEXT:  Link: 1
+// PACKED32-HEADERS-NEXT:  Info: 0
+// PACKED32-HEADERS-NEXT:  AddressAlignment: 4
+// PACKED32-HEADERS-NEXT:  EntrySize: 1
+
+// PACKED32-HEADERS: 0x6000000F ANDROID_REL          [[ADDR]]
+// PACKED32-HEADERS: 0x60000010 ANDROID_RELSZ        [[SIZE]]
+
+// Packed should have the larger groups of relative relocations first,
+// i.e. the 8 and 9 followed by the 7.
+// PACKED32:          0x1000 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1004 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1008 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x100C R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1010 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1014 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1018 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x101C R_ARM_RELATIVE - 0x0
+
+// PACKED32-NEXT:     0x1044 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1048 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x104C R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1050 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1054 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1058 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x105C R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1060 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1064 R_ARM_RELATIVE - 0x0
+
+// PACKED32-NEXT:     0x1024 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1028 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x102C R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1030 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1034 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x1038 R_ARM_RELATIVE - 0x0
+// PACKED32-NEXT:     0x103C R_ARM_RELATIVE - 0x0
+
+// PACKED32-NEXT:     0x1020 R_ARM_ABS32 bar2 0x0
+// PACKED32-NEXT:     0x1040 R_ARM_ABS32 zed2 0x0
+
+// RUN: llvm-mc -filetype=obj -triple=aarch64-unknown-linux %p/Inputs/shared2.s -o %t.a64.so.o
+// RUN: ld.lld -shared %t.a64.so.o -o %t.a64.so
+// RUN: llvm-mc -filetype=obj -triple=aarch64-unknown-linux %s -o %t.a64
+// RUN: ld.lld -pie --pack-dyn-relocs=none %t.a64 %t.a64.so -o %t2.a64
+// RUN: llvm-readobj -relocations %t2.a64 | FileCheck --check-prefix=UNPACKED64 %s
+// RUN: ld.lld -pie --pack-dyn-relocs=android %t.a64 %t.a64.so -o %t3.a64
+// RUN: llvm-readobj -s -dynamic-table %t3.a64 | FileCheck --check-prefix=PACKED64-HEADERS %s
+// RUN: llvm-readobj -relocations %t3.a64 | FileCheck --check-prefix=PACKED64 %s
+
+// UNPACKED64:          0x10000 R_AARCH64_RELATIVE - 0x1
+// UNPACKED64-NEXT:     0x10008 R_AARCH64_RELATIVE - 0x2
+// UNPACKED64-NEXT:     0x10010 R_AARCH64_RELATIVE - 0x3
+// UNPACKED64-NEXT:     0x10018 R_AARCH64_RELATIVE - 0x4
+// UNPACKED64-NEXT:     0x10020 R_AARCH64_RELATIVE - 0x5
+// UNPACKED64-NEXT:     0x10028 R_AARCH64_RELATIVE - 0x6
+// UNPACKED64-NEXT:     0x10030 R_AARCH64_RELATIVE - 0x7
+// UNPACKED64-NEXT:     0x10038 R_AARCH64_RELATIVE - 0x8
+
+// UNPACKED64-NEXT:     0x10048 R_AARCH64_RELATIVE - 0x1
+// UNPACKED64-NEXT:     0x10050 R_AARCH64_RELATIVE - 0x2
+// UNPACKED64-NEXT:     0x10058 R_AARCH64_RELATIVE - 0x3
+// UNPACKED64-NEXT:     0x10060 R_AARCH64_RELATIVE - 0x4
+// UNPACKED64-NEXT:     0x10068 R_AARCH64_RELATIVE - 0x5
+// UNPACKED64-NEXT:     0x10070 R_AARCH64_RELATIVE - 0x6
+// UNPACKED64-NEXT:     0x10078 R_AARCH64_RELATIVE - 0x7
+
+// UNPACKED64-NEXT:     0x10088 R_AARCH64_RELATIVE - 0x1
+// UNPACKED64-NEXT:     0x10090 R_AARCH64_RELATIVE - 0x2
+// UNPACKED64-NEXT:     0x10098 R_AARCH64_RELATIVE - 0x3
+// UNPACKED64-NEXT:     0x100A0 R_AARCH64_RELATIVE - 0x4
+// UNPACKED64-NEXT:     0x100A8 R_AARCH64_RELATIVE - 0x5
+// UNPACKED64-NEXT:     0x100B0 R_AARCH64_RELATIVE - 0x6
+// UNPACKED64-NEXT:     0x100B8 R_AARCH64_RELATIVE - 0x7
+// UNPACKED64-NEXT:     0x100C0 R_AARCH64_RELATIVE - 0x8
+// UNPACKED64-NEXT:     0x100C8 R_AARCH64_RELATIVE - 0x9
+
+// UNPACKED64-NEXT:     0x10040 R_AARCH64_ABS64 bar2 0x1
+// UNPACKED64-NEXT:     0x10080 R_AARCH64_ABS64 zed2 0x0
+
+// PACKED64:          0x10000 R_AARCH64_RELATIVE - 0x1
+// PACKED64-NEXT:     0x10008 R_AARCH64_RELATIVE - 0x2
+// PACKED64-NEXT:     0x10010 R_AARCH64_RELATIVE - 0x3
+// PACKED64-NEXT:     0x10018 R_AARCH64_RELATIVE - 0x4
+// PACKED64-NEXT:     0x10020 R_AARCH64_RELATIVE - 0x5
+// PACKED64-NEXT:     0x10028 R_AARCH64_RELATIVE - 0x6
+// PACKED64-NEXT:     0x10030 R_AARCH64_RELATIVE - 0x7
+// PACKED64-NEXT:     0x10038 R_AARCH64_RELATIVE - 0x8
+
+// PACKED64-NEXT:     0x10088 R_AARCH64_RELATIVE - 0x1
+// PACKED64-NEXT:     0x10090 R_AARCH64_RELATIVE - 0x2
+// PACKED64-NEXT:     0x10098 R_AARCH64_RELATIVE - 0x3
+// PACKED64-NEXT:     0x100A0 R_AARCH64_RELATIVE - 0x4
+// PACKED64-NEXT:     0x100A8 R_AARCH64_RELATIVE - 0x5
+// PACKED64-NEXT:     0x100B0 R_AARCH64_RELATIVE - 0x6
+// PACKED64-NEXT:     0x100B8 R_AARCH64_RELATIVE - 0x7
+// PACKED64-NEXT:     0x100C0 R_AARCH64_RELATIVE - 0x8
+// PACKED64-NEXT:     0x100C8 R_AARCH64_RELATIVE - 0x9
+
+// PACKED64-NEXT:     0x10048 R_AARCH64_RELATIVE - 0x1
+// PACKED64-NEXT:     0x10050 R_AARCH64_RELATIVE - 0x2
+// PACKED64-NEXT:     0x10058 R_AARCH64_RELATIVE - 0x3
+// PACKED64-NEXT:     0x10060 R_AARCH64_RELATIVE - 0x4
+// PACKED64-NEXT:     0x10068 R_AARCH64_RELATIVE - 0x5
+// PACKED64-NEXT:     0x10070 R_AARCH64_RELATIVE - 0x6
+// PACKED64-NEXT:     0x10078 R_AARCH64_RELATIVE - 0x7
+
+// PACKED64-NEXT:     0x10040 R_AARCH64_ABS64 bar2 0x1
+// PACKED64-NEXT:     0x10080 R_AARCH64_ABS64 zed2 0x0
+
+// PACKED64-HEADERS:       Index: 1
+// PACKED64-HEADERS-NEXT:  Name: .dynsym
+
+// PACKED64-HEADERS:       Name: .rela.dyn
+// PACKED64-HEADERS-NEXT:  Type: SHT_ANDROID_RELA
+// PACKED64-HEADERS-NEXT:  Flags [ (0x2)
+// PACKED64-HEADERS-NEXT:    SHF_ALLOC (0x2)
+// PACKED64-HEADERS-NEXT:  ]
+// PACKED64-HEADERS-NEXT:  Address: [[ADDR:.*]]
+// PACKED64-HEADERS-NEXT:  Offset: [[ADDR]]
+// PACKED64-HEADERS-NEXT:  Size: [[SIZE:.*]]
+// PACKED64-HEADERS-NEXT:  Link: 1
+// PACKED64-HEADERS-NEXT:  Info: 0
+// PACKED64-HEADERS-NEXT:  AddressAlignment: 8
+// PACKED64-HEADERS-NEXT:  EntrySize: 1
+
+// PACKED64-HEADERS: 0x0000000060000011 ANDROID_RELA          [[ADDR]]
+// PACKED64-HEADERS: 0x0000000060000012 ANDROID_RELASZ        [[SIZE]]
+
+.data
+.dc.a __ehdr_start + 1
+.dc.a __ehdr_start + 2
+.dc.a __ehdr_start + 3
+.dc.a __ehdr_start + 4
+.dc.a __ehdr_start + 5
+.dc.a __ehdr_start + 6
+.dc.a __ehdr_start + 7
+.dc.a __ehdr_start + 8
+.dc.a bar2 + 1
+
+.dc.a __ehdr_start + 1
+.dc.a __ehdr_start + 2
+.dc.a __ehdr_start + 3
+.dc.a __ehdr_start + 4
+.dc.a __ehdr_start + 5
+.dc.a __ehdr_start + 6
+.dc.a __ehdr_start + 7
+.dc.a zed2
+
+.dc.a __ehdr_start + 1
+.dc.a __ehdr_start + 2
+.dc.a __ehdr_start + 3
+.dc.a __ehdr_start + 4
+.dc.a __ehdr_start + 5
+.dc.a __ehdr_start + 6
+.dc.a __ehdr_start + 7
+.dc.a __ehdr_start + 8
+.dc.a __ehdr_start + 9

llvm/trunk/lib/Object/ELF.cpp

switch (Type) {
     STRINGIFY_ENUM_CASE(ELF, SHT_REL);
     STRINGIFY_ENUM_CASE(ELF, SHT_SHLIB);
     STRINGIFY_ENUM_CASE(ELF, SHT_DYNSYM);
     STRINGIFY_ENUM_CASE(ELF, SHT_INIT_ARRAY);
     STRINGIFY_ENUM_CASE(ELF, SHT_FINI_ARRAY);
     STRINGIFY_ENUM_CASE(ELF, SHT_PREINIT_ARRAY);
     STRINGIFY_ENUM_CASE(ELF, SHT_GROUP);
     STRINGIFY_ENUM_CASE(ELF, SHT_SYMTAB_SHNDX);
+    STRINGIFY_ENUM_CASE(ELF, SHT_ANDROID_REL);
+    STRINGIFY_ENUM_CASE(ELF, SHT_ANDROID_RELA);
     STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_ODRTAB);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_ATTRIBUTES);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_HASH);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_verdef);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_verneed);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_versym);
   default:
     return "Unknown";

llvm/trunk/tools/llvm-readobj/ELFDumper.cpp

case EM_MIPS:
     LLVM_READOBJ_TYPE_CASE(MIPS_UNREFEXTNO);
     LLVM_READOBJ_TYPE_CASE(MIPS_GOTSYM);
     LLVM_READOBJ_TYPE_CASE(MIPS_RLD_MAP);
     LLVM_READOBJ_TYPE_CASE(MIPS_PLTGOT);
     LLVM_READOBJ_TYPE_CASE(MIPS_OPTIONS);
     }
   }
   switch (Type) {
+  LLVM_READOBJ_TYPE_CASE(ANDROID_REL);
+  LLVM_READOBJ_TYPE_CASE(ANDROID_RELSZ);
+  LLVM_READOBJ_TYPE_CASE(ANDROID_RELA);
+  LLVM_READOBJ_TYPE_CASE(ANDROID_RELASZ);
   LLVM_READOBJ_TYPE_CASE(BIND_NOW);
   LLVM_READOBJ_TYPE_CASE(DEBUG);
   LLVM_READOBJ_TYPE_CASE(FINI);
   LLVM_READOBJ_TYPE_CASE(FINI_ARRAY);
   LLVM_READOBJ_TYPE_CASE(FINI_ARRAYSZ);
   LLVM_READOBJ_TYPE_CASE(FLAGS);
   LLVM_READOBJ_TYPE_CASE(FLAGS_1);
   LLVM_READOBJ_TYPE_CASE(HASH);
void ELFDumper<ELFT>::printValue(uint64_t Type, uint64_t Value) {
   case DT_RELAENT:
   case DT_STRSZ:
   case DT_SYMENT:
   case DT_RELSZ:
   case DT_RELENT:
   case DT_INIT_ARRAYSZ:
   case DT_FINI_ARRAYSZ:
   case DT_PREINIT_ARRAYSZ:
+  case DT_ANDROID_RELSZ:
+  case DT_ANDROID_RELASZ:
     OS << Value << " (bytes)";
     break;
   case DT_NEEDED:
     printLibrary(OS, "Shared library", getDynamicString(Value));
     break;
   case DT_SONAME:
     printLibrary(OS, "Library soname", getDynamicString(Value));
     break;