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 /* Index within the merged section. */
39 /* Which section is it in. */
41 /* Next entity in the hash table. */
42 struct sec_merge_hash_entry *next;
45 /* The section merge hash table. */
49 struct bfd_hash_table table;
50 /* Next available index. */
52 /* First entity in the SEC_MERGE sections of this type. */
53 struct sec_merge_hash_entry *first;
54 /* Last entity in the SEC_MERGE sections of this type. */
55 struct sec_merge_hash_entry *last;
58 /* Start of each string needs to be aligned to 1 << alignment_power
60 unsigned int alignment_power;
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 *, boolean));
89 static struct sec_merge_hash *sec_merge_init
90 PARAMS ((unsigned int, unsigned int, boolean));
91 static struct sec_merge_hash_entry *sec_merge_add
92 PARAMS ((struct sec_merge_hash *, const char *));
93 static boolean sec_merge_emit
94 PARAMS ((bfd *, struct sec_merge_hash *, 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;
126 return (struct bfd_hash_entry *)ret;
129 /* Look up an entry in a section merge hash table. */
131 static struct sec_merge_hash_entry *
132 sec_merge_hash_lookup (table, string, create)
133 struct sec_merge_hash *table;
137 register const unsigned char *s;
138 register unsigned long hash;
139 register unsigned int c;
140 struct sec_merge_hash_entry *hashp;
146 s = (const unsigned char *) string;
149 if (table->entsize == 1)
151 while ((c = *s++) != '\0')
153 hash += c + (c << 17);
157 hash += len + (len << 17);
163 for (i = 0; i < table->entsize; ++i)
166 if (i == table->entsize)
168 for (i = 0; i < table->entsize; ++i)
171 hash += c + (c << 17);
176 hash += len + (len << 17);
177 len *= table->entsize;
180 len += table->entsize;
184 for (i = 0; i < table->entsize; ++i)
187 hash += c + (c << 17);
190 len = table->entsize;
193 index = hash % table->table.size;
194 for (hashp = (struct sec_merge_hash_entry *) table->table.table[index];
195 hashp != (struct sec_merge_hash_entry *) NULL;
196 hashp = (struct sec_merge_hash_entry *) hashp->next)
198 if (hashp->root.hash == hash
200 && memcmp (hashp->root.string, string, len) == 0)
205 return (struct sec_merge_hash_entry *) NULL;
207 hashp = (struct sec_merge_hash_entry *)
208 sec_merge_hash_newfunc ((struct bfd_hash_entry *) NULL,
209 (struct bfd_hash_table *) table, string);
210 if (hashp == (struct sec_merge_hash_entry *) NULL)
211 return (struct sec_merge_hash_entry *) NULL;
212 hashp->root.string = string;
213 hashp->root.hash = hash;
215 hashp->root.next = table->table.table[index];
216 table->table.table[index] = (struct bfd_hash_entry *) hashp;
221 /* Create a new hash table. */
223 static struct sec_merge_hash *
224 sec_merge_init (alignment_power, entsize, strings)
225 unsigned int alignment_power, entsize;
228 struct sec_merge_hash *table;
230 table = ((struct sec_merge_hash *)
231 bfd_malloc (sizeof (struct sec_merge_hash)));
235 if (! bfd_hash_table_init (&table->table, sec_merge_hash_newfunc))
244 table->alignment_power = alignment_power;
245 table->entsize = entsize;
246 table->strings = strings;
251 /* Get the index of an entity in a hash table, adding it if it is not
254 static struct sec_merge_hash_entry *
255 sec_merge_add (tab, str)
256 struct sec_merge_hash *tab;
259 register struct sec_merge_hash_entry *entry;
261 entry = sec_merge_hash_lookup (tab, str, true);
265 if (entry->index == (bfd_size_type) -1)
267 entry->index = tab->size;
268 tab->size += entry->len;
269 tab->size = align_power (tab->size, tab->alignment_power);
270 if (tab->first == NULL)
273 tab->last->next = entry;
281 sec_merge_emit (abfd, tab, entry)
283 struct sec_merge_hash *tab;
284 struct sec_merge_hash_entry *entry;
286 asection *sec = entry->sec;
289 if (tab->alignment_power)
290 pad = bfd_zmalloc (1 << tab->alignment_power);
292 for (; entry != NULL && entry->sec == sec; entry = entry->next)
294 register const char *str;
297 str = entry->root.string;
300 if (bfd_write ((PTR) str, 1, len, abfd) != len)
303 if (tab->alignment_power)
305 len &= (1 << tab->alignment_power) - 1;
306 if (len && bfd_write ((PTR) pad, 1,
307 (1 << tab->alignment_power) - len,
308 abfd) != (1 << tab->alignment_power) - len)
313 if (tab->alignment_power)
316 return entry == NULL || entry->sec != sec;
319 /* This function is called for each input file from the add_symbols
320 pass of the linker. */
323 _bfd_merge_section (abfd, psinfo, sec, psecinfo)
330 struct sec_merge_info *sinfo;
331 struct sec_merge_sec_info *secinfo;
332 unsigned char *p, *end;
337 if (sec->_raw_size == 0
338 || (sec->flags & SEC_MERGE) == 0
339 || sec->entsize == 0)
342 if ((sec->flags & SEC_RELOC) != 0)
344 /* We aren't prepared to handle relocations in merged sections. */
348 if (sec->output_section != NULL
349 && bfd_is_abs_section (sec->output_section))
351 /* The section is being discarded from the link, so we should
356 align = bfd_get_section_alignment (abfd, sec);
357 if ((sec->flags & SEC_STRINGS)
358 && ((sec->entsize < (unsigned int)(1 << align)
359 && (sec->entsize & (sec->entsize - 1)))
360 || (sec->entsize > (unsigned int)(1 << align)
361 && (sec->entsize & ((1 << align) - 1)))))
363 /* Sanity check. If string character size is smaller than
364 alignment, then we require character size to be a power
365 of 2, otherwise character size must be integer multiple
372 for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next)
373 if (! ((sinfo->last->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS))
374 && sinfo->last->entsize == sec->entsize
375 && ! strcmp (sinfo->last->name, sec->name)
376 && bfd_get_section_alignment (abfd, sinfo->last) == align)
381 /* Initialize the information we need to keep track of. */
383 sinfo = (struct sec_merge_info *)
384 bfd_alloc (abfd, sizeof (struct sec_merge_info));
387 sinfo->next = (struct sec_merge_info *) *psinfo;
388 *psinfo = (PTR) sinfo;
390 sec_merge_init ((sec->flags & SEC_STRINGS) ? align : 0,
391 sec->entsize, (sec->flags & SEC_STRINGS));
392 if (sinfo->htab == NULL)
396 /* Read the section from abfd. */
398 *psecinfo = bfd_alloc (abfd, sizeof (struct sec_merge_sec_info)
399 + sec->_raw_size - 1);
400 if (*psecinfo == NULL)
403 secinfo = (struct sec_merge_sec_info *)*psecinfo;
404 secinfo->htab = sinfo->htab;
405 sinfo->htab->size = 0;
406 secinfo->first = NULL;
408 if (! bfd_get_section_contents (abfd, sec, secinfo->contents, 0,
412 end = secinfo->contents + sec->_raw_size;
414 mask = ((bfd_vma)1 << sinfo->htab->alignment_power) - 1;
415 if (sec->flags & SEC_STRINGS)
417 for (p = secinfo->contents; p < end;)
419 struct sec_merge_hash_entry *entry;
421 entry = sec_merge_add (sinfo->htab, p);
422 if (entry->sec == NULL)
424 if (secinfo->first == NULL)
425 secinfo->first = entry;
429 if (sec->entsize == 1)
431 while (p < end && *p == 0)
433 if (!nul && !((p - secinfo->contents) & mask))
436 entry = sec_merge_add (sinfo->htab, "");
437 if (entry->sec == NULL)
439 if (secinfo->first == NULL)
440 secinfo->first = entry;
451 for (i = 0; i < sec->entsize; i++)
454 if (i != sec->entsize)
456 if (!nul && !((p - secinfo->contents) & mask))
459 entry = sec_merge_add (sinfo->htab, p);
460 if (entry->sec == NULL)
462 if (secinfo->first == NULL)
463 secinfo->first = entry;
474 for (p = secinfo->contents; p < end; p += sec->entsize)
476 struct sec_merge_hash_entry *entry;
478 entry = sec_merge_add (sinfo->htab, p);
479 if (entry->sec == NULL)
481 if (secinfo->first == NULL)
482 secinfo->first = entry;
488 sec->_cooked_size = sinfo->htab->size;
489 if (!sec->_cooked_size)
490 sec->flags |= SEC_EXCLUDE;
495 if (*psecinfo != NULL)
501 /* Write out the merged section. */
504 _bfd_write_merged_section (output_bfd, sec, psecinfo)
509 struct sec_merge_sec_info *secinfo;
511 secinfo = (struct sec_merge_sec_info *) psecinfo;
516 if (bfd_seek (output_bfd,
517 (sec->output_section->filepos + sec->output_offset),
521 if (! sec_merge_emit (output_bfd, secinfo->htab, secinfo->first))
527 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
528 *PSEC, this returns the new offset in the adjusted SEC_MERGE
529 section and writes the new section back into *PSEC. */
532 _bfd_merged_section_offset (output_bfd, psec, psecinfo, offset, addend)
533 bfd *output_bfd ATTRIBUTE_UNUSED;
536 bfd_vma offset, addend;
538 struct sec_merge_sec_info *secinfo;
539 struct sec_merge_hash_entry *entry;
541 asection *sec = *psec;
543 secinfo = (struct sec_merge_sec_info *) psecinfo;
545 if (offset + addend >= sec->_raw_size)
547 if (offset + addend > sec->_raw_size)
548 (*_bfd_error_handler) (_("%s: access beyond end of merged section (%ld + %ld)"),
549 bfd_get_filename (sec->owner), (long)offset,
551 return (secinfo->first ? sec->_cooked_size : 0);
554 if (secinfo->htab->strings)
556 if (sec->entsize == 1)
558 p = secinfo->contents + offset + addend - 1;
559 while (*p && p >= secinfo->contents)
565 p = secinfo->contents
566 + ((offset + addend) / sec->entsize) * sec->entsize;
568 while (p >= secinfo->contents)
572 for (i = 0; i < sec->entsize; ++i)
575 if (i == sec->entsize)
584 p = secinfo->contents
585 + ((offset + addend) / sec->entsize) * sec->entsize;
587 entry = sec_merge_hash_lookup (secinfo->htab, p, false);
590 if (! secinfo->htab->strings)
592 /* This should only happen if somebody points into the padding
593 after a NUL character but before next entity. */
596 if (! secinfo->htab->first)
598 entry = secinfo->htab->first;
599 p = secinfo->contents
600 + ((offset + addend) / sec->entsize + 1) * sec->entsize
605 return entry->index + (secinfo->contents + offset - p);