Adjust for final version of GNU-style hash table format.

8 files changed, 238 insertions, 49 deletions

diff --git a/libelf/ChangeLog b/libelf/ChangeLog
index 7967107f..424eddc4 100644
--- a/libelf/ChangeLog
+++ b/libelf/ChangeLog
@@ -1,3 +1,10 @@
+2006-07-11  Ulrich Drepper  <drepper@redhat.com>
+
+	* libelf.h: Define ELF_T_GNUHASH.
+	* elf_getdata.c (TYPEIDX): Handle SHT_GNU_HASH.
+	(shtype_map): Add SHT_GNU_HASH entries.
+	* gelf_xlate.c (__elf_xfctstom): Add ELF_T_GNUHASH entries.
+
 2006-07-06  Ulrich Drepper  <drepper@redhat.com>
 
 	* elf_gnu_hash.c: New file.
diff --git a/libelf/elf_getdata.c b/libelf/elf_getdata.c
index 676f0a07..5e37cbeb 100644
--- a/libelf/elf_getdata.c
+++ b/libelf/elf_getdata.c
@@ -1,5 +1,5 @@
 /* Return the next data element from the section after possibly converting it.
-   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Red Hat, Inc.
+   Copyright (C) 1998-2005, 2006 Red Hat, Inc.
    This file is part of Red Hat elfutils.
    Written by Ulrich Drepper <drepper@redhat.com>, 1998.
 
@@ -73,8 +73,8 @@
 #define TYPEIDX(Sh_Type) \
   (Sh_Type >= SHT_NULL && Sh_Type < SHT_NUM				      \
    ? Sh_Type								      \
-   : (Sh_Type >= SHT_GNU_LIBLIST && Sh_Type <= SHT_HISUNW		      \
-      ? SHT_NUM + Sh_Type - SHT_GNU_LIBLIST				      \
+   : (Sh_Type >= SHT_GNU_HASH && Sh_Type <= SHT_HISUNW			      \
+      ? SHT_NUM + Sh_Type - SHT_GNU_HASH				      \
       : 0))
 
 static const struct
@@ -131,12 +131,16 @@ static const struct
       [TYPEIDX (SHT_SUNW_move)] = { ELF_T_MOVE, sizeof (ElfW2(Bits,Move))     \
 				    AL (__alignof__ (ElfW2(Bits,Move))) },    \
       [TYPEIDX (SHT_GNU_LIBLIST)] = { ELF_T_LIB, sizeof (ElfW2(Bits,Lib))     \
-				    AL (__alignof__ (ElfW2(Bits,Lib))) }
-      DEFINE (32)
+				      AL (__alignof__ (ElfW2(Bits,Lib))) }
+      DEFINE (32),
+      [TYPEIDX (SHT_GNU_HASH)] = { ELF_T_WORD, sizeof (Elf32_Word)
+				   AL (__alignof__ (Elf32_Word)) }
     },
     [ELFCLASS64 - 1] =
     {
-      DEFINE (64)
+      DEFINE (64),
+      [TYPEIDX (SHT_GNU_HASH)] = { ELF_T_GNUHASH, 1
+				   AL (__alignof__ (Elf64_Xword)) }
     }
   }
 };
@@ -335,8 +339,8 @@ __libelf_set_rawdata (Elf_Scn *scn)
       GElf_Ehdr ehdr_mem;
 
       scn->rawdata.d.d_type
-	= (SH_ENTSIZE_HASH (INTUSE(gelf_getehdr) (elf, &ehdr_mem))
-	   == 4 ? ELF_T_WORD : ELF_T_XWORD);
+	= (SH_ENTSIZE_HASH (INTUSE(gelf_getehdr) (elf, &ehdr_mem)) == 4
+	   ? ELF_T_WORD : ELF_T_XWORD);
     }
   else
     {
diff --git a/libelf/gelf_xlate.c b/libelf/gelf_xlate.c
index 34e74d00..f1bbdf3a 100644
--- a/libelf/gelf_xlate.c
+++ b/libelf/gelf_xlate.c
@@ -1,5 +1,5 @@
 /* Transformation functions for ELF data types.
-   Copyright (C) 1998, 1999, 2000, 2002, 2004, 2005 Red Hat, Inc.
+   Copyright (C) 1998, 1999, 2000, 2002, 2004, 2005, 2006 Red Hat, Inc.
    This file is part of Red Hat elfutils.
    Written by Ulrich Drepper <drepper@redhat.com>, 1998.
 
@@ -184,6 +184,7 @@ union unaligned
 /* We have a few functions which we must create by hand since the sections
    do not contain records of only one type.  */
 #include "version_xlate.h"
