Commit | Line | Data |
---|---|---|
2b0f7ef9 | 1 | /* ELF strtab with GC and suffix merging support. |
82704155 | 2 | Copyright (C) 2001-2019 Free Software Foundation, Inc. |
2b0f7ef9 JJ |
3 | Written by Jakub Jelinek <jakub@redhat.com>. |
4 | ||
7217313c | 5 | This file is part of BFD, the Binary File Descriptor library. |
2b0f7ef9 | 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. |
2b0f7ef9 | 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. | |
2b0f7ef9 | 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. */ | |
2b0f7ef9 | 21 | |
2b0f7ef9 | 22 | #include "sysdep.h" |
3db64b00 | 23 | #include "bfd.h" |
2b0f7ef9 JJ |
24 | #include "libbfd.h" |
25 | #include "elf-bfd.h" | |
26 | #include "hashtab.h" | |
7217313c | 27 | #include "libiberty.h" |
2b0f7ef9 JJ |
28 | |
29 | /* An entry in the strtab hash table. */ | |
30 | ||
31 | struct elf_strtab_hash_entry | |
32 | { | |
33 | struct bfd_hash_entry root; | |
ddb2b442 AM |
34 | /* Length of this entry. This includes the zero terminator. */ |
35 | int len; | |
2b0f7ef9 JJ |
36 | unsigned int refcount; |
37 | union { | |
38 | /* Index within the merged section. */ | |
39 | bfd_size_type index; | |
ddb2b442 | 40 | /* Entry this is a suffix of (if len < 0). */ |
2b0f7ef9 JJ |
41 | struct elf_strtab_hash_entry *suffix; |
42 | } u; | |
43 | }; | |
44 | ||
45 | /* The strtab hash table. */ | |
46 | ||
47 | struct elf_strtab_hash | |
48 | { | |
49 | struct bfd_hash_table table; | |
50 | /* Next available index. */ | |
ef53be89 | 51 | size_t size; |
2b0f7ef9 | 52 | /* Number of array entries alloced. */ |
ef53be89 | 53 | size_t alloced; |
2b0f7ef9 JJ |
54 | /* Final strtab size. */ |
55 | bfd_size_type sec_size; | |
56 | /* Array of pointers to strtab entries. */ | |
57 | struct elf_strtab_hash_entry **array; | |
58 | }; | |
59 | ||
2b0f7ef9 JJ |
60 | /* Routine to create an entry in a section merge hashtab. */ |
61 | ||
62 | static struct bfd_hash_entry * | |
c39a58e6 AM |
63 | elf_strtab_hash_newfunc (struct bfd_hash_entry *entry, |
64 | struct bfd_hash_table *table, | |
65 | const char *string) | |
2b0f7ef9 | 66 | { |
2b0f7ef9 JJ |
67 | /* Allocate the structure if it has not already been allocated by a |
68 | subclass. */ | |
c39a58e6 | 69 | if (entry == NULL) |
a50b1753 | 70 | entry = (struct bfd_hash_entry *) |
07d6d2b8 | 71 | bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); |
c39a58e6 | 72 | if (entry == NULL) |
2b0f7ef9 JJ |
73 | return NULL; |
74 | ||
75 | /* Call the allocation method of the superclass. */ | |
c39a58e6 | 76 | entry = bfd_hash_newfunc (entry, table, string); |
2b0f7ef9 | 77 | |
c39a58e6 | 78 | if (entry) |
2b0f7ef9 JJ |
79 | { |
80 | /* Initialize the local fields. */ | |
c39a58e6 AM |
81 | struct elf_strtab_hash_entry *ret; |
82 | ||
83 | ret = (struct elf_strtab_hash_entry *) entry; | |
2b0f7ef9 JJ |
84 | ret->u.index = -1; |
85 | ret->refcount = 0; | |
86 | ret->len = 0; | |
87 | } | |
88 | ||
c39a58e6 | 89 | return entry; |
2b0f7ef9 JJ |
90 | } |
91 | ||
92 | /* Create a new hash table. */ | |
93 | ||
94 | struct elf_strtab_hash * | |
c39a58e6 | 95 | _bfd_elf_strtab_init (void) |
2b0f7ef9 JJ |
96 | { |
97 | struct elf_strtab_hash *table; | |
98 | bfd_size_type amt = sizeof (struct elf_strtab_hash); | |
99 | ||
a50b1753 | 100 | table = (struct elf_strtab_hash *) bfd_malloc (amt); |
2b0f7ef9 JJ |
101 | if (table == NULL) |
102 | return NULL; | |
103 | ||
66eb6687 AM |
104 | if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc, |
105 | sizeof (struct elf_strtab_hash_entry))) | |
2b0f7ef9 JJ |
106 | { |
107 | free (table); | |
108 | return NULL; | |
109 | } | |
110 | ||
111 | table->sec_size = 0; | |
112 | table->size = 1; | |
113 | table->alloced = 64; | |
114 | amt = sizeof (struct elf_strtab_hasn_entry *); | |
ef53be89 AM |
115 | table->array = ((struct elf_strtab_hash_entry **) |
116 | bfd_malloc (table->alloced * amt)); | |
2b0f7ef9 JJ |
117 | if (table->array == NULL) |
118 | { | |
119 | free (table); | |
120 | return NULL; | |
121 | } | |
122 | ||
123 | table->array[0] = NULL; | |
124 | ||
125 | return table; | |
126 | } | |
127 | ||
128 | /* Free a strtab. */ | |
129 | ||
130 | void | |
c39a58e6 | 131 | _bfd_elf_strtab_free (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
132 | { |
133 | bfd_hash_table_free (&tab->table); | |
134 | free (tab->array); | |
135 | free (tab); | |
136 | } | |
137 | ||
138 | /* Get the index of an entity in a hash table, adding it if it is not | |
139 | already present. */ | |
140 | ||
ef53be89 | 141 | size_t |
c39a58e6 AM |
142 | _bfd_elf_strtab_add (struct elf_strtab_hash *tab, |
143 | const char *str, | |
144 | bfd_boolean copy) | |
2b0f7ef9 JJ |
145 | { |
146 | register struct elf_strtab_hash_entry *entry; | |
147 | ||
148 | /* We handle this specially, since we don't want to do refcounting | |
149 | on it. */ | |
150 | if (*str == '\0') | |
151 | return 0; | |
152 | ||
153 | BFD_ASSERT (tab->sec_size == 0); | |
154 | entry = (struct elf_strtab_hash_entry *) | |
b34976b6 | 155 | bfd_hash_lookup (&tab->table, str, TRUE, copy); |
2b0f7ef9 JJ |
156 | |
157 | if (entry == NULL) | |
ef53be89 | 158 | return (size_t) -1; |
2b0f7ef9 JJ |
159 | |
160 | entry->refcount++; | |
161 | if (entry->len == 0) | |
162 | { | |
163 | entry->len = strlen (str) + 1; | |
ddb2b442 AM |
164 | /* 2G strings lose. */ |
165 | BFD_ASSERT (entry->len > 0); | |
2b0f7ef9 JJ |
166 | if (tab->size == tab->alloced) |
167 | { | |
168 | bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); | |
169 | tab->alloced *= 2; | |
a50b1753 | 170 | tab->array = (struct elf_strtab_hash_entry **) |
07d6d2b8 | 171 | bfd_realloc_or_free (tab->array, tab->alloced * amt); |
2b0f7ef9 | 172 | if (tab->array == NULL) |
ef53be89 | 173 | return (size_t) -1; |
2b0f7ef9 JJ |
174 | } |
175 | ||
176 | entry->u.index = tab->size++; | |
177 | tab->array[entry->u.index] = entry; | |
178 | } | |
179 | return entry->u.index; | |
180 | } | |
181 | ||
182 | void | |
ef53be89 | 183 | _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, size_t idx) |
2b0f7ef9 | 184 | { |
ef53be89 | 185 | if (idx == 0 || idx == (size_t) -1) |
2b0f7ef9 JJ |
186 | return; |
187 | BFD_ASSERT (tab->sec_size == 0); | |
188 | BFD_ASSERT (idx < tab->size); | |
189 | ++tab->array[idx]->refcount; | |
190 | } | |
191 | ||
192 | void | |
ef53be89 | 193 | _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, size_t idx) |
2b0f7ef9 | 194 | { |
ef53be89 | 195 | if (idx == 0 || idx == (size_t) -1) |
2b0f7ef9 JJ |
196 | return; |
197 | BFD_ASSERT (tab->sec_size == 0); | |
198 | BFD_ASSERT (idx < tab->size); | |
199 | BFD_ASSERT (tab->array[idx]->refcount > 0); | |
200 | --tab->array[idx]->refcount; | |
201 | } | |
202 | ||
02be4619 | 203 | unsigned int |
ef53be89 | 204 | _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, size_t idx) |
02be4619 AM |
205 | { |
206 | return tab->array[idx]->refcount; | |
207 | } | |
208 | ||
2b0f7ef9 | 209 | void |
d45f8bda | 210 | _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab) |
2b0f7ef9 | 211 | { |
ef53be89 | 212 | size_t idx; |
d45f8bda AM |
213 | |
214 | for (idx = 1; idx < tab->size; idx++) | |
215 | tab->array[idx]->refcount = 0; | |
216 | } | |
217 | ||
5b677558 AM |
218 | /* Save strtab refcounts prior to adding --as-needed library. */ |
219 | ||
220 | struct strtab_save | |
221 | { | |
ef53be89 | 222 | size_t size; |
5b677558 AM |
223 | unsigned int refcount[1]; |
224 | }; | |
225 | ||
226 | void * | |
227 | _bfd_elf_strtab_save (struct elf_strtab_hash *tab) | |
228 | { | |
229 | struct strtab_save *save; | |
ef53be89 | 230 | size_t idx, size; |
5b677558 AM |
231 | |
232 | size = sizeof (*save) + (tab->size - 1) * sizeof (save->refcount[0]); | |
233 | save = bfd_malloc (size); | |
234 | if (save == NULL) | |
235 | return save; | |
236 | ||
237 | save->size = tab->size; | |
238 | for (idx = 1; idx < tab->size; idx++) | |
239 | save->refcount[idx] = tab->array[idx]->refcount; | |
240 | return save; | |
241 | } | |
242 | ||
243 | /* Restore strtab refcounts on finding --as-needed library not needed. */ | |
244 | ||
d45f8bda | 245 | void |
5b677558 | 246 | _bfd_elf_strtab_restore (struct elf_strtab_hash *tab, void *buf) |
d45f8bda | 247 | { |
ef53be89 | 248 | size_t idx, curr_size = tab->size; |
5b677558 | 249 | struct strtab_save *save = (struct strtab_save *) buf; |
d45f8bda AM |
250 | |
251 | BFD_ASSERT (tab->sec_size == 0); | |
5b677558 AM |
252 | BFD_ASSERT (save->size <= curr_size); |
253 | tab->size = save->size; | |
254 | for (idx = 1; idx < save->size; ++idx) | |
255 | tab->array[idx]->refcount = save->refcount[idx]; | |
256 | ||
d45f8bda AM |
257 | for (; idx < curr_size; ++idx) |
258 | { | |
259 | /* We don't remove entries from the hash table, just set their | |
260 | REFCOUNT to zero. Setting LEN zero will result in the size | |
261 | growing if the entry is added again. See _bfd_elf_strtab_add. */ | |
262 | tab->array[idx]->refcount = 0; | |
263 | tab->array[idx]->len = 0; | |
264 | } | |
2b0f7ef9 JJ |
265 | } |
266 | ||
267 | bfd_size_type | |
c39a58e6 | 268 | _bfd_elf_strtab_size (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
269 | { |
270 | return tab->sec_size ? tab->sec_size : tab->size; | |
271 | } | |
272 | ||
273 | bfd_size_type | |
ef53be89 | 274 | _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, size_t idx) |
2b0f7ef9 JJ |
275 | { |
276 | struct elf_strtab_hash_entry *entry; | |
277 | ||
278 | if (idx == 0) | |
279 | return 0; | |
280 | BFD_ASSERT (idx < tab->size); | |
281 | BFD_ASSERT (tab->sec_size); | |
282 | entry = tab->array[idx]; | |
283 | BFD_ASSERT (entry->refcount > 0); | |
284 | entry->refcount--; | |
285 | return tab->array[idx]->u.index; | |
286 | } | |
287 | ||
b34976b6 | 288 | bfd_boolean |
c39a58e6 | 289 | _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) |
2b0f7ef9 | 290 | { |
ef53be89 AM |
291 | bfd_size_type off = 1; |
292 | size_t i; | |
2b0f7ef9 JJ |
293 | |
294 | if (bfd_bwrite ("", 1, abfd) != 1) | |
b34976b6 | 295 | return FALSE; |
2b0f7ef9 JJ |
296 | |
297 | for (i = 1; i < tab->size; ++i) | |
298 | { | |
299 | register const char *str; | |
ddb2b442 | 300 | register unsigned int len; |
2b0f7ef9 | 301 | |
2b0f7ef9 | 302 | BFD_ASSERT (tab->array[i]->refcount == 0); |
ddb2b442 AM |
303 | len = tab->array[i]->len; |
304 | if ((int) len < 0) | |
2b0f7ef9 JJ |
305 | continue; |
306 | ||
ddb2b442 | 307 | str = tab->array[i]->root.string; |
c39a58e6 | 308 | if (bfd_bwrite (str, len, abfd) != len) |
b34976b6 | 309 | return FALSE; |
2b0f7ef9 JJ |
310 | |
311 | off += len; | |
312 | } | |
313 | ||
314 | BFD_ASSERT (off == tab->sec_size); | |
b34976b6 | 315 | return TRUE; |
2b0f7ef9 JJ |
316 | } |
317 | ||
ddb2b442 | 318 | /* Compare two elf_strtab_hash_entry structures. Called via qsort. */ |
2b0f7ef9 JJ |
319 | |
320 | static int | |
ddb2b442 | 321 | strrevcmp (const void *a, const void *b) |
2b0f7ef9 | 322 | { |
c39a58e6 AM |
323 | struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; |
324 | struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; | |
ddb2b442 AM |
325 | unsigned int lenA = A->len; |
326 | unsigned int lenB = B->len; | |
f075ee0c AM |
327 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
328 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 | 329 | int l = lenA < lenB ? lenA : lenB; |
2b0f7ef9 | 330 | |
ddb2b442 AM |
331 | while (l) |
332 | { | |
333 | if (*s != *t) | |
334 | return (int) *s - (int) *t; | |
335 | s--; | |
336 | t--; | |
337 | l--; | |
338 | } | |
339 | return lenA - lenB; | |
2b0f7ef9 JJ |
340 | } |
341 | ||
ddb2b442 AM |
342 | static inline int |
343 | is_suffix (const struct elf_strtab_hash_entry *A, | |
344 | const struct elf_strtab_hash_entry *B) | |
2b0f7ef9 | 345 | { |
2b0f7ef9 JJ |
346 | if (A->len <= B->len) |
347 | /* B cannot be a suffix of A unless A is equal to B, which is guaranteed | |
348 | not to be equal by the hash table. */ | |
349 | return 0; | |
350 | ||
351 | return memcmp (A->root.string + (A->len - B->len), | |
ddb2b442 | 352 | B->root.string, B->len - 1) == 0; |
2b0f7ef9 JJ |
353 | } |
354 | ||
2b0f7ef9 JJ |
355 | /* This function assigns final string table offsets for used strings, |
356 | merging strings matching suffixes of longer strings if possible. */ | |
357 | ||
358 | void | |
c39a58e6 | 359 | _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) |
2b0f7ef9 | 360 | { |
ddb2b442 | 361 | struct elf_strtab_hash_entry **array, **a, *e; |
ef53be89 AM |
362 | bfd_size_type amt, sec_size; |
363 | size_t size, i; | |
2b0f7ef9 | 364 | |
ddb2b442 | 365 | /* Sort the strings by suffix and length. */ |
ef53be89 AM |
366 | amt = tab->size; |
367 | amt *= sizeof (struct elf_strtab_hash_entry *); | |
a50b1753 | 368 | array = (struct elf_strtab_hash_entry **) bfd_malloc (amt); |
2b0f7ef9 JJ |
369 | if (array == NULL) |
370 | goto alloc_failure; | |
371 | ||
372 | for (i = 1, a = array; i < tab->size; ++i) | |
ddb2b442 AM |
373 | { |
374 | e = tab->array[i]; | |
375 | if (e->refcount) | |
376 | { | |
377 | *a++ = e; | |
378 | /* Adjust the length to not include the zero terminator. */ | |
379 | e->len -= 1; | |
380 | } | |
381 | else | |
382 | e->len = 0; | |
383 | } | |
2b0f7ef9 JJ |
384 | |
385 | size = a - array; | |
ddb2b442 AM |
386 | if (size != 0) |
387 | { | |
388 | qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); | |
2b0f7ef9 | 389 | |
ddb2b442 AM |
390 | /* Loop over the sorted array and merge suffixes. Start from the |
391 | end because we want eg. | |
2b0f7ef9 | 392 | |
ddb2b442 AM |
393 | s1 -> "d" |
394 | s2 -> "bcd" | |
395 | s3 -> "abcd" | |
2b0f7ef9 | 396 | |
ddb2b442 | 397 | to end up as |
2b0f7ef9 | 398 | |
ddb2b442 AM |
399 | s3 -> "abcd" |
400 | s2 _____^ | |
401 | s1 _______^ | |
2b0f7ef9 | 402 | |
ddb2b442 AM |
403 | ie. we don't want s1 pointing into the old s2. */ |
404 | e = *--a; | |
405 | e->len += 1; | |
406 | while (--a >= array) | |
407 | { | |
408 | struct elf_strtab_hash_entry *cmp = *a; | |
53c3f2be | 409 | |
ddb2b442 AM |
410 | cmp->len += 1; |
411 | if (is_suffix (e, cmp)) | |
53c3f2be | 412 | { |
ddb2b442 AM |
413 | cmp->u.suffix = e; |
414 | cmp->len = -cmp->len; | |
53c3f2be | 415 | } |
ddb2b442 AM |
416 | else |
417 | e = cmp; | |
2b0f7ef9 | 418 | } |
2b0f7ef9 JJ |
419 | } |
420 | ||
421 | alloc_failure: | |
422 | if (array) | |
423 | free (array); | |
2b0f7ef9 | 424 | |
ddb2b442 | 425 | /* Assign positions to the strings we want to keep. */ |
ef53be89 | 426 | sec_size = 1; |
2b0f7ef9 JJ |
427 | for (i = 1; i < tab->size; ++i) |
428 | { | |
429 | e = tab->array[i]; | |
ddb2b442 | 430 | if (e->refcount && e->len > 0) |
2b0f7ef9 | 431 | { |
ef53be89 AM |
432 | e->u.index = sec_size; |
433 | sec_size += e->len; | |
2b0f7ef9 JJ |
434 | } |
435 | } | |
436 | ||
ef53be89 | 437 | tab->sec_size = sec_size; |
2b0f7ef9 | 438 | |
ddb2b442 | 439 | /* Adjust the rest. */ |
2b0f7ef9 JJ |
440 | for (i = 1; i < tab->size; ++i) |
441 | { | |
442 | e = tab->array[i]; | |
ddb2b442 AM |
443 | if (e->refcount && e->len < 0) |
444 | e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); | |
2b0f7ef9 JJ |
445 | } |
446 | } |