1 /* ELF strtab with GC and suffix merging support. 2 Copyright 2001, 2002, 2003, 2005, 2006, 2007, 2008 3 Free Software Foundation, Inc. 4 Written by Jakub Jelinek <jakub@redhat.com>. 5 6 This file is part of BFD, the Binary File Descriptor library. 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, write to the Free Software 20 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 21 MA 02110-1301, USA. */ 22 23 #include "sysdep.h" 24 #include "bfd.h" 25 #include "libbfd.h" 26 #include "elf-bfd.h" 27 #include "hashtab.h" 28 #include "libiberty.h" 29 30 /* An entry in the strtab hash table. */ 31 32 struct elf_strtab_hash_entry 33 { 34 struct bfd_hash_entry root; 35 /* Length of this entry. This includes the zero terminator. */ 36 int len; 37 unsigned int refcount; 38 union { 39 /* Index within the merged section. */ 40 bfd_size_type index; 41 /* Entry this is a suffix of (if len < 0). */ 42 struct elf_strtab_hash_entry *suffix; 43 } u; 44 }; 45 46 /* The strtab hash table. */ 47 48 struct elf_strtab_hash 49 { 50 struct bfd_hash_table table; 51 /* Next available index. */ 52 bfd_size_type size; 53 /* Number of array entries alloced. */ 54 bfd_size_type alloced; 55 /* Final strtab size. */ 56 bfd_size_type sec_size; 57 /* Array of pointers to strtab entries. */ 58 struct elf_strtab_hash_entry **array; 59 }; 60 61 /* Routine to create an entry in a section merge hashtab. */ 62 63 static struct bfd_hash_entry * 64 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry, 65 struct bfd_hash_table *table, 66 const char *string) 67 { 68 /* Allocate the structure if it has not already been allocated by a 69 subclass. */ 70 if (entry == NULL) 71 entry = (struct bfd_hash_entry *) 72 bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); 73 if (entry == NULL) 74 return NULL; 75 76 /* Call the allocation method of the superclass. */ 77 entry = bfd_hash_newfunc (entry, table, string); 78 79 if (entry) 80 { 81 /* Initialize the local fields. */ 82 struct elf_strtab_hash_entry *ret; 83 84 ret = (struct elf_strtab_hash_entry *) entry; 85 ret->u.index = -1; 86 ret->refcount = 0; 87 ret->len = 0; 88 } 89 90 return entry; 91 } 92 93 /* Create a new hash table. */ 94 95 struct elf_strtab_hash * 96 _bfd_elf_strtab_init (void) 97 { 98 struct elf_strtab_hash *table; 99 bfd_size_type amt = sizeof (struct elf_strtab_hash); 100 101 table = (struct elf_strtab_hash *) bfd_malloc (amt); 102 if (table == NULL) 103 return NULL; 104 105 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc, 106 sizeof (struct elf_strtab_hash_entry))) 107 { 108 free (table); 109 return NULL; 110 } 111 112 table->sec_size = 0; 113 table->size = 1; 114 table->alloced = 64; 115 amt = sizeof (struct elf_strtab_hasn_entry *); 116 table->array = (struct elf_strtab_hash_entry **) 117 bfd_malloc (table->alloced * amt); 118 if (table->array == NULL) 119 { 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 bfd_size_type 143 _bfd_elf_strtab_add (struct elf_strtab_hash *tab, 144 const char *str, 145 bfd_boolean 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 (bfd_size_type) -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 (bfd_size_type) -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, bfd_size_type idx) 185 { 186 if (idx == 0 || idx == (bfd_size_type) -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, bfd_size_type idx) 195 { 196 if (idx == 0 || idx == (bfd_size_type) -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, bfd_size_type 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 bfd_size_type idx; 214 215 for (idx = 1; idx < tab->size; idx++) 216 tab->array[idx]->refcount = 0; 217 } 218 219 /* Downsizes strtab. Entries from IDX up to the current size are 220 removed from the array. */ 221 void 222 _bfd_elf_strtab_restore_size (struct elf_strtab_hash *tab, bfd_size_type idx) 223 { 224 bfd_size_type curr_size = tab->size; 225 226 BFD_ASSERT (tab->sec_size == 0); 227 BFD_ASSERT (idx <= curr_size); 228 tab->size = idx; 229 for (; idx < curr_size; ++idx) 230 { 231 /* We don't remove entries from the hash table, just set their 232 REFCOUNT to zero. Setting LEN zero will result in the size 233 growing if the entry is added again. See _bfd_elf_strtab_add. */ 234 tab->array[idx]->refcount = 0; 235 tab->array[idx]->len = 0; 236 } 237 } 238 239 bfd_size_type 240 _bfd_elf_strtab_size (struct elf_strtab_hash *tab) 241 { 242 return tab->sec_size ? tab->sec_size : tab->size; 243 } 244 245 bfd_size_type 246 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx) 247 { 248 struct elf_strtab_hash_entry *entry; 249 250 if (idx == 0) 251 return 0; 252 BFD_ASSERT (idx < tab->size); 253 BFD_ASSERT (tab->sec_size); 254 entry = tab->array[idx]; 255 BFD_ASSERT (entry->refcount > 0); 256 entry->refcount--; 257 return tab->array[idx]->u.index; 258 } 259 260 bfd_boolean 261 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) 262 { 263 bfd_size_type off = 1, i; 264 265 if (bfd_bwrite ("", 1, abfd) != 1) 266 return FALSE; 267 268 for (i = 1; i < tab->size; ++i) 269 { 270 register const char *str; 271 register unsigned int len; 272 273 BFD_ASSERT (tab->array[i]->refcount == 0); 274 len = tab->array[i]->len; 275 if ((int) len < 0) 276 continue; 277 278 str = tab->array[i]->root.string; 279 if (bfd_bwrite (str, len, abfd) != len) 280 return FALSE; 281 282 off += len; 283 } 284 285 BFD_ASSERT (off == tab->sec_size); 286 return TRUE; 287 } 288 289 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */ 290 291 static int 292 strrevcmp (const void *a, const void *b) 293 { 294 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; 295 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; 296 unsigned int lenA = A->len; 297 unsigned int lenB = B->len; 298 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 299 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 300 int l = lenA < lenB ? lenA : lenB; 301 302 while (l) 303 { 304 if (*s != *t) 305 return (int) *s - (int) *t; 306 s--; 307 t--; 308 l--; 309 } 310 return lenA - lenB; 311 } 312 313 static inline int 314 is_suffix (const struct elf_strtab_hash_entry *A, 315 const struct elf_strtab_hash_entry *B) 316 { 317 if (A->len <= B->len) 318 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 319 not to be equal by the hash table. */ 320 return 0; 321 322 return memcmp (A->root.string + (A->len - B->len), 323 B->root.string, B->len - 1) == 0; 324 } 325 326 /* This function assigns final string table offsets for used strings, 327 merging strings matching suffixes of longer strings if possible. */ 328 329 void 330 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) 331 { 332 struct elf_strtab_hash_entry **array, **a, *e; 333 bfd_size_type size, amt; 334 335 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is 336 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd. 337 Besides, indexing with a long long wouldn't give anything but extra 338 cycles. */ 339 size_t i; 340 341 /* Sort the strings by suffix and length. */ 342 amt = tab->size * sizeof (struct elf_strtab_hash_entry *); 343 array = (struct elf_strtab_hash_entry **) bfd_malloc (amt); 344 if (array == NULL) 345 goto alloc_failure; 346 347 for (i = 1, a = array; i < tab->size; ++i) 348 { 349 e = tab->array[i]; 350 if (e->refcount) 351 { 352 *a++ = e; 353 /* Adjust the length to not include the zero terminator. */ 354 e->len -= 1; 355 } 356 else 357 e->len = 0; 358 } 359 360 size = a - array; 361 if (size != 0) 362 { 363 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); 364 365 /* Loop over the sorted array and merge suffixes. Start from the 366 end because we want eg. 367 368 s1 -> "d" 369 s2 -> "bcd" 370 s3 -> "abcd" 371 372 to end up as 373 374 s3 -> "abcd" 375 s2 _____^ 376 s1 _______^ 377 378 ie. we don't want s1 pointing into the old s2. */ 379 e = *--a; 380 e->len += 1; 381 while (--a >= array) 382 { 383 struct elf_strtab_hash_entry *cmp = *a; 384 385 cmp->len += 1; 386 if (is_suffix (e, cmp)) 387 { 388 cmp->u.suffix = e; 389 cmp->len = -cmp->len; 390 } 391 else 392 e = cmp; 393 } 394 } 395 396 alloc_failure: 397 if (array) 398 free (array); 399 400 /* Assign positions to the strings we want to keep. */ 401 size = 1; 402 for (i = 1; i < tab->size; ++i) 403 { 404 e = tab->array[i]; 405 if (e->refcount && e->len > 0) 406 { 407 e->u.index = size; 408 size += e->len; 409 } 410 } 411 412 tab->sec_size = size; 413 414 /* Adjust the rest. */ 415 for (i = 1; i < tab->size; ++i) 416 { 417 e = tab->array[i]; 418 if (e->refcount && e->len < 0) 419 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); 420 } 421 } 422