+#include "gnuhash_xlate.h"
 
 
 /* Now the externally visible table with the function pointers.  */
@@ -216,10 +217,12 @@ const xfct_t __elf_xfctstom[EV_NUM - 1][EV_NUM - 1][ELFCLASSNUM - 1][ELF_T_NUM]
 	[ELF_T_SYMINFO] = ElfW2(Bits, cvt_Syminfo),			      \
 	[ELF_T_MOVE]	= ElfW2(Bits, cvt_Move),			      \
 	[ELF_T_LIB]	= ElfW2(Bits, cvt_Lib)
-        define_xfcts (32)
+        define_xfcts (32),
+	[ELF_T_GNUHASH] = Elf32_cvt_Word
       },
       [ELFCLASS64 - 1] = {
-	define_xfcts (64)
+	define_xfcts (64),
+	[ELF_T_GNUHASH] = elf_cvt_gnuhash
       }
     }
   }
diff --git a/libelf/gnuhash_xlate.h b/libelf/gnuhash_xlate.h
new file mode 100644
index 00000000..9012ffa1
--- /dev/null
+++ b/libelf/gnuhash_xlate.h
@@ -0,0 +1,95 @@
+/* Conversion functions for versioning information.
+   Copyright (C) 2006 Red Hat, Inc.
+   This file is part of Red Hat elfutils.
+   Written by Ulrich Drepper <drepper@redhat.com>, 2006.
+
+   Red Hat elfutils is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by the
+   Free Software Foundation; version 2 of the License.
+
+   Red Hat elfutils is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License along
+   with Red Hat elfutils; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
+
+   In addition, as a special exception, Red Hat, Inc. gives You the
+   additional right to link the code of Red Hat elfutils with code licensed
+   under any Open Source Initiative certified open source license
+   (http://www.opensource.org/licenses/index.php) which requires the
+   distribution of source code with any binary distribution and to
+   distribute linked combinations of the two.  Non-GPL Code permitted under
+   this exception must only link to the code of Red Hat elfutils through
+   those well defined interfaces identified in the file named EXCEPTION
+   found in the source code files (the "Approved Interfaces").  The files
+   of Non-GPL Code may instantiate templates or use macros or inline
+   functions from the Approved Interfaces without causing the resulting
+   work to be covered by the GNU General Public License.  Only Red Hat,
+   Inc. may make changes or additions to the list of Approved Interfaces.
+   Red Hat's grant of this exception is conditioned upon your not adding
+   any new exceptions.  If you wish to add a new Approved Interface or
+   exception, please contact Red Hat.  You must obey the GNU General Public
+   License in all respects for all of the Red Hat elfutils code and other
+   code used in conjunction with Red Hat elfutils except the Non-GPL Code
+   covered by this exception.  If you modify this file, you may extend this
+   exception to your version of the file, but you are not obligated to do
+   so.  If you do not wish to provide this exception without modification,
+   you must delete this exception statement from your version and license
+   this file solely under the GPL without exception.
+
+   Red Hat elfutils is an included package of the Open Invention Network.
+   An included package of the Open Invention Network is a package for which
+   Open Invention Network licensees cross-license their patents.  No patent
+   license is granted, either expressly or impliedly, by designation as an
+   included package.  Should you wish to participate in the Open Invention
+   Network licensing program, please visit www.openinventionnetwork.com
+   <http://www.openinventionnetwork.com>.  */
+
+#include <assert.h>
+#include <gelf.h>
+
+#include "libelfP.h"
+
+
+static void
+elf_cvt_gnuhash (void *dest, const void *src, size_t len, int encode)
+{
+  /* The GNU hash table format on 64 bit machines mixes 32 bit and 64 bit
+     words.  We must detangle them here.   */
+  Elf32_Word *dest32 = dest;
+  const Elf32_Word *src32 = src;
+
+  /* First four control words, 32 bits.  */
+  for (unsigned int cnt = 0; cnt < 4; ++cnt)
+    {
+      if (len < 4)
+	return;
+      dest32[cnt] = bswap_32 (src32[cnt]);
+      len -= 4;
+    }
+
+  Elf32_Word bitmask_words = encode ? src32[2] : dest32[2];
+
+  /* Now the 64 bit words.  */
+  Elf64_Xword *dest64 = (Elf64_Xword *) &dest32[4];
+  const Elf64_Xword *src64 = (const Elf64_Xword *) &src32[4];
+  for (unsigned int cnt = 0; cnt < bitmask_words; ++cnt)
+    {
+      if (len < 8)
+	return;
+      dest64[cnt] = bswap_64 (src64[cnt]);
+      len -= 8;
+    }
+
+  /* The rest are 32 bit words again.  */
+  src32 = (const Elf32_Word *) &src64[bitmask_words];
+  dest32 = (Elf32_Word *) &dest64[bitmask_words];
+  while (len > 4)
+    {
+      *dest32++ = bswap_32 (*src32++);
+      len -= 4;
+    }
+}
diff --git a/libelf/libelf.h b/libelf/libelf.h
index d8d8487c..2f58e4c4 100644
--- a/libelf/libelf.h
+++ b/libelf/libelf.h
@@ -82,6 +82,7 @@ typedef enum
   ELF_T_SYMINFO,		/* Elf32_Syminfo, Elf64_Syminfo, ... */
   ELF_T_MOVE,			/* Elf32_Move, Elf64_Move, ... */
   ELF_T_LIB,			/* Elf32_Lib, Elf64_Lib, ... */
