Add rts/Linker support for more than 64k sections

Since some ELF fields ran out of range to represent that many sections,
they've been extended with magic numbers that indicate that the full
value is stored in another field.

This will be necessary for GHCi with -split-sections on ELF platforms
that don't use GNU ld.

Reviewers: austin, bgamari, simonmar, erikd

Reviewed By: bgamari, simonmar, erikd

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1357

GHC Trac Issues: #8405

1 files changed, 141 insertions, 39 deletions

diff --git a/rts/Linker.c b/rts/Linker.c
index 34bae5b143..af3854ffc6 100644
--- a/rts/Linker.c
+++ b/rts/Linker.c
@@ -4026,9 +4026,11 @@ ocRunInit_PEi386 ( ObjectCode *oc )
 #define Elf_Addr    Elf64_Addr
 #define Elf_Word    Elf64_Word
 #define Elf_Sword   Elf64_Sword
+#define Elf_Half    Elf64_Half
 #define Elf_Ehdr    Elf64_Ehdr
 #define Elf_Phdr    Elf64_Phdr
 #define Elf_Shdr    Elf64_Shdr
+#define Elf_Section Elf64_Section
 #define Elf_Sym     Elf64_Sym
 #define Elf_Rel     Elf64_Rel
 #define Elf_Rela    Elf64_Rela
@@ -4049,9 +4051,11 @@ ocRunInit_PEi386 ( ObjectCode *oc )
 #define Elf_Addr    Elf32_Addr
 #define Elf_Word    Elf32_Word
 #define Elf_Sword   Elf32_Sword
+#define Elf_Half    Elf32_Half
 #define Elf_Ehdr    Elf32_Ehdr
 #define Elf_Phdr    Elf32_Phdr
 #define Elf_Shdr    Elf32_Shdr
+#define Elf_Section Elf32_Section
 #define Elf_Sym     Elf32_Sym
 #define Elf_Rel     Elf32_Rel
 #define Elf_Rela    Elf32_Rela
@@ -4165,6 +4169,61 @@ PLTSize(void)
 #endif
 
 /*
+
+   Note [Many ELF Sections]
+
+   The normal section number fields in ELF are limited to 16 bits, which runs
+   out of bits when you try to cram in more sections than that.
+
+   To solve this, the fields e_shnum and e_shstrndx in the ELF header have an
+   escape value (different for each case), and the actual section number is
+   stashed into unused fields in the first section header.
+
+   For symbols, there seems to have been no place in the actual symbol table
+   for the extra bits, so the indexes have been moved into an auxilliary
+   section instead.
+   For symbols in sections beyond 0xff00, the symbol's st_shndx will be an
+   escape value (SHN_XINDEX), and the actual 32-bit section number for symbol N
+   is stored at index N in the SHT_SYMTAB_SHNDX table.
+
+   These extensions seem to be undocumented in version 4.1 of the ABI and only
+   appear in the drafts for the "next" version:
+      https://refspecs.linuxfoundation.org/elf/gabi4+/contents.html
+
+*/
+
+static Elf_Word elf_shnum(Elf_Ehdr* ehdr)
+{
+   Elf_Shdr* shdr = (Elf_Shdr*) ((char*)ehdr + ehdr->e_shoff);
+   Elf_Half shnum = ehdr->e_shnum;
+   return shnum != SHN_UNDEF ? shnum : shdr[0].sh_size;
+}
+
+static Elf_Word elf_shstrndx(Elf_Ehdr* ehdr)
+{
+   Elf_Shdr* shdr = (Elf_Shdr*) ((char*)ehdr + ehdr->e_shoff);
+   Elf_Half shstrndx = ehdr->e_shstrndx;
+   return shstrndx != SHN_XINDEX ? shstrndx : shdr[0].sh_link;
+}
+
+static Elf_Word*
+get_shndx_table(Elf_Ehdr* ehdr)
+{
+   Elf_Word  i;
+   char*     ehdrC    = (char*)ehdr;
+   Elf_Shdr* shdr     = (Elf_Shdr*) (ehdrC + ehdr->e_shoff);
+   const Elf_Word shnum = elf_shnum(ehdr);
+
+   for (i = 0; i < shnum; i++) {
+     if (shdr[i].sh_type == SHT_SYMTAB_SHNDX) {
+       return (Elf32_Word*)(ehdrC + shdr[i].sh_offset);
+     }
+   }
+   return NULL;
+}
+
+
+/*
  * Generic ELF functions
  */
 
