2 Copyright (C) 2001-2017 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 3 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., 51 Franklin Street - Fifth Floor, Boston,
20 MA 02110-1301, USA. */
23 /* This file contains support for merging duplicate entities within sections,
24 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
= (struct bfd_hash_entry
*)
112 bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
));
116 /* Call the allocation method of the superclass. */
117 entry
= bfd_hash_newfunc (entry
, table
, string
);
121 /* Initialize the local fields. */
122 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
124 ret
->u
.suffix
= NULL
;
133 /* Look up an entry in a section merge hash table. */
135 static struct sec_merge_hash_entry
*
136 sec_merge_hash_lookup (struct sec_merge_hash
*table
, const char *string
,
137 unsigned int alignment
, bfd_boolean create
)
139 const unsigned char *s
;
142 struct sec_merge_hash_entry
*hashp
;
148 s
= (const unsigned char *) string
;
151 if (table
->entsize
== 1)
153 while ((c
= *s
++) != '\0')
155 hash
+= c
+ (c
<< 17);
159 hash
+= len
+ (len
<< 17);
165 for (i
= 0; i
< table
->entsize
; ++i
)
168 if (i
== table
->entsize
)
170 for (i
= 0; i
< table
->entsize
; ++i
)
173 hash
+= c
+ (c
<< 17);
178 hash
+= len
+ (len
<< 17);
179 len
*= table
->entsize
;
182 len
+= table
->entsize
;
186 for (i
= 0; i
< table
->entsize
; ++i
)
189 hash
+= c
+ (c
<< 17);
192 len
= table
->entsize
;
195 _index
= hash
% table
->table
.size
;
196 for (hashp
= (struct sec_merge_hash_entry
*) table
->table
.table
[_index
];
198 hashp
= (struct sec_merge_hash_entry
*) hashp
->root
.next
)
200 if (hashp
->root
.hash
== hash
202 && memcmp (hashp
->root
.string
, string
, len
) == 0)
204 /* If the string we found does not have at least the required
205 alignment, we need to insert another copy. */
206 if (hashp
->alignment
< alignment
)
210 /* Mark the less aligned copy as deleted. */
212 hashp
->alignment
= 0;
223 hashp
= ((struct sec_merge_hash_entry
*)
224 bfd_hash_insert (&table
->table
, string
, hash
));
228 hashp
->alignment
= alignment
;
232 /* Create a new hash table. */
234 static struct sec_merge_hash
*
235 sec_merge_init (unsigned int entsize
, bfd_boolean strings
)
237 struct sec_merge_hash
*table
;
239 table
= (struct sec_merge_hash
*) bfd_malloc (sizeof (struct sec_merge_hash
));
243 if (! bfd_hash_table_init_n (&table
->table
, sec_merge_hash_newfunc
,
244 sizeof (struct sec_merge_hash_entry
), 16699))
253 table
->entsize
= entsize
;
254 table
->strings
= strings
;
259 /* Get the index of an entity in a hash table, adding it if it is not
262 static struct sec_merge_hash_entry
*
263 sec_merge_add (struct sec_merge_hash
*tab
, const char *str
,
264 unsigned int alignment
, struct sec_merge_sec_info
*secinfo
)
266 struct sec_merge_hash_entry
*entry
;
268 entry
= sec_merge_hash_lookup (tab
, str
, alignment
, TRUE
);
272 if (entry
->secinfo
== NULL
)
275 entry
->secinfo
= secinfo
;
276 if (tab
->first
== NULL
)
279 tab
->last
->next
= entry
;
287 sec_merge_emit (bfd
*abfd
, struct sec_merge_hash_entry
*entry
,
288 unsigned char *contents
, file_ptr offset
)
290 struct sec_merge_sec_info
*secinfo
= entry
->secinfo
;
291 asection
*sec
= secinfo
->sec
;
293 bfd_size_type off
= 0;
294 int alignment_power
= sec
->output_section
->alignment_power
;
295 bfd_size_type pad_len
;
297 /* FIXME: If alignment_power is 0 then really we should scan the
298 entry list for the largest required alignment and use that. */
299 pad_len
= alignment_power
? ((bfd_size_type
) 1 << alignment_power
) : 16;
301 pad
= (char *) bfd_zmalloc (pad_len
);
305 for (; entry
!= NULL
&& entry
->secinfo
== secinfo
; entry
= entry
->next
)
310 len
= -off
& (entry
->alignment
- 1);
313 BFD_ASSERT (len
<= pad_len
);
316 memcpy (contents
+ offset
, pad
, len
);
319 else if (bfd_bwrite (pad
, len
, abfd
) != len
)
324 str
= entry
->root
.string
;
329 memcpy (contents
+ offset
, str
, len
);
332 else if (bfd_bwrite (str
, len
, abfd
) != len
)
338 /* Trailing alignment needed? */
339 off
= sec
->size
- off
;
342 BFD_ASSERT (off
<= pad_len
);
344 memcpy (contents
+ offset
, pad
, off
);
345 else if (bfd_bwrite (pad
, off
, abfd
) != off
)
357 /* Register a SEC_MERGE section as a candidate for merging.
358 This function is called for all non-dynamic SEC_MERGE input sections. */
361 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
364 struct sec_merge_info
*sinfo
;
365 struct sec_merge_sec_info
*secinfo
;
370 if ((abfd
->flags
& DYNAMIC
) != 0
371 || (sec
->flags
& SEC_MERGE
) == 0)
375 || (sec
->flags
& SEC_EXCLUDE
) != 0
376 || sec
->entsize
== 0)
379 if ((sec
->flags
& SEC_RELOC
) != 0)
381 /* We aren't prepared to handle relocations in merged sections. */
385 align
= sec
->alignment_power
;
386 if ((sec
->entsize
< (unsigned) 1 << align
387 && ((sec
->entsize
& (sec
->entsize
- 1))
388 || !(sec
->flags
& SEC_STRINGS
)))
389 || (sec
->entsize
> (unsigned) 1 << align
390 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
392 /* Sanity check. If string character size is smaller than
393 alignment, then we require character size to be a power
394 of 2, otherwise character size must be integer multiple
395 of alignment. For non-string constants, alignment must
396 be smaller than or equal to entity size and entity size
397 must be integer multiple of alignment. */
401 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
402 if ((secinfo
= sinfo
->chain
)
403 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
404 && secinfo
->sec
->entsize
== sec
->entsize
405 && secinfo
->sec
->alignment_power
== sec
->alignment_power
406 && secinfo
->sec
->output_section
== sec
->output_section
)
411 /* Initialize the information we need to keep track of. */
412 sinfo
= (struct sec_merge_info
*)
413 bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
416 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
419 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
420 if (sinfo
->htab
== NULL
)
424 /* Read the section from abfd. */
426 amt
= sizeof (struct sec_merge_sec_info
) - 1 + sec
->size
;
427 if (sec
->flags
& SEC_STRINGS
)
428 /* Some versions of gcc may emit a string without a zero terminator.
429 See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html
430 Allocate space for an extra zero. */
432 *psecinfo
= bfd_alloc (abfd
, amt
);
433 if (*psecinfo
== NULL
)
436 secinfo
= (struct sec_merge_sec_info
*) *psecinfo
;
439 secinfo
->next
= sinfo
->chain
->next
;
440 sinfo
->chain
->next
= secinfo
;
443 secinfo
->next
= secinfo
;
444 sinfo
->chain
= secinfo
;
446 secinfo
->psecinfo
= psecinfo
;
447 secinfo
->htab
= sinfo
->htab
;
448 secinfo
->first_str
= NULL
;
450 sec
->rawsize
= sec
->size
;
451 if (sec
->flags
& SEC_STRINGS
)
452 memset (secinfo
->contents
+ sec
->size
, 0, sec
->entsize
);
453 contents
= secinfo
->contents
;
454 if (! bfd_get_full_section_contents (sec
->owner
, sec
, &contents
))
464 /* Record one section into the hash table. */
466 record_section (struct sec_merge_info
*sinfo
,
467 struct sec_merge_sec_info
*secinfo
)
469 asection
*sec
= secinfo
->sec
;
470 struct sec_merge_hash_entry
*entry
;
472 unsigned char *p
, *end
;
473 bfd_vma mask
, eltalign
;
474 unsigned int align
, i
;
476 align
= sec
->alignment_power
;
477 end
= secinfo
->contents
+ sec
->size
;
479 mask
= ((bfd_vma
) 1 << align
) - 1;
480 if (sec
->flags
& SEC_STRINGS
)
482 for (p
= secinfo
->contents
; p
< end
; )
484 eltalign
= p
- secinfo
->contents
;
485 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
486 if (!eltalign
|| eltalign
> mask
)
488 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
493 if (sec
->entsize
== 1)
495 while (p
< end
&& *p
== 0)
497 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
500 entry
= sec_merge_add (sinfo
->htab
, "",
501 (unsigned) mask
+ 1, secinfo
);
512 for (i
= 0; i
< sec
->entsize
; i
++)
515 if (i
!= sec
->entsize
)
517 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
520 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
521 (unsigned) mask
+ 1, secinfo
);
532 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
534 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
543 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
544 *secinfo
->psecinfo
= NULL
;
549 strrevcmp (const void *a
, const void *b
)
551 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
552 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
553 unsigned int lenA
= A
->len
;
554 unsigned int lenB
= B
->len
;
555 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
556 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
557 int l
= lenA
< lenB
? lenA
: lenB
;
562 return (int) *s
- (int) *t
;
570 /* Like strrevcmp, but for the case where all strings have the same
571 alignment > entsize. */
574 strrevcmp_align (const void *a
, const void *b
)
576 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
577 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
578 unsigned int lenA
= A
->len
;
579 unsigned int lenB
= B
->len
;
580 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
581 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
582 int l
= lenA
< lenB
? lenA
: lenB
;
583 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
591 return (int) *s
- (int) *t
;
600 is_suffix (const struct sec_merge_hash_entry
*A
,
601 const struct sec_merge_hash_entry
*B
)
603 if (A
->len
<= B
->len
)
604 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
605 not to be equal by the hash table. */
608 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
609 B
->root
.string
, B
->len
) == 0;
612 /* This is a helper function for _bfd_merge_sections. It attempts to
613 merge strings matching suffixes of longer strings. */
615 merge_strings (struct sec_merge_info
*sinfo
)
617 struct sec_merge_hash_entry
**array
, **a
, *e
;
618 struct sec_merge_sec_info
*secinfo
;
619 bfd_size_type size
, amt
;
620 unsigned int alignment
= 0;
622 /* Now sort the strings */
623 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
624 array
= (struct sec_merge_hash_entry
**) bfd_malloc (amt
);
628 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
632 /* Adjust the length to not include the zero terminator. */
633 e
->len
-= sinfo
->htab
->entsize
;
634 if (alignment
!= e
->alignment
)
637 alignment
= e
->alignment
;
639 alignment
= (unsigned) -1;
643 sinfo
->htab
->size
= a
- array
;
644 if (sinfo
->htab
->size
!= 0)
646 qsort (array
, (size_t) sinfo
->htab
->size
,
647 sizeof (struct sec_merge_hash_entry
*),
648 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
649 ? strrevcmp_align
: strrevcmp
));
651 /* Loop over the sorted array and merge suffixes */
653 e
->len
+= sinfo
->htab
->entsize
;
656 struct sec_merge_hash_entry
*cmp
= *a
;
658 cmp
->len
+= sinfo
->htab
->entsize
;
659 if (e
->alignment
>= cmp
->alignment
660 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
661 && is_suffix (e
, cmp
))
673 /* Now assign positions to the strings we want to keep. */
675 secinfo
= sinfo
->htab
->first
->secinfo
;
676 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
678 if (e
->secinfo
!= secinfo
)
680 secinfo
->sec
->size
= size
;
681 secinfo
= e
->secinfo
;
685 if (e
->secinfo
->first_str
== NULL
)
687 e
->secinfo
->first_str
= e
;
690 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
695 secinfo
->sec
->size
= size
;
696 if (secinfo
->sec
->alignment_power
!= 0)
698 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
699 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
702 /* And now adjust the rest, removing them from the chain (but not hashtable)
704 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
712 e
->secinfo
= e
->u
.suffix
->secinfo
;
713 e
->alignment
= e
->u
.suffix
->alignment
;
714 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
720 /* This function is called once after all SEC_MERGE sections are registered
721 with _bfd_merge_section. */
724 _bfd_merge_sections (bfd
*abfd
,
725 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
727 void (*remove_hook
) (bfd
*, asection
*))
729 struct sec_merge_info
*sinfo
;
731 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
733 struct sec_merge_sec_info
* secinfo
;
738 /* Move sinfo->chain to head of the chain, terminate it. */
739 secinfo
= sinfo
->chain
;
740 sinfo
->chain
= secinfo
->next
;
741 secinfo
->next
= NULL
;
743 /* Record the sections into the hash table. */
744 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
745 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
747 *secinfo
->psecinfo
= NULL
;
749 (*remove_hook
) (abfd
, secinfo
->sec
);
751 else if (! record_section (sinfo
, secinfo
))
757 if (sinfo
->htab
->first
== NULL
)
760 if (sinfo
->htab
->strings
)
762 if (!merge_strings (sinfo
))
767 struct sec_merge_hash_entry
*e
;
768 bfd_size_type size
= 0;
770 /* Things are much simpler for non-strings.
771 Just assign them slots in the section. */
773 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
775 if (e
->secinfo
->first_str
== NULL
)
778 secinfo
->sec
->size
= size
;
779 e
->secinfo
->first_str
= e
;
782 size
= (size
+ e
->alignment
- 1)
783 & ~((bfd_vma
) e
->alignment
- 1);
786 secinfo
= e
->secinfo
;
788 secinfo
->sec
->size
= size
;
791 /* Finally remove all input sections which have not made it into
792 the hash table at all. */
793 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
794 if (secinfo
->first_str
== NULL
)
795 secinfo
->sec
->flags
|= SEC_EXCLUDE
| SEC_KEEP
;
801 /* Write out the merged section. */
804 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
806 struct sec_merge_sec_info
*secinfo
;
808 unsigned char *contents
;
809 Elf_Internal_Shdr
*hdr
;
811 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
816 if (secinfo
->first_str
== NULL
)
819 /* FIXME: octets_per_byte. */
820 hdr
= &elf_section_data (sec
->output_section
)->this_hdr
;
821 if (hdr
->sh_offset
== (file_ptr
) -1)
823 /* We must compress this section. Write output to the
825 contents
= hdr
->contents
;
826 if ((sec
->output_section
->flags
& SEC_ELF_COMPRESS
) == 0
833 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
834 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
838 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
, contents
,
845 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
846 *PSEC, this returns the new offset in the adjusted SEC_MERGE
847 section and writes the new section back into *PSEC. */
850 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
851 void *psecinfo
, bfd_vma offset
)
853 struct sec_merge_sec_info
*secinfo
;
854 struct sec_merge_hash_entry
*entry
;
856 asection
*sec
= *psec
;
858 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
863 if (offset
>= sec
->rawsize
)
865 if (offset
> sec
->rawsize
)
867 /* xgettext:c-format */
868 (_("%B: access beyond end of merged section (%Ld)"),
870 return secinfo
->first_str
? sec
->size
: 0;
873 if (secinfo
->htab
->strings
)
875 if (sec
->entsize
== 1)
877 p
= secinfo
->contents
+ offset
- 1;
878 while (p
>= secinfo
->contents
&& *p
)
884 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
886 while (p
>= secinfo
->contents
)
890 for (i
= 0; i
< sec
->entsize
; ++i
)
893 if (i
== sec
->entsize
)
902 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
904 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
907 if (! secinfo
->htab
->strings
)
909 /* This should only happen if somebody points into the padding
910 after a NUL character but before next entity. */
913 if (! secinfo
->htab
->first
)
915 entry
= secinfo
->htab
->first
;
916 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
920 *psec
= entry
->secinfo
->sec
;
921 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);
924 /* Tidy up when done. */
927 _bfd_merge_sections_free (void *xsinfo
)
929 struct sec_merge_info
*sinfo
;
931 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
933 bfd_hash_table_free (&sinfo
->htab
->table
);