[PATCH v4] BaseTools/GenFw: Add X64 GOTPCREL Support to GenFw

[Zenith432 <zenith432@users.sourceforge.net>]

Adds support for the following X64 ELF relocations to GenFw
  R_X86_64_GOTPCREL
  R_X86_64_GOTPCRELX
  R_X86_64_REX_GOTPCRELX

Background:
The GCC49 and GCC5 toolchains use the small pie model for X64.  In the
small pie model, gcc emits a GOTPCREL relocation whenever C code takes
the address of a global function.  The emission of GOTPCREL is mitigated
by several factors
1. In GCC49, all global symbols are declared hidden thereby eliminating
the emission of GOTPCREL.
2. In GCC5, LTO is used.  In LTO, the complier first creates intermediate
representation (IR) files.  During the static link stage, the LTO compiler
combines all IR files as a single compilation unit, using linker symbol
assistance to generate code.  Any global symbols defined in the IR that
are not referenced from outside the IR are converted to local symbols -
thereby eliminating the emission of GOTPCREL for them.
3. The linker (binutils ld) further transforms any GOTPCREL used with
the movq opcode to a direct rip-relative relocation used with the leaq
opcode.  This linker optimization can be disabled with the option
-Wl,--no-relax.  Furthermore, gcc is able to emit GOTPCREL with other
opcodes
  - pushq opcode for passing arguments to functions.
  - addq/subq opcodes for pointer arithmetic.
These other opcode uses are not transformed by the linker.
Ultimately, in GCC5 there are some emissions of GOTPCREL that survive
all these mitigations - if C code takes the address of a global function
defined in assembly code - and performs pointer arithmetic on the
address - then the GOTPCREL remains in the final linker product.
A GOTPCREL relocation today causes the build to stop since GenFw does
not handle them.  It is possible to eliminate any remaining GOTPCREL
emissions by manually declaring the global symbols causing them to have
hidden visibility.  This patch is offered instead to allow GenFw to
handle any residual GOTPCREL.

Cc: Shi Steven <steven.shi@intel.com>
Cc: Yonghong Zhu <yonghong.zhu@intel.com>
Cc: Liming Gao <liming.gao@intel.com>
Contributed-under: TianoCore Contribution Agreement 1.1
Signed-off-by: Zenith432 <zenith432@users.sourceforge.net>
---
 BaseTools/Source/C/GenFw/Elf64Convert.c | 203 +++++++++++++++++++++++-
 BaseTools/Source/C/GenFw/elf_common.h   |  17 ++
 2 files changed, 219 insertions(+), 1 deletion(-)

diff --git a/BaseTools/Source/C/GenFw/Elf64Convert.c b/BaseTools/Source/C/GenFw/Elf64Convert.c
index 4636cfee..90351125 100644
--- a/BaseTools/Source/C/GenFw/Elf64Convert.c
+++ b/BaseTools/Source/C/GenFw/Elf64Convert.c
@@ -94,6 +94,15 @@ STATIC Elf_Ehdr *mEhdr;
 STATIC Elf_Shdr *mShdrBase;
 STATIC Elf_Phdr *mPhdrBase;
 
+//
+// GOT information
+//
+STATIC Elf_Shdr *mGOTShdr = NULL;
+STATIC UINT32   mGOTShindex = 0;
+STATIC UINT32   *mGOTCoffEntries = NULL;
+STATIC UINT32   mGOTMaxCoffEntries = 0;
+STATIC UINT32   mGOTNumCoffEntries = 0;
+
 //
 // Coff information
 //
@@ -322,6 +331,134 @@ GetSymName (
   return StrtabContents + Sym->st_name;
 }
 
