bfd/elf-strtab.c

   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 }