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