+//
+// Find the ELF section hosting the GOT from an ELF Rva
+//   of a single GOT entry.  Normally, GOT is placed in
+//   ELF .text section, so assume once we find in which
+//   section the GOT is, all GOT entries are there, and
+//   just verify this.
+//
+STATIC
+VOID
+FindElfGOTSectionFromGOTEntryElfRva (
+  Elf64_Addr GOTEntryElfRva
+  )
+{
+  UINT32 i;
+  if (mGOTShdr != NULL) {
+    if (GOTEntryElfRva >= mGOTShdr->sh_addr &&
+        GOTEntryElfRva <  mGOTShdr->sh_addr + mGOTShdr->sh_size) {
+      return;
+    }
+    Error (NULL, 0, 3000, "Unsupported", "FindElfGOTSectionFromGOTEntryElfRva: GOT entries found in multiple sections.");
+    exit(EXIT_FAILURE);
+  }
+  for (i = 0; i < mEhdr->e_shnum; i++) {
+    Elf_Shdr *shdr = GetShdrByIndex(i);
+    if (GOTEntryElfRva >= shdr->sh_addr &&
+        GOTEntryElfRva <  shdr->sh_addr + shdr->sh_size) {
+      mGOTShdr = shdr;
+      mGOTShindex = i;
+      return;
+    }
+  }
+  Error (NULL, 0, 3000, "Invalid", "FindElfGOTSectionFromGOTEntryElfRva: ElfRva 0x%016LX for GOT entry not found in any section.", GOTEntryElfRva);
+  exit(EXIT_FAILURE);
+}
+
+//
+// Stores locations of GOT entries in COFF image.
+//   Returns TRUE if GOT entry is new.
+//   Simple implementation as number of GOT
+//   entries is expected to be low.
+//
+
+STATIC
+BOOLEAN
+AccumulateCoffGOTEntries (
+  UINT32 GOTCoffEntry
+  )
+{
+  UINT32 i;
+  if (mGOTCoffEntries != NULL) {
+    for (i = 0; i < mGOTNumCoffEntries; i++) {
+      if (mGOTCoffEntries[i] == GOTCoffEntry) {
+        return FALSE;
+      }
+    }
+  }
+  if (mGOTCoffEntries == NULL) {
+    mGOTCoffEntries = (UINT32*)malloc(5 * sizeof *mGOTCoffEntries);
+    if (mGOTCoffEntries == NULL) {
+      Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
+    }
+    assert (mGOTCoffEntries != NULL);
+    mGOTMaxCoffEntries = 5;
+    mGOTNumCoffEntries = 0;
+  } else if (mGOTNumCoffEntries == mGOTMaxCoffEntries) {
+    mGOTCoffEntries = (UINT32*)realloc(mGOTCoffEntries, 2 * mGOTMaxCoffEntries * sizeof *mGOTCoffEntries);
+    if (mGOTCoffEntries == NULL) {
+      Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
+    }
+    assert (mGOTCoffEntries != NULL);
+    mGOTMaxCoffEntries += mGOTMaxCoffEntries;
+  }
+  mGOTCoffEntries[mGOTNumCoffEntries++] = GOTCoffEntry;
+  return TRUE;
+}
+
+//
+// 32-bit Unsigned integer comparator for qsort.
+//
+STATIC
+int
+UINT32Comparator (
+  const void* lhs,
+  const void* rhs
+  )
+{
+  if (*(const UINT32*)lhs < *(const UINT32*)rhs) {
+    return -1;
+  }
+  return *(const UINT32*)lhs > *(const UINT32*)rhs;
+}
+
+//
+// Emit accumulated Coff GOT entry relocations into
+//   Coff image.  This function performs its job
+//   once and then releases the entry list, so
+//   it can safely be called multiple times.
+//
+STATIC
+VOID
+EmitGOTRelocations (
+  VOID
+  )
+{
+  UINT32 i;
+  if (mGOTCoffEntries == NULL) {
+    return;
+  }
+  //
+  // Emit Coff relocations with Rvas ordered.
+  //
+  qsort(
+    mGOTCoffEntries,
+    mGOTNumCoffEntries,
+    sizeof *mGOTCoffEntries,
+    UINT32Comparator);
+  for (i = 0; i < mGOTNumCoffEntries; i++) {
+    VerboseMsg ("EFI_IMAGE_REL_BASED_DIR64 Offset: 0x%08X", mGOTCoffEntries[i]);
+    CoffAddFixup(
+      mGOTCoffEntries[i],
+      EFI_IMAGE_REL_BASED_DIR64);
+  }
+  free(mGOTCoffEntries);
+  mGOTCoffEntries = NULL;
+  mGOTMaxCoffEntries = 0;
+  mGOTNumCoffEntries = 0;
+}
+
 //
 // Elf functions interface implementation
 //
