2 Copyright 2001, 2002, 2003, 2004, 2005, 2006
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 2 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, MA 02110-1301, USA. */
22 /* This file contains support for merging duplicate entities within sections,
23 as used in ELF SHF_MERGE. */
29 #include "libiberty.h"
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. This includes the zero terminator. */
40 /* Start of this string needs to be aligned to
41 alignment octets (not 1 << align). */
42 unsigned int alignment
;
45 /* Index within the merged section. */
47 /* Entry this is a suffix of (if alignment is 0). */
48 struct sec_merge_hash_entry
*suffix
;
50 /* Which section is it in. */
51 struct sec_merge_sec_info
*secinfo
;
52 /* Next entity in the hash table. */
53 struct sec_merge_hash_entry
*next
;
56 /* The section merge hash table. */
60 struct bfd_hash_table table
;
61 /* Next available index. */
63 /* First entity in the SEC_MERGE sections of this type. */
64 struct sec_merge_hash_entry
*first
;
65 /* Last entity in the SEC_MERGE sections of this type. */
66 struct sec_merge_hash_entry
*last
;
69 /* Are entries fixed size or zero terminated strings? */
75 /* Chain of sec_merge_infos. */
76 struct sec_merge_info
*next
;
77 /* Chain of sec_merge_sec_infos. */
78 struct sec_merge_sec_info
*chain
;
79 /* A hash table used to hold section content. */
80 struct sec_merge_hash
*htab
;
83 struct sec_merge_sec_info
85 /* Chain of sec_merge_sec_infos. */
86 struct sec_merge_sec_info
*next
;
87 /* The corresponding section. */
89 /* Pointer to merge_info pointing to us. */
91 /* A hash table used to hold section content. */
92 struct sec_merge_hash
*htab
;
93 /* First string in this section. */
94 struct sec_merge_hash_entry
*first_str
;
95 /* Original section content. */
96 unsigned char contents
[1];
100 /* Routine to create an entry in a section merge hashtab. */
102 static struct bfd_hash_entry
*
103 sec_merge_hash_newfunc (struct bfd_hash_entry
*entry
,
104 struct bfd_hash_table
*table
, const char *string
)
106 /* Allocate the structure if it has not already been allocated by a
109 entry
= bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
));
113 /* Call the allocation method of the superclass. */
114 entry
= bfd_hash_newfunc (entry
, table
, string
);
118 /* Initialize the local fields. */
119 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
121 ret
->u
.suffix
= NULL
;
130 /* Look up an entry in a section merge hash table. */
132 static struct sec_merge_hash_entry
*
133 sec_merge_hash_lookup (struct sec_merge_hash
*table
, const char *string
,
134 unsigned int alignment
, bfd_boolean create
)
136 register const unsigned char *s
;
137 register unsigned long hash
;
138 register unsigned int c
;
139 struct sec_merge_hash_entry
*hashp
;
145 s
= (const unsigned char *) string
;
148 if (table
->entsize
== 1)
150 while ((c
= *s
++) != '\0')
152 hash
+= c
+ (c
<< 17);
156 hash
+= len
+ (len
<< 17);
162 for (i
= 0; i
< table
->entsize
; ++i
)
165 if (i
== table
->entsize
)
167 for (i
= 0; i
< table
->entsize
; ++i
)
170 hash
+= c
+ (c
<< 17);
175 hash
+= len
+ (len
<< 17);
176 len
*= table
->entsize
;
179 len
+= table
->entsize
;
183 for (i
= 0; i
< table
->entsize
; ++i
)
186 hash
+= c
+ (c
<< 17);
189 len
= table
->entsize
;
192 index
= hash
% table
->table
.size
;
193 for (hashp
= (struct sec_merge_hash_entry
*) table
->table
.table
[index
];
195 hashp
= (struct sec_merge_hash_entry
*) hashp
->root
.next
)
197 if (hashp
->root
.hash
== hash
199 && memcmp (hashp
->root
.string
, string
, len
) == 0)
201 /* If the string we found does not have at least the required
202 alignment, we need to insert another copy. */
203 if (hashp
->alignment
< alignment
)
207 /* Mark the less aligned copy as deleted. */
209 hashp
->alignment
= 0;
220 hashp
= ((struct sec_merge_hash_entry
*)
221 sec_merge_hash_newfunc (NULL
, &table
->table
, string
));
224 hashp
->root
.string
= string
;
225 hashp
->root
.hash
= hash
;
227 hashp
->alignment
= alignment
;
228 hashp
->root
.next
= table
->table
.table
[index
];
229 table
->table
.table
[index
] = (struct bfd_hash_entry
*) hashp
;
234 /* Create a new hash table. */
236 static struct sec_merge_hash
*
237 sec_merge_init (unsigned int entsize
, bfd_boolean strings
)
239 struct sec_merge_hash
*table
;
241 table
= bfd_malloc (sizeof (struct sec_merge_hash
));
245 if (! bfd_hash_table_init_n (&table
->table
, sec_merge_hash_newfunc
,
246 sizeof (struct sec_merge_hash_entry
), 16699))
255 table
->entsize
= entsize
;
256 table
->strings
= strings
;
261 /* Get the index of an entity in a hash table, adding it if it is not
264 static struct sec_merge_hash_entry
*
265 sec_merge_add (struct sec_merge_hash
*tab
, const char *str
,
266 unsigned int alignment
, struct sec_merge_sec_info
*secinfo
)
268 register struct sec_merge_hash_entry
*entry
;
270 entry
= sec_merge_hash_lookup (tab
, str
, alignment
, TRUE
);
274 if (entry
->secinfo
== NULL
)
277 entry
->secinfo
= secinfo
;
278 if (tab
->first
== NULL
)
281 tab
->last
->next
= entry
;
289 sec_merge_emit (bfd
*abfd
, struct sec_merge_hash_entry
*entry
)
291 struct sec_merge_sec_info
*secinfo
= entry
->secinfo
;
292 asection
*sec
= secinfo
->sec
;
294 bfd_size_type off
= 0;
295 int alignment_power
= sec
->output_section
->alignment_power
;
299 pad
= bfd_zmalloc ((bfd_size_type
) 1 << alignment_power
);
304 for (; entry
!= NULL
&& entry
->secinfo
== secinfo
; entry
= entry
->next
)
309 len
= -off
& (entry
->alignment
- 1);
312 if (bfd_bwrite (pad
, len
, abfd
) != len
)
317 str
= entry
->root
.string
;
320 if (bfd_bwrite (str
, len
, abfd
) != len
)
326 /* Trailing alignment needed? */
327 off
= sec
->size
- off
;
329 && bfd_bwrite (pad
, off
, abfd
) != off
)
342 /* Register a SEC_MERGE section as a candidate for merging.
343 This function is called for all non-dynamic SEC_MERGE input sections. */
346 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
349 struct sec_merge_info
*sinfo
;
350 struct sec_merge_sec_info
*secinfo
;
354 if ((abfd
->flags
& DYNAMIC
) != 0
355 || (sec
->flags
& SEC_MERGE
) == 0)
359 || (sec
->flags
& SEC_EXCLUDE
) != 0
360 || sec
->entsize
== 0)
363 if ((sec
->flags
& SEC_RELOC
) != 0)
365 /* We aren't prepared to handle relocations in merged sections. */
369 align
= sec
->alignment_power
;
370 if ((sec
->entsize
< (unsigned) 1 << align
371 && ((sec
->entsize
& (sec
->entsize
- 1))
372 || !(sec
->flags
& SEC_STRINGS
)))
373 || (sec
->entsize
> (unsigned) 1 << align
374 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
376 /* Sanity check. If string character size is smaller than
377 alignment, then we require character size to be a power
378 of 2, otherwise character size must be integer multiple
379 of alignment. For non-string constants, alignment must
380 be smaller than or equal to entity size and entity size
381 must be integer multiple of alignment. */
385 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
386 if ((secinfo
= sinfo
->chain
)
387 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
388 && secinfo
->sec
->entsize
== sec
->entsize
389 && secinfo
->sec
->alignment_power
== sec
->alignment_power
390 && secinfo
->sec
->output_section
== sec
->output_section
)
395 /* Initialize the information we need to keep track of. */
396 sinfo
= bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
399 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
402 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
403 if (sinfo
->htab
== NULL
)
407 /* Read the section from abfd. */
409 amt
= sizeof (struct sec_merge_sec_info
) + sec
->size
- 1;
410 *psecinfo
= bfd_alloc (abfd
, amt
);
411 if (*psecinfo
== NULL
)
414 secinfo
= (struct sec_merge_sec_info
*) *psecinfo
;
417 secinfo
->next
= sinfo
->chain
->next
;
418 sinfo
->chain
->next
= secinfo
;
421 secinfo
->next
= secinfo
;
422 sinfo
->chain
= secinfo
;
424 secinfo
->psecinfo
= psecinfo
;
425 secinfo
->htab
= sinfo
->htab
;
426 secinfo
->first_str
= NULL
;
428 sec
->rawsize
= sec
->size
;
429 if (! bfd_get_section_contents (sec
->owner
, sec
, secinfo
->contents
,
440 /* Record one section into the hash table. */
442 record_section (struct sec_merge_info
*sinfo
,
443 struct sec_merge_sec_info
*secinfo
)
445 asection
*sec
= secinfo
->sec
;
446 struct sec_merge_hash_entry
*entry
;
448 unsigned char *p
, *end
;
449 bfd_vma mask
, eltalign
;
450 unsigned int align
, i
;
452 align
= sec
->alignment_power
;
453 end
= secinfo
->contents
+ sec
->size
;
455 mask
= ((bfd_vma
) 1 << align
) - 1;
456 if (sec
->flags
& SEC_STRINGS
)
458 for (p
= secinfo
->contents
; p
< end
; )
460 eltalign
= p
- secinfo
->contents
;
461 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
462 if (!eltalign
|| eltalign
> mask
)
464 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
469 if (sec
->entsize
== 1)
471 while (p
< end
&& *p
== 0)
473 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
476 entry
= sec_merge_add (sinfo
->htab
, "",
477 (unsigned) mask
+ 1, secinfo
);
488 for (i
= 0; i
< sec
->entsize
; i
++)
491 if (i
!= sec
->entsize
)
493 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
496 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
497 (unsigned) mask
+ 1, secinfo
);
508 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
510 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
519 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
520 *secinfo
->psecinfo
= NULL
;
525 strrevcmp (const void *a
, const void *b
)
527 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
528 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
529 unsigned int lenA
= A
->len
;
530 unsigned int lenB
= B
->len
;
531 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
532 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
533 int l
= lenA
< lenB
? lenA
: lenB
;
538 return (int) *s
- (int) *t
;
546 /* Like strrevcmp, but for the case where all strings have the same
547 alignment > entsize. */
550 strrevcmp_align (const void *a
, const void *b
)
552 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
553 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
554 unsigned int lenA
= A
->len
;
555 unsigned int lenB
= B
->len
;
556 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
557 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
558 int l
= lenA
< lenB
? lenA
: lenB
;
559 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
567 return (int) *s
- (int) *t
;
576 is_suffix (const struct sec_merge_hash_entry
*A
,
577 const struct sec_merge_hash_entry
*B
)
579 if (A
->len
<= B
->len
)
580 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
581 not to be equal by the hash table. */
584 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
585 B
->root
.string
, B
->len
) == 0;
588 /* This is a helper function for _bfd_merge_sections. It attempts to
589 merge strings matching suffixes of longer strings. */
591 merge_strings (struct sec_merge_info
*sinfo
)
593 struct sec_merge_hash_entry
**array
, **a
, *e
;
594 struct sec_merge_sec_info
*secinfo
;
595 bfd_size_type size
, amt
;
596 unsigned int alignment
= 0;
598 /* Now sort the strings */
599 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
600 array
= bfd_malloc (amt
);
604 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
608 /* Adjust the length to not include the zero terminator. */
609 e
->len
-= sinfo
->htab
->entsize
;
610 if (alignment
!= e
->alignment
)
613 alignment
= e
->alignment
;
615 alignment
= (unsigned) -1;
619 sinfo
->htab
->size
= a
- array
;
620 if (sinfo
->htab
->size
!= 0)
622 qsort (array
, (size_t) sinfo
->htab
->size
,
623 sizeof (struct sec_merge_hash_entry
*),
624 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
625 ? strrevcmp_align
: strrevcmp
));
627 /* Loop over the sorted array and merge suffixes */
629 e
->len
+= sinfo
->htab
->entsize
;
632 struct sec_merge_hash_entry
*cmp
= *a
;
634 cmp
->len
+= sinfo
->htab
->entsize
;
635 if (e
->alignment
>= cmp
->alignment
636 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
637 && is_suffix (e
, cmp
))
651 /* Now assign positions to the strings we want to keep. */
653 secinfo
= sinfo
->htab
->first
->secinfo
;
654 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
656 if (e
->secinfo
!= secinfo
)
658 secinfo
->sec
->size
= size
;
659 secinfo
= e
->secinfo
;
663 if (e
->secinfo
->first_str
== NULL
)
665 e
->secinfo
->first_str
= e
;
668 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
673 secinfo
->sec
->size
= size
;
674 if (secinfo
->sec
->alignment_power
!= 0)
676 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
677 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
680 /* And now adjust the rest, removing them from the chain (but not hashtable)
682 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
690 e
->secinfo
= e
->u
.suffix
->secinfo
;
691 e
->alignment
= e
->u
.suffix
->alignment
;
692 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
697 /* This function is called once after all SEC_MERGE sections are registered
698 with _bfd_merge_section. */
701 _bfd_merge_sections (bfd
*abfd ATTRIBUTE_UNUSED
,
702 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
704 void (*remove_hook
) (bfd
*, asection
*))
706 struct sec_merge_info
*sinfo
;
708 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
710 struct sec_merge_sec_info
* secinfo
;
715 /* Move sinfo->chain to head of the chain, terminate it. */
716 secinfo
= sinfo
->chain
;
717 sinfo
->chain
= secinfo
->next
;
718 secinfo
->next
= NULL
;
720 /* Record the sections into the hash table. */
721 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
722 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
724 *secinfo
->psecinfo
= NULL
;
726 (*remove_hook
) (abfd
, secinfo
->sec
);
728 else if (! record_section (sinfo
, secinfo
))
734 if (sinfo
->htab
->first
== NULL
)
737 if (sinfo
->htab
->strings
)
738 merge_strings (sinfo
);
741 struct sec_merge_hash_entry
*e
;
742 bfd_size_type size
= 0;
744 /* Things are much simpler for non-strings.
745 Just assign them slots in the section. */
747 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
749 if (e
->secinfo
->first_str
== NULL
)
752 secinfo
->sec
->size
= size
;
753 e
->secinfo
->first_str
= e
;
756 size
= (size
+ e
->alignment
- 1)
757 & ~((bfd_vma
) e
->alignment
- 1);
760 secinfo
= e
->secinfo
;
762 secinfo
->sec
->size
= size
;
765 /* Finally remove all input sections which have not made it into
766 the hash table at all. */
767 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
768 if (secinfo
->first_str
== NULL
)
769 secinfo
->sec
->flags
|= SEC_EXCLUDE
;
775 /* Write out the merged section. */
778 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
780 struct sec_merge_sec_info
*secinfo
;
783 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
785 if (secinfo
->first_str
== NULL
)
788 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
789 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
792 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
))
798 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
799 *PSEC, this returns the new offset in the adjusted SEC_MERGE
800 section and writes the new section back into *PSEC. */
803 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
804 void *psecinfo
, bfd_vma offset
)
806 struct sec_merge_sec_info
*secinfo
;
807 struct sec_merge_hash_entry
*entry
;
809 asection
*sec
= *psec
;
811 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
813 if (offset
>= sec
->rawsize
)
815 if (offset
> sec
->rawsize
)
817 (*_bfd_error_handler
)
818 (_("%s: access beyond end of merged section (%ld)"),
819 bfd_get_filename (sec
->owner
), (long) offset
);
821 return secinfo
->first_str
? sec
->size
: 0;
824 if (secinfo
->htab
->strings
)
826 if (sec
->entsize
== 1)
828 p
= secinfo
->contents
+ offset
- 1;
829 while (p
>= secinfo
->contents
&& *p
)
835 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
837 while (p
>= secinfo
->contents
)
841 for (i
= 0; i
< sec
->entsize
; ++i
)
844 if (i
== sec
->entsize
)
853 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
855 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
858 if (! secinfo
->htab
->strings
)
860 /* This should only happen if somebody points into the padding
861 after a NUL character but before next entity. */
864 if (! secinfo
->htab
->first
)
866 entry
= secinfo
->htab
->first
;
867 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
871 *psec
= entry
->secinfo
->sec
;
872 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);