2 Copyright 2001, 2002 Free Software Foundation, Inc.
3 Written by Jakub Jelinek <jakub@redhat.com>.
5 This file is part of BFD, the Binary File Descriptor library.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
21 /* This file contains support for merging duplicate entities within sections,
22 as used in ELF SHF_MERGE. */
28 #include "libiberty.h"
30 struct sec_merge_sec_info;
32 /* An entry in the section merge hash table. */
34 struct sec_merge_hash_entry
36 struct bfd_hash_entry root;
37 /* Length of this entry. */
39 /* Start of this string needs to be aligned to
40 alignment octets (not 1 << align). */
41 unsigned int alignment;
44 /* Index within the merged section. */
46 /* Entity size (if present in suffix hash tables). */
48 /* Entry this is a suffix of (if alignment is 0). */
49 struct sec_merge_hash_entry *suffix;
51 /* Which section is it in. */
52 struct sec_merge_sec_info *secinfo;
53 /* Next entity in the hash table. */
54 struct sec_merge_hash_entry *next;
57 /* The section merge hash table. */
61 struct bfd_hash_table table;
62 /* Next available index. */
64 /* First entity in the SEC_MERGE sections of this type. */
65 struct sec_merge_hash_entry *first;
66 /* Last entity in the SEC_MERGE sections of this type. */
67 struct sec_merge_hash_entry *last;
70 /* Are entries fixed size or zero terminated strings? */
76 /* Chain of sec_merge_infos. */
77 struct sec_merge_info *next;
78 /* Chain of sec_merge_sec_infos. */
79 struct sec_merge_sec_info *chain;
80 /* A hash table used to hold section content. */
81 struct sec_merge_hash *htab;
84 struct sec_merge_sec_info
86 /* Chain of sec_merge_sec_infos. */
87 struct sec_merge_sec_info *next;
88 /* The corresponding section. */
90 /* Pointer to merge_info pointing to us. */
92 /* A hash table used to hold section content. */
93 struct sec_merge_hash *htab;
94 /* First string in this section. */
95 struct sec_merge_hash_entry *first;
96 /* Original section content. */
97 unsigned char contents[1];
100 static struct bfd_hash_entry *sec_merge_hash_newfunc
101 PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *));
102 static struct sec_merge_hash_entry *sec_merge_hash_lookup
103 PARAMS ((struct sec_merge_hash *, const char *, unsigned int, boolean));
104 static struct sec_merge_hash *sec_merge_init
105 PARAMS ((unsigned int, boolean));
106 static struct sec_merge_hash_entry *sec_merge_add
107 PARAMS ((struct sec_merge_hash *, const char *, unsigned int,
108 struct sec_merge_sec_info *));
109 static boolean sec_merge_emit
110 PARAMS ((bfd *, struct sec_merge_hash_entry *));
111 static int cmplengthentry PARAMS ((const PTR, const PTR));
112 static int last4_eq PARAMS ((const PTR, const PTR));
113 static int last_eq PARAMS ((const PTR, const PTR));
114 static boolean record_section
115 PARAMS ((struct sec_merge_info *, struct sec_merge_sec_info *));
116 static void merge_strings PARAMS ((struct sec_merge_info *));
118 /* Routine to create an entry in a section merge hashtab. */
120 static struct bfd_hash_entry *
121 sec_merge_hash_newfunc (entry, table, string)
122 struct bfd_hash_entry *entry;
123 struct bfd_hash_table *table;
126 struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry;
128 /* Allocate the structure if it has not already been allocated by a
130 if (ret == (struct sec_merge_hash_entry *) NULL)
131 ret = ((struct sec_merge_hash_entry *)
132 bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)));
133 if (ret == (struct sec_merge_hash_entry *) NULL)
136 /* Call the allocation method of the superclass. */
137 ret = ((struct sec_merge_hash_entry *)
138 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string));
142 /* Initialize the local fields. */
143 ret->u.suffix = NULL;
149 return (struct bfd_hash_entry *) ret;
152 /* Look up an entry in a section merge hash table. */
154 static struct sec_merge_hash_entry *
155 sec_merge_hash_lookup (table, string, alignment, create)
156 struct sec_merge_hash *table;
158 unsigned int alignment;
161 register const unsigned char *s;
162 register unsigned long hash;
163 register unsigned int c;
164 struct sec_merge_hash_entry *hashp;
170 s = (const unsigned char *) string;
173 if (table->entsize == 1)
175 while ((c = *s++) != '\0')
177 hash += c + (c << 17);
181 hash += len + (len << 17);
187 for (i = 0; i < table->entsize; ++i)
190 if (i == table->entsize)
192 for (i = 0; i < table->entsize; ++i)
195 hash += c + (c << 17);
200 hash += len + (len << 17);
201 len *= table->entsize;
204 len += table->entsize;
208 for (i = 0; i < table->entsize; ++i)
211 hash += c + (c << 17);
214 len = table->entsize;
217 index = hash % table->table.size;
218 for (hashp = (struct sec_merge_hash_entry *) table->table.table[index];
219 hashp != (struct sec_merge_hash_entry *) NULL;
220 hashp = (struct sec_merge_hash_entry *) hashp->root.next)
222 if (hashp->root.hash == hash
224 && memcmp (hashp->root.string, string, len) == 0)
226 /* If the string we found does not have at least the required
227 alignment, we need to insert another copy. */
228 if (hashp->alignment < alignment)
230 /* Mark the less aligned copy as deleted. */
232 hashp->alignment = 0;
240 return (struct sec_merge_hash_entry *) NULL;
242 hashp = (struct sec_merge_hash_entry *)
243 sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL,
244 (struct bfd_hash_table *) table, string);
245 if (hashp == (struct sec_merge_hash_entry *) NULL)
246 return (struct sec_merge_hash_entry *) NULL;
247 hashp->root.string = string;
248 hashp->root.hash = hash;
250 hashp->alignment = alignment;
251 hashp->root.next = table->table.table[index];
252 table->table.table[index] = (struct bfd_hash_entry *) hashp;
257 /* Create a new hash table. */
259 static struct sec_merge_hash *
260 sec_merge_init (entsize, strings)
261 unsigned int entsize;
264 struct sec_merge_hash *table;
265 bfd_size_type amt = sizeof (struct sec_merge_hash);
267 table = (struct sec_merge_hash *) bfd_malloc (amt);
271 if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
280 table->entsize = entsize;
281 table->strings = strings;
286 /* Get the index of an entity in a hash table, adding it if it is not
289 static struct sec_merge_hash_entry *
290 sec_merge_add (tab, str, alignment, secinfo)
291 struct sec_merge_hash *tab;
293 unsigned int alignment;
294 struct sec_merge_sec_info *secinfo;
296 register struct sec_merge_hash_entry *entry;
298 entry = sec_merge_hash_lookup (tab, str, alignment, true);
302 if (entry->secinfo == NULL)
305 entry->secinfo = secinfo;
306 if (tab->first == NULL)
309 tab->last->next = entry;
317 sec_merge_emit (abfd, entry)
319 struct sec_merge_hash_entry *entry;
321 struct sec_merge_sec_info *secinfo = entry->secinfo;
322 asection *sec = secinfo->sec;
324 bfd_size_type off = 0;
325 int alignment_power = bfd_get_section_alignment (abfd, sec->output_section);
328 pad = bfd_zmalloc ((bfd_size_type) 1 << alignment_power);
330 for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next)
332 register const char *str;
335 len = off & (entry->alignment - 1);
338 len = entry->alignment - len;
339 if (bfd_bwrite ((PTR) pad, (bfd_size_type) len, abfd) != len)
344 str = entry->root.string;
347 if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len)
356 return entry == NULL || entry->secinfo != secinfo;
359 /* This function is called for each input file from the add_symbols
360 pass of the linker. */
363 _bfd_merge_section (abfd, psinfo, sec, psecinfo)
369 struct sec_merge_info *sinfo;
370 struct sec_merge_sec_info *secinfo;
374 if (sec->_raw_size == 0
375 || (sec->flags & SEC_EXCLUDE)
376 || (sec->flags & SEC_MERGE) == 0
377 || sec->entsize == 0)
380 if ((sec->flags & SEC_RELOC) != 0)
382 /* We aren't prepared to handle relocations in merged sections. */
386 if (sec->output_section != NULL
387 && bfd_is_abs_section (sec->output_section))
389 /* The section is being discarded from the link, so we should
394 align = bfd_get_section_alignment (sec->owner, sec);
395 if ((sec->entsize < (unsigned int)(1 << align)
396 && ((sec->entsize & (sec->entsize - 1))
397 || !(sec->flags & SEC_STRINGS)))
398 || (sec->entsize > (unsigned int)(1 << align)
399 && (sec->entsize & ((1 << align) - 1))))
401 /* Sanity check. If string character size is smaller than
402 alignment, then we require character size to be a power
403 of 2, otherwise character size must be integer multiple
404 of alignment. For non-string constants, alignment must
405 be smaller than or equal to entity size and entity size
406 must be integer multiple of alignment. */
410 for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
411 if ((secinfo = sinfo->chain)
412 && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
413 && secinfo->sec->entsize == sec->entsize
414 && ! strcmp (secinfo->sec->name, sec->name))
419 /* Initialize the information we need to keep track of. */
420 sinfo = (struct sec_merge_info *)
421 bfd_alloc (abfd, (bfd_size_type) sizeof (struct sec_merge_info));
424 sinfo->next = (struct sec_merge_info *) *psinfo;
426 *psinfo = (PTR) sinfo;
428 sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS));
429 if (sinfo->htab == NULL)
433 /* Read the section from abfd. */
435 amt = sizeof (struct sec_merge_sec_info) + sec->_raw_size - 1;
436 *psecinfo = bfd_alloc (abfd, amt);
437 if (*psecinfo == NULL)
440 secinfo = (struct sec_merge_sec_info *)*psecinfo;
443 secinfo->next = sinfo->chain->next;
444 sinfo->chain->next = secinfo;
447 secinfo->next = secinfo;
448 sinfo->chain = secinfo;
450 secinfo->psecinfo = psecinfo;
451 secinfo->htab = sinfo->htab;
452 secinfo->first = NULL;
454 if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents,
455 (bfd_vma) 0, sec->_raw_size))
465 /* Compare two sec_merge_hash_entry structures. This is called via qsort. */
468 cmplengthentry (a, b)
472 struct sec_merge_hash_entry * A = *(struct sec_merge_hash_entry **) a;
473 struct sec_merge_hash_entry * B = *(struct sec_merge_hash_entry **) b;
477 else if (A->len > B->len)
480 return memcmp (A->root.string, B->root.string, A->len);
488 struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
489 struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
491 if (memcmp (A->root.string + A->len - 5 * A->u.entsize,
492 B->root.string + B->len - 5 * A->u.entsize,
493 4 * A->u.entsize) != 0)
494 /* This was a hashtable collision. */
497 if (A->len <= B->len)
498 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
499 not to be equal by the hash table. */
502 if (A->alignment < B->alignment
503 || ((A->len - B->len) & (B->alignment - 1)))
504 /* The suffix is not sufficiently aligned. */
507 return memcmp (A->root.string + (A->len - B->len),
508 B->root.string, B->len - 5 * A->u.entsize) == 0;
516 struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
517 struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
519 if (B->len >= 5 * A->u.entsize)
520 /* Longer strings are just pushed into the hash table,
521 they'll be used when looking up for very short strings. */
524 if (memcmp (A->root.string + A->len - 2 * A->u.entsize,
525 B->root.string + B->len - 2 * A->u.entsize,
527 /* This was a hashtable collision. */
530 if (A->len <= B->len)
531 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
532 not to be equal by the hash table. */
535 if (A->alignment < B->alignment
536 || ((A->len - B->len) & (B->alignment - 1)))
537 /* The suffix is not sufficiently aligned. */
540 return memcmp (A->root.string + (A->len - B->len),
541 B->root.string, B->len - 2 * A->u.entsize) == 0;
544 /* Record one section into the hash table. */
546 record_section (sinfo, secinfo)
547 struct sec_merge_info *sinfo;
548 struct sec_merge_sec_info *secinfo;
550 asection *sec = secinfo->sec;
551 struct sec_merge_hash_entry *entry;
553 unsigned char *p, *end;
554 bfd_vma mask, eltalign;
555 unsigned int align, i;
557 align = bfd_get_section_alignment (sec->owner, sec);
558 end = secinfo->contents + sec->_raw_size;
560 mask = ((bfd_vma) 1 << align) - 1;
561 if (sec->flags & SEC_STRINGS)
563 for (p = secinfo->contents; p < end; )
565 eltalign = p - secinfo->contents;
566 eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1;
567 if (!eltalign || eltalign > mask)
569 entry = sec_merge_add (sinfo->htab, p, (unsigned) eltalign, secinfo);
573 if (sec->entsize == 1)
575 while (p < end && *p == 0)
577 if (!nul && !((p - secinfo->contents) & mask))
580 entry = sec_merge_add (sinfo->htab, "",
581 (unsigned) mask + 1, secinfo);
592 for (i = 0; i < sec->entsize; i++)
595 if (i != sec->entsize)
597 if (!nul && !((p - secinfo->contents) & mask))
600 entry = sec_merge_add (sinfo->htab, p,
601 (unsigned) mask + 1, secinfo);
612 for (p = secinfo->contents; p < end; p += sec->entsize)
614 entry = sec_merge_add (sinfo->htab, p, 1, secinfo);
623 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
624 *secinfo->psecinfo = NULL;
628 /* This is a helper function for _bfd_merge_sections. It attempts to
629 merge strings matching suffixes of longer strings. */
631 merge_strings (sinfo)
632 struct sec_merge_info *sinfo;
634 struct sec_merge_hash_entry **array, **a, **end, *e;
635 struct sec_merge_sec_info *secinfo;
636 htab_t lasttab = NULL, last4tab = NULL;
637 bfd_size_type size, amt;
639 /* Now sort the strings by length, longest first. */
641 amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *);
642 array = (struct sec_merge_hash_entry **) bfd_malloc (amt);
646 for (e = sinfo->htab->first, a = array; e; e = e->next)
650 sinfo->htab->size = a - array;
652 qsort (array, (size_t) sinfo->htab->size,
653 sizeof (struct sec_merge_hash_entry *), cmplengthentry);
655 last4tab = htab_create_alloc ((size_t) sinfo->htab->size * 4,
656 NULL, last4_eq, NULL, calloc, free);
657 lasttab = htab_create_alloc ((size_t) sinfo->htab->size * 4,
658 NULL, last_eq, NULL, calloc, free);
659 if (lasttab == NULL || last4tab == NULL)
662 /* Now insert the strings into hash tables (strings with last 4 characters
663 and strings with last character equal), look for longer strings which
665 for (a = array, end = array + sinfo->htab->size; a < end; a++)
667 register hashval_t hash;
670 const unsigned char *s;
674 e->u.entsize = sinfo->htab->entsize;
675 if (e->len <= e->u.entsize)
677 if (e->len > 4 * e->u.entsize)
679 s = e->root.string + e->len - e->u.entsize;
681 for (i = 0; i < 4 * e->u.entsize; i++)
684 hash += c + (c << 17);
687 p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
692 struct sec_merge_hash_entry *ent;
694 ent = (struct sec_merge_hash_entry *) *p;
702 s = e->root.string + e->len - e->u.entsize;
704 for (i = 0; i < e->u.entsize; i++)
707 hash += c + (c << 17);
710 p = htab_find_slot_with_hash (lasttab, e, hash, INSERT);
715 struct sec_merge_hash_entry *ent;
717 ent = (struct sec_merge_hash_entry *) *p;
729 htab_delete (lasttab);
731 htab_delete (last4tab);
733 /* Now assign positions to the strings we want to keep. */
735 secinfo = sinfo->htab->first->secinfo;
736 for (e = sinfo->htab->first; e; e = e->next)
738 if (e->secinfo != secinfo)
740 secinfo->sec->_cooked_size = size;
741 secinfo = e->secinfo;
745 if (e->secinfo->first == NULL)
747 e->secinfo->first = e;
750 size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1);
755 secinfo->sec->_cooked_size = size;
757 /* And now adjust the rest, removing them from the chain (but not hashtable)
759 for (a = &sinfo->htab->first, e = *a; e; e = e->next)
767 e->secinfo = e->u.suffix->secinfo;
768 e->alignment = e->u.suffix->alignment;
769 e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len);
774 /* This function is called once after all SEC_MERGE sections are registered
775 with _bfd_merge_section. */
778 _bfd_merge_sections (abfd, xsinfo, remove_hook)
779 bfd *abfd ATTRIBUTE_UNUSED;
781 void (*remove_hook) PARAMS((bfd *, asection *));
783 struct sec_merge_info *sinfo;
785 for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next)
787 struct sec_merge_sec_info * secinfo;
792 /* Move sinfo->chain to head of the chain, terminate it. */
793 secinfo = sinfo->chain;
794 sinfo->chain = secinfo->next;
795 secinfo->next = NULL;
797 /* Record the sections into the hash table. */
798 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
799 if (secinfo->sec->flags & SEC_EXCLUDE)
801 *secinfo->psecinfo = NULL;
803 (*remove_hook) (abfd, secinfo->sec);
805 else if (! record_section (sinfo, secinfo))
811 if (sinfo->htab->first == NULL)
814 if (sinfo->htab->strings)
815 merge_strings (sinfo);
818 struct sec_merge_hash_entry *e;
819 bfd_size_type size = 0;
821 /* Things are much simpler for non-strings.
822 Just assign them slots in the section. */
824 for (e = sinfo->htab->first; e; e = e->next)
826 if (e->secinfo->first == NULL)
829 secinfo->sec->_cooked_size = size;
830 e->secinfo->first = e;
833 size = (size + e->alignment - 1)
834 & ~((bfd_vma) e->alignment - 1);
837 secinfo = e->secinfo;
839 secinfo->sec->_cooked_size = size;
842 /* Finally shrink all input sections which have not made it into
843 the hash table at all. */
844 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
845 if (secinfo->first == NULL)
847 secinfo->sec->_cooked_size = 0;
848 secinfo->sec->flags |= SEC_EXCLUDE;
855 /* Write out the merged section. */
858 _bfd_write_merged_section (output_bfd, sec, psecinfo)
863 struct sec_merge_sec_info *secinfo;
866 secinfo = (struct sec_merge_sec_info *) psecinfo;
871 pos = sec->output_section->filepos + sec->output_offset;
872 if (bfd_seek (output_bfd, pos, SEEK_SET) != 0)
875 if (! sec_merge_emit (output_bfd, secinfo->first))
881 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
882 *PSEC, this returns the new offset in the adjusted SEC_MERGE
883 section and writes the new section back into *PSEC. */
886 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
887 bfd *output_bfd ATTRIBUTE_UNUSED;
890 bfd_vma offset, addend;
892 struct sec_merge_sec_info *secinfo;
893 struct sec_merge_hash_entry *entry;
895 asection *sec = *psec;
897 secinfo = (struct sec_merge_sec_info *) psecinfo;
899 if (offset + addend >= sec->_raw_size)
901 if (offset + addend > sec->_raw_size)
903 (*_bfd_error_handler)
904 (_("%s: access beyond end of merged section (%ld + %ld)"),
905 bfd_get_filename (sec->owner), (long) offset, (long) addend);
907 return (secinfo->first ? sec->_cooked_size : 0);
910 if (secinfo->htab->strings)
912 if (sec->entsize == 1)
914 p = secinfo->contents + offset + addend - 1;
915 while (*p && p >= secinfo->contents)
921 p = secinfo->contents
922 + ((offset + addend) / sec->entsize) * sec->entsize;
924 while (p >= secinfo->contents)
928 for (i = 0; i < sec->entsize; ++i)
931 if (i == sec->entsize)
940 p = secinfo->contents
941 + ((offset + addend) / sec->entsize) * sec->entsize;
943 entry = sec_merge_hash_lookup (secinfo->htab, p, 0, false);
946 if (! secinfo->htab->strings)
948 /* This should only happen if somebody points into the padding
949 after a NUL character but before next entity. */
952 if (! secinfo->htab->first)
954 entry = secinfo->htab->first;
955 p = secinfo->contents
956 + ((offset + addend) / sec->entsize + 1) * sec->entsize
960 *psec = entry->secinfo->sec;
961 return entry->u.index + (secinfo->contents + offset - p);