@@ -643,6 +780,7 @@ WriteSections64 (
   Elf_Shdr    *SecShdr;
   UINT32      SecOffset;
   BOOLEAN     (*Filter)(Elf_Shdr *);
+  Elf64_Addr  GOTEntryRva;
 
   //
   // Initialize filter pointer
@@ -710,7 +848,7 @@ WriteSections64 (
     // section that applies to the entire binary, and which will have its section
     // index set to #0 (which is a NULL section with the SHF_ALLOC bit cleared).
     //
-    // In the absence of GOT based relocations (which we currently don't support),
+    // In the absence of GOT based relocations,
     // this RELA section will contain redundant R_xxx_RELATIVE relocations, one
     // for every R_xxx_xx64 relocation appearing in the per-section RELA sections.
     // (i.e., .rela.text and .rela.data)
@@ -846,6 +984,44 @@ WriteSections64 (
               - (SecOffset - SecShdr->sh_addr));
             VerboseMsg ("Relocation:  0x%08X", *(UINT32 *)Targ);
             break;
+          case R_X86_64_GOTPCREL:
+          case R_X86_64_GOTPCRELX:
+          case R_X86_64_REX_GOTPCRELX:
+            VerboseMsg ("R_X86_64_GOTPCREL family");
+            VerboseMsg ("Offset: 0x%08X, Addend: 0x%08X",
+              (UINT32)(SecOffset + (Rel->r_offset - SecShdr->sh_addr)),
+              *(UINT32 *)Targ);
+            GOTEntryRva = Rel->r_offset - Rel->r_addend + *(INT32 *)Targ;
+            FindElfGOTSectionFromGOTEntryElfRva(GOTEntryRva);
+            *(UINT32 *)Targ = (UINT32) (*(UINT32 *)Targ
+              + (mCoffSectionsOffset[mGOTShindex] - mGOTShdr->sh_addr)
+              - (SecOffset - SecShdr->sh_addr));
+            VerboseMsg ("Relocation:  0x%08X", *(UINT32 *)Targ);
+            GOTEntryRva += (mCoffSectionsOffset[mGOTShindex] - mGOTShdr->sh_addr);  // ELF Rva -> COFF Rva
+            if (AccumulateCoffGOTEntries((UINT32)GOTEntryRva)) {
+              //
+              // Relocate GOT entry if it's the first time we run into it
+              //
+              Targ = mCoffFile + GOTEntryRva;
+              //
+              // Limitation: The following three statements assume memory
+              //   at *Targ is valid because the section containing the GOT
+              //   has already been copied from the ELF image to the Coff image.
+              //   This pre-condition presently holds because the GOT is placed
+              //   in section .text, and the ELF text sections are all copied
+              //   prior to reaching this point.
+              //   If the pre-condition is violated in the future, this fixup
+              //   either needs to be deferred after the GOT section is copied
+              //   to the Coff image, or the fixup should be performed on the
+              //   source Elf image instead of the destination Coff image.
+              //
+              VerboseMsg ("Offset: 0x%08X, Addend: 0x%016LX",
+                (UINT32)GOTEntryRva,
+                *(UINT64 *)Targ);
+              *(UINT64 *)Targ = *(UINT64 *)Targ - SymShdr->sh_addr + mCoffSectionsOffset[Sym->st_shndx];
+              VerboseMsg ("Relocation:  0x%016LX", *(UINT64*)Targ);
+            }
+            break;
           default:
             Error (NULL, 0, 3000, "Invalid", "%s unsupported ELF EM_X86_64 relocation 0x%x.", mInImageName, (unsigned) ELF_R_TYPE(Rel->r_info));
           }
@@ -984,6 +1160,9 @@ WriteRelocations64 (
             case R_X86_64_NONE:
             case R_X86_64_PC32:
             case R_X86_64_PLT32:
+            case R_X86_64_GOTPCREL:
+            case R_X86_64_GOTPCRELX:
+            case R_X86_64_REX_GOTPCRELX:
               break;
             case R_X86_64_64:
               VerboseMsg ("EFI_IMAGE_REL_BASED_DIR64 Offset: 0x%08X",
@@ -1052,10 +1231,32 @@ WriteRelocations64 (
             Error (NULL, 0, 3000, "Not Supported", "This tool does not support relocations for ELF with e_machine %u (processor type).", (unsigned) mEhdr->e_machine);
           }
         }
+        if (mEhdr->e_machine == EM_X86_64 && RelShdr->sh_info == mGOTShindex) {
+          //
+          // Tack relocations for GOT entries after other relocations for
+          //   the section the GOT is in, as it's usually found at the end
+          //   of the section.  This is done in order to maintain Rva order
+          //   of Coff relocations.
+          //
+          EmitGOTRelocations();
+        }
       }
     }
   }
 
