2 Copyright (C) 2001-2018 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
->size
% sec
->entsize
!= 0)
382 if ((sec
->flags
& SEC_RELOC
) != 0)
384 /* We aren't prepared to handle relocations in merged sections. */
388 align
= sec
->alignment_power
;
389 if ((sec
->entsize
< (unsigned) 1 << align
390 && ((sec
->entsize
& (sec
->entsize
- 1))
391 || !(sec
->flags
& SEC_STRINGS
)))
392 || (sec
->entsize
> (unsigned) 1 << align
393 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
395 /* Sanity check. If string character size is smaller than
396 alignment, then we require character size to be a power
397 of 2, otherwise character size must be integer multiple
398 of alignment. For non-string constants, alignment must
399 be smaller than or equal to entity size and entity size
400 must be integer multiple of alignment. */
404 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
405 if ((secinfo
= sinfo
->chain
)
406 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
407 && secinfo
->sec
->entsize
== sec
->entsize
408 && secinfo
->sec
->alignment_power
== sec
->alignment_power
409 && secinfo
->sec
->output_section
== sec
->output_section
)
414 /* Initialize the information we need to keep track of. */
415 sinfo
= (struct sec_merge_info
*)
416 bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
419 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
422 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
423 if (sinfo
->htab
== NULL
)
427 /* Read the section from abfd. */
429 amt
= sizeof (struct sec_merge_sec_info
) - 1 + sec
->size
;
430 if (sec
->flags
& SEC_STRINGS
)
431 /* Some versions of gcc may emit a string without a zero terminator.
432 See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html
433 Allocate space for an extra zero. */
435 *psecinfo
= bfd_alloc (abfd
, amt
);
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_str
= NULL
;
453 sec
->rawsize
= sec
->size
;
454 if (sec
->flags
& SEC_STRINGS
)
455 memset (secinfo
->contents
+ sec
->size
, 0, sec
->entsize
);
456 contents
= secinfo
->contents
;
457 if (! bfd_get_full_section_contents (sec
->owner
, sec
, &contents
))
467 /* Record one section into the hash table. */
469 record_section (struct sec_merge_info
*sinfo
,
470 struct sec_merge_sec_info
*secinfo
)
472 asection
*sec
= secinfo
->sec
;
473 struct sec_merge_hash_entry
*entry
;
475 unsigned char *p
, *end
;
476 bfd_vma mask
, eltalign
;
477 unsigned int align
, i
;
479 align
= sec
->alignment_power
;
480 end
= secinfo
->contents
+ sec
->size
;
482 mask
= ((bfd_vma
) 1 << align
) - 1;
483 if (sec
->flags
& SEC_STRINGS
)
485 for (p
= secinfo
->contents
; p
< end
; )
487 eltalign
= p
- secinfo
->contents
;
488 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
489 if (!eltalign
|| eltalign
> mask
)
491 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
496 if (sec
->entsize
== 1)
498 while (p
< end
&& *p
== 0)
500 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
503 entry
= sec_merge_add (sinfo
->htab
, "",
504 (unsigned) mask
+ 1, secinfo
);
515 for (i
= 0; i
< sec
->entsize
; i
++)
518 if (i
!= sec
->entsize
)
520 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
523 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
524 (unsigned) mask
+ 1, secinfo
);
535 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
537 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
546 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
547 *secinfo
->psecinfo
= NULL
;
552 strrevcmp (const void *a
, const void *b
)
554 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
555 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
556 unsigned int lenA
= A
->len
;
557 unsigned int lenB
= B
->len
;
558 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
559 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
560 int l
= lenA
< lenB
? lenA
: lenB
;
565 return (int) *s
- (int) *t
;
573 /* Like strrevcmp, but for the case where all strings have the same
574 alignment > entsize. */
577 strrevcmp_align (const void *a
, const void *b
)
579 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
580 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
581 unsigned int lenA
= A
->len
;
582 unsigned int lenB
= B
->len
;
583 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
584 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
585 int l
= lenA
< lenB
? lenA
: lenB
;
586 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
594 return (int) *s
- (int) *t
;
603 is_suffix (const struct sec_merge_hash_entry
*A
,
604 const struct sec_merge_hash_entry
*B
)
606 if (A
->len
<= B
->len
)
607 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
608 not to be equal by the hash table. */
611 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
612 B
->root
.string
, B
->len
) == 0;
615 /* This is a helper function for _bfd_merge_sections. It attempts to
616 merge strings matching suffixes of longer strings. */
618 merge_strings (struct sec_merge_info
*sinfo
)
620 struct sec_merge_hash_entry
**array
, **a
, *e
;
621 struct sec_merge_sec_info
*secinfo
;
622 bfd_size_type size
, amt
;
623 unsigned int alignment
= 0;
625 /* Now sort the strings */
626 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
627 array
= (struct sec_merge_hash_entry
**) bfd_malloc (amt
);
631 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
635 /* Adjust the length to not include the zero terminator. */
636 e
->len
-= sinfo
->htab
->entsize
;
637 if (alignment
!= e
->alignment
)
640 alignment
= e
->alignment
;
642 alignment
= (unsigned) -1;
646 sinfo
->htab
->size
= a
- array
;
647 if (sinfo
->htab
->size
!= 0)
649 qsort (array
, (size_t) sinfo
->htab
->size
,
650 sizeof (struct sec_merge_hash_entry
*),
651 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
652 ? strrevcmp_align
: strrevcmp
));
654 /* Loop over the sorted array and merge suffixes */
656 e
->len
+= sinfo
->htab
->entsize
;
659 struct sec_merge_hash_entry
*cmp
= *a
;
661 cmp
->len
+= sinfo
->htab
->entsize
;
662 if (e
->alignment
>= cmp
->alignment
663 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
664 && is_suffix (e
, cmp
))
676 /* Now assign positions to the strings we want to keep. */
678 secinfo
= sinfo
->htab
->first
->secinfo
;
679 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
681 if (e
->secinfo
!= secinfo
)
683 secinfo
->sec
->size
= size
;
684 secinfo
= e
->secinfo
;
688 if (e
->secinfo
->first_str
== NULL
)
690 e
->secinfo
->first_str
= e
;
693 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
698 secinfo
->sec
->size
= size
;
699 if (secinfo
->sec
->alignment_power
!= 0)
701 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
702 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
705 /* And now adjust the rest, removing them from the chain (but not hashtable)
707 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
715 e
->secinfo
= e
->u
.suffix
->secinfo
;
716 e
->alignment
= e
->u
.suffix
->alignment
;
717 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
723 /* This function is called once after all SEC_MERGE sections are registered
724 with _bfd_merge_section. */
727 _bfd_merge_sections (bfd
*abfd
,
728 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
730 void (*remove_hook
) (bfd
*, asection
*))
732 struct sec_merge_info
*sinfo
;
734 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
736 struct sec_merge_sec_info
* secinfo
;
741 /* Move sinfo->chain to head of the chain, terminate it. */
742 secinfo
= sinfo
->chain
;
743 sinfo
->chain
= secinfo
->next
;
744 secinfo
->next
= NULL
;
746 /* Record the sections into the hash table. */
747 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
748 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
750 *secinfo
->psecinfo
= NULL
;
752 (*remove_hook
) (abfd
, secinfo
->sec
);
754 else if (! record_section (sinfo
, secinfo
))
760 if (sinfo
->htab
->first
== NULL
)
763 if (sinfo
->htab
->strings
)
765 if (!merge_strings (sinfo
))
770 struct sec_merge_hash_entry
*e
;
771 bfd_size_type size
= 0;
773 /* Things are much simpler for non-strings.
774 Just assign them slots in the section. */
776 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
778 if (e
->secinfo
->first_str
== NULL
)
781 secinfo
->sec
->size
= size
;
782 e
->secinfo
->first_str
= e
;
785 size
= (size
+ e
->alignment
- 1)
786 & ~((bfd_vma
) e
->alignment
- 1);
789 secinfo
= e
->secinfo
;
791 secinfo
->sec
->size
= size
;
794 /* Finally remove all input sections which have not made it into
795 the hash table at all. */
796 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
797 if (secinfo
->first_str
== NULL
)
798 secinfo
->sec
->flags
|= SEC_EXCLUDE
| SEC_KEEP
;
804 /* Write out the merged section. */
807 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
809 struct sec_merge_sec_info
*secinfo
;
811 unsigned char *contents
;
812 Elf_Internal_Shdr
*hdr
;
814 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
819 if (secinfo
->first_str
== NULL
)
822 /* FIXME: octets_per_byte. */
823 hdr
= &elf_section_data (sec
->output_section
)->this_hdr
;
824 if (hdr
->sh_offset
== (file_ptr
) -1)
826 /* We must compress this section. Write output to the
828 contents
= hdr
->contents
;
829 if ((sec
->output_section
->flags
& SEC_ELF_COMPRESS
) == 0
836 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
837 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
841 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
, contents
,
848 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
849 *PSEC, this returns the new offset in the adjusted SEC_MERGE
850 section and writes the new section back into *PSEC. */
853 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
854 void *psecinfo
, bfd_vma offset
)
856 struct sec_merge_sec_info
*secinfo
;
857 struct sec_merge_hash_entry
*entry
;
859 asection
*sec
= *psec
;
861 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
866 if (offset
>= sec
->rawsize
)
868 if (offset
> sec
->rawsize
)
870 /* xgettext:c-format */
871 (_("%pB: access beyond end of merged section (%" PRId64
")"),
872 sec
->owner
, (int64_t) offset
);
873 return secinfo
->first_str
? sec
->size
: 0;
876 if (secinfo
->htab
->strings
)
878 if (sec
->entsize
== 1)
880 p
= secinfo
->contents
+ offset
- 1;
881 while (p
>= secinfo
->contents
&& *p
)
887 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
889 while (p
>= secinfo
->contents
)
893 for (i
= 0; i
< sec
->entsize
; ++i
)
896 if (i
== sec
->entsize
)
905 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
907 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
910 if (! secinfo
->htab
->strings
)
912 /* This should only happen if somebody points into the padding
913 after a NUL character but before next entity. */
916 if (! secinfo
->htab
->first
)
918 entry
= secinfo
->htab
->first
;
919 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
923 *psec
= entry
->secinfo
->sec
;
924 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);
927 /* Tidy up when done. */
930 _bfd_merge_sections_free (void *xsinfo
)
932 struct sec_merge_info
*sinfo
;
934 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
936 bfd_hash_table_free (&sinfo
->htab
->table
);