[ELF] Support --pack-dyn-relocs=rel+relr

[mcgrathr]

Summary

This rewrites RELA to REL as well as generating RELR. This is a
more compact representation for dynamic linker ABIs that support
both REL and RELA encodings (such as Fuchsia's).

[mcgrathr]

I'm not sure what all tests this should have. It was surprisingly easy to implement and seems to work perfectly. I've done a Fuchsia build with it that shows binaries that look as they should by eyeball, though I haven't yet tested it at runtime.

[mcgrathr]

Oh, and perhaps I'll update that comment since we do know why ELF specified RELA in the first place, which is for general-case reloc types for machines not like x86, where some reloc types don't apply to locations that store as many bits as the full address size that the addend can be in the general case. When you have TEXTRELs, then any dynamic reloc can also be such a type. For newer ABIs that never allowed TEXTRELs, I think people just assumed that the encoding for dynamic relocs should match the encoding for ET_REL relocs without thinking about it deeply. In the ABIs we're concerned with today, the only narrow reloc type that might appear as a dynamic reloc is ABS32 in ELFCLASS64, but limiting addends to 32 bits is no more limiting than the rules of the small memory model, so you just wouldn't use rela->rel encoding with large memory model (or you could punt only for specific programs when you hit an out of range addend for real, which seems unlikely). (A similar constraint has always been tolerated for R_ARM_MOV[WT]* relocs where EM_ARM is canonically REL rather than RELA and so addends used in relocs for movw/movt instructions are limited to 16 bits though the address computation is always a full 32 bit computation before the reloc stores the high or low 16 bits.)

[mcgrathr]

Also note that compatible dynamic linkers support not just either, but both in the same executable (though the format requires that only one or the other be the format for PLT relocs, but those never need addends anyway). So for the large model case one could theoretically produce RELA for any relocs whose addend is too large for the bits available in the relocated entity while still producing REL for everything that fits. (The need ever to support large addends in the real world seems unlikely, but just saying.)

[MaskRay]

I haven't thought much on this yet. First impression: why isn't the RELA->REL toggle a new option? It does not seem to fit with the rest of --pack-dyn-relocs which selects Android packed dynamic relocations or RELR or both.

Regarding tests, you can add llvm-readelf -S RUN lines to check .rel.dyn or .rela.dyn. See some newly touched test files.

musl ld.so supports both REL and RELA. I can probably finish the patch and test it on musl.

[mcgrathr]

In D79664#2028262, @MaskRay wrote:

I haven't thought much on this yet. First impression: why isn't the RELA->REL toggle a new option? It does not seem to fit with the rest of --pack-dyn-relocs which selects Android packed dynamic relocations or RELR or both.

--pack-dyn-relocs seems exactly appropriate to me since it's about packing the dynamic relocs. It does RELA->REL conversion just as the existing option does REL(A)->RELR conversion. But I'm not concerned with the switch syntax. I'm fine with whatever syntax people prefer. (For example, I don't at all think it's important to disallow the RELA->REL conversion without RELR support, I just don't care about that mode at all.) I probably wouldn't have added --pack-dyn-relocs with its string syntax in the first place, but instead just added separate -z android-relocs and -z relr switches so the new one would be -z rel or something. But given --pack-dyn-relocs exists, it seems like the natural place for this to me now.

Regarding tests, you can add llvm-readelf -S RUN lines to check .rel.dyn or .rela.dyn. See some newly touched test files.

musl ld.so supports both REL and RELA. I can probably finish the patch and test it on musl.

Thanks very much! Fuchsia's current dynamic linker is a (distant) fork from musl and supports both as well. I haven't looked at musl lately so perhaps it hasn't added RELR support as Fuchsia did (where RELR encoding is the preferred default). So using and testing with musl (or older musl) might be a good reason to support doing RELA->REL encoding without doing RELR encoding.

[grimar]

In D79664#2028360, @mcgrathr wrote:

