2 Copyright 2001 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. */
30 /* An entry in the section merge hash table. */
32 struct sec_merge_hash_entry
34 struct bfd_hash_entry root
;
35 /* Length of this entry. */
37 /* Start of this string needs to be aligned to
38 alignment octets (not 1 << align). */
39 unsigned int alignment
;
40 /* Index within the merged section. */
42 /* Which section is it in. */
44 /* Next entity in the hash table. */
45 struct sec_merge_hash_entry
*next
;
48 /* The section merge hash table. */
52 struct bfd_hash_table table
;
53 /* Next available index. */
55 /* First entity in the SEC_MERGE sections of this type. */
56 struct sec_merge_hash_entry
*first
;
57 /* Last entity in the SEC_MERGE sections of this type. */
58 struct sec_merge_hash_entry
*last
;
61 /* Are entries fixed size or zero terminated strings? */
67 /* Chain of sec_merge_infos. */
68 struct sec_merge_info
*next
;
69 /* A hash table used to hold section content. */
70 struct sec_merge_hash
*htab
;
71 /* The last section attempted for merge. */
75 struct sec_merge_sec_info
77 /* A hash table used to hold section content. */
78 struct sec_merge_hash
*htab
;
79 /* First string in this section. */
80 struct sec_merge_hash_entry
*first
;
81 /* Original section content. */
82 unsigned char contents
[1];
85 static struct bfd_hash_entry
*sec_merge_hash_newfunc
86 PARAMS ((struct bfd_hash_entry
*, struct bfd_hash_table
*, const char *));
87 static struct sec_merge_hash_entry
*sec_merge_hash_lookup
88 PARAMS ((struct sec_merge_hash
*, const char *, unsigned int, boolean
));
89 static struct sec_merge_hash
*sec_merge_init
90 PARAMS ((unsigned int, boolean
));
91 static struct sec_merge_hash_entry
*sec_merge_add
92 PARAMS ((struct sec_merge_hash
*, const char *, unsigned int));
93 static boolean sec_merge_emit
94 PARAMS ((bfd
*, struct sec_merge_hash_entry
*));
96 /* Routine to create an entry in a section merge hashtab. */
98 static struct bfd_hash_entry
*
99 sec_merge_hash_newfunc (entry
, table
, string
)
100 struct bfd_hash_entry
*entry
;
101 struct bfd_hash_table
*table
;
104 struct sec_merge_hash_entry
*ret
= (struct sec_merge_hash_entry
*) entry
;
106 /* Allocate the structure if it has not already been allocated by a
108 if (ret
== (struct sec_merge_hash_entry
*) NULL
)
109 ret
= ((struct sec_merge_hash_entry
*)
110 bfd_hash_allocate (table
, sizeof (struct sec_merge_hash_entry
)));
111 if (ret
== (struct sec_merge_hash_entry
*) NULL
)
114 /* Call the allocation method of the superclass. */
115 ret
= ((struct sec_merge_hash_entry
*)
116 bfd_hash_newfunc ((struct bfd_hash_entry
*) ret
, table
, string
));
120 /* Initialize the local fields. */
121 ret
->index
= (bfd_size_type
) -1;
127 return (struct bfd_hash_entry
*)ret
;
130 /* Look up an entry in a section merge hash table. */
132 static struct sec_merge_hash_entry
*
133 sec_merge_hash_lookup (table
, string
, alignment
, create
)
134 struct sec_merge_hash
*table
;
136 unsigned int alignment
;
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 FIXME: The old copy could be removed and the space allocated
207 for it filled by some new string (similarly with padding). */
208 if (hashp
->alignment
< alignment
)
215 return (struct sec_merge_hash_entry
*) NULL
;
217 hashp
= (struct sec_merge_hash_entry
*)
218 sec_merge_hash_newfunc ((struct bfd_hash_entry
*) NULL
,
219 (struct bfd_hash_table
*) table
, string
);
220 if (hashp
== (struct sec_merge_hash_entry
*) NULL
)
221 return (struct sec_merge_hash_entry
*) NULL
;
222 hashp
->root
.string
= string
;
223 hashp
->root
.hash
= hash
;
225 hashp
->alignment
= alignment
;
226 hashp
->root
.next
= table
->table
.table
[index
];
227 table
->table
.table
[index
] = (struct bfd_hash_entry
*) hashp
;
232 /* Create a new hash table. */
234 static struct sec_merge_hash
*
235 sec_merge_init (entsize
, strings
)
236 unsigned int entsize
;
239 struct sec_merge_hash
*table
;
241 table
= ((struct sec_merge_hash
*)
242 bfd_malloc (sizeof (struct sec_merge_hash
)));
246 if (! bfd_hash_table_init (&table
->table
, sec_merge_hash_newfunc
))
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 (tab
, str
, alignment
)
266 struct sec_merge_hash
*tab
;
268 unsigned int alignment
;
270 register struct sec_merge_hash_entry
*entry
;
272 entry
= sec_merge_hash_lookup (tab
, str
, alignment
, true);
276 if (entry
->index
== (bfd_size_type
) -1)
278 tab
->size
= (tab
->size
+ alignment
- 1) & ~((bfd_vma
) alignment
- 1);
279 entry
->index
= tab
->size
;
280 tab
->size
+= entry
->len
;
281 if (tab
->first
== NULL
)
284 tab
->last
->next
= entry
;
292 sec_merge_emit (abfd
, entry
)
294 struct sec_merge_hash_entry
*entry
;
296 asection
*sec
= entry
->sec
;
298 bfd_size_type off
= 0;
299 int alignment_power
= bfd_get_section_alignment (abfd
, sec
->output_section
);
302 pad
= bfd_zmalloc (1 << alignment_power
);
304 for (; entry
!= NULL
&& entry
->sec
== sec
; entry
= entry
->next
)
306 register const char *str
;
309 len
= off
& (entry
->alignment
- 1);
312 len
= entry
->alignment
- len
;
313 if (bfd_write ((PTR
) pad
, 1, len
, abfd
) != len
)
318 str
= entry
->root
.string
;
321 if (bfd_write ((PTR
) str
, 1, len
, abfd
) != len
)
330 return entry
== NULL
|| entry
->sec
!= sec
;
333 /* This function is called for each input file from the add_symbols
334 pass of the linker. */
337 _bfd_merge_section (abfd
, psinfo
, sec
, psecinfo
)
344 struct sec_merge_info
*sinfo
;
345 struct sec_merge_sec_info
*secinfo
;
346 unsigned char *p
, *end
;
347 bfd_vma mask
, eltalign
;
351 if (sec
->_raw_size
== 0
352 || (sec
->flags
& SEC_MERGE
) == 0
353 || sec
->entsize
== 0)
356 if ((sec
->flags
& SEC_RELOC
) != 0)
358 /* We aren't prepared to handle relocations in merged sections. */
362 if (sec
->output_section
!= NULL
363 && bfd_is_abs_section (sec
->output_section
))
365 /* The section is being discarded from the link, so we should
370 align
= bfd_get_section_alignment (abfd
, sec
);
371 if ((sec
->entsize
< (unsigned int)(1 << align
)
372 && ((sec
->entsize
& (sec
->entsize
- 1))
373 || !(sec
->flags
& SEC_STRINGS
)))
374 || (sec
->entsize
> (unsigned int)(1 << align
)
375 && (sec
->entsize
& ((1 << align
) - 1))))
377 /* Sanity check. If string character size is smaller than
378 alignment, then we require character size to be a power
379 of 2, otherwise character size must be integer multiple
380 of alignment. For non-string constants, alignment must
381 be smaller than or equal to entity size and entity size
382 must be integer multiple of alignment. */
388 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
389 if (! ((sinfo
->last
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
390 && sinfo
->last
->entsize
== sec
->entsize
391 && ! strcmp (sinfo
->last
->name
, sec
->name
))
396 /* 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
;
403 *psinfo
= (PTR
) sinfo
;
405 sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
406 if (sinfo
->htab
== NULL
)
410 /* Read the section from abfd. */
412 *psecinfo
= bfd_alloc (abfd
, sizeof (struct sec_merge_sec_info
)
413 + sec
->_raw_size
- 1);
414 if (*psecinfo
== NULL
)
417 secinfo
= (struct sec_merge_sec_info
*)*psecinfo
;
418 secinfo
->htab
= sinfo
->htab
;
419 sinfo
->htab
->size
= 0;
420 secinfo
->first
= NULL
;
422 if (! bfd_get_section_contents (abfd
, sec
, secinfo
->contents
, 0,
426 end
= secinfo
->contents
+ sec
->_raw_size
;
428 mask
= ((bfd_vma
)1 << align
) - 1;
429 if (sec
->flags
& SEC_STRINGS
)
431 for (p
= secinfo
->contents
; p
< end
;)
433 struct sec_merge_hash_entry
*entry
;
435 eltalign
= p
- secinfo
->contents
;
436 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
437 if (!eltalign
|| eltalign
> mask
)
439 entry
= sec_merge_add (sinfo
->htab
, p
, eltalign
);
440 if (entry
->sec
== NULL
)
442 if (secinfo
->first
== NULL
)
443 secinfo
->first
= entry
;
447 if (sec
->entsize
== 1)
449 while (p
< end
&& *p
== 0)
451 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
454 entry
= sec_merge_add (sinfo
->htab
, "", mask
+ 1);
455 if (entry
->sec
== NULL
)
457 if (secinfo
->first
== NULL
)
458 secinfo
->first
= entry
;
469 for (i
= 0; i
< sec
->entsize
; i
++)
472 if (i
!= sec
->entsize
)
474 if (!nul
&& !((p
- secinfo
->contents
) & mask
))
477 entry
= sec_merge_add (sinfo
->htab
, p
, mask
+ 1);
478 if (entry
->sec
== NULL
)
480 if (secinfo
->first
== NULL
)
481 secinfo
->first
= entry
;
492 for (p
= secinfo
->contents
; p
< end
; p
+= sec
->entsize
)
494 struct sec_merge_hash_entry
*entry
;
496 entry
= sec_merge_add (sinfo
->htab
, p
, 1);
497 if (entry
->sec
== NULL
)
499 if (secinfo
->first
== NULL
)
500 secinfo
->first
= entry
;
506 sec
->_cooked_size
= sinfo
->htab
->size
;
507 if (!sec
->_cooked_size
)
508 sec
->flags
|= SEC_EXCLUDE
;
513 if (*psecinfo
!= NULL
)
519 /* Write out the merged section. */
522 _bfd_write_merged_section (output_bfd
, sec
, psecinfo
)
527 struct sec_merge_sec_info
*secinfo
;
529 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
534 if (bfd_seek (output_bfd
,
535 (sec
->output_section
->filepos
+ sec
->output_offset
),
539 if (! sec_merge_emit (output_bfd
, secinfo
->first
))
545 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
546 *PSEC, this returns the new offset in the adjusted SEC_MERGE
547 section and writes the new section back into *PSEC. */
550 _bfd_merged_section_offset (output_bfd
, psec
, psecinfo
, offset
, addend
)
551 bfd
*output_bfd ATTRIBUTE_UNUSED
;
554 bfd_vma offset
, addend
;
556 struct sec_merge_sec_info
*secinfo
;
557 struct sec_merge_hash_entry
*entry
;
559 asection
*sec
= *psec
;
561 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
563 if (offset
+ addend
>= sec
->_raw_size
)
565 if (offset
+ addend
> sec
->_raw_size
)
566 (*_bfd_error_handler
) (_("%s: access beyond end of merged section (%ld + %ld)"),
567 bfd_get_filename (sec
->owner
), (long)offset
,
569 return (secinfo
->first
? sec
->_cooked_size
: 0);
572 if (secinfo
->htab
->strings
)
574 if (sec
->entsize
== 1)
576 p
= secinfo
->contents
+ offset
+ addend
- 1;
577 while (*p
&& p
>= secinfo
->contents
)
583 p
= secinfo
->contents
584 + ((offset
+ addend
) / sec
->entsize
) * sec
->entsize
;
586 while (p
>= secinfo
->contents
)
590 for (i
= 0; i
< sec
->entsize
; ++i
)
593 if (i
== sec
->entsize
)
602 p
= secinfo
->contents
603 + ((offset
+ addend
) / sec
->entsize
) * sec
->entsize
;
605 entry
= sec_merge_hash_lookup (secinfo
->htab
, p
, 0, false);
608 if (! secinfo
->htab
->strings
)
610 /* This should only happen if somebody points into the padding
611 after a NUL character but before next entity. */
614 if (! secinfo
->htab
->first
)
616 entry
= secinfo
->htab
->first
;
617 p
= secinfo
->contents
618 + ((offset
+ addend
) / sec
->entsize
+ 1) * sec
->entsize
623 return entry
->index
+ (secinfo
->contents
+ offset
- p
);