contrib/binutils-2.17/bfd/elf-strtab.c

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