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