2 Copyright 2001, 2002, 2003, 2004, 2005 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 2 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
21 /* This file contains support for merging duplicate entities within sections,
22 as used in ELF SHF_MERGE. */
28 #include "libiberty.h"
30 struct sec_merge_sec_info
;
32 /* An entry in the section merge hash table. */
34 struct sec_merge_hash_entry
36 struct bfd_hash_entry root
;
37 /* Length of this entry. This includes the zero terminator. */
39 /* Start of this string needs to be aligned to
40 alignment octets (not 1 << align). */
41 unsigned int alignment
;
44 /* Index within the merged section. */
46 /* Entry this is a suffix of (if alignment is 0). */
47 struct sec_merge_hash_entry
*suffix
;
49 /* Which section is it in. */
50 struct sec_merge_sec_info
*secinfo
;
51 /* Next entity in the hash table. */
52 struct sec_merge_hash_entry
*next
;
55 /* The section merge hash table. */
59 struct bfd_hash_table table
;
60 /* Next available index. */
62 /* First entity in the SEC_MERGE sections of this type. */
63 struct sec_merge_hash_entry
*first
;
64 /* Last entity in the SEC_MERGE sections of this type. */
65 struct sec_merge_hash_entry
*last
;
68 /* Are entries fixed size or zero terminated strings? */
74 /* Chain of sec_merge_infos. */
75 struct sec_merge_info
*next
;
76 /* Chain of sec_merge_sec_infos. */
77 struct sec_merge_sec_info
*chain
;
78 /* A hash table used to hold section content. */
79 struct sec_merge_hash
*htab
;
82 struct sec_merge_sec_info
84 /* Chain of sec_merge_sec_infos. */
85 struct sec_merge_sec_info
*next
;
86 /* The corresponding section. */
88 /* Pointer to merge_info pointing to us. */
90 /* A hash table used to hold section content. */
91 struct sec_merge_hash
*htab
;
92 /* First string in this section. */
93 struct sec_merge_hash_entry
*first_str
;
94 /* Original section content. */
95 unsigned char contents
[1];
99 /* Routine to create an entry in a section merge hashtab. */
101 static struct bfd_hash_entry
*
102 sec_merge_hash_newfunc (struct bfd_hash_entry
*entry
,
103 struct bfd_hash_table
*table
, const char *string
)
105 /* Allocate the structure if it has not already been allocated by a
108 entry
= bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
));
112 /* Call the allocation method of the superclass. */
113 entry
= bfd_hash_newfunc (entry
, table
, string
);
117 /* Initialize the local fields. */
118 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
120 ret
->u
.suffix
= NULL
;
129 /* Look up an entry in a section merge hash table. */
131 static struct sec_merge_hash_entry
*
132 sec_merge_hash_lookup (struct sec_merge_hash
*table
, const char *string
,
133 unsigned int alignment
, bfd_boolean create
)
135 register const unsigned char *s
;
136 register unsigned long hash
;
137 register unsigned int c
;
138 struct sec_merge_hash_entry
*hashp
;
144 s
= (const unsigned char *) string
;
147 if (table
->entsize
== 1)
149 while ((c
= *s
++) != '\0')
151 hash
+= c
+ (c
<< 17);
155 hash
+= len
+ (len
<< 17);
161 for (i
= 0; i
< table
->entsize
; ++i
)
164 if (i
== table
->entsize
)
166 for (i
= 0; i
< table
->entsize
; ++i
)
169 hash
+= c
+ (c
<< 17);
174 hash
+= len
+ (len
<< 17);
175 len
*= table
->entsize
;
178 len
+= table
->entsize
;
182 for (i
= 0; i
< table
->entsize
; ++i
)
185 hash
+= c
+ (c
<< 17);
188 len
= table
->entsize
;
191 index
= hash
% table
->table
.size
;
192 for (hashp
= (struct sec_merge_hash_entry
*) table
->table
.table
[index
];
194 hashp
= (struct sec_merge_hash_entry
*) hashp
->root
.next
)
196 if (hashp
->root
.hash
== hash
198 && memcmp (hashp
->root
.string
, string
, len
) == 0)
200 /* If the string we found does not have at least the required
201 alignment, we need to insert another copy. */
202 if (hashp
->alignment
< alignment
)
206 /* Mark the less aligned copy as deleted. */
208 hashp
->alignment
= 0;
219 hashp
= ((struct sec_merge_hash_entry
*)
220 sec_merge_hash_newfunc (NULL
, &table
->table
, string
));
223 hashp
->root
.string
= string
;
224 hashp
->root
.hash
= hash
;
226 hashp
->alignment
= alignment
;
227 hashp
->root
.next
= table
->table
.table
[index
];
228 table
->table
.table
[index
] = (struct bfd_hash_entry
*) hashp
;
233 /* Create a new hash table. */
235 static struct sec_merge_hash
*
236 sec_merge_init (unsigned int entsize
, bfd_boolean strings
)
238 struct sec_merge_hash
*table
;
240 table
= bfd_malloc (sizeof (struct sec_merge_hash
));
244 if (! bfd_hash_table_init (&table
->table
, sec_merge_hash_newfunc
))
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 register 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
= 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 if (bfd_bwrite (pad
, len
, abfd
) != len
)
315 str
= entry
->root
.string
;
318 if (bfd_bwrite (str
, len
, abfd
) != len
)
324 /* Trailing alignment needed? */
325 off
= sec
->size
- off
;
327 && bfd_bwrite (pad
, off
, abfd
) != off
)
340 /* Register a SEC_MERGE section as a candidate for merging.
341 This function is called for all non-dynamic SEC_MERGE input sections. */
344 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
347 struct sec_merge_info
*sinfo
;
348 struct sec_merge_sec_info
*secinfo
;
352 if ((abfd
->flags
& DYNAMIC
) != 0
353 || (sec
->flags
& SEC_MERGE
) == 0)
357 || (sec
->flags
& SEC_EXCLUDE
) != 0
358 || sec
->entsize
== 0)
361 if ((sec
->flags
& SEC_RELOC
) != 0)
363 /* We aren't prepared to handle relocations in merged sections. */
367 align
= sec
->alignment_power
;
368 if ((sec
->entsize
< (unsigned) 1 << align
369 && ((sec
->entsize
& (sec
->entsize
- 1))
370 || !(sec
->flags
& SEC_STRINGS
)))
371 || (sec
->entsize
> (unsigned) 1 << align
372 && (sec
->entsize
& (((unsigned) 1 << align
) - 1))))
374 /* Sanity check. If string character size is smaller than
375 alignment, then we require character size to be a power
376 of 2, otherwise character size must be integer multiple
377 of alignment. For non-string constants, alignment must
378 be smaller than or equal to entity size and entity size
379 must be integer multiple of alignment. */
383 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
384 if ((secinfo
= sinfo
->chain
)
385 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
386 && secinfo
->sec
->entsize
== sec
->entsize
387 && secinfo
->sec
->alignment_power
== sec
->alignment_power
388 && secinfo
->sec
->output_section
== sec
->output_section
)
393 /* Initialize the information we need to keep track of. */
394 sinfo
= bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
397 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
400 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
401 if (sinfo
->htab
== NULL
)
405 /* Read the section from abfd. */
407 amt
= sizeof (struct sec_merge_sec_info
) + sec
->size
- 1;
408 *psecinfo
= bfd_alloc (abfd
, amt
);
409 if (*psecinfo
== NULL
)
412 secinfo
= (struct sec_merge_sec_info
*) *psecinfo
;
415 secinfo
->next
= sinfo
->chain
->next
;
416 sinfo
->chain
->next
= secinfo
;
419 secinfo
->next
= secinfo
;
420 sinfo
->chain
= secinfo
;
422 secinfo
->psecinfo
= psecinfo
;
423 secinfo
->htab
= sinfo
->htab
;
424 secinfo
->first_str
= NULL
;
426 sec
->rawsize
= sec
->size
;
427 if (! bfd_get_section_contents (sec
->owner
, sec
, secinfo
->contents
,
438 /* Record one section into the hash table. */
440 record_section (struct sec_merge_info
*sinfo
,
441 struct sec_merge_sec_info
*secinfo
)
443 asection
*sec
= secinfo
->sec
;
444 struct sec_merge_hash_entry
*entry
;
446 unsigned char *p
, *end
;
447 bfd_vma mask
, eltalign
;
448 unsigned int align
, i
;
450 align
= sec
->alignment_power
;
451 end
= secinfo
->contents
+ sec
->size
;
453 mask
= ((bfd_vma
) 1 << align
) - 1;
454 if (sec
->flags
& SEC_STRINGS
)
456 for (p
= secinfo
->contents
; p
< end
; )
458 eltalign
= p
- secinfo
->contents
;
459 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
460 if (!eltalign
|| eltalign
> mask
)
462 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, (unsigned) eltalign
,
467 if (sec
->entsize
== 1)
469 while (p
< end
&& *p
== 0)
471 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
474 entry
= sec_merge_add (sinfo
->htab
, "",
475 (unsigned) mask
+ 1, secinfo
);
486 for (i
= 0; i
< sec
->entsize
; i
++)
489 if (i
!= sec
->entsize
)
491 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
494 entry
= sec_merge_add (sinfo
->htab
, (char *) p
,
495 (unsigned) mask
+ 1, secinfo
);
506 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
508 entry
= sec_merge_add (sinfo
->htab
, (char *) p
, 1, secinfo
);
517 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
518 *secinfo
->psecinfo
= NULL
;
523 strrevcmp (const void *a
, const void *b
)
525 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
526 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
527 unsigned int lenA
= A
->len
;
528 unsigned int lenB
= B
->len
;
529 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
530 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
531 int l
= lenA
< lenB
? lenA
: lenB
;
536 return (int) *s
- (int) *t
;
544 /* Like strrevcmp, but for the case where all strings have the same
545 alignment > entsize. */
548 strrevcmp_align (const void *a
, const void *b
)
550 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
551 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
552 unsigned int lenA
= A
->len
;
553 unsigned int lenB
= B
->len
;
554 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
555 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
556 int l
= lenA
< lenB
? lenA
: lenB
;
557 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
565 return (int) *s
- (int) *t
;
574 is_suffix (const struct sec_merge_hash_entry
*A
,
575 const struct sec_merge_hash_entry
*B
)
577 if (A
->len
<= B
->len
)
578 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
579 not to be equal by the hash table. */
582 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
583 B
->root
.string
, B
->len
) == 0;
586 /* This is a helper function for _bfd_merge_sections. It attempts to
587 merge strings matching suffixes of longer strings. */
589 merge_strings (struct sec_merge_info
*sinfo
)
591 struct sec_merge_hash_entry
**array
, **a
, *e
;
592 struct sec_merge_sec_info
*secinfo
;
593 bfd_size_type size
, amt
;
594 unsigned int alignment
= 0;
596 /* Now sort the strings */
597 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
598 array
= bfd_malloc (amt
);
602 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
606 /* Adjust the length to not include the zero terminator. */
607 e
->len
-= sinfo
->htab
->entsize
;
608 if (alignment
!= e
->alignment
)
611 alignment
= e
->alignment
;
613 alignment
= (unsigned) -1;
617 sinfo
->htab
->size
= a
- array
;
618 if (sinfo
->htab
->size
!= 0)
620 qsort (array
, (size_t) sinfo
->htab
->size
,
621 sizeof (struct sec_merge_hash_entry
*),
622 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
623 ? strrevcmp_align
: strrevcmp
));
625 /* Loop over the sorted array and merge suffixes */
627 e
->len
+= sinfo
->htab
->entsize
;
630 struct sec_merge_hash_entry
*cmp
= *a
;
632 cmp
->len
+= sinfo
->htab
->entsize
;
633 if (e
->alignment
>= cmp
->alignment
634 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
635 && is_suffix (e
, cmp
))
649 /* Now assign positions to the strings we want to keep. */
651 secinfo
= sinfo
->htab
->first
->secinfo
;
652 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
654 if (e
->secinfo
!= secinfo
)
656 secinfo
->sec
->size
= size
;
657 secinfo
= e
->secinfo
;
661 if (e
->secinfo
->first_str
== NULL
)
663 e
->secinfo
->first_str
= e
;
666 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
671 secinfo
->sec
->size
= size
;
672 if (secinfo
->sec
->alignment_power
!= 0)
674 bfd_size_type align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
675 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
678 /* And now adjust the rest, removing them from the chain (but not hashtable)
680 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
688 e
->secinfo
= e
->u
.suffix
->secinfo
;
689 e
->alignment
= e
->u
.suffix
->alignment
;
690 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
695 /* This function is called once after all SEC_MERGE sections are registered
696 with _bfd_merge_section. */
699 _bfd_merge_sections (bfd
*abfd ATTRIBUTE_UNUSED
, struct bfd_link_info
*info
,
700 void *xsinfo
, void (*remove_hook
) (bfd
*, asection
*))
702 struct sec_merge_info
*sinfo
;
704 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
706 struct sec_merge_sec_info
* secinfo
;
711 /* Move sinfo->chain to head of the chain, terminate it. */
712 secinfo
= sinfo
->chain
;
713 sinfo
->chain
= secinfo
->next
;
714 secinfo
->next
= NULL
;
716 /* Record the sections into the hash table. */
717 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
718 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
720 *secinfo
->psecinfo
= NULL
;
722 (*remove_hook
) (abfd
, secinfo
->sec
);
724 else if (! record_section (sinfo
, secinfo
))
730 if (sinfo
->htab
->first
== NULL
)
733 if (sinfo
->htab
->strings
)
734 merge_strings (sinfo
);
737 struct sec_merge_hash_entry
*e
;
738 bfd_size_type size
= 0;
740 /* Things are much simpler for non-strings.
741 Just assign them slots in the section. */
743 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
745 if (e
->secinfo
->first_str
== NULL
)
748 secinfo
->sec
->size
= size
;
749 e
->secinfo
->first_str
= e
;
752 size
= (size
+ e
->alignment
- 1)
753 & ~((bfd_vma
) e
->alignment
- 1);
756 secinfo
= e
->secinfo
;
758 secinfo
->sec
->size
= size
;
761 /* Finally remove all input sections which have not made it into
762 the hash table at all. */
763 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
764 if (secinfo
->first_str
== NULL
)
765 _bfd_strip_section_from_output (info
, secinfo
->sec
);
771 /* Write out the merged section. */
774 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
776 struct sec_merge_sec_info
*secinfo
;
779 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
781 if (secinfo
->first_str
== NULL
)
784 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
785 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
788 if (! sec_merge_emit (output_bfd
, secinfo
->first_str
))
794 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
795 *PSEC, this returns the new offset in the adjusted SEC_MERGE
796 section and writes the new section back into *PSEC. */
799 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
800 void *psecinfo
, bfd_vma offset
)
802 struct sec_merge_sec_info
*secinfo
;
803 struct sec_merge_hash_entry
*entry
;
805 asection
*sec
= *psec
;
807 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
809 if (offset
>= sec
->rawsize
)
811 if (offset
> sec
->rawsize
)
813 (*_bfd_error_handler
)
814 (_("%s: access beyond end of merged section (%ld)"),
815 bfd_get_filename (sec
->owner
), (long) offset
);
817 return secinfo
->first_str
? sec
->size
: 0;
820 if (secinfo
->htab
->strings
)
822 if (sec
->entsize
== 1)
824 p
= secinfo
->contents
+ offset
- 1;
825 while (p
>= secinfo
->contents
&& *p
)
831 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
833 while (p
>= secinfo
->contents
)
837 for (i
= 0; i
< sec
->entsize
; ++i
)
840 if (i
== sec
->entsize
)
849 p
= secinfo
->contents
+ (offset
/ sec
->entsize
) * sec
->entsize
;
851 entry
= sec_merge_hash_lookup (secinfo
->htab
, (char *) p
, 0, FALSE
);
854 if (! secinfo
->htab
->strings
)
856 /* This should only happen if somebody points into the padding
857 after a NUL character but before next entity. */
860 if (! secinfo
->htab
->first
)
862 entry
= secinfo
->htab
->first
;
863 p
= (secinfo
->contents
+ (offset
/ sec
->entsize
+ 1) * sec
->entsize
867 *psec
= entry
->secinfo
->sec
;
868 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);