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