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 = 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 = 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 = bfd_malloc (table->alloced * amt);
 116   if (table->array == NULL)
 117     {
 118       free (table);
 119       return NULL;
 120     }
 121
 122   table->array[0] = NULL;
 123
 124   return table;
 125 }
 126
 127 /* Free a strtab.  */
 128
 129 void
 130 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
 131 {
 132   bfd_hash_table_free (&tab->table);
 133   free (tab->array);
 134   free (tab);
 135 }
 136
 137 /* Get the index of an entity in a hash table, adding it if it is not
 138    already present.  */
 139
 140 bfd_size_type
 141 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
 142                      const char *str,
 143                      bfd_boolean copy)
 144 {
 145   register struct elf_strtab_hash_entry *entry;
 146
 147   /* We handle this specially, since we don't want to do refcounting
 148      on it.  */
 149   if (*str == '\0')
 150     return 0;
 151
 152   BFD_ASSERT (tab->sec_size == 0);
 153   entry = (struct elf_strtab_hash_entry *)
 154           bfd_hash_lookup (&tab->table, str, TRUE, copy);
 155
 156   if (entry == NULL)
 157     return (bfd_size_type) -1;
 158
 159   entry->refcount++;
 160   if (entry->len == 0)
 161     {
 162       entry->len = strlen (str) + 1;
 163       /* 2G strings lose.  */
 164       BFD_ASSERT (entry->len > 0);
 165       if (tab->size == tab->alloced)
 166         {
 167           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 168           tab->alloced *= 2;
 169           tab->array = bfd_realloc_or_free (tab->array, tab->alloced * amt);
 170           if (tab->array == NULL)
 171             return (bfd_size_type) -1;
 172         }
 173
 174       entry->u.index = tab->size++;
 175       tab->array[entry->u.index] = entry;
 176     }
 177   return entry->u.index;
 178 }
 179
 180 void
 181 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
 182 {
 183   if (idx == 0 || idx == (bfd_size_type) -1)
 184     return;
 185   BFD_ASSERT (tab->sec_size == 0);
 186   BFD_ASSERT (idx < tab->size);
 187   ++tab->array[idx]->refcount;
 188 }
 189
 190 void
 191 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
 192 {
 193   if (idx == 0 || idx == (bfd_size_type) -1)
 194     return;
 195   BFD_ASSERT (tab->sec_size == 0);
 196   BFD_ASSERT (idx < tab->size);
 197   BFD_ASSERT (tab->array[idx]->refcount > 0);
 198   --tab->array[idx]->refcount;
 199 }
 200
 201 void
 202 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
 203 {
 204   bfd_size_type idx;
 205
 206   for (idx = 1; idx < tab->size; ++idx)
 207     tab->array[idx]->refcount = 0;
 208 }
 209
 210 bfd_size_type
 211 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
 212 {
 213   return tab->sec_size ? tab->sec_size : tab->size;
 214 }
 215
 216 bfd_size_type
 217 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
 218 {
 219   struct elf_strtab_hash_entry *entry;
 220
 221   if (idx == 0)
 222     return 0;
 223   BFD_ASSERT (idx < tab->size);
 224   BFD_ASSERT (tab->sec_size);
 225   entry = tab->array[idx];
 226   BFD_ASSERT (entry->refcount > 0);
 227   entry->refcount--;
 228   return tab->array[idx]->u.index;
 229 }
 230
 231 bfd_boolean
 232 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 233 {
 234   bfd_size_type off = 1, i;
 235
 236   if (bfd_bwrite ("", 1, abfd) != 1)
 237     return FALSE;
 238
 239   for (i = 1; i < tab->size; ++i)
 240     {
 241       register const char *str;
 242       register unsigned int len;
 243
 244       BFD_ASSERT (tab->array[i]->refcount == 0);
 245       len = tab->array[i]->len;
 246       if ((int) len < 0)
 247         continue;
 248
 249       str = tab->array[i]->root.string;
 250       if (bfd_bwrite (str, len, abfd) != len)
 251         return FALSE;
 252
 253       off += len;
 254     }
 255
 256   BFD_ASSERT (off == tab->sec_size);
 257   return TRUE;
 258 }
 259
 260 /* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
 261
 262 static int
 263 strrevcmp (const void *a, const void *b)
 264 {
 265   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
 266   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
 267   unsigned int lenA = A->len;
 268   unsigned int lenB = B->len;
 269   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
 270   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
 271   int l = lenA < lenB ? lenA : lenB;
 272
 273   while (l)
 274     {
 275       if (*s != *t)
 276         return (int) *s - (int) *t;
 277       s--;
 278       t--;
 279       l--;
 280     }
 281   return lenA - lenB;
 282 }
 283
 284 static inline int
 285 is_suffix (const struct elf_strtab_hash_entry *A,
 286            const struct elf_strtab_hash_entry *B)
 287 {
 288   if (A->len <= B->len)
 289     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 290        not to be equal by the hash table.  */
 291     return 0;
 292
 293   return memcmp (A->root.string + (A->len - B->len),
 294                  B->root.string, B->len - 1) == 0;
 295 }
 296
 297 /* This function assigns final string table offsets for used strings,
 298    merging strings matching suffixes of longer strings if possible.  */
 299
 300 void
 301 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
 302 {
 303   struct elf_strtab_hash_entry **array, **a, *e;
 304   bfd_size_type size, amt;
 305
 306   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
 307      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
 308      Besides, indexing with a long long wouldn't give anything but extra
 309      cycles.  */
 310   size_t i;
 311
 312   /* Sort the strings by suffix and length.  */
 313   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
 314   array = bfd_malloc (amt);
 315   if (array == NULL)
 316     goto alloc_failure;
 317
 318   for (i = 1, a = array; i < tab->size; ++i)
 319     {
 320       e = tab->array[i];
 321       if (e->refcount)
 322         {
 323           *a++ = e;
 324           /* Adjust the length to not include the zero terminator.  */
 325           e->len -= 1;
 326         }
 327       else
 328         e->len = 0;
 329     }
 330
 331   size = a - array;
 332   if (size != 0)
 333     {
 334       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
 335
 336       /* Loop over the sorted array and merge suffixes.  Start from the
 337          end because we want eg.
 338
 339          s1 -> "d"
 340          s2 -> "bcd"
 341          s3 -> "abcd"
 342
 343          to end up as
 344
 345          s3 -> "abcd"
 346          s2 _____^
 347          s1 _______^
 348
 349          ie. we don't want s1 pointing into the old s2.  */
 350       e = *--a;
 351       e->len += 1;
 352       while (--a >= array)
 353         {
 354           struct elf_strtab_hash_entry *cmp = *a;
 355
 356           cmp->len += 1;
 357           if (is_suffix (e, cmp))
 358             {
 359               cmp->u.suffix = e;
 360               cmp->len = -cmp->len;
 361             }
 362           else
 363             e = cmp;
 364         }
 365     }
 366
 367 alloc_failure:
 368   if (array)
 369     free (array);
 370
 371   /* Assign positions to the strings we want to keep.  */
 372   size = 1;
 373   for (i = 1; i < tab->size; ++i)
 374     {
 375       e = tab->array[i];
 376       if (e->refcount && e->len > 0)
 377         {
 378           e->u.index = size;
 379           size += e->len;
 380         }
 381     }
 382
 383   tab->sec_size = size;
 384
 385   /* Adjust the rest.  */
 386   for (i = 1; i < tab->size; ++i)
 387     {
 388       e = tab->array[i];
 389       if (e->refcount && e->len < 0)
 390         e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
 391     }
 392 }