189857Sobrien/* ELF strtab with GC and suffix merging support. 2218822Sdim Copyright 2001, 2002, 2003, 2005, 2006, 2007 3218822Sdim Free Software Foundation, Inc. 489857Sobrien Written by Jakub Jelinek <jakub@redhat.com>. 589857Sobrien 6104834Sobrien This file is part of BFD, the Binary File Descriptor library. 789857Sobrien 8104834Sobrien This program is free software; you can redistribute it and/or modify 9104834Sobrien it under the terms of the GNU General Public License as published by 10104834Sobrien the Free Software Foundation; either version 2 of the License, or 11104834Sobrien (at your option) any later version. 1289857Sobrien 13104834Sobrien This program is distributed in the hope that it will be useful, 14104834Sobrien but WITHOUT ANY WARRANTY; without even the implied warranty of 15104834Sobrien MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16104834Sobrien GNU General Public License for more details. 1789857Sobrien 18104834Sobrien You should have received a copy of the GNU General Public License 19104834Sobrien along with this program; if not, write to the Free Software 20218822Sdim Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 2189857Sobrien 22218822Sdim#include "sysdep.h" 2389857Sobrien#include "bfd.h" 2489857Sobrien#include "libbfd.h" 2589857Sobrien#include "elf-bfd.h" 2689857Sobrien#include "hashtab.h" 27104834Sobrien#include "libiberty.h" 2889857Sobrien 2989857Sobrien/* An entry in the strtab hash table. */ 3089857Sobrien 3189857Sobrienstruct elf_strtab_hash_entry 3289857Sobrien{ 3389857Sobrien struct bfd_hash_entry root; 34130561Sobrien /* Length of this entry. This includes the zero terminator. */ 35130561Sobrien int len; 3689857Sobrien unsigned int refcount; 3789857Sobrien union { 3889857Sobrien /* Index within the merged section. */ 3989857Sobrien bfd_size_type index; 40130561Sobrien /* Entry this is a suffix of (if len < 0). */ 4189857Sobrien struct elf_strtab_hash_entry *suffix; 4289857Sobrien } u; 4389857Sobrien}; 4489857Sobrien 4589857Sobrien/* The strtab hash table. */ 4689857Sobrien 4789857Sobrienstruct elf_strtab_hash 4889857Sobrien{ 4989857Sobrien struct bfd_hash_table table; 5089857Sobrien /* Next available index. */ 5189857Sobrien bfd_size_type size; 5289857Sobrien /* Number of array entries alloced. */ 5389857Sobrien bfd_size_type alloced; 5489857Sobrien /* Final strtab size. */ 5589857Sobrien bfd_size_type sec_size; 5689857Sobrien /* Array of pointers to strtab entries. */ 5789857Sobrien struct elf_strtab_hash_entry **array; 5889857Sobrien}; 5989857Sobrien 6089857Sobrien/* Routine to create an entry in a section merge hashtab. */ 6189857Sobrien 6289857Sobrienstatic struct bfd_hash_entry * 63130561Sobrienelf_strtab_hash_newfunc (struct bfd_hash_entry *entry, 64130561Sobrien struct bfd_hash_table *table, 65130561Sobrien const char *string) 6689857Sobrien{ 6789857Sobrien /* Allocate the structure if it has not already been allocated by a 6889857Sobrien subclass. */ 69130561Sobrien if (entry == NULL) 70130561Sobrien entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); 71130561Sobrien if (entry == NULL) 7289857Sobrien return NULL; 7389857Sobrien 7489857Sobrien /* Call the allocation method of the superclass. */ 75130561Sobrien entry = bfd_hash_newfunc (entry, table, string); 7689857Sobrien 77130561Sobrien if (entry) 7889857Sobrien { 7989857Sobrien /* Initialize the local fields. */ 80130561Sobrien struct elf_strtab_hash_entry *ret; 81130561Sobrien 82130561Sobrien ret = (struct elf_strtab_hash_entry *) entry; 8389857Sobrien ret->u.index = -1; 8489857Sobrien ret->refcount = 0; 8589857Sobrien ret->len = 0; 8689857Sobrien } 8789857Sobrien 88130561Sobrien return entry; 8989857Sobrien} 9089857Sobrien 9189857Sobrien/* Create a new hash table. */ 9289857Sobrien 9389857Sobrienstruct elf_strtab_hash * 94130561Sobrien_bfd_elf_strtab_init (void) 9589857Sobrien{ 9689857Sobrien struct elf_strtab_hash *table; 9789857Sobrien bfd_size_type amt = sizeof (struct elf_strtab_hash); 9889857Sobrien 99130561Sobrien table = bfd_malloc (amt); 10089857Sobrien if (table == NULL) 10189857Sobrien return NULL; 10289857Sobrien 103218822Sdim if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc, 104218822Sdim sizeof (struct elf_strtab_hash_entry))) 10589857Sobrien { 10689857Sobrien free (table); 10789857Sobrien return NULL; 10889857Sobrien } 10989857Sobrien 11089857Sobrien table->sec_size = 0; 11189857Sobrien table->size = 1; 11289857Sobrien table->alloced = 64; 11389857Sobrien amt = sizeof (struct elf_strtab_hasn_entry *); 114130561Sobrien table->array = bfd_malloc (table->alloced * amt); 11589857Sobrien if (table->array == NULL) 11689857Sobrien { 11789857Sobrien free (table); 11889857Sobrien return NULL; 11989857Sobrien } 12089857Sobrien 12189857Sobrien table->array[0] = NULL; 12289857Sobrien 12389857Sobrien return table; 12489857Sobrien} 12589857Sobrien 12689857Sobrien/* Free a strtab. */ 12789857Sobrien 12889857Sobrienvoid 129130561Sobrien_bfd_elf_strtab_free (struct elf_strtab_hash *tab) 13089857Sobrien{ 13189857Sobrien bfd_hash_table_free (&tab->table); 13289857Sobrien free (tab->array); 13389857Sobrien free (tab); 13489857Sobrien} 13589857Sobrien 13689857Sobrien/* Get the index of an entity in a hash table, adding it if it is not 13789857Sobrien already present. */ 13889857Sobrien 13989857Sobrienbfd_size_type 140130561Sobrien_bfd_elf_strtab_add (struct elf_strtab_hash *tab, 141130561Sobrien const char *str, 142130561Sobrien bfd_boolean copy) 14389857Sobrien{ 14489857Sobrien register struct elf_strtab_hash_entry *entry; 14589857Sobrien 14689857Sobrien /* We handle this specially, since we don't want to do refcounting 14789857Sobrien on it. */ 14889857Sobrien if (*str == '\0') 14989857Sobrien return 0; 15089857Sobrien 15189857Sobrien BFD_ASSERT (tab->sec_size == 0); 15289857Sobrien entry = (struct elf_strtab_hash_entry *) 153130561Sobrien bfd_hash_lookup (&tab->table, str, TRUE, copy); 15489857Sobrien 15589857Sobrien if (entry == NULL) 15689857Sobrien return (bfd_size_type) -1; 15789857Sobrien 15889857Sobrien entry->refcount++; 15989857Sobrien if (entry->len == 0) 16089857Sobrien { 16189857Sobrien entry->len = strlen (str) + 1; 162130561Sobrien /* 2G strings lose. */ 163130561Sobrien BFD_ASSERT (entry->len > 0); 16489857Sobrien if (tab->size == tab->alloced) 16589857Sobrien { 16689857Sobrien bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); 16789857Sobrien tab->alloced *= 2; 168130561Sobrien tab->array = bfd_realloc (tab->array, tab->alloced * amt); 16989857Sobrien if (tab->array == NULL) 17089857Sobrien return (bfd_size_type) -1; 17189857Sobrien } 17289857Sobrien 17389857Sobrien entry->u.index = tab->size++; 17489857Sobrien tab->array[entry->u.index] = entry; 17589857Sobrien } 17689857Sobrien return entry->u.index; 17789857Sobrien} 17889857Sobrien 17989857Sobrienvoid 180130561Sobrien_bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx) 18189857Sobrien{ 18289857Sobrien if (idx == 0 || idx == (bfd_size_type) -1) 18389857Sobrien return; 18489857Sobrien BFD_ASSERT (tab->sec_size == 0); 18589857Sobrien BFD_ASSERT (idx < tab->size); 18689857Sobrien ++tab->array[idx]->refcount; 18789857Sobrien} 18889857Sobrien 18989857Sobrienvoid 190130561Sobrien_bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx) 19189857Sobrien{ 19289857Sobrien if (idx == 0 || idx == (bfd_size_type) -1) 19389857Sobrien return; 19489857Sobrien BFD_ASSERT (tab->sec_size == 0); 19589857Sobrien BFD_ASSERT (idx < tab->size); 19689857Sobrien BFD_ASSERT (tab->array[idx]->refcount > 0); 19789857Sobrien --tab->array[idx]->refcount; 19889857Sobrien} 19989857Sobrien 20089857Sobrienvoid 201130561Sobrien_bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab) 20289857Sobrien{ 20389857Sobrien bfd_size_type idx; 20489857Sobrien 20589857Sobrien for (idx = 1; idx < tab->size; ++idx) 20689857Sobrien tab->array[idx]->refcount = 0; 20789857Sobrien} 20889857Sobrien 20989857Sobrienbfd_size_type 210130561Sobrien_bfd_elf_strtab_size (struct elf_strtab_hash *tab) 21189857Sobrien{ 21289857Sobrien return tab->sec_size ? tab->sec_size : tab->size; 21389857Sobrien} 21489857Sobrien 21589857Sobrienbfd_size_type 216130561Sobrien_bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx) 21789857Sobrien{ 21889857Sobrien struct elf_strtab_hash_entry *entry; 21989857Sobrien 22089857Sobrien if (idx == 0) 22189857Sobrien return 0; 22289857Sobrien BFD_ASSERT (idx < tab->size); 22389857Sobrien BFD_ASSERT (tab->sec_size); 22489857Sobrien entry = tab->array[idx]; 22589857Sobrien BFD_ASSERT (entry->refcount > 0); 22689857Sobrien entry->refcount--; 22789857Sobrien return tab->array[idx]->u.index; 22889857Sobrien} 22989857Sobrien 230130561Sobrienbfd_boolean 231130561Sobrien_bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) 23289857Sobrien{ 23389857Sobrien bfd_size_type off = 1, i; 23489857Sobrien 23589857Sobrien if (bfd_bwrite ("", 1, abfd) != 1) 236130561Sobrien return FALSE; 23789857Sobrien 23889857Sobrien for (i = 1; i < tab->size; ++i) 23989857Sobrien { 24089857Sobrien register const char *str; 241130561Sobrien register unsigned int len; 24289857Sobrien 243130561Sobrien BFD_ASSERT (tab->array[i]->refcount == 0); 24489857Sobrien len = tab->array[i]->len; 245130561Sobrien if ((int) len < 0) 24689857Sobrien continue; 24789857Sobrien 248130561Sobrien str = tab->array[i]->root.string; 249130561Sobrien if (bfd_bwrite (str, len, abfd) != len) 250130561Sobrien return FALSE; 25189857Sobrien 25289857Sobrien off += len; 25389857Sobrien } 25489857Sobrien 25589857Sobrien BFD_ASSERT (off == tab->sec_size); 256130561Sobrien return TRUE; 25789857Sobrien} 25889857Sobrien 259130561Sobrien/* Compare two elf_strtab_hash_entry structures. Called via qsort. */ 26089857Sobrien 26189857Sobrienstatic int 262130561Sobrienstrrevcmp (const void *a, const void *b) 26389857Sobrien{ 264130561Sobrien struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; 265130561Sobrien struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; 266130561Sobrien unsigned int lenA = A->len; 267130561Sobrien unsigned int lenB = B->len; 268218822Sdim const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 269218822Sdim const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 270130561Sobrien int l = lenA < lenB ? lenA : lenB; 27189857Sobrien 272130561Sobrien while (l) 273130561Sobrien { 274130561Sobrien if (*s != *t) 275130561Sobrien return (int) *s - (int) *t; 276130561Sobrien s--; 277130561Sobrien t--; 278130561Sobrien l--; 279130561Sobrien } 280130561Sobrien return lenA - lenB; 28189857Sobrien} 28289857Sobrien 283130561Sobrienstatic inline int 284130561Sobrienis_suffix (const struct elf_strtab_hash_entry *A, 285130561Sobrien const struct elf_strtab_hash_entry *B) 28689857Sobrien{ 28789857Sobrien if (A->len <= B->len) 28889857Sobrien /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 28989857Sobrien not to be equal by the hash table. */ 29089857Sobrien return 0; 29189857Sobrien 29289857Sobrien return memcmp (A->root.string + (A->len - B->len), 293130561Sobrien B->root.string, B->len - 1) == 0; 29489857Sobrien} 29589857Sobrien 29689857Sobrien/* This function assigns final string table offsets for used strings, 29789857Sobrien merging strings matching suffixes of longer strings if possible. */ 29889857Sobrien 29989857Sobrienvoid 300130561Sobrien_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) 30189857Sobrien{ 302130561Sobrien struct elf_strtab_hash_entry **array, **a, *e; 30389857Sobrien bfd_size_type size, amt; 30489857Sobrien 30589857Sobrien /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is 30689857Sobrien a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd. 30789857Sobrien Besides, indexing with a long long wouldn't give anything but extra 30889857Sobrien cycles. */ 30989857Sobrien size_t i; 31089857Sobrien 311130561Sobrien /* Sort the strings by suffix and length. */ 31289857Sobrien amt = tab->size * sizeof (struct elf_strtab_hash_entry *); 313130561Sobrien array = bfd_malloc (amt); 31489857Sobrien if (array == NULL) 31589857Sobrien goto alloc_failure; 31689857Sobrien 31789857Sobrien for (i = 1, a = array; i < tab->size; ++i) 318130561Sobrien { 319130561Sobrien e = tab->array[i]; 320130561Sobrien if (e->refcount) 321130561Sobrien { 322130561Sobrien *a++ = e; 323130561Sobrien /* Adjust the length to not include the zero terminator. */ 324130561Sobrien e->len -= 1; 325130561Sobrien } 326130561Sobrien else 327130561Sobrien e->len = 0; 328130561Sobrien } 32989857Sobrien 33089857Sobrien size = a - array; 331130561Sobrien if (size != 0) 332130561Sobrien { 333130561Sobrien qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); 33489857Sobrien 335130561Sobrien /* Loop over the sorted array and merge suffixes. Start from the 336130561Sobrien end because we want eg. 33789857Sobrien 338130561Sobrien s1 -> "d" 339130561Sobrien s2 -> "bcd" 340130561Sobrien s3 -> "abcd" 34189857Sobrien 342130561Sobrien to end up as 34389857Sobrien 344130561Sobrien s3 -> "abcd" 345130561Sobrien s2 _____^ 346130561Sobrien s1 _______^ 34789857Sobrien 348130561Sobrien ie. we don't want s1 pointing into the old s2. */ 349130561Sobrien e = *--a; 350130561Sobrien e->len += 1; 351130561Sobrien while (--a >= array) 35289857Sobrien { 353130561Sobrien struct elf_strtab_hash_entry *cmp = *a; 35489857Sobrien 355130561Sobrien cmp->len += 1; 356130561Sobrien if (is_suffix (e, cmp)) 35789857Sobrien { 358130561Sobrien cmp->u.suffix = e; 359130561Sobrien cmp->len = -cmp->len; 36089857Sobrien } 361130561Sobrien else 362130561Sobrien e = cmp; 36389857Sobrien } 36489857Sobrien } 36589857Sobrien 36689857Sobrienalloc_failure: 36789857Sobrien if (array) 36889857Sobrien free (array); 36989857Sobrien 370130561Sobrien /* Assign positions to the strings we want to keep. */ 37189857Sobrien size = 1; 37289857Sobrien for (i = 1; i < tab->size; ++i) 37389857Sobrien { 37489857Sobrien e = tab->array[i]; 375130561Sobrien if (e->refcount && e->len > 0) 37689857Sobrien { 37789857Sobrien e->u.index = size; 37889857Sobrien size += e->len; 37989857Sobrien } 38089857Sobrien } 38189857Sobrien 38289857Sobrien tab->sec_size = size; 38389857Sobrien 384130561Sobrien /* Adjust the rest. */ 38589857Sobrien for (i = 1; i < tab->size; ++i) 38689857Sobrien { 38789857Sobrien e = tab->array[i]; 388130561Sobrien if (e->refcount && e->len < 0) 389130561Sobrien e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); 39089857Sobrien } 39189857Sobrien} 392