From 2b0f7ef92ee30445837f86ca0149ec6c6c01dc93 Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Wed, 7 Nov 2001 16:50:38 +0000 Subject: * Makefile.am (BFD32_BACKENDS): Add elf-strtab.lo. (BFD32_BACKENDS_CFILES): Add elf-strtab.c. (elf-strtab.lo): Add rule. * Makefile.in: Rebuilt. * configure.in (elf): Add elf-strtab.lo. * configure: Rebuilt. * elf-bfd.h (elf_strtab_hash): Forward declare. (struct elf_link_hash_table): Change dynstr type to struct elf_strtab_hash *. (struct elf_obj_tdata): Change strtab_ptr type to struct elf_strtab_hash *. (_bfd_elf_strtab_init, _bfd_elf_strtab_free, _bfd_elf_strtab_add, _bfd_elf_strtab_addref, _bfd_elf_strtab_delref, _bfd_elf_strtab_clear_all_refs, _bfd_elf_strtab_size, _bfd_elf_strtab_offset, _bfd_elf_strtab_emit, _bfd_elf_strtab_finalize): New prototypes. * elf-strtab.c: New file. * elflink.h (elf_link_add_object_symbols): Use _bfd_elf_strtab_add and _bfd_elf_strtab_size instead of _bfd_stringtab calls. Call _bfd_elf_strtab_delref if DT_NEEDED entry is not needed or when forcing dynamic symbol to local. (elf_link_create_dynamic_sections): Call _bfd_elf_strtab_init instead of elf_stringtab_init. (elf_link_record_local_dynamic_symbol): Likewise, change dynstr type. Use _bfd_elf_strtab functions instead of _bfd_stringtab calls. (size_dynamic_sections): Use _bfd_elf_strtab functions instead of _bfd_stringtab calls. For DT_RUNPATH and Verdaux vda_name fields, call _bfd_elf_strtab_addref. Call elf_finalize_dynstr. (elf_adjust_dynstr_offsets, elf_finalize_dynstr): New functions. (elf_fix_symbol_flags): Call _bfd_elf_strtab_delref when forcing dynamic symbol to local. (elf_link_assign_sym_version): Likewise. (elf_bfd_final_link): Call _bfd_elf_strtab_emit instead of _bfd_stringtab_emit. * elflink.c (_bfd_elf_link_record_dynamic_symbol): Change dynstr type. Call _bfd_elf_strtab functions instead of _bfd_stringtab functions. * elf64-sparc.c (sparc64_elf_size_dynamic_sections): Likewise. * elf.c (_bfd_elf_init_reloc_shdr): Likewise. (elf_fake_sections): Likewise. (assign_section_numbers): Call _bfd_elf_strtab_clear_all_refs on shstrtab hash table, call _bfd_elf_strtab_addref on each section name in the output. Call _bfd_elf_strtab_finalize and use _bfd_elf_strtab_offset to finalize sh_name section header fields. (_bfd_elf_compute_section_file_positions): Use _bfd_elf_strtab_size instead of _bfd_stringtab_size. (prep_headers): Change shstrtab type. Use _bfd_elf_strtab calls instead of _bfd_stringtab calls. --- bfd/elf-strtab.c | 459 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 459 insertions(+) create mode 100644 bfd/elf-strtab.c (limited to 'bfd/elf-strtab.c') diff --git a/bfd/elf-strtab.c b/bfd/elf-strtab.c new file mode 100644 index 0000000..59a25a5 --- /dev/null +++ b/bfd/elf-strtab.c @@ -0,0 +1,459 @@ +/* ELF strtab with GC and suffix merging support. + Copyright 2001 Free Software Foundation, Inc. + Written by Jakub Jelinek . + +This file is part of BFD, the Binary File Descriptor library. + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2 of the License, or +(at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#include "bfd.h" +#include "sysdep.h" +#include "libbfd.h" +#include "elf-bfd.h" +#include "hashtab.h" + +/* An entry in the strtab hash table. */ + +struct elf_strtab_hash_entry +{ + struct bfd_hash_entry root; + /* Length of this entry. */ + unsigned int len; + unsigned int refcount; + union { + /* Index within the merged section. */ + bfd_size_type index; + /* Entry this is a suffix of (if len is 0). */ + struct elf_strtab_hash_entry *suffix; + } u; +}; + +/* The strtab hash table. */ + +struct elf_strtab_hash +{ + struct bfd_hash_table table; + /* Next available index. */ + bfd_size_type size; + /* Number of array entries alloced. */ + bfd_size_type alloced; + /* Final strtab size. */ + bfd_size_type sec_size; + /* Array of pointers to strtab entries. */ + struct elf_strtab_hash_entry **array; +}; + +static struct bfd_hash_entry *elf_strtab_hash_newfunc + PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *)); +static int cmplengthentry PARAMS ((const PTR, const PTR)); +static int last4_eq PARAMS ((const PTR, const PTR)); +static int last_eq PARAMS ((const PTR, const PTR)); + +/* Routine to create an entry in a section merge hashtab. */ + +static struct bfd_hash_entry * +elf_strtab_hash_newfunc (entry, table, string) + struct bfd_hash_entry *entry; + struct bfd_hash_table *table; + const char *string; +{ + struct elf_strtab_hash_entry *ret = (struct elf_strtab_hash_entry *) entry; + + /* Allocate the structure if it has not already been allocated by a + subclass. */ + if (ret == (struct elf_strtab_hash_entry *) NULL) + ret = ((struct elf_strtab_hash_entry *) + bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry))); + if (ret == (struct elf_strtab_hash_entry *) NULL) + return NULL; + + /* Call the allocation method of the superclass. */ + ret = ((struct elf_strtab_hash_entry *) + bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string)); + + if (ret) + { + /* Initialize the local fields. */ + ret->u.index = -1; + ret->refcount = 0; + ret->len = 0; + } + + return (struct bfd_hash_entry *)ret; +} + +/* Create a new hash table. */ + +struct elf_strtab_hash * +_bfd_elf_strtab_init () +{ + struct elf_strtab_hash *table; + bfd_size_type amt = sizeof (struct elf_strtab_hash); + + table = (struct elf_strtab_hash *) bfd_malloc (amt); + if (table == NULL) + return NULL; + + if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc)) + { + free (table); + return NULL; + } + + table->sec_size = 0; + table->size = 1; + table->alloced = 64; + amt = sizeof (struct elf_strtab_hasn_entry *); + table->array = (struct elf_strtab_hash_entry **) + bfd_malloc (table->alloced * amt); + if (table->array == NULL) + { + free (table); + return NULL; + } + + table->array[0] = NULL; + + return table; +} + +/* Free a strtab. */ + +void +_bfd_elf_strtab_free (tab) + struct elf_strtab_hash *tab; +{ + bfd_hash_table_free (&tab->table); + free (tab->array); + free (tab); +} + +/* Get the index of an entity in a hash table, adding it if it is not + already present. */ + +bfd_size_type +_bfd_elf_strtab_add (tab, str, copy) + struct elf_strtab_hash *tab; + const char *str; + boolean copy; +{ + register struct elf_strtab_hash_entry *entry; + + /* We handle this specially, since we don't want to do refcounting + on it. */ + if (*str == '\0') + return 0; + + BFD_ASSERT (tab->sec_size == 0); + entry = (struct elf_strtab_hash_entry *) + bfd_hash_lookup (&tab->table, str, true, copy); + + if (entry == NULL) + return (bfd_size_type) -1; + + entry->refcount++; + if (entry->len == 0) + { + entry->len = strlen (str) + 1; + if (tab->size == tab->alloced) + { + bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); + tab->alloced *= 2; + tab->array = (struct elf_strtab_hash_entry **) + bfd_realloc (tab->array, tab->alloced * amt); + if (tab->array == NULL) + return (bfd_size_type) -1; + } + + entry->u.index = tab->size++; + tab->array[entry->u.index] = entry; + } + return entry->u.index; +} + +void +_bfd_elf_strtab_addref (tab, idx) + struct elf_strtab_hash *tab; + bfd_size_type idx; +{ + if (idx == 0 || idx == (bfd_size_type) -1) + return; + BFD_ASSERT (tab->sec_size == 0); + BFD_ASSERT (idx < tab->size); + ++tab->array[idx]->refcount; +} + +void +_bfd_elf_strtab_delref (tab, idx) + struct elf_strtab_hash *tab; + bfd_size_type idx; +{ + if (idx == 0 || idx == (bfd_size_type) -1) + return; + BFD_ASSERT (tab->sec_size == 0); + BFD_ASSERT (idx < tab->size); + BFD_ASSERT (tab->array[idx]->refcount > 0); + --tab->array[idx]->refcount; +} + +void +_bfd_elf_strtab_clear_all_refs (tab) + struct elf_strtab_hash *tab; +{ + bfd_size_type idx; + + for (idx = 1; idx < tab->size; ++idx) + tab->array[idx]->refcount = 0; +} + +bfd_size_type +_bfd_elf_strtab_size (tab) + struct elf_strtab_hash *tab; +{ + return tab->sec_size ? tab->sec_size : tab->size; +} + +bfd_size_type +_bfd_elf_strtab_offset (tab, idx) + struct elf_strtab_hash *tab; + bfd_size_type idx; +{ + struct elf_strtab_hash_entry *entry; + + if (idx == 0) + return 0; + BFD_ASSERT (idx < tab->size); + BFD_ASSERT (tab->sec_size); + entry = tab->array[idx]; + BFD_ASSERT (entry->refcount > 0); + entry->refcount--; + return tab->array[idx]->u.index; +} + +boolean +_bfd_elf_strtab_emit (abfd, tab) + register bfd *abfd; + struct elf_strtab_hash *tab; +{ + bfd_size_type off = 1, i; + + if (bfd_bwrite ("", 1, abfd) != 1) + return false; + + for (i = 1; i < tab->size; ++i) + { + register const char *str; + register size_t len; + + str = tab->array[i]->root.string; + len = tab->array[i]->len; + BFD_ASSERT (tab->array[i]->refcount == 0); + if (len == 0) + continue; + + if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len) + return false; + + off += len; + } + + BFD_ASSERT (off == tab->sec_size); + return true; +} + +/* Compare two elf_strtab_hash_entry structures. This is called via qsort. */ + +static int +cmplengthentry (a, b) + const PTR a; + const PTR b; +{ + struct elf_strtab_hash_entry * A = *(struct elf_strtab_hash_entry **) a; + struct elf_strtab_hash_entry * B = *(struct elf_strtab_hash_entry **) b; + + if (A->len < B->len) + return 1; + else if (A->len > B->len) + return -1; + + return memcmp (A->root.string, B->root.string, A->len); +} + +static int +last4_eq (a, b) + const PTR a; + const PTR b; +{ + struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a; + struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b; + + if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4) + != 0) + /* This was a hashtable collision. */ + return 0; + + if (A->len <= B->len) + /* B cannot be a suffix of A unless A is equal to B, which is guaranteed + not to be equal by the hash table. */ + return 0; + + return memcmp (A->root.string + (A->len - B->len), + B->root.string, B->len - 5) == 0; +} + +static int +last_eq (a, b) + const PTR a; + const PTR b; +{ + struct elf_strtab_hash_entry * A = (struct elf_strtab_hash_entry *) a; + struct elf_strtab_hash_entry * B = (struct elf_strtab_hash_entry *) b; + + if (B->len >= 5) + /* Longer strings are just pushed into the hash table, + they'll be used when looking up for very short strings. */ + return 0; + + if (memcmp (A->root.string + A->len - 2, B->root.string + B->len - 2, 1) + != 0) + /* This was a hashtable collision. */ + return 0; + + if (A->len <= B->len) + /* B cannot be a suffix of A unless A is equal to B, which is guaranteed + not to be equal by the hash table. */ + return 0; + + return memcmp (A->root.string + (A->len - B->len), + B->root.string, B->len - 2) == 0; +} + +/* This function assigns final string table offsets for used strings, + merging strings matching suffixes of longer strings if possible. */ + +void +_bfd_elf_strtab_finalize (tab) + struct elf_strtab_hash *tab; +{ + struct elf_strtab_hash_entry **array, **a, **end, *e; + htab_t lasttab = NULL, last4tab = NULL; + bfd_size_type size, amt, i; + + /* Now sort the strings by length, longest first. */ + array = NULL; + amt = tab->size * sizeof (struct elf_strtab_hash_entry *); + array = (struct elf_strtab_hash_entry **) bfd_malloc (amt); + if (array == NULL) + goto alloc_failure; + + for (i = 1, a = array; i < tab->size; ++i) + if (tab->array[i]->refcount) + *a++ = tab->array[i]; + else + tab->array[i]->len = 0; + + size = a - array; + + qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry); + + last4tab = htab_create (size * 4, NULL, last4_eq, NULL); + lasttab = htab_create (size * 4, NULL, last_eq, NULL); + if (lasttab == NULL || last4tab == NULL) + goto alloc_failure; + + /* Now insert the strings into hash tables (strings with last 4 characters + and strings with last character equal), look for longer strings which + we're suffix of. */ + for (a = array, end = array + size; a < end; a++) + { + register hashval_t hash; + unsigned int c; + unsigned int i; + const unsigned char *s; + PTR *p; + + e = *a; + if (e->len > 4) + { + s = e->root.string + e->len - 1; + hash = 0; + for (i = 0; i < 4; i++) + { + c = *--s; + hash += c + (c << 17); + hash ^= hash >> 2; + } + p = htab_find_slot_with_hash (last4tab, e, hash, INSERT); + if (p == NULL) + goto alloc_failure; + if (*p) + { + struct elf_strtab_hash_entry *ent; + + ent = (struct elf_strtab_hash_entry *) *p; + e->u.suffix = ent; + e->len = 0; + continue; + } + else + *p = (PTR) e; + } + c = (unsigned char) e->root.string[e->len - 1]; + p = htab_find_slot_with_hash (lasttab, e, c, INSERT); + if (p == NULL) + goto alloc_failure; + if (*p) + { + struct elf_strtab_hash_entry *ent; + + ent = (struct elf_strtab_hash_entry *) *p; + e->u.suffix = ent; + e->len = 0; + } + else + *p = (PTR) e; + } + +alloc_failure: + if (array) + free (array); + if (lasttab) + htab_delete (lasttab); + if (last4tab) + htab_delete (last4tab); + + /* Now assign positions to the strings we want to keep. */ + size = 1; + for (i = 1; i < tab->size; ++i) + { + e = tab->array[i]; + if (e->refcount && e->len) + { + e->u.index = size; + size += e->len; + } + } + + tab->sec_size = size; + + /* And now adjust the rest. */ + for (i = 1; i < tab->size; ++i) + { + e = tab->array[i]; + if (e->refcount && ! e->len) + e->u.index = e->u.suffix->u.index + + (e->u.suffix->len - strlen (e->root.string) - 1); + } +} -- cgit v1.1