2 Copyright 2001 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. */
31 struct sec_merge_sec_info;
33 /* An entry in the section merge hash table. */
35 struct sec_merge_hash_entry
37 struct bfd_hash_entry root;
38 /* Length of this entry. */
40 /* Start of this string needs to be aligned to
41 alignment octets (not 1 << align). */
42 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;
266 table = ((struct sec_merge_hash *)
267 bfd_malloc (sizeof (struct sec_merge_hash)));
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 (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_write ((PTR) pad, 1, len, abfd) != len)
344 str = entry->root.string;
347 if (bfd_write ((PTR) str, 1, 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;
373 if (sec->_raw_size == 0
374 || (sec->flags & SEC_EXCLUDE)
375 || (sec->flags & SEC_MERGE) == 0
376 || sec->entsize == 0)
379 if ((sec->flags & SEC_RELOC) != 0)
381 /* We aren't prepared to handle relocations in merged sections. */
385 if (sec->output_section != NULL
386 && bfd_is_abs_section (sec->output_section))
388 /* The section is being discarded from the link, so we should
393 align = bfd_get_section_alignment (sec->owner, sec);
394 if ((sec->entsize < (unsigned int)(1 << align)
395 && ((sec->entsize & (sec->entsize - 1))
396 || !(sec->flags & SEC_STRINGS)))
397 || (sec->entsize > (unsigned int)(1 << align)
398 && (sec->entsize & ((1 << align) - 1))))
400 /* Sanity check. If string character size is smaller than
401 alignment, then we require character size to be a power
402 of 2, otherwise character size must be integer multiple
403 of alignment. For non-string constants, alignment must
404 be smaller than or equal to entity size and entity size
405 must be integer multiple of alignment. */
409 for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
410 if ((secinfo = sinfo->chain)
411 && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
412 && secinfo->sec->entsize == sec->entsize
413 && ! strcmp (secinfo->sec->name, sec->name))
418 /* Initialize the information we need to keep track of. */
419 sinfo = (struct sec_merge_info *)
420 bfd_alloc (abfd, sizeof (struct sec_merge_info));
423 sinfo->next = (struct sec_merge_info *) *psinfo;
425 *psinfo = (PTR) sinfo;
427 sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS));
428 if (sinfo->htab == NULL)
432 /* Read the section from abfd. */
434 *psecinfo = bfd_alloc (abfd, sizeof (struct sec_merge_sec_info)
435 + sec->_raw_size - 1);
436 if (*psecinfo == NULL)
439 secinfo = (struct sec_merge_sec_info *)*psecinfo;
442 secinfo->next = sinfo->chain->next;
443 sinfo->chain->next = secinfo;
446 secinfo->next = secinfo;
447 sinfo->chain = secinfo;
449 secinfo->psecinfo = psecinfo;
450 secinfo->htab = sinfo->htab;
451 secinfo->first = NULL;
453 if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents, 0,
464 /* Compare two sec_merge_hash_entry structures. This is called via qsort. */
467 cmplengthentry (a, b)
471 struct sec_merge_hash_entry * A = *(struct sec_merge_hash_entry **) a;
472 struct sec_merge_hash_entry * B = *(struct sec_merge_hash_entry **) b;
476 else if (A->len > B->len)
479 return memcmp (A->root.string, B->root.string, A->len);
487 struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
488 struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
490 if (memcmp (A->root.string + A->len - 5 * A->u.entsize,
491 B->root.string + B->len - 5 * A->u.entsize,
492 4 * A->u.entsize) != 0)
493 /* This was a hashtable collision. */
496 if (A->len <= B->len)
497 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
498 not to be equal by the hash table. */
501 if (A->alignment < B->alignment
502 || ((A->len - B->len) & (B->alignment - 1)))
503 /* The suffix is not sufficiently aligned. */
506 return memcmp (A->root.string + (A->len - B->len),
507 B->root.string, B->len - 5 * A->u.entsize) == 0;
515 struct sec_merge_hash_entry * A = (struct sec_merge_hash_entry *) a;
516 struct sec_merge_hash_entry * B = (struct sec_merge_hash_entry *) b;
518 if (B->len >= 5 * A->u.entsize)
519 /* Longer strings are just pushed into the hash table,
520 they'll be used when looking up for very short strings. */
523 if (memcmp (A->root.string + A->len - 2 * A->u.entsize,
524 B->root.string + B->len - 2 * A->u.entsize,
526 /* This was a hashtable collision. */
529 if (A->len <= B->len)
530 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
531 not to be equal by the hash table. */
534 if (A->alignment < B->alignment
535 || ((A->len - B->len) & (B->alignment - 1)))
536 /* The suffix is not sufficiently aligned. */
539 return memcmp (A->root.string + (A->len - B->len),
540 B->root.string, B->len - 2 * A->u.entsize) == 0;
543 /* Record one section into the hash table. */
545 record_section (sinfo, secinfo)
546 struct sec_merge_info *sinfo;
547 struct sec_merge_sec_info *secinfo;
549 asection *sec = secinfo->sec;
550 struct sec_merge_hash_entry *entry;
552 unsigned char *p, *end;
553 bfd_vma mask, eltalign;
554 unsigned int align, i;
556 align = bfd_get_section_alignment (sec->owner, sec);
557 end = secinfo->contents + sec->_raw_size;
559 mask = ((bfd_vma)1 << align) - 1;
560 if (sec->flags & SEC_STRINGS)
562 for (p = secinfo->contents; p < end;)
564 eltalign = p - secinfo->contents;
565 eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1;
566 if (!eltalign || eltalign > mask)
568 entry = sec_merge_add (sinfo->htab, p, eltalign, secinfo);
572 if (sec->entsize == 1)
574 while (p < end && *p == 0)
576 if (!nul && !((p - secinfo->contents) & mask))
579 entry = sec_merge_add (sinfo->htab, "", mask + 1,
591 for (i = 0; i < sec->entsize; i++)
594 if (i != sec->entsize)
596 if (!nul && !((p - secinfo->contents) & mask))
599 entry = sec_merge_add (sinfo->htab, p, mask + 1,
611 for (p = secinfo->contents; p < end; p += sec->entsize)
613 entry = sec_merge_add (sinfo->htab, p, 1, secinfo);
622 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
623 *secinfo->psecinfo = NULL;
627 /* This is a helper function for _bfd_merge_sections. It attempts to
628 merge strings matching suffixes of longer strings. */
630 merge_strings (sinfo)
631 struct sec_merge_info *sinfo;
633 struct sec_merge_hash_entry **array, **a, **end, *e;
634 struct sec_merge_sec_info *secinfo;
635 htab_t lasttab = NULL, last4tab = NULL;
638 /* Now sort the strings by length, longest first. */
639 array = (struct sec_merge_hash_entry **)
640 malloc (sinfo->htab->size
641 * sizeof (struct sec_merge_hash_entry *));
645 for (e = sinfo->htab->first, a = array; e; e = e->next)
649 sinfo->htab->size = a - array;
651 qsort (array, sinfo->htab->size, sizeof (struct sec_merge_hash_entry *),
654 last4tab = htab_create (sinfo->htab->size * 4, NULL, last4_eq, NULL);
655 lasttab = htab_create (sinfo->htab->size * 4, NULL, last_eq, NULL);
656 if (lasttab == NULL || last4tab == NULL)
659 /* Now insert the strings into hash tables (strings with last 4 characters
660 and strings with last character equal), look for longer strings which
662 for (a = array, end = array + sinfo->htab->size; a < end; a++)
664 register hashval_t hash;
667 const unsigned char *s;
671 e->u.entsize = sinfo->htab->entsize;
672 if (e->len <= e->u.entsize)
674 if (e->len > 4 * e->u.entsize)
676 s = e->root.string + e->len - e->u.entsize;
678 for (i = 0; i < 4 * e->u.entsize; i++)
681 hash += c + (c << 17);
684 p = htab_find_slot_with_hash (last4tab, e, hash, INSERT);
689 struct sec_merge_hash_entry *ent;
691 ent = (struct sec_merge_hash_entry *) *p;
699 s = e->root.string + e->len - e->u.entsize;
701 for (i = 0; i < e->u.entsize; i++)
704 hash += c + (c << 17);
707 p = htab_find_slot_with_hash (lasttab, e, hash, INSERT);
712 struct sec_merge_hash_entry *ent;
714 ent = (struct sec_merge_hash_entry *) *p;
726 htab_delete (lasttab);
728 htab_delete (last4tab);
730 /* Now assign positions to the strings we want to keep. */
732 secinfo = sinfo->htab->first->secinfo;
733 for (e = sinfo->htab->first; e; e = e->next)
735 if (e->secinfo != secinfo)
737 secinfo->sec->_cooked_size = size;
738 secinfo = e->secinfo;
742 if (e->secinfo->first == NULL)
744 e->secinfo->first = e;
747 size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1);
752 secinfo->sec->_cooked_size = size;
754 /* And now adjust the rest, removing them from the chain (but not hashtable)
756 for (a = &sinfo->htab->first, e = *a; e; e = e->next)
764 e->secinfo = e->u.suffix->secinfo;
765 e->alignment = e->u.suffix->alignment;
766 e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len);
771 /* This function is called once after all SEC_MERGE sections are registered
772 with _bfd_merge_section. */
775 _bfd_merge_sections (abfd, xsinfo)
776 bfd *abfd ATTRIBUTE_UNUSED;
779 struct sec_merge_info *sinfo;
781 for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next)
783 struct sec_merge_sec_info * secinfo;
788 /* Move sinfo->chain to head of the chain, terminate it. */
789 secinfo = sinfo->chain;
790 sinfo->chain = secinfo->next;
791 secinfo->next = NULL;
793 /* Record the sections into the hash table. */
794 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
795 if (secinfo->sec->flags & SEC_EXCLUDE)
796 *secinfo->psecinfo = NULL;
797 else if (! record_section (sinfo, secinfo))
803 if (sinfo->htab->strings)
804 merge_strings (sinfo);
807 struct sec_merge_hash_entry *e;
808 bfd_size_type size = 0;
810 /* Things are much simpler for non-strings.
811 Just assign them slots in the section. */
813 for (e = sinfo->htab->first; e; e = e->next)
815 if (e->secinfo->first == NULL)
818 secinfo->sec->_cooked_size = size;
819 e->secinfo->first = e;
822 size = (size + e->alignment - 1)
823 & ~((bfd_vma) e->alignment - 1);
826 secinfo = e->secinfo;
828 secinfo->sec->_cooked_size = size;
831 /* Finally shrink all input sections which have not made it into
832 the hash table at all. */
833 for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next)
834 if (secinfo->first == NULL)
836 secinfo->sec->_cooked_size = 0;
837 secinfo->sec->flags |= SEC_EXCLUDE;
844 /* Write out the merged section. */
847 _bfd_write_merged_section (output_bfd, sec, psecinfo)
852 struct sec_merge_sec_info *secinfo;
854 secinfo = (struct sec_merge_sec_info *) psecinfo;
859 if (bfd_seek (output_bfd,
860 (sec->output_section->filepos + sec->output_offset),
864 if (! sec_merge_emit (output_bfd, secinfo->first))
870 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
871 *PSEC, this returns the new offset in the adjusted SEC_MERGE
872 section and writes the new section back into *PSEC. */
875 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
876 bfd *output_bfd ATTRIBUTE_UNUSED;
879 bfd_vma offset, addend;
881 struct sec_merge_sec_info *secinfo;
882 struct sec_merge_hash_entry *entry;
884 asection *sec = *psec;
886 secinfo = (struct sec_merge_sec_info *) psecinfo;
888 if (offset + addend >= sec->_raw_size)
890 if (offset + addend > sec->_raw_size)
891 (*_bfd_error_handler) (_("%s: access beyond end of merged section (%ld + %ld)"),
892 bfd_get_filename (sec->owner), (long)offset,
894 return (secinfo->first ? sec->_cooked_size : 0);
897 if (secinfo->htab->strings)
899 if (sec->entsize == 1)
901 p = secinfo->contents + offset + addend - 1;
902 while (*p && p >= secinfo->contents)
908 p = secinfo->contents
909 + ((offset + addend) / sec->entsize) * sec->entsize;
911 while (p >= secinfo->contents)
915 for (i = 0; i < sec->entsize; ++i)
918 if (i == sec->entsize)
927 p = secinfo->contents
928 + ((offset + addend) / sec->entsize) * sec->entsize;
930 entry = sec_merge_hash_lookup (secinfo->htab, p, 0, false);
933 if (! secinfo->htab->strings)
935 /* This should only happen if somebody points into the padding
936 after a NUL character but before next entity. */
939 if (! secinfo->htab->first)
941 entry = secinfo->htab->first;
942 p = secinfo->contents
943 + ((offset + addend) / sec->entsize + 1) * sec->entsize
947 *psec = entry->secinfo->sec;
948 return entry->u.index + (secinfo->contents + offset - p);