189857Sobrien/* SEC_MERGE support. 2218822Sdim Copyright 2001, 2002, 2003, 2004, 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 2289857Sobrien/* This file contains support for merging duplicate entities within sections, 2389857Sobrien as used in ELF SHF_MERGE. */ 2489857Sobrien 25218822Sdim#include "sysdep.h" 2689857Sobrien#include "bfd.h" 2789857Sobrien#include "libbfd.h" 2889857Sobrien#include "hashtab.h" 29104834Sobrien#include "libiberty.h" 3089857Sobrien 3189857Sobrienstruct sec_merge_sec_info; 3289857Sobrien 3389857Sobrien/* An entry in the section merge hash table. */ 3489857Sobrien 3589857Sobrienstruct sec_merge_hash_entry 3689857Sobrien{ 3789857Sobrien struct bfd_hash_entry root; 38130561Sobrien /* Length of this entry. This includes the zero terminator. */ 3989857Sobrien unsigned int len; 4089857Sobrien /* Start of this string needs to be aligned to 4189857Sobrien alignment octets (not 1 << align). */ 4289857Sobrien unsigned int alignment; 43104834Sobrien union 44104834Sobrien { 4589857Sobrien /* Index within the merged section. */ 4689857Sobrien bfd_size_type index; 4789857Sobrien /* Entry this is a suffix of (if alignment is 0). */ 4889857Sobrien struct sec_merge_hash_entry *suffix; 4989857Sobrien } u; 5089857Sobrien /* Which section is it in. */ 5189857Sobrien struct sec_merge_sec_info *secinfo; 5289857Sobrien /* Next entity in the hash table. */ 5389857Sobrien struct sec_merge_hash_entry *next; 5489857Sobrien}; 5589857Sobrien 5689857Sobrien/* The section merge hash table. */ 5789857Sobrien 5889857Sobrienstruct sec_merge_hash 5989857Sobrien{ 6089857Sobrien struct bfd_hash_table table; 6189857Sobrien /* Next available index. */ 6289857Sobrien bfd_size_type size; 6389857Sobrien /* First entity in the SEC_MERGE sections of this type. */ 6489857Sobrien struct sec_merge_hash_entry *first; 6589857Sobrien /* Last entity in the SEC_MERGE sections of this type. */ 6689857Sobrien struct sec_merge_hash_entry *last; 6789857Sobrien /* Entity size. */ 6889857Sobrien unsigned int entsize; 6989857Sobrien /* Are entries fixed size or zero terminated strings? */ 70130561Sobrien bfd_boolean strings; 7189857Sobrien}; 7289857Sobrien 7389857Sobrienstruct sec_merge_info 7489857Sobrien{ 7589857Sobrien /* Chain of sec_merge_infos. */ 7689857Sobrien struct sec_merge_info *next; 7789857Sobrien /* Chain of sec_merge_sec_infos. */ 7889857Sobrien struct sec_merge_sec_info *chain; 7989857Sobrien /* A hash table used to hold section content. */ 8089857Sobrien struct sec_merge_hash *htab; 8189857Sobrien}; 8289857Sobrien 8389857Sobrienstruct sec_merge_sec_info 8489857Sobrien{ 8589857Sobrien /* Chain of sec_merge_sec_infos. */ 8689857Sobrien struct sec_merge_sec_info *next; 8789857Sobrien /* The corresponding section. */ 8889857Sobrien asection *sec; 8989857Sobrien /* Pointer to merge_info pointing to us. */ 90130561Sobrien void **psecinfo; 9189857Sobrien /* A hash table used to hold section content. */ 9289857Sobrien struct sec_merge_hash *htab; 9389857Sobrien /* First string in this section. */ 94218822Sdim struct sec_merge_hash_entry *first_str; 9589857Sobrien /* Original section content. */ 9689857Sobrien unsigned char contents[1]; 9789857Sobrien}; 9889857Sobrien 9989857Sobrien 10089857Sobrien/* Routine to create an entry in a section merge hashtab. */ 10189857Sobrien 10289857Sobrienstatic struct bfd_hash_entry * 103130561Sobriensec_merge_hash_newfunc (struct bfd_hash_entry *entry, 104130561Sobrien struct bfd_hash_table *table, const char *string) 10589857Sobrien{ 10689857Sobrien /* Allocate the structure if it has not already been allocated by a 10789857Sobrien subclass. */ 108218822Sdim if (entry == NULL) 109218822Sdim entry = bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)); 110218822Sdim if (entry == NULL) 11189857Sobrien return NULL; 11289857Sobrien 11389857Sobrien /* Call the allocation method of the superclass. */ 114218822Sdim entry = bfd_hash_newfunc (entry, table, string); 11589857Sobrien 116218822Sdim if (entry != NULL) 11789857Sobrien { 11889857Sobrien /* Initialize the local fields. */ 119218822Sdim struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry; 120218822Sdim 12189857Sobrien ret->u.suffix = NULL; 12289857Sobrien ret->alignment = 0; 12389857Sobrien ret->secinfo = NULL; 12489857Sobrien ret->next = NULL; 12589857Sobrien } 12689857Sobrien 127218822Sdim return entry; 12889857Sobrien} 12989857Sobrien 13089857Sobrien/* Look up an entry in a section merge hash table. */ 13189857Sobrien 13289857Sobrienstatic struct sec_merge_hash_entry * 133130561Sobriensec_merge_hash_lookup (struct sec_merge_hash *table, const char *string, 134130561Sobrien unsigned int alignment, bfd_boolean create) 13589857Sobrien{ 13689857Sobrien register const unsigned char *s; 13789857Sobrien register unsigned long hash; 13889857Sobrien register unsigned int c; 13989857Sobrien struct sec_merge_hash_entry *hashp; 14089857Sobrien unsigned int len, i; 14189857Sobrien unsigned int index; 14289857Sobrien 14389857Sobrien hash = 0; 14489857Sobrien len = 0; 14589857Sobrien s = (const unsigned char *) string; 14689857Sobrien if (table->strings) 14789857Sobrien { 14889857Sobrien if (table->entsize == 1) 14989857Sobrien { 15089857Sobrien while ((c = *s++) != '\0') 15189857Sobrien { 15289857Sobrien hash += c + (c << 17); 15389857Sobrien hash ^= hash >> 2; 15489857Sobrien ++len; 15589857Sobrien } 15689857Sobrien hash += len + (len << 17); 15789857Sobrien } 15889857Sobrien else 15989857Sobrien { 16089857Sobrien for (;;) 16189857Sobrien { 16289857Sobrien for (i = 0; i < table->entsize; ++i) 16389857Sobrien if (s[i] != '\0') 16489857Sobrien break; 16589857Sobrien if (i == table->entsize) 16689857Sobrien break; 16789857Sobrien for (i = 0; i < table->entsize; ++i) 16889857Sobrien { 16989857Sobrien c = *s++; 17089857Sobrien hash += c + (c << 17); 17189857Sobrien hash ^= hash >> 2; 17289857Sobrien } 17389857Sobrien ++len; 17489857Sobrien } 17589857Sobrien hash += len + (len << 17); 17689857Sobrien len *= table->entsize; 17789857Sobrien } 17889857Sobrien hash ^= hash >> 2; 17989857Sobrien len += table->entsize; 18089857Sobrien } 18189857Sobrien else 18289857Sobrien { 18389857Sobrien for (i = 0; i < table->entsize; ++i) 18489857Sobrien { 18589857Sobrien c = *s++; 18689857Sobrien hash += c + (c << 17); 18789857Sobrien hash ^= hash >> 2; 18889857Sobrien } 18989857Sobrien len = table->entsize; 19089857Sobrien } 19189857Sobrien 19289857Sobrien index = hash % table->table.size; 19389857Sobrien for (hashp = (struct sec_merge_hash_entry *) table->table.table[index]; 194218822Sdim hashp != NULL; 19589857Sobrien hashp = (struct sec_merge_hash_entry *) hashp->root.next) 19689857Sobrien { 19789857Sobrien if (hashp->root.hash == hash 19889857Sobrien && len == hashp->len 19989857Sobrien && memcmp (hashp->root.string, string, len) == 0) 20089857Sobrien { 20189857Sobrien /* If the string we found does not have at least the required 20289857Sobrien alignment, we need to insert another copy. */ 20389857Sobrien if (hashp->alignment < alignment) 20489857Sobrien { 205130561Sobrien if (create) 206130561Sobrien { 207130561Sobrien /* Mark the less aligned copy as deleted. */ 208130561Sobrien hashp->len = 0; 209130561Sobrien hashp->alignment = 0; 210130561Sobrien } 21189857Sobrien break; 21289857Sobrien } 21389857Sobrien return hashp; 21489857Sobrien } 21589857Sobrien } 21689857Sobrien 21789857Sobrien if (! create) 218218822Sdim return NULL; 21989857Sobrien 220218822Sdim hashp = ((struct sec_merge_hash_entry *) 221218822Sdim sec_merge_hash_newfunc (NULL, &table->table, string)); 222218822Sdim if (hashp == NULL) 223218822Sdim return NULL; 22489857Sobrien hashp->root.string = string; 22589857Sobrien hashp->root.hash = hash; 22689857Sobrien hashp->len = len; 22789857Sobrien hashp->alignment = alignment; 22889857Sobrien hashp->root.next = table->table.table[index]; 22989857Sobrien table->table.table[index] = (struct bfd_hash_entry *) hashp; 23089857Sobrien 23189857Sobrien return hashp; 23289857Sobrien} 23389857Sobrien 23489857Sobrien/* Create a new hash table. */ 23589857Sobrien 23689857Sobrienstatic struct sec_merge_hash * 237130561Sobriensec_merge_init (unsigned int entsize, bfd_boolean strings) 23889857Sobrien{ 23989857Sobrien struct sec_merge_hash *table; 24089857Sobrien 241218822Sdim table = bfd_malloc (sizeof (struct sec_merge_hash)); 24289857Sobrien if (table == NULL) 24389857Sobrien return NULL; 24489857Sobrien 245218822Sdim if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc, 246218822Sdim sizeof (struct sec_merge_hash_entry), 16699)) 24789857Sobrien { 24889857Sobrien free (table); 24989857Sobrien return NULL; 25089857Sobrien } 25189857Sobrien 25289857Sobrien table->size = 0; 25389857Sobrien table->first = NULL; 25489857Sobrien table->last = NULL; 25589857Sobrien table->entsize = entsize; 25689857Sobrien table->strings = strings; 25789857Sobrien 25889857Sobrien return table; 25989857Sobrien} 26089857Sobrien 26189857Sobrien/* Get the index of an entity in a hash table, adding it if it is not 26289857Sobrien already present. */ 26389857Sobrien 26489857Sobrienstatic struct sec_merge_hash_entry * 265130561Sobriensec_merge_add (struct sec_merge_hash *tab, const char *str, 266130561Sobrien unsigned int alignment, struct sec_merge_sec_info *secinfo) 26789857Sobrien{ 26889857Sobrien register struct sec_merge_hash_entry *entry; 26989857Sobrien 270130561Sobrien entry = sec_merge_hash_lookup (tab, str, alignment, TRUE); 27189857Sobrien if (entry == NULL) 27289857Sobrien return NULL; 27389857Sobrien 27489857Sobrien if (entry->secinfo == NULL) 27589857Sobrien { 27689857Sobrien tab->size++; 27789857Sobrien entry->secinfo = secinfo; 27889857Sobrien if (tab->first == NULL) 27989857Sobrien tab->first = entry; 28089857Sobrien else 28189857Sobrien tab->last->next = entry; 28289857Sobrien tab->last = entry; 28389857Sobrien } 28489857Sobrien 28589857Sobrien return entry; 28689857Sobrien} 28789857Sobrien 288130561Sobrienstatic bfd_boolean 289130561Sobriensec_merge_emit (bfd *abfd, struct sec_merge_hash_entry *entry) 29089857Sobrien{ 29189857Sobrien struct sec_merge_sec_info *secinfo = entry->secinfo; 29289857Sobrien asection *sec = secinfo->sec; 293218822Sdim char *pad = NULL; 29489857Sobrien bfd_size_type off = 0; 295218822Sdim int alignment_power = sec->output_section->alignment_power; 29689857Sobrien 29789857Sobrien if (alignment_power) 298218822Sdim { 299218822Sdim pad = bfd_zmalloc ((bfd_size_type) 1 << alignment_power); 300218822Sdim if (pad == NULL) 301218822Sdim return FALSE; 302218822Sdim } 30389857Sobrien 30489857Sobrien for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next) 30589857Sobrien { 306218822Sdim const char *str; 307218822Sdim bfd_size_type len; 30889857Sobrien 309218822Sdim len = -off & (entry->alignment - 1); 310218822Sdim if (len != 0) 31189857Sobrien { 312218822Sdim if (bfd_bwrite (pad, len, abfd) != len) 313218822Sdim goto err; 31489857Sobrien off += len; 31589857Sobrien } 31689857Sobrien 31789857Sobrien str = entry->root.string; 31889857Sobrien len = entry->len; 31989857Sobrien 320218822Sdim if (bfd_bwrite (str, len, abfd) != len) 321218822Sdim goto err; 32289857Sobrien 32389857Sobrien off += len; 32489857Sobrien } 32589857Sobrien 326218822Sdim /* Trailing alignment needed? */ 327218822Sdim off = sec->size - off; 328218822Sdim if (off != 0 329218822Sdim && bfd_bwrite (pad, off, abfd) != off) 330218822Sdim goto err; 331218822Sdim 332218822Sdim if (pad != NULL) 33389857Sobrien free (pad); 334218822Sdim return TRUE; 33589857Sobrien 336218822Sdim err: 337218822Sdim if (pad != NULL) 338218822Sdim free (pad); 339218822Sdim return FALSE; 34089857Sobrien} 34189857Sobrien 342218822Sdim/* Register a SEC_MERGE section as a candidate for merging. 343218822Sdim This function is called for all non-dynamic SEC_MERGE input sections. */ 34489857Sobrien 345130561Sobrienbfd_boolean 346218822Sdim_bfd_add_merge_section (bfd *abfd, void **psinfo, asection *sec, 347218822Sdim void **psecinfo) 34889857Sobrien{ 34989857Sobrien struct sec_merge_info *sinfo; 35089857Sobrien struct sec_merge_sec_info *secinfo; 35189857Sobrien unsigned int align; 35289857Sobrien bfd_size_type amt; 35389857Sobrien 354218822Sdim if ((abfd->flags & DYNAMIC) != 0 355218822Sdim || (sec->flags & SEC_MERGE) == 0) 356218822Sdim abort (); 357218822Sdim 358218822Sdim if (sec->size == 0 359218822Sdim || (sec->flags & SEC_EXCLUDE) != 0 36089857Sobrien || sec->entsize == 0) 361130561Sobrien return TRUE; 36289857Sobrien 36389857Sobrien if ((sec->flags & SEC_RELOC) != 0) 36489857Sobrien { 36589857Sobrien /* We aren't prepared to handle relocations in merged sections. */ 366130561Sobrien return TRUE; 36789857Sobrien } 36889857Sobrien 369218822Sdim align = sec->alignment_power; 370218822Sdim if ((sec->entsize < (unsigned) 1 << align 37189857Sobrien && ((sec->entsize & (sec->entsize - 1)) 37289857Sobrien || !(sec->flags & SEC_STRINGS))) 373218822Sdim || (sec->entsize > (unsigned) 1 << align 374218822Sdim && (sec->entsize & (((unsigned) 1 << align) - 1)))) 37589857Sobrien { 37689857Sobrien /* Sanity check. If string character size is smaller than 37789857Sobrien alignment, then we require character size to be a power 37889857Sobrien of 2, otherwise character size must be integer multiple 37989857Sobrien of alignment. For non-string constants, alignment must 38089857Sobrien be smaller than or equal to entity size and entity size 38189857Sobrien must be integer multiple of alignment. */ 382130561Sobrien return TRUE; 38389857Sobrien } 38489857Sobrien 38589857Sobrien for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next) 38689857Sobrien if ((secinfo = sinfo->chain) 38789857Sobrien && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS)) 38889857Sobrien && secinfo->sec->entsize == sec->entsize 389218822Sdim && secinfo->sec->alignment_power == sec->alignment_power 390218822Sdim && secinfo->sec->output_section == sec->output_section) 39189857Sobrien break; 39289857Sobrien 39389857Sobrien if (sinfo == NULL) 39489857Sobrien { 39589857Sobrien /* Initialize the information we need to keep track of. */ 396218822Sdim sinfo = bfd_alloc (abfd, sizeof (struct sec_merge_info)); 39789857Sobrien if (sinfo == NULL) 39889857Sobrien goto error_return; 39989857Sobrien sinfo->next = (struct sec_merge_info *) *psinfo; 40089857Sobrien sinfo->chain = NULL; 401130561Sobrien *psinfo = sinfo; 402104834Sobrien sinfo->htab = sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS)); 40389857Sobrien if (sinfo->htab == NULL) 40489857Sobrien goto error_return; 40589857Sobrien } 40689857Sobrien 40789857Sobrien /* Read the section from abfd. */ 40889857Sobrien 409218822Sdim amt = sizeof (struct sec_merge_sec_info) + sec->size - 1; 41089857Sobrien *psecinfo = bfd_alloc (abfd, amt); 41189857Sobrien if (*psecinfo == NULL) 41289857Sobrien goto error_return; 41389857Sobrien 414218822Sdim secinfo = (struct sec_merge_sec_info *) *psecinfo; 41589857Sobrien if (sinfo->chain) 41689857Sobrien { 41789857Sobrien secinfo->next = sinfo->chain->next; 41889857Sobrien sinfo->chain->next = secinfo; 41989857Sobrien } 42089857Sobrien else 42189857Sobrien secinfo->next = secinfo; 42289857Sobrien sinfo->chain = secinfo; 42389857Sobrien secinfo->sec = sec; 42489857Sobrien secinfo->psecinfo = psecinfo; 42589857Sobrien secinfo->htab = sinfo->htab; 426218822Sdim secinfo->first_str = NULL; 42789857Sobrien 428218822Sdim sec->rawsize = sec->size; 42989857Sobrien if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents, 430218822Sdim 0, sec->size)) 43189857Sobrien goto error_return; 43289857Sobrien 433130561Sobrien return TRUE; 43489857Sobrien 43589857Sobrien error_return: 43689857Sobrien *psecinfo = NULL; 437130561Sobrien return FALSE; 43889857Sobrien} 43989857Sobrien 44089857Sobrien/* Record one section into the hash table. */ 441130561Sobrienstatic bfd_boolean 442130561Sobrienrecord_section (struct sec_merge_info *sinfo, 443130561Sobrien struct sec_merge_sec_info *secinfo) 44489857Sobrien{ 44589857Sobrien asection *sec = secinfo->sec; 44689857Sobrien struct sec_merge_hash_entry *entry; 447130561Sobrien bfd_boolean nul; 44889857Sobrien unsigned char *p, *end; 44989857Sobrien bfd_vma mask, eltalign; 45089857Sobrien unsigned int align, i; 45189857Sobrien 452218822Sdim align = sec->alignment_power; 453218822Sdim end = secinfo->contents + sec->size; 454130561Sobrien nul = FALSE; 45589857Sobrien mask = ((bfd_vma) 1 << align) - 1; 45689857Sobrien if (sec->flags & SEC_STRINGS) 45789857Sobrien { 45889857Sobrien for (p = secinfo->contents; p < end; ) 45989857Sobrien { 46089857Sobrien eltalign = p - secinfo->contents; 46189857Sobrien eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1; 46289857Sobrien if (!eltalign || eltalign > mask) 46389857Sobrien eltalign = mask + 1; 464218822Sdim entry = sec_merge_add (sinfo->htab, (char *) p, (unsigned) eltalign, 465218822Sdim secinfo); 46689857Sobrien if (! entry) 46789857Sobrien goto error_return; 46889857Sobrien p += entry->len; 46989857Sobrien if (sec->entsize == 1) 47089857Sobrien { 47189857Sobrien while (p < end && *p == 0) 47289857Sobrien { 47389857Sobrien if (!nul && !((p - secinfo->contents) & mask)) 47489857Sobrien { 475130561Sobrien nul = TRUE; 47689857Sobrien entry = sec_merge_add (sinfo->htab, "", 47789857Sobrien (unsigned) mask + 1, secinfo); 47889857Sobrien if (! entry) 47989857Sobrien goto error_return; 48089857Sobrien } 48189857Sobrien p++; 482130561Sobrien } 48389857Sobrien } 48489857Sobrien else 48589857Sobrien { 48689857Sobrien while (p < end) 48789857Sobrien { 48889857Sobrien for (i = 0; i < sec->entsize; i++) 48989857Sobrien if (p[i] != '\0') 49089857Sobrien break; 49189857Sobrien if (i != sec->entsize) 49289857Sobrien break; 49389857Sobrien if (!nul && !((p - secinfo->contents) & mask)) 49489857Sobrien { 495130561Sobrien nul = TRUE; 496218822Sdim entry = sec_merge_add (sinfo->htab, (char *) p, 49789857Sobrien (unsigned) mask + 1, secinfo); 49889857Sobrien if (! entry) 49989857Sobrien goto error_return; 50089857Sobrien } 50189857Sobrien p += sec->entsize; 50289857Sobrien } 50389857Sobrien } 50489857Sobrien } 50589857Sobrien } 50689857Sobrien else 50789857Sobrien { 50889857Sobrien for (p = secinfo->contents; p < end; p += sec->entsize) 50989857Sobrien { 510218822Sdim entry = sec_merge_add (sinfo->htab, (char *) p, 1, secinfo); 51189857Sobrien if (! entry) 51289857Sobrien goto error_return; 51389857Sobrien } 51489857Sobrien } 51589857Sobrien 516130561Sobrien return TRUE; 51789857Sobrien 51889857Sobrienerror_return: 51989857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 52089857Sobrien *secinfo->psecinfo = NULL; 521130561Sobrien return FALSE; 52289857Sobrien} 52389857Sobrien 524130561Sobrienstatic int 525130561Sobrienstrrevcmp (const void *a, const void *b) 526130561Sobrien{ 527130561Sobrien struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; 528130561Sobrien struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; 529130561Sobrien unsigned int lenA = A->len; 530130561Sobrien unsigned int lenB = B->len; 531218822Sdim const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 532218822Sdim const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 533130561Sobrien int l = lenA < lenB ? lenA : lenB; 534130561Sobrien 535130561Sobrien while (l) 536130561Sobrien { 537130561Sobrien if (*s != *t) 538130561Sobrien return (int) *s - (int) *t; 539130561Sobrien s--; 540130561Sobrien t--; 541130561Sobrien l--; 542130561Sobrien } 543130561Sobrien return lenA - lenB; 544130561Sobrien} 545130561Sobrien 546130561Sobrien/* Like strrevcmp, but for the case where all strings have the same 547130561Sobrien alignment > entsize. */ 548130561Sobrien 549130561Sobrienstatic int 550130561Sobrienstrrevcmp_align (const void *a, const void *b) 551130561Sobrien{ 552130561Sobrien struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; 553130561Sobrien struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; 554130561Sobrien unsigned int lenA = A->len; 555130561Sobrien unsigned int lenB = B->len; 556218822Sdim const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; 557218822Sdim const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; 558130561Sobrien int l = lenA < lenB ? lenA : lenB; 559130561Sobrien int tail_align = (lenA & (A->alignment - 1)) - (lenB & (A->alignment - 1)); 560130561Sobrien 561130561Sobrien if (tail_align != 0) 562130561Sobrien return tail_align; 563130561Sobrien 564130561Sobrien while (l) 565130561Sobrien { 566130561Sobrien if (*s != *t) 567130561Sobrien return (int) *s - (int) *t; 568130561Sobrien s--; 569130561Sobrien t--; 570130561Sobrien l--; 571130561Sobrien } 572130561Sobrien return lenA - lenB; 573130561Sobrien} 574130561Sobrien 575130561Sobrienstatic inline int 576130561Sobrienis_suffix (const struct sec_merge_hash_entry *A, 577130561Sobrien const struct sec_merge_hash_entry *B) 578130561Sobrien{ 579130561Sobrien if (A->len <= B->len) 580130561Sobrien /* B cannot be a suffix of A unless A is equal to B, which is guaranteed 581130561Sobrien not to be equal by the hash table. */ 582130561Sobrien return 0; 583130561Sobrien 584130561Sobrien return memcmp (A->root.string + (A->len - B->len), 585130561Sobrien B->root.string, B->len) == 0; 586130561Sobrien} 587130561Sobrien 58889857Sobrien/* This is a helper function for _bfd_merge_sections. It attempts to 58989857Sobrien merge strings matching suffixes of longer strings. */ 59089857Sobrienstatic void 591130561Sobrienmerge_strings (struct sec_merge_info *sinfo) 59289857Sobrien{ 593130561Sobrien struct sec_merge_hash_entry **array, **a, *e; 59489857Sobrien struct sec_merge_sec_info *secinfo; 59589857Sobrien bfd_size_type size, amt; 596130561Sobrien unsigned int alignment = 0; 59789857Sobrien 598130561Sobrien /* Now sort the strings */ 59989857Sobrien amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); 600218822Sdim array = bfd_malloc (amt); 60189857Sobrien if (array == NULL) 60289857Sobrien goto alloc_failure; 60389857Sobrien 60489857Sobrien for (e = sinfo->htab->first, a = array; e; e = e->next) 60589857Sobrien if (e->alignment) 606130561Sobrien { 607130561Sobrien *a++ = e; 608130561Sobrien /* Adjust the length to not include the zero terminator. */ 609130561Sobrien e->len -= sinfo->htab->entsize; 610130561Sobrien if (alignment != e->alignment) 611130561Sobrien { 612130561Sobrien if (alignment == 0) 613130561Sobrien alignment = e->alignment; 614130561Sobrien else 615130561Sobrien alignment = (unsigned) -1; 616130561Sobrien } 617130561Sobrien } 61889857Sobrien 61989857Sobrien sinfo->htab->size = a - array; 620130561Sobrien if (sinfo->htab->size != 0) 62189857Sobrien { 622130561Sobrien qsort (array, (size_t) sinfo->htab->size, 623130561Sobrien sizeof (struct sec_merge_hash_entry *), 624130561Sobrien (alignment != (unsigned) -1 && alignment > sinfo->htab->entsize 625130561Sobrien ? strrevcmp_align : strrevcmp)); 62689857Sobrien 627130561Sobrien /* Loop over the sorted array and merge suffixes */ 628130561Sobrien e = *--a; 629130561Sobrien e->len += sinfo->htab->entsize; 630130561Sobrien while (--a >= array) 63189857Sobrien { 632130561Sobrien struct sec_merge_hash_entry *cmp = *a; 633130561Sobrien 634130561Sobrien cmp->len += sinfo->htab->entsize; 635130561Sobrien if (e->alignment >= cmp->alignment 636130561Sobrien && !((e->len - cmp->len) & (cmp->alignment - 1)) 637130561Sobrien && is_suffix (e, cmp)) 63889857Sobrien { 639130561Sobrien cmp->u.suffix = e; 640130561Sobrien cmp->alignment = 0; 64189857Sobrien } 64289857Sobrien else 643130561Sobrien e = cmp; 64489857Sobrien } 64589857Sobrien } 64689857Sobrien 64789857Sobrienalloc_failure: 64889857Sobrien if (array) 64989857Sobrien free (array); 65089857Sobrien 65189857Sobrien /* Now assign positions to the strings we want to keep. */ 65289857Sobrien size = 0; 65389857Sobrien secinfo = sinfo->htab->first->secinfo; 65489857Sobrien for (e = sinfo->htab->first; e; e = e->next) 65589857Sobrien { 65689857Sobrien if (e->secinfo != secinfo) 65789857Sobrien { 658218822Sdim secinfo->sec->size = size; 65989857Sobrien secinfo = e->secinfo; 66089857Sobrien } 66189857Sobrien if (e->alignment) 66289857Sobrien { 663218822Sdim if (e->secinfo->first_str == NULL) 66489857Sobrien { 665218822Sdim e->secinfo->first_str = e; 66689857Sobrien size = 0; 66789857Sobrien } 66889857Sobrien size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1); 66989857Sobrien e->u.index = size; 67089857Sobrien size += e->len; 67189857Sobrien } 67289857Sobrien } 673218822Sdim secinfo->sec->size = size; 674218822Sdim if (secinfo->sec->alignment_power != 0) 675218822Sdim { 676218822Sdim bfd_size_type align = (bfd_size_type) 1 << secinfo->sec->alignment_power; 677218822Sdim secinfo->sec->size = (secinfo->sec->size + align - 1) & -align; 678218822Sdim } 67989857Sobrien 68089857Sobrien /* And now adjust the rest, removing them from the chain (but not hashtable) 68189857Sobrien at the same time. */ 68289857Sobrien for (a = &sinfo->htab->first, e = *a; e; e = e->next) 68389857Sobrien if (e->alignment) 68489857Sobrien a = &e->next; 68589857Sobrien else 68689857Sobrien { 68789857Sobrien *a = e->next; 68889857Sobrien if (e->len) 68989857Sobrien { 69089857Sobrien e->secinfo = e->u.suffix->secinfo; 69189857Sobrien e->alignment = e->u.suffix->alignment; 69289857Sobrien e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len); 69389857Sobrien } 69489857Sobrien } 69589857Sobrien} 69689857Sobrien 69789857Sobrien/* This function is called once after all SEC_MERGE sections are registered 69889857Sobrien with _bfd_merge_section. */ 69989857Sobrien 700130561Sobrienbfd_boolean 701218822Sdim_bfd_merge_sections (bfd *abfd ATTRIBUTE_UNUSED, 702218822Sdim struct bfd_link_info *info ATTRIBUTE_UNUSED, 703218822Sdim void *xsinfo, 704130561Sobrien void (*remove_hook) (bfd *, asection *)) 70589857Sobrien{ 70689857Sobrien struct sec_merge_info *sinfo; 70789857Sobrien 70889857Sobrien for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) 70989857Sobrien { 71089857Sobrien struct sec_merge_sec_info * secinfo; 71189857Sobrien 71289857Sobrien if (! sinfo->chain) 71389857Sobrien continue; 71489857Sobrien 71589857Sobrien /* Move sinfo->chain to head of the chain, terminate it. */ 71689857Sobrien secinfo = sinfo->chain; 71789857Sobrien sinfo->chain = secinfo->next; 71889857Sobrien secinfo->next = NULL; 71989857Sobrien 72089857Sobrien /* Record the sections into the hash table. */ 72189857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 72289857Sobrien if (secinfo->sec->flags & SEC_EXCLUDE) 72389857Sobrien { 72489857Sobrien *secinfo->psecinfo = NULL; 72589857Sobrien if (remove_hook) 72689857Sobrien (*remove_hook) (abfd, secinfo->sec); 72789857Sobrien } 72889857Sobrien else if (! record_section (sinfo, secinfo)) 72989857Sobrien break; 73089857Sobrien 73189857Sobrien if (secinfo) 73289857Sobrien continue; 73389857Sobrien 73494536Sobrien if (sinfo->htab->first == NULL) 73594536Sobrien continue; 73694536Sobrien 73789857Sobrien if (sinfo->htab->strings) 73889857Sobrien merge_strings (sinfo); 73989857Sobrien else 74089857Sobrien { 74189857Sobrien struct sec_merge_hash_entry *e; 74289857Sobrien bfd_size_type size = 0; 74389857Sobrien 74489857Sobrien /* Things are much simpler for non-strings. 74589857Sobrien Just assign them slots in the section. */ 74689857Sobrien secinfo = NULL; 74789857Sobrien for (e = sinfo->htab->first; e; e = e->next) 74889857Sobrien { 749218822Sdim if (e->secinfo->first_str == NULL) 75089857Sobrien { 75189857Sobrien if (secinfo) 752218822Sdim secinfo->sec->size = size; 753218822Sdim e->secinfo->first_str = e; 75489857Sobrien size = 0; 75589857Sobrien } 75689857Sobrien size = (size + e->alignment - 1) 75789857Sobrien & ~((bfd_vma) e->alignment - 1); 75889857Sobrien e->u.index = size; 75989857Sobrien size += e->len; 76089857Sobrien secinfo = e->secinfo; 76189857Sobrien } 762218822Sdim secinfo->sec->size = size; 76389857Sobrien } 76489857Sobrien 765130561Sobrien /* Finally remove all input sections which have not made it into 76689857Sobrien the hash table at all. */ 76789857Sobrien for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) 768218822Sdim if (secinfo->first_str == NULL) 769218822Sdim secinfo->sec->flags |= SEC_EXCLUDE | SEC_KEEP; 77089857Sobrien } 77189857Sobrien 772130561Sobrien return TRUE; 77389857Sobrien} 77489857Sobrien 77589857Sobrien/* Write out the merged section. */ 77689857Sobrien 777130561Sobrienbfd_boolean 778130561Sobrien_bfd_write_merged_section (bfd *output_bfd, asection *sec, void *psecinfo) 77989857Sobrien{ 78089857Sobrien struct sec_merge_sec_info *secinfo; 78189857Sobrien file_ptr pos; 78289857Sobrien 78389857Sobrien secinfo = (struct sec_merge_sec_info *) psecinfo; 78489857Sobrien 785218822Sdim if (secinfo->first_str == NULL) 786130561Sobrien return TRUE; 78789857Sobrien 78889857Sobrien pos = sec->output_section->filepos + sec->output_offset; 78989857Sobrien if (bfd_seek (output_bfd, pos, SEEK_SET) != 0) 790130561Sobrien return FALSE; 79189857Sobrien 792218822Sdim if (! sec_merge_emit (output_bfd, secinfo->first_str)) 793130561Sobrien return FALSE; 79489857Sobrien 795130561Sobrien return TRUE; 79689857Sobrien} 79789857Sobrien 79889857Sobrien/* Adjust an address in the SEC_MERGE section. Given OFFSET within 79989857Sobrien *PSEC, this returns the new offset in the adjusted SEC_MERGE 80089857Sobrien section and writes the new section back into *PSEC. */ 80189857Sobrien 80289857Sobrienbfd_vma 803130561Sobrien_bfd_merged_section_offset (bfd *output_bfd ATTRIBUTE_UNUSED, asection **psec, 804218822Sdim void *psecinfo, bfd_vma offset) 80589857Sobrien{ 80689857Sobrien struct sec_merge_sec_info *secinfo; 80789857Sobrien struct sec_merge_hash_entry *entry; 80889857Sobrien unsigned char *p; 80989857Sobrien asection *sec = *psec; 81089857Sobrien 81189857Sobrien secinfo = (struct sec_merge_sec_info *) psecinfo; 81289857Sobrien 813218822Sdim if (offset >= sec->rawsize) 81489857Sobrien { 815218822Sdim if (offset > sec->rawsize) 81689857Sobrien { 81789857Sobrien (*_bfd_error_handler) 818218822Sdim (_("%s: access beyond end of merged section (%ld)"), 819218822Sdim bfd_get_filename (sec->owner), (long) offset); 82089857Sobrien } 821218822Sdim return secinfo->first_str ? sec->size : 0; 82289857Sobrien } 82389857Sobrien 82489857Sobrien if (secinfo->htab->strings) 82589857Sobrien { 82689857Sobrien if (sec->entsize == 1) 82789857Sobrien { 828218822Sdim p = secinfo->contents + offset - 1; 829104834Sobrien while (p >= secinfo->contents && *p) 83089857Sobrien --p; 83189857Sobrien ++p; 83289857Sobrien } 83389857Sobrien else 83489857Sobrien { 835218822Sdim p = secinfo->contents + (offset / sec->entsize) * sec->entsize; 83689857Sobrien p -= sec->entsize; 83789857Sobrien while (p >= secinfo->contents) 83889857Sobrien { 83989857Sobrien unsigned int i; 84089857Sobrien 84189857Sobrien for (i = 0; i < sec->entsize; ++i) 84289857Sobrien if (p[i] != '\0') 84389857Sobrien break; 84489857Sobrien if (i == sec->entsize) 84589857Sobrien break; 84689857Sobrien p -= sec->entsize; 84789857Sobrien } 84889857Sobrien p += sec->entsize; 84989857Sobrien } 85089857Sobrien } 85189857Sobrien else 85289857Sobrien { 853218822Sdim p = secinfo->contents + (offset / sec->entsize) * sec->entsize; 85489857Sobrien } 855218822Sdim entry = sec_merge_hash_lookup (secinfo->htab, (char *) p, 0, FALSE); 85689857Sobrien if (!entry) 85789857Sobrien { 85889857Sobrien if (! secinfo->htab->strings) 85989857Sobrien abort (); 86089857Sobrien /* This should only happen if somebody points into the padding 86189857Sobrien after a NUL character but before next entity. */ 86289857Sobrien if (*p) 86389857Sobrien abort (); 86489857Sobrien if (! secinfo->htab->first) 86589857Sobrien abort (); 86689857Sobrien entry = secinfo->htab->first; 867218822Sdim p = (secinfo->contents + (offset / sec->entsize + 1) * sec->entsize 868218822Sdim - entry->len); 86989857Sobrien } 87089857Sobrien 87189857Sobrien *psec = entry->secinfo->sec; 87289857Sobrien return entry->u.index + (secinfo->contents + offset - p); 87389857Sobrien} 874