@@ -4173,7 +4232,8 @@ ocVerifyImage_ELF ( ObjectCode* oc )
 {
    Elf_Shdr* shdr;
    Elf_Sym*  stab;
-   int i, j, nent, nstrtab, nsymtabs;
+   int j, nent, nstrtab, nsymtabs;
+   Elf_Word i, shnum, shstrndx;
    char* sh_strtab;
 
    char*     ehdrC = (char*)(oc->image);
@@ -4233,24 +4293,26 @@ ocVerifyImage_ELF ( ObjectCode* oc )
                      return 0;
    }
 
+   shnum = elf_shnum(ehdr);
    IF_DEBUG(linker,debugBelch(
              "\nSection header table: start %ld, n_entries %d, ent_size %d\n",
-             (long)ehdr->e_shoff, ehdr->e_shnum, ehdr->e_shentsize  ));
+             (long)ehdr->e_shoff, shnum, ehdr->e_shentsize  ));
 
    ASSERT (ehdr->e_shentsize == sizeof(Elf_Shdr));
 
    shdr = (Elf_Shdr*) (ehdrC + ehdr->e_shoff);
 
-   if (ehdr->e_shstrndx == SHN_UNDEF) {
+   shstrndx = elf_shstrndx(ehdr);
+   if (shstrndx == SHN_UNDEF) {
       errorBelch("%s: no section header string table", oc->fileName);
       return 0;
    } else {
       IF_DEBUG(linker,debugBelch( "Section header string table is section %d\n",
-                          ehdr->e_shstrndx));
-      sh_strtab = ehdrC + shdr[ehdr->e_shstrndx].sh_offset;
+                          shstrndx));
+      sh_strtab = ehdrC + shdr[shstrndx].sh_offset;
    }
 
-   for (i = 0; i < ehdr->e_shnum; i++) {
+   for (i = 0; i < shnum; i++) {
       IF_DEBUG(linker,debugBelch("%2d:  ", i ));
       IF_DEBUG(linker,debugBelch("type=%2d  ", (int)shdr[i].sh_type ));
       IF_DEBUG(linker,debugBelch("size=%4d  ", (int)shdr[i].sh_size ));
@@ -4259,7 +4321,7 @@ ocVerifyImage_ELF ( ObjectCode* oc )
                ehdrC + shdr[i].sh_offset,
                       ehdrC + shdr[i].sh_offset + shdr[i].sh_size - 1));
 
