bfd/elf-strtab.c

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