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