2 Copyright (C) 2001-2023 Free Software Foundation, Inc.
3 Written by Jakub Jelinek <jakub@redhat.com>.
5 This file is part of BFD, the Binary File Descriptor library.
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 3 of the License, or
10 (at your option) any later version.
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.
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., 51 Franklin Street - Fifth Floor, Boston,
20 MA 02110-1301, USA. */
23 /* This file contains support for merging duplicate entities within sections,
24 as used in ELF SHF_MERGE. */
32 #include "libiberty.h"
34 /* We partition all mergable input sections into sets of similar
35 characteristics. These sets are the unit of merging. All content
36 of the input sections is scanned and inserted into a hash table.
37 We also remember an input-offset to entry mapping per input section, but
38 the content itself is removed. After everything is read in we assign
39 output offsets to all hash entries, and when relocations are processed we
40 lookup the given input offset per input-section, get the matching entry
41 and its output offset (possibly adjusted for offset pointing into the
44 The input-offset-to-entry mapping (in map_ofs/map) is sorted, so in principle
45 we could binary search it, but that's not cache-friendly and it's faster
46 to add another lookup structure that gets us very near the correct
47 entry in just one step (that's what ofstolowbound is for) and do a linear
50 /* An entry in the section merge hash table. */
52 struct sec_merge_hash_entry
54 /* Length of this entry. This includes the zero terminator. */
56 /* Start of this string needs to be aligned to
57 alignment octets (not 1 << align). */
58 unsigned int alignment
;
61 /* Index within the merged section. */
63 /* Entry this is a suffix of (if alignment is 0). */
64 struct sec_merge_hash_entry
*suffix
;
66 /* Next entity in the hash table (in order of entering). */
67 struct sec_merge_hash_entry
*next
;
71 /* The section merge hash table. */
75 struct bfd_hash_table table
;
76 /* Next available index. */
78 /* First entity in the SEC_MERGE sections of this type. */
79 struct sec_merge_hash_entry
*first
;
80 /* Last entity in the SEC_MERGE sections of this type. */
81 struct sec_merge_hash_entry
*last
;
84 /* Are entries fixed size or zero terminated strings? */
86 /* struct-of-array variant of all entries in the hash-table: */
87 unsigned int nbuckets
;
88 /* We keep hash-code and length of entry together in a separate
89 array in such a way that it can be checked with just a single memory
90 reference. In this way we don't need indirect access to the entries
91 in the normal case. keys_lens[i] is 'hashcode << 32) | len' for entry
92 i (which is pointed to be values[i]). */
94 struct sec_merge_hash_entry
**values
;
97 struct sec_merge_sec_info
;
99 /* Information per merged blob. This is the unit of merging and is
100 related to (multiple) input sections of similar characteristics
101 (alignment, entity size, strings or blobs). */
102 struct sec_merge_info
104 /* Chain of sec_merge_infos. */
105 struct sec_merge_info
*next
;
106 /* Chain of sec_merge_sec_infos. This first one will be the representative
107 section that conceptually collects all merged content. */
108 struct sec_merge_sec_info
*chain
;
109 struct sec_merge_sec_info
**last
;
110 /* A hash table used to hold section content. */
111 struct sec_merge_hash
*htab
;
114 /* Offset into input mergable sections are represented by this type.
115 Note how doesn't support crazy large mergable sections. */
116 typedef uint32_t mapofs_type
;
118 /* Given a sec_merge_sec_info S this gives the input offset of the IDX's
120 #define MAP_OFS(S,IDX) (S)->map_ofs[IDX]
121 /* And this gives the output offset (in the merged blob representing
123 #define MAP_IDX(S,IDX) (S)->map[IDX].idx
124 /* For quick lookup of output offset given an input offset we store
125 an array mapping intput-offset / OFSDIV to entry index.
126 16 is better than 8, 32 is roughly same as 16, but uses less memory, so
130 /* Information per input merge section. */
131 struct sec_merge_sec_info
133 /* Chain of sec_merge_sec_infos. */
134 struct sec_merge_sec_info
*next
;
135 /* The corresponding section. */
137 /* Pointer to merge_info pointing to us. */
139 /* The merge entity this is a part of. */
140 struct sec_merge_info
*sinfo
;
141 /* The section associated with sinfo (i.e. the representative section).
142 Same as sinfo->chain->sec, but faster to access in the hot function. */
144 /* First string in this section. */
145 struct sec_merge_hash_entry
*first_str
;
146 /* Sparse mapping from input offset to entry covering that offset: */
147 unsigned int noffsetmap
; /* Number of these mappings. */
148 mapofs_type
*map_ofs
; /* Input offset. */
150 struct sec_merge_hash_entry
*entry
; /* Covering hash entry ... */
151 bfd_size_type idx
; /* ... or destination offset. */
153 /* Quick access: index into map_ofs[]. ofstolowbound[o / OFSDIV]=I is
154 such that map_ofs[I] is the smallest offset higher that
155 rounddown(o, OFSDIV) (and hence I-1 is the largest entry whose offset is
156 smaller or equal to o/OFSDIV*OFSDIV). */
157 unsigned int *ofstolowbound
;
162 /* Given a merge hash table TABLE and a number of entries to be
163 ADDED, possibly resize the table for this to fit without further
167 sec_merge_maybe_resize (struct sec_merge_hash
*table
, unsigned added
)
169 struct bfd_hash_table
*bfdtab
= &table
->table
;
170 if (bfdtab
->count
+ added
> table
->nbuckets
* 2 / 3)
173 unsigned long newnb
= table
->nbuckets
* 2;
174 struct sec_merge_hash_entry
**newv
;
178 while (bfdtab
->count
+ added
> newnb
* 2 / 3)
185 alloc
= newnb
* sizeof (newl
[0]);
186 if (alloc
/ sizeof (newl
[0]) != newnb
)
188 newl
= objalloc_alloc ((struct objalloc
*) table
->table
.memory
, alloc
);
191 memset (newl
, 0, alloc
);
192 alloc
= newnb
* sizeof (newv
[0]);
193 if (alloc
/ sizeof (newv
[0]) != newnb
)
195 newv
= objalloc_alloc ((struct objalloc
*) table
->table
.memory
, alloc
);
198 memset (newv
, 0, alloc
);
200 for (i
= 0; i
< table
->nbuckets
; i
++)
202 struct sec_merge_hash_entry
*v
= table
->values
[i
];
205 uint32_t thishash
= table
->key_lens
[i
] >> 32;
206 unsigned idx
= thishash
& (newnb
- 1);
208 idx
= (idx
+ 1) & (newnb
- 1);
209 newl
[idx
] = table
->key_lens
[i
];
214 table
->key_lens
= newl
;
215 table
->values
= newv
;
216 table
->nbuckets
= newnb
;
221 /* Insert STRING (actually a byte blob of length LEN, with pre-computed
222 HASH and bucket _INDEX) into our hash TABLE. */
224 static struct sec_merge_hash_entry
*
225 sec_merge_hash_insert (struct sec_merge_hash
*table
,
227 uint64_t hash
, unsigned int len
, unsigned int _index
)
229 struct bfd_hash_table
*bfdtab
= &table
->table
;
230 struct sec_merge_hash_entry
*hashp
;
232 hashp
= (struct sec_merge_hash_entry
*)
233 bfd_hash_allocate (bfdtab
, len
+ sizeof (struct sec_merge_hash_entry
));
237 memcpy (hashp
->str
, string
, len
);
239 hashp
->alignment
= 0;
240 hashp
->u
.suffix
= NULL
;
242 // We must not need resizing, otherwise _index is wrong
243 BFD_ASSERT (bfdtab
->count
+ 1 <= table
->nbuckets
* 2 / 3);
245 table
->key_lens
[_index
] = (hash
<< 32) | (uint32_t)len
;
246 table
->values
[_index
] = hashp
;
251 /* Read four bytes from *STR, interpret it as 32bit unsigned little
252 endian value and return that. */
254 static inline uint32_t
255 hash_read32 (const char *str
)
258 /* All reasonable compilers will inline this memcpy and generate optimal
259 code on architectures that support unaligned (4-byte) accesses. */
261 #ifdef WORDS_BIGENDIAN
262 i
= (i
<< 24) | ((i
& 0xff00) << 8) | ((i
>> 8) & 0xff00) | (i
>> 24);
267 /* Calculate and return a hashvalue of the bytes at STR[0..LEN-1].
268 All non-zero lengths and all alignments are supported.
270 This is somewhat similar to xxh3 (of xxhash), but restricted to 32bit.
271 On cc1 strings this has quite similar statistic properties, and we
272 don't need to jump through hoops to get fast 64x64->128 mults,
273 or 64bit arith on 32 bit hosts. We also don't care for seeds
274 or secrets. They improve mixing very little. */
277 hash_blob (const char *str
, unsigned int len
)
280 uint32_t mul
= (1 << 0) + (1 << 2) + (1 << 3) + (1 << 5) + (1 << 7);
281 mul
+= (1 << 11) + (1 << 13) + (1 << 17) + (0 << 19) + (1 << 23) + (1 << 29);
285 uint32_t acc
= len
* 0x9e3779b1;
288 uint32_t i1
= hash_read32 (str
) ^ (0x396cfeb8 + 1*len
);
289 uint32_t i2
= hash_read32 (str
+ 4) ^ (0xbe4ba423 + 1*len
);
292 uint64_t m
= (uint64_t)i1
* i2
;
293 acc
+= (uint32_t)m
^ (uint32_t)(m
>> 32);
295 acc
= acc
^ (acc
>> 7);
296 uint64_t r
= (uint64_t)mul
* acc
;
297 ret
= (uint32_t)r
^ (uint32_t)(r
>> 32);
303 uint32_t i1
= hash_read32 (str
);
304 uint32_t i2
= hash_read32 (str
+ len
- 4);
305 i1
= ((i1
+ len
) ^ (i1
>> 7));
307 uint64_t r
= (uint64_t)mul
* i1
+ i2
;
308 ret
+= r
^ (r
>> 32);
312 /* Cleverly read in 1 to 3 bytes without further conditionals. */
313 unsigned char c1
= str
[0];
314 unsigned char c2
= str
[len
>> 1];
315 unsigned char c3
= str
[len
- 1];
316 uint32_t i1
= ((uint32_t)c1
<< 16) | ((uint32_t)c2
<< 24)
317 | ((uint32_t) c3
) | (len
<< 8);
319 uint64_t r
= (uint64_t)mul
* i1
;
320 ret
+= r
^ (r
>> 32);
326 /* Given a hash TABLE, return the hash of STRING (a blob described
327 according to info in TABLE, either a character string, or some fixed
328 size entity) and set *PLEN to the length of this blob. */
331 hashit (struct sec_merge_hash
*table
, const char *string
, unsigned int *plen
)
333 const unsigned char *s
;
337 s
= (const unsigned char *) string
;
340 if (table
->entsize
== 1)
341 len
= strlen (string
) + 1;
347 for (i
= 0; i
< table
->entsize
; ++i
)
350 if (i
== table
->entsize
)
355 len
*= table
->entsize
;
356 len
+= table
->entsize
;
360 len
= table
->entsize
;
361 hash
= hash_blob (string
, len
);
366 /* Lookup or insert a blob STRING (of length LEN, precomputed HASH and
367 input ALIGNMENT) into TABLE. Return the found or new hash table entry. */
369 static struct sec_merge_hash_entry
*
370 sec_merge_hash_lookup (struct sec_merge_hash
*table
, const char *string
,
371 unsigned int len
, uint64_t hash
,
372 unsigned int alignment
)
374 struct sec_merge_hash_entry
*hashp
;
377 /*printf ("YYY insert 0x%x into %u buckets (%s)\n",
378 (unsigned)hash, (unsigned)table->nbuckets, string);*/
379 uint64_t *key_lens
= table
->key_lens
;
380 struct sec_merge_hash_entry
**values
= table
->values
;
381 uint64_t hlen
= (hash
<< 32) | (uint32_t)len
;
382 unsigned int nbuckets
= table
->nbuckets
;
383 _index
= hash
& (nbuckets
- 1);
386 uint64_t candlen
= key_lens
[_index
];
388 && !memcmp (values
[_index
]->str
, string
, len
))
390 hashp
= values
[_index
];
391 if (hashp
->alignment
< alignment
)
392 hashp
->alignment
= alignment
;
395 if (!(candlen
& (uint32_t)-1))
397 _index
= (_index
+ 1) & (nbuckets
- 1);
400 hashp
= sec_merge_hash_insert (table
, string
, hash
, len
, _index
);
403 hashp
->alignment
= alignment
;
406 BFD_ASSERT (table
->size
== table
->table
.count
);
407 if (table
->first
== NULL
)
408 table
->first
= hashp
;
410 table
->last
->next
= hashp
;
416 /* Create a new hash table. */
418 static struct sec_merge_hash
*
419 sec_merge_init (unsigned int entsize
, bool strings
)
421 struct sec_merge_hash
*table
;
423 table
= (struct sec_merge_hash
*) bfd_malloc (sizeof (struct sec_merge_hash
));
427 if (! bfd_hash_table_init_n (&table
->table
, NULL
,
428 sizeof (struct sec_merge_hash_entry
), 0x2000))
437 table
->entsize
= entsize
;
438 table
->strings
= strings
;
440 table
->nbuckets
= 0x2000;
441 table
->key_lens
= objalloc_alloc ((struct objalloc
*) table
->table
.memory
,
442 table
->nbuckets
* sizeof (table
->key_lens
[0]));
443 memset (table
->key_lens
, 0, table
->nbuckets
* sizeof (table
->key_lens
[0]));
444 table
->values
= objalloc_alloc ((struct objalloc
*) table
->table
.memory
,
445 table
->nbuckets
* sizeof (table
->values
[0]));
446 memset (table
->values
, 0, table
->nbuckets
* sizeof (table
->values
[0]));
451 /* Append the tuple of input-offset O corresponding
452 to hash table ENTRY into SECINFO, such that we later may lookup the
456 append_offsetmap (struct sec_merge_sec_info
*secinfo
,
458 struct sec_merge_hash_entry
*entry
)
460 if ((secinfo
->noffsetmap
& 2047) == 0)
463 amt
= (secinfo
->noffsetmap
+ 2048);
464 secinfo
->map_ofs
= bfd_realloc (secinfo
->map_ofs
,
465 amt
* sizeof(secinfo
->map_ofs
[0]));
466 if (!secinfo
->map_ofs
)
468 secinfo
->map
= bfd_realloc (secinfo
->map
, amt
* sizeof(secinfo
->map
[0]));
472 unsigned int i
= secinfo
->noffsetmap
++;
473 MAP_OFS(secinfo
, i
) = o
;
474 secinfo
->map
[i
].entry
= entry
;
478 /* Prepare the input-offset-to-entry tables after output offsets are
482 prepare_offsetmap (struct sec_merge_sec_info
*secinfo
)
484 unsigned int noffsetmap
= secinfo
->noffsetmap
;
486 bfd_size_type l
, sz
, amt
;
488 secinfo
->fast_state
= 1;
490 for (i
= 0; i
< noffsetmap
; i
++)
491 MAP_IDX(secinfo
, i
) = secinfo
->map
[i
].entry
->u
.index
;
493 sz
= secinfo
->sec
->rawsize
;
494 amt
= (sz
/ OFSDIV
+ 1) * sizeof (secinfo
->ofstolowbound
[0]);
495 secinfo
->ofstolowbound
= bfd_zmalloc (amt
);
496 if (!secinfo
->ofstolowbound
)
498 for (l
= lbi
= 0; l
< sz
; l
+= OFSDIV
)
500 /* No need for bounds checking on lbi, as we've added a sentinel that's
501 larger than any offset. */
502 while (MAP_OFS(secinfo
, lbi
) <= l
)
504 //BFD_ASSERT ((l / OFSDIV) <= (i / OFSDIV));
505 secinfo
->ofstolowbound
[l
/ OFSDIV
] = lbi
;
507 secinfo
->fast_state
= 2;
511 sec_merge_emit (bfd
*abfd
, struct sec_merge_sec_info
*secinfo
,
512 unsigned char *contents
)
514 struct sec_merge_hash_entry
*entry
= secinfo
->first_str
;
515 asection
*sec
= secinfo
->sec
;
516 file_ptr offset
= sec
->output_offset
;
518 bfd_size_type off
= 0;
519 unsigned int opb
= bfd_octets_per_byte (abfd
, sec
);
520 int alignment_power
= sec
->output_section
->alignment_power
* opb
;
521 bfd_size_type pad_len
; /* Octets. */
523 /* FIXME: If alignment_power is 0 then really we should scan the
524 entry list for the largest required alignment and use that. */
525 pad_len
= alignment_power
? ((bfd_size_type
) 1 << alignment_power
) : 16;
527 pad
= (char *) bfd_zmalloc (pad_len
);
531 for (; entry
!= NULL
; entry
= entry
->next
)
538 BFD_ASSERT (entry
->alignment
);
539 len
= -off
& (entry
->alignment
- 1);
542 BFD_ASSERT (len
<= pad_len
);
545 memcpy (contents
+ offset
, pad
, len
);
548 else if (bfd_write (pad
, len
, abfd
) != len
)
558 memcpy (contents
+ offset
, str
, len
);
561 else if (bfd_write (str
, len
, abfd
) != len
)
568 /* Trailing alignment needed? */
569 off
= sec
->size
- off
;
572 BFD_ASSERT (off
<= pad_len
);
574 memcpy (contents
+ offset
, pad
, off
);
575 else if (bfd_write (pad
, off
, abfd
) != off
)
587 /* Register a SEC_MERGE section as a candidate for merging.
588 This function is called for all non-dynamic SEC_MERGE input sections. */
591 _bfd_add_merge_section (bfd
*abfd
, void **psinfo
, asection
*sec
,
594 struct sec_merge_info
*sinfo
;
595 struct sec_merge_sec_info
*secinfo
;
597 unsigned int alignment_power
; /* Octets. */
598 unsigned int align
; /* Octets. */
599 unsigned int opb
= bfd_octets_per_byte (abfd
, sec
);
601 if ((abfd
->flags
& DYNAMIC
) != 0
602 || (sec
->flags
& SEC_MERGE
) == 0)
606 || (sec
->flags
& SEC_EXCLUDE
) != 0
607 || sec
->entsize
== 0)
610 if (sec
->size
% sec
->entsize
!= 0)
613 if ((sec
->flags
& SEC_RELOC
) != 0)
615 /* We aren't prepared to handle relocations in merged sections. */
619 if (sec
->size
> (mapofs_type
)-1)
621 /* Input offsets must be representable by mapofs_type. */
628 alignment_power
= sec
->alignment_power
* opb
;
629 if (alignment_power
>= sizeof (align
) * CHAR_BIT
)
632 align
= 1u << alignment_power
;
633 if ((sec
->entsize
< align
634 && ((sec
->entsize
& (sec
->entsize
- 1))
635 || !(sec
->flags
& SEC_STRINGS
)))
636 || (sec
->entsize
> align
637 && (sec
->entsize
& (align
- 1))))
639 /* Sanity check. If string character size is smaller than
640 alignment, then we require character size to be a power
641 of 2, otherwise character size must be integer multiple
642 of alignment. For non-string constants, alignment must
643 be smaller than or equal to entity size and entity size
644 must be integer multiple of alignment. */
648 /* Initialize the descriptor for this input section. */
650 *psecinfo
= secinfo
= bfd_zalloc (abfd
, sizeof (*secinfo
));
651 if (*psecinfo
== NULL
)
655 secinfo
->psecinfo
= psecinfo
;
657 /* Search for a matching output merged section. */
658 for (sinfo
= (struct sec_merge_info
*) *psinfo
; sinfo
; sinfo
= sinfo
->next
)
660 && (repr
= sinfo
->chain
->sec
)
661 && ! ((repr
->flags
^ sec
->flags
) & (SEC_MERGE
| SEC_STRINGS
))
662 && repr
->entsize
== sec
->entsize
663 && repr
->alignment_power
== sec
->alignment_power
664 && repr
->output_section
== sec
->output_section
)
669 /* Initialize the information we need to keep track of. */
670 sinfo
= (struct sec_merge_info
*)
671 bfd_alloc (abfd
, sizeof (struct sec_merge_info
));
674 sinfo
->next
= (struct sec_merge_info
*) *psinfo
;
676 sinfo
->last
= &sinfo
->chain
;
678 sinfo
->htab
= sec_merge_init (sec
->entsize
, (sec
->flags
& SEC_STRINGS
));
679 if (sinfo
->htab
== NULL
)
683 *sinfo
->last
= secinfo
;
684 sinfo
->last
= &secinfo
->next
;
686 secinfo
->sinfo
= sinfo
;
687 secinfo
->reprsec
= sinfo
->chain
->sec
;
696 /* Record one whole input section (described by SECINFO) into the hash table
700 record_section (struct sec_merge_info
*sinfo
,
701 struct sec_merge_sec_info
*secinfo
)
703 asection
*sec
= secinfo
->sec
;
704 struct sec_merge_hash_entry
*entry
;
705 unsigned char *p
, *end
;
706 bfd_vma mask
, eltalign
;
712 if (sec
->flags
& SEC_STRINGS
)
713 /* Some versions of gcc may emit a string without a zero terminator.
714 See http://gcc.gnu.org/ml/gcc-patches/2006-06/msg01004.html
715 Allocate space for an extra zero. */
717 contents
= bfd_malloc (amt
);
721 /* Slurp in all section contents (possibly decompressing it). */
722 sec
->rawsize
= sec
->size
;
723 if (sec
->flags
& SEC_STRINGS
)
724 memset (contents
+ sec
->size
, 0, sec
->entsize
);
725 if (! bfd_get_full_section_contents (sec
->owner
, sec
, &contents
))
728 /* Now populate the hash table and offset mapping. */
730 /* Presize the hash table for what we're going to add. We overestimate
731 quite a bit, but if it turns out to be too much then other sections
732 merged into this area will make use of that as well. */
733 if (!sec_merge_maybe_resize (sinfo
->htab
, 1 + sec
->size
/ 2))
735 bfd_set_error (bfd_error_no_memory
);
739 /* Walk through the contents, calculate hashes and length of all
740 blobs (strings or fixed-size entries) we find and fill the
741 hash and offset tables. */
742 align
= sec
->alignment_power
;
743 mask
= ((bfd_vma
) 1 << align
) - 1;
744 end
= contents
+ sec
->size
;
745 for (p
= contents
; p
< end
;)
748 uint32_t hash
= hashit (sinfo
->htab
, (char*) p
, &len
);
749 unsigned int ofs
= p
- contents
;
751 eltalign
= ((eltalign
^ (eltalign
- 1)) + 1) >> 1;
752 if (!eltalign
|| eltalign
> mask
)
754 entry
= sec_merge_hash_lookup (sinfo
->htab
, (char *) p
, len
, hash
,
755 (unsigned) eltalign
);
758 if (! append_offsetmap (secinfo
, ofs
, entry
))
763 /* Add a sentinel element that's conceptually behind all others. */
764 append_offsetmap (secinfo
, sec
->size
, NULL
);
765 /* But don't count it. */
766 secinfo
->noffsetmap
--;
770 /*printf ("ZZZ %s:%s %u entries\n", sec->owner->filename, sec->name,
771 (unsigned)secinfo->noffsetmap);*/
778 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
779 *secinfo
->psecinfo
= NULL
;
783 /* qsort comparison function. Won't ever return zero as all entries
784 differ, so there is no issue with qsort stability here. */
787 strrevcmp (const void *a
, const void *b
)
789 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
790 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
791 unsigned int lenA
= A
->len
;
792 unsigned int lenB
= B
->len
;
793 const unsigned char *s
= (const unsigned char *) A
->str
+ lenA
- 1;
794 const unsigned char *t
= (const unsigned char *) B
->str
+ lenB
- 1;
795 int l
= lenA
< lenB
? lenA
: lenB
;
800 return (int) *s
- (int) *t
;
808 /* Like strrevcmp, but for the case where all strings have the same
809 alignment > entsize. */
812 strrevcmp_align (const void *a
, const void *b
)
814 struct sec_merge_hash_entry
*A
= *(struct sec_merge_hash_entry
**) a
;
815 struct sec_merge_hash_entry
*B
= *(struct sec_merge_hash_entry
**) b
;
816 unsigned int lenA
= A
->len
;
817 unsigned int lenB
= B
->len
;
818 const unsigned char *s
= (const unsigned char *) A
->str
+ lenA
- 1;
819 const unsigned char *t
= (const unsigned char *) B
->str
+ lenB
- 1;
820 int l
= lenA
< lenB
? lenA
: lenB
;
821 int tail_align
= (lenA
& (A
->alignment
- 1)) - (lenB
& (A
->alignment
- 1));
829 return (int) *s
- (int) *t
;
838 is_suffix (const struct sec_merge_hash_entry
*A
,
839 const struct sec_merge_hash_entry
*B
)
841 if (A
->len
<= B
->len
)
842 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
843 not to be equal by the hash table. */
846 return memcmp (A
->str
+ (A
->len
- B
->len
),
847 B
->str
, B
->len
) == 0;
850 /* This is a helper function for _bfd_merge_sections. It attempts to
851 merge strings matching suffixes of longer strings. */
852 static struct sec_merge_sec_info
*
853 merge_strings (struct sec_merge_info
*sinfo
)
855 struct sec_merge_hash_entry
**array
, **a
, *e
;
856 struct sec_merge_sec_info
*secinfo
;
857 bfd_size_type size
, amt
;
858 unsigned int alignment
= 0;
860 /* Now sort the strings */
861 amt
= sinfo
->htab
->size
* sizeof (struct sec_merge_hash_entry
*);
862 array
= (struct sec_merge_hash_entry
**) bfd_malloc (amt
);
866 for (e
= sinfo
->htab
->first
, a
= array
; e
; e
= e
->next
)
870 /* Adjust the length to not include the zero terminator. */
871 e
->len
-= sinfo
->htab
->entsize
;
872 if (alignment
!= e
->alignment
)
875 alignment
= e
->alignment
;
877 alignment
= (unsigned) -1;
881 sinfo
->htab
->size
= a
- array
;
882 if (sinfo
->htab
->size
!= 0)
884 qsort (array
, (size_t) sinfo
->htab
->size
,
885 sizeof (struct sec_merge_hash_entry
*),
886 (alignment
!= (unsigned) -1 && alignment
> sinfo
->htab
->entsize
887 ? strrevcmp_align
: strrevcmp
));
889 /* Loop over the sorted array and merge suffixes */
891 e
->len
+= sinfo
->htab
->entsize
;
894 struct sec_merge_hash_entry
*cmp
= *a
;
896 cmp
->len
+= sinfo
->htab
->entsize
;
897 if (e
->alignment
>= cmp
->alignment
898 && !((e
->len
- cmp
->len
) & (cmp
->alignment
- 1))
899 && is_suffix (e
, cmp
))
911 /* Now assign positions to the strings we want to keep. */
913 secinfo
= sinfo
->chain
;
914 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
918 size
= (size
+ e
->alignment
- 1) & ~((bfd_vma
) e
->alignment
- 1);
923 secinfo
->sec
->size
= size
;
925 /* And now adjust the rest, removing them from the chain (but not hashtable)
927 for (a
= &sinfo
->htab
->first
, e
= *a
; e
; e
= e
->next
)
935 e
->alignment
= e
->u
.suffix
->alignment
;
936 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
- e
->len
);
940 BFD_ASSERT (!secinfo
->first_str
);
941 secinfo
->first_str
= sinfo
->htab
->first
;
946 /* This function is called once after all SEC_MERGE sections are registered
947 with _bfd_merge_section. */
950 _bfd_merge_sections (bfd
*abfd
,
951 struct bfd_link_info
*info ATTRIBUTE_UNUSED
,
953 void (*remove_hook
) (bfd
*, asection
*))
955 struct sec_merge_info
*sinfo
;
957 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
959 struct sec_merge_sec_info
*secinfo
;
960 bfd_size_type align
; /* Bytes. */
965 /* Record the sections into the hash table. */
967 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
968 if (secinfo
->sec
->flags
& SEC_EXCLUDE
)
970 *secinfo
->psecinfo
= NULL
;
972 (*remove_hook
) (abfd
, secinfo
->sec
);
976 if (!record_section (sinfo
, secinfo
))
980 unsigned int opb
= bfd_octets_per_byte (abfd
, secinfo
->sec
);
982 align
= (bfd_size_type
) 1 << secinfo
->sec
->alignment_power
;
983 if (((secinfo
->sec
->size
/ opb
) & (align
- 1)) != 0)
988 if (sinfo
->htab
->first
== NULL
)
991 if (sinfo
->htab
->strings
)
993 secinfo
= merge_strings (sinfo
);
999 struct sec_merge_hash_entry
*e
= sinfo
->htab
->first
;
1000 bfd_size_type size
= 0; /* Octets. */
1002 /* Things are much simpler for non-strings.
1003 Just assign them slots in the section. */
1004 secinfo
= sinfo
->chain
;
1005 BFD_ASSERT (!secinfo
->first_str
);
1006 secinfo
->first_str
= e
;
1007 for (e
= sinfo
->htab
->first
; e
; e
= e
->next
)
1011 size
= (size
+ e
->alignment
- 1)
1012 & ~((bfd_vma
) e
->alignment
- 1);
1017 secinfo
->sec
->size
= size
;
1020 /* If the input sections were padded according to their alignments,
1021 then pad the output too. */
1023 secinfo
->sec
->size
= (secinfo
->sec
->size
+ align
- 1) & -align
;
1025 /* Finally remove all input sections which have not made it into
1026 the hash table at all. */
1027 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
1028 if (secinfo
->first_str
== NULL
)
1029 secinfo
->sec
->flags
|= SEC_EXCLUDE
| SEC_KEEP
;
1035 /* Write out the merged section. */
1038 _bfd_write_merged_section (bfd
*output_bfd
, asection
*sec
, void *psecinfo
)
1040 struct sec_merge_sec_info
*secinfo
;
1042 unsigned char *contents
;
1043 Elf_Internal_Shdr
*hdr
;
1045 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
1050 if (secinfo
->first_str
== NULL
)
1053 /* FIXME: octets_per_byte. */
1054 hdr
= &elf_section_data (sec
->output_section
)->this_hdr
;
1055 if (hdr
->sh_offset
== (file_ptr
) -1)
1057 /* We must compress this section. Write output to the
1059 contents
= hdr
->contents
;
1060 if (contents
== NULL
)
1066 pos
= sec
->output_section
->filepos
+ sec
->output_offset
;
1067 if (bfd_seek (output_bfd
, pos
, SEEK_SET
) != 0)
1071 BFD_ASSERT (sec
== secinfo
->sec
);
1072 BFD_ASSERT (secinfo
== secinfo
->sinfo
->chain
);
1073 if (! sec_merge_emit (output_bfd
, secinfo
, contents
))
1079 /* Adjust an address in the SEC_MERGE section. Given OFFSET within
1080 *PSEC, this returns the new offset in the adjusted SEC_MERGE
1081 section and writes the new section back into *PSEC. */
1084 _bfd_merged_section_offset (bfd
*output_bfd ATTRIBUTE_UNUSED
, asection
**psec
,
1085 void *psecinfo
, bfd_vma offset
)
1087 struct sec_merge_sec_info
*secinfo
;
1088 asection
*sec
= *psec
;
1090 secinfo
= (struct sec_merge_sec_info
*) psecinfo
;
1095 if (offset
>= sec
->rawsize
)
1097 if (offset
> sec
->rawsize
)
1099 /* xgettext:c-format */
1100 (_("%pB: access beyond end of merged section (%" PRId64
")"),
1101 sec
->owner
, (int64_t) offset
);
1102 return secinfo
->first_str
? sec
->size
: 0;
1105 if (secinfo
->fast_state
!= 2)
1107 if (!secinfo
->fast_state
)
1108 prepare_offsetmap (secinfo
);
1109 if (secinfo
->fast_state
!= 2)
1113 long lb
= secinfo
->ofstolowbound
[offset
/ OFSDIV
];
1114 *psec
= secinfo
->reprsec
;
1116 /* No need for bounds checking on lb, as we've added a sentinel that's
1117 larger than any offset. */
1118 while (MAP_OFS(secinfo
, lb
) <= offset
)
1122 /*printf ("YYY (%s:%s):%u -> (%s):%u\n",
1123 sec->owner->filename, sec->name, (unsigned)offset,
1124 (*psec)->name, (unsigned)lb);*/
1125 return MAP_IDX(secinfo
, lb
) + offset
- MAP_OFS(secinfo
, lb
);
1128 /* Tidy up when done. */
1131 _bfd_merge_sections_free (void *xsinfo
)
1133 struct sec_merge_info
*sinfo
;
1135 for (sinfo
= (struct sec_merge_info
*) xsinfo
; sinfo
; sinfo
= sinfo
->next
)
1137 struct sec_merge_sec_info
*secinfo
;
1138 for (secinfo
= sinfo
->chain
; secinfo
; secinfo
= secinfo
->next
)
1140 free (secinfo
->ofstolowbound
);
1141 free (secinfo
->map
);
1142 free (secinfo
->map_ofs
);
1144 bfd_hash_table_free (&sinfo
->htab
->table
);