+  if (mEhdr->e_machine == EM_X86_64) {
+    //
+    // This is a safety net just in case the GOT is in a section
+    //   with no other relocations and the first invocation of
+    //   EmitGOTRelocations() above was skipped.  This invocation
+    //   does not maintain Rva order of Coff relocations.
+    //   At present, with a single text section, all references to
+    //   the GOT and the GOT itself reside in section .text, so
+    //   if there's a GOT at all, the first invocation above
+    //   is executed.
+    //
+    EmitGOTRelocations();
+  }
   //
   // Pad by adding empty entries.
   //
diff --git a/BaseTools/Source/C/GenFw/elf_common.h b/BaseTools/Source/C/GenFw/elf_common.h
index 242ad00a..03dec50c 100644
--- a/BaseTools/Source/C/GenFw/elf_common.h
+++ b/BaseTools/Source/C/GenFw/elf_common.h
@@ -1052,6 +1052,23 @@ typedef struct {
 #define  R_X86_64_DTPOFF32  21  /* Offset in TLS block */
 #define  R_X86_64_GOTTPOFF  22  /* PC relative offset to IE GOT entry */
 #define  R_X86_64_TPOFF32  23  /* Offset in static TLS block */
+#define  R_X86_64_PC64  24  /* PC relative 64 bit */
+#define  R_X86_64_GOTOFF64  25  /* 64 bit offset to GOT */
+#define  R_X86_64_GOTPC3  26  /* 32 bit signed pc relative offset to GOT */
+#define  R_X86_64_GOT64  27  /* 64-bit GOT entry offset */
+#define  R_X86_64_GOTPCREL64  28  /* 64-bit PC relative offset to GOT entry */
+#define  R_X86_64_GOTPC64  29  /* 64-bit PC relative offset to GOT */
+#define  R_X86_64_GOTPLT64  30  /* like GOT64, says PLT entry needed */
+#define  R_X86_64_PLTOFF64  31  /* 64-bit GOT relative offset to PLT entry */
+#define  R_X86_64_SIZE32  32  /* Size of symbol plus 32-bit addend */
+#define  R_X86_64_SIZE64  33  /* Size of symbol plus 64-bit addend */
+#define  R_X86_64_GOTPC32_TLSDESC  34  /* GOT offset for TLS descriptor. */
+#define  R_X86_64_TLSDESC_CALL  35  /* Marker for call through TLS descriptor. */
+#define  R_X86_64_TLSDESC  36  /* TLS descriptor. */
+#define  R_X86_64_IRELATIVE  37  /* Adjust indirectly by program base */
+#define  R_X86_64_RELATIVE64  38  /* 64-bit adjust by program base */
+#define  R_X86_64_GOTPCRELX  41  /* Load from 32 bit signed pc relative offset to GOT entry without REX prefix, relaxable. */
+#define  R_X86_64_REX_GOTPCRELX  42  /* Load from 32 bit signed pc relative offset to GOT entry with REX prefix, relaxable. */
 
 
 #endif /* !_SYS_ELF_COMMON_H_ */
-- 
2.17.1