Resolve unresolved externals when loading object files.

Object files that depend on each other will cause an unresolved
external. The change lets object files load with unresolved
externals and will resolve them when the object file with the
external is loaded.

A common table of symbol strings and relocation records is maintained.
The symbol string is shared by each object file that is unresolved.
Each relocation record that references the symbol is held. The table
is a series of small blocks that compact as symbols are resolved. The
number of symbols left unresolved is typically small this design avoids
fragmentation of the heap memory.

1 files changed, 128 insertions, 39 deletions

diff --git a/rtl-elf.c b/rtl-elf.c
index acf7893..cd96192 100644
--- a/rtl-elf.c
+++ b/rtl-elf.c
@@ -12,7 +12,7 @@
  *
  * @brief RTEMS Run-Time Link Editor
  *
- * This is the RTL implementation. 
+ * This is the RTL implementation.
  */
 
 #if HAVE_CONFIG_H
@@ -30,6 +30,14 @@
 #include "rtl-elf.h"
 #include "rtl-error.h"
 #include "rtl-trace.h"
+#include "rtl-unresolved.h"
+
+/**
+ * The offsets in the unresolved array.
+ */
+#define REL_R_OFFSET (0)
+#define REL_R_INFO   (1)
+#define REL_R_ADDEND (2)
 
 static bool
 rtems_rtl_elf_machine_check (Elf_Ehdr* ehdr)
@@ -93,7 +101,6 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
   bool                   is_rela;
   size_t                 reloc_size;
   int                    reloc;
-  int                    unresolved;
 
   /*
    * First check if the section the relocations are for exists. If it does not
@@ -102,12 +109,12 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
   targetsect = rtems_rtl_obj_find_section_by_index (obj, sect->info);
   if (!targetsect)
     return true;
-  
+
   rtems_rtl_obj_caches (&symbols, &strings, &relocs);
 
   if (!symbols || !strings || !relocs)
     return false;
-  
+
   symsect = rtems_rtl_obj_find_section (obj, ".symtab");
   if (!symsect)
   {
@@ -121,7 +128,7 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
     rtems_rtl_set_error (EINVAL, "no .strtab section");
     return false;
   }
-  
+
   if (rtems_rtl_trace (RTEMS_RTL_TRACE_RELOC))
     printf ("rtl: relocation: %s, syms:%s\n", sect->name, symsect->name);
 
@@ -132,8 +139,8 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
              RTEMS_RTL_OBJ_SECT_RELA) ? true : false;
   reloc_size = is_rela ? sizeof (Elf_Rela) : sizeof (Elf_Rel);
 
-  unresolved = 0;
-  
+  obj->unresolved = 0;
+
   for (reloc = 0; reloc < (sect->size / reloc_size); ++reloc)
   {
     uint8_t         relbuf[reloc_size];
@@ -171,7 +178,7 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
       size_t len;
       off = obj->ooffset + strtab->offset + sym.st_name;
       len = RTEMS_RTL_ELF_STRING_MAX;
-    
+
       if (!rtems_rtl_obj_cache_read (strings, fd, off,
                                      (void**) &symname, &len))
         return false;
@@ -180,7 +187,8 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
     /*
      * See if the record references an external symbol. If it does find the
      * symbol value. If the symbol cannot be found flag the object file as
-     * having unresolved externals.
+     * having unresolved externals and store the externals. The load of an
+     * object after this one may provide the unresolved externals.
      */
     if (is_rela)
       type = ELF_R_TYPE(rela->r_info);
@@ -188,13 +196,38 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
       type = ELF_R_TYPE(rel->r_info);
 
     relocate = true;