+  ELF_T_GNUHASH,		/* GNU-style hash section.  */
   /* Keep this the last entry.  */
   ELF_T_NUM
 } Elf_Type;
diff --git a/src/ChangeLog b/src/ChangeLog
index 1c153b00..7ac79785 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,8 @@
+2006-07-11  Ulrich Drepper  <drepper@redhat.com>
+
+	* readelf.c (handle_gnu_hash): Adjust for final form of .gnu.hash.
+	* elflint.c (check_gnu_hash): Likewise.
+
 2006-07-06  Ulrich Drepper  <drepper@redhat.com>
 
 	* elflint.c: Adjust for latest new hash table format.
diff --git a/src/elflint.c b/src/elflint.c
index a679acc4..b0aa9ab0 100644
--- a/src/elflint.c
+++ b/src/elflint.c
@@ -1897,17 +1897,34 @@ check_gnu_hash (Ebl *ebl, GElf_Shdr *shdr, Elf_Data *data, int idx,
 {
   Elf32_Word nbuckets = ((Elf32_Word *) data->d_buf)[0];
   Elf32_Word symbias = ((Elf32_Word *) data->d_buf)[1];
+  Elf32_Word bitmask_words = ((Elf32_Word *) data->d_buf)[2];
 
-  if (shdr->sh_size < (2 + 2 * nbuckets) * sizeof (Elf32_Word))
+  if (!powerof2 (bitmask_words))
+    ERROR (gettext ("\
+section [%2d] '%s': bitmask size not power of 2: %u\n"),
+	   idx, section_name (ebl, idx), bitmask_words);
+
+  size_t bitmask_idxmask = bitmask_words - 1;
+  if (gelf_getclass (ebl->elf) == ELFCLASS64)
+    bitmask_words *= 2;
+  Elf32_Word shift = ((Elf32_Word *) data->d_buf)[3];
+
+  if (shdr->sh_size < (4 + bitmask_words + nbuckets) * sizeof (Elf32_Word))
     {
       ERROR (gettext ("\
 section [%2d] '%s': hash table section is too small (is %ld, expected at least%ld)\n"),
 	     idx, section_name (ebl, idx), (long int) shdr->sh_size,
-	     (long int) ((2 + 2 * nbuckets) * sizeof (Elf32_Word)));
+	     (long int) ((4 + bitmask_words + nbuckets) * sizeof (Elf32_Word)));
       return;
     }
 
-  size_t maxidx = shdr->sh_size / sizeof (Elf32_Word) - (2 + 2 * nbuckets);
+  if (shift > 31)
+    ERROR (gettext ("\
+section [%2d] '%s': 2nd hash function shift too big: %u\n"),
+	   idx, section_name (ebl, idx), shift);
+
+  size_t maxidx = shdr->sh_size / sizeof (Elf32_Word) - (4 + bitmask_words
+							 + nbuckets);
 
   if (symshdr != NULL)
     maxidx = MIN (maxidx, symshdr->sh_size / symshdr->sh_entsize);
@@ -1915,35 +1932,36 @@ section [%2d] '%s': hash table section is too small (is %ld, expected at least%l
   /* We need the symbol section data.  */
   Elf_Data *symdata = elf_getdata (elf_getscn (ebl->elf, shdr->sh_link), NULL);
 
+  union
+  {
+    Elf32_Word *p32;
+    Elf64_Xword *p64;
+  } bitmask = { .p32 = &((Elf32_Word *) data->d_buf)[4] },
+      collected = { .p32 = xcalloc (bitmask_words, sizeof (Elf32_Word)) };
+
+  size_t classbits = gelf_getclass (ebl->elf) == ELFCLASS32 ? 32 : 64;
+
   size_t cnt;
-  for (cnt = 2; cnt < 2 + 2 * nbuckets; cnt += 2)
+  for (cnt = 4 + bitmask_words; cnt < 4 + bitmask_words + nbuckets; ++cnt)
     {
-      Elf32_Word bitset = ((Elf32_Word *) data->d_buf)[cnt];
-      Elf32_Word symidx = ((Elf32_Word *) data->d_buf)[cnt + 1];
+      Elf32_Word symidx = ((Elf32_Word *) data->d_buf)[cnt];
 
       if (symidx == 0)
-	{
-	  /* Nothing in here.  No bit in the bitset should be set either.  */
-	  if (bitset != 0)
-	    ERROR (gettext ("\
-section [%2d] '%s': hash chain for bucket %zu empty but bitset is not\n"),
-		   idx, section_name (ebl, idx), cnt / 2 - 1);
-
-	  continue;
-	}
+	continue;
 
       if (symidx < symbias)
 	{
 	  ERROR (gettext ("\
 section [%2d] '%s': hash chain for bucket %zu lower than symbol index bias\n"),
-		 idx, section_name (ebl, idx), cnt / 2 - 1);
+		 idx, section_name (ebl, idx), cnt - (4 + bitmask_words));
 	  continue;
 	}
 
-      Elf32_Word collected_bitset = 0;
       while (symidx - symbias < maxidx)
 	{
-	  Elf32_Word chainhash = ((Elf32_Word *) data->d_buf)[2 + 2 * nbuckets
+	  Elf32_Word chainhash = ((Elf32_Word *) data->d_buf)[4
+							      + bitmask_words
+							      + nbuckets
 							      + symidx
 							      - symbias];
 
@@ -1966,11 +1984,26 @@ section [%2d] '%s': symbol %u referenced in chain for bucket %zu is undefined\n"
 		    ERROR (gettext ("\
 section [%2d] '%s': hash value for symbol %u in chain for bucket %zu wrong\n"),
 			   idx, section_name (ebl, idx), symidx, cnt / 2 - 1);
+
+		  /* Set the bits in the bitmask.  */
+		  size_t maskidx = (hval / classbits) & bitmask_idxmask;
+		  if (classbits == 32)
+		    {
+		      collected.p32[maskidx]
+			|= UINT32_C (1) << (hval & (classbits - 1));
+		      collected.p32[maskidx]
+			|= UINT32_C (1) << ((hval >> shift) & (classbits - 1));
+		    }
+		  else
+		    {
+		      collected.p64[maskidx]
+			|= UINT64_C (1) << (hval & (classbits - 1));
+		      collected.p64[maskidx]
+			|= UINT64_C (1) << ((hval >> shift) & (classbits - 1));
+		    }
 		}
 	    }
 
-	  collected_bitset |= 1 << ((chainhash >> 5) & 31);
-
 	  if ((chainhash & 1) != 0)
 	    break;
 
@@ -1986,13 +2019,14 @@ section [%2d] '%s': hash chain for bucket %zu out of bounds\n"),
 	ERROR (gettext ("\
 section [%2d] '%s': symbol reference in chain for bucket %zu out of bounds\n"),
 	       idx, section_name (ebl, idx), cnt / 2 - 1);
-
-      if (bitset != collected_bitset)
-	ERROR (gettext ("\
-section [%2d] '%s': bitset for bucket %zu does not match chain entries: computed %#x, reported %#x\n"),
-	       idx, section_name (ebl, idx), cnt / 2 - 1,
-	       collected_bitset, bitset);
     }
+
+  if (memcmp (collected.p32, bitmask.p32, bitmask_words * sizeof (Elf32_Word)))
+    ERROR (gettext ("\
+section [%2d] '%s': bitmask does not match names in the hash table\n"),
+	   idx, section_name (ebl, idx));
+
+  free (collected.p32);
 }
 
 
