bfd/elf-strtab.c

   1 /* ELF strtab with GC and suffix merging support.
   2    Copyright 2001, 2002 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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.  */
  34   unsigned 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 is 0).  */
  40     struct elf_strtab_hash_entry *suffix;
  41     struct elf_strtab_hash_entry *next;
  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     {
 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       if (tab->size == tab->alloced)
 162         {
 163           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 164           tab->alloced *= 2;
 165           tab->array = bfd_realloc (tab->array, tab->alloced * amt);
 166           if (tab->array == NULL)
 167             return (bfd_size_type) -1;
 168         }
 169
 170       entry->u.index = tab->size++;
 171       tab->array[entry->u.index] = entry;
 172     }
 173   return entry->u.index;
 174 }
 175
 176 void
 177 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
 178 {
 179   if (idx == 0 || idx == (bfd_size_type) -1)
 180     return;
 181   BFD_ASSERT (tab->sec_size == 0);
 182   BFD_ASSERT (idx < tab->size);
 183   ++tab->array[idx]->refcount;
 184 }
 185
 186 void
 187 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
 188 {
 189   if (idx == 0 || idx == (bfd_size_type) -1)
 190     return;
 191   BFD_ASSERT (tab->sec_size == 0);
 192   BFD_ASSERT (idx < tab->size);
 193   BFD_ASSERT (tab->array[idx]->refcount > 0);
 194   --tab->array[idx]->refcount;
 195 }
 196
 197 void
 198 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
 199 {
 200   bfd_size_type idx;
 201
 202   for (idx = 1; idx < tab->size; ++idx)
 203     tab->array[idx]->refcount = 0;
 204 }
 205
 206 bfd_size_type
 207 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
 208 {
 209   return tab->sec_size ? tab->sec_size : tab->size;
 210 }
 211
 212 bfd_size_type
 213 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
 214 {
 215   struct elf_strtab_hash_entry *entry;
 216
 217   if (idx == 0)
 218     return 0;
 219   BFD_ASSERT (idx < tab->size);
 220   BFD_ASSERT (tab->sec_size);
 221   entry = tab->array[idx];
 222   BFD_ASSERT (entry->refcount > 0);
 223   entry->refcount--;
 224   return tab->array[idx]->u.index;
 225 }
 226
 227 bfd_boolean
 228 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 229 {
 230   bfd_size_type off = 1, i;
 231
 232   if (bfd_bwrite ("", 1, abfd) != 1)
 233     return FALSE;
 234
 235   for (i = 1; i < tab->size; ++i)
 236     {
 237       register const char *str;
 238       register size_t len;
 239
 240       str = tab->array[i]->root.string;
 241       len = tab->array[i]->len;
 242       BFD_ASSERT (tab->array[i]->refcount == 0);
 243       if (len == 0)
 244         continue;
 245
 246       if (bfd_bwrite (str, len, abfd) != len)
 247         return FALSE;
 248
 249       off += len;
 250     }
 251
 252   BFD_ASSERT (off == tab->sec_size);
 253   return TRUE;
 254 }
 255
 256 /* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
 257
 258 static int
 259 cmplengthentry (const void *a, const void *b)
 260 {
 261   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
 262   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
 263
 264   if (A->len < B->len)
 265     return 1;
 266   else if (A->len > B->len)
 267     return -1;
 268
 269   return memcmp (A->root.string, B->root.string, A->len);
 270 }
 271
 272 static int
 273 last4_eq (const void *a, const void *b)
 274 {
 275   const struct elf_strtab_hash_entry *A = a;
 276   const struct elf_strtab_hash_entry *B = b;
 277
 278   if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
 279       != 0)
 280     /* This was a hashtable collision.  */
 281     return 0;
 282
 283   if (A->len <= B->len)
 284     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 285        not to be equal by the hash table.  */
 286     return 0;
 287
 288   return memcmp (A->root.string + (A->len - B->len),
 289                  B->root.string, B->len - 5) == 0;
 290 }
 291
 292 /* This function assigns final string table offsets for used strings,
 293    merging strings matching suffixes of longer strings if possible.  */
 294
 295 void
 296 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
 297 {
 298   struct elf_strtab_hash_entry **array, **a, **end, *e;
 299   htab_t last4tab = NULL;
 300   bfd_size_type size, amt;
 301   struct elf_strtab_hash_entry *last[256], **last_ptr[256];
 302
 303   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
 304      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
 305      Besides, indexing with a long long wouldn't give anything but extra
 306      cycles.  */
 307   size_t i;
 308
 309   /* Now sort the strings by length, longest first.  */
 310   array = NULL;
 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   memset (last, 0, sizeof (last));
 317   for (i = 0; i < 256; ++i)
 318     last_ptr[i] = &last[i];
 319   for (i = 1, a = array; i < tab->size; ++i)
 320     if (tab->array[i]->refcount)
 321       *a++ = tab->array[i];
 322     else
 323       tab->array[i]->len = 0;
 324
 325   size = a - array;
 326
 327   qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
 328
 329   last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free);
 330   if (last4tab == NULL)
 331     goto alloc_failure;
 332
 333   /* Now insert the strings into hash tables (strings with last 4 characters
 334      and strings with last character equal), look for longer strings which
 335      we're suffix of.  */
 336   for (a = array, end = array + size; a < end; a++)
 337     {
 338       register hashval_t hash;
 339       unsigned int c;
 340       unsigned int j;
 341       const unsigned char *s;
 342       void **p;
 343
 344       e = *a;
 345       if (e->len > 4)
 346         {
 347           s = e->root.string + e->len - 1;
 348           hash = 0;
 349           for (j = 0; j < 4; j++)
 350             {
 351               c = *--s;
 352               hash += c + (c << 17);
 353               hash ^= hash >> 2;
 354             }
 355           p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
 356           if (p == NULL)
 357             goto alloc_failure;
 358           if (*p)
 359             {
 360               struct elf_strtab_hash_entry *ent;
 361
 362               ent = *p;
 363               e->u.suffix = ent;
 364               e->len = 0;
 365               continue;
 366             }
 367           else
 368             *p = e;
 369         }
 370       else
 371         {
 372           struct elf_strtab_hash_entry *tem;
 373
 374           c = e->root.string[e->len - 2] & 0xff;
 375
 376           for (tem = last[c]; tem; tem = tem->u.next)
 377             if (tem->len > e->len
 378                 && memcmp (tem->root.string + (tem->len - e->len),
 379                            e->root.string, e->len - 1) == 0)
 380               break;
 381           if (tem)
 382             {
 383               e->u.suffix = tem;
 384               e->len = 0;
 385               continue;
 386             }
 387         }
 388
 389       c = e->root.string[e->len - 2] & 0xff;
 390       /* Put longest strings first.  */
 391       *last_ptr[c] = e;
 392       last_ptr[c] = &e->u.next;
 393       e->u.next = NULL;
 394     }
 395
 396 alloc_failure:
 397   if (array)
 398     free (array);
 399   if (last4tab)
 400     htab_delete (last4tab);
 401
 402   /* Now assign positions to the strings we want to keep.  */
 403   size = 1;
 404   for (i = 1; i < tab->size; ++i)
 405     {
 406       e = tab->array[i];
 407       if (e->refcount && e->len)
 408         {
 409           e->u.index = size;
 410           size += e->len;
 411         }
 412     }
 413
 414   tab->sec_size = size;
 415
 416   /* And now adjust the rest.  */
 417   for (i = 1; i < tab->size; ++i)
 418     {
 419       e = tab->array[i];
 420       if (e->refcount && ! e->len)
 421         e->u.index = e->u.suffix->u.index
 422                      + (e->u.suffix->len - strlen (e->root.string) - 1);
 423     }
 424 }