Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /* ELF strtab with GC and suffix merging support.
  2.    Copyright 2001, 2002, 2003, 2005, 2006, 2007, 2008
  3.    Free Software Foundation, Inc.
  4.    Written by Jakub Jelinek <jakub@redhat.com>.
  5.  
  6.    This file is part of BFD, the Binary File Descriptor library.
  7.  
  8.    This program is free software; you can redistribute it and/or modify
  9.    it under the terms of the GNU General Public License as published by
  10.    the Free Software Foundation; either version 3 of the License, or
  11.    (at your option) any later version.
  12.  
  13.    This program is distributed in the hope that it will be useful,
  14.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.    GNU General Public License for more details.
  17.  
  18.    You should have received a copy of the GNU General Public License
  19.    along with this program; if not, write to the Free Software
  20.    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  21.    MA 02110-1301, USA.  */
  22.  
  23. #include "sysdep.h"
  24. #include "bfd.h"
  25. #include "libbfd.h"
  26. #include "elf-bfd.h"
  27. #include "hashtab.h"
  28. #include "libiberty.h"
  29.  
  30. /* An entry in the strtab hash table.  */
  31.  
  32. struct elf_strtab_hash_entry
  33. {
  34.   struct bfd_hash_entry root;
  35.   /* Length of this entry.  This includes the zero terminator.  */
  36.   int len;
  37.   unsigned int refcount;
  38.   union {
  39.     /* Index within the merged section.  */
  40.     bfd_size_type index;
  41.     /* Entry this is a suffix of (if len < 0).  */
  42.     struct elf_strtab_hash_entry *suffix;
  43.   } u;
  44. };
  45.  
  46. /* The strtab hash table.  */
  47.  
  48. struct elf_strtab_hash
  49. {
  50.   struct bfd_hash_table table;
  51.   /* Next available index.  */
  52.   bfd_size_type size;
  53.   /* Number of array entries alloced.  */
  54.   bfd_size_type alloced;
  55.   /* Final strtab size.  */
  56.   bfd_size_type sec_size;
  57.   /* Array of pointers to strtab entries.  */
  58.   struct elf_strtab_hash_entry **array;
  59. };
  60.  
  61. /* Routine to create an entry in a section merge hashtab.  */
  62.  
  63. static struct bfd_hash_entry *
  64. elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
  65.                          struct bfd_hash_table *table,
  66.                          const char *string)
  67. {
  68.   /* Allocate the structure if it has not already been allocated by a
  69.      subclass.  */
  70.   if (entry == NULL)
  71.     entry = (struct bfd_hash_entry *)
  72.         bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
  73.   if (entry == NULL)
  74.     return NULL;
  75.  
  76.   /* Call the allocation method of the superclass.  */
  77.   entry = bfd_hash_newfunc (entry, table, string);
  78.  
  79.   if (entry)
  80.     {
  81.       /* Initialize the local fields.  */
  82.       struct elf_strtab_hash_entry *ret;
  83.  
  84.       ret = (struct elf_strtab_hash_entry *) entry;
  85.       ret->u.index = -1;
  86.       ret->refcount = 0;
  87.       ret->len = 0;
  88.     }
  89.  
  90.   return entry;
  91. }
  92.  
  93. /* Create a new hash table.  */
  94.  
  95. struct elf_strtab_hash *
  96. _bfd_elf_strtab_init (void)
  97. {
  98.   struct elf_strtab_hash *table;
  99.   bfd_size_type amt = sizeof (struct elf_strtab_hash);
  100.  
  101.   table = (struct elf_strtab_hash *) bfd_malloc (amt);
  102.   if (table == NULL)
  103.     return NULL;
  104.  
  105.   if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
  106.                             sizeof (struct elf_strtab_hash_entry)))
  107.     {
  108.       free (table);
  109.       return NULL;
  110.     }
  111.  
  112.   table->sec_size = 0;
  113.   table->size = 1;
  114.   table->alloced = 64;
  115.   amt = sizeof (struct elf_strtab_hasn_entry *);
  116.   table->array = (struct elf_strtab_hash_entry **)
  117.       bfd_malloc (table->alloced * amt);
  118.   if (table->array == NULL)
  119.     {
  120.       free (table);
  121.       return NULL;
  122.     }
  123.  
  124.   table->array[0] = NULL;
  125.  
  126.   return table;
  127. }
  128.  
  129. /* Free a strtab.  */
  130.  
  131. void
  132. _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
  133. {
  134.   bfd_hash_table_free (&tab->table);
  135.   free (tab->array);
  136.   free (tab);
  137. }
  138.  
  139. /* Get the index of an entity in a hash table, adding it if it is not
  140.    already present.  */
  141.  
  142. bfd_size_type
  143. _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
  144.                      const char *str,
  145.                      bfd_boolean copy)
  146. {
  147.   register struct elf_strtab_hash_entry *entry;
  148.  
  149.   /* We handle this specially, since we don't want to do refcounting
  150.      on it.  */
  151.   if (*str == '\0')
  152.     return 0;
  153.  
  154.   BFD_ASSERT (tab->sec_size == 0);
  155.   entry = (struct elf_strtab_hash_entry *)
  156.           bfd_hash_lookup (&tab->table, str, TRUE, copy);
  157.  
  158.   if (entry == NULL)
  159.     return (bfd_size_type) -1;
  160.  
  161.   entry->refcount++;
  162.   if (entry->len == 0)
  163.     {
  164.       entry->len = strlen (str) + 1;
  165.       /* 2G strings lose.  */
  166.       BFD_ASSERT (entry->len > 0);
  167.       if (tab->size == tab->alloced)
  168.         {
  169.           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
  170.           tab->alloced *= 2;
  171.           tab->array = (struct elf_strtab_hash_entry **)
  172.               bfd_realloc_or_free (tab->array, tab->alloced * amt);
  173.           if (tab->array == NULL)
  174.             return (bfd_size_type) -1;
  175.         }
  176.  
  177.       entry->u.index = tab->size++;
  178.       tab->array[entry->u.index] = entry;
  179.     }
  180.   return entry->u.index;
  181. }
  182.  
  183. void
  184. _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
  185. {
  186.   if (idx == 0 || idx == (bfd_size_type) -1)
  187.     return;
  188.   BFD_ASSERT (tab->sec_size == 0);
  189.   BFD_ASSERT (idx < tab->size);
  190.   ++tab->array[idx]->refcount;
  191. }
  192.  
  193. void
  194. _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
  195. {
  196.   if (idx == 0 || idx == (bfd_size_type) -1)
  197.     return;
  198.   BFD_ASSERT (tab->sec_size == 0);
  199.   BFD_ASSERT (idx < tab->size);
  200.   BFD_ASSERT (tab->array[idx]->refcount > 0);
  201.   --tab->array[idx]->refcount;
  202. }
  203.  
  204. unsigned int
  205. _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, bfd_size_type idx)
  206. {
  207.   return tab->array[idx]->refcount;
  208. }
  209.  
  210. void
  211. _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
  212. {
  213.   bfd_size_type idx;
  214.  
  215.   for (idx = 1; idx < tab->size; idx++)
  216.     tab->array[idx]->refcount = 0;
  217. }
  218.  
  219. /* Downsizes strtab.  Entries from IDX up to the current size are
  220.    removed from the array.  */
  221. void
  222. _bfd_elf_strtab_restore_size (struct elf_strtab_hash *tab, bfd_size_type idx)
  223. {
  224.   bfd_size_type curr_size = tab->size;
  225.  
  226.   BFD_ASSERT (tab->sec_size == 0);
  227.   BFD_ASSERT (idx <= curr_size);
  228.   tab->size = idx;
  229.   for (; idx < curr_size; ++idx)
  230.     {
  231.       /* We don't remove entries from the hash table, just set their
  232.          REFCOUNT to zero.  Setting LEN zero will result in the size
  233.          growing if the entry is added again.  See _bfd_elf_strtab_add.  */
  234.       tab->array[idx]->refcount = 0;
  235.       tab->array[idx]->len = 0;
  236.     }
  237. }
  238.  
  239. bfd_size_type
  240. _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
  241. {
  242.   return tab->sec_size ? tab->sec_size : tab->size;
  243. }
  244.  
  245. bfd_size_type
  246. _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
  247. {
  248.   struct elf_strtab_hash_entry *entry;
  249.  
  250.   if (idx == 0)
  251.     return 0;
  252.   BFD_ASSERT (idx < tab->size);
  253.   BFD_ASSERT (tab->sec_size);
  254.   entry = tab->array[idx];
  255.   BFD_ASSERT (entry->refcount > 0);
  256.   entry->refcount--;
  257.   return tab->array[idx]->u.index;
  258. }
  259.  
  260. bfd_boolean
  261. _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
  262. {
  263.   bfd_size_type off = 1, i;
  264.  
  265.   if (bfd_bwrite ("", 1, abfd) != 1)
  266.     return FALSE;
  267.  
  268.   for (i = 1; i < tab->size; ++i)
  269.     {
  270.       register const char *str;
  271.       register unsigned int len;
  272.  
  273.       BFD_ASSERT (tab->array[i]->refcount == 0);
  274.       len = tab->array[i]->len;
  275.       if ((int) len < 0)
  276.         continue;
  277.  
  278.       str = tab->array[i]->root.string;
  279.       if (bfd_bwrite (str, len, abfd) != len)
  280.         return FALSE;
  281.  
  282.       off += len;
  283.     }
  284.  
  285.   BFD_ASSERT (off == tab->sec_size);
  286.   return TRUE;
  287. }
  288.  
  289. /* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
  290.  
  291. static int
  292. strrevcmp (const void *a, const void *b)
  293. {
  294.   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
  295.   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
  296.   unsigned int lenA = A->len;
  297.   unsigned int lenB = B->len;
  298.   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
  299.   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
  300.   int l = lenA < lenB ? lenA : lenB;
  301.  
  302.   while (l)
  303.     {
  304.       if (*s != *t)
  305.         return (int) *s - (int) *t;
  306.       s--;
  307.       t--;
  308.       l--;
  309.     }
  310.   return lenA - lenB;
  311. }
  312.  
  313. static inline int
  314. is_suffix (const struct elf_strtab_hash_entry *A,
  315.            const struct elf_strtab_hash_entry *B)
  316. {
  317.   if (A->len <= B->len)
  318.     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
  319.        not to be equal by the hash table.  */
  320.     return 0;
  321.  
  322.   return memcmp (A->root.string + (A->len - B->len),
  323.                  B->root.string, B->len - 1) == 0;
  324. }
  325.  
  326. /* This function assigns final string table offsets for used strings,
  327.    merging strings matching suffixes of longer strings if possible.  */
  328.  
  329. void
  330. _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
  331. {
  332.   struct elf_strtab_hash_entry **array, **a, *e;
  333.   bfd_size_type size, amt;
  334.  
  335.   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
  336.      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
  337.      Besides, indexing with a long long wouldn't give anything but extra
  338.      cycles.  */
  339.   size_t i;
  340.  
  341.   /* Sort the strings by suffix and length.  */
  342.   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
  343.   array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
  344.   if (array == NULL)
  345.     goto alloc_failure;
  346.  
  347.   for (i = 1, a = array; i < tab->size; ++i)
  348.     {
  349.       e = tab->array[i];
  350.       if (e->refcount)
  351.         {
  352.           *a++ = e;
  353.           /* Adjust the length to not include the zero terminator.  */
  354.           e->len -= 1;
  355.         }
  356.       else
  357.         e->len = 0;
  358.     }
  359.  
  360.   size = a - array;
  361.   if (size != 0)
  362.     {
  363.       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
  364.  
  365.       /* Loop over the sorted array and merge suffixes.  Start from the
  366.          end because we want eg.
  367.  
  368.          s1 -> "d"
  369.          s2 -> "bcd"
  370.          s3 -> "abcd"
  371.  
  372.          to end up as
  373.  
  374.          s3 -> "abcd"
  375.          s2 _____^
  376.          s1 _______^
  377.  
  378.          ie. we don't want s1 pointing into the old s2.  */
  379.       e = *--a;
  380.       e->len += 1;
  381.       while (--a >= array)
  382.         {
  383.           struct elf_strtab_hash_entry *cmp = *a;
  384.  
  385.           cmp->len += 1;
  386.           if (is_suffix (e, cmp))
  387.             {
  388.               cmp->u.suffix = e;
  389.               cmp->len = -cmp->len;
  390.             }
  391.           else
  392.             e = cmp;
  393.         }
  394.     }
  395.  
  396. alloc_failure:
  397.   if (array)
  398.     free (array);
  399.  
  400.   /* Assign positions to the strings we want to keep.  */
  401.   size = 1;
  402.   for (i = 1; i < tab->size; ++i)
  403.     {
  404.       e = tab->array[i];
  405.       if (e->refcount && e->len > 0)
  406.         {
  407.           e->u.index = size;
  408.           size += e->len;
  409.         }
  410.     }
  411.  
  412.   tab->sec_size = size;
  413.  
  414.   /* Adjust the rest.  */
  415.   for (i = 1; i < tab->size; ++i)
  416.     {
  417.       e = tab->array[i];
  418.       if (e->refcount && e->len < 0)
  419.         e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
  420.     }
  421. }
  422.