merge.c revision 218822
150724Scg/* SEC_MERGE support. 250724Scg Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007 350724Scg Free Software Foundation, Inc. 450724Scg Written by Jakub Jelinek <jakub@redhat.com>. 550724Scg 650724Scg This file is part of BFD, the Binary File Descriptor library. 750724Scg 850724Scg This program is free software; you can redistribute it and/or modify 950724Scg it under the terms of the GNU General Public License as published by 1050724Scg the Free Software Foundation; either version 2 of the License, or 1150724Scg (at your option) any later version. 1250724Scg 1350724Scg This program is distributed in the hope that it will be useful, 1450724Scg but WITHOUT ANY WARRANTY; without even the implied warranty of 1550724Scg MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1650724Scg GNU General Public License for more details. 1750724Scg 1850724Scg You should have received a copy of the GNU General Public License 1950724Scg along with this program; if not, write to the Free Software 2050724Scg Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA. */ 2150724Scg 2250724Scg/* This file contains support for merging duplicate entities within sections, 2350724Scg as used in ELF SHF_MERGE. */ 2450724Scg 2550724Scg#include "sysdep.h" 2650724Scg#include "bfd.h" 2750724Scg#include "libbfd.h" 2853465Scg#include "hashtab.h" 2977269Scg#include "libiberty.h" 3065207Scg 3150724Scgstruct sec_merge_sec_info; 3282180Scg 3382180Scg/* An entry in the section merge hash table. */ 3482180Scg 3582180Scgstruct sec_merge_hash_entry 3682180Scg{ 3782180Scg struct bfd_hash_entry root; 3882180Scg /* Length of this entry. This includes the zero terminator. */ 3982180Scg unsigned int len; 4082180Scg /* Start of this string needs to be aligned to 4182180Scg alignment octets (not 1 << align). */ 4282180Scg unsigned int alignment; 4382180Scg union 4483614Scg { 4582180Scg /* Index within the merged section. */ 4682180Scg bfd_size_type index; 4783614Scg /* Entry this is a suffix of (if alignment is 0). */ 4882180Scg struct sec_merge_hash_entry *suffix; 4982180Scg } u; 5082180Scg /* Which section is it in. */ 5182180Scg struct sec_merge_sec_info *secinfo; 5282180Scg /* Next entity in the hash table. */ 53107285Scg struct sec_merge_hash_entry *next; 5482180Scg}; 5582180Scg 5678362Scg/* The section merge hash table. */ 5750724Scg 5889834Scgstruct sec_merge_hash 5989834Scg{ 6073127Scg struct bfd_hash_table table; 6178362Scg /* Next available index. */ 6277900Speter bfd_size_type size; 6373127Scg /* First entity in the SEC_MERGE sections of this type. */ 6479141Scg struct sec_merge_hash_entry *first; 6582180Scg /* Last entity in the SEC_MERGE sections of this type. */ 6682180Scg struct sec_merge_hash_entry *last; 6750724Scg /* Entity size. */ 6873127Scg unsigned int entsize; 6973127Scg /* Are entries fixed size or zero terminated strings? */ 7082180Scg bfd_boolean strings; 7182180Scg}; 7282180Scg 7382180Scgstruct sec_merge_info 7482180Scg{ 7582180Scg /* Chain of sec_merge_infos. */ 7682180Scg struct sec_merge_info *next; 7782180Scg /* Chain of sec_merge_sec_infos. */ 7882180Scg struct sec_merge_sec_info *chain; 7982180Scg /* A hash table used to hold section content. */ 8082180Scg struct sec_merge_hash *htab; 8182180Scg}; 8282180Scg 8382180Scgstruct sec_merge_sec_info 8482180Scg{ 8582180Scg /* Chain of sec_merge_sec_infos. */ 8682180Scg struct sec_merge_sec_info *next; 8782180Scg /* The corresponding section. */ 8873131Scg asection *sec; 8993814Sjhb /* Pointer to merge_info pointing to us. */ 9073131Scg void **psecinfo; 9173131Scg /* A hash table used to hold section content. */ 9273131Scg struct sec_merge_hash *htab; 9373131Scg /* First string in this section. */ 94111119Simp struct sec_merge_hash_entry *first_str; 9573131Scg /* Original section content. */ 9673131Scg unsigned char contents[1]; 9793814Sjhb}; 9873131Scg 9973131Scg 10073757Scg/* Routine to create an entry in a section merge hashtab. */ 10173131Scg 10273131Scgstatic struct bfd_hash_entry * 10373131Scgsec_merge_hash_newfunc (struct bfd_hash_entry *entry, 10473131Scg struct bfd_hash_table *table, const char *string) 10573131Scg{ 10673131Scg /* Allocate the structure if it has not already been allocated by a 10773131Scg subclass. */ 10873131Scg if (entry == NULL) 10973131Scg entry = bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)); 110107237Scg if (entry == NULL) 11173131Scg return NULL; 11273131Scg 11373131Scg /* Call the allocation method of the superclass. */ 11473131Scg entry = bfd_hash_newfunc (entry, table, string); 11573131Scg 11673131Scg if (entry != NULL) 11773131Scg { 11873131Scg /* Initialize the local fields. */ 11973131Scg struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry; 12078670Scg 12173131Scg ret->u.suffix = NULL; 12273131Scg ret->alignment = 0; 12373131Scg ret->secinfo = NULL; 12473131Scg ret->next = NULL; 12578670Scg } 12673131Scg 127107237Scg return entry; 12873131Scg} 12973131Scg 13073131Scg/* Look up an entry in a section merge hash table. */ 13173131Scg 13273131Scgstatic struct sec_merge_hash_entry * 13373131Scgsec_merge_hash_lookup (struct sec_merge_hash *table, const char *string, 13473131Scg unsigned int alignment, bfd_boolean create) 13573131Scg{ 13673131Scg register const unsigned char *s; 13773131Scg register unsigned long hash; 13873131Scg register unsigned int c; 13973131Scg struct sec_merge_hash_entry *hashp; 14073131Scg unsigned int len, i; 14173131Scg unsigned int index; 14273131Scg 14373131Scg hash = 0; 14473131Scg len = 0; 14573131Scg s = (const unsigned char *) string; 14673131Scg if (table->strings) 147107237Scg { 14873131Scg if (table->entsize == 1) 14973131Scg { 15073131Scg while ((c = *s++) != '\0') 15173131Scg { 15273131Scg hash += c + (c << 17); 15378366Speter hash ^= hash >> 2; 15473131Scg ++len; 15578366Speter } 15673131Scg hash += len + (len << 17); 15773131Scg } 15873131Scg else 15973131Scg { 16082180Scg for (;;) 16182180Scg { 16282180Scg for (i = 0; i < table->entsize; ++i) 16382180Scg if (s[i] != '\0') 16482180Scg break; 16582180Scg if (i == table->entsize) 16682180Scg break; 16782180Scg for (i = 0; i < table->entsize; ++i) 16882180Scg { 16982180Scg c = *s++; 17082180Scg hash += c + (c << 17); 17182180Scg hash ^= hash >> 2; 17282180Scg } 17382180Scg ++len; 17482180Scg } 17582180Scg hash += len + (len << 17); 17682180Scg len *= table->entsize; 17782180Scg } 17878214Scg hash ^= hash >> 2; 17977269Scg len += table->entsize; 18083089Scg } 18177269Scg else 18277269Scg { 18377269Scg for (i = 0; i < table->entsize; ++i) 18478895Scg { 18577269Scg c = *s++; 18678214Scg hash += c + (c << 17); 18778895Scg hash ^= hash >> 2; 18878895Scg } 18977269Scg len = table->entsize; 19077269Scg } 19177882Scg 19277269Scg index = hash % table->table.size; 19383089Scg for (hashp = (struct sec_merge_hash_entry *) table->table.table[index]; 19483089Scg hashp != NULL; 19583089Scg hashp = (struct sec_merge_hash_entry *) hashp->root.next) 19683089Scg { 19783089Scg if (hashp->root.hash == hash 19877269Scg && len == hashp->len 19977882Scg && memcmp (hashp->root.string, string, len) == 0) 20077269Scg { 20178895Scg /* If the string we found does not have at least the required 20278895Scg alignment, we need to insert another copy. */ 20378895Scg if (hashp->alignment < alignment) 20482180Scg { 20578895Scg if (create) 20678895Scg { 20778895Scg /* Mark the less aligned copy as deleted. */ 20878895Scg hashp->len = 0; 20978895Scg hashp->alignment = 0; 21078895Scg } 21183089Scg break; 21278895Scg } 21378895Scg return hashp; 21478895Scg } 21578895Scg } 21678895Scg 21778895Scg if (! create) 21878895Scg return NULL; 21977269Scg 22077269Scg hashp = ((struct sec_merge_hash_entry *) 22177269Scg sec_merge_hash_newfunc (NULL, &table->table, string)); 22278214Scg if (hashp == NULL) 22377269Scg return NULL; 22478214Scg hashp->root.string = string; 22577269Scg hashp->root.hash = hash; 22678214Scg hashp->len = len; 22777269Scg hashp->alignment = alignment; 22878214Scg hashp->root.next = table->table.table[index]; 22977882Scg table->table.table[index] = (struct bfd_hash_entry *) hashp; 23077269Scg 23177269Scg return hashp; 23277269Scg} 23377269Scg 23477269Scg/* Create a new hash table. */ 23577269Scg 23677882Scgstatic struct sec_merge_hash * 23777882Scgsec_merge_init (unsigned int entsize, bfd_boolean strings) 23878214Scg{ 23977269Scg struct sec_merge_hash *table; 24077882Scg 24177882Scg table = bfd_malloc (sizeof (struct sec_merge_hash)); 24277269Scg if (table == NULL) 24377269Scg return NULL; 24482180Scg 24582180Scg if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc, 24682180Scg sizeof (struct sec_merge_hash_entry), 16699)) 24782180Scg { 24882180Scg free (table); 24982180Scg return NULL; 25082180Scg } 25182180Scg 25282180Scg table->size = 0; 25382180Scg table->first = NULL; 25482180Scg table->last = NULL; 25582180Scg table->entsize = entsize; 25682180Scg table->strings = strings; 25782180Scg 25882180Scg return table; 25982180Scg} 26082180Scg 26182180Scg/* Get the index of an entity in a hash table, adding it if it is not 26282180Scg already present. */ 26382180Scg 26482180Scgstatic struct sec_merge_hash_entry * 26582180Scgsec_merge_add (struct sec_merge_hash *tab, const char *str, 26682180Scg unsigned int alignment, struct sec_merge_sec_info *secinfo) 26782180Scg{ 26882180Scg register struct sec_merge_hash_entry *entry; 26982180Scg 27082180Scg entry = sec_merge_hash_lookup (tab, str, alignment, TRUE); 27182180Scg if (entry == NULL) 27282180Scg return NULL; 27382180Scg 27482180Scg if (entry->secinfo == NULL) 27582180Scg { 27682180Scg tab->size++; 27782180Scg entry->secinfo = secinfo; 27882180Scg if (tab->first == NULL) 27982180Scg tab->first = entry; 28082180Scg else 28182180Scg tab->last->next = entry; 28282180Scg tab->last = entry; 28396928Speter } 28482180Scg 28582180Scg return entry; 28682180Scg} 28782180Scg 28882180Scgstatic bfd_boolean 28982180Scgsec_merge_emit (bfd *abfd, struct sec_merge_hash_entry *entry) 29073127Scg{ 29165340Scg struct sec_merge_sec_info *secinfo = entry->secinfo; 29278853Scg asection *sec = secinfo->sec; 29365340Scg char *pad = NULL; 29478214Scg bfd_size_type off = 0; 29565340Scg int alignment_power = sec->output_section->alignment_power; 29665340Scg 29765340Scg if (alignment_power) 29865340Scg { 29965340Scg pad = bfd_zmalloc ((bfd_size_type) 1 << alignment_power); 30078396Scg if (pad == NULL) 30178214Scg return FALSE; 30278214Scg } 30378395Scg 30478214Scg for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next) 30565340Scg { 30665340Scg const char *str; 30765340Scg bfd_size_type len; 30865340Scg 30970617Sjhb len = -off & (entry->alignment - 1); 31078853Scg if (len != 0) 31173127Scg { 31265340Scg if (bfd_bwrite (pad, len, abfd) != len) 31378853Scg goto err; 31482180Scg off += len; 31578853Scg } 31682180Scg 31782180Scg str = entry->root.string; 31878853Scg len = entry->len; 31982180Scg 32078853Scg if (bfd_bwrite (str, len, abfd) != len) 32178853Scg goto err; 32278853Scg 32378853Scg off += len; 32482180Scg } 32582180Scg 32682180Scg /* Trailing alignment needed? */ 32782180Scg off = sec->size - off; 32882180Scg if (off != 0 32982180Scg && bfd_bwrite (pad, off, abfd) != off) 33082180Scg goto err; 33182180Scg 33282180Scg if (pad != NULL) 33378853Scg free (pad); 33478853Scg return TRUE; 33578853Scg 33682180Scg err: 33782180Scg if (pad != NULL) 33878853Scg free (pad); 33977269Scg return FALSE; 34077269Scg} 34150724Scg 34277269Scg/* Register a SEC_MERGE section as a candidate for merging. 34365340Scg This function is called for all non-dynamic SEC_MERGE input sections. */ 34483614Scg 34550724Scgbfd_boolean 34677269Scg_bfd_add_merge_section (bfd *abfd, void **psinfo, asection *sec, 34777269Scg void **psecinfo) 34877269Scg{ 34983614Scg struct sec_merge_info *sinfo; 35077269Scg struct sec_merge_sec_info *secinfo; 35183614Scg unsigned int align; 35277269Scg bfd_size_type amt; 35377269Scg 35483614Scg if ((abfd->flags & DYNAMIC) != 0 35577269Scg || (sec->flags & SEC_MERGE) == 0) 35683614Scg abort (); 35777269Scg 35877269Scg if (sec->size == 0 35977269Scg || (sec->flags & SEC_EXCLUDE) != 0 36083614Scg || sec->entsize == 0) 36177269Scg return TRUE; 36283614Scg 36377269Scg if ((sec->flags & SEC_RELOC) != 0) 36477269Scg { 36577269Scg /* We aren't prepared to handle relocations in merged sections. */ 36665340Scg return TRUE; 367111119Simp } 36877269Scg 36977269Scg align = sec->alignment_power; 37077269Scg if ((sec->entsize < (unsigned) 1 << align 371111119Simp && ((sec->entsize & (sec->entsize - 1)) 37277269Scg || !(sec->flags & SEC_STRINGS))) 37377269Scg || (sec->entsize > (unsigned) 1 << align 37483614Scg && (sec->entsize & (((unsigned) 1 << align) - 1)))) 37577269Scg { 37661344Scg /* Sanity check. If string character size is smaller than 37777269Scg alignment, then we require character size to be a power 378107237Scg of 2, otherwise character size must be integer multiple 37983614Scg of alignment. For non-string constants, alignment must 380107237Scg be smaller than or equal to entity size and entity size 38183614Scg must be integer multiple of alignment. */ 38277269Scg return TRUE; 38377269Scg } 38477269Scg 38589774Sscottl for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next) 386107237Scg if ((secinfo = sinfo->chain) 38777269Scg && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS)) 38870134Scg && secinfo->sec->entsize == sec->entsize 38970134Scg && secinfo->sec->alignment_power == sec->alignment_power 39083614Scg && secinfo->sec->output_section == sec->output_section) 39177269Scg break; 39277269Scg 393107237Scg if (sinfo == NULL) 39483614Scg { 395107237Scg /* Initialize the information we need to keep track of. */ 39683614Scg sinfo = bfd_alloc (abfd, sizeof (struct sec_merge_info)); 39777269Scg if (sinfo == NULL) 39855483Scg goto error_return; 39977269Scg sinfo->next = (struct sec_merge_info *) *psinfo; 40077269Scg sinfo->chain = NULL; 40177269Scg *psinfo = sinfo; 40277269Scg sinfo->htab = sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS)); 40377269Scg if (sinfo->htab == NULL) 40477269Scg goto error_return; 40577269Scg } 40683614Scg 40777269Scg /* Read the section from abfd. */ 40877269Scg 40983614Scg amt = sizeof (struct sec_merge_sec_info) + sec->size - 1; 41077269Scg *psecinfo = bfd_alloc (abfd, amt); 41177269Scg if (*psecinfo == NULL) 41283614Scg goto error_return; 41377269Scg 41477269Scg secinfo = (struct sec_merge_sec_info *) *psecinfo; 41577269Scg if (sinfo->chain) 41677269Scg { 41777269Scg secinfo->next = sinfo->chain->next; 41877269Scg sinfo->chain->next = secinfo; 41977269Scg } 42077269Scg else 42177269Scg secinfo->next = secinfo; 42277269Scg sinfo->chain = secinfo; 42378895Scg secinfo->sec = sec; 42477269Scg secinfo->psecinfo = psecinfo; 42582180Scg secinfo->htab = sinfo->htab; 42677269Scg secinfo->first_str = NULL; 427107237Scg 42877269Scg sec->rawsize = sec->size; 429111119Simp if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents, 43077269Scg 0, sec->size)) 43177269Scg goto error_return; 43277269Scg 43377269Scg return TRUE; 434100478Sorion 43577269Scg error_return: 43682180Scg *psecinfo = NULL; 43782180Scg return FALSE; 43882180Scg} 43982180Scg 44082180Scg/* Record one section into the hash table. */ 44182180Scgstatic bfd_boolean 44282180Scgrecord_section (struct sec_merge_info *sinfo, 44382180Scg struct sec_merge_sec_info *secinfo) 44482180Scg{ 445107237Scg asection *sec = secinfo->sec; 446107237Scg struct sec_merge_hash_entry *entry; 447107237Scg bfd_boolean nul; 44877269Scg unsigned char *p, *end; 44983089Scg bfd_vma mask, eltalign; 450107237Scg unsigned int align, i; 45183089Scg 45283089Scg align = sec->alignment_power; 45383089Scg end = secinfo->contents + sec->size; 45477269Scg nul = FALSE; 45550724Scg mask = ((bfd_vma) 1 << align) - 1; 45650724Scg if (sec->flags & SEC_STRINGS) 45750724Scg { 45877269Scg for (p = secinfo->contents; p < end; ) 45978895Scg { 46065340Scg eltalign = p - secinfo->contents; 46177269Scg eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1; 46277269Scg if (!eltalign || eltalign > mask) 46365340Scg eltalign = mask + 1; 46477882Scg entry = sec_merge_add (sinfo->htab, (char *) p, (unsigned) eltalign, 46577269Scg secinfo); 46677269Scg if (! entry) 46777269Scg goto error_return; 46865340Scg p += entry->len; 46977882Scg if (sec->entsize == 1) 47077269Scg { 47177269Scg while (p < end && *p == 0) 47277269Scg { 47383089Scg if (!nul && !((p - secinfo->contents) & mask)) 47478895Scg { 47583089Scg nul = TRUE; 47683614Scg entry = sec_merge_add (sinfo->htab, "", 47783089Scg (unsigned) mask + 1, secinfo); 478107237Scg if (! entry) 479107237Scg goto error_return; 480107237Scg } 481107237Scg p++; 482107237Scg } 483107237Scg } 484107237Scg else 485107237Scg { 48677882Scg while (p < end) 487107237Scg { 48877269Scg for (i = 0; i < sec->entsize; i++) 48965340Scg if (p[i] != '\0') 49065340Scg break; 49165340Scg if (i != sec->entsize) 49250724Scg break; 49377269Scg if (!nul && !((p - secinfo->contents) & mask)) 49477269Scg { 49577269Scg nul = TRUE; 49682180Scg entry = sec_merge_add (sinfo->htab, (char *) p, 49782180Scg (unsigned) mask + 1, secinfo); 49877269Scg if (! entry) 49977269Scg goto error_return; 50077269Scg } 50177269Scg p += sec->entsize; 50277269Scg } 50377269Scg } 50478853Scg } 50578895Scg } 50677269Scg else 50777269Scg { 508107237Scg for (p = secinfo->contents; p < end; p += sec->entsize) 50977269Scg { 51078853Scg entry = sec_merge_add (sinfo->htab, (char *) p, 1, secinfo); 51177269Scg if (! entry) 51277269Scg goto error_return; 513100576Skan } 514100576Skan } 51578853Scg 51682180Scg return TRUE; 51778853Scg 51882180Scgerror_return: 51982180Scg for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 52078853Scg *secinfo->psecinfo = NULL; 52178853Scg return FALSE; 52278853Scg} 52377269Scg 52477269Scgstatic int 52577269Scgstrrevcmp (const void *a, const void *b) 52677269Scg{ 52777269Scg struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; 52877269Scg struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; 52977269Scg unsigned int lenA = A->len; 53077269Scg unsigned int lenB = B->len; 531106420Scognet const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 532106420Scognet const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 53377269Scg int l = lenA < lenB ? lenA : lenB; 53477882Scg 53577269Scg while (l) 53677882Scg { 537106420Scognet if (*s != *t) 53877269Scg return (int) *s - (int) *t; 539109236Scognet s--; 540106420Scognet t--; 541106420Scognet l--; 542106420Scognet } 54377269Scg return lenA - lenB; 54477269Scg} 54577269Scg 54650724Scg/* Like strrevcmp, but for the case where all strings have the same 54750724Scg alignment > entsize. */ 54874763Scg 54977882Scgstatic int 55077882Scgstrrevcmp_align (const void *a, const void *b) 55150724Scg{ 55277882Scg struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; 55350724Scg struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; 55450724Scg unsigned int lenA = A->len; 55550724Scg unsigned int lenB = B->len; 55650724Scg const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 55750724Scg const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 55850724Scg int l = lenA < lenB ? lenA : lenB; 55974763Scg int tail_align = (lenA & (A->alignment - 1)) - (lenB & (A->alignment - 1)); 56077882Scg 56150724Scg if (tail_align != 0) 56250724Scg return tail_align; 56350724Scg 56450724Scg while (l) 56550724Scg { 56650724Scg if (*s != *t) 56774763Scg return (int) *s - (int) *t; 56878362Scg s--; 56950724Scg t--; 57050724Scg l--; 57150724Scg } 57258384Scg return lenA - lenB; 57358384Scg} 57458384Scg 57574763Scgstatic inline int 57677882Scgis_suffix (const struct sec_merge_hash_entry *A, 57758384Scg const struct sec_merge_hash_entry *B) 57858384Scg{ 57958384Scg if (A->len <= B->len) 58083614Scg /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 58183614Scg not to be equal by the hash table. */ 58283614Scg return 0; 58383614Scg 58489690Scg return memcmp (A->root.string + (A->len - B->len), 58583614Scg B->root.string, B->len) == 0; 58683614Scg} 58789690Scg 58889690Scg/* This is a helper function for _bfd_merge_sections. It attempts to 58983614Scg merge strings matching suffixes of longer strings. */ 59089690Scgstatic void 59189690Scgmerge_strings (struct sec_merge_info *sinfo) 59289690Scg{ 59389690Scg struct sec_merge_hash_entry **array, **a, *e; 59489690Scg struct sec_merge_sec_info *secinfo; 59589690Scg bfd_size_type size, amt; 59689690Scg unsigned int alignment = 0; 59789690Scg 59889690Scg /* Now sort the strings */ 59989690Scg amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); 60089690Scg array = bfd_malloc (amt); 60189690Scg if (array == NULL) 60283614Scg goto alloc_failure; 60389690Scg 60489690Scg for (e = sinfo->htab->first, a = array; e; e = e->next) 60583614Scg if (e->alignment) 60683614Scg { 60783614Scg *a++ = e; 60883614Scg /* Adjust the length to not include the zero terminator. */ 60983614Scg e->len -= sinfo->htab->entsize; 61050724Scg if (alignment != e->alignment) 61150724Scg { 61250724Scg if (alignment == 0) 61374763Scg alignment = e->alignment; 61450724Scg else 61589834Scg alignment = (unsigned) -1; 61689834Scg } 61789834Scg } 61889834Scg 61989834Scg sinfo->htab->size = a - array; 62089834Scg if (sinfo->htab->size != 0) 62193814Sjhb { 62277269Scg qsort (array, (size_t) sinfo->htab->size, 62378853Scg sizeof (struct sec_merge_hash_entry *), 62461886Scg (alignment != (unsigned) -1 && alignment > sinfo->htab->entsize 62550724Scg ? strrevcmp_align : strrevcmp)); 62678895Scg 62783089Scg /* Loop over the sorted array and merge suffixes */ 62883614Scg e = *--a; 62978895Scg e->len += sinfo->htab->entsize; 63078362Scg while (--a >= array) 63150724Scg { 63278362Scg struct sec_merge_hash_entry *cmp = *a; 63378214Scg 63478362Scg cmp->len += sinfo->htab->entsize; 63578214Scg if (e->alignment >= cmp->alignment 63678214Scg && !((e->len - cmp->len) & (cmp->alignment - 1)) 63755494Scg && is_suffix (e, cmp)) 63873127Scg { 63970680Sjhb cmp->u.suffix = e; 64070680Sjhb cmp->alignment = 0; 64170943Sjhb } 64270680Sjhb else 64370943Sjhb e = cmp; 64470680Sjhb } 64570680Sjhb } 64670680Sjhb 64783614Scgalloc_failure: 64883614Scg if (array) 64973127Scg free (array); 65078214Scg 65182180Scg /* Now assign positions to the strings we want to keep. */ 65278853Scg size = 0; 65378853Scg secinfo = sinfo->htab->first->secinfo; 65478853Scg for (e = sinfo->htab->first; e; e = e->next) 65582180Scg { 65650724Scg if (e->secinfo != secinfo) 65750724Scg { 65877882Scg secinfo->sec->size = size; 65950724Scg secinfo = e->secinfo; 66050724Scg } 66150724Scg if (e->alignment) 66265340Scg { 66365340Scg if (e->secinfo->first_str == NULL) 66465207Scg { 66574763Scg e->secinfo->first_str = e; 66677269Scg size = 0; 66783614Scg } 66865207Scg size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1); 66977882Scg e->u.index = size; 67078362Scg size += e->len; 67183476Sgreid } 67278362Scg } 67378362Scg secinfo->sec->size = size; 67478362Scg if (secinfo->sec->alignment_power != 0) 67583476Sgreid { 67683476Sgreid bfd_size_type align = (bfd_size_type) 1 << secinfo->sec->alignment_power; 67783476Sgreid secinfo->sec->size = (secinfo->sec->size + align - 1) & -align; 67883476Sgreid } 67983476Sgreid 68077269Scg /* And now adjust the rest, removing them from the chain (but not hashtable) 68183614Scg at the same time. */ 68283614Scg for (a = &sinfo->htab->first, e = *a; e; e = e->next) 68395684Scg if (e->alignment) 68477882Scg a = &e->next; 68577269Scg else 68677269Scg { 68765487Scg *a = e->next; 68878362Scg if (e->len) 68983476Sgreid { 69077882Scg e->secinfo = e->u.suffix->secinfo; 69165487Scg e->alignment = e->u.suffix->alignment; 69265487Scg e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len); 69365207Scg } 69474763Scg } 69574763Scg} 69674763Scg 69774763Scg/* This function is called once after all SEC_MERGE sections are registered 69878395Scg with _bfd_merge_section. */ 69977269Scg 70065207Scgbfd_boolean 70174763Scg_bfd_merge_sections (bfd *abfd ATTRIBUTE_UNUSED, 70274763Scg struct bfd_link_info *info ATTRIBUTE_UNUSED, 70373127Scg void *xsinfo, 704102374Snsayer void (*remove_hook) (bfd *, asection *)) 70577882Scg{ 70665340Scg struct sec_merge_info *sinfo; 70765207Scg 70865207Scg for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) 70982180Scg { 71082180Scg struct sec_merge_sec_info * secinfo; 71182180Scg 71282180Scg if (! sinfo->chain) 71382180Scg continue; 71482180Scg 71582180Scg /* Move sinfo->chain to head of the chain, terminate it. */ 71682180Scg secinfo = sinfo->chain; 71782180Scg sinfo->chain = secinfo->next; 71882180Scg secinfo->next = NULL; 71982180Scg 72082180Scg /* Record the sections into the hash table. */ 72182180Scg for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 72282180Scg if (secinfo->sec->flags & SEC_EXCLUDE) 72382180Scg { 72482180Scg *secinfo->psecinfo = NULL; 72582180Scg if (remove_hook) 72682180Scg (*remove_hook) (abfd, secinfo->sec); 72782180Scg } 72882180Scg else if (! record_section (sinfo, secinfo)) 72982180Scg break; 73082180Scg 73182180Scg if (secinfo) 73282180Scg continue; 73382180Scg 73482180Scg if (sinfo->htab->first == NULL) 73582180Scg continue; 73682180Scg 73782180Scg if (sinfo->htab->strings) 73882180Scg merge_strings (sinfo); 73982180Scg else 74083614Scg { 74182180Scg struct sec_merge_hash_entry *e; 74282180Scg bfd_size_type size = 0; 74382180Scg 74482180Scg /* Things are much simpler for non-strings. 74582180Scg Just assign them slots in the section. */ 74682180Scg secinfo = NULL; 74782180Scg for (e = sinfo->htab->first; e; e = e->next) 74882180Scg { 74982180Scg if (e->secinfo->first_str == NULL) 75082180Scg { 75182180Scg if (secinfo) 75282479Scg secinfo->sec->size = size; 75382479Scg e->secinfo->first_str = e; 75482479Scg size = 0; 75589691Scg } 75689691Scg size = (size + e->alignment - 1) 75789691Scg & ~((bfd_vma) e->alignment - 1); 75889691Scg e->u.index = size; 75989691Scg size += e->len; 76089691Scg secinfo = e->secinfo; 76189691Scg } 76282180Scg secinfo->sec->size = size; 76382180Scg } 76482180Scg 76589691Scg /* Finally remove all input sections which have not made it into 76682492Scg the hash table at all. */ 76782479Scg for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 76882479Scg if (secinfo->first_str == NULL) 76982479Scg secinfo->sec->flags |= SEC_EXCLUDE | SEC_KEEP; 77082479Scg } 77182479Scg 77282492Scg return TRUE; 77382492Scg} 77482479Scg 77582479Scg/* Write out the merged section. */ 77689691Scg 77789691Scgbfd_boolean 77889691Scg_bfd_write_merged_section (bfd *output_bfd, asection *sec, void *psecinfo) 77982180Scg{ 78089691Scg struct sec_merge_sec_info *secinfo; 78189691Scg file_ptr pos; 78289691Scg 78382180Scg secinfo = (struct sec_merge_sec_info *) psecinfo; 78482180Scg 78589691Scg if (secinfo->first_str == NULL) 78682180Scg return TRUE; 78789691Scg 78882180Scg pos = sec->output_section->filepos + sec->output_offset; 78989691Scg if (bfd_seek (output_bfd, pos, SEEK_SET) != 0) 79089691Scg return FALSE; 79189691Scg 79282180Scg if (! sec_merge_emit (output_bfd, secinfo->first_str)) 79389691Scg return FALSE; 79482180Scg 79582180Scg return TRUE; 79682180Scg} 79796928Speter 79882180Scg/* Adjust an address in the SEC_MERGE section. Given OFFSET within 79982180Scg *PSEC, this returns the new offset in the adjusted SEC_MERGE 80082180Scg section and writes the new section back into *PSEC. */ 80182180Scg 80282180Scgbfd_vma 80382180Scg_bfd_merged_section_offset (bfd *output_bfd ATTRIBUTE_UNUSED, asection **psec, 80482180Scg void *psecinfo, bfd_vma offset) 80582180Scg{ 80682180Scg struct sec_merge_sec_info *secinfo; 80782180Scg struct sec_merge_hash_entry *entry; 80882180Scg unsigned char *p; 80982180Scg asection *sec = *psec; 81082180Scg 81182180Scg secinfo = (struct sec_merge_sec_info *) psecinfo; 812100654Sgreen 81382180Scg if (offset >= sec->rawsize) 81482180Scg { 81582180Scg if (offset > sec->rawsize) 81682180Scg { 81782180Scg (*_bfd_error_handler) 81882180Scg (_("%s: access beyond end of merged section (%ld)"), 81982180Scg bfd_get_filename (sec->owner), (long) offset); 82082180Scg } 82182180Scg return secinfo->first_str ? sec->size : 0; 82282180Scg } 82382180Scg 82482180Scg if (secinfo->htab->strings) 825100654Sgreen { 82682180Scg if (sec->entsize == 1) 827100654Sgreen { 828100654Sgreen p = secinfo->contents + offset - 1; 829100654Sgreen while (p >= secinfo->contents && *p) 830100654Sgreen --p; 831100654Sgreen ++p; 832100654Sgreen } 833100654Sgreen else 834100654Sgreen { 835100654Sgreen p = secinfo->contents + (offset / sec->entsize) * sec->entsize; 836100654Sgreen p -= sec->entsize; 837100654Sgreen while (p >= secinfo->contents) 83882180Scg { 83982180Scg unsigned int i; 84082180Scg 84182180Scg for (i = 0; i < sec->entsize; ++i) 84282180Scg if (p[i] != '\0') 84382180Scg break; 84482180Scg if (i == sec->entsize) 84582180Scg break; 84682180Scg p -= sec->entsize; 84782180Scg } 84882180Scg p += sec->entsize; 84982180Scg } 85096928Speter } 85182180Scg else 85282180Scg { 85396928Speter p = secinfo->contents + (offset / sec->entsize) * sec->entsize; 85482180Scg } 85582180Scg entry = sec_merge_hash_lookup (secinfo->htab, (char *) p, 0, FALSE); 85696928Speter if (!entry) 85782180Scg { 85882180Scg if (! secinfo->htab->strings) 85982180Scg abort (); 86082180Scg /* This should only happen if somebody points into the padding 86182180Scg after a NUL character but before next entity. */ 86282180Scg if (*p) 86382180Scg abort (); 86482180Scg if (! secinfo->htab->first) 86582180Scg abort (); 86682180Scg entry = secinfo->htab->first; 86782180Scg p = (secinfo->contents + (offset / sec->entsize + 1) * sec->entsize 86882180Scg - entry->len); 86982180Scg } 87082180Scg 87182180Scg *psec = entry->secinfo->sec; 87282180Scg return entry->u.index + (secinfo->contents + offset - p); 87382180Scg} 87482180Scg