In D79664#2028262, @MaskRay wrote:

I haven't thought much on this yet. First impression: why isn't the RELA->REL toggle a new option? It does not seem to fit with the rest of --pack-dyn-relocs which selects Android packed dynamic relocations or RELR or both.

--pack-dyn-relocs seems exactly appropriate to me since it's about packing the dynamic relocs. It does RELA->REL conversion just as the existing option does REL(A)->RELR conversion. But I'm not concerned with the switch syntax. I'm fine with whatever syntax people prefer. (For example, I don't at all think it's important to disallow the RELA->REL conversion without RELR support, I just don't care about that mode at all.) I probably wouldn't have added --pack-dyn-relocs with its string syntax in the first place, but instead just added separate -z android-relocs and -z relr switches so the new one would be -z rel or something. But given --pack-dyn-relocs exists, it seems like the natural place for this to me now.

I am inclined to agree. I've added a few suggestions about the code.

lld/ELF/Driver.cpp

743

aside: I wonder why we support "android+relr", but not "android,relr". The latter form looks more natural to me.

755

Its a bit hard to read a tuple of 3 bools probably? Perhaps I'd do the same what we do for -hash-style.
(See "Parse -hash-style={sysv,gnu,both}.") below.

I.e. I'd:

1. Inline this method.
2. Set config->androidPackDynRelocs, config->relrPackDynRelocs, config->relPackDynRelocs to false by default.

And do something similar to what -hash-style does:

// Parse -hash-style={sysv,gnu,both}.
if (auto *arg = args.getLastArg(OPT_pack_dyn_relocs)) {
  StringRef s = arg->getValue();
  if (s.startsWith("android")) {
    config->androidPackDynRelocs = true;
    // Check "+relr" ..
  } else if ...
  ....
}

1222

This comment have double spaces after full stops.

1235

I believe usually we assign config variables once. So it could be:

config->isRela = !config->relPackDynRelocs && ...

[arichardson]

lld/ELF/Driver.cpp

743

I agree. How about allowing comma-separated list where the order does not matter?

746

I don't think it makes sense to omit an option because it might be a typo.
I doubt many people will manually pass -Wl,--pack-dyn-relocs=, it will probably come from some build system default.
Those who pass it manually probably know to check the output binary to see if worked as expected.

I would quite like to see the plain rel option since it's useful on platforms that don't have RELR and also useful for LLD tests to check that we always write addends in REL format.
I noticed quite a few bugs in the RELA->REL conversion in the past (I have been working mostly with MIPS where clang emits RELA, but LLD converts them to REL). Having this conversion would allow writing tests that don't depend on MIPS.

[grimar]

lld/ELF/Driver.cpp

743

It would look better to me.

[MaskRay]

I probably wouldn't have added --pack-dyn-relocs with its string syntax in the first place, but instead just added separate -z android-relocs and -z relr switches so the new one would be -z rel or something. But given --pack-dyn-relocs exists, it seems like the natural place for this to me now.

I learned that -z is reserved for ELF specific options in GNU ld. So, -z would indeed be more suitable. -z rel may be a good name. Are you going to create a feature request on GNU ld side:) ?

Thanks very much! Fuchsia's current dynamic linker is a (distant) fork from musl and supports both as well. I haven't looked at musl lately so perhaps it hasn't added RELR support as Fuchsia did (where RELR encoding is the preferred default). So using and testing with musl (or older musl) might be a good reason to support doing RELA->REL encoding without doing RELR encoding.