-#define SECTION_INDEX_VALID(ndx) (ndx > SHN_UNDEF && ndx < ehdr->e_shnum)
+#define SECTION_INDEX_VALID(ndx) (ndx > SHN_UNDEF && ndx < shnum)
 
       switch (shdr[i].sh_type) {
 
@@ -4318,10 +4380,10 @@ ocVerifyImage_ELF ( ObjectCode* oc )
 
    IF_DEBUG(linker,debugBelch( "\nString tables\n" ));
    nstrtab = 0;
-   for (i = 0; i < ehdr->e_shnum; i++) {
+   for (i = 0; i < shnum; i++) {
       if (shdr[i].sh_type == SHT_STRTAB
           /* Ignore the section header's string table. */
-          && i != ehdr->e_shstrndx
+          && i != shstrndx
           /* Ignore string tables named .stabstr, as they contain
              debugging info. */
           && 0 != memcmp(".stabstr", sh_strtab + shdr[i].sh_name, 8)
@@ -4334,9 +4396,10 @@ ocVerifyImage_ELF ( ObjectCode* oc )
       IF_DEBUG(linker,debugBelch("   no normal string tables (potentially, but not necessarily a problem)\n"));
    }
 
+   Elf_Word* shndxTable = get_shndx_table(ehdr);
    nsymtabs = 0;
    IF_DEBUG(linker,debugBelch( "Symbol tables\n" ));
-   for (i = 0; i < ehdr->e_shnum; i++) {
+   for (i = 0; i < shnum; i++) {
       if (shdr[i].sh_type != SHT_SYMTAB) continue;
       IF_DEBUG(linker,debugBelch( "section %d is a symbol table\n", i ));
       nsymtabs++;
@@ -4351,9 +4414,15 @@ ocVerifyImage_ELF ( ObjectCode* oc )
          return 0;
       }
       for (j = 0; j < nent; j++) {
+         Elf_Word secno = stab[j].st_shndx;
+         /* See Note [Many ELF Sections] */
+         if (secno == SHN_XINDEX) {
+            ASSERT(shndxTable);
+            secno = shndxTable[j];
+         }
          IF_DEBUG(linker,debugBelch("   %2d  ", j ));
          IF_DEBUG(linker,debugBelch("  sec=%-5d  size=%-3d  val=%5p  ",
-                             (int)stab[j].st_shndx,
+                             (int)secno,
                              (int)stab[j].st_size,
                              (char*)stab[j].st_value ));
 
@@ -4377,9 +4446,10 @@ ocVerifyImage_ELF ( ObjectCode* oc )
          }
          IF_DEBUG(linker,debugBelch("  " ));
 
-         IF_DEBUG(linker,debugBelch("name=%s\n",
+         IF_DEBUG(linker,debugBelch("other=%2x ", stab[j].st_other ));
+         IF_DEBUG(linker,debugBelch("name=%s [%x]\n",
                         ehdrC + shdr[shdr[i].sh_link].sh_offset
-                              + stab[j].st_name ));
+                              + stab[j].st_name, stab[j].st_name ));
       }
    }
 
@@ -4455,7 +4525,8 @@ mapObjectFileSection (int fd, Elf_Word offset, Elf_Word size,
 static int
 ocGetNames_ELF ( ObjectCode* oc )
 {
-   int i, j, nent, result, fd = -1;
+   Elf_Word i;
+   int j, nent, result, fd = -1;
    Elf_Sym* stab;
 
    char*     ehdrC    = (char*)(oc->image);
@@ -4463,13 +4534,15 @@ ocGetNames_ELF ( ObjectCode* oc )
    char*     strtab;
    Elf_Shdr* shdr     = (Elf_Shdr*) (ehdrC + ehdr->e_shoff);
    Section * sections;
+   Elf_Word* shndxTable = get_shndx_table(ehdr);
+   const Elf_Word shnum = elf_shnum(ehdr);
 
    ASSERT(symhash != NULL);
 
-   sections = (Section*)stgCallocBytes(sizeof(Section), ehdr->e_shnum,
+   sections = (Section*)stgCallocBytes(sizeof(Section), shnum,
                                        "ocGetNames_ELF(sections)");
    oc->sections = sections;
-   oc->n_sections = ehdr->e_shnum;
+   oc->n_sections = shnum;
 
 
    if (oc->imageMapped) {
@@ -4484,7 +4557,7 @@ ocGetNames_ELF ( ObjectCode* oc )
        }
    }
 
-   for (i = 0; i < ehdr->e_shnum; i++) {
+   for (i = 0; i < shnum; i++) {
       int         is_bss = FALSE;
       SectionKind kind   = getSectionKind_ELF(&shdr[i], &is_bss);
       SectionAlloc alloc = SECTION_NOMEM;
@@ -4556,12 +4629,25 @@ ocGetNames_ELF ( ObjectCode* oc )
          HsBool isWeak = HS_BOOL_FALSE;
          char* ad      = NULL;
          char* nm      = strtab + stab[j].st_name;
-         int   secno   = stab[j].st_shndx;
+         Elf_Section shndx = stab[j].st_shndx;
+         Elf_Word secno;
+
+         /* See Note [Many ELF Sections] */
+         /* Note that future checks for special SHN_* numbers should check the
+          * shndx variable, not the section number in secno. Sections with the
+          * real number in the SHN_LORESERVE..HIRESERVE range will have shndx
+          * SHN_XINDEX and a secno with one of the reserved values. */
+         if (shndx == SHN_XINDEX) {
+            ASSERT(shndxTable);
+            secno = shndxTable[j];
+         } else {
+            secno = shndx;
+         }
 
          /* Figure out if we want to add it; if so, set ad to its
             address.  Otherwise leave ad == NULL. */
 
-         if (secno == SHN_COMMON) {
+         if (shndx == SHN_COMMON) {
             isLocal = FALSE;
             ad = stgCallocBytes(1, stab[j].st_size, "ocGetNames_ELF(COMMON)");
             /*
@@ -4577,9 +4663,9 @@ ocGetNames_ELF ( ObjectCode* oc )
                 || ELF_ST_BIND(stab[j].st_info)==STB_WEAK
               )
               /* and not an undefined symbol */
-              && stab[j].st_shndx != SHN_UNDEF
+              && shndx != SHN_UNDEF
               /* and not in a "special section" */
-              && stab[j].st_shndx < SHN_LORESERVE
+              && (shndx < SHN_LORESERVE || shndx == SHN_XINDEX)
               &&
               /* and it's a not a section or string table or anything silly */
               ( ELF_ST_TYPE(stab[j].st_info)==STT_FUNC ||
@@ -4588,7 +4674,7 @@ ocGetNames_ELF ( ObjectCode* oc )
               )
             ) {
             /* Section 0 is the undefined section, hence > and not >=. */
-            ASSERT(secno > 0 && secno < ehdr->e_shnum);
+            ASSERT(secno > 0 && secno < shnum);
             /*
             if (shdr[secno].sh_type == SHT_NOBITS) {
                debugBelch("   BSS symbol, size %d off %d name %s\n",
@@ -4635,10 +4721,10 @@ ocGetNames_ELF ( ObjectCode* oc )
                                    strtab + stab[j].st_name ));
             /*
             debugBelch(
-                    "skipping   bind = %d,  type = %d,  shndx = %d   `%s'\n",
+                    "skipping   bind = %d,  type = %d,  secno = %d   `%s'\n",
                     (int)ELF_ST_BIND(stab[j].st_info),
                     (int)ELF_ST_TYPE(stab[j].st_info),
-                    (int)stab[j].st_shndx,
+                    (int)secno,
                     strtab + stab[j].st_name
                    );
             */
@@ -4676,6 +4762,7 @@ do_Elf_Rel_relocations ( ObjectCode* oc, char* ehdrC,
    int target_shndx = shdr[shnum].sh_info;
    int symtab_shndx = shdr[shnum].sh_link;
    int strtab_shndx = shdr[symtab_shndx].sh_link;
+   Elf_Word* shndx_table = get_shndx_table((Elf_Ehdr*)ehdrC);
 
    stab  = (Elf_Sym*) (ehdrC + shdr[ symtab_shndx ].sh_offset);
    strtab= (char*)    (ehdrC + shdr[ strtab_shndx ].sh_offset);
@@ -4719,9 +4806,14 @@ do_Elf_Rel_relocations ( ObjectCode* oc, char* ehdrC,
             /* Yes, so we can get the address directly from the ELF symbol
                table. */
             symbol = sym.st_name==0 ? "(noname)" : strtab+sym.st_name;
-            S = (Elf_Addr)oc->sections[sym.st_shndx].start +
+            /* See Note [Many ELF Sections] */
+            Elf_Word secno = sym.st_shndx;
+            if (secno == SHN_XINDEX) {
+               ASSERT(shndx_table);
+               secno = shndx_table[ELF_R_SYM(info)];
+            }
+            S = (Elf_Addr)oc->sections[ secno ].start +
                 stab[ELF_R_SYM(info)].st_value;
-
          } else {
             symbol = strtab + sym.st_name;
             S_tmp = lookupSymbol_( symbol );
@@ -4980,6 +5072,7 @@ do_Elf_Rela_relocations ( ObjectCode* oc, char* ehdrC,
    int symtab_shndx = shdr[shnum].sh_link;
    int strtab_shndx = shdr[symtab_shndx].sh_link;
    int target_shndx = shdr[shnum].sh_info;
+   Elf_Word* shndx_table = get_shndx_table((Elf_Ehdr*)ehdrC);
 #if defined(DEBUG) || defined(sparc_HOST_ARCH) || defined(ia64_HOST_ARCH) || defined(powerpc_HOST_ARCH) || defined(x86_64_HOST_ARCH)
    /* This #ifdef only serves to avoid unused-var warnings. */
    Elf_Addr targ = (Elf_Addr) oc->sections[target_shndx].start;
@@ -5030,7 +5123,12 @@ do_Elf_Rela_relocations ( ObjectCode* oc, char* ehdrC,
             /* Yes, so we can get the address directly from the ELF symbol
                table. */
             symbol = sym.st_name==0 ? "(noname)" : strtab+sym.st_name;
-            S = (Elf_Addr)oc->sections[sym.st_shndx].start
+            /* See Note [Many ELF Sections] */
+            Elf_Word secno = sym.st_shndx;
+            if (secno == SHN_XINDEX) {
+              secno = shndx_table[ELF_R_SYM(info)];
+            }
+            S = (Elf_Addr)oc->sections[secno].start
                 + stab[ELF_R_SYM(info)].st_value;
 #ifdef ELF_FUNCTION_DESC
             /* Make a function descriptor for this function */
@@ -5309,20 +5407,22 @@ do_Elf_Rela_relocations ( ObjectCode* oc, char* ehdrC,
 static int
 ocResolve_ELF ( ObjectCode* oc )
 {
-   int   shnum, ok;
+   int       ok;
+   Elf_Word  i;
    char*     ehdrC = (char*)(oc->image);
    Elf_Ehdr* ehdr  = (Elf_Ehdr*) ehdrC;
    Elf_Shdr* shdr  = (Elf_Shdr*) (ehdrC + ehdr->e_shoff);
+   const Elf_Word shnum = elf_shnum(ehdr);
 
    /* Process the relocation sections. */
-   for (shnum = 0; shnum < ehdr->e_shnum; shnum++) {
-      if (shdr[shnum].sh_type == SHT_REL) {
-         ok = do_Elf_Rel_relocations ( oc, ehdrC, shdr, shnum );
+   for (i = 0; i < shnum; i++) {
+      if (shdr[i].sh_type == SHT_REL) {
+         ok = do_Elf_Rel_relocations ( oc, ehdrC, shdr, i );
          if (!ok) return ok;
       }
       else
-      if (shdr[shnum].sh_type == SHT_RELA) {
-         ok = do_Elf_Rela_relocations ( oc, ehdrC, shdr, shnum );
+      if (shdr[i].sh_type == SHT_RELA) {
+         ok = do_Elf_Rela_relocations ( oc, ehdrC, shdr, i );
          if (!ok) return ok;
       }
    }
@@ -5336,11 +5436,11 @@ ocResolve_ELF ( ObjectCode* oc )
 
 static int ocRunInit_ELF( ObjectCode *oc )
 {
-   int   i;
+   Elf_Word i;
    char*     ehdrC = (char*)(oc->image);
    Elf_Ehdr* ehdr  = (Elf_Ehdr*) ehdrC;
    Elf_Shdr* shdr  = (Elf_Shdr*) (ehdrC + ehdr->e_shoff);
-   char* sh_strtab = ehdrC + shdr[ehdr->e_shstrndx].sh_offset;
+   char* sh_strtab = ehdrC + shdr[elf_shstrndx(ehdr)].sh_offset;
    int argc, envc;
    char **argv, **envv;
 
@@ -5351,7 +5451,7 @@ static int ocRunInit_ELF( ObjectCode *oc )
    // special!  See DL_DT_INIT_ADDRESS macro in glibc
    // as well as ELF_FUNCTION_PTR_IS_SPECIAL.  We've not handled
    // it here, please file a bug report if it affects you.
-   for (i = 0; i < ehdr->e_shnum; i++) {
+   for (i = 0; i < elf_shnum(ehdr); i++) {
       init_t *init_start, *init_end, *init;
       int is_bss = FALSE;
       SectionKind kind = getSectionKind_ELF(&shdr[i], &is_bss);
@@ -5398,16 +5498,18 @@ static int ocAllocateSymbolExtras_ELF( ObjectCode *oc )
 {
   Elf_Ehdr *ehdr;
   Elf_Shdr* shdr;
-  int i;
+  Elf_Word i, shnum;
 
   ehdr = (Elf_Ehdr *) oc->image;
   shdr = (Elf_Shdr *) ( ((char *)oc->image) + ehdr->e_shoff );
 
-  for( i = 0; i < ehdr->e_shnum; i++ )
+  shnum = elf_shnum(ehdr);
+
+  for( i = 0; i < shnum; i++ )
     if( shdr[i].sh_type == SHT_SYMTAB )
       break;
 
-  if( i == ehdr->e_shnum )
+  if( i == shnum )
   {
     // Not having a symbol table is not in principle a problem.
     // When an object file has no symbols then the 'strip' program