1 /* ELF strtab with GC and suffix merging support. 2 Copyright (C) 2001-2020 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 bfd_size_type 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 130 void 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 141 size_t 142 _bfd_elf_strtab_add (struct elf_strtab_hash *tab, 143 const char *str, 144 bfd_boolean 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 182 void 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 192 void 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 203 unsigned int 204 _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, size_t idx) 205 { 206 return tab->array[idx]->refcount; 207 } 208 209 void 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 220 struct strtab_save 221 { 222 size_t size; 223 unsigned int refcount[1]; 224 }; 225 226 void * 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 245 void 246 _bfd_elf_strtab_restore (struct elf_strtab_hash *tab, void *buf) 247 { 248 size_t idx, curr_size = tab->size; 249 struct strtab_save *save = (struct strtab_save *) buf; 250 251 BFD_ASSERT (tab->sec_size == 0); 252 BFD_ASSERT (save->size <= curr_size); 253 tab->size = save->size; 254 for (idx = 1; idx < save->size; ++idx) 255 tab->array[idx]->refcount = save->refcount[idx]; 256 257 for (; idx < curr_size; ++idx) 258 { 259 /* We don't remove entries from the hash table, just set their 260 REFCOUNT to zero. Setting LEN zero will result in the size 261 growing if the entry is added again. See _bfd_elf_strtab_add. */ 262 tab->array[idx]->refcount = 0; 263 tab->array[idx]->len = 0; 264 } 265 } 266 267 bfd_size_type 268 _bfd_elf_strtab_size (struct elf_strtab_hash *tab) 269 { 270 return tab->sec_size ? tab->sec_size : tab->size; 271 } 272 273 bfd_size_type 274 _bfd_elf_strtab_len (struct elf_strtab_hash *tab) 275 { 276 return tab->size; 277 } 278 279 bfd_size_type 280 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, size_t idx) 281 { 282 struct elf_strtab_hash_entry *entry; 283 284 if (idx == 0) 285 return 0; 286 BFD_ASSERT (idx < tab->size); 287 BFD_ASSERT (tab->sec_size); 288 entry = tab->array[idx]; 289 BFD_ASSERT (entry->refcount > 0); 290 entry->refcount--; 291 return tab->array[idx]->u.index; 292 } 293 294 const char * 295 _bfd_elf_strtab_str (struct elf_strtab_hash *tab, size_t idx, 296 bfd_size_type *offset) 297 { 298 if (idx == 0) 299 return 0; 300 BFD_ASSERT (idx < tab->size); 301 BFD_ASSERT (tab->sec_size); 302 if (offset) 303 *offset = tab->array[idx]->u.index; 304 return tab->array[idx]->root.string; 305 } 306 307 bfd_boolean 308 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) 309 { 310 bfd_size_type off = 1; 311 size_t i; 312 313 if (bfd_bwrite ("", 1, abfd) != 1) 314 return FALSE; 315 316 for (i = 1; i < tab->size; ++i) 317 { 318 register const char *str; 319 register unsigned int len; 320 321 BFD_ASSERT (tab->array[i]->refcount == 0); 322 len = tab->array[i]->len; 323 if ((int) len < 0) 324 continue; 325 326 str = tab->array[i]->root.string; 327 if (bfd_bwrite (str, len, abfd) != len) 328 return FALSE; 329 330 off += len; 331 } 332 333 BFD_ASSERT (off == tab->sec_size); 334 return TRUE; 335 } 336 337 /* Compare two elf_strtab_hash_entry structures. Called via qsort. 338 Won't ever return zero as all entries differ, so there is no issue 339 with qsort stability here. */ 340 341 static int 342 strrevcmp (const void *a, const void *b) 343 { 344 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; 345 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; 346 unsigned int lenA = A->len; 347 unsigned int lenB = B->len; 348 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 349 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 350 int l = lenA < lenB ? lenA : lenB; 351 352 while (l) 353 { 354 if (*s != *t) 355 return (int) *s - (int) *t; 356 s--; 357 t--; 358 l--; 359 } 360 return lenA - lenB; 361 } 362 363 static inline int 364 is_suffix (const struct elf_strtab_hash_entry *A, 365 const struct elf_strtab_hash_entry *B) 366 { 367 if (A->len <= B->len) 368 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 369 not to be equal by the hash table. */ 370 return 0; 371 372 return memcmp (A->root.string + (A->len - B->len), 373 B->root.string, B->len - 1) == 0; 374 } 375 376 /* This function assigns final string table offsets for used strings, 377 merging strings matching suffixes of longer strings if possible. */ 378 379 void 380 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) 381 { 382 struct elf_strtab_hash_entry **array, **a, *e; 383 bfd_size_type amt, sec_size; 384 size_t size, i; 385 386 /* Sort the strings by suffix and length. */ 387 amt = tab->size; 388 amt *= sizeof (struct elf_strtab_hash_entry *); 389 array = (struct elf_strtab_hash_entry **) bfd_malloc (amt); 390 if (array == NULL) 391 goto alloc_failure; 392 393 for (i = 1, a = array; i < tab->size; ++i) 394 { 395 e = tab->array[i]; 396 if (e->refcount) 397 { 398 *a++ = e; 399 /* Adjust the length to not include the zero terminator. */ 400 e->len -= 1; 401 } 402 else 403 e->len = 0; 404 } 405 406 size = a - array; 407 if (size != 0) 408 { 409 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); 410 411 /* Loop over the sorted array and merge suffixes. Start from the 412 end because we want eg. 413 414 s1 -> "d" 415 s2 -> "bcd" 416 s3 -> "abcd" 417 418 to end up as 419 420 s3 -> "abcd" 421 s2 _____^ 422 s1 _______^ 423 424 ie. we don't want s1 pointing into the old s2. */ 425 e = *--a; 426 e->len += 1; 427 while (--a >= array) 428 { 429 struct elf_strtab_hash_entry *cmp = *a; 430 431 cmp->len += 1; 432 if (is_suffix (e, cmp)) 433 { 434 cmp->u.suffix = e; 435 cmp->len = -cmp->len; 436 } 437 else 438 e = cmp; 439 } 440 } 441 442 alloc_failure: 443 if (array) 444 free (array); 445 446 /* Assign positions to the strings we want to keep. */ 447 sec_size = 1; 448 for (i = 1; i < tab->size; ++i) 449 { 450 e = tab->array[i]; 451 if (e->refcount && e->len > 0) 452 { 453 e->u.index = sec_size; 454 sec_size += e->len; 455 } 456 } 457 458 tab->sec_size = sec_size; 459 460 /* Adjust the rest. */ 461 for (i = 1; i < tab->size; ++i) 462 { 463 e = tab->array[i]; 464 if (e->refcount && e->len < 0) 465 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); 466 } 467 } 468