Commit | Line | Data |
---|---|---|
f5fa8ca2 | 1 | /* SEC_MERGE support. |
219d1afa | 2 | Copyright (C) 2001-2018 Free Software Foundation, Inc. |
f5fa8ca2 JJ |
3 | Written by Jakub Jelinek <jakub@redhat.com>. |
4 | ||
7217313c | 5 | This file is part of BFD, the Binary File Descriptor library. |
f5fa8ca2 | 6 | |
7217313c NC |
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 | |
cd123cb7 | 9 | the Free Software Foundation; either version 3 of the License, or |
7217313c | 10 | (at your option) any later version. |
f5fa8ca2 | 11 | |
7217313c NC |
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. | |
f5fa8ca2 | 16 | |
7217313c NC |
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 | |
cd123cb7 NC |
19 | Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, |
20 | MA 02110-1301, USA. */ | |
21 | ||
f5fa8ca2 JJ |
22 | |
23 | /* This file contains support for merging duplicate entities within sections, | |
24 | as used in ELF SHF_MERGE. */ | |
25 | ||
f5fa8ca2 | 26 | #include "sysdep.h" |
3db64b00 | 27 | #include "bfd.h" |
0ce398f1 | 28 | #include "elf-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 | 111 | entry = (struct bfd_hash_entry *) |
07d6d2b8 | 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 |
0ce398f1 L |
287 | sec_merge_emit (bfd *abfd, struct sec_merge_hash_entry *entry, |
288 | unsigned char *contents, file_ptr offset) | |
f5fa8ca2 | 289 | { |
8550eb6e JJ |
290 | struct sec_merge_sec_info *secinfo = entry->secinfo; |
291 | asection *sec = secinfo->sec; | |
92ceba1e | 292 | char *pad = NULL; |
a531bbd2 | 293 | bfd_size_type off = 0; |
57ceae94 | 294 | int alignment_power = sec->output_section->alignment_power; |
38b28f70 | 295 | bfd_size_type pad_len; |
f5fa8ca2 | 296 | |
38b28f70 NC |
297 | /* FIXME: If alignment_power is 0 then really we should scan the |
298 | entry list for the largest required alignment and use that. */ | |
299 | pad_len = alignment_power ? ((bfd_size_type) 1 << alignment_power) : 16; | |
300 | ||
301 | pad = (char *) bfd_zmalloc (pad_len); | |
302 | if (pad == NULL) | |
303 | return FALSE; | |
f5fa8ca2 | 304 | |
8550eb6e | 305 | for (; entry != NULL && entry->secinfo == secinfo; entry = entry->next) |
f5fa8ca2 | 306 | { |
92ceba1e AM |
307 | const char *str; |
308 | bfd_size_type len; | |
f5fa8ca2 | 309 | |
92ceba1e AM |
310 | len = -off & (entry->alignment - 1); |
311 | if (len != 0) | |
a531bbd2 | 312 | { |
38b28f70 | 313 | BFD_ASSERT (len <= pad_len); |
0ce398f1 L |
314 | if (contents) |
315 | { | |
316 | memcpy (contents + offset, pad, len); | |
317 | offset += len; | |
318 | } | |
319 | else if (bfd_bwrite (pad, len, abfd) != len) | |
92ceba1e | 320 | goto err; |
a531bbd2 JJ |
321 | off += len; |
322 | } | |
323 | ||
f5fa8ca2 JJ |
324 | str = entry->root.string; |
325 | len = entry->len; | |
326 | ||
0ce398f1 L |
327 | if (contents) |
328 | { | |
329 | memcpy (contents + offset, str, len); | |
330 | offset += len; | |
331 | } | |
332 | else if (bfd_bwrite (str, len, abfd) != len) | |
92ceba1e | 333 | goto err; |
f5fa8ca2 | 334 | |
a531bbd2 | 335 | off += len; |
f5fa8ca2 JJ |
336 | } |
337 | ||
92ceba1e AM |
338 | /* Trailing alignment needed? */ |
339 | off = sec->size - off; | |
0ce398f1 L |
340 | if (off != 0) |
341 | { | |
38b28f70 | 342 | BFD_ASSERT (off <= pad_len); |
0ce398f1 L |
343 | if (contents) |
344 | memcpy (contents + offset, pad, off); | |
345 | else if (bfd_bwrite (pad, off, abfd) != off) | |
346 | goto err; | |
347 | } | |
92ceba1e | 348 | |
38b28f70 | 349 | free (pad); |
92ceba1e | 350 | return TRUE; |
f5fa8ca2 | 351 | |
92ceba1e | 352 | err: |
38b28f70 | 353 | free (pad); |
92ceba1e | 354 | return FALSE; |
f5fa8ca2 JJ |
355 | } |
356 | ||
57ceae94 AM |
357 | /* Register a SEC_MERGE section as a candidate for merging. |
358 | This function is called for all non-dynamic SEC_MERGE input sections. */ | |
f5fa8ca2 | 359 | |
b34976b6 | 360 | bfd_boolean |
57ceae94 AM |
361 | _bfd_add_merge_section (bfd *abfd, void **psinfo, asection *sec, |
362 | void **psecinfo) | |
f5fa8ca2 | 363 | { |
f5fa8ca2 JJ |
364 | struct sec_merge_info *sinfo; |
365 | struct sec_merge_sec_info *secinfo; | |
f5fa8ca2 | 366 | unsigned int align; |
dc810e39 | 367 | bfd_size_type amt; |
4a114e3e | 368 | bfd_byte *contents; |
f5fa8ca2 | 369 | |
57ceae94 AM |
370 | if ((abfd->flags & DYNAMIC) != 0 |
371 | || (sec->flags & SEC_MERGE) == 0) | |
372 | abort (); | |
373 | ||
eea6121a | 374 | if (sec->size == 0 |
57ceae94 | 375 | || (sec->flags & SEC_EXCLUDE) != 0 |
f5fa8ca2 | 376 | || sec->entsize == 0) |
b34976b6 | 377 | return TRUE; |
f5fa8ca2 | 378 | |
ab419ddb AM |
379 | if (sec->size % sec->entsize != 0) |
380 | return TRUE; | |
381 | ||
f5fa8ca2 JJ |
382 | if ((sec->flags & SEC_RELOC) != 0) |
383 | { | |
384 | /* We aren't prepared to handle relocations in merged sections. */ | |
b34976b6 | 385 | return TRUE; |
f5fa8ca2 JJ |
386 | } |
387 | ||
57ceae94 AM |
388 | align = sec->alignment_power; |
389 | if ((sec->entsize < (unsigned) 1 << align | |
a531bbd2 JJ |
390 | && ((sec->entsize & (sec->entsize - 1)) |
391 | || !(sec->flags & SEC_STRINGS))) | |
57ceae94 AM |
392 | || (sec->entsize > (unsigned) 1 << align |
393 | && (sec->entsize & (((unsigned) 1 << align) - 1)))) | |
f5fa8ca2 JJ |
394 | { |
395 | /* Sanity check. If string character size is smaller than | |
396 | alignment, then we require character size to be a power | |
397 | of 2, otherwise character size must be integer multiple | |
a531bbd2 JJ |
398 | of alignment. For non-string constants, alignment must |
399 | be smaller than or equal to entity size and entity size | |
400 | must be integer multiple of alignment. */ | |
b34976b6 | 401 | return TRUE; |
f5fa8ca2 JJ |
402 | } |
403 | ||
f5fa8ca2 | 404 | for (sinfo = (struct sec_merge_info *) *psinfo; sinfo; sinfo = sinfo->next) |
8550eb6e JJ |
405 | if ((secinfo = sinfo->chain) |
406 | && ! ((secinfo->sec->flags ^ sec->flags) & (SEC_MERGE | SEC_STRINGS)) | |
407 | && secinfo->sec->entsize == sec->entsize | |
57ceae94 AM |
408 | && secinfo->sec->alignment_power == sec->alignment_power |
409 | && secinfo->sec->output_section == sec->output_section) | |
f5fa8ca2 JJ |
410 | break; |
411 | ||
412 | if (sinfo == NULL) | |
413 | { | |
414 | /* Initialize the information we need to keep track of. */ | |
a50b1753 | 415 | sinfo = (struct sec_merge_info *) |
07d6d2b8 | 416 | bfd_alloc (abfd, sizeof (struct sec_merge_info)); |
f5fa8ca2 JJ |
417 | if (sinfo == NULL) |
418 | goto error_return; | |
419 | sinfo->next = (struct sec_merge_info *) *psinfo; | |
8550eb6e | 420 | sinfo->chain = NULL; |
ac0e732e | 421 | *psinfo = sinfo; |
699cb9b8 | 422 | sinfo->htab = sec_merge_init (sec->entsize, (sec->flags & SEC_STRINGS)); |
f5fa8ca2 JJ |
423 | if (sinfo->htab == NULL) |
424 | goto error_return; | |
425 | } | |
426 | ||
427 | /* Read the section from abfd. */ | |
428 | ||
9ca98086 AM |
429 | amt = sizeof (struct sec_merge_sec_info) - 1 + sec->size; |
430 | if (sec->flags & SEC_STRINGS) | |
431 | /* Some versions of gcc may emit a string without a zero terminator. | |
432 | See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html | |
433 | Allocate space for an extra zero. */ | |
434 | amt += sec->entsize; | |
dc810e39 | 435 | *psecinfo = bfd_alloc (abfd, amt); |
f5fa8ca2 JJ |
436 | if (*psecinfo == NULL) |
437 | goto error_return; | |
438 | ||
57ceae94 | 439 | secinfo = (struct sec_merge_sec_info *) *psecinfo; |
8550eb6e JJ |
440 | if (sinfo->chain) |
441 | { | |
442 | secinfo->next = sinfo->chain->next; | |
443 | sinfo->chain->next = secinfo; | |
444 | } | |
445 | else | |
446 | secinfo->next = secinfo; | |
447 | sinfo->chain = secinfo; | |
448 | secinfo->sec = sec; | |
449 | secinfo->psecinfo = psecinfo; | |
f5fa8ca2 | 450 | secinfo->htab = sinfo->htab; |
57ceae94 | 451 | secinfo->first_str = NULL; |
f5fa8ca2 | 452 | |
eea6121a | 453 | sec->rawsize = sec->size; |
9ca98086 AM |
454 | if (sec->flags & SEC_STRINGS) |
455 | memset (secinfo->contents + sec->size, 0, sec->entsize); | |
4a114e3e L |
456 | contents = secinfo->contents; |
457 | if (! bfd_get_full_section_contents (sec->owner, sec, &contents)) | |
f5fa8ca2 JJ |
458 | goto error_return; |
459 | ||
b34976b6 | 460 | return TRUE; |
8550eb6e JJ |
461 | |
462 | error_return: | |
463 | *psecinfo = NULL; | |
b34976b6 | 464 | return FALSE; |
8550eb6e JJ |
465 | } |
466 | ||
8550eb6e | 467 | /* Record one section into the hash table. */ |
b34976b6 | 468 | static bfd_boolean |
9ca98086 | 469 | record_section (struct sec_merge_info *sinfo, |
ac0e732e | 470 | struct sec_merge_sec_info *secinfo) |
8550eb6e JJ |
471 | { |
472 | asection *sec = secinfo->sec; | |
473 | struct sec_merge_hash_entry *entry; | |
b34976b6 | 474 | bfd_boolean nul; |
8550eb6e JJ |
475 | unsigned char *p, *end; |
476 | bfd_vma mask, eltalign; | |
477 | unsigned int align, i; | |
478 | ||
57ceae94 | 479 | align = sec->alignment_power; |
eea6121a | 480 | end = secinfo->contents + sec->size; |
b34976b6 | 481 | nul = FALSE; |
dc810e39 | 482 | mask = ((bfd_vma) 1 << align) - 1; |
f5fa8ca2 JJ |
483 | if (sec->flags & SEC_STRINGS) |
484 | { | |
dc810e39 | 485 | for (p = secinfo->contents; p < end; ) |
f5fa8ca2 | 486 | { |
a531bbd2 JJ |
487 | eltalign = p - secinfo->contents; |
488 | eltalign = ((eltalign ^ (eltalign - 1)) + 1) >> 1; | |
489 | if (!eltalign || eltalign > mask) | |
490 | eltalign = mask + 1; | |
f075ee0c AM |
491 | entry = sec_merge_add (sinfo->htab, (char *) p, (unsigned) eltalign, |
492 | secinfo); | |
8550eb6e JJ |
493 | if (! entry) |
494 | goto error_return; | |
f5fa8ca2 JJ |
495 | p += entry->len; |
496 | if (sec->entsize == 1) | |
497 | { | |
498 | while (p < end && *p == 0) | |
499 | { | |
500 | if (!nul && !((p - secinfo->contents) & mask)) | |
501 | { | |
b34976b6 | 502 | nul = TRUE; |
dc810e39 AM |
503 | entry = sec_merge_add (sinfo->htab, "", |
504 | (unsigned) mask + 1, secinfo); | |
8550eb6e JJ |
505 | if (! entry) |
506 | goto error_return; | |
f5fa8ca2 JJ |
507 | } |
508 | p++; | |
ddb2b442 | 509 | } |
f5fa8ca2 JJ |
510 | } |
511 | else | |
512 | { | |
513 | while (p < end) | |
514 | { | |
515 | for (i = 0; i < sec->entsize; i++) | |
516 | if (p[i] != '\0') | |
517 | break; | |
518 | if (i != sec->entsize) | |
519 | break; | |
520 | if (!nul && !((p - secinfo->contents) & mask)) | |
521 | { | |
b34976b6 | 522 | nul = TRUE; |
f075ee0c | 523 | entry = sec_merge_add (sinfo->htab, (char *) p, |
dc810e39 | 524 | (unsigned) mask + 1, secinfo); |
8550eb6e JJ |
525 | if (! entry) |
526 | goto error_return; | |
f5fa8ca2 JJ |
527 | } |
528 | p += sec->entsize; | |
529 | } | |
530 | } | |
531 | } | |
532 | } | |
533 | else | |
534 | { | |
535 | for (p = secinfo->contents; p < end; p += sec->entsize) | |
536 | { | |
f075ee0c | 537 | entry = sec_merge_add (sinfo->htab, (char *) p, 1, secinfo); |
8550eb6e JJ |
538 | if (! entry) |
539 | goto error_return; | |
540 | } | |
541 | } | |
542 | ||
b34976b6 | 543 | return TRUE; |
8550eb6e JJ |
544 | |
545 | error_return: | |
546 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
547 | *secinfo->psecinfo = NULL; | |
b34976b6 | 548 | return FALSE; |
8550eb6e JJ |
549 | } |
550 | ||
ddb2b442 AM |
551 | static int |
552 | strrevcmp (const void *a, const void *b) | |
553 | { | |
554 | struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; | |
555 | struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; | |
556 | unsigned int lenA = A->len; | |
557 | unsigned int lenB = B->len; | |
f075ee0c AM |
558 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
559 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 AM |
560 | int l = lenA < lenB ? lenA : lenB; |
561 | ||
562 | while (l) | |
563 | { | |
564 | if (*s != *t) | |
565 | return (int) *s - (int) *t; | |
566 | s--; | |
567 | t--; | |
568 | l--; | |
569 | } | |
570 | return lenA - lenB; | |
571 | } | |
572 | ||
573 | /* Like strrevcmp, but for the case where all strings have the same | |
574 | alignment > entsize. */ | |
575 | ||
576 | static int | |
577 | strrevcmp_align (const void *a, const void *b) | |
578 | { | |
579 | struct sec_merge_hash_entry *A = *(struct sec_merge_hash_entry **) a; | |
580 | struct sec_merge_hash_entry *B = *(struct sec_merge_hash_entry **) b; | |
581 | unsigned int lenA = A->len; | |
582 | unsigned int lenB = B->len; | |
f075ee0c AM |
583 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
584 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 AM |
585 | int l = lenA < lenB ? lenA : lenB; |
586 | int tail_align = (lenA & (A->alignment - 1)) - (lenB & (A->alignment - 1)); | |
587 | ||
588 | if (tail_align != 0) | |
589 | return tail_align; | |
590 | ||
591 | while (l) | |
592 | { | |
593 | if (*s != *t) | |
594 | return (int) *s - (int) *t; | |
595 | s--; | |
596 | t--; | |
597 | l--; | |
598 | } | |
599 | return lenA - lenB; | |
600 | } | |
601 | ||
602 | static inline int | |
603 | is_suffix (const struct sec_merge_hash_entry *A, | |
604 | const struct sec_merge_hash_entry *B) | |
605 | { | |
606 | if (A->len <= B->len) | |
607 | /* B cannot be a suffix of A unless A is equal to B, which is guaranteed | |
608 | not to be equal by the hash table. */ | |
609 | return 0; | |
610 | ||
611 | return memcmp (A->root.string + (A->len - B->len), | |
612 | B->root.string, B->len) == 0; | |
613 | } | |
614 | ||
8550eb6e JJ |
615 | /* This is a helper function for _bfd_merge_sections. It attempts to |
616 | merge strings matching suffixes of longer strings. */ | |
f6ac8c52 | 617 | static bfd_boolean |
ac0e732e | 618 | merge_strings (struct sec_merge_info *sinfo) |
8550eb6e | 619 | { |
ddb2b442 | 620 | struct sec_merge_hash_entry **array, **a, *e; |
8550eb6e | 621 | struct sec_merge_sec_info *secinfo; |
dc810e39 | 622 | bfd_size_type size, amt; |
ddb2b442 | 623 | unsigned int alignment = 0; |
8550eb6e | 624 | |
ddb2b442 | 625 | /* Now sort the strings */ |
dc810e39 | 626 | amt = sinfo->htab->size * sizeof (struct sec_merge_hash_entry *); |
a50b1753 | 627 | array = (struct sec_merge_hash_entry **) bfd_malloc (amt); |
8550eb6e | 628 | if (array == NULL) |
f6ac8c52 | 629 | return FALSE; |
8550eb6e JJ |
630 | |
631 | for (e = sinfo->htab->first, a = array; e; e = e->next) | |
632 | if (e->alignment) | |
ddb2b442 AM |
633 | { |
634 | *a++ = e; | |
635 | /* Adjust the length to not include the zero terminator. */ | |
636 | e->len -= sinfo->htab->entsize; | |
637 | if (alignment != e->alignment) | |
638 | { | |
639 | if (alignment == 0) | |
640 | alignment = e->alignment; | |
641 | else | |
642 | alignment = (unsigned) -1; | |
643 | } | |
644 | } | |
8550eb6e JJ |
645 | |
646 | sinfo->htab->size = a - array; | |
ddb2b442 | 647 | if (sinfo->htab->size != 0) |
8550eb6e | 648 | { |
ddb2b442 AM |
649 | qsort (array, (size_t) sinfo->htab->size, |
650 | sizeof (struct sec_merge_hash_entry *), | |
651 | (alignment != (unsigned) -1 && alignment > sinfo->htab->entsize | |
652 | ? strrevcmp_align : strrevcmp)); | |
653 | ||
654 | /* Loop over the sorted array and merge suffixes */ | |
655 | e = *--a; | |
656 | e->len += sinfo->htab->entsize; | |
657 | while (--a >= array) | |
8550eb6e | 658 | { |
ddb2b442 | 659 | struct sec_merge_hash_entry *cmp = *a; |
8550eb6e | 660 | |
ddb2b442 AM |
661 | cmp->len += sinfo->htab->entsize; |
662 | if (e->alignment >= cmp->alignment | |
663 | && !((e->len - cmp->len) & (cmp->alignment - 1)) | |
664 | && is_suffix (e, cmp)) | |
665 | { | |
666 | cmp->u.suffix = e; | |
667 | cmp->alignment = 0; | |
f5fa8ca2 | 668 | } |
8550eb6e | 669 | else |
ddb2b442 | 670 | e = cmp; |
8550eb6e | 671 | } |
f5fa8ca2 JJ |
672 | } |
673 | ||
f6ac8c52 | 674 | free (array); |
8550eb6e JJ |
675 | |
676 | /* Now assign positions to the strings we want to keep. */ | |
677 | size = 0; | |
678 | secinfo = sinfo->htab->first->secinfo; | |
679 | for (e = sinfo->htab->first; e; e = e->next) | |
680 | { | |
681 | if (e->secinfo != secinfo) | |
682 | { | |
eea6121a | 683 | secinfo->sec->size = size; |
8550eb6e JJ |
684 | secinfo = e->secinfo; |
685 | } | |
686 | if (e->alignment) | |
687 | { | |
57ceae94 | 688 | if (e->secinfo->first_str == NULL) |
8550eb6e | 689 | { |
57ceae94 | 690 | e->secinfo->first_str = e; |
8550eb6e JJ |
691 | size = 0; |
692 | } | |
693 | size = (size + e->alignment - 1) & ~((bfd_vma) e->alignment - 1); | |
694 | e->u.index = size; | |
695 | size += e->len; | |
696 | } | |
697 | } | |
eea6121a | 698 | secinfo->sec->size = size; |
8699aa54 AM |
699 | if (secinfo->sec->alignment_power != 0) |
700 | { | |
701 | bfd_size_type align = (bfd_size_type) 1 << secinfo->sec->alignment_power; | |
702 | secinfo->sec->size = (secinfo->sec->size + align - 1) & -align; | |
703 | } | |
8550eb6e JJ |
704 | |
705 | /* And now adjust the rest, removing them from the chain (but not hashtable) | |
706 | at the same time. */ | |
707 | for (a = &sinfo->htab->first, e = *a; e; e = e->next) | |
708 | if (e->alignment) | |
709 | a = &e->next; | |
710 | else | |
711 | { | |
712 | *a = e->next; | |
713 | if (e->len) | |
714 | { | |
715 | e->secinfo = e->u.suffix->secinfo; | |
716 | e->alignment = e->u.suffix->alignment; | |
717 | e->u.index = e->u.suffix->u.index + (e->u.suffix->len - e->len); | |
718 | } | |
719 | } | |
f6ac8c52 | 720 | return TRUE; |
8550eb6e | 721 | } |
f5fa8ca2 | 722 | |
8550eb6e JJ |
723 | /* This function is called once after all SEC_MERGE sections are registered |
724 | with _bfd_merge_section. */ | |
725 | ||
b34976b6 | 726 | bfd_boolean |
e6c6c8f3 | 727 | _bfd_merge_sections (bfd *abfd, |
8423293d AM |
728 | struct bfd_link_info *info ATTRIBUTE_UNUSED, |
729 | void *xsinfo, | |
730 | void (*remove_hook) (bfd *, asection *)) | |
8550eb6e JJ |
731 | { |
732 | struct sec_merge_info *sinfo; | |
733 | ||
734 | for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) | |
735 | { | |
736 | struct sec_merge_sec_info * secinfo; | |
737 | ||
738 | if (! sinfo->chain) | |
739 | continue; | |
740 | ||
741 | /* Move sinfo->chain to head of the chain, terminate it. */ | |
742 | secinfo = sinfo->chain; | |
743 | sinfo->chain = secinfo->next; | |
744 | secinfo->next = NULL; | |
745 | ||
746 | /* Record the sections into the hash table. */ | |
747 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
748 | if (secinfo->sec->flags & SEC_EXCLUDE) | |
d3c456e9 JJ |
749 | { |
750 | *secinfo->psecinfo = NULL; | |
751 | if (remove_hook) | |
752 | (*remove_hook) (abfd, secinfo->sec); | |
753 | } | |
9ca98086 | 754 | else if (! record_section (sinfo, secinfo)) |
f6ac8c52 | 755 | return FALSE; |
8550eb6e JJ |
756 | |
757 | if (secinfo) | |
758 | continue; | |
759 | ||
86eaf01e JJ |
760 | if (sinfo->htab->first == NULL) |
761 | continue; | |
762 | ||
8550eb6e | 763 | if (sinfo->htab->strings) |
f6ac8c52 AM |
764 | { |
765 | if (!merge_strings (sinfo)) | |
766 | return FALSE; | |
767 | } | |
8550eb6e JJ |
768 | else |
769 | { | |
770 | struct sec_merge_hash_entry *e; | |
771 | bfd_size_type size = 0; | |
772 | ||
773 | /* Things are much simpler for non-strings. | |
774 | Just assign them slots in the section. */ | |
775 | secinfo = NULL; | |
776 | for (e = sinfo->htab->first; e; e = e->next) | |
777 | { | |
57ceae94 | 778 | if (e->secinfo->first_str == NULL) |
8550eb6e JJ |
779 | { |
780 | if (secinfo) | |
eea6121a | 781 | secinfo->sec->size = size; |
57ceae94 | 782 | e->secinfo->first_str = e; |
8550eb6e JJ |
783 | size = 0; |
784 | } | |
785 | size = (size + e->alignment - 1) | |
786 | & ~((bfd_vma) e->alignment - 1); | |
787 | e->u.index = size; | |
788 | size += e->len; | |
789 | secinfo = e->secinfo; | |
790 | } | |
eea6121a | 791 | secinfo->sec->size = size; |
8550eb6e JJ |
792 | } |
793 | ||
27c630ba | 794 | /* Finally remove all input sections which have not made it into |
8550eb6e JJ |
795 | the hash table at all. */ |
796 | for (secinfo = sinfo->chain; secinfo; secinfo = secinfo->next) | |
57ceae94 | 797 | if (secinfo->first_str == NULL) |
a14a5de3 | 798 | secinfo->sec->flags |= SEC_EXCLUDE | SEC_KEEP; |
8550eb6e JJ |
799 | } |
800 | ||
b34976b6 | 801 | return TRUE; |
f5fa8ca2 JJ |
802 | } |
803 | ||
804 | /* Write out the merged section. */ | |
805 | ||
b34976b6 | 806 | bfd_boolean |
ac0e732e | 807 | _bfd_write_merged_section (bfd *output_bfd, asection *sec, void *psecinfo) |
f5fa8ca2 JJ |
808 | { |
809 | struct sec_merge_sec_info *secinfo; | |
dc810e39 | 810 | file_ptr pos; |
0ce398f1 L |
811 | unsigned char *contents; |
812 | Elf_Internal_Shdr *hdr; | |
f5fa8ca2 JJ |
813 | |
814 | secinfo = (struct sec_merge_sec_info *) psecinfo; | |
815 | ||
e6c6c8f3 JM |
816 | if (!secinfo) |
817 | return FALSE; | |
818 | ||
57ceae94 | 819 | if (secinfo->first_str == NULL) |
b34976b6 | 820 | return TRUE; |
f5fa8ca2 | 821 | |
5dabe785 | 822 | /* FIXME: octets_per_byte. */ |
0ce398f1 L |
823 | hdr = &elf_section_data (sec->output_section)->this_hdr; |
824 | if (hdr->sh_offset == (file_ptr) -1) | |
825 | { | |
826 | /* We must compress this section. Write output to the | |
827 | buffer. */ | |
828 | contents = hdr->contents; | |
829 | if ((sec->output_section->flags & SEC_ELF_COMPRESS) == 0 | |
830 | || contents == NULL) | |
831 | abort (); | |
832 | } | |
833 | else | |
834 | { | |
835 | contents = NULL; | |
836 | pos = sec->output_section->filepos + sec->output_offset; | |
837 | if (bfd_seek (output_bfd, pos, SEEK_SET) != 0) | |
838 | return FALSE; | |
839 | } | |
f5fa8ca2 | 840 | |
0ce398f1 L |
841 | if (! sec_merge_emit (output_bfd, secinfo->first_str, contents, |
842 | sec->output_offset)) | |
b34976b6 | 843 | return FALSE; |
f5fa8ca2 | 844 | |
b34976b6 | 845 | return TRUE; |
f5fa8ca2 JJ |
846 | } |
847 | ||
848 | /* Adjust an address in the SEC_MERGE section. Given OFFSET within | |
849 | *PSEC, this returns the new offset in the adjusted SEC_MERGE | |
850 | section and writes the new section back into *PSEC. */ | |
851 | ||
852 | bfd_vma | |
ac0e732e | 853 | _bfd_merged_section_offset (bfd *output_bfd ATTRIBUTE_UNUSED, asection **psec, |
753731ee | 854 | void *psecinfo, bfd_vma offset) |
f5fa8ca2 JJ |
855 | { |
856 | struct sec_merge_sec_info *secinfo; | |
857 | struct sec_merge_hash_entry *entry; | |
858 | unsigned char *p; | |
859 | asection *sec = *psec; | |
860 | ||
861 | secinfo = (struct sec_merge_sec_info *) psecinfo; | |
862 | ||
e6c6c8f3 | 863 | if (!secinfo) |
9ca98086 | 864 | return offset; |
e6c6c8f3 | 865 | |
eea6121a | 866 | if (offset >= sec->rawsize) |
f5fa8ca2 | 867 | { |
eea6121a | 868 | if (offset > sec->rawsize) |
4eca0228 | 869 | _bfd_error_handler |
695344c0 | 870 | /* xgettext:c-format */ |
2dcf00ce AM |
871 | (_("%pB: access beyond end of merged section (%" PRId64 ")"), |
872 | sec->owner, (int64_t) offset); | |
eea6121a | 873 | return secinfo->first_str ? sec->size : 0; |
f5fa8ca2 JJ |
874 | } |
875 | ||
876 | if (secinfo->htab->strings) | |
877 | { | |
878 | if (sec->entsize == 1) | |
879 | { | |
753731ee | 880 | p = secinfo->contents + offset - 1; |
894bb1ee | 881 | while (p >= secinfo->contents && *p) |
f5fa8ca2 JJ |
882 | --p; |
883 | ++p; | |
884 | } | |
885 | else | |
886 | { | |
753731ee | 887 | p = secinfo->contents + (offset / sec->entsize) * sec->entsize; |
f5fa8ca2 JJ |
888 | p -= sec->entsize; |
889 | while (p >= secinfo->contents) | |
890 | { | |
891 | unsigned int i; | |
892 | ||
893 | for (i = 0; i < sec->entsize; ++i) | |
894 | if (p[i] != '\0') | |
895 | break; | |
896 | if (i == sec->entsize) | |
897 | break; | |
898 | p -= sec->entsize; | |
899 | } | |
900 | p += sec->entsize; | |
901 | } | |
902 | } | |
903 | else | |
904 | { | |
753731ee | 905 | p = secinfo->contents + (offset / sec->entsize) * sec->entsize; |
f5fa8ca2 | 906 | } |
9ca98086 | 907 | entry = sec_merge_hash_lookup (secinfo->htab, (char *) p, 0, FALSE); |
f5fa8ca2 JJ |
908 | if (!entry) |
909 | { | |
910 | if (! secinfo->htab->strings) | |
911 | abort (); | |
912 | /* This should only happen if somebody points into the padding | |
913 | after a NUL character but before next entity. */ | |
914 | if (*p) | |
915 | abort (); | |
916 | if (! secinfo->htab->first) | |
917 | abort (); | |
918 | entry = secinfo->htab->first; | |
753731ee AM |
919 | p = (secinfo->contents + (offset / sec->entsize + 1) * sec->entsize |
920 | - entry->len); | |
f5fa8ca2 JJ |
921 | } |
922 | ||
8550eb6e JJ |
923 | *psec = entry->secinfo->sec; |
924 | return entry->u.index + (secinfo->contents + offset - p); | |
f5fa8ca2 | 925 | } |
9f7c3e5e AM |
926 | |
927 | /* Tidy up when done. */ | |
928 | ||
929 | void | |
930 | _bfd_merge_sections_free (void *xsinfo) | |
931 | { | |
932 | struct sec_merge_info *sinfo; | |
933 | ||
934 | for (sinfo = (struct sec_merge_info *) xsinfo; sinfo; sinfo = sinfo->next) | |
935 | { | |
936 | bfd_hash_table_free (&sinfo->htab->table); | |
937 | free (sinfo->htab); | |
938 | } | |
939 | } |