@@ -2024,7 +2058,8 @@ section [%2d] '%s': hash table not for dynamic symbol table\n"),
 	   idx, section_name (ebl, idx));
 
   if (shdr->sh_entsize != (tag == SHT_GNU_HASH
-			   ? sizeof (Elf32_Word)
+			   ? (gelf_getclass (ebl->elf) == ELFCLASS32
+			      ? sizeof (Elf32_Word) : 0)
 			   : (size_t) ebl_sysvhash_entrysize (ebl)))
     ERROR (gettext ("\
 section [%2d] '%s': hash table entry size incorrect\n"),
@@ -2034,10 +2069,10 @@ section [%2d] '%s': hash table entry size incorrect\n"),
     ERROR (gettext ("section [%2d] '%s': not marked to be allocated\n"),
 	   idx, section_name (ebl, idx));
 
-  if (shdr->sh_size < 2 * shdr->sh_entsize)
+  if (shdr->sh_size < (tag == SHT_GNU_HASH ? 4 : 2) * (shdr->sh_entsize ?: 4))
     {
       ERROR (gettext ("\
-section [%2d] '%s': hash table has not even room for initial two administrative entries\n"),
+section [%2d] '%s': hash table has not even room for initial administrative entries\n"),
 	     idx, section_name (ebl, idx));
       return;
     }
@@ -2056,7 +2091,7 @@ section [%2d] '%s': hash table has not even room for initial two administrative
       break;
 
     default:
-      assert (! "should not  happen");
+      assert (! "should not happen");
     }
 }
 
