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