merge.c revision 89857
189857Sobrien/* SEC_MERGE support. 289857Sobrien Copyright 2001 Free Software Foundation, Inc. 389857Sobrien Written by Jakub Jelinek <jakub@redhat.com>. 489857Sobrien 589857SobrienThis file is part of BFD, the Binary File Descriptor library. 689857Sobrien 789857SobrienThis program is free software; you can redistribute it and/or modify 889857Sobrienit under the terms of the GNU General Public License as published by 989857Sobrienthe Free Software Foundation; either version 2 of the License, or 1089857Sobrien(at your option) any later version. 1189857Sobrien 1289857SobrienThis program is distributed in the hope that it will be useful, 1389857Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1489857SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1589857SobrienGNU General Public License for more details. 1689857Sobrien 1789857SobrienYou should have received a copy of the GNU General Public License 1889857Sobrienalong with this program; if not, write to the Free Software 1989857SobrienFoundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 2089857Sobrien 2189857Sobrien/* This file contains support for merging duplicate entities within sections, 2289857Sobrien as used in ELF SHF_MERGE. */ 2389857Sobrien 2489857Sobrien#include "bfd.h" 2589857Sobrien#include "sysdep.h" 2689857Sobrien#include "libbfd.h" 2789857Sobrien#include "hashtab.h" 2889857Sobrien 2989857Sobrienstruct sec_merge_sec_info; 3089857Sobrien 3189857Sobrien/* An entry in the section merge hash table. */ 3289857Sobrien 3389857Sobrienstruct sec_merge_hash_entry 3489857Sobrien{ 3589857Sobrien struct bfd_hash_entry root; 3689857Sobrien /* Length of this entry. */ 3789857Sobrien unsigned int len; 3889857Sobrien /* Start of this string needs to be aligned to 3989857Sobrien alignment octets (not 1 << align). */ 4089857Sobrien unsigned int alignment; 4189857Sobrien union { 4289857Sobrien /* Index within the merged section. */ 4389857Sobrien bfd_size_type index; 4489857Sobrien /* Entity size (if present in suffix hash tables). */ 4589857Sobrien unsigned int entsize; 4689857Sobrien /* Entry this is a suffix of (if alignment is 0). */ 4789857Sobrien struct sec_merge_hash_entry *suffix; 4889857Sobrien } u; 4989857Sobrien /* Which section is it in. */ 5089857Sobrien struct sec_merge_sec_info *secinfo; 5189857Sobrien /* Next entity in the hash table. */ 5289857Sobrien struct sec_merge_hash_entry *next; 5389857Sobrien}; 5489857Sobrien 5589857Sobrien/* The section merge hash table. */ 5689857Sobrien 5789857Sobrienstruct sec_merge_hash 5889857Sobrien{ 5989857Sobrien struct bfd_hash_table table; 6089857Sobrien /* Next available index. */ 6189857Sobrien bfd_size_type size; 6289857Sobrien /* First entity in the SEC_MERGE sections of this type. */ 6389857Sobrien struct sec_merge_hash_entry *first; 6489857Sobrien /* Last entity in the SEC_MERGE sections of this type. */ 6589857Sobrien struct sec_merge_hash_entry *last; 6689857Sobrien /* Entity size. */ 6789857Sobrien unsigned int entsize; 6889857Sobrien /* Are entries fixed size or zero terminated strings? */ 6989857Sobrien boolean strings; 7089857Sobrien}; 7189857Sobrien 7289857Sobrienstruct sec_merge_info 7389857Sobrien{ 7489857Sobrien /* Chain of sec_merge_infos. */ 7589857Sobrien struct sec_merge_info *next; 7689857Sobrien /* Chain of sec_merge_sec_infos. */ 7789857Sobrien struct sec_merge_sec_info *chain; 7889857Sobrien /* A hash table used to hold section content. */ 7989857Sobrien struct sec_merge_hash *htab; 8089857Sobrien}; 8189857Sobrien 8289857Sobrienstruct sec_merge_sec_info 8389857Sobrien{ 8489857Sobrien /* Chain of sec_merge_sec_infos. */ 8589857Sobrien struct sec_merge_sec_info *next; 8689857Sobrien /* The corresponding section. */ 8789857Sobrien asection *sec; 8889857Sobrien /* Pointer to merge_info pointing to us. */ 8989857Sobrien PTR *psecinfo; 9089857Sobrien /* A hash table used to hold section content. */ 9189857Sobrien struct sec_merge_hash *htab; 9289857Sobrien /* First string in this section. */ 9389857Sobrien struct sec_merge_hash_entry *first; 9489857Sobrien /* Original section content. */ 9589857Sobrien unsigned char contents[1]; 9689857Sobrien}; 9789857Sobrien 9889857Sobrienstatic struct bfd_hash_entry *sec_merge_hash_newfunc 9989857Sobrien PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *)); 10089857Sobrienstatic struct sec_merge_hash_entry *sec_merge_hash_lookup 10189857Sobrien PARAMS ((struct sec_merge_hash *, const char *, unsigned int, boolean)); 10289857Sobrienstatic struct sec_merge_hash *sec_merge_init 10389857Sobrien PARAMS ((unsigned int, boolean)); 10489857Sobrienstatic struct sec_merge_hash_entry *sec_merge_add 10589857Sobrien PARAMS ((struct sec_merge_hash *, const char *, unsigned int, 10689857Sobrien struct sec_merge_sec_info *)); 10789857Sobrienstatic boolean sec_merge_emit 10889857Sobrien PARAMS ((bfd *, struct sec_merge_hash_entry *)); 10989857Sobrienstatic int cmplengthentry PARAMS ((const PTR, const PTR)); 11089857Sobrienstatic int last4_eq PARAMS ((const PTR, const PTR)); 11189857Sobrienstatic int last_eq PARAMS ((const PTR, const PTR)); 11289857Sobrienstatic boolean record_section 11389857Sobrien PARAMS ((struct sec_merge_info *, struct sec_merge_sec_info *)); 11489857Sobrienstatic void merge_strings PARAMS ((struct sec_merge_info *)); 11589857Sobrien 11689857Sobrien/* Routine to create an entry in a section merge hashtab. */ 11789857Sobrien 11889857Sobrienstatic struct bfd_hash_entry * 11989857Sobriensec_merge_hash_newfunc (entry, table, string) 12089857Sobrien struct bfd_hash_entry *entry; 12189857Sobrien struct bfd_hash_table *table; 12289857Sobrien const char *string; 12389857Sobrien{ 12489857Sobrien struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry; 12589857Sobrien 12689857Sobrien /* Allocate the structure if it has not already been allocated by a 12789857Sobrien subclass. */ 12889857Sobrien if (ret == (struct sec_merge_hash_entry *) NULL) 12989857Sobrien ret = ((struct sec_merge_hash_entry *) 13089857Sobrien bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry))); 13189857Sobrien if (ret == (struct sec_merge_hash_entry *) NULL) 13289857Sobrien return NULL; 13389857Sobrien 13489857Sobrien /* Call the allocation method of the superclass. */ 13589857Sobrien ret = ((struct sec_merge_hash_entry *) 13689857Sobrien bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string)); 13789857Sobrien 13889857Sobrien if (ret) 13989857Sobrien { 14089857Sobrien /* Initialize the local fields. */ 14189857Sobrien ret->u.suffix = NULL; 14289857Sobrien ret->alignment = 0; 14389857Sobrien ret->secinfo = NULL; 14489857Sobrien ret->next = NULL; 14589857Sobrien } 14689857Sobrien 14789857Sobrien return (struct bfd_hash_entry *)ret; 14889857Sobrien} 14989857Sobrien 15089857Sobrien/* Look up an entry in a section merge hash table. */ 15189857Sobrien 15289857Sobrienstatic struct sec_merge_hash_entry * 15389857Sobriensec_merge_hash_lookup (table, string, alignment, create) 15489857Sobrien struct sec_merge_hash *table; 15589857Sobrien const char *string; 15689857Sobrien unsigned int alignment; 15789857Sobrien boolean create; 15889857Sobrien{ 15989857Sobrien register const unsigned char *s; 16089857Sobrien register unsigned long hash; 16189857Sobrien register unsigned int c; 16289857Sobrien struct sec_merge_hash_entry *hashp; 16389857Sobrien unsigned int len, i; 16489857Sobrien unsigned int index; 16589857Sobrien 16689857Sobrien hash = 0; 16789857Sobrien len = 0; 16889857Sobrien s = (const unsigned char *) string; 16989857Sobrien if (table->strings) 17089857Sobrien { 17189857Sobrien if (table->entsize == 1) 17289857Sobrien { 17389857Sobrien while ((c = *s++) != '\0') 17489857Sobrien { 17589857Sobrien hash += c + (c << 17); 17689857Sobrien hash ^= hash >> 2; 17789857Sobrien ++len; 17889857Sobrien } 17989857Sobrien hash += len + (len << 17); 18089857Sobrien } 18189857Sobrien else 18289857Sobrien { 18389857Sobrien for (;;) 18489857Sobrien { 18589857Sobrien for (i = 0; i < table->entsize; ++i) 18689857Sobrien if (s[i] != '\0') 18789857Sobrien break; 18889857Sobrien if (i == table->entsize) 18989857Sobrien break; 19089857Sobrien for (i = 0; i < table->entsize; ++i) 19189857Sobrien { 19289857Sobrien c = *s++; 19389857Sobrien hash += c + (c << 17); 19489857Sobrien hash ^= hash >> 2; 19589857Sobrien } 19689857Sobrien ++len; 19789857Sobrien } 19889857Sobrien hash += len + (len << 17); 19989857Sobrien len *= table->entsize; 20089857Sobrien } 20189857Sobrien hash ^= hash >> 2; 20289857Sobrien len += table->entsize; 20389857Sobrien } 20489857Sobrien else 20589857Sobrien { 20689857Sobrien for (i = 0; i < table->entsize; ++i) 20789857Sobrien { 20889857Sobrien c = *s++; 20989857Sobrien hash += c + (c << 17); 21089857Sobrien hash ^= hash >> 2; 21189857Sobrien } 21289857Sobrien len = table->entsize; 21389857Sobrien } 21489857Sobrien 21589857Sobrien index = hash % table->table.size; 21689857Sobrien for (hashp = (struct sec_merge_hash_entry *) table->table.table[index]; 21789857Sobrien hashp != (struct sec_merge_hash_entry *) NULL; 21889857Sobrien hashp = (struct sec_merge_hash_entry *) hashp->root.next) 21989857Sobrien { 22089857Sobrien if (hashp->root.hash == hash 22189857Sobrien && len == hashp->len 22289857Sobrien && memcmp (hashp->root.string, string, len) == 0) 22389857Sobrien { 22489857Sobrien /* If the string we found does not have at least the required 22589857Sobrien alignment, we need to insert another copy. */ 22689857Sobrien if (hashp->alignment < alignment) 22789857Sobrien { 22889857Sobrien /* Mark the less aligned copy as deleted. */ 22989857Sobrien hashp->len = 0; 23089857Sobrien hashp->alignment = 0; 23189857Sobrien break; 23289857Sobrien } 23389857Sobrien return hashp; 23489857Sobrien } 23589857Sobrien } 23689857Sobrien 23789857Sobrien if (! create) 23889857Sobrien return (struct sec_merge_hash_entry *) NULL; 23989857Sobrien 24089857Sobrien hashp = (struct sec_merge_hash_entry *) 24189857Sobrien sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL, 24289857Sobrien (struct bfd_hash_table *) table, string); 24389857Sobrien if (hashp == (struct sec_merge_hash_entry *) NULL) 24489857Sobrien return (struct sec_merge_hash_entry *) NULL; 24589857Sobrien hashp->root.string = string; 24689857Sobrien hashp->root.hash = hash; 24789857Sobrien hashp->len = len; 24889857Sobrien hashp->alignment = alignment; 24989857Sobrien hashp->root.next = table->table.table[index]; 25089857Sobrien table->table.table[index] = (struct bfd_hash_entry *) hashp; 25189857Sobrien 25289857Sobrien return hashp; 25389857Sobrien} 25489857Sobrien 25589857Sobrien/* Create a new hash table. */ 25689857Sobrien 25789857Sobrienstatic struct sec_merge_hash * 25889857Sobriensec_merge_init (entsize, strings) 25989857Sobrien unsigned int entsize; 26089857Sobrien boolean strings; 26189857Sobrien{ 26289857Sobrien struct sec_merge_hash *table; 26389857Sobrien bfd_size_type amt = sizeof (struct sec_merge_hash); 26489857Sobrien 26589857Sobrien table = (struct sec_merge_hash *) bfd_malloc (amt); 26689857Sobrien if (table == NULL) 26789857Sobrien return NULL; 26889857Sobrien 26989857Sobrien if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc)) 27089857Sobrien { 27189857Sobrien free (table); 27289857Sobrien return NULL; 27389857Sobrien } 27489857Sobrien 27589857Sobrien table->size = 0; 27689857Sobrien table->first = NULL; 27789857Sobrien table->last = NULL; 27889857Sobrien table->entsize = entsize; 27989857Sobrien table->strings = strings; 28089857Sobrien 28189857Sobrien return table; 28289857Sobrien} 28389857Sobrien 28489857Sobrien/* Get the index of an entity in a hash table, adding it if it is not 28589857Sobrien already present. */ 28689857Sobrien 28789857Sobrienstatic struct sec_merge_hash_entry * 28889857Sobriensec_merge_add (tab, str, alignment, secinfo) 28989857Sobrien struct sec_merge_hash *tab; 29089857Sobrien const char *str; 29189857Sobrien unsigned int alignment; 29289857Sobrien struct sec_merge_sec_info *secinfo; 29389857Sobrien{ 29489857Sobrien register struct sec_merge_hash_entry *entry; 29589857Sobrien 29689857Sobrien entry = sec_merge_hash_lookup (tab, str, alignment, true); 29789857Sobrien if (entry == NULL) 29889857Sobrien return NULL; 29989857Sobrien 30089857Sobrien if (entry->secinfo == NULL) 30189857Sobrien { 30289857Sobrien tab->size++; 30389857Sobrien entry->secinfo = secinfo; 30489857Sobrien if (tab->first == NULL) 30589857Sobrien tab->first = entry; 30689857Sobrien else 30789857Sobrien tab->last->next = entry; 30889857Sobrien tab->last = entry; 30989857Sobrien } 31089857Sobrien 31189857Sobrien return entry; 31289857Sobrien} 31389857Sobrien 31489857Sobrienstatic boolean 31589857Sobriensec_merge_emit (abfd, entry) 31689857Sobrien register bfd *abfd; 31789857Sobrien struct sec_merge_hash_entry *entry; 31889857Sobrien{ 31989857Sobrien struct sec_merge_sec_info *secinfo = entry->secinfo; 32089857Sobrien asection *sec = secinfo->sec; 32189857Sobrien char *pad = ""; 32289857Sobrien bfd_size_type off = 0; 32389857Sobrien int alignment_power = bfd_get_section_alignment (abfd, sec->output_section); 32489857Sobrien 32589857Sobrien if (alignment_power) 32689857Sobrien pad = bfd_zmalloc ((bfd_size_type) 1 << alignment_power); 32789857Sobrien 32889857Sobrien for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next) 32989857Sobrien { 33089857Sobrien register const char *str; 33189857Sobrien register size_t len; 33289857Sobrien 33389857Sobrien len = off & (entry->alignment - 1); 33489857Sobrien if (len) 33589857Sobrien { 33689857Sobrien len = entry->alignment - len; 33789857Sobrien if (bfd_bwrite ((PTR) pad, (bfd_size_type) len, abfd) != len) 33889857Sobrien break; 33989857Sobrien off += len; 34089857Sobrien } 34189857Sobrien 34289857Sobrien str = entry->root.string; 34389857Sobrien len = entry->len; 34489857Sobrien 34589857Sobrien if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len) 34689857Sobrien break; 34789857Sobrien 34889857Sobrien off += len; 34989857Sobrien } 35089857Sobrien 35189857Sobrien if (alignment_power) 35289857Sobrien free (pad); 35389857Sobrien 35489857Sobrien return entry == NULL || entry->secinfo != secinfo; 35589857Sobrien} 35689857Sobrien 35789857Sobrien/* This function is called for each input file from the add_symbols 35889857Sobrien pass of the linker. */ 35989857Sobrien 36089857Sobrienboolean 36189857Sobrien_bfd_merge_section (abfd, psinfo, sec, psecinfo) 36289857Sobrien bfd *abfd; 36389857Sobrien PTR *psinfo; 36489857Sobrien asection *sec; 36589857Sobrien PTR *psecinfo; 36689857Sobrien{ 36789857Sobrien struct sec_merge_info *sinfo; 36889857Sobrien struct sec_merge_sec_info *secinfo; 36989857Sobrien unsigned int align; 37089857Sobrien bfd_size_type amt; 37189857Sobrien 37289857Sobrien if (sec->_raw_size == 0 37389857Sobrien || (sec->flags & SEC_EXCLUDE) 37489857Sobrien || (sec->flags & SEC_MERGE) == 0 37589857Sobrien || sec->entsize == 0) 37689857Sobrien return true; 37789857Sobrien 37889857Sobrien if ((sec->flags & SEC_RELOC) != 0) 37989857Sobrien { 38089857Sobrien /* We aren't prepared to handle relocations in merged sections. */ 38189857Sobrien return true; 38289857Sobrien } 38389857Sobrien 38489857Sobrien if (sec->output_section != NULL 38589857Sobrien && bfd_is_abs_section (sec->output_section)) 38689857Sobrien { 38789857Sobrien /* The section is being discarded from the link, so we should 38889857Sobrien just ignore it. */ 38989857Sobrien return true; 39089857Sobrien } 39189857Sobrien 39289857Sobrien align = bfd_get_section_alignment (sec->owner, sec); 39389857Sobrien if ((sec->entsize < (unsigned int)(1 << align) 39489857Sobrien && ((sec->entsize & (sec->entsize - 1)) 39589857Sobrien || !(sec->flags & SEC_STRINGS))) 39689857Sobrien || (sec->entsize > (unsigned int)(1 << align) 39789857Sobrien && (sec->entsize & ((1 << align) - 1)))) 39889857Sobrien { 39989857Sobrien /* Sanity check. If string character size is smaller than 40089857Sobrien alignment, then we require character size to be a power 40189857Sobrien of 2, otherwise character size must be integer multiple 40289857Sobrien of alignment. For non-string constants, alignment must 40389857Sobrien be smaller than or equal to entity size and entity size 40489857Sobrien must be integer multiple of alignment. */ 40589857Sobrien return true; 40689857Sobrien } 40789857Sobrien 40889857Sobrien for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next) 40989857Sobrien if ((secinfo = sinfo->chain) 41089857Sobrien && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS)) 41189857Sobrien && secinfo->sec->entsize == sec->entsize 41289857Sobrien && ! strcmp (secinfo->sec->name, sec->name)) 41389857Sobrien break; 41489857Sobrien 41589857Sobrien if (sinfo == NULL) 41689857Sobrien { 41789857Sobrien /* Initialize the information we need to keep track of. */ 41889857Sobrien sinfo = (struct sec_merge_info *) 41989857Sobrien bfd_alloc (abfd, (bfd_size_type) sizeof (struct sec_merge_info)); 42089857Sobrien if (sinfo == NULL) 42189857Sobrien goto error_return; 42289857Sobrien sinfo->next = (struct sec_merge_info *) *psinfo; 42389857Sobrien sinfo->chain = NULL; 42489857Sobrien *psinfo = (PTR) sinfo; 42589857Sobrien sinfo->htab = 42689857Sobrien sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS)); 42789857Sobrien if (sinfo->htab == NULL) 42889857Sobrien goto error_return; 42989857Sobrien } 43089857Sobrien 43189857Sobrien /* Read the section from abfd. */ 43289857Sobrien 43389857Sobrien amt = sizeof (struct sec_merge_sec_info) + sec->_raw_size - 1; 43489857Sobrien *psecinfo = bfd_alloc (abfd, amt); 43589857Sobrien if (*psecinfo == NULL) 43689857Sobrien goto error_return; 43789857Sobrien 43889857Sobrien secinfo = (struct sec_merge_sec_info *)*psecinfo; 43989857Sobrien if (sinfo->chain) 44089857Sobrien { 44189857Sobrien secinfo->next = sinfo->chain->next; 44289857Sobrien sinfo->chain->next = secinfo; 44389857Sobrien } 44489857Sobrien else 44589857Sobrien secinfo->next = secinfo; 44689857Sobrien sinfo->chain = secinfo; 44789857Sobrien secinfo->sec = sec; 44889857Sobrien secinfo->psecinfo = psecinfo; 44989857Sobrien secinfo->htab = sinfo->htab; 45089857Sobrien secinfo->first = NULL; 45189857Sobrien 45289857Sobrien if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents, 45389857Sobrien (bfd_vma) 0, sec->_raw_size)) 45489857Sobrien goto error_return; 45589857Sobrien 45689857Sobrien return true; 45789857Sobrien 45889857Sobrien error_return: 45989857Sobrien *psecinfo = NULL; 46089857Sobrien return false; 46189857Sobrien} 46289857Sobrien 46389857Sobrien/* Compare two sec_merge_hash_entry structures. This is called via qsort. */ 46489857Sobrien 46589857Sobrienstatic int 46689857Sobriencmplengthentry (a, b) 46789857Sobrien const PTR a; 46889857Sobrien const PTR b; 46989857Sobrien{ 47089857Sobrien struct sec_merge_hash_entry * A = *(struct sec_merge_hash_entry **) a; 47189857Sobrien struct sec_merge_hash_entry * B = *(struct sec_merge_hash_entry **) b; 47289857Sobrien 47389857Sobrien if (A->len < B->len) 47489857Sobrien return 1; 47589857Sobrien else if (A->len > B->len) 47689857Sobrien return -1; 47789857Sobrien 47889857Sobrien return memcmp (A->root.string, B->root.string, A->len); 47989857Sobrien} 48089857Sobrien 48189857Sobrienstatic int 48289857Sobrienlast4_eq (a, b) 48389857Sobrien const PTR a; 48489857Sobrien const PTR b; 48589857Sobrien{ 48689857Sobrien struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a; 48789857Sobrien struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b; 48889857Sobrien 48989857Sobrien if (memcmp (A->root.string + A->len - 5 * A->u.entsize, 49089857Sobrien B->root.string + B->len - 5 * A->u.entsize, 49189857Sobrien 4 * A->u.entsize) != 0) 49289857Sobrien /* This was a hashtable collision. */ 49389857Sobrien return 0; 49489857Sobrien 49589857Sobrien if (A->len <= B->len) 49689857Sobrien /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 49789857Sobrien not to be equal by the hash table. */ 49889857Sobrien return 0; 49989857Sobrien 50089857Sobrien if (A->alignment < B->alignment 50189857Sobrien || ((A->len - B->len) & (B->alignment - 1))) 50289857Sobrien /* The suffix is not sufficiently aligned. */ 50389857Sobrien return 0; 50489857Sobrien 50589857Sobrien return memcmp (A->root.string + (A->len - B->len), 50689857Sobrien B->root.string, B->len - 5 * A->u.entsize) == 0; 50789857Sobrien} 50889857Sobrien 50989857Sobrienstatic int 51089857Sobrienlast_eq (a, b) 51189857Sobrien const PTR a; 51289857Sobrien const PTR b; 51389857Sobrien{ 51489857Sobrien struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a; 51589857Sobrien struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b; 51689857Sobrien 51789857Sobrien if (B->len >= 5 * A->u.entsize) 51889857Sobrien /* Longer strings are just pushed into the hash table, 51989857Sobrien they'll be used when looking up for very short strings. */ 52089857Sobrien return 0; 52189857Sobrien 52289857Sobrien if (memcmp (A->root.string + A->len - 2 * A->u.entsize, 52389857Sobrien B->root.string + B->len - 2 * A->u.entsize, 52489857Sobrien A->u.entsize) != 0) 52589857Sobrien /* This was a hashtable collision. */ 52689857Sobrien return 0; 52789857Sobrien 52889857Sobrien if (A->len <= B->len) 52989857Sobrien /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 53089857Sobrien not to be equal by the hash table. */ 53189857Sobrien return 0; 53289857Sobrien 53389857Sobrien if (A->alignment < B->alignment 53489857Sobrien || ((A->len - B->len) & (B->alignment - 1))) 53589857Sobrien /* The suffix is not sufficiently aligned. */ 53689857Sobrien return 0; 53789857Sobrien 53889857Sobrien return memcmp (A->root.string + (A->len - B->len), 53989857Sobrien B->root.string, B->len - 2 * A->u.entsize) == 0; 54089857Sobrien} 54189857Sobrien 54289857Sobrien/* Record one section into the hash table. */ 54389857Sobrienstatic boolean 54489857Sobrienrecord_section (sinfo, secinfo) 54589857Sobrien struct sec_merge_info *sinfo; 54689857Sobrien struct sec_merge_sec_info *secinfo; 54789857Sobrien{ 54889857Sobrien asection *sec = secinfo->sec; 54989857Sobrien struct sec_merge_hash_entry *entry; 55089857Sobrien boolean nul; 55189857Sobrien unsigned char *p, *end; 55289857Sobrien bfd_vma mask, eltalign; 55389857Sobrien unsigned int align, i; 55489857Sobrien 55589857Sobrien align = bfd_get_section_alignment (sec->owner, sec); 55689857Sobrien end = secinfo->contents + sec->_raw_size; 55789857Sobrien nul = false; 55889857Sobrien mask = ((bfd_vma) 1 << align) - 1; 55989857Sobrien if (sec->flags & SEC_STRINGS) 56089857Sobrien { 56189857Sobrien for (p = secinfo->contents; p < end; ) 56289857Sobrien { 56389857Sobrien eltalign = p - secinfo->contents; 56489857Sobrien eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1; 56589857Sobrien if (!eltalign || eltalign > mask) 56689857Sobrien eltalign = mask + 1; 56789857Sobrien entry = sec_merge_add (sinfo->htab, p, (unsigned) eltalign, secinfo); 56889857Sobrien if (! entry) 56989857Sobrien goto error_return; 57089857Sobrien p += entry->len; 57189857Sobrien if (sec->entsize == 1) 57289857Sobrien { 57389857Sobrien while (p < end && *p == 0) 57489857Sobrien { 57589857Sobrien if (!nul && !((p - secinfo->contents) & mask)) 57689857Sobrien { 57789857Sobrien nul = true; 57889857Sobrien entry = sec_merge_add (sinfo->htab, "", 57989857Sobrien (unsigned) mask + 1, secinfo); 58089857Sobrien if (! entry) 58189857Sobrien goto error_return; 58289857Sobrien } 58389857Sobrien p++; 58489857Sobrien } 58589857Sobrien } 58689857Sobrien else 58789857Sobrien { 58889857Sobrien while (p < end) 58989857Sobrien { 59089857Sobrien for (i = 0; i < sec->entsize; i++) 59189857Sobrien if (p[i] != '\0') 59289857Sobrien break; 59389857Sobrien if (i != sec->entsize) 59489857Sobrien break; 59589857Sobrien if (!nul && !((p - secinfo->contents) & mask)) 59689857Sobrien { 59789857Sobrien nul = true; 59889857Sobrien entry = sec_merge_add (sinfo->htab, p, 59989857Sobrien (unsigned) mask + 1, secinfo); 60089857Sobrien if (! entry) 60189857Sobrien goto error_return; 60289857Sobrien } 60389857Sobrien p += sec->entsize; 60489857Sobrien } 60589857Sobrien } 60689857Sobrien } 60789857Sobrien } 60889857Sobrien else 60989857Sobrien { 61089857Sobrien for (p = secinfo->contents; p < end; p += sec->entsize) 61189857Sobrien { 61289857Sobrien entry = sec_merge_add (sinfo->htab, p, 1, secinfo); 61389857Sobrien if (! entry) 61489857Sobrien goto error_return; 61589857Sobrien } 61689857Sobrien } 61789857Sobrien 61889857Sobrien return true; 61989857Sobrien 62089857Sobrienerror_return: 62189857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 62289857Sobrien *secinfo->psecinfo = NULL; 62389857Sobrien return false; 62489857Sobrien} 62589857Sobrien 62689857Sobrien/* This is a helper function for _bfd_merge_sections. It attempts to 62789857Sobrien merge strings matching suffixes of longer strings. */ 62889857Sobrienstatic void 62989857Sobrienmerge_strings (sinfo) 63089857Sobrien struct sec_merge_info *sinfo; 63189857Sobrien{ 63289857Sobrien struct sec_merge_hash_entry **array, **a, **end, *e; 63389857Sobrien struct sec_merge_sec_info *secinfo; 63489857Sobrien htab_t lasttab = NULL, last4tab = NULL; 63589857Sobrien bfd_size_type size, amt; 63689857Sobrien 63789857Sobrien /* Now sort the strings by length, longest first. */ 63889857Sobrien array = NULL; 63989857Sobrien amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); 64089857Sobrien array = (struct sec_merge_hash_entry **) bfd_malloc (amt); 64189857Sobrien if (array == NULL) 64289857Sobrien goto alloc_failure; 64389857Sobrien 64489857Sobrien for (e = sinfo->htab->first, a = array; e; e = e->next) 64589857Sobrien if (e->alignment) 64689857Sobrien *a++ = e; 64789857Sobrien 64889857Sobrien sinfo->htab->size = a - array; 64989857Sobrien 65089857Sobrien qsort (array, (size_t) sinfo->htab->size, 65189857Sobrien sizeof (struct sec_merge_hash_entry *), cmplengthentry); 65289857Sobrien 65389857Sobrien last4tab = htab_create ((size_t) sinfo->htab->size * 4, NULL, last4_eq, NULL); 65489857Sobrien lasttab = htab_create ((size_t) sinfo->htab->size * 4, NULL, last_eq, NULL); 65589857Sobrien if (lasttab == NULL || last4tab == NULL) 65689857Sobrien goto alloc_failure; 65789857Sobrien 65889857Sobrien /* Now insert the strings into hash tables (strings with last 4 characters 65989857Sobrien and strings with last character equal), look for longer strings which 66089857Sobrien we're suffix of. */ 66189857Sobrien for (a = array, end = array + sinfo->htab->size; a < end; a++) 66289857Sobrien { 66389857Sobrien register hashval_t hash; 66489857Sobrien unsigned int c; 66589857Sobrien unsigned int i; 66689857Sobrien const unsigned char *s; 66789857Sobrien PTR *p; 66889857Sobrien 66989857Sobrien e = *a; 67089857Sobrien e->u.entsize = sinfo->htab->entsize; 67189857Sobrien if (e->len <= e->u.entsize) 67289857Sobrien break; 67389857Sobrien if (e->len > 4 * e->u.entsize) 67489857Sobrien { 67589857Sobrien s = e->root.string + e->len - e->u.entsize; 67689857Sobrien hash = 0; 67789857Sobrien for (i = 0; i < 4 * e->u.entsize; i++) 67889857Sobrien { 67989857Sobrien c = *--s; 68089857Sobrien hash += c + (c << 17); 68189857Sobrien hash ^= hash >> 2; 68289857Sobrien } 68389857Sobrien p = htab_find_slot_with_hash (last4tab, e, hash, INSERT); 68489857Sobrien if (p == NULL) 68589857Sobrien goto alloc_failure; 68689857Sobrien if (*p) 68789857Sobrien { 68889857Sobrien struct sec_merge_hash_entry *ent; 68989857Sobrien 69089857Sobrien ent = (struct sec_merge_hash_entry *) *p; 69189857Sobrien e->u.suffix = ent; 69289857Sobrien e->alignment = 0; 69389857Sobrien continue; 69489857Sobrien } 69589857Sobrien else 69689857Sobrien *p = (PTR) e; 69789857Sobrien } 69889857Sobrien s = e->root.string + e->len - e->u.entsize; 69989857Sobrien hash = 0; 70089857Sobrien for (i = 0; i < e->u.entsize; i++) 70189857Sobrien { 70289857Sobrien c = *--s; 70389857Sobrien hash += c + (c << 17); 70489857Sobrien hash ^= hash >> 2; 70589857Sobrien } 70689857Sobrien p = htab_find_slot_with_hash (lasttab, e, hash, INSERT); 70789857Sobrien if (p == NULL) 70889857Sobrien goto alloc_failure; 70989857Sobrien if (*p) 71089857Sobrien { 71189857Sobrien struct sec_merge_hash_entry *ent; 71289857Sobrien 71389857Sobrien ent = (struct sec_merge_hash_entry *) *p; 71489857Sobrien e->u.suffix = ent; 71589857Sobrien e->alignment = 0; 71689857Sobrien } 71789857Sobrien else 71889857Sobrien *p = (PTR) e; 71989857Sobrien } 72089857Sobrien 72189857Sobrienalloc_failure: 72289857Sobrien if (array) 72389857Sobrien free (array); 72489857Sobrien if (lasttab) 72589857Sobrien htab_delete (lasttab); 72689857Sobrien if (last4tab) 72789857Sobrien htab_delete (last4tab); 72889857Sobrien 72989857Sobrien /* Now assign positions to the strings we want to keep. */ 73089857Sobrien size = 0; 73189857Sobrien secinfo = sinfo->htab->first->secinfo; 73289857Sobrien for (e = sinfo->htab->first; e; e = e->next) 73389857Sobrien { 73489857Sobrien if (e->secinfo != secinfo) 73589857Sobrien { 73689857Sobrien secinfo->sec->_cooked_size = size; 73789857Sobrien secinfo = e->secinfo; 73889857Sobrien } 73989857Sobrien if (e->alignment) 74089857Sobrien { 74189857Sobrien if (e->secinfo->first == NULL) 74289857Sobrien { 74389857Sobrien e->secinfo->first = e; 74489857Sobrien size = 0; 74589857Sobrien } 74689857Sobrien size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1); 74789857Sobrien e->u.index = size; 74889857Sobrien size += e->len; 74989857Sobrien } 75089857Sobrien } 75189857Sobrien secinfo->sec->_cooked_size = size; 75289857Sobrien 75389857Sobrien /* And now adjust the rest, removing them from the chain (but not hashtable) 75489857Sobrien at the same time. */ 75589857Sobrien for (a = &sinfo->htab->first, e = *a; e; e = e->next) 75689857Sobrien if (e->alignment) 75789857Sobrien a = &e->next; 75889857Sobrien else 75989857Sobrien { 76089857Sobrien *a = e->next; 76189857Sobrien if (e->len) 76289857Sobrien { 76389857Sobrien e->secinfo = e->u.suffix->secinfo; 76489857Sobrien e->alignment = e->u.suffix->alignment; 76589857Sobrien e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len); 76689857Sobrien } 76789857Sobrien } 76889857Sobrien} 76989857Sobrien 77089857Sobrien/* This function is called once after all SEC_MERGE sections are registered 77189857Sobrien with _bfd_merge_section. */ 77289857Sobrien 77389857Sobrienboolean 77489857Sobrien_bfd_merge_sections (abfd, xsinfo, remove_hook) 77589857Sobrien bfd *abfd ATTRIBUTE_UNUSED; 77689857Sobrien PTR xsinfo; 77789857Sobrien void (*remove_hook) PARAMS((bfd *, asection *)); 77889857Sobrien{ 77989857Sobrien struct sec_merge_info *sinfo; 78089857Sobrien 78189857Sobrien for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) 78289857Sobrien { 78389857Sobrien struct sec_merge_sec_info * secinfo; 78489857Sobrien 78589857Sobrien if (! sinfo->chain) 78689857Sobrien continue; 78789857Sobrien 78889857Sobrien /* Move sinfo->chain to head of the chain, terminate it. */ 78989857Sobrien secinfo = sinfo->chain; 79089857Sobrien sinfo->chain = secinfo->next; 79189857Sobrien secinfo->next = NULL; 79289857Sobrien 79389857Sobrien /* Record the sections into the hash table. */ 79489857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 79589857Sobrien if (secinfo->sec->flags & SEC_EXCLUDE) 79689857Sobrien { 79789857Sobrien *secinfo->psecinfo = NULL; 79889857Sobrien if (remove_hook) 79989857Sobrien (*remove_hook) (abfd, secinfo->sec); 80089857Sobrien } 80189857Sobrien else if (! record_section (sinfo, secinfo)) 80289857Sobrien break; 80389857Sobrien 80489857Sobrien if (secinfo) 80589857Sobrien continue; 80689857Sobrien 80789857Sobrien if (sinfo->htab->strings) 80889857Sobrien merge_strings (sinfo); 80989857Sobrien else 81089857Sobrien { 81189857Sobrien struct sec_merge_hash_entry *e; 81289857Sobrien bfd_size_type size = 0; 81389857Sobrien 81489857Sobrien /* Things are much simpler for non-strings. 81589857Sobrien Just assign them slots in the section. */ 81689857Sobrien secinfo = NULL; 81789857Sobrien for (e = sinfo->htab->first; e; e = e->next) 81889857Sobrien { 81989857Sobrien if (e->secinfo->first == NULL) 82089857Sobrien { 82189857Sobrien if (secinfo) 82289857Sobrien secinfo->sec->_cooked_size = size; 82389857Sobrien e->secinfo->first = e; 82489857Sobrien size = 0; 82589857Sobrien } 82689857Sobrien size = (size + e->alignment - 1) 82789857Sobrien & ~((bfd_vma) e->alignment - 1); 82889857Sobrien e->u.index = size; 82989857Sobrien size += e->len; 83089857Sobrien secinfo = e->secinfo; 83189857Sobrien } 83289857Sobrien secinfo->sec->_cooked_size = size; 83389857Sobrien } 83489857Sobrien 83589857Sobrien /* Finally shrink all input sections which have not made it into 83689857Sobrien the hash table at all. */ 83789857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 83889857Sobrien if (secinfo->first == NULL) 83989857Sobrien { 84089857Sobrien secinfo->sec->_cooked_size = 0; 84189857Sobrien secinfo->sec->flags |= SEC_EXCLUDE; 84289857Sobrien } 84389857Sobrien } 84489857Sobrien 84589857Sobrien return true; 84689857Sobrien} 84789857Sobrien 84889857Sobrien/* Write out the merged section. */ 84989857Sobrien 85089857Sobrienboolean 85189857Sobrien_bfd_write_merged_section (output_bfd, sec, psecinfo) 85289857Sobrien bfd *output_bfd; 85389857Sobrien asection *sec; 85489857Sobrien PTR psecinfo; 85589857Sobrien{ 85689857Sobrien struct sec_merge_sec_info *secinfo; 85789857Sobrien file_ptr pos; 85889857Sobrien 85989857Sobrien secinfo = (struct sec_merge_sec_info *) psecinfo; 86089857Sobrien 86189857Sobrien if (!secinfo->first) 86289857Sobrien return true; 86389857Sobrien 86489857Sobrien pos = sec->output_section->filepos + sec->output_offset; 86589857Sobrien if (bfd_seek (output_bfd, pos, SEEK_SET) != 0) 86689857Sobrien return false; 86789857Sobrien 86889857Sobrien if (! sec_merge_emit (output_bfd, secinfo->first)) 86989857Sobrien return false; 87089857Sobrien 87189857Sobrien return true; 87289857Sobrien} 87389857Sobrien 87489857Sobrien/* Adjust an address in the SEC_MERGE section. Given OFFSET within 87589857Sobrien *PSEC, this returns the new offset in the adjusted SEC_MERGE 87689857Sobrien section and writes the new section back into *PSEC. */ 87789857Sobrien 87889857Sobrienbfd_vma 87989857Sobrien_bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend) 88089857Sobrien bfd *output_bfd ATTRIBUTE_UNUSED; 88189857Sobrien asection **psec; 88289857Sobrien PTR psecinfo; 88389857Sobrien bfd_vma offset, addend; 88489857Sobrien{ 88589857Sobrien struct sec_merge_sec_info *secinfo; 88689857Sobrien struct sec_merge_hash_entry *entry; 88789857Sobrien unsigned char *p; 88889857Sobrien asection *sec = *psec; 88989857Sobrien 89089857Sobrien secinfo = (struct sec_merge_sec_info *) psecinfo; 89189857Sobrien 89289857Sobrien if (offset + addend >= sec->_raw_size) 89389857Sobrien { 89489857Sobrien if (offset + addend > sec->_raw_size) 89589857Sobrien { 89689857Sobrien (*_bfd_error_handler) 89789857Sobrien (_("%s: access beyond end of merged section (%ld + %ld)"), 89889857Sobrien bfd_get_filename (sec->owner), (long) offset, (long) addend); 89989857Sobrien } 90089857Sobrien return (secinfo->first ? sec->_cooked_size : 0); 90189857Sobrien } 90289857Sobrien 90389857Sobrien if (secinfo->htab->strings) 90489857Sobrien { 90589857Sobrien if (sec->entsize == 1) 90689857Sobrien { 90789857Sobrien p = secinfo->contents + offset + addend - 1; 90889857Sobrien while (*p && p >= secinfo->contents) 90989857Sobrien --p; 91089857Sobrien ++p; 91189857Sobrien } 91289857Sobrien else 91389857Sobrien { 91489857Sobrien p = secinfo->contents 91589857Sobrien + ((offset + addend) / sec->entsize) * sec->entsize; 91689857Sobrien p -= sec->entsize; 91789857Sobrien while (p >= secinfo->contents) 91889857Sobrien { 91989857Sobrien unsigned int i; 92089857Sobrien 92189857Sobrien for (i = 0; i < sec->entsize; ++i) 92289857Sobrien if (p[i] != '\0') 92389857Sobrien break; 92489857Sobrien if (i == sec->entsize) 92589857Sobrien break; 92689857Sobrien p -= sec->entsize; 92789857Sobrien } 92889857Sobrien p += sec->entsize; 92989857Sobrien } 93089857Sobrien } 93189857Sobrien else 93289857Sobrien { 93389857Sobrien p = secinfo->contents 93489857Sobrien + ((offset + addend) / sec->entsize) * sec->entsize; 93589857Sobrien } 93689857Sobrien entry = sec_merge_hash_lookup (secinfo->htab, p, 0, false); 93789857Sobrien if (!entry) 93889857Sobrien { 93989857Sobrien if (! secinfo->htab->strings) 94089857Sobrien abort (); 94189857Sobrien /* This should only happen if somebody points into the padding 94289857Sobrien after a NUL character but before next entity. */ 94389857Sobrien if (*p) 94489857Sobrien abort (); 94589857Sobrien if (! secinfo->htab->first) 94689857Sobrien abort (); 94789857Sobrien entry = secinfo->htab->first; 94889857Sobrien p = secinfo->contents 94989857Sobrien + ((offset + addend) / sec->entsize + 1) * sec->entsize 95089857Sobrien - entry->len; 95189857Sobrien } 95289857Sobrien 95389857Sobrien *psec = entry->secinfo->sec; 95489857Sobrien return entry->u.index + (secinfo->contents + offset - p); 95589857Sobrien} 956