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