-    
+
     if (rtems_rtl_elf_rel_resolve_sym (type))
     {
       if (!rtems_rtl_elf_find_symbol (obj, &sym, symname, &symvalue))
       {
-        ++unresolved;
+        uint16_t         flags = 0;
+        rtems_rtl_word_t rel_words[3];
+
+        ++obj->unresolved;
         relocate = false;
+
+        if (is_rela)
+        {
+          flags = 1;
+          rel_words[REL_R_OFFSET] = rela->r_offset;
+          rel_words[REL_R_INFO] = rela->r_info;
+          rel_words[REL_R_ADDEND] = rela->r_addend;
+        }
+        else
+        {
+          rel_words[REL_R_OFFSET] = rel->r_offset;
+          rel_words[REL_R_INFO] = rel->r_info;
+          rel_words[REL_R_ADDEND] = 0;
+        }
+
+        if (!rtems_rtl_unresolved_add (obj,
+                                       flags,
+                                       symname,
+                                       targetsect->section,
+                                       rel_words))
+        {
+        }
       }
     }
 
@@ -212,9 +245,9 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
       else
       {
         if (rtems_rtl_trace (RTEMS_RTL_TRACE_RELOC))
-        printf ("rtl: rel: sym:%-2d type:%-2d off:%08lx\n",
-                (int) ELF_R_SYM (rel->r_info), (int) ELF_R_TYPE (rel->r_info),
-                rel->r_offset);
+          printf ("rtl: rel: sym:%-2d type:%-2d off:%08lx\n",
+                  (int) ELF_R_SYM (rel->r_info), (int) ELF_R_TYPE (rel->r_info),
+                  rel->r_offset);
         if (!rtems_rtl_elf_relocate_rel (obj, rel, targetsect, symvalue))
           return false;
       }
@@ -224,12 +257,63 @@ rtems_rtl_elf_relocator (rtems_rtl_obj_t*      obj,
   /*
    * Set the unresolved externals status if there are unresolved externals.
    */
-  if (unresolved)
+  if (obj->unresolved)
     obj->flags |= RTEMS_RTL_OBJ_UNRESOLVED;
 
   return true;
 }
 
