contrib/binutils/bfd/elf-strtab.c

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