2 Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Written by Jakub Jelinek <jakub@redhat.com>.
6 This file is part of BFD, the Binary File Descriptor library.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21 MA 02110-1301, USA. */
24 /* This file contains support for merging duplicate entities within sections,
25 as used in ELF SHF_MERGE. */
31 #include "libiberty.h"
33 struct sec_merge_sec_info
;
35 /* An entry in the section merge hash table. */
37 struct sec_merge_hash_entry
39 struct bfd_hash_entry root
;
40 /* Length of this entry. This includes the zero terminator. */
42 /* Start of this string needs to be aligned to
43 alignment octets (not 1 << align). */
44 unsigned int alignment
;
47 /* Index within the merged section. */
49 /* Entry this is a suffix of (if alignment is 0). */
50 struct sec_merge_hash_entry
*suffix
;
52 /* Which section is it in. */
53 struct sec_merge_sec_info
*secinfo
;
54 /* Next entity in the hash table. */
55 struct sec_merge_hash_entry
*next
;
58 /* The section merge hash table. */
62 struct bfd_hash_table table
;
63 /* Next available index. */
65 /* First entity in the SEC_MERGE sections of this type. */
66 struct sec_merge_hash_entry
*first
;
67 /* Last entity in the SEC_MERGE sections of this type. */
68 struct sec_merge_hash_entry
*last
;
71 /* Are entries fixed size or zero terminated strings? */
77 /* Chain of sec_merge_infos. */
78 struct sec_merge_info
*next
;
79 /* Chain of sec_merge_sec_infos. */
80 struct sec_merge_sec_info
*chain
;
81 /* A hash table used to hold section content. */
82 struct sec_merge_hash
*htab
;
85 struct sec_merge_sec_info
87 /* Chain of sec_merge_sec_infos. */
88 struct sec_merge_sec_info
*next
;
89 /* The corresponding section. */
91 /* Pointer to merge_info pointing to us. */
93 /* A hash table used to hold section content. */
94 struct sec_merge_hash
*htab
;
95 /* First string in this section. */
96 struct sec_merge_hash_entry
*first_str
;
97 /* Original section content. */
98 unsigned char contents
[1];
102 /* Routine to create an entry in a section merge hashtab. */
104 static struct bfd_hash_entry
*
105 sec_merge_hash_newfunc (struct bfd_hash_entry
*entry
,
106 struct bfd_hash_table
*table
, const char *string
)
108 /* Allocate the structure if it has not already been allocated by a
111 entry
= bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
));
115 /* Call the allocation method of the superclass. */
116 entry
= bfd_hash_newfunc (entry
, table
, string
);
120 /* Initialize the local fields. */
121 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
123 ret
->u
.suffix
= NULL
;
132 /* Look up an entry in a section merge hash table. */
134 static struct sec_merge_hash_entry
*
135 sec_merge_hash_lookup (struct sec_merge_hash
*table
, const char *string
,
136 unsigned int alignment
, bfd_boolean create
)
138 register const unsigned char *s
;
139 register unsigned long hash
;
140 register unsigned int c
;
141 struct sec_merge_hash_entry
*hashp
;
147 s
= (const unsigned char *) string
;
150 if (table
->entsize
== 1)
152 while ((c
= *s
++) != '\0')
154 hash
+= c
+ (c
<< 17);
158 hash
+= len
+ (len
<< 17);
164 for (i
= 0; i
< table
->entsize
; ++i
)
167 if (i
== table
->entsize
)
169 for (i
= 0; i
< table
->entsize
; ++i
)
172 hash
+= c
+ (c
<< 17);
177 hash
+= len
+ (len
<< 17);
178 len
*= table
->entsize
;
181 len
+= table
->entsize
;
185 for (i
= 0; i
< table
->entsize
; ++i
)
188 hash
+= c
+ (c
<< 17);
191 len
= table
->entsize
;
194 index
= hash
% table
->table
.size
;
195 for (hashp
= (struct sec_merge_hash_entry
*) table
->table
.table
[index
];
197 hashp
= (struct sec_merge_hash_entry
*) hashp
->root
.next
)
199 if (hashp
->root
.hash
== hash
201 && memcmp (hashp
->root
.string
, string
, len
) == 0)
203 /* If the string we found does not have at least the required
204 alignment, we need to insert another copy. */
205 if (hashp
->alignment
< alignment
)
209 /* Mark the less aligned copy as deleted. */
211 hashp
->alignment
= 0;
222 hashp
= ((struct sec_merge_hash_entry
*)
223 bfd_hash_insert (&table
->table
, string
, hash
));
227 hashp
->alignment
= alignment
;
231 /* Create a new hash table. */
233 static struct sec_merge_hash
*
234 sec_merge_init (unsigned int entsize
, bfd_boolean strings
)
236 struct sec_merge_hash
*table
;
238 table
= bfd_malloc (sizeof (struct sec_merge_hash
));
242 if (! bfd_hash_table_init_n (&table
->table
, sec_merge_hash_newfunc
,
243 sizeof (struct sec_merge_hash_entry
), 16699))
252 table
->entsize
= entsize
;
253 table
->strings
= strings
;
258 /* Get the index of an entity in a hash table, adding it if it is not
261 static struct sec_merge_hash_entry
*
262 sec_merge_add (struct sec_merge_hash
*tab
, const char *str
,
263 unsigned int alignment
, struct sec_merge_sec_info
*secinfo
)
265 register struct sec_merge_hash_entry
*entry
;
267 entry
= sec_merge_hash_lookup (tab
, str
, alignment
, TRUE
);
271 if (entry
->secinfo
== NULL
)
274 entry
->secinfo
= secinfo
;
275 if (tab
->first
== NULL
)
278 tab
->last
->next
= entry
;
286 sec_merge_emit (bfd
*abfd
, struct sec_merge_hash_entry
*entry
)
288 struct sec_merge_sec_info
*secinfo
= entry
->secinfo
;
289 asection
*sec
= secinfo
->sec
;
291 bfd_size_type off
= 0;
292 int alignment_power
= sec
->output_section
->alignment_power
;
296 pad
= bfd_zmalloc ((bfd_size_type
) 1 << alignment_power
);
301 for (; entry
!= NULL
&& entry
->secinfo
== secinfo
; entry
= entry
->next
)
306 len
= -off
& (entry
->alignment
- 1);
309 if (bfd_bwrite (pad
, len
, abfd
) != len
)
314 str
= entry
->root
.string
;
317 if (bfd_bwrite (str
, len
, abfd
) != len
)
323 /* Trailing alignment needed? */
324 off
= sec
->size
- off
;
326 && bfd_bwrite (pad
, off
, abfd
) != off
)
339 /* Register a SEC_MERGE section as a candidate for merging.
340 This function is called for all non-dynamic SEC_MERGE input sections. */
343 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
346 struct sec_merge_info
*sinfo
;
347 struct sec_merge_sec_info
*secinfo
;
351 if ((abfd
->flags
& DYNAMIC
) != 0
352 || (sec
->flags
& SEC_MERGE
) == 0)
356 || (sec
->flags
& SEC_EXCLUDE
) != 0
357 || sec
->entsize
== 0)
360 if ((sec
->flags
& SEC_RELOC
) != 0)
362 /* We aren't prepared to handle relocations in merged sections. */
366 align
= sec
->alignment_power
;
367 if ((sec
->entsize
< (unsigned) 1 << align
368 && ((sec
->entsize
& (sec
->entsize
- 1))
369 || !(sec
->flags
& SEC_STRINGS
)))
370 || (sec
->entsize
> (unsigned) 1 << align
371 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
373 /* Sanity check. If string character size is smaller than
374 alignment, then we require character size to be a power
375 of 2, otherwise character size must be integer multiple
376 of alignment. For non-string constants, alignment must
377 be smaller than or equal to entity size and entity size
378 must be integer multiple of alignment. */
382 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
383 if ((secinfo
= sinfo
->chain
)
384 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
385 && secinfo
->sec
->entsize
== sec
->entsize
386 && secinfo
->sec
->alignment_power
== sec
->alignment_power
387 && secinfo
->sec
->output_section
== sec
->output_section
)
392 /* Initialize the information we need to keep track of. */
393 sinfo
= bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
396 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
399 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
400 if (sinfo
->htab
== NULL
)
404 /* Read the section from abfd. */
406 amt
= sizeof (struct sec_merge_sec_info
) + sec
->size
- 1;
407 *psecinfo
= bfd_alloc (abfd
, amt
);
408 if (*psecinfo
== NULL
)
411 secinfo
= (struct sec_merge_sec_info
*) *psecinfo
;
414 secinfo
->next
= sinfo
->chain
->next
;
415 sinfo
->chain
->next
= secinfo
;
418 secinfo
->next
= secinfo
;
419 sinfo
->chain
= secinfo
;
421 secinfo
->psecinfo
= psecinfo
;
422 secinfo
->htab
= sinfo
->htab
;
423 secinfo
->first_str
= NULL
;
425 sec
->rawsize
= sec
->size
;
426 if (! bfd_get_section_contents (sec
->owner
, sec
, secinfo
->contents
,
437 /* Record one section into the hash table. */
439 record_section (struct sec_merge_info
*sinfo
,
440 struct sec_merge_sec_info
*secinfo
)
442 asection
*sec
= secinfo
->sec
;
443 struct sec_merge_hash_entry
*entry
;
445 unsigned char *p
, *end
;
446 bfd_vma mask
, eltalign
;
447 unsigned int align
, i
;
449 align
= sec
->alignment_power
;
450 end
= secinfo
->contents
+ sec
->size
;
452 mask
= ((bfd_vma
) 1 << align
) - 1;
453 if (sec
->flags
& SEC_STRINGS
)
455 for (p
= secinfo
->contents
; p
< end
; )
457 eltalign
= p
- secinfo
->contents
;
458 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
459 if (!eltalign
|| eltalign
> mask
)
461 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
466 if (sec
->entsize
== 1)
468 while (p
< end
&& *p
== 0)
470 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
473 entry
= sec_merge_add (sinfo
->htab
, "",
474 (unsigned) mask
+ 1, secinfo
);
485 for (i
= 0; i
< sec
->entsize
; i
++)
488 if (i
!= sec
->entsize
)
490 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
493 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
494 (unsigned) mask
+ 1, secinfo
);
505 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
507 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
516 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
517 *secinfo
->psecinfo
= NULL
;
522 strrevcmp (const void *a
, const void *b
)
524 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
525 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
526 unsigned int lenA
= A
->len
;
527 unsigned int lenB
= B
->len
;
528 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
529 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
530 int l
= lenA
< lenB
? lenA
: lenB
;
535 return (int) *s
- (int) *t
;
543 /* Like strrevcmp, but for the case where all strings have the same
544 alignment > entsize. */
547 strrevcmp_align (const void *a
, const void *b
)
549 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
550 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
551 unsigned int lenA
= A
->len
;
552 unsigned int lenB
= B
->len
;
553 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
554 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
555 int l
= lenA
< lenB
? lenA
: lenB
;
556 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
564 return (int) *s
- (int) *t
;
573 is_suffix (const struct sec_merge_hash_entry
*A
,
574 const struct sec_merge_hash_entry
*B
)
576 if (A
->len
<= B
->len
)
577 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
578 not to be equal by the hash table. */
581 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
582 B
->root
.string
, B
->len
) == 0;
585 /* This is a helper function for _bfd_merge_sections. It attempts to
586 merge strings matching suffixes of longer strings. */
588 merge_strings (struct sec_merge_info
*sinfo
)
590 struct sec_merge_hash_entry
**array
, **a
, *e
;
591 struct sec_merge_sec_info
*secinfo
;
592 bfd_size_type size
, amt
;
593 unsigned int alignment
= 0;
595 /* Now sort the strings */
596 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
597 array
= bfd_malloc (amt
);
601 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
605 /* Adjust the length to not include the zero terminator. */
606 e
->len
-= sinfo
->htab
->entsize
;
607 if (alignment
!= e
->alignment
)
610 alignment
= e
->alignment
;
612 alignment
= (unsigned) -1;
616 sinfo
->htab
->size
= a
- array
;
617 if (sinfo
->htab
->size
!= 0)
619 qsort (array
, (size_t) sinfo
->htab
->size
,
620 sizeof (struct sec_merge_hash_entry
*),
621 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
622 ? strrevcmp_align
: strrevcmp
));
624 /* Loop over the sorted array and merge suffixes */
626 e
->len
+= sinfo
->htab
->entsize
;
629 struct sec_merge_hash_entry
*cmp
= *a
;
631 cmp
->len
+= sinfo
->htab
->entsize
;
632 if (e
->alignment
>= cmp
->alignment
633 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
634 && is_suffix (e
, cmp
))
648 /* Now assign positions to the strings we want to keep. */
650 secinfo
= sinfo
->htab
->first
->secinfo
;
651 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
653 if (e
->secinfo
!= secinfo
)
655 secinfo
->sec
->size
= size
;
656 secinfo
= e
->secinfo
;
660 if (e
->secinfo
->first_str
== NULL
)
662 e
->secinfo
->first_str
= e
;
665 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
670 secinfo
->sec
->size
= size
;
671 if (secinfo
->sec
->alignment_power
!= 0)
673 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
674 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
677 /* And now adjust the rest, removing them from the chain (but not hashtable)
679 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
687 e
->secinfo
= e
->u
.suffix
->secinfo
;
688 e
->alignment
= e
->u
.suffix
->alignment
;
689 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
694 /* This function is called once after all SEC_MERGE sections are registered
695 with _bfd_merge_section. */
698 _bfd_merge_sections (bfd
*abfd ATTRIBUTE_UNUSED
,
699 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
701 void (*remove_hook
) (bfd
*, asection
*))
703 struct sec_merge_info
*sinfo
;
705 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
707 struct sec_merge_sec_info
* secinfo
;
712 /* Move sinfo->chain to head of the chain, terminate it. */
713 secinfo
= sinfo
->chain
;
714 sinfo
->chain
= secinfo
->next
;
715 secinfo
->next
= NULL
;
717 /* Record the sections into the hash table. */
718 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
719 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
721 *secinfo
->psecinfo
= NULL
;
723 (*remove_hook
) (abfd
, secinfo
->sec
);
725 else if (! record_section (sinfo
, secinfo
))
731 if (sinfo
->htab
->first
== NULL
)
734 if (sinfo
->htab
->strings
)
735 merge_strings (sinfo
);
738 struct sec_merge_hash_entry
*e
;
739 bfd_size_type size
= 0;
741 /* Things are much simpler for non-strings.
742 Just assign them slots in the section. */
744 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
746 if (e
->secinfo
->first_str
== NULL
)
749 secinfo
->sec
->size
= size
;
750 e
->secinfo
->first_str
= e
;
753 size
= (size
+ e
->alignment
- 1)
754 & ~((bfd_vma
) e
->alignment
- 1);
757 secinfo
= e
->secinfo
;
759 secinfo
->sec
->size
= size
;
762 /* Finally remove all input sections which have not made it into
763 the hash table at all. */
764 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
765 if (secinfo
->first_str
== NULL
)
766 secinfo
->sec
->flags
|= SEC_EXCLUDE
| SEC_KEEP
;
772 /* Write out the merged section. */
775 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
777 struct sec_merge_sec_info
*secinfo
;
780 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
782 if (secinfo
->first_str
== NULL
)
785 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
786 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
789 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
))
795 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
796 *PSEC, this returns the new offset in the adjusted SEC_MERGE
797 section and writes the new section back into *PSEC. */
800 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
801 void *psecinfo
, bfd_vma offset
)
803 struct sec_merge_sec_info
*secinfo
;
804 struct sec_merge_hash_entry
*entry
;
806 asection
*sec
= *psec
;
808 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
810 if (offset
>= sec
->rawsize
)
812 if (offset
> sec
->rawsize
)
814 (*_bfd_error_handler
)
815 (_("%s: access beyond end of merged section (%ld)"),
816 bfd_get_filename (sec
->owner
), (long) offset
);
818 return secinfo
->first_str
? sec
->size
: 0;
821 if (secinfo
->htab
->strings
)
823 if (sec
->entsize
== 1)
825 p
= secinfo
->contents
+ offset
- 1;
826 while (p
>= secinfo
->contents
&& *p
)
832 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
834 while (p
>= secinfo
->contents
)
838 for (i
= 0; i
< sec
->entsize
; ++i
)
841 if (i
== sec
->entsize
)
850 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
852 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
855 if (! secinfo
->htab
->strings
)
857 /* This should only happen if somebody points into the padding
858 after a NUL character but before next entity. */
861 if (! secinfo
->htab
->first
)
863 entry
= secinfo
->htab
->first
;
864 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
868 *psec
= entry
->secinfo
->sec
;
869 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);