+bool
+rtems_rtl_obj_relocate_unresolved (rtems_rtl_unresolv_reloc_t* reloc,
+                                   rtems_rtl_obj_sym_t*        sym)
+{
+  rtems_rtl_obj_sect_t* sect;
+  bool                  is_rela;
+  Elf_Word              symvalue;
+
+  is_rela =reloc->flags & 1;
+
+  sect = rtems_rtl_obj_find_section_by_index (reloc->obj, reloc->sect);
+  if (!sect)
+    return false;
+
+  symvalue = (Elf_Word) (intptr_t) sym->value;
+  if (is_rela)
+  {
+    Elf_Rela rela;
+    rela.r_offset = reloc->rel[REL_R_OFFSET];
+    rela.r_info = reloc->rel[REL_R_INFO];
+    rela.r_addend = reloc->rel[REL_R_ADDEND];
+    if (rtems_rtl_trace (RTEMS_RTL_TRACE_RELOC))
+          printf ("rtl: rela: sym:%-2d type:%-2d off:%08lx addend:%d\n",
+                  (int) ELF_R_SYM (rela.r_info), (int) ELF_R_TYPE (rela.r_info),
+                  rela.r_offset, (int) rela.r_addend);
+    if (!rtems_rtl_elf_relocate_rela (reloc->obj, &rela, sect, symvalue))
+      return false;
+  }
+  else
+  {
+    Elf_Rel rel;
+    rel.r_offset = reloc->rel[REL_R_OFFSET];
+    rel.r_info = reloc->rel[REL_R_INFO];
+    if (rtems_rtl_trace (RTEMS_RTL_TRACE_RELOC))
+      printf ("rtl: rel: sym:%-2d type:%-2d off:%08lx\n",
+              (int) ELF_R_SYM (rel.r_info), (int) ELF_R_TYPE (rel.r_info),
+              rel.r_offset);
+    if (!rtems_rtl_elf_relocate_rel (reloc->obj, &rel, sect, symvalue))
+      return false;
+  }
+
+  if (reloc->obj->unresolved)
+  {
+    --reloc->obj->unresolved;
+    if (!reloc->obj->unresolved)
+      reloc->obj->flags &= ~RTEMS_RTL_OBJ_UNRESOLVED;
+  }
+
+  return true;
+}
+
 static bool
 rtems_rtl_elf_symbols (rtems_rtl_obj_t*      obj,
                        int                   fd,
@@ -276,10 +360,10 @@ rtems_rtl_elf_symbols (rtems_rtl_obj_t*      obj,
     if (!rtems_rtl_obj_cache_read_byval (symbols, fd, off,
                                          &symbol, sizeof (symbol)))
       return false;
-    
+
     off = obj->ooffset + strtab->offset + symbol.st_name;
     len = RTEMS_RTL_ELF_STRING_MAX;
-    
+
     if (!rtems_rtl_obj_cache_read (strings, fd, off, (void**) &name, &len))
       return false;
 
@@ -317,7 +401,7 @@ rtems_rtl_elf_symbols (rtems_rtl_obj_t*      obj,
   if (globals)
   {
     rtems_rtl_obj_sym_t* gsym;
-    
+
     obj->global_size = globals * sizeof (rtems_rtl_obj_sym_t) + string_space;
     obj->global_table = rtems_rtl_alloc_new (RTEMS_RTL_ALLOC_SYMBOL,
                                              obj->global_size, true);
@@ -356,7 +440,7 @@ rtems_rtl_elf_symbols (rtems_rtl_obj_t*      obj,
 
       off = obj->ooffset + strtab->offset + symbol.st_name;
       len = RTEMS_RTL_ELF_STRING_MAX;
-    
+
       if (!rtems_rtl_obj_cache_read (strings, fd, off, (void**) &name, &len))
         return false;
 
@@ -376,24 +460,29 @@ rtems_rtl_elf_symbols (rtems_rtl_obj_t*      obj,
           rtems_rtl_set_error (EINVAL, "sym section not found");
           return false;
         }
+
+        rtems_chain_set_off_chain (&gsym->node);
+
         memcpy (string, name, strlen (name) + 1);
         gsym->name = string;
         string += strlen (name) + 1;
         gsym->value = symbol.st_value + (uint8_t*) symsect->base;
 
         if (rtems_rtl_trace (RTEMS_RTL_TRACE_SYMBOL))
-          printf ("rtl: sym:%-2d name:%-2d:%-20s bind:%-2d type:%-2d val:%8p sect:%d size:%d\n",
+          printf ("rtl: sym:add:%-2d name:%-2d:%-20s bind:%-2d type:%-2d val:%8p sect:%d size:%d\n",
                   sym, (int) symbol.st_name, gsym->name,
                   (int) ELF_ST_BIND (symbol.st_info),
                   (int) ELF_ST_TYPE (symbol.st_info),
                   gsym->value, symbol.st_shndx,
                   (int) symbol.st_size);
-      
+
         ++gsym;
       }
     }
+
+    rtems_rtl_symbol_obj_add (obj);
   }
-  
+
   return true;
 }
 
@@ -406,17 +495,17 @@ rtems_rtl_elf_parse_sections (rtems_rtl_obj_t* obj, int fd, Elf_Ehdr* ehdr)
   off_t                  sectstroff;
   off_t                  off;
   Elf_Shdr               shdr;
-  
+
   rtems_rtl_obj_caches (&sects, &strings, NULL);
 
   if (!sects || !strings)
     return false;
-  
+
   /*
    * Get the offset to the section string table.
    */
   off = obj->ooffset + ehdr->e_shoff + (ehdr->e_shstrndx * ehdr->e_shentsize);
-  
+
   if (!rtems_rtl_obj_cache_read_byval (sects, fd, off, &shdr, sizeof (shdr)))
     return false;
 
@@ -438,7 +527,7 @@ rtems_rtl_elf_parse_sections (rtems_rtl_obj_t* obj, int fd, Elf_Ehdr* ehdr)
       return false;
 
     flags = 0;
-    
+
     switch (shdr.sh_type)
     {
       case SHT_NULL:
@@ -476,7 +565,7 @@ rtems_rtl_elf_parse_sections (rtems_rtl_obj_t* obj, int fd, Elf_Ehdr* ehdr)
       case SHT_RELA:
         flags = RTEMS_RTL_OBJ_SECT_RELA;
         break;
-        
+
       case SHT_REL:
         /*
          * The sh_link holds the section index for the symbol table. The sh_info
@@ -498,7 +587,7 @@ rtems_rtl_elf_parse_sections (rtems_rtl_obj_t* obj, int fd, Elf_Ehdr* ehdr)
                 section, (int) shdr.sh_type, (int) shdr.sh_flags);
         break;
     }
-    
+
     if (flags != 0)
     {
       char*  name;
@@ -514,7 +603,7 @@ rtems_rtl_elf_parse_sections (rtems_rtl_obj_t* obj, int fd, Elf_Ehdr* ehdr)
         flags |= RTEMS_RTL_OBJ_SECT_CTOR;
       if (strcmp (".dtors", name) == 0)
         flags |= RTEMS_RTL_OBJ_SECT_DTOR;
-      
+
       if (!rtems_rtl_obj_add_section (obj, section, name,
                                       shdr.sh_size, shdr.sh_offset,
                                       shdr.sh_addralign, shdr.sh_link,
@@ -531,9 +620,9 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
 {
   rtems_rtl_obj_cache_t* header;
   Elf_Ehdr               ehdr;
-  
+
   rtems_rtl_obj_caches (&header, NULL, NULL);
-  
+
   if (!rtems_rtl_obj_cache_read_byval (header, fd, obj->ooffset,
                                        &ehdr, sizeof (ehdr)))
     return false;
@@ -541,7 +630,7 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
   /*
    * Check we have a valid ELF file.
    */
-  if ((memcmp (ELFMAG, ehdr.e_ident, SELFMAG) != 0) 
+  if ((memcmp (ELFMAG, ehdr.e_ident, SELFMAG) != 0)
       || ehdr.e_ident[EI_CLASS] != ELFCLASS)
   {
     rtems_rtl_set_error (EINVAL, "invalid ELF file format");
@@ -555,7 +644,7 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
     rtems_rtl_set_error (EINVAL, "unsupported ELF file version");
     return false;
   }
-      
+
   if (!rtems_rtl_elf_machine_check (&ehdr))
   {
     rtems_rtl_set_error (EINVAL, "unsupported machine type");
@@ -573,7 +662,7 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
     rtems_rtl_set_error (EINVAL, "ELF file contains program headers");
     return false;
   }
-  
+
   if (ehdr.e_shentsize != sizeof (Elf_Shdr))
   {
     rtems_rtl_set_error (EINVAL, "invalid ELF section header size");
@@ -584,10 +673,10 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
    * Parse the section information first so we have the memory map of the object
    * file and the memory allocated. Any further allocations we make to complete
    * the load will not fragment the memory.
-   */ 
+   */
   if (!rtems_rtl_elf_parse_sections (obj, fd, &ehdr))
     return false;
-  
+
   obj->entry = (void*)(uintptr_t) ehdr.e_entry;
 
   if (!rtems_rtl_obj_load_sections (obj, fd))
@@ -595,10 +684,10 @@ rtems_rtl_obj_file_load (rtems_rtl_obj_t* obj, int fd)
 
   if (!rtems_rtl_obj_load_symbols (obj, fd, rtems_rtl_elf_symbols, &ehdr))
     return false;
-  
+
   if (!rtems_rtl_obj_relocate (obj, fd, rtems_rtl_elf_relocator, &ehdr))
     return false;
-  
+
   return true;
-} 
+}