2 Copyright 2001, 2002, 2003 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. */
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 /* Entity size (if present in suffix hash tables). */
48 /* Entry this is a suffix of (if alignment is 0). */
49 struct sec_merge_hash_entry
*suffix
;
51 /* Which section is it in. */
52 struct sec_merge_sec_info
*secinfo
;
53 /* Next entity in the hash table. */
54 struct sec_merge_hash_entry
*next
;
57 /* The section merge hash table. */
61 struct bfd_hash_table table
;
62 /* Next available index. */
64 /* First entity in the SEC_MERGE sections of this type. */
65 struct sec_merge_hash_entry
*first
;
66 /* Last entity in the SEC_MERGE sections of this type. */
67 struct sec_merge_hash_entry
*last
;
70 /* Are entries fixed size or zero terminated strings? */
76 /* Chain of sec_merge_infos. */
77 struct sec_merge_info
*next
;
78 /* Chain of sec_merge_sec_infos. */
79 struct sec_merge_sec_info
*chain
;
80 /* A hash table used to hold section content. */
81 struct sec_merge_hash
*htab
;
84 struct sec_merge_sec_info
86 /* Chain of sec_merge_sec_infos. */
87 struct sec_merge_sec_info
*next
;
88 /* The corresponding section. */
90 /* Pointer to merge_info pointing to us. */
92 /* A hash table used to hold section content. */
93 struct sec_merge_hash
*htab
;
94 /* First string in this section. */
95 struct sec_merge_hash_entry
*first
;
96 /* Original section content. */
97 unsigned char contents
[1];
101 /* Routine to create an entry in a section merge hashtab. */
103 static struct bfd_hash_entry
*
104 sec_merge_hash_newfunc (struct bfd_hash_entry
*entry
,
105 struct bfd_hash_table
*table
, const char *string
)
107 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
109 /* Allocate the structure if it has not already been allocated by a
111 if (ret
== (struct sec_merge_hash_entry
*) NULL
)
112 ret
= ((struct sec_merge_hash_entry
*)
113 bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
)));
114 if (ret
== (struct sec_merge_hash_entry
*) NULL
)
117 /* Call the allocation method of the superclass. */
118 ret
= ((struct sec_merge_hash_entry
*)
119 bfd_hash_newfunc ((struct bfd_hash_entry
*) ret
, table
, string
));
123 /* Initialize the local fields. */
124 ret
->u
.suffix
= NULL
;
130 return (struct bfd_hash_entry
*) ret
;
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 register const unsigned char *s
;
140 register unsigned long hash
;
141 register unsigned int c
;
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
];
197 hashp
!= (struct sec_merge_hash_entry
*) NULL
;
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
)
208 /* Mark the less aligned copy as deleted. */
210 hashp
->alignment
= 0;
218 return (struct sec_merge_hash_entry
*) NULL
;
220 hashp
= (struct sec_merge_hash_entry
*)
221 sec_merge_hash_newfunc ((struct bfd_hash_entry
*) NULL
,
222 (struct bfd_hash_table
*) table
, string
);
223 if (hashp
== (struct sec_merge_hash_entry
*) NULL
)
224 return (struct sec_merge_hash_entry
*) NULL
;
225 hashp
->root
.string
= string
;
226 hashp
->root
.hash
= hash
;
228 hashp
->alignment
= alignment
;
229 hashp
->root
.next
= table
->table
.table
[index
];
230 table
->table
.table
[index
] = (struct bfd_hash_entry
*) hashp
;
235 /* Create a new hash table. */
237 static struct sec_merge_hash
*
238 sec_merge_init (unsigned int entsize
, bfd_boolean strings
)
240 struct sec_merge_hash
*table
;
241 bfd_size_type amt
= sizeof (struct sec_merge_hash
);
243 table
= (struct sec_merge_hash
*) bfd_malloc (amt
);
247 if (! bfd_hash_table_init (&table
->table
, sec_merge_hash_newfunc
))
256 table
->entsize
= entsize
;
257 table
->strings
= strings
;
262 /* Get the index of an entity in a hash table, adding it if it is not
265 static struct sec_merge_hash_entry
*
266 sec_merge_add (struct sec_merge_hash
*tab
, const char *str
,
267 unsigned int alignment
, struct sec_merge_sec_info
*secinfo
)
269 register struct sec_merge_hash_entry
*entry
;
271 entry
= sec_merge_hash_lookup (tab
, str
, alignment
, TRUE
);
275 if (entry
->secinfo
== NULL
)
278 entry
->secinfo
= secinfo
;
279 if (tab
->first
== NULL
)
282 tab
->last
->next
= entry
;
290 sec_merge_emit (register bfd
*abfd
, struct sec_merge_hash_entry
*entry
)
292 struct sec_merge_sec_info
*secinfo
= entry
->secinfo
;
293 asection
*sec
= secinfo
->sec
;
295 bfd_size_type off
= 0;
296 int alignment_power
= bfd_get_section_alignment (abfd
, sec
->output_section
);
299 pad
= bfd_zmalloc ((bfd_size_type
) 1 << alignment_power
);
301 for (; entry
!= NULL
&& entry
->secinfo
== secinfo
; entry
= entry
->next
)
303 register const char *str
;
306 len
= off
& (entry
->alignment
- 1);
309 len
= entry
->alignment
- len
;
310 if (bfd_bwrite (pad
, (bfd_size_type
) len
, abfd
) != len
)
315 str
= entry
->root
.string
;
318 if (bfd_bwrite (str
, (bfd_size_type
) len
, abfd
) != len
)
327 return entry
== NULL
|| entry
->secinfo
!= secinfo
;
330 /* This function is called for each input file from the add_symbols
331 pass of the linker. */
334 _bfd_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
, void **psecinfo
)
336 struct sec_merge_info
*sinfo
;
337 struct sec_merge_sec_info
*secinfo
;
341 if (sec
->_raw_size
== 0
342 || (sec
->flags
& SEC_EXCLUDE
)
343 || (sec
->flags
& SEC_MERGE
) == 0
344 || sec
->entsize
== 0)
347 if ((sec
->flags
& SEC_RELOC
) != 0)
349 /* We aren't prepared to handle relocations in merged sections. */
353 align
= bfd_get_section_alignment (sec
->owner
, sec
);
354 if ((sec
->entsize
< (unsigned int)(1 << align
)
355 && ((sec
->entsize
& (sec
->entsize
- 1))
356 || !(sec
->flags
& SEC_STRINGS
)))
357 || (sec
->entsize
> (unsigned int)(1 << align
)
358 && (sec
->entsize
& ((1 << align
) - 1))))
360 /* Sanity check. If string character size is smaller than
361 alignment, then we require character size to be a power
362 of 2, otherwise character size must be integer multiple
363 of alignment. For non-string constants, alignment must
364 be smaller than or equal to entity size and entity size
365 must be integer multiple of alignment. */
369 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
370 if ((secinfo
= sinfo
->chain
)
371 && ! ((secinfo
->sec
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
372 && secinfo
->sec
->entsize
== sec
->entsize
373 && ! strcmp (secinfo
->sec
->name
, sec
->name
))
378 /* Initialize the information we need to keep track of. */
379 amt
= sizeof (struct sec_merge_info
);
380 sinfo
= (struct sec_merge_info
*) bfd_alloc (abfd
, amt
);
383 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
386 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
387 if (sinfo
->htab
== NULL
)
391 /* Read the section from abfd. */
393 amt
= sizeof (struct sec_merge_sec_info
) + sec
->_raw_size
- 1;
394 *psecinfo
= bfd_alloc (abfd
, amt
);
395 if (*psecinfo
== NULL
)
398 secinfo
= (struct sec_merge_sec_info
*)*psecinfo
;
401 secinfo
->next
= sinfo
->chain
->next
;
402 sinfo
->chain
->next
= secinfo
;
405 secinfo
->next
= secinfo
;
406 sinfo
->chain
= secinfo
;
408 secinfo
->psecinfo
= psecinfo
;
409 secinfo
->htab
= sinfo
->htab
;
410 secinfo
->first
= NULL
;
412 if (! bfd_get_section_contents (sec
->owner
, sec
, secinfo
->contents
,
413 (bfd_vma
) 0, sec
->_raw_size
))
423 /* Compare two sec_merge_hash_entry structures. This is called via qsort. */
426 cmplengthentry (const void *a
, const void *b
)
428 struct sec_merge_hash_entry
* A
= *(struct sec_merge_hash_entry
**) a
;
429 struct sec_merge_hash_entry
* B
= *(struct sec_merge_hash_entry
**) b
;
433 else if (A
->len
> B
->len
)
436 return memcmp (A
->root
.string
, B
->root
.string
, A
->len
);
440 last4_eq (const void *a
, const void *b
)
442 struct sec_merge_hash_entry
* A
= (struct sec_merge_hash_entry
*) a
;
443 struct sec_merge_hash_entry
* B
= (struct sec_merge_hash_entry
*) b
;
445 if (memcmp (A
->root
.string
+ A
->len
- 5 * A
->u
.entsize
,
446 B
->root
.string
+ B
->len
- 5 * A
->u
.entsize
,
447 4 * A
->u
.entsize
) != 0)
448 /* This was a hashtable collision. */
451 if (A
->len
<= B
->len
)
452 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
453 not to be equal by the hash table. */
456 if (A
->alignment
< B
->alignment
457 || ((A
->len
- B
->len
) & (B
->alignment
- 1)))
458 /* The suffix is not sufficiently aligned. */
461 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
462 B
->root
.string
, B
->len
- 5 * A
->u
.entsize
) == 0;
466 last_eq (const void *a
, const void *b
)
468 struct sec_merge_hash_entry
* A
= (struct sec_merge_hash_entry
*) a
;
469 struct sec_merge_hash_entry
* B
= (struct sec_merge_hash_entry
*) b
;
471 if (B
->len
>= 5 * A
->u
.entsize
)
472 /* Longer strings are just pushed into the hash table,
473 they'll be used when looking up for very short strings. */
476 if (memcmp (A
->root
.string
+ A
->len
- 2 * A
->u
.entsize
,
477 B
->root
.string
+ B
->len
- 2 * A
->u
.entsize
,
479 /* This was a hashtable collision. */
482 if (A
->len
<= B
->len
)
483 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
484 not to be equal by the hash table. */
487 if (A
->alignment
< B
->alignment
488 || ((A
->len
- B
->len
) & (B
->alignment
- 1)))
489 /* The suffix is not sufficiently aligned. */
492 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
493 B
->root
.string
, B
->len
- 2 * A
->u
.entsize
) == 0;
496 /* Record one section into the hash table. */
498 record_section (struct sec_merge_info
*sinfo
,
499 struct sec_merge_sec_info
*secinfo
)
501 asection
*sec
= secinfo
->sec
;
502 struct sec_merge_hash_entry
*entry
;
504 unsigned char *p
, *end
;
505 bfd_vma mask
, eltalign
;
506 unsigned int align
, i
;
508 align
= bfd_get_section_alignment (sec
->owner
, sec
);
509 end
= secinfo
->contents
+ sec
->_raw_size
;
511 mask
= ((bfd_vma
) 1 << align
) - 1;
512 if (sec
->flags
& SEC_STRINGS
)
514 for (p
= secinfo
->contents
; p
< end
; )
516 eltalign
= p
- secinfo
->contents
;
517 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
518 if (!eltalign
|| eltalign
> mask
)
520 entry
= sec_merge_add (sinfo
->htab
, p
, (unsigned) eltalign
, secinfo
);
524 if (sec
->entsize
== 1)
526 while (p
< end
&& *p
== 0)
528 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
531 entry
= sec_merge_add (sinfo
->htab
, "",
532 (unsigned) mask
+ 1, secinfo
);
543 for (i
= 0; i
< sec
->entsize
; i
++)
546 if (i
!= sec
->entsize
)
548 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
551 entry
= sec_merge_add (sinfo
->htab
, p
,
552 (unsigned) mask
+ 1, secinfo
);
563 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
565 entry
= sec_merge_add (sinfo
->htab
, p
, 1, secinfo
);
574 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
575 *secinfo
->psecinfo
= NULL
;
579 /* This is a helper function for _bfd_merge_sections. It attempts to
580 merge strings matching suffixes of longer strings. */
582 merge_strings (struct sec_merge_info
*sinfo
)
584 struct sec_merge_hash_entry
**array
, **a
, **end
, *e
;
585 struct sec_merge_sec_info
*secinfo
;
586 htab_t lasttab
= NULL
, last4tab
= NULL
;
587 bfd_size_type size
, amt
;
589 /* Now sort the strings by length, longest first. */
591 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
592 array
= (struct sec_merge_hash_entry
**) bfd_malloc (amt
);
596 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
600 sinfo
->htab
->size
= a
- array
;
602 qsort (array
, (size_t) sinfo
->htab
->size
,
603 sizeof (struct sec_merge_hash_entry
*), cmplengthentry
);
605 last4tab
= htab_create_alloc ((size_t) sinfo
->htab
->size
* 4,
606 NULL
, last4_eq
, NULL
, calloc
, free
);
607 lasttab
= htab_create_alloc ((size_t) sinfo
->htab
->size
* 4,
608 NULL
, last_eq
, NULL
, calloc
, free
);
609 if (lasttab
== NULL
|| last4tab
== NULL
)
612 /* Now insert the strings into hash tables (strings with last 4 characters
613 and strings with last character equal), look for longer strings which
615 for (a
= array
, end
= array
+ sinfo
->htab
->size
; a
< end
; a
++)
617 register hashval_t hash
;
620 const unsigned char *s
;
624 e
->u
.entsize
= sinfo
->htab
->entsize
;
625 if (e
->len
<= e
->u
.entsize
)
627 if (e
->len
> 4 * e
->u
.entsize
)
629 s
= (const unsigned char *) (e
->root
.string
+ e
->len
- e
->u
.entsize
);
631 for (i
= 0; i
< 4 * e
->u
.entsize
; i
++)
634 hash
+= c
+ (c
<< 17);
637 p
= htab_find_slot_with_hash (last4tab
, e
, hash
, INSERT
);
642 struct sec_merge_hash_entry
*ent
;
644 ent
= (struct sec_merge_hash_entry
*) *p
;
652 s
= (const unsigned char *) (e
->root
.string
+ e
->len
- e
->u
.entsize
);
654 for (i
= 0; i
< e
->u
.entsize
; i
++)
657 hash
+= c
+ (c
<< 17);
660 p
= htab_find_slot_with_hash (lasttab
, e
, hash
, INSERT
);
665 struct sec_merge_hash_entry
*ent
;
667 ent
= (struct sec_merge_hash_entry
*) *p
;
679 htab_delete (lasttab
);
681 htab_delete (last4tab
);
683 /* Now assign positions to the strings we want to keep. */
685 secinfo
= sinfo
->htab
->first
->secinfo
;
686 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
688 if (e
->secinfo
!= secinfo
)
690 secinfo
->sec
->_cooked_size
= size
;
691 secinfo
= e
->secinfo
;
695 if (e
->secinfo
->first
== NULL
)
697 e
->secinfo
->first
= e
;
700 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
705 secinfo
->sec
->_cooked_size
= size
;
707 /* And now adjust the rest, removing them from the chain (but not hashtable)
709 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
717 e
->secinfo
= e
->u
.suffix
->secinfo
;
718 e
->alignment
= e
->u
.suffix
->alignment
;
719 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
724 /* This function is called once after all SEC_MERGE sections are registered
725 with _bfd_merge_section. */
728 _bfd_merge_sections (bfd
*abfd ATTRIBUTE_UNUSED
, void *xsinfo
,
729 void (*remove_hook
) (bfd
*, asection
*))
731 struct sec_merge_info
*sinfo
;
733 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
735 struct sec_merge_sec_info
* secinfo
;
740 /* Move sinfo->chain to head of the chain, terminate it. */
741 secinfo
= sinfo
->chain
;
742 sinfo
->chain
= secinfo
->next
;
743 secinfo
->next
= NULL
;
745 /* Record the sections into the hash table. */
746 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
747 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
749 *secinfo
->psecinfo
= NULL
;
751 (*remove_hook
) (abfd
, secinfo
->sec
);
753 else if (! record_section (sinfo
, secinfo
))
759 if (sinfo
->htab
->first
== NULL
)
762 if (sinfo
->htab
->strings
)
763 merge_strings (sinfo
);
766 struct sec_merge_hash_entry
*e
;
767 bfd_size_type size
= 0;
769 /* Things are much simpler for non-strings.
770 Just assign them slots in the section. */
772 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
774 if (e
->secinfo
->first
== NULL
)
777 secinfo
->sec
->_cooked_size
= size
;
778 e
->secinfo
->first
= e
;
781 size
= (size
+ e
->alignment
- 1)
782 & ~((bfd_vma
) e
->alignment
- 1);
785 secinfo
= e
->secinfo
;
787 secinfo
->sec
->_cooked_size
= size
;
790 /* Finally shrink all input sections which have not made it into
791 the hash table at all. */
792 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
793 if (secinfo
->first
== NULL
)
794 secinfo
->sec
->_cooked_size
= 0;
800 /* Write out the merged section. */
803 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
805 struct sec_merge_sec_info
*secinfo
;
808 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
813 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
814 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
817 if (! sec_merge_emit (output_bfd
, secinfo
->first
))
823 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
824 *PSEC, this returns the new offset in the adjusted SEC_MERGE
825 section and writes the new section back into *PSEC. */
828 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
829 void *psecinfo
, bfd_vma offset
, bfd_vma addend
)
831 struct sec_merge_sec_info
*secinfo
;
832 struct sec_merge_hash_entry
*entry
;
834 asection
*sec
= *psec
;
836 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
838 if (offset
+ addend
>= sec
->_raw_size
)
840 if (offset
+ addend
> sec
->_raw_size
)
842 (*_bfd_error_handler
)
843 (_("%s: access beyond end of merged section (%ld + %ld)"),
844 bfd_get_filename (sec
->owner
), (long) offset
, (long) addend
);
846 return (secinfo
->first
? sec
->_cooked_size
: 0);
849 if (secinfo
->htab
->strings
)
851 if (sec
->entsize
== 1)
853 p
= secinfo
->contents
+ offset
+ addend
- 1;
854 while (p
>= secinfo
->contents
&& *p
)
860 p
= secinfo
->contents
861 + ((offset
+ addend
) / sec
->entsize
) * sec
->entsize
;
863 while (p
>= secinfo
->contents
)
867 for (i
= 0; i
< sec
->entsize
; ++i
)
870 if (i
== sec
->entsize
)
879 p
= secinfo
->contents
880 + ((offset
+ addend
) / sec
->entsize
) * sec
->entsize
;
882 entry
= sec_merge_hash_lookup (secinfo
->htab
, p
, 0, FALSE
);
885 if (! secinfo
->htab
->strings
)
887 /* This should only happen if somebody points into the padding
888 after a NUL character but before next entity. */
891 if (! secinfo
->htab
->first
)
893 entry
= secinfo
->htab
->first
;
894 p
= secinfo
->contents
895 + ((offset
+ addend
) / sec
->entsize
+ 1) * sec
->entsize
899 *psec
= entry
->secinfo
->sec
;
900 return entry
->u
.index
+ (secinfo
->contents
+ offset
- p
);