diff --git a/src/readelf.c b/src/readelf.c
index 9fbc24d6..eba6dd81 100644
--- a/src/readelf.c
+++ b/src/readelf.c
@@ -2323,7 +2323,7 @@ handle_versym (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr)
 static void
 print_hash_info (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx,
 		 uint_fast32_t maxlength, Elf32_Word nbucket,
-		 uint_fast32_t nsyms, uint32_t *lengths)
+		 uint_fast32_t nsyms, uint32_t *lengths, const char *extrastr)
 {
   uint32_t *counts = (uint32_t *) xcalloc (maxlength + 1, sizeof (uint32_t));
 
@@ -2347,6 +2347,9 @@ print_hash_info (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx,
 		      gelf_getshdr (elf_getscn (ebl->elf, shdr->sh_link),
 				    &glink)->sh_name));
 
+  if (extrastr != NULL)
+    fputs (extrastr, stdout);
+
   if (nbucket > 0)
     {
       uint64_t success = 0;
@@ -2419,7 +2422,7 @@ handle_sysv_hash (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx)
     }
 
   print_hash_info (ebl, scn, shdr, shstrndx, maxlength, nbucket, nsyms,
-		   lengths);
+		   lengths, NULL);
 
   free (lengths);
 }
@@ -2461,7 +2464,7 @@ handle_sysv_hash64 (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx)
     }
 
   print_hash_info (ebl, scn, shdr, shstrndx, maxlength, nbucket, nsyms,
-		   lengths);
+		   lengths, NULL);
 
   free (lengths);
 }
