2 Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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
= (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
)
289 struct sec_merge_sec_info
*secinfo
= entry
->secinfo
;
290 asection
*sec
= secinfo
->sec
;
292 bfd_size_type off
= 0;
293 int alignment_power
= sec
->output_section
->alignment_power
;
297 pad
= (char *) bfd_zmalloc ((bfd_size_type
) 1 << alignment_power
);
302 for (; entry
!= NULL
&& entry
->secinfo
== secinfo
; entry
= entry
->next
)
307 len
= -off
& (entry
->alignment
- 1);
310 /* We should never have an entry with an alignment
311 greater than the section's alignment. */
312 BFD_ASSERT (len
<= (bfd_size_type
) (1 << alignment_power
));
313 if (bfd_bwrite (pad
, len
, abfd
) != len
)
318 str
= entry
->root
.string
;
321 if (bfd_bwrite (str
, len
, abfd
) != len
)
327 /* Trailing alignment needed? */
328 off
= sec
->size
- off
;
331 && bfd_bwrite (pad
, off
, abfd
) != off
)
344 /* Register a SEC_MERGE section as a candidate for merging.
345 This function is called for all non-dynamic SEC_MERGE input sections. */
348 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
351 struct sec_merge_info
*sinfo
;
352 struct sec_merge_sec_info
*secinfo
;
356 if ((abfd
->flags
& DYNAMIC
) != 0
357 || (sec
->flags
& SEC_MERGE
) == 0)
361 || (sec
->flags
& SEC_EXCLUDE
) != 0
362 || sec
->entsize
== 0)
365 if ((sec
->flags
& SEC_RELOC
) != 0)
367 /* We aren't prepared to handle relocations in merged sections. */
371 align
= sec
->alignment_power
;
372 if ((sec
->entsize
< (unsigned) 1 << align
373 && ((sec
->entsize
& (sec
->entsize
- 1))
374 || !(sec
->flags
& SEC_STRINGS
)))
375 || (sec
->entsize
> (unsigned) 1 << align
376 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
378 /* Sanity check. If string character size is smaller than
379 alignment, then we require character size to be a power
380 of 2, otherwise character size must be integer multiple
381 of alignment. For non-string constants, alignment must
382 be smaller than or equal to entity size and entity size
383 must be integer multiple of alignment. */
387 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
388 if ((secinfo
= sinfo
->chain
)
389 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
390 && secinfo
->sec
->entsize
== sec
->entsize
391 && secinfo
->sec
->alignment_power
== sec
->alignment_power
392 && secinfo
->sec
->output_section
== sec
->output_section
)
397 /* Initialize the information we need to keep track of. */
398 sinfo
= (struct sec_merge_info
*)
399 bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
402 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
405 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
406 if (sinfo
->htab
== NULL
)
410 /* Read the section from abfd. */
412 amt
= sizeof (struct sec_merge_sec_info
) - 1 + sec
->size
;
413 if (sec
->flags
& SEC_STRINGS
)
414 /* Some versions of gcc may emit a string without a zero terminator.
415 See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html
416 Allocate space for an extra zero. */
418 *psecinfo
= bfd_alloc (abfd
, amt
);
419 if (*psecinfo
== NULL
)
422 secinfo
= (struct sec_merge_sec_info
*) *psecinfo
;
425 secinfo
->next
= sinfo
->chain
->next
;
426 sinfo
->chain
->next
= secinfo
;
429 secinfo
->next
= secinfo
;
430 sinfo
->chain
= secinfo
;
432 secinfo
->psecinfo
= psecinfo
;
433 secinfo
->htab
= sinfo
->htab
;
434 secinfo
->first_str
= NULL
;
436 sec
->rawsize
= sec
->size
;
437 if (sec
->flags
& SEC_STRINGS
)
438 memset (secinfo
->contents
+ sec
->size
, 0, sec
->entsize
);
439 if (! bfd_get_section_contents (sec
->owner
, sec
, secinfo
->contents
,
450 /* Record one section into the hash table. */
452 record_section (struct sec_merge_info
*sinfo
,
453 struct sec_merge_sec_info
*secinfo
)
455 asection
*sec
= secinfo
->sec
;
456 struct sec_merge_hash_entry
*entry
;
458 unsigned char *p
, *end
;
459 bfd_vma mask
, eltalign
;
460 unsigned int align
, i
;
462 align
= sec
->alignment_power
;
463 end
= secinfo
->contents
+ sec
->size
;
465 mask
= ((bfd_vma
) 1 << align
) - 1;
466 if (sec
->flags
& SEC_STRINGS
)
468 for (p
= secinfo
->contents
; p
< end
; )
470 eltalign
= p
- secinfo
->contents
;
471 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
472 if (!eltalign
|| eltalign
> mask
)
474 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
479 if (sec
->entsize
== 1)
481 while (p
< end
&& *p
== 0)
483 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
486 entry
= sec_merge_add (sinfo
->htab
, "",
487 (unsigned) mask
+ 1, secinfo
);
498 for (i
= 0; i
< sec
->entsize
; i
++)
501 if (i
!= sec
->entsize
)
503 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
506 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
507 (unsigned) mask
+ 1, secinfo
);
518 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
520 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
529 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
530 *secinfo
->psecinfo
= NULL
;
535 strrevcmp (const void *a
, const void *b
)
537 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
538 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
539 unsigned int lenA
= A
->len
;
540 unsigned int lenB
= B
->len
;
541 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
542 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
543 int l
= lenA
< lenB
? lenA
: lenB
;
548 return (int) *s
- (int) *t
;
556 /* Like strrevcmp, but for the case where all strings have the same
557 alignment > entsize. */
560 strrevcmp_align (const void *a
, const void *b
)
562 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
563 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
564 unsigned int lenA
= A
->len
;
565 unsigned int lenB
= B
->len
;
566 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
567 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
568 int l
= lenA
< lenB
? lenA
: lenB
;
569 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
577 return (int) *s
- (int) *t
;
586 is_suffix (const struct sec_merge_hash_entry
*A
,
587 const struct sec_merge_hash_entry
*B
)
589 if (A
->len
<= B
->len
)
590 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
591 not to be equal by the hash table. */
594 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
595 B
->root
.string
, B
->len
) == 0;
598 /* This is a helper function for _bfd_merge_sections. It attempts to
599 merge strings matching suffixes of longer strings. */
601 merge_strings (struct sec_merge_info
*sinfo
)
603 struct sec_merge_hash_entry
**array
, **a
, *e
;
604 struct sec_merge_sec_info
*secinfo
;
605 bfd_size_type size
, amt
;
606 unsigned int alignment
= 0;
608 /* Now sort the strings */
609 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
610 array
= (struct sec_merge_hash_entry
**) bfd_malloc (amt
);
614 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
618 /* Adjust the length to not include the zero terminator. */
619 e
->len
-= sinfo
->htab
->entsize
;
620 if (alignment
!= e
->alignment
)
623 alignment
= e
->alignment
;
625 alignment
= (unsigned) -1;
629 sinfo
->htab
->size
= a
- array
;
630 if (sinfo
->htab
->size
!= 0)
632 qsort (array
, (size_t) sinfo
->htab
->size
,
633 sizeof (struct sec_merge_hash_entry
*),
634 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
635 ? strrevcmp_align
: strrevcmp
));
637 /* Loop over the sorted array and merge suffixes */
639 e
->len
+= sinfo
->htab
->entsize
;
642 struct sec_merge_hash_entry
*cmp
= *a
;
644 cmp
->len
+= sinfo
->htab
->entsize
;
645 if (e
->alignment
>= cmp
->alignment
646 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
647 && is_suffix (e
, cmp
))
661 /* Now assign positions to the strings we want to keep. */
663 secinfo
= sinfo
->htab
->first
->secinfo
;
664 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
666 if (e
->secinfo
!= secinfo
)
668 secinfo
->sec
->size
= size
;
669 secinfo
= e
->secinfo
;
673 if (e
->secinfo
->first_str
== NULL
)
675 e
->secinfo
->first_str
= e
;
678 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
683 secinfo
->sec
->size
= size
;
684 if (secinfo
->sec
->alignment_power
!= 0)
686 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
687 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
690 /* And now adjust the rest, removing them from the chain (but not hashtable)
692 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
700 e
->secinfo
= e
->u
.suffix
->secinfo
;
701 e
->alignment
= e
->u
.suffix
->alignment
;
702 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
707 /* This function is called once after all SEC_MERGE sections are registered
708 with _bfd_merge_section. */
711 _bfd_merge_sections (bfd
*abfd
,
712 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
714 void (*remove_hook
) (bfd
*, asection
*))
716 struct sec_merge_info
*sinfo
;
718 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
720 struct sec_merge_sec_info
* secinfo
;
725 /* Move sinfo->chain to head of the chain, terminate it. */
726 secinfo
= sinfo
->chain
;
727 sinfo
->chain
= secinfo
->next
;
728 secinfo
->next
= NULL
;
730 /* Record the sections into the hash table. */
731 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
732 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
734 *secinfo
->psecinfo
= NULL
;
736 (*remove_hook
) (abfd
, secinfo
->sec
);
738 else if (! record_section (sinfo
, secinfo
))
744 if (sinfo
->htab
->first
== NULL
)
747 if (sinfo
->htab
->strings
)
748 merge_strings (sinfo
);
751 struct sec_merge_hash_entry
*e
;
752 bfd_size_type size
= 0;
754 /* Things are much simpler for non-strings.
755 Just assign them slots in the section. */
757 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
759 if (e
->secinfo
->first_str
== NULL
)
762 secinfo
->sec
->size
= size
;
763 e
->secinfo
->first_str
= e
;
766 size
= (size
+ e
->alignment
- 1)
767 & ~((bfd_vma
) e
->alignment
- 1);
770 secinfo
= e
->secinfo
;
772 secinfo
->sec
->size
= size
;
775 /* Finally remove all input sections which have not made it into
776 the hash table at all. */
777 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
778 if (secinfo
->first_str
== NULL
)
779 secinfo
->sec
->flags
|= SEC_EXCLUDE
| SEC_KEEP
;
785 /* Write out the merged section. */
788 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
790 struct sec_merge_sec_info
*secinfo
;
793 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
798 if (secinfo
->first_str
== NULL
)
801 /* FIXME: octets_per_byte. */
802 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
803 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
806 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
))
812 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
813 *PSEC, this returns the new offset in the adjusted SEC_MERGE
814 section and writes the new section back into *PSEC. */
817 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
818 void *psecinfo
, bfd_vma offset
)
820 struct sec_merge_sec_info
*secinfo
;
821 struct sec_merge_hash_entry
*entry
;
823 asection
*sec
= *psec
;
825 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
830 if (offset
>= sec
->rawsize
)
832 if (offset
> sec
->rawsize
)
834 (*_bfd_error_handler
)
835 (_("%s: access beyond end of merged section (%ld)"),
836 bfd_get_filename (sec
->owner
), (long) offset
);
838 return secinfo
->first_str
? sec
->size
: 0;
841 if (secinfo
->htab
->strings
)
843 if (sec
->entsize
== 1)
845 p
= secinfo
->contents
+ offset
- 1;
846 while (p
>= secinfo
->contents
&& *p
)
852 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
854 while (p
>= secinfo
->contents
)
858 for (i
= 0; i
< sec
->entsize
; ++i
)
861 if (i
== sec
->entsize
)
870 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
872 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
875 if (! secinfo
->htab
->strings
)
877 /* This should only happen if somebody points into the padding
878 after a NUL character but before next entity. */
881 if (! secinfo
->htab
->first
)
883 entry
= secinfo
->htab
->first
;
884 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
888 *psec
= entry
->secinfo
->sec
;
889 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);