1 /* ELF strtab with GC and suffix merging support. 2 Copyright 2001, 2002, 2003, 2005, 2006 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., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 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. This includes the zero terminator. */ 34 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 < 0). */ 40 struct elf_strtab_hash_entry *suffix; 41 } u; 42 }; 43 44 /* The strtab hash table. */ 45 46 struct elf_strtab_hash 47 { 48 struct bfd_hash_table table; 49 /* Next available index. */ 50 bfd_size_type size; 51 /* Number of array entries alloced. */ 52 bfd_size_type alloced; 53 /* Final strtab size. */ 54 bfd_size_type sec_size; 55 /* Array of pointers to strtab entries. */ 56 struct elf_strtab_hash_entry **array; 57 }; 58 59 /* Routine to create an entry in a section merge hashtab. */ 60 61 static struct bfd_hash_entry * 62 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry, 63 struct bfd_hash_table *table, 64 const char *string) 65 { 66 /* Allocate the structure if it has not already been allocated by a 67 subclass. */ 68 if (entry == NULL) 69 entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); 70 if (entry == NULL) 71 return NULL; 72 73 /* Call the allocation method of the superclass. */ 74 entry = bfd_hash_newfunc (entry, table, string); 75 76 if (entry) 77 { 78 /* Initialize the local fields. */ 79 struct elf_strtab_hash_entry *ret; 80 81 ret = (struct elf_strtab_hash_entry *) entry; 82 ret->u.index = -1; 83 ret->refcount = 0; 84 ret->len = 0; 85 } 86 87 return entry; 88 } 89 90 /* Create a new hash table. */ 91 92 struct elf_strtab_hash * 93 _bfd_elf_strtab_init (void) 94 { 95 struct elf_strtab_hash *table; 96 bfd_size_type amt = sizeof (struct elf_strtab_hash); 97 98 table = bfd_malloc (amt); 99 if (table == NULL) 100 return NULL; 101 102 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc, 103 sizeof (struct elf_strtab_hash_entry))) 104 { 105 free (table); 106 return NULL; 107 } 108 109 table->sec_size = 0; 110 table->size = 1; 111 table->alloced = 64; 112 amt = sizeof (struct elf_strtab_hasn_entry *); 113 table->array = bfd_malloc (table->alloced * amt); 114 if (table->array == NULL) 115 { 116 free (table); 117 return NULL; 118 } 119 120 table->array[0] = NULL; 121 122 return table; 123 } 124 125 /* Free a strtab. */ 126 127 void 128 _bfd_elf_strtab_free (struct elf_strtab_hash *tab) 129 { 130 bfd_hash_table_free (&tab->table); 131 free (tab->array); 132 free (tab); 133 } 134 135 /* Get the index of an entity in a hash table, adding it if it is not 136 already present. */ 137 138 bfd_size_type 139 _bfd_elf_strtab_add (struct elf_strtab_hash *tab, 140 const char *str, 141 bfd_boolean copy) 142 { 143 register struct elf_strtab_hash_entry *entry; 144 145 /* We handle this specially, since we don't want to do refcounting 146 on it. */ 147 if (*str == '\0') 148 return 0; 149 150 BFD_ASSERT (tab->sec_size == 0); 151 entry = (struct elf_strtab_hash_entry *) 152 bfd_hash_lookup (&tab->table, str, TRUE, copy); 153 154 if (entry == NULL) 155 return (bfd_size_type) -1; 156 157 entry->refcount++; 158 if (entry->len == 0) 159 { 160 entry->len = strlen (str) + 1; 161 /* 2G strings lose. */ 162 BFD_ASSERT (entry->len > 0); 163 if (tab->size == tab->alloced) 164 { 165 bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); 166 tab->alloced *= 2; 167 tab->array = bfd_realloc (tab->array, tab->alloced * amt); 168 if (tab->array == NULL) 169 return (bfd_size_type) -1; 170 } 171 172 entry->u.index = tab->size++; 173 tab->array[entry->u.index] = entry; 174 } 175 return entry->u.index; 176 } 177 178 void 179 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx) 180 { 181 if (idx == 0 || idx == (bfd_size_type) -1) 182 return; 183 BFD_ASSERT (tab->sec_size == 0); 184 BFD_ASSERT (idx < tab->size); 185 ++tab->array[idx]->refcount; 186 } 187 188 void 189 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx) 190 { 191 if (idx == 0 || idx == (bfd_size_type) -1) 192 return; 193 BFD_ASSERT (tab->sec_size == 0); 194 BFD_ASSERT (idx < tab->size); 195 BFD_ASSERT (tab->array[idx]->refcount > 0); 196 --tab->array[idx]->refcount; 197 } 198 199 void 200 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab) 201 { 202 bfd_size_type idx; 203 204 for (idx = 1; idx < tab->size; ++idx) 205 tab->array[idx]->refcount = 0; 206 } 207 208 bfd_size_type 209 _bfd_elf_strtab_size (struct elf_strtab_hash *tab) 210 { 211 return tab->sec_size ? tab->sec_size : tab->size; 212 } 213 214 bfd_size_type 215 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx) 216 { 217 struct elf_strtab_hash_entry *entry; 218 219 if (idx == 0) 220 return 0; 221 BFD_ASSERT (idx < tab->size); 222 BFD_ASSERT (tab->sec_size); 223 entry = tab->array[idx]; 224 BFD_ASSERT (entry->refcount > 0); 225 entry->refcount--; 226 return tab->array[idx]->u.index; 227 } 228 229 bfd_boolean 230 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) 231 { 232 bfd_size_type off = 1, i; 233 234 if (bfd_bwrite ("", 1, abfd) != 1) 235 return FALSE; 236 237 for (i = 1; i < tab->size; ++i) 238 { 239 register const char *str; 240 register unsigned int len; 241 242 BFD_ASSERT (tab->array[i]->refcount == 0); 243 len = tab->array[i]->len; 244 if ((int) len < 0) 245 continue; 246 247 str = tab->array[i]->root.string; 248 if (bfd_bwrite (str, len, abfd) != len) 249 return FALSE; 250 251 off += len; 252 } 253 254 BFD_ASSERT (off == tab->sec_size); 255 return TRUE; 256 } 257 258 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */ 259 260 static int 261 strrevcmp (const void *a, const void *b) 262 { 263 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; 264 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; 265 unsigned int lenA = A->len; 266 unsigned int lenB = B->len; 267 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 268 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 269 int l = lenA < lenB ? lenA : lenB; 270 271 while (l) 272 { 273 if (*s != *t) 274 return (int) *s - (int) *t; 275 s--; 276 t--; 277 l--; 278 } 279 return lenA - lenB; 280 } 281 282 static inline int 283 is_suffix (const struct elf_strtab_hash_entry *A, 284 const struct elf_strtab_hash_entry *B) 285 { 286 if (A->len <= B->len) 287 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 288 not to be equal by the hash table. */ 289 return 0; 290 291 return memcmp (A->root.string + (A->len - B->len), 292 B->root.string, B->len - 1) == 0; 293 } 294 295 /* This function assigns final string table offsets for used strings, 296 merging strings matching suffixes of longer strings if possible. */ 297 298 void 299 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) 300 { 301 struct elf_strtab_hash_entry **array, **a, *e; 302 bfd_size_type size, amt; 303 304 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is 305 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd. 306 Besides, indexing with a long long wouldn't give anything but extra 307 cycles. */ 308 size_t i; 309 310 /* Sort the strings by suffix and length. */ 311 amt = tab->size * sizeof (struct elf_strtab_hash_entry *); 312 array = bfd_malloc (amt); 313 if (array == NULL) 314 goto alloc_failure; 315 316 for (i = 1, a = array; i < tab->size; ++i) 317 { 318 e = tab->array[i]; 319 if (e->refcount) 320 { 321 *a++ = e; 322 /* Adjust the length to not include the zero terminator. */ 323 e->len -= 1; 324 } 325 else 326 e->len = 0; 327 } 328 329 size = a - array; 330 if (size != 0) 331 { 332 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); 333 334 /* Loop over the sorted array and merge suffixes. Start from the 335 end because we want eg. 336 337 s1 -> "d" 338 s2 -> "bcd" 339 s3 -> "abcd" 340 341 to end up as 342 343 s3 -> "abcd" 344 s2 _____^ 345 s1 _______^ 346 347 ie. we don't want s1 pointing into the old s2. */ 348 e = *--a; 349 e->len += 1; 350 while (--a >= array) 351 { 352 struct elf_strtab_hash_entry *cmp = *a; 353 354 cmp->len += 1; 355 if (is_suffix (e, cmp)) 356 { 357 cmp->u.suffix = e; 358 cmp->len = -cmp->len; 359 } 360 else 361 e = cmp; 362 } 363 } 364 365 alloc_failure: 366 if (array) 367 free (array); 368 369 /* Assign positions to the strings we want to keep. */ 370 size = 1; 371 for (i = 1; i < tab->size; ++i) 372 { 373 e = tab->array[i]; 374 if (e->refcount && e->len > 0) 375 { 376 e->u.index = size; 377 size += e->len; 378 } 379 } 380 381 tab->sec_size = size; 382 383 /* Adjust the rest. */ 384 for (i = 1; i < tab->size; ++i) 385 { 386 e = tab->array[i]; 387 if (e->refcount && e->len < 0) 388 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); 389 } 390 } 391