Commit | Line | Data |
---|---|---|
f5fa8ca2 | 1 | /* SEC_MERGE support. |
aa820537 | 2 | Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
66eb6687 | 3 | Free Software Foundation, Inc. |
f5fa8ca2 JJ |
4 | Written by Jakub Jelinek <jakub@redhat.com>. |
5 | ||
7217313c | 6 | This file is part of BFD, the Binary File Descriptor library. |
f5fa8ca2 | 7 | |
7217313c NC |
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 | |
cd123cb7 | 10 | the Free Software Foundation; either version 3 of the License, or |
7217313c | 11 | (at your option) any later version. |
f5fa8ca2 | 12 | |
7217313c NC |
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. | |
f5fa8ca2 | 17 | |
7217313c NC |
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 | |
cd123cb7 NC |
20 | Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, |
21 | MA 02110-1301, USA. */ | |
22 | ||
f5fa8ca2 JJ |
23 | |
24 | /* This file contains support for merging duplicate entities within sections, | |
25 | as used in ELF SHF_MERGE. */ | |
26 | ||
f5fa8ca2 | 27 | #include "sysdep.h" |
3db64b00 | 28 | #include "bfd.h" |
f5fa8ca2 | 29 | #include "libbfd.h" |
8550eb6e | 30 | #include "hashtab.h" |
7217313c | 31 | #include "libiberty.h" |
f5fa8ca2 | 32 | |
8550eb6e JJ |
33 | struct sec_merge_sec_info; |
34 | ||
f5fa8ca2 JJ |
35 | /* An entry in the section merge hash table. */ |
36 | ||
37 | struct sec_merge_hash_entry | |
38 | { | |
39 | struct bfd_hash_entry root; | |
ddb2b442 | 40 | /* Length of this entry. This includes the zero terminator. */ |
f5fa8ca2 | 41 | unsigned int len; |
a531bbd2 JJ |
42 | /* Start of this string needs to be aligned to |
43 | alignment octets (not 1 << align). */ | |
44 | unsigned int alignment; | |
7217313c NC |
45 | union |
46 | { | |
8550eb6e JJ |
47 | /* Index within the merged section. */ |
48 | bfd_size_type index; | |
8550eb6e JJ |
49 | /* Entry this is a suffix of (if alignment is 0). */ |
50 | struct sec_merge_hash_entry *suffix; | |
51 | } u; | |
f5fa8ca2 | 52 | /* Which section is it in. */ |
8550eb6e | 53 | struct sec_merge_sec_info *secinfo; |
f5fa8ca2 JJ |
54 | /* Next entity in the hash table. */ |
55 | struct sec_merge_hash_entry *next; | |
56 | }; | |
57 | ||
58 | /* The section merge hash table. */ | |
59 | ||
60 | struct sec_merge_hash | |
61 | { | |
62 | struct bfd_hash_table table; | |
63 | /* Next available index. */ | |
64 | bfd_size_type size; | |
65 | /* First entity in the SEC_MERGE sections of this type. */ | |
66 | struct sec_merge_hash_entry *first; | |
67 | /* Last entity in the SEC_MERGE sections of this type. */ | |
68 | struct sec_merge_hash_entry *last; | |
69 | /* Entity size. */ | |
70 | unsigned int entsize; | |
f5fa8ca2 | 71 | /* Are entries fixed size or zero terminated strings? */ |
b34976b6 | 72 | bfd_boolean strings; |
f5fa8ca2 JJ |
73 | }; |
74 | ||
75 | struct sec_merge_info | |
76 | { | |
77 | /* Chain of sec_merge_infos. */ | |
78 | struct sec_merge_info *next; | |
8550eb6e JJ |
79 | /* Chain of sec_merge_sec_infos. */ |
80 | struct sec_merge_sec_info *chain; | |
f5fa8ca2 JJ |
81 | /* A hash table used to hold section content. */ |
82 | struct sec_merge_hash *htab; | |
f5fa8ca2 JJ |
83 | }; |
84 | ||
85 | struct sec_merge_sec_info | |
86 | { | |
8550eb6e JJ |
87 | /* Chain of sec_merge_sec_infos. */ |
88 | struct sec_merge_sec_info *next; | |
89 | /* The corresponding section. */ | |
90 | asection *sec; | |
91 | /* Pointer to merge_info pointing to us. */ | |
ac0e732e | 92 | void **psecinfo; |
f5fa8ca2 JJ |
93 | /* A hash table used to hold section content. */ |
94 | struct sec_merge_hash *htab; | |
95 | /* First string in this section. */ | |
57ceae94 | 96 | struct sec_merge_hash_entry *first_str; |
f5fa8ca2 JJ |
97 | /* Original section content. */ |
98 | unsigned char contents[1]; | |
99 | }; | |
100 | ||
f5fa8ca2 JJ |
101 | |
102 | /* Routine to create an entry in a section merge hashtab. */ | |
103 | ||
104 | static struct bfd_hash_entry * | |
ac0e732e AJ |
105 | sec_merge_hash_newfunc (struct bfd_hash_entry *entry, |
106 | struct bfd_hash_table *table, const char *string) | |
f5fa8ca2 | 107 | { |
f5fa8ca2 JJ |
108 | /* Allocate the structure if it has not already been allocated by a |
109 | subclass. */ | |
57ceae94 | 110 | if (entry == NULL) |
a50b1753 NC |
111 | entry = (struct bfd_hash_entry *) |
112 | bfd_hash_allocate (table, sizeof (struct sec_merge_hash_entry)); | |
57ceae94 | 113 | if (entry == NULL) |
f5fa8ca2 JJ |
114 | return NULL; |
115 | ||
116 | /* Call the allocation method of the superclass. */ | |
57ceae94 | 117 | entry = bfd_hash_newfunc (entry, table, string); |
f5fa8ca2 | 118 | |
57ceae94 | 119 | if (entry != NULL) |
f5fa8ca2 JJ |
120 | { |
121 | /* Initialize the local fields. */ | |
57ceae94 AM |
122 | struct sec_merge_hash_entry *ret = (struct sec_merge_hash_entry *) entry; |
123 | ||
8550eb6e | 124 | ret->u.suffix = NULL; |
a531bbd2 | 125 | ret->alignment = 0; |
8550eb6e | 126 | ret->secinfo = NULL; |
f5fa8ca2 JJ |
127 | ret->next = NULL; |
128 | } | |
129 | ||
57ceae94 | 130 | return entry; |
f5fa8ca2 JJ |
131 | } |
132 | ||
133 | /* Look up an entry in a section merge hash table. */ | |
134 | ||
135 | static struct sec_merge_hash_entry * | |
ac0e732e AJ |
136 | sec_merge_hash_lookup (struct sec_merge_hash *table, const char *string, |
137 | unsigned int alignment, bfd_boolean create) | |
f5fa8ca2 | 138 | { |
91d6fa6a NC |
139 | const unsigned char *s; |
140 | unsigned long hash; | |
141 | unsigned int c; | |
f5fa8ca2 JJ |
142 | struct sec_merge_hash_entry *hashp; |
143 | unsigned int len, i; | |
91d6fa6a | 144 | unsigned int _index; |
f5fa8ca2 JJ |
145 | |
146 | hash = 0; | |
147 | len = 0; | |
148 | s = (const unsigned char *) string; | |
149 | if (table->strings) | |
150 | { | |
151 | if (table->entsize == 1) | |
152 | { | |
153 | while ((c = *s++) != '\0') | |
154 | { | |
155 | hash += c + (c << 17); | |
156 | hash ^= hash >> 2; | |
157 | ++len; | |
158 | } | |
159 | hash += len + (len << 17); | |
160 | } | |
161 | else | |
162 | { | |
163 | for (;;) | |
164 | { | |
165 | for (i = 0; i < table->entsize; ++i) | |
166 | if (s[i] != '\0') | |
167 | break; | |
168 | if (i == table->entsize) | |
169 | break; | |
170 | for (i = 0; i < table->entsize; ++i) | |
171 | { | |
172 | c = *s++; | |
173 | hash += c + (c << 17); | |
174 | hash ^= hash >> 2; | |
175 | } | |
176 | ++len; | |
177 | } | |
178 | hash += len + (len << 17); | |
179 | len *= table->entsize; | |
180 | } | |
181 | hash ^= hash >> 2; | |
182 | len += table->entsize; | |
dc810e39 | 183 | } |
f5fa8ca2 JJ |
184 | else |
185 | { | |
186 | for (i = 0; i < table->entsize; ++i) | |
187 | { | |
188 | c = *s++; | |
189 | hash += c + (c << 17); | |
190 | hash ^= hash >> 2; | |
191 | } | |
192 | len = table->entsize; | |
193 | } | |
194 | ||
91d6fa6a NC |
195 | _index = hash % table->table.size; |
196 | for (hashp = (struct sec_merge_hash_entry *) table->table.table[_index]; | |
57ceae94 | 197 | hashp != NULL; |
a531bbd2 | 198 | hashp = (struct sec_merge_hash_entry *) hashp->root.next) |
f5fa8ca2 JJ |
199 | { |
200 | if (hashp->root.hash == hash | |
201 | && len == hashp->len | |
202 | && memcmp (hashp->root.string, string, len) == 0) | |
a531bbd2 JJ |
203 | { |
204 | /* If the string we found does not have at least the required | |
8550eb6e | 205 | alignment, we need to insert another copy. */ |
a531bbd2 | 206 | if (hashp->alignment < alignment) |
8550eb6e | 207 | { |
ddb2b442 AM |
208 | if (create) |
209 | { | |
210 | /* Mark the less aligned copy as deleted. */ | |
211 | hashp->len = 0; | |
212 | hashp->alignment = 0; | |
213 | } | |
8550eb6e JJ |
214 | break; |
215 | } | |
a531bbd2 JJ |
216 | return hashp; |
217 | } | |
f5fa8ca2 JJ |
218 | } |
219 | ||
220 | if (! create) | |
57ceae94 | 221 | return NULL; |
f5fa8ca2 | 222 | |
57ceae94 | 223 | hashp = ((struct sec_merge_hash_entry *) |
a69898aa | 224 | bfd_hash_insert (&table->table, string, hash)); |
57ceae94 AM |
225 | if (hashp == NULL) |
226 | return NULL; | |
f5fa8ca2 | 227 | hashp->len = len; |
a531bbd2 | 228 | hashp->alignment = alignment; |
f5fa8ca2 JJ |
229 | return hashp; |
230 | } | |
231 | ||
232 | /* Create a new hash table. */ | |
233 | ||
234 | static struct sec_merge_hash * | |
ac0e732e | 235 | sec_merge_init (unsigned int entsize, bfd_boolean strings) |
f5fa8ca2 JJ |
236 | { |
237 | struct sec_merge_hash *table; | |
238 | ||
a50b1753 | 239 | table = (struct sec_merge_hash *) bfd_malloc (sizeof (struct sec_merge_hash)); |
f5fa8ca2 JJ |
240 | if (table == NULL) |
241 | return NULL; | |
242 | ||
d05da6a8 | 243 | if (! bfd_hash_table_init_n (&table->table, sec_merge_hash_newfunc, |
66eb6687 | 244 | sizeof (struct sec_merge_hash_entry), 16699)) |
f5fa8ca2 JJ |
245 | { |
246 | free (table); | |
247 | return NULL; | |
248 | } | |
249 | ||
250 | table->size = 0; | |
251 | table->first = NULL; | |
252 | table->last = NULL; | |
f5fa8ca2 JJ |
253 | table->entsize = entsize; |
254 | table->strings = strings; | |
255 | ||
256 | return table; | |
257 | } | |
258 | ||
259 | /* Get the index of an entity in a hash table, adding it if it is not | |
260 | already present. */ | |
261 | ||
262 | static struct sec_merge_hash_entry * | |
ac0e732e AJ |
263 | sec_merge_add (struct sec_merge_hash *tab, const char *str, |
264 | unsigned int alignment, struct sec_merge_sec_info *secinfo) | |
f5fa8ca2 | 265 | { |
91d6fa6a | 266 | struct sec_merge_hash_entry *entry; |
f5fa8ca2 | 267 | |
9ca98086 | 268 | entry = sec_merge_hash_lookup (tab, str, alignment, TRUE); |
f5fa8ca2 JJ |
269 | if (entry == NULL) |
270 | return NULL; | |
271 | ||
8550eb6e | 272 | if (entry->secinfo == NULL) |
f5fa8ca2 | 273 | { |
8550eb6e JJ |
274 | tab->size++; |
275 | entry->secinfo = secinfo; | |
f5fa8ca2 JJ |
276 | if (tab->first == NULL) |
277 | tab->first = entry; | |
278 | else | |
279 | tab->last->next = entry; | |
280 | tab->last = entry; | |
281 | } | |
282 | ||
283 | return entry; | |
284 | } | |
285 | ||
b34976b6 | 286 | static bfd_boolean |
ddb2b442 | 287 | sec_merge_emit (bfd *abfd, struct sec_merge_hash_entry *entry) |
f5fa8ca2 | 288 | { |
8550eb6e JJ |
289 | struct sec_merge_sec_info *secinfo = entry->secinfo; |
290 | asection *sec = secinfo->sec; | |
92ceba1e | 291 | char *pad = NULL; |
a531bbd2 | 292 | bfd_size_type off = 0; |
57ceae94 | 293 | int alignment_power = sec->output_section->alignment_power; |
f5fa8ca2 | 294 | |
a531bbd2 | 295 | if (alignment_power) |
92ceba1e | 296 | { |
a50b1753 | 297 | pad = (char *) bfd_zmalloc ((bfd_size_type) 1 << alignment_power); |
92ceba1e AM |
298 | if (pad == NULL) |
299 | return FALSE; | |
300 | } | |
f5fa8ca2 | 301 | |
8550eb6e | 302 | for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next) |
f5fa8ca2 | 303 | { |
92ceba1e AM |
304 | const char *str; |
305 | bfd_size_type len; | |
f5fa8ca2 | 306 | |
92ceba1e AM |
307 | len = -off & (entry->alignment - 1); |
308 | if (len != 0) | |
a531bbd2 | 309 | { |
736cba80 NC |
310 | /* We should never have an entry with an alignment |
311 | greater than the section's alignment. */ | |
312 | BFD_ASSERT (len <= (bfd_size_type) (1 << alignment_power)); | |
57ceae94 | 313 | if (bfd_bwrite (pad, len, abfd) != len) |
92ceba1e | 314 | goto err; |
a531bbd2 JJ |
315 | off += len; |
316 | } | |
317 | ||
f5fa8ca2 JJ |
318 | str = entry->root.string; |
319 | len = entry->len; | |
320 | ||
57ceae94 | 321 | if (bfd_bwrite (str, len, abfd) != len) |
92ceba1e | 322 | goto err; |
f5fa8ca2 | 323 | |
a531bbd2 | 324 | off += len; |
f5fa8ca2 JJ |
325 | } |
326 | ||
92ceba1e AM |
327 | /* Trailing alignment needed? */ |
328 | off = sec->size - off; | |
329 | if (off != 0 | |
736cba80 | 330 | && alignment_power |
92ceba1e AM |
331 | && bfd_bwrite (pad, off, abfd) != off) |
332 | goto err; | |
333 | ||
334 | if (pad != NULL) | |
f5fa8ca2 | 335 | free (pad); |
92ceba1e | 336 | return TRUE; |
f5fa8ca2 | 337 | |
92ceba1e AM |
338 | err: |
339 | if (pad != NULL) | |
340 | free (pad); | |
341 | return FALSE; | |
f5fa8ca2 JJ |
342 | } |
343 | ||
57ceae94 AM |
344 | /* Register a SEC_MERGE section as a candidate for merging. |
345 | This function is called for all non-dynamic SEC_MERGE input sections. */ | |
f5fa8ca2 | 346 | |
b34976b6 | 347 | bfd_boolean |
57ceae94 AM |
348 | _bfd_add_merge_section (bfd *abfd, void **psinfo, asection *sec, |
349 | void **psecinfo) | |
f5fa8ca2 | 350 | { |
f5fa8ca2 JJ |
351 | struct sec_merge_info *sinfo; |
352 | struct sec_merge_sec_info *secinfo; | |
f5fa8ca2 | 353 | unsigned int align; |
dc810e39 | 354 | bfd_size_type amt; |
f5fa8ca2 | 355 | |
57ceae94 AM |
356 | if ((abfd->flags & DYNAMIC) != 0 |
357 | || (sec->flags & SEC_MERGE) == 0) | |
358 | abort (); | |
359 | ||
eea6121a | 360 | if (sec->size == 0 |
57ceae94 | 361 | || (sec->flags & SEC_EXCLUDE) != 0 |
f5fa8ca2 | 362 | || sec->entsize == 0) |
b34976b6 | 363 | return TRUE; |
f5fa8ca2 JJ |
364 | |
365 | if ((sec->flags & SEC_RELOC) != 0) | |
366 | { | |
367 | /* We aren't prepared to handle relocations in merged sections. */ | |
b34976b6 | 368 | return TRUE; |
f5fa8ca2 JJ |
369 | } |
370 | ||
57ceae94 AM |
371 | align = sec->alignment_power; |
372 | if ((sec->entsize < (unsigned) 1 << align | |
a531bbd2 JJ |
373 | && ((sec->entsize & (sec->entsize - 1)) |
374 | || !(sec->flags & SEC_STRINGS))) | |
57ceae94 AM |
375 | || (sec->entsize > (unsigned) 1 << align |
376 | && (sec->entsize & (((unsigned) 1 << align) - 1)))) | |
f5fa8ca2 JJ |
377 | { |
378 | /* Sanity check. If string character size is smaller than | |
379 | alignment, then we require character size to be a power | |
380 | of 2, otherwise character size must be integer multiple | |
a531bbd2 JJ |
381 | of alignment. For non-string constants, alignment must |
382 | be smaller than or equal to entity size and entity size | |
383 | must be integer multiple of alignment. */ | |
b34976b6 | 384 | return TRUE; |
f5fa8ca2 JJ |
385 | } |
386 | ||
f5fa8ca2 | 387 | for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next) |
8550eb6e JJ |
388 | if ((secinfo = sinfo->chain) |
389 | && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS)) | |
390 | && secinfo->sec->entsize == sec->entsize | |
57ceae94 AM |
391 | && secinfo->sec->alignment_power == sec->alignment_power |
392 | && secinfo->sec->output_section == sec->output_section) | |
f5fa8ca2 JJ |
393 | break; |
394 | ||
395 | if (sinfo == NULL) | |
396 | { | |
397 | /* Initialize the information we need to keep track of. */ | |
a50b1753 NC |
398 | sinfo = (struct sec_merge_info *) |
399 | bfd_alloc (abfd, sizeof (struct sec_merge_info)); | |
f5fa8ca2 JJ |
400 | if (sinfo == NULL) |
401 | goto error_return; | |
402 | sinfo->next = (struct sec_merge_info *) *psinfo; | |
8550eb6e | 403 | sinfo->chain = NULL; |
ac0e732e | 404 | *psinfo = sinfo; |
699cb9b8 | 405 | sinfo->htab = sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS)); |
f5fa8ca2 JJ |
406 | if (sinfo->htab == NULL) |
407 | goto error_return; | |
408 | } | |
409 | ||
410 | /* Read the section from abfd. */ | |
411 | ||
9ca98086 AM |
412 | amt = sizeof (struct sec_merge_sec_info) - 1 + sec->size; |
413 | if (sec->flags & SEC_STRINGS) | |
414 | /* Some versions of gcc may emit a string without a zero terminator. | |
415 | See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html | |
416 | Allocate space for an extra zero. */ | |
417 | amt += sec->entsize; | |
dc810e39 | 418 | *psecinfo = bfd_alloc (abfd, amt); |
f5fa8ca2 JJ |
419 | if (*psecinfo == NULL) |
420 | goto error_return; | |
421 | ||
57ceae94 | 422 | secinfo = (struct sec_merge_sec_info *) *psecinfo; |
8550eb6e JJ |
423 | if (sinfo->chain) |
424 | { | |
425 | secinfo->next = sinfo->chain->next; | |
426 | sinfo->chain->next = secinfo; | |
427 | } | |
428 | else | |
429 | secinfo->next = secinfo; | |
430 | sinfo->chain = secinfo; | |
431 | secinfo->sec = sec; | |
432 | secinfo->psecinfo = psecinfo; | |
f5fa8ca2 | 433 | secinfo->htab = sinfo->htab; |
57ceae94 | 434 | secinfo->first_str = NULL; |
f5fa8ca2 | 435 | |
eea6121a | 436 | sec->rawsize = sec->size; |
9ca98086 AM |
437 | if (sec->flags & SEC_STRINGS) |
438 | memset (secinfo->contents + sec->size, 0, sec->entsize); | |
dc810e39 | 439 | if (! bfd_get_section_contents (sec->owner, sec, secinfo->contents, |
eea6121a | 440 | 0, sec->size)) |
f5fa8ca2 JJ |
441 | goto error_return; |
442 | ||
b34976b6 | 443 | return TRUE; |
8550eb6e JJ |
444 | |
445 | error_return: | |
446 | *psecinfo = NULL; | |
b34976b6 | 447 | return FALSE; |
8550eb6e JJ |
448 | } |
449 | ||
8550eb6e | 450 | /* Record one section into the hash table. */ |
b34976b6 | 451 | static bfd_boolean |
9ca98086 | 452 | record_section (struct sec_merge_info *sinfo, |
ac0e732e | 453 | struct sec_merge_sec_info *secinfo) |
8550eb6e JJ |
454 | { |
455 | asection *sec = secinfo->sec; | |
456 | struct sec_merge_hash_entry *entry; | |
b34976b6 | 457 | bfd_boolean nul; |
8550eb6e JJ |
458 | unsigned char *p, *end; |
459 | bfd_vma mask, eltalign; | |
460 | unsigned int align, i; | |
461 | ||
57ceae94 | 462 | align = sec->alignment_power; |
eea6121a | 463 | end = secinfo->contents + sec->size; |
b34976b6 | 464 | nul = FALSE; |
dc810e39 | 465 | mask = ((bfd_vma) 1 << align) - 1; |
f5fa8ca2 JJ |
466 | if (sec->flags & SEC_STRINGS) |
467 | { | |
dc810e39 | 468 | for (p = secinfo->contents; p < end; ) |
f5fa8ca2 | 469 | { |
a531bbd2 JJ |
470 | eltalign = p - secinfo->contents; |
471 | eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1; | |
472 | if (!eltalign || eltalign > mask) | |
473 | eltalign = mask + 1; | |
f075ee0c AM |
474 | entry = sec_merge_add (sinfo->htab, (char *) p, (unsigned) eltalign, |
475 | secinfo); | |
8550eb6e JJ |
476 | if (! entry) |
477 | goto error_return; | |
f5fa8ca2 JJ |
478 | p += entry->len; |
479 | if (sec->entsize == 1) | |
480 | { | |
481 | while (p < end && *p == 0) | |
482 | { | |
483 | if (!nul && !((p - secinfo->contents) & mask)) | |
484 | { | |
b34976b6 | 485 | nul = TRUE; |
dc810e39 AM |
486 | entry = sec_merge_add (sinfo->htab, "", |
487 | (unsigned) mask + 1, secinfo); | |
8550eb6e JJ |
488 | if (! entry) |
489 | goto error_return; | |
f5fa8ca2 JJ |
490 | } |
491 | p++; | |
ddb2b442 | 492 | } |
f5fa8ca2 JJ |
493 | } |
494 | else | |
495 | { | |
496 | while (p < end) | |
497 | { | |
498 | for (i = 0; i < sec->entsize; i++) | |
499 | if (p[i] != '\0') | |
500 | break; | |
501 | if (i != sec->entsize) | |
502 | break; | |
503 | if (!nul && !((p - secinfo->contents) & mask)) | |
504 | { | |
b34976b6 | 505 | nul = TRUE; |
f075ee0c | 506 | entry = sec_merge_add (sinfo->htab, (char *) p, |
dc810e39 | 507 | (unsigned) mask + 1, secinfo); |
8550eb6e JJ |
508 | if (! entry) |
509 | goto error_return; | |
f5fa8ca2 JJ |
510 | } |
511 | p += sec->entsize; | |
512 | } | |
513 | } | |
514 | } | |
515 | } | |
516 | else | |
517 | { | |
518 | for (p = secinfo->contents; p < end; p += sec->entsize) | |
519 | { | |
f075ee0c | 520 | entry = sec_merge_add (sinfo->htab, (char *) p, 1, secinfo); |
8550eb6e JJ |
521 | if (! entry) |
522 | goto error_return; | |
523 | } | |
524 | } | |
525 | ||
b34976b6 | 526 | return TRUE; |
8550eb6e JJ |
527 | |
528 | error_return: | |
529 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
530 | *secinfo->psecinfo = NULL; | |
b34976b6 | 531 | return FALSE; |
8550eb6e JJ |
532 | } |
533 | ||
ddb2b442 AM |
534 | static int |
535 | strrevcmp (const void *a, const void *b) | |
536 | { | |
537 | struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; | |
538 | struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; | |
539 | unsigned int lenA = A->len; | |
540 | unsigned int lenB = B->len; | |
f075ee0c AM |
541 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
542 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 AM |
543 | int l = lenA < lenB ? lenA : lenB; |
544 | ||
545 | while (l) | |
546 | { | |
547 | if (*s != *t) | |
548 | return (int) *s - (int) *t; | |
549 | s--; | |
550 | t--; | |
551 | l--; | |
552 | } | |
553 | return lenA - lenB; | |
554 | } | |
555 | ||
556 | /* Like strrevcmp, but for the case where all strings have the same | |
557 | alignment > entsize. */ | |
558 | ||
559 | static int | |
560 | strrevcmp_align (const void *a, const void *b) | |
561 | { | |
562 | struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; | |
563 | struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; | |
564 | unsigned int lenA = A->len; | |
565 | unsigned int lenB = B->len; | |
f075ee0c AM |
566 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
567 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 AM |
568 | int l = lenA < lenB ? lenA : lenB; |
569 | int tail_align = (lenA & (A->alignment - 1)) - (lenB & (A->alignment - 1)); | |
570 | ||
571 | if (tail_align != 0) | |
572 | return tail_align; | |
573 | ||
574 | while (l) | |
575 | { | |
576 | if (*s != *t) | |
577 | return (int) *s - (int) *t; | |
578 | s--; | |
579 | t--; | |
580 | l--; | |
581 | } | |
582 | return lenA - lenB; | |
583 | } | |
584 | ||
585 | static inline int | |
586 | is_suffix (const struct sec_merge_hash_entry *A, | |
587 | const struct sec_merge_hash_entry *B) | |
588 | { | |
589 | if (A->len <= B->len) | |
590 | /* B cannot be a suffix of A unless A is equal to B, which is guaranteed | |
591 | not to be equal by the hash table. */ | |
592 | return 0; | |
593 | ||
594 | return memcmp (A->root.string + (A->len - B->len), | |
595 | B->root.string, B->len) == 0; | |
596 | } | |
597 | ||
8550eb6e JJ |
598 | /* This is a helper function for _bfd_merge_sections. It attempts to |
599 | merge strings matching suffixes of longer strings. */ | |
600 | static void | |
ac0e732e | 601 | merge_strings (struct sec_merge_info *sinfo) |
8550eb6e | 602 | { |
ddb2b442 | 603 | struct sec_merge_hash_entry **array, **a, *e; |
8550eb6e | 604 | struct sec_merge_sec_info *secinfo; |
dc810e39 | 605 | bfd_size_type size, amt; |
ddb2b442 | 606 | unsigned int alignment = 0; |
8550eb6e | 607 | |
ddb2b442 | 608 | /* Now sort the strings */ |
dc810e39 | 609 | amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); |
a50b1753 | 610 | array = (struct sec_merge_hash_entry **) bfd_malloc (amt); |
8550eb6e JJ |
611 | if (array == NULL) |
612 | goto alloc_failure; | |
613 | ||
614 | for (e = sinfo->htab->first, a = array; e; e = e->next) | |
615 | if (e->alignment) | |
ddb2b442 AM |
616 | { |
617 | *a++ = e; | |
618 | /* Adjust the length to not include the zero terminator. */ | |
619 | e->len -= sinfo->htab->entsize; | |
620 | if (alignment != e->alignment) | |
621 | { | |
622 | if (alignment == 0) | |
623 | alignment = e->alignment; | |
624 | else | |
625 | alignment = (unsigned) -1; | |
626 | } | |
627 | } | |
8550eb6e JJ |
628 | |
629 | sinfo->htab->size = a - array; | |
ddb2b442 | 630 | if (sinfo->htab->size != 0) |
8550eb6e | 631 | { |
ddb2b442 AM |
632 | qsort (array, (size_t) sinfo->htab->size, |
633 | sizeof (struct sec_merge_hash_entry *), | |
634 | (alignment != (unsigned) -1 && alignment > sinfo->htab->entsize | |
635 | ? strrevcmp_align : strrevcmp)); | |
636 | ||
637 | /* Loop over the sorted array and merge suffixes */ | |
638 | e = *--a; | |
639 | e->len += sinfo->htab->entsize; | |
640 | while (--a >= array) | |
8550eb6e | 641 | { |
ddb2b442 | 642 | struct sec_merge_hash_entry *cmp = *a; |
8550eb6e | 643 | |
ddb2b442 AM |
644 | cmp->len += sinfo->htab->entsize; |
645 | if (e->alignment >= cmp->alignment | |
646 | && !((e->len - cmp->len) & (cmp->alignment - 1)) | |
647 | && is_suffix (e, cmp)) | |
648 | { | |
649 | cmp->u.suffix = e; | |
650 | cmp->alignment = 0; | |
f5fa8ca2 | 651 | } |
8550eb6e | 652 | else |
ddb2b442 | 653 | e = cmp; |
8550eb6e | 654 | } |
f5fa8ca2 JJ |
655 | } |
656 | ||
8550eb6e JJ |
657 | alloc_failure: |
658 | if (array) | |
659 | free (array); | |
8550eb6e JJ |
660 | |
661 | /* Now assign positions to the strings we want to keep. */ | |
662 | size = 0; | |
663 | secinfo = sinfo->htab->first->secinfo; | |
664 | for (e = sinfo->htab->first; e; e = e->next) | |
665 | { | |
666 | if (e->secinfo != secinfo) | |
667 | { | |
eea6121a | 668 | secinfo->sec->size = size; |
8550eb6e JJ |
669 | secinfo = e->secinfo; |
670 | } | |
671 | if (e->alignment) | |
672 | { | |
57ceae94 | 673 | if (e->secinfo->first_str == NULL) |
8550eb6e | 674 | { |
57ceae94 | 675 | e->secinfo->first_str = e; |
8550eb6e JJ |
676 | size = 0; |
677 | } | |
678 | size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1); | |
679 | e->u.index = size; | |
680 | size += e->len; | |
681 | } | |
682 | } | |
eea6121a | 683 | secinfo->sec->size = size; |
8699aa54 AM |
684 | if (secinfo->sec->alignment_power != 0) |
685 | { | |
686 | bfd_size_type align = (bfd_size_type) 1 << secinfo->sec->alignment_power; | |
687 | secinfo->sec->size = (secinfo->sec->size + align - 1) & -align; | |
688 | } | |
8550eb6e JJ |
689 | |
690 | /* And now adjust the rest, removing them from the chain (but not hashtable) | |
691 | at the same time. */ | |
692 | for (a = &sinfo->htab->first, e = *a; e; e = e->next) | |
693 | if (e->alignment) | |
694 | a = &e->next; | |
695 | else | |
696 | { | |
697 | *a = e->next; | |
698 | if (e->len) | |
699 | { | |
700 | e->secinfo = e->u.suffix->secinfo; | |
701 | e->alignment = e->u.suffix->alignment; | |
702 | e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len); | |
703 | } | |
704 | } | |
705 | } | |
f5fa8ca2 | 706 | |
8550eb6e JJ |
707 | /* This function is called once after all SEC_MERGE sections are registered |
708 | with _bfd_merge_section. */ | |
709 | ||
b34976b6 | 710 | bfd_boolean |
e6c6c8f3 | 711 | _bfd_merge_sections (bfd *abfd, |
8423293d AM |
712 | struct bfd_link_info *info ATTRIBUTE_UNUSED, |
713 | void *xsinfo, | |
714 | void (*remove_hook) (bfd *, asection *)) | |
8550eb6e JJ |
715 | { |
716 | struct sec_merge_info *sinfo; | |
717 | ||
718 | for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) | |
719 | { | |
720 | struct sec_merge_sec_info * secinfo; | |
721 | ||
722 | if (! sinfo->chain) | |
723 | continue; | |
724 | ||
725 | /* Move sinfo->chain to head of the chain, terminate it. */ | |
726 | secinfo = sinfo->chain; | |
727 | sinfo->chain = secinfo->next; | |
728 | secinfo->next = NULL; | |
729 | ||
730 | /* Record the sections into the hash table. */ | |
731 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
732 | if (secinfo->sec->flags & SEC_EXCLUDE) | |
d3c456e9 JJ |
733 | { |
734 | *secinfo->psecinfo = NULL; | |
735 | if (remove_hook) | |
736 | (*remove_hook) (abfd, secinfo->sec); | |
737 | } | |
9ca98086 | 738 | else if (! record_section (sinfo, secinfo)) |
8550eb6e JJ |
739 | break; |
740 | ||
741 | if (secinfo) | |
742 | continue; | |
743 | ||
86eaf01e JJ |
744 | if (sinfo->htab->first == NULL) |
745 | continue; | |
746 | ||
8550eb6e JJ |
747 | if (sinfo->htab->strings) |
748 | merge_strings (sinfo); | |
749 | else | |
750 | { | |
751 | struct sec_merge_hash_entry *e; | |
752 | bfd_size_type size = 0; | |
753 | ||
754 | /* Things are much simpler for non-strings. | |
755 | Just assign them slots in the section. */ | |
756 | secinfo = NULL; | |
757 | for (e = sinfo->htab->first; e; e = e->next) | |
758 | { | |
57ceae94 | 759 | if (e->secinfo->first_str == NULL) |
8550eb6e JJ |
760 | { |
761 | if (secinfo) | |
eea6121a | 762 | secinfo->sec->size = size; |
57ceae94 | 763 | e->secinfo->first_str = e; |
8550eb6e JJ |
764 | size = 0; |
765 | } | |
766 | size = (size + e->alignment - 1) | |
767 | & ~((bfd_vma) e->alignment - 1); | |
768 | e->u.index = size; | |
769 | size += e->len; | |
770 | secinfo = e->secinfo; | |
771 | } | |
eea6121a | 772 | secinfo->sec->size = size; |
8550eb6e JJ |
773 | } |
774 | ||
27c630ba | 775 | /* Finally remove all input sections which have not made it into |
8550eb6e JJ |
776 | the hash table at all. */ |
777 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
57ceae94 | 778 | if (secinfo->first_str == NULL) |
a14a5de3 | 779 | secinfo->sec->flags |= SEC_EXCLUDE | SEC_KEEP; |
8550eb6e JJ |
780 | } |
781 | ||
b34976b6 | 782 | return TRUE; |
f5fa8ca2 JJ |
783 | } |
784 | ||
785 | /* Write out the merged section. */ | |
786 | ||
b34976b6 | 787 | bfd_boolean |
ac0e732e | 788 | _bfd_write_merged_section (bfd *output_bfd, asection *sec, void *psecinfo) |
f5fa8ca2 JJ |
789 | { |
790 | struct sec_merge_sec_info *secinfo; | |
dc810e39 | 791 | file_ptr pos; |
f5fa8ca2 JJ |
792 | |
793 | secinfo = (struct sec_merge_sec_info *) psecinfo; | |
794 | ||
e6c6c8f3 JM |
795 | if (!secinfo) |
796 | return FALSE; | |
797 | ||
57ceae94 | 798 | if (secinfo->first_str == NULL) |
b34976b6 | 799 | return TRUE; |
f5fa8ca2 | 800 | |
5dabe785 | 801 | /* FIXME: octets_per_byte. */ |
dc810e39 AM |
802 | pos = sec->output_section->filepos + sec->output_offset; |
803 | if (bfd_seek (output_bfd, pos, SEEK_SET) != 0) | |
b34976b6 | 804 | return FALSE; |
f5fa8ca2 | 805 | |
57ceae94 | 806 | if (! sec_merge_emit (output_bfd, secinfo->first_str)) |
b34976b6 | 807 | return FALSE; |
f5fa8ca2 | 808 | |
b34976b6 | 809 | return TRUE; |
f5fa8ca2 JJ |
810 | } |
811 | ||
812 | /* Adjust an address in the SEC_MERGE section. Given OFFSET within | |
813 | *PSEC, this returns the new offset in the adjusted SEC_MERGE | |
814 | section and writes the new section back into *PSEC. */ | |
815 | ||
816 | bfd_vma | |
ac0e732e | 817 | _bfd_merged_section_offset (bfd *output_bfd ATTRIBUTE_UNUSED, asection **psec, |
753731ee | 818 | void *psecinfo, bfd_vma offset) |
f5fa8ca2 JJ |
819 | { |
820 | struct sec_merge_sec_info *secinfo; | |
821 | struct sec_merge_hash_entry *entry; | |
822 | unsigned char *p; | |
823 | asection *sec = *psec; | |
824 | ||
825 | secinfo = (struct sec_merge_sec_info *) psecinfo; | |
826 | ||
e6c6c8f3 | 827 | if (!secinfo) |
9ca98086 | 828 | return offset; |
e6c6c8f3 | 829 | |
eea6121a | 830 | if (offset >= sec->rawsize) |
f5fa8ca2 | 831 | { |
eea6121a | 832 | if (offset > sec->rawsize) |
923f08ff AM |
833 | { |
834 | (*_bfd_error_handler) | |
753731ee AM |
835 | (_("%s: access beyond end of merged section (%ld)"), |
836 | bfd_get_filename (sec->owner), (long) offset); | |
923f08ff | 837 | } |
eea6121a | 838 | return secinfo->first_str ? sec->size : 0; |
f5fa8ca2 JJ |
839 | } |
840 | ||
841 | if (secinfo->htab->strings) | |
842 | { | |
843 | if (sec->entsize == 1) | |
844 | { | |
753731ee | 845 | p = secinfo->contents + offset - 1; |
894bb1ee | 846 | while (p >= secinfo->contents && *p) |
f5fa8ca2 JJ |
847 | --p; |
848 | ++p; | |
849 | } | |
850 | else | |
851 | { | |
753731ee | 852 | p = secinfo->contents + (offset / sec->entsize) * sec->entsize; |
f5fa8ca2 JJ |
853 | p -= sec->entsize; |
854 | while (p >= secinfo->contents) | |
855 | { | |
856 | unsigned int i; | |
857 | ||
858 | for (i = 0; i < sec->entsize; ++i) | |
859 | if (p[i] != '\0') | |
860 | break; | |
861 | if (i == sec->entsize) | |
862 | break; | |
863 | p -= sec->entsize; | |
864 | } | |
865 | p += sec->entsize; | |
866 | } | |
867 | } | |
868 | else | |
869 | { | |
753731ee | 870 | p = secinfo->contents + (offset / sec->entsize) * sec->entsize; |
f5fa8ca2 | 871 | } |
9ca98086 | 872 | entry = sec_merge_hash_lookup (secinfo->htab, (char *) p, 0, FALSE); |
f5fa8ca2 JJ |
873 | if (!entry) |
874 | { | |
875 | if (! secinfo->htab->strings) | |
876 | abort (); | |
877 | /* This should only happen if somebody points into the padding | |
878 | after a NUL character but before next entity. */ | |
879 | if (*p) | |
880 | abort (); | |
881 | if (! secinfo->htab->first) | |
882 | abort (); | |
883 | entry = secinfo->htab->first; | |
753731ee AM |
884 | p = (secinfo->contents + (offset / sec->entsize + 1) * sec->entsize |
885 | - entry->len); | |
f5fa8ca2 JJ |
886 | } |
887 | ||
8550eb6e JJ |
888 | *psec = entry->secinfo->sec; |
889 | return entry->u.index + (secinfo->contents + offset - p); | |
f5fa8ca2 | 890 | } |