I even posted a musl patch last year, but it could not be accepted because RELR is not in the standard. (https://groups.google.com/forum/#!topic/generic-abi/9OO5vhxb00Y "Ongoing Maintenance of the gABI" might make the situation better.)

-z rel does not need to be coupled with RELR and it has its own usefulness which can be easily justified. Dynamic relocations usually have 0 addend. GLOB_DAT, J[U]MP_SLOT and COPY always have 0 addend and do not need to read the implicit addend. The symbolic absolute relocation type usually has 0 addend. Unfortunately FreeBSD rtld and glibc ld.so are structured in the way that supporting both REL and RELA is not out-of-the-box.

lld/ELF/Driver.cpp

743

Note, in compiler drivers (GCC+clang), -Wl, does not have escapes for commas, so commas in the linker generally does not work well.

[arichardson]

lld/ELF/Driver.cpp

743

That is a good very good reason not to use ,.
Maybe allowing the option multiple times is the best solution. Or if that is too verbose, + or : as a separator should be fine.
I would also prefer if we didn't require a fixed order: why should rel+relr be accepted but not relr+rel?

[mcgrathr]

If people are agreed, I think separate -z rel, -z relr, and -z android-relocs flags that operate independent makes the most sense. The existing --pack-dyn-relocs can be accepted for compatibility, but need not get any new supported values.

[MaskRay]

In D79664#2032775, @mcgrathr wrote:

If people are agreed, I think separate -z rel, -z relr, and -z android-relocs flags that operate independent makes the most sense. The existing --pack-dyn-relocs can be accepted for compatibility, but need not get any new supported values.

-z rel and -z relr look good to me. I created D80496 for -z rel and -z rela. (It should work out of the box with --pack-dyn-relocs=android)

I don't know how the magic APS2 was picked but I think the -z option for Android packed relocation section can mention the magic, i.e. -z pack-dyn-relocs=APS2 or similar. @danalbert

On the GNU ld side, I created https://sourceware.org/pipermail/binutils/2020-May/111086.html but there has been no response ¯\_(ツ)_/¯

[MaskRay]

Seems that this can be closed because D80496 landed.

[mcgrathr]

obviated by -z rel

lld/ELF/Config.h

struct Configuration {
   bool omagic;
   bool optimizeBBJumps;
   bool optRemarksWithHotness;
   bool picThunk;
   bool pie;
   bool printGcSections;
   bool printIcfSections;
   bool relocatable;
+  bool relPackDynRelocs;
   bool relrPackDynRelocs;
   bool saveTemps;
   llvm::Optional<uint32_t> shuffleSectionSeed;
   bool singleRoRx;
   bool shared;
   bool isStatic = false;
   bool sysvHash = false;
   bool target1Rel;

lld/ELF/Driver.cpp

getBuildId(opt::InputArgList &args) {
   if (s.startswith("0x"))
     return {BuildIdKind::Hexstring, parseHex(s.substr(2))};
 
   if (s != "none")
     error("unknown --build-id style: " + s);
   return {BuildIdKind::None, {}};
 }
 
-static std::pair<bool, bool> getPackDynRelocs(opt::InputArgList &args) {
+static std::tuple<bool, bool, bool> getPackDynRelocs(opt::InputArgList &args) {
   StringRef s = args.getLastArgValue(OPT_pack_dyn_relocs, "none");
   if (s == "android")
-    return {true, false};
+    return {true, false, false};
   if (s == "relr")
-    return {false, true};
+    return {false, true, false};
+  // Note there is no plain "rel" option here since rela->rel rewriting is
+  // motivated by space savings and relr is the biggest win for that, so "rel"
+  // alone is more likely to be a typo for "relr" than an intentional selection
+  // of rela->rel without relr.
+  if (s == "rel+relr")
+    return {false, true, true};
   if (s == "android+relr")
-    return {true, true};
+    return {true, true, false};
 
   if (s != "none")
     error("unknown -pack-dyn-relocs format: " + s);
-  return {false, false};
+  return {false, false, false};
 }
 
 static void readCallGraph(MemoryBufferRef mb) {
   // Build a map from symbol name to section
   DenseMap<StringRef, Symbol *> map;
   for (InputFile *file : objectFiles)
     for (Symbol *sym : file->getSymbols())
       map[sym->getName()] = sym;
 
static void readConfigs(opt::InputArgList &args) {
   // Page alignment can be disabled by the -n (--nmagic) and -N (--omagic).
   // As PT_GNU_RELRO relies on Paging, do not create it when we have disabled
   // it.
   if (config->nmagic || config->omagic)
     config->zRelro = false;
 
   std::tie(config->buildId, config->buildIdVector) = getBuildId(args);
 
-  std::tie(config->androidPackDynRelocs, config->relrPackDynRelocs) =
-      getPackDynRelocs(args);
+  std::tie(config->androidPackDynRelocs, config->relrPackDynRelocs,
+           config->relPackDynRelocs) = getPackDynRelocs(args);
 
   if (auto *arg = args.getLastArg(OPT_symbol_ordering_file)){
     if (args.hasArg(OPT_call_graph_ordering_file))
       error("--symbol-ordering-file and --call-graph-order-file "
             "may not be used together");
     if (Optional<MemoryBufferRef> buffer = readFile(arg->getValue())){
       config->symbolOrderingFile = getSymbolOrderingFile(*buffer);
       // Also need to disable CallGraphProfileSort to prevent
static void setConfigs(opt::InputArgList &args) {
   //  Rel:  Addends are stored to the location where relocations are applied.
   //  Rela: Addends are stored as part of relocation entry.
   //
   // In other words, Rela makes it easy to read addends at the price of extra
   // 4 or 8 byte for each relocation entry. We don't know why ELF defined two
   // different mechanisms in the first place, but this is how the spec is
   // defined.
   //
-  // You cannot choose which one, Rel or Rela, you want to use. Instead each
-  // ABI defines which one you need to use. The following expression expresses
-  // that.
+  // The psABI for each processor specifies the canonical one to use.  The
+  // following expression expresses that.  But actual compatibility depends on
+  // the dynamic linker implementation (some can handle either format), so when
+  // targetting a particular OS environment with known dynamic linking ABI
+  // support, a contrary choice can be made.  The REL format is more compact,
+  // and when TEXTRELs are not supported, all the dynamic relocation types that
+  // can be emitted encode their in-section addends straightforwardly with
+  // sufficient range for all cases supported by the small memory model (or
+  // never have addends at all, such as GLOB_DAT and JMP_SLOT).
   config->isRela = m == EM_AARCH64 || m == EM_AMDGPU || m == EM_HEXAGON ||
                    m == EM_PPC || m == EM_PPC64 || m == EM_RISCV ||
                    m == EM_X86_64;
+  if (config->relPackDynRelocs)
+    config->isRela = false;
 
   // If the output uses REL relocations we must store the dynamic relocation
   // addends to the output sections. We also store addends for RELA relocations
   // if --apply-dynamic-relocs is used.
   // We default to not writing the addends when using RELA relocations since
   // any standard conforming tool can find it in r_addend.
   config->writeAddends = args.hasFlag(OPT_apply_dynamic_relocs,
                                       OPT_no_apply_dynamic_relocs, false) ||

lld/ELF/Options.td

 def omagic: FF<"omagic">, MetaVarName<"<magic>">,
   HelpText<"Set the text and data sections to be readable and writable, do not page align sections, link against static libraries">;
 
 defm orphan_handling:
   Eq<"orphan-handling", "Control how orphan sections are handled when linker script used">;
 
 defm pack_dyn_relocs:
   Eq<"pack-dyn-relocs", "Pack dynamic relocations in the given format">,
-  MetaVarName<"[none,android,relr,android+relr]">;
+  MetaVarName<"[none,android,relr,rel+relr,android+relr]">;
 
 defm use_android_relr_tags: B<"use-android-relr-tags",
     "Use SHT_ANDROID_RELR / DT_ANDROID_RELR* tags instead of SHT_RELR / DT_RELR*",
     "Use SHT_RELR / DT_RELR* tags (default)">;
 
 def pic_veneer: F<"pic-veneer">,
   HelpText<"Always generate position independent thunks (veneers)">;