[RFC][PATCH][EXPERIMENTAL] enable MIPS gnu hash (was: Re: use of gnu hash for MIPS)

[Hiroki Kaminaga <kaminaga at sm dot sony dot co dot jp>]

Hi,

From: Richard Sandiford <richard@codesourcery.com>
> Sorry for the late reply.
> 
> Hiroki Kaminaga <kaminaga@sm.sony.co.jp> writes:
> > 1) make .gnu.dynsym section
> >    - which is specific for .gnu.hash, but obiously redundant
> > 2) allow bitmap portion of gnu hash for MIPS
> >    - to benefit speedup of that part (which is not bad idea, I think)
> >    - the symbol lookup part is same as before
> 
> I admit I haven't really looked into this in enough detail to know
> which of these alternatives (or other variations on the format)
> would be better.  But...
> 
> > 3) Somehow work out to co-existance of sorting order of .dynsym
> >
> > Regarding choice 3), my understanding is as follows:
> >
> > .got requires order of
> >
> >   +------------+
> >   | local sym  |
> >   | local sym  |
> >   +------------+  <- DT_MIPS_LOCAL_GOTNO
> >   | extern sym |
> >   | extern sym |
> >   | extern sym |
> >   +------------+
> >
> > but there is no constraints in ordering. (except to be 1:1 with
> > .dynsym) On the other hand, gnu hash sorts .dynsym in hash value
> > order. So, does this method work?
> >
> > 1) locate local symbols on first part
> >    - to obey .got requirement
> > 2) locate external sorted by hash after local symbols
> >    - to apply gnu hash
> > 3) sort .got entries according to hash value
> >    - to obey .got 1:1 with .dynsym
> 
> I think this would interact badly with the multigot feature.  Symbols
> in the primary GOT must come before those that aren't in the primary GOT,
> so there's really a third division:
> 
>    +------------------------+
>    | local sym              |
>    | ...                    |
>    | local sym              |
>    +------------------------+  <- DT_MIPS_LOCAL_GOTNO
>    | primary extern sym     |
>    | ...                    |
>    | primary extern sym     |
>    +------------------------+
>    | non-primary extern sym |
>    | ...                    |
>    | non-primary extern sym |
>    +------------------------+
> 
> Secondary GOTs have an impact on start-up time too.  They disable
> lazy binding and they rely on normal relocation entries instead of
> the dynsym<->got mapping, thus increasing the number of symbol lookups
> needed.  So I think the interests of the primary GOT take precedent
> here; we don't want to make less use of it.
> 
> FWIW, I don't see any problem off-hand with sorting within these
> three groups.  Page 5-14 of the psABI says:
> 
>   To take advantage of Quickstart functionality, the .dynsym and
>   .rel.dyn sections must obey ordering constraints. The GOT-mapped
>   portion of the .dynsym section must be ordered on increasing values in
>   the st_value field. This requires that the .got section have the same
>   order, since it must correspond to the .dynsym section.
> 
> but AIUI, the GNU tools have taken this to mean "if you're not using
> QuickStart, don't bother", and symbols aren't ordered by increasing
> st_value.
> 
> For extra flexibility, you might like to have an unbounded list
> of external symbol blocks, each of which is sorted as required by
> .gnu.hash.  Although I think we only need at most two blocks at
> the moment, who knows what we'll need in future?


Attached is patch I've made to enable MIPS gnu hash.
These patches are highly experimental, and have following drawbacks.
The patches are against binutils-2.17.50.0.15 and glibc-2.5.

 - .got section will increase
 - -hash-style=both can't be selected (forced to lean towards gnu hash)
 - not considered about multi got
 - added extra flag in st_other field of symbol, to enable fast
   lookup, referenced in glibc's runtime loader

The basic concept is to keep 1:1 relationship of .dynsym and .got, while
.dynsym is ordered by gnu hash, as mentioned above.

Best Regards,
(Hiroki Kaminaga)
t
--

<diffstat>

 binutils-2.17.50.0.15/bfd/elfxx-mips.c              |  102 +++++++++++++--
 binutils-2.17.50.0.15/binutils/readelf.c            |    1 
 binutils-2.17.50.0.15/include/elf/mips.h            |    3 
 binutils-2.17.50.0.15/ld/emultempl/mipself.em       |    8 +
 glibc-2.5/elf/elf.h                                 |    1 
 glibc-2.5/glibc-ports-2.5/sysdeps/mips/dl-machine.h |   10 +
 6 files changed, 117 insertions(+), 8 deletions(-)

<patch>

Index: binutils-2.17.50.0.15/bfd/elfxx-mips.c
===================================================================
--- binutils-2.17.50.0.15/bfd/elfxx-mips.c
+++ binutils-2.17.50.0.15/bfd/elfxx-mips.c
@@ -491,6 +491,8 @@ static struct mips_got_entry *mips_elf_c
    asection *, bfd_vma, unsigned long, struct mips_elf_link_hash_entry *, int);
 static bfd_boolean mips_elf_sort_hash_table_f
   (struct mips_elf_link_hash_entry *, void *);
+static bfd_boolean mips_elf_sort_gnu_hash_table_f
+  (struct mips_elf_link_hash_entry *, void *);
 static bfd_vma mips_elf_high
   (bfd_vma);
 static bfd_boolean mips16_stub_section_p
@@ -2828,6 +2830,64 @@ mips_elf_sort_hash_table_f (struct mips_
   return TRUE;
 }
 
+/* No sorting of dynindx is done here, since it is done by gun hash
+   routine. Just track the lowest entry. */
+static bfd_boolean
+mips_elf_sort_gnu_hash_table (struct bfd_link_info *info)
+{
+  struct mips_elf_hash_sort_data hsd;
+  struct mips_got_info *g;
+  bfd *dynobj;
+
+  dynobj = elf_hash_table (info)->dynobj;
+
+  g = mips_elf_got_info (dynobj, NULL);
+
+  hsd.low = NULL;
+  mips_elf_link_hash_traverse (((struct mips_elf_link_hash_table *)
+				elf_hash_table (info)),
+			       mips_elf_sort_gnu_hash_table_f,
+			       &hsd);
+  /* Now we know which dynamic symbole has the lowest dynamic symbol
+     table index in the GOT. */
+  g->global_gotsym = hsd.low;
+
+  return TRUE;
+}
+
+static bfd_boolean
+mips_elf_sort_gnu_hash_table_f (struct mips_elf_link_hash_entry *h, void *data)
+{
+  struct mips_elf_hash_sort_data *hsd = data;
+
+  if (h->root.root.type == bfd_link_hash_warning)
+    h = (struct mips_elf_link_hash_entry *) h->root.root.u.i.link;
+
+  /* Symbols without dynamic symbol table entries aren't interesting
+     at all */
+  if (h->root.dynindx == -1)
+    return TRUE;
+
+  /* For gnu hash, symbols that don't need got is forced to have got entry.
+     This is redundant, but since gnu hash restricts the .dynsym order and
+     symbols that don't need got is *not* placed on upper part of external
+     part of got, it is forced to have got entry.
+     Track the lowest entry. */
+  if (hsd->low == NULL)
+    hsd->low = (struct elf_link_hash_entry *)h;
+  else if (hsd->low->dynindx > h->root.dynindx)
+    hsd->low = (struct elf_link_hash_entry *)h;
+
+  /* Mark symbols that really needs GOT entry.
+     Global symbols that don't need GOT entries get -1.
+     We mark entry that really need GOT to st_other member.
+     Also refer to glibc's mips/dl-machine.h */
+  if (h->root.got.offset != MINUS_ONE)
+    h->root.other |= STO_MIPS_GNUHASH;
+
+  return TRUE;
+}
+
 /* If H is a symbol that needs a global GOT entry, but has a dynamic
    symbol table index lower than any we've seen to date, record it for
    posterity.  */
@@ -3537,8 +3597,12 @@ mips_elf_multi_got (bfd *abfd, struct bf
   set_got_offset_arg.value = 1;
   htab_traverse (g->got_entries, mips_elf_set_global_got_offset,
 		 &set_got_offset_arg);
-  if (! mips_elf_sort_hash_table (info, 1))
-    return FALSE;
+  if (info->emit_hash)
+    if (! mips_elf_sort_hash_table (info, 1))
+      return FALSE;
+  if (info->emit_gnu_hash)
+    if (! mips_elf_sort_gnu_hash_table (info))
+      return FALSE;
 
   /* Now go through the GOTs assigning them offset ranges.
      [assigned_gotno, local_gotno[ will be set to the range of local
@@ -7284,11 +7348,19 @@ _bfd_mips_elf_always_size_sections (bfd 
      higher.  Therefore, it make sense to put those symbols
      that need GOT entries at the end of the symbol table.  We
      do that here.  */
-  if (! mips_elf_sort_hash_table (info, 1))
-    return FALSE;
+  if (info->emit_hash)
+    if (! mips_elf_sort_hash_table (info, 1))
+      return FALSE;
+  if (info->emit_gnu_hash)
+    if (! mips_elf_sort_gnu_hash_table (info))
+      return FALSE;
 
-  if (g->global_gotsym != NULL)
+  if (g->global_gotsym != NULL) {
     i = elf_hash_table (info)->dynsymcount - g->global_gotsym->dynindx;
+    if (info->emit_gnu_hash) {
+      i += g->global_gotsym->dynindx;
+    }
+  }
   else
     /* If there are no global symbols, or none requiring
        relocations, then GLOBAL_GOTSYM will be NULL.  */
@@ -7519,6 +7591,18 @@ _bfd_mips_elf_size_dynamic_sections (bfd
 	      needed_relocs += arg.needed;
 	    }
 
+	  /*  -export-dynamic might have increased the symbol. For gnu hash
+	      to keep 1:1 entry with dynsym and got, increase additional sym
+	      to got entry. */
+	  if (info->emit_gnu_hash)
+	    {
+	      int increase;
+	      increase = elf_hash_table (info)->dynsymcount - g->global_gotno;
+	      s->size += increase * MIPS_ELF_GOT_SIZE (output_bfd);
+	      g->global_gotno += increase;
+	      mips_elf_resolve_final_got_entries (g);
+	    }
+
 	  if (needed_relocs)
 	    mips_elf_allocate_dynamic_relocations (dynobj, info,
 						   needed_relocs);
@@ -10303,8 +10387,12 @@ _bfd_mips_elf_final_link (bfd *abfd, str
 	 section above.  */
 
       dynsecsymcount = count_section_dynsyms (abfd, info);
-      if (! mips_elf_sort_hash_table (info, dynsecsymcount + 1))
-	return FALSE;
+      if (info->emit_hash)
+	if (! mips_elf_sort_hash_table (info, dynsecsymcount + 1))
+	  return FALSE;
+      if (info->emit_gnu_hash)
+	if (! mips_elf_sort_gnu_hash_table (info))
+	  return FALSE;
 
       /* Make sure we didn't grow the global .got region.  */
       dynobj = elf_hash_table (info)->dynobj;
Index: binutils-2.17.50.0.15/ld/emultempl/mipself.em
===================================================================
--- binutils-2.17.50.0.15/ld/emultempl/mipself.em
+++ binutils-2.17.50.0.15/ld/emultempl/mipself.em
@@ -24,12 +24,18 @@ mips_after_parse (void)
   /* .gnu.hash and the MIPS ABI require .dynsym to be sorted in different
      ways.  .gnu.hash needs symbols to be grouped by hash code whereas the
      MIPS ABI requires a mapping between the GOT and the symbol table.  */
-  if (link_info.emit_gnu_hash)
+  /* This constraint is solved by re-ordering GOT section, GOT is now
+     sorted in 1:1 with gnu hash, which is also 1:1 mapping with .dynsym */
+  if (link_info.emit_gnu_hash && 0)
     {
       einfo ("%X%P: .gnu.hash is incompatible with the MIPS ABI\n");
       link_info.emit_hash = TRUE;
       link_info.emit_gnu_hash = FALSE;
     }
+  /* In current MIPS gnu hash method, both is not an option. force it
+     to gnu hash if both is selected. */
+  if (link_info.emit_gnu_hash && link_info.emit_hash)
+    link_info.emit_hash = FALSE;
   after_parse_default ();
 }
 EOF
Index: binutils-2.17.50.0.15/binutils/readelf.c
===================================================================
--- binutils-2.17.50.0.15/binutils/readelf.c
+++ binutils-2.17.50.0.15/binutils/readelf.c
@@ -6958,6 +6958,7 @@ get_mips_symbol_other (unsigned int othe
     {
     case STO_OPTIONAL:  return "OPTIONAL";
     case STO_MIPS16:    return "MIPS16";
+    case STO_MIPS_GNUHASH: return "GNUHASH";
     default:      	return NULL;
     }
 }
Index: binutils-2.17.50.0.15/include/elf/mips.h
===================================================================
--- binutils-2.17.50.0.15/include/elf/mips.h
+++ binutils-2.17.50.0.15/include/elf/mips.h
@@ -727,6 +727,9 @@ extern void bfd_mips_elf32_swap_reginfo_
    is optional - if, at final link time, it cannot be found, no
    error message should be produced.  */
 #define STO_OPTIONAL		(1 << 2)
+/* This bit is used to mark symbol that needs GOT entry when
+   gnu hash is specified as hash style. */
+#define STO_MIPS_GNUHASH         (1 << 3)
 /* A macro to examine the STO_OPTIONAL bit.  */
 #define ELF_MIPS_IS_OPTIONAL(other)	((other) & STO_OPTIONAL)
 

Index: glibc-2.5/glibc-ports-2.5/sysdeps/mips/dl-machine.h
===================================================================
--- glibc-2.5/glibc-ports-2.5/sysdeps/mips/dl-machine.h
+++ glibc-2.5/glibc-ports-2.5/sysdeps/mips/dl-machine.h
@@ -487,6 +487,7 @@ elf_machine_got_rel (struct link_map *ma
   ElfW(Sym) *sym;
   const ElfW(Half) *vernum;
   int i, n, symidx;
+  int is_gnuhash;
 
 #define RESOLVE_GOTSYM(sym,vernum,sym_index)				  \
     ({									  \
@@ -529,10 +530,18 @@ elf_machine_got_rel (struct link_map *ma
   sym = (ElfW(Sym) *) D_PTR (map, l_info[DT_SYMTAB]) + symidx;
   i = (map->l_info[DT_MIPS (SYMTABNO)]->d_un.d_val
        - map->l_info[DT_MIPS (GOTSYM)]->d_un.d_val);
+  /* check hash style */
+  is_gnuhash = map->l_info[DT_ADDRTAGIDX (DT_GNU_HASH) + DT_NUM
+			   + DT_THISPROCNUM + DT_VERSIONTAGNUM
+			   + DT_EXTRANUM + DT_VALNUM];
 
   /* This loop doesn't handle Quickstart.  */
   while (i--)
     {
+      /* in gnu hash, skip symbol that doesn't need GOT entries */
+      if (is_gnuhash && (sym->st_other & STO_MIPS_GNUHASH) != STO_MIPS_GNUHASH)
+	goto skip;
+
       if (sym->st_shndx == SHN_UNDEF)
 	{
 	  if (ELFW(ST_TYPE) (sym->st_info) == STT_FUNC
@@ -555,6 +564,7 @@ elf_machine_got_rel (struct link_map *ma
       else
 	*got = RESOLVE_GOTSYM (sym, vernum, symidx);
 
+  skip:
       ++got;
       ++sym;
       ++symidx;
Index: glibc-2.5/elf/elf.h
===================================================================
--- glibc-2.5/elf/elf.h
+++ glibc-2.5/elf/elf.h
@@ -1366,6 +1366,7 @@ typedef struct
 #define STO_MIPS_INTERNAL		0x1
 #define STO_MIPS_HIDDEN			0x2
 #define STO_MIPS_PROTECTED		0x3
+#define STO_MIPS_GNUHASH		(1 << 3)
 #define STO_MIPS_SC_ALIGN_UNUSED	0xff
 
 /* MIPS specific values for `st_info'.  */