bfd/elf-strtab.c

   1 /* ELF strtab with GC and suffix merging support.
   2    Copyright (C) 2001-2023 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 3 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., 51 Franklin Street - Fifth Floor, Boston,
  20    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   size_t size;
  52   /* Number of array entries alloced.  */
  53   size_t 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 = (struct bfd_hash_entry *)
  71         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   size_t amt = sizeof (struct elf_strtab_hash);
  99
 100   table = (struct elf_strtab_hash *) 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 = ((struct elf_strtab_hash_entry **)
 116                   bfd_malloc (table->alloced * amt));
 117   if (table->array == NULL)
 118     {
 119       bfd_hash_table_free (&table->table);
 120       free (table);
 121       return NULL;
 122     }
 123
 124   table->array[0] = NULL;
 125
 126   return table;
 127 }
 128
 129 /* Free a strtab.  */
 130
 131 void
 132 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
 133 {
 134   bfd_hash_table_free (&tab->table);
 135   free (tab->array);
 136   free (tab);
 137 }
 138
 139 /* Get the index of an entity in a hash table, adding it if it is not
 140    already present.  */
 141
 142 size_t
 143 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
 144                      const char *str,
 145                      bool copy)
 146 {
 147   register struct elf_strtab_hash_entry *entry;
 148
 149   /* We handle this specially, since we don't want to do refcounting
 150      on it.  */
 151   if (*str == '\0')
 152     return 0;
 153
 154   BFD_ASSERT (tab->sec_size == 0);
 155   entry = (struct elf_strtab_hash_entry *)
 156           bfd_hash_lookup (&tab->table, str, true, copy);
 157
 158   if (entry == NULL)
 159     return (size_t) -1;
 160
 161   entry->refcount++;
 162   if (entry->len == 0)
 163     {
 164       entry->len = strlen (str) + 1;
 165       /* 2G strings lose.  */
 166       BFD_ASSERT (entry->len > 0);
 167       if (tab->size == tab->alloced)
 168         {
 169           bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
 170           tab->alloced *= 2;
 171           tab->array = (struct elf_strtab_hash_entry **)
 172               bfd_realloc_or_free (tab->array, tab->alloced * amt);
 173           if (tab->array == NULL)
 174             return (size_t) -1;
 175         }
 176
 177       entry->u.index = tab->size++;
 178       tab->array[entry->u.index] = entry;
 179     }
 180   return entry->u.index;
 181 }
 182
 183 void
 184 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, size_t idx)
 185 {
 186   if (idx == 0 || idx == (size_t) -1)
 187     return;
 188   BFD_ASSERT (tab->sec_size == 0);
 189   BFD_ASSERT (idx < tab->size);
 190   ++tab->array[idx]->refcount;
 191 }
 192
 193 void
 194 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, size_t idx)
 195 {
 196   if (idx == 0 || idx == (size_t) -1)
 197     return;
 198   BFD_ASSERT (tab->sec_size == 0);
 199   BFD_ASSERT (idx < tab->size);
 200   BFD_ASSERT (tab->array[idx]->refcount > 0);
 201   --tab->array[idx]->refcount;
 202 }
 203
 204 unsigned int
 205 _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, size_t idx)
 206 {
 207   return tab->array[idx]->refcount;
 208 }
 209
 210 void
 211 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
 212 {
 213   size_t idx;
 214
 215   for (idx = 1; idx < tab->size; idx++)
 216     tab->array[idx]->refcount = 0;
 217 }
 218
 219 /* Save strtab refcounts prior to adding --as-needed library.  */
 220
 221 struct strtab_save
 222 {
 223   size_t size;
 224   unsigned int refcount[1];
 225 };
 226
 227 void *
 228 _bfd_elf_strtab_save (struct elf_strtab_hash *tab)
 229 {
 230   struct strtab_save *save;
 231   size_t idx, size;
 232
 233   size = sizeof (*save) + (tab->size - 1) * sizeof (save->refcount[0]);
 234   save = bfd_malloc (size);
 235   if (save == NULL)
 236     return save;
 237
 238   save->size = tab->size;
 239   for (idx = 1; idx < tab->size; idx++)
 240     save->refcount[idx] = tab->array[idx]->refcount;
 241   return save;
 242 }
 243
 244 /* Restore strtab refcounts on finding --as-needed library not needed.  */
 245
 246 void
 247 _bfd_elf_strtab_restore (struct elf_strtab_hash *tab, void *buf)
 248 {
 249   size_t idx, curr_size = tab->size, save_size;
 250   struct strtab_save *save = (struct strtab_save *) buf;
 251
 252   BFD_ASSERT (tab->sec_size == 0);
 253   save_size = 1;
 254   if (save != NULL)
 255     save_size = save->size;
 256   BFD_ASSERT (save_size <= curr_size);
 257   tab->size = save_size;
 258   for (idx = 1; idx < save_size; ++idx)
 259     tab->array[idx]->refcount = save->refcount[idx];
 260
 261   for (; idx < curr_size; ++idx)
 262     {
 263       /* We don't remove entries from the hash table, just set their
 264          REFCOUNT to zero.  Setting LEN zero will result in the size
 265          growing if the entry is added again.  See _bfd_elf_strtab_add.  */
 266       tab->array[idx]->refcount = 0;
 267       tab->array[idx]->len = 0;
 268     }
 269 }
 270
 271 bfd_size_type
 272 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
 273 {
 274   return tab->sec_size ? tab->sec_size : tab->size;
 275 }
 276
 277 bfd_size_type
 278 _bfd_elf_strtab_len (struct elf_strtab_hash *tab)
 279 {
 280   return tab->size;
 281 }
 282
 283 bfd_size_type
 284 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, size_t idx)
 285 {
 286   struct elf_strtab_hash_entry *entry;
 287
 288   if (idx == 0)
 289     return 0;
 290   BFD_ASSERT (idx < tab->size);
 291   BFD_ASSERT (tab->sec_size);
 292   entry = tab->array[idx];
 293   BFD_ASSERT (entry->refcount > 0);
 294   entry->refcount--;
 295   return tab->array[idx]->u.index;
 296 }
 297
 298 const char *
 299 _bfd_elf_strtab_str (struct elf_strtab_hash *tab, size_t idx,
 300                      bfd_size_type *offset)
 301 {
 302   if (idx == 0)
 303     return NULL;
 304   BFD_ASSERT (idx < tab->size);
 305   BFD_ASSERT (tab->sec_size);
 306   if (tab->array[idx]->refcount == 0)
 307     return NULL;
 308   if (offset)
 309     *offset = tab->array[idx]->u.index;
 310   return tab->array[idx]->root.string;
 311 }
 312
 313 bool
 314 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
 315 {
 316   bfd_size_type off = 1;
 317   size_t i;
 318
 319   if (bfd_write ("", 1, abfd) != 1)
 320     return false;
 321
 322   for (i = 1; i < tab->size; ++i)
 323     {
 324       register const char *str;
 325       register unsigned int len;
 326
 327       BFD_ASSERT (tab->array[i]->refcount == 0);
 328       len = tab->array[i]->len;
 329       if ((int) len < 0)
 330         continue;
 331
 332       str = tab->array[i]->root.string;
 333       if (bfd_write (str, len, abfd) != len)
 334         return false;
 335
 336       off += len;
 337     }
 338
 339   BFD_ASSERT (off == tab->sec_size);
 340   return true;
 341 }
 342
 343 /* Compare two elf_strtab_hash_entry structures.  Called via qsort.
 344    Won't ever return zero as all entries differ, so there is no issue
 345    with qsort stability here.  */
 346
 347 static int
 348 strrevcmp (const void *a, const void *b)
 349 {
 350   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
 351   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
 352   unsigned int lenA = A->len;
 353   unsigned int lenB = B->len;
 354   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
 355   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
 356   int l = lenA < lenB ? lenA : lenB;
 357
 358   while (l)
 359     {
 360       if (*s != *t)
 361         return (int) *s - (int) *t;
 362       s--;
 363       t--;
 364       l--;
 365     }
 366   return lenA - lenB;
 367 }
 368
 369 static inline int
 370 is_suffix (const struct elf_strtab_hash_entry *A,
 371            const struct elf_strtab_hash_entry *B)
 372 {
 373   if (A->len <= B->len)
 374     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
 375        not to be equal by the hash table.  */
 376     return 0;
 377
 378   return memcmp (A->root.string + (A->len - B->len),
 379                  B->root.string, B->len - 1) == 0;
 380 }
 381
 382 /* This function assigns final string table offsets for used strings,
 383    merging strings matching suffixes of longer strings if possible.  */
 384
 385 void
 386 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
 387 {
 388   struct elf_strtab_hash_entry **array, **a, *e;
 389   bfd_size_type amt, sec_size;
 390   size_t size, i;
 391
 392   /* Sort the strings by suffix and length.  */
 393   amt = tab->size;
 394   amt *= sizeof (struct elf_strtab_hash_entry *);
 395   array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
 396   if (array == NULL)
 397     goto alloc_failure;
 398
 399   for (i = 1, a = array; i < tab->size; ++i)
 400     {
 401       e = tab->array[i];
 402       if (e->refcount)
 403         {
 404           *a++ = e;
 405           /* Adjust the length to not include the zero terminator.  */
 406           e->len -= 1;
 407         }
 408       else
 409         e->len = 0;
 410     }
 411
 412   size = a - array;
 413   if (size != 0)
 414     {
 415       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
 416
 417       /* Loop over the sorted array and merge suffixes.  Start from the
 418          end because we want eg.
 419
 420          s1 -> "d"
 421          s2 -> "bcd"
 422          s3 -> "abcd"
 423
 424          to end up as
 425
 426          s3 -> "abcd"
 427          s2 _____^
 428          s1 _______^
 429
 430          ie. we don't want s1 pointing into the old s2.  */
 431       e = *--a;
 432       e->len += 1;
 433       while (--a >= array)
 434         {
 435           struct elf_strtab_hash_entry *cmp = *a;
 436
 437           cmp->len += 1;
 438           if (is_suffix (e, cmp))
 439             {
 440               cmp->u.suffix = e;
 441               cmp->len = -cmp->len;
 442             }
 443           else
 444             e = cmp;
 445         }
 446     }
 447
 448  alloc_failure:
 449   free (array);
 450
 451   /* Assign positions to the strings we want to keep.  */
 452   sec_size = 1;
 453   for (i = 1; i < tab->size; ++i)
 454     {
 455       e = tab->array[i];
 456       if (e->refcount && e->len > 0)
 457         {
 458           e->u.index = sec_size;
 459           sec_size += e->len;
 460         }
 461     }
 462
 463   tab->sec_size = sec_size;
 464
 465   /* Adjust the rest.  */
 466   for (i = 1; i < tab->size; ++i)
 467     {
 468       e = tab->array[i];
 469       if (e->refcount && e->len < 0)
 470         e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
 471     }
 472 }