@@ -2481,17 +2484,30 @@ handle_gnu_hash (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx)
 
   Elf32_Word nbucket = ((Elf32_Word *) data->d_buf)[0];
   Elf32_Word symbias = ((Elf32_Word *) data->d_buf)[1];
-  Elf32_Word *bucket = &((Elf32_Word *) data->d_buf)[2];
-  Elf32_Word *chain = &((Elf32_Word *) data->d_buf)[2 + 2 * nbucket];
+
+  /* Next comes the size of the bitmap.  It's measured in words for
+     the architecture.  It's 32 bits for 32 bit archs, and 64 bits for
+     64 bit archs.  */
+  Elf32_Word bitmask_words = ((Elf32_Word *) data->d_buf)[2];
+  if (gelf_getclass (ebl->elf) == ELFCLASS64)
+    bitmask_words *= 2;
+
+  Elf32_Word shift = ((Elf32_Word *) data->d_buf)[3];
 
   uint32_t *lengths = (uint32_t *) xcalloc (nbucket, sizeof (uint32_t));
 
+  Elf32_Word *bitmask = &((Elf32_Word *) data->d_buf)[4];
+  Elf32_Word *bucket = &((Elf32_Word *) data->d_buf)[4 + bitmask_words];
+  Elf32_Word *chain = &((Elf32_Word *) data->d_buf)[4 + bitmask_words
+						    + nbucket];
+
+  /* Compute distribution of chain lengths.  */
   uint_fast32_t maxlength = 0;
   uint_fast32_t nsyms = 0;
   for (Elf32_Word cnt = 0; cnt < nbucket; ++cnt)
-    if (bucket[2 * cnt + 1] != 0)
+    if (bucket[cnt] != 0)
       {
-	Elf32_Word inner = bucket[2 * cnt + 1] - symbias;
+	Elf32_Word inner = bucket[cnt] - symbias;
 	do
 	  {
 	    ++nsyms;
@@ -2501,9 +2517,32 @@ handle_gnu_hash (Ebl *ebl, Elf_Scn *scn, GElf_Shdr *shdr, size_t shstrndx)
 	while ((chain[inner++] & 1) == 0);
       }
 
+  /* Count bits in bitmask.  */
+  uint_fast32_t nbits = 0;
+  for (Elf32_Word cnt = 0; cnt < bitmask_words; ++cnt)
+    {
+      uint_fast32_t word = bitmask[cnt];
+
+      word = (word & 0x55555555) + ((word >> 1) & 0x55555555);
+      word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
+      word = (word & 0x0f0f0f0f) + ((word >> 4) & 0x0f0f0f0f);
+      word = (word & 0x00ff00ff) + ((word >> 8) & 0x00ff00ff);
+      nbits += (word & 0x0000ffff) + ((word >> 16) & 0x0000ffff);
+    }
+
+  char *str;
+  if (asprintf (&str, gettext ("\
+ Symbol Bias: %u\n\
+ Bitmask Size: %zu bytes  %" PRIuFAST32 "%% bits set  2nd hash shift: %u\n"),
+		symbias, bitmask_words * sizeof (Elf32_Word),
+		(nbits * 100 + 50) / (bitmask_words * sizeof (Elf32_Word) * 8),
+		shift) == -1)
+    error (EXIT_FAILURE, 0, gettext ("memory exhausted"));
+
   print_hash_info (ebl, scn, shdr, shstrndx, maxlength, nbucket, nsyms,
-		   lengths);
+		   lengths, str);
 
+  free (str);
   free (lengths);
 }