bfd/elf-strtab.c

   1 /* ELF strtab with GC and suffix merging support.
   2    Copyright 2001 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
  27 /* An entry in the strtab hash table.  */
  28
  29 struct elf_strtab_hash_entry
  30 {
  31   struct bfd_hash_entry root;
  32   /* Length of this entry.  */
  33   unsigned int len;
  34   unsigned int refcount;
  35   union {
  36     /* Index within the merged section.  */
  37     bfd_size_type index;
  38     /* Entry this is a suffix of (if len is 0).  */
  39     struct elf_strtab_hash_entry *suffix;
  40   } u;
  41 };
  42
  43 /* The strtab hash table.  */
  44
  45 struct elf_strtab_hash
  46 {
  47   struct bfd_hash_table table;
  48   /* Next available index.  */
  49   bfd_size_type size;
  50   /* Number of array entries alloced.  */
  51   bfd_size_type alloced;
  52   /* Final strtab size.  */
  53   bfd_size_type sec_size;
  54   /* Array of pointers to strtab entries.  */
  55   struct elf_strtab_hash_entry **array;
  56 };
  57
  58 static struct bfd_hash_entry *elf_strtab_hash_newfunc
  59   PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
  60 static int cmplengthentry PARAMS ((const PTR, const PTR));
  61 static int last4_eq PARAMS ((const PTR, const PTR));
  62 static int last_eq PARAMS ((const PTR, const PTR));
  63
  64 /* Routine to create an entry in a section merge hashtab.  */
  65
  66 static struct bfd_hash_entry *
  67 elf_strtab_hash_newfunc (entry, table, string)
  68      struct bfd_hash_entry *entry;
  69      struct bfd_hash_table *table;
  70      const char *string;
  71 {
  72   struct elf_strtab_hash_entry *ret = (struct elf_strtab_hash_entry *) entry;
  73
  74   /* Allocate the structure if it has not already been allocated by a
  75      subclass.  */
  76   if (ret == (struct elf_strtab_hash_entry *) NULL)
  77     ret = ((struct elf_strtab_hash_entry *)
  78            bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)));
  79   if (ret == (struct elf_strtab_hash_entry *) NULL)
  80     return NULL;
  81
  82   /* Call the allocation method of the superclass.  */
  83   ret = ((struct elf_strtab_hash_entry *)
  84          bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
  85
  86   if (ret)
  87     {
  88       /* Initialize the local fields.  */
  89       ret->u.index = -1;
  90       ret->refcount = 0;
  91       ret->len = 0;
  92     }
  93
  94   return (struct bfd_hash_entry *)ret;
  95 }
  96
  97 /* Create a new hash table.  */
  98
  99 struct elf_strtab_hash *
 100 _bfd_elf_strtab_init ()
 101 {
 102   struct elf_strtab_hash *table;
 103   bfd_size_type amt = sizeof (struct elf_strtab_hash);
 104
 105   table = (struct elf_strtab_hash *) bfd_malloc (amt);
 106   if (table == NULL)
 107     return NULL;
 108
 109   if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc))
 110     {
 111       free (table);
 112       return NULL;
 113     }
 114
 115   table->sec_size = 0;
 116   table->size = 1;
 117   table->alloced = 64;
 118   amt = sizeof (struct elf_strtab_hasn_entry *);
 119   table->array = (struct elf_strtab_hash_entry **)
 120                  bfd_malloc (table->alloced * amt);
 121   if (table->array == NULL)
 122     {
 123       free (table);
 124       return NULL;
 125     }
 126
 127   table->array[0] = NULL;
 128
 129   return table;
 130 }
 131
 132 /* Free a strtab.  */
 133
 134 void
 135 _bfd_elf_strtab_free (tab)
 136      struct elf_strtab_hash *tab;
 137 {
 138   bfd_hash_table_free (&tab->table);
 139   free (tab->array);
 140   free (tab);
 141 }
 142
 143 /* Get the index of an entity in a hash table, adding it if it is not
 144    already present.  */
 145
 146 bfd_size_type
 147 _bfd_elf_strtab_add (tab, str, copy)
 148      struct elf_strtab_hash *tab;
 149      const char *str;
 150      boolean copy;
 151 {
 152   register struct elf_strtab_hash_entry *entry;
 153
 154   /* We handle this specially, since we don't want to do refcounting
 155      on it.  */
 156   if (*str == '\0')
 157     return 0;
 158
 159   BFD_ASSERT (tab->sec_size == 0);
 160   entry = (struct elf_strtab_hash_entry *)
 161           bfd_hash_lookup (&tab->table, str, true, copy);
 162
 163   if (entry == NULL)
 164     return (bfd_size_type) -1;
 165
 166   entry->refcount++;
 167   if (entry->len == 0)
 168     {
 169       entry->len = strlen (str) + 1;
 170       if (tab->size == tab->alloced)
 171         {
 172           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 173           tab->alloced *= 2;
 174           tab->array = (struct elf_strtab_hash_entry **)
 175                        bfd_realloc (tab->array, tab->alloced * amt);
 176           if (tab->array == NULL)
 177             return (bfd_size_type) -1;
 178         }
 179
 180       entry->u.index = tab->size++;
 181       tab->array[entry->u.index] = entry;
 182     }
 183   return entry->u.index;
 184 }
 185
 186 void
 187 _bfd_elf_strtab_addref (tab, idx)
 188      struct elf_strtab_hash *tab;
 189      bfd_size_type idx;
 190 {
 191   if (idx == 0 || idx == (bfd_size_type) -1)
 192     return;
 193   BFD_ASSERT (tab->sec_size == 0);
 194   BFD_ASSERT (idx < tab->size);
 195   ++tab->array[idx]->refcount;
 196 }
 197
 198 void
 199 _bfd_elf_strtab_delref (tab, idx)
 200      struct elf_strtab_hash *tab;
 201      bfd_size_type idx;
 202 {
 203   if (idx == 0 || idx == (bfd_size_type) -1)
 204     return;
 205   BFD_ASSERT (tab->sec_size == 0);
 206   BFD_ASSERT (idx < tab->size);
 207   BFD_ASSERT (tab->array[idx]->refcount > 0);
 208   --tab->array[idx]->refcount;
 209 }
 210
 211 void
 212 _bfd_elf_strtab_clear_all_refs (tab)
 213      struct elf_strtab_hash *tab;
 214 {
 215   bfd_size_type idx;
 216
 217   for (idx = 1; idx < tab->size; ++idx)
 218     tab->array[idx]->refcount = 0;
 219 }
 220
 221 bfd_size_type
 222 _bfd_elf_strtab_size (tab)
 223      struct elf_strtab_hash *tab;
 224 {
 225   return tab->sec_size ? tab->sec_size : tab->size;
 226 }
 227
 228 bfd_size_type
 229 _bfd_elf_strtab_offset (tab, idx)
 230      struct elf_strtab_hash *tab;
 231      bfd_size_type idx;
 232 {
 233   struct elf_strtab_hash_entry *entry;
 234
 235   if (idx == 0)
 236     return 0;
 237   BFD_ASSERT (idx < tab->size);
 238   BFD_ASSERT (tab->sec_size);
 239   entry = tab->array[idx];
 240   BFD_ASSERT (entry->refcount > 0);
 241   entry->refcount--;
 242   return tab->array[idx]->u.index;
 243 }
 244
 245 boolean
 246 _bfd_elf_strtab_emit (abfd, tab)
 247      register bfd *abfd;
 248      struct elf_strtab_hash *tab;
 249 {
 250   bfd_size_type off = 1, i;
 251
 252   if (bfd_bwrite ("", 1, abfd) != 1)
 253     return false;
 254
 255   for (i = 1; i < tab->size; ++i)
 256     {
 257       register const char *str;
 258       register size_t len;
 259
 260       str = tab->array[i]->root.string;
 261       len = tab->array[i]->len;
 262       BFD_ASSERT (tab->array[i]->refcount == 0);
 263       if (len == 0)
 264         continue;
 265
 266       if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
 267         return false;
 268
 269       off += len;
 270     }
 271
 272   BFD_ASSERT (off == tab->sec_size);
 273   return true;
 274 }
 275
 276 /* Compare two elf_strtab_hash_entry structures.  This is called via qsort.  */
 277
 278 static int
 279 cmplengthentry (a, b)
 280      const PTR a;
 281      const PTR b;
 282 {
 283   struct elf_strtab_hash_entry * A = *(struct elf_strtab_hash_entry **) a;
 284   struct elf_strtab_hash_entry * B = *(struct elf_strtab_hash_entry **) b;
 285
 286   if (A->len < B->len)
 287     return 1;
 288   else if (A->len > B->len)
 289     return -1;
 290
 291   return memcmp (A->root.string, B->root.string, A->len);
 292 }
 293
 294 static int
 295 last4_eq (a, b)
 296      const PTR a;
 297      const PTR b;
 298 {
 299   struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
 300   struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
 301
 302   if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4)
 303       != 0)
 304     /* This was a hashtable collision.  */
 305     return 0;
 306
 307   if (A->len <= B->len)
 308     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 309        not to be equal by the hash table.  */
 310     return 0;
 311
 312   return memcmp (A->root.string + (A->len - B->len),
 313                  B->root.string, B->len - 5) == 0;
 314 }
 315
 316 static int
 317 last_eq (a, b)
 318      const PTR a;
 319      const PTR b;
 320 {
 321   struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a;
 322   struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b;
 323
 324   if (B->len >= 5)
 325     /* Longer strings are just pushed into the hash table,
 326        they'll be used when looking up for very short strings.  */
 327     return 0;
 328
 329   if (memcmp (A->root.string + A->len - 2, B->root.string + B->len - 2, 1)
 330       != 0)
 331     /* This was a hashtable collision.  */
 332     return 0;
 333
 334   if (A->len <= B->len)
 335     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 336        not to be equal by the hash table.  */
 337     return 0;
 338
 339   return memcmp (A->root.string + (A->len - B->len),
 340                  B->root.string, B->len - 2) == 0;
 341 }
 342
 343 /* This function assigns final string table offsets for used strings,
 344    merging strings matching suffixes of longer strings if possible.  */
 345
 346 void
 347 _bfd_elf_strtab_finalize (tab)
 348      struct elf_strtab_hash *tab;
 349 {
 350   struct elf_strtab_hash_entry **array, **a, **end, *e;
 351   htab_t lasttab = NULL, last4tab = NULL;
 352   bfd_size_type size, amt, i;
 353
 354   /* Now sort the strings by length, longest first.  */
 355   array = NULL;
 356   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
 357   array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
 358   if (array == NULL)
 359     goto alloc_failure;
 360
 361   for (i = 1, a = array; i < tab->size; ++i)
 362     if (tab->array[i]->refcount)
 363       *a++ = tab->array[i];
 364     else
 365       tab->array[i]->len = 0;
 366
 367   size = a - array;
 368
 369   qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry);
 370
 371   last4tab = htab_create (size * 4, NULL, last4_eq, NULL);
 372   lasttab = htab_create (size * 4, NULL, last_eq, NULL);
 373   if (lasttab == NULL || last4tab == NULL)
 374     goto alloc_failure;
 375
 376   /* Now insert the strings into hash tables (strings with last 4 characters
 377      and strings with last character equal), look for longer strings which
 378      we're suffix of.  */
 379   for (a = array, end = array + size; a < end; a++)
 380     {
 381       register hashval_t hash;
 382       unsigned int c;
 383       unsigned int i;
 384       const unsigned char *s;
 385       PTR *p;
 386
 387       e = *a;
 388       if (e->len > 4)
 389         {
 390           s = e->root.string + e->len - 1;
 391           hash = 0;
 392           for (i = 0; i < 4; i++)
 393             {
 394               c = *--s;
 395               hash += c + (c << 17);
 396               hash ^= hash >> 2;
 397             }
 398           p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
 399           if (p == NULL)
 400             goto alloc_failure;
 401           if (*p)
 402             {
 403               struct elf_strtab_hash_entry *ent;
 404
 405               ent = (struct elf_strtab_hash_entry *) *p;
 406               e->u.suffix = ent;
 407               e->len = 0;
 408               continue;
 409             }
 410           else
 411             *p = (PTR) e;
 412         }
 413       c = (unsigned char) e->root.string[e->len - 1];
 414       p = htab_find_slot_with_hash (lasttab, e, c, INSERT);
 415       if (p == NULL)
 416         goto alloc_failure;
 417       if (*p)
 418         {
 419           struct elf_strtab_hash_entry *ent;
 420
 421           ent = (struct elf_strtab_hash_entry *) *p;
 422           e->u.suffix = ent;
 423           e->len = 0;
 424         }
 425       else
 426         *p = (PTR) e;
 427     }
 428
 429 alloc_failure:
 430   if (array)
 431     free (array);
 432   if (lasttab)
 433     htab_delete (lasttab);
 434   if (last4tab)
 435     htab_delete (last4tab);
 436
 437   /* Now assign positions to the strings we want to keep.  */
 438   size = 1;
 439   for (i = 1; i < tab->size; ++i)
 440     {
 441       e = tab->array[i];
 442       if (e->refcount && e->len)
 443         {
 444           e->u.index = size;
 445           size += e->len;
 446         }
 447     }
 448
 449   tab->sec_size = size;
 450
 451   /* And now adjust the rest.  */
 452   for (i = 1; i < tab->size; ++i)
 453     {
 454       e = tab->array[i];
 455       if (e->refcount && ! e->len)
 456         e->u.index = e->u.suffix->u.index
 457                      + (e->u.suffix->len - strlen (e->root.string) - 1);
 458     }
 459 }