1 /* ELF strtab with GC and suffix merging support.
2 Copyright (C) 2001-2023 Free Software Foundation, Inc.
3 Written by Jakub Jelinek <jakub@redhat.com>.
4
5 This file is part of BFD, the Binary File Descriptor library.
6
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.
11
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.
16
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. */
21
22 #include "sysdep.h"
23 #include "bfd.h"
24 #include "libbfd.h"
25 #include "elf-bfd.h"
26 #include "hashtab.h"
27 #include "libiberty.h"
28
29 /* An entry in the strtab hash table. */
30
31 struct elf_strtab_hash_entry
32 {
33 struct bfd_hash_entry root;
34 /* Length of this entry. This includes the zero terminator. */
35 int len;
36 unsigned int refcount;
37 union {
38 /* Index within the merged section. */
39 bfd_size_type index;
40 /* Entry this is a suffix of (if len < 0). */
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. */
51 size_t size;
52 /* Number of array entries alloced. */
53 size_t alloced;
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
60 /* Routine to create an entry in a section merge hashtab. */
61
62 static struct bfd_hash_entry *
63 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
64 struct bfd_hash_table *table,
65 const char *string)
66 {
67 /* Allocate the structure if it has not already been allocated by a
68 subclass. */
69 if (entry == NULL)
70 entry = (struct bfd_hash_entry *)
71 bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
72 if (entry == NULL)
73 return NULL;
74
75 /* Call the allocation method of the superclass. */
76 entry = bfd_hash_newfunc (entry, table, string);
77
78 if (entry)
79 {
80 /* Initialize the local fields. */
81 struct elf_strtab_hash_entry *ret;
82
83 ret = (struct elf_strtab_hash_entry *) entry;
84 ret->u.index = -1;
85 ret->refcount = 0;
86 ret->len = 0;
87 }
88
89 return entry;
90 }
91
92 /* Create a new hash table. */
93
94 struct elf_strtab_hash *
95 _bfd_elf_strtab_init (void)
96 {
97 struct elf_strtab_hash *table;
98 size_t amt = sizeof (struct elf_strtab_hash);
99
100 table = (struct elf_strtab_hash *) bfd_malloc (amt);
101 if (table == NULL)
102 return NULL;
103
104 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
105 sizeof (struct elf_strtab_hash_entry)))
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 *);
115 table->array = ((struct elf_strtab_hash_entry **)
116 bfd_malloc (table->alloced * amt));
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
131 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
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
141 size_t
142 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
143 const char *str,
144 bool copy)
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 *)
155 bfd_hash_lookup (&tab->table, str, true, copy);
156
157 if (entry == NULL)
158 return (size_t) -1;
159
160 entry->refcount++;
161 if (entry->len == 0)
162 {
163 entry->len = strlen (str) + 1;
164 /* 2G strings lose. */
165 BFD_ASSERT (entry->len > 0);
166 if (tab->size == tab->alloced)
167 {
168 bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
169 tab->alloced *= 2;
170 tab->array = (struct elf_strtab_hash_entry **)
171 bfd_realloc_or_free (tab->array, tab->alloced * amt);
172 if (tab->array == NULL)
173 return (size_t) -1;
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
183 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, size_t idx)
184 {
185 if (idx == 0 || idx == (size_t) -1)
186 return;
187 BFD_ASSERT (tab->sec_size == 0);
188 BFD_ASSERT (idx < tab->size);
189 ++tab->array[idx]->refcount;
190 }
191
192 void
193 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, size_t idx)
194 {
195 if (idx == 0 || idx == (size_t) -1)
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
203 unsigned int
204 _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, size_t idx)
205 {
206 return tab->array[idx]->refcount;
207 }
208
209 void
210 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
211 {
212 size_t idx;
213
214 for (idx = 1; idx < tab->size; idx++)
215 tab->array[idx]->refcount = 0;
216 }
217
218 /* Save strtab refcounts prior to adding --as-needed library. */
219
220 struct strtab_save
221 {
222 size_t size;
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;
230 size_t idx, size;
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
245 void
246 _bfd_elf_strtab_restore (struct elf_strtab_hash *tab, void *buf)
247 {
248 size_t idx, curr_size = tab->size, save_size;
249 struct strtab_save *save = (struct strtab_save *) buf;
250
251 BFD_ASSERT (tab->sec_size == 0);
252 save_size = 1;
253 if (save != NULL)
254 save_size = save->size;
255 BFD_ASSERT (save_size <= curr_size);
256 tab->size = save_size;
257 for (idx = 1; idx < save_size; ++idx)
258 tab->array[idx]->refcount = save->refcount[idx];
259
260 for (; idx < curr_size; ++idx)
261 {
262 /* We don't remove entries from the hash table, just set their
263 REFCOUNT to zero. Setting LEN zero will result in the size
264 growing if the entry is added again. See _bfd_elf_strtab_add. */
265 tab->array[idx]->refcount = 0;
266 tab->array[idx]->len = 0;
267 }
268 }
269
270 bfd_size_type
271 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
272 {
273 return tab->sec_size ? tab->sec_size : tab->size;
274 }
275
276 bfd_size_type
277 _bfd_elf_strtab_len (struct elf_strtab_hash *tab)
278 {
279 return tab->size;
280 }
281
282 bfd_size_type
283 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, size_t idx)
284 {
285 struct elf_strtab_hash_entry *entry;
286
287 if (idx == 0)
288 return 0;
289 BFD_ASSERT (idx < tab->size);
290 BFD_ASSERT (tab->sec_size);
291 entry = tab->array[idx];
292 BFD_ASSERT (entry->refcount > 0);
293 entry->refcount--;
294 return tab->array[idx]->u.index;
295 }
296
297 const char *
298 _bfd_elf_strtab_str (struct elf_strtab_hash *tab, size_t idx,
299 bfd_size_type *offset)
300 {
301 if (idx == 0)
302 return NULL;
303 BFD_ASSERT (idx < tab->size);
304 BFD_ASSERT (tab->sec_size);
305 if (tab->array[idx]->refcount == 0)
306 return NULL;
307 if (offset)
308 *offset = tab->array[idx]->u.index;
309 return tab->array[idx]->root.string;
310 }
311
312 bool
313 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
314 {
315 bfd_size_type off = 1;
316 size_t i;
317
318 if (bfd_bwrite ("", 1, abfd) != 1)
319 return false;
320
321 for (i = 1; i < tab->size; ++i)
322 {
323 register const char *str;
324 register unsigned int len;
325
326 BFD_ASSERT (tab->array[i]->refcount == 0);
327 len = tab->array[i]->len;
328 if ((int) len < 0)
329 continue;
330
331 str = tab->array[i]->root.string;
332 if (bfd_bwrite (str, len, abfd) != len)
333 return false;
334
335 off += len;
336 }
337
338 BFD_ASSERT (off == tab->sec_size);
339 return true;
340 }
341
342 /* Compare two elf_strtab_hash_entry structures. Called via qsort.
343 Won't ever return zero as all entries differ, so there is no issue
344 with qsort stability here. */
345
346 static int
347 strrevcmp (const void *a, const void *b)
348 {
349 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
350 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
351 unsigned int lenA = A->len;
352 unsigned int lenB = B->len;
353 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
354 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
355 int l = lenA < lenB ? lenA : lenB;
356
357 while (l)
358 {
359 if (*s != *t)
360 return (int) *s - (int) *t;
361 s--;
362 t--;
363 l--;
364 }
365 return lenA - lenB;
366 }
367
368 static inline int
369 is_suffix (const struct elf_strtab_hash_entry *A,
370 const struct elf_strtab_hash_entry *B)
371 {
372 if (A->len <= B->len)
373 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
374 not to be equal by the hash table. */
375 return 0;
376
377 return memcmp (A->root.string + (A->len - B->len),
378 B->root.string, B->len - 1) == 0;
379 }
380
381 /* This function assigns final string table offsets for used strings,
382 merging strings matching suffixes of longer strings if possible. */
383
384 void
385 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
386 {
387 struct elf_strtab_hash_entry **array, **a, *e;
388 bfd_size_type amt, sec_size;
389 size_t size, i;
390
391 /* Sort the strings by suffix and length. */
392 amt = tab->size;
393 amt *= sizeof (struct elf_strtab_hash_entry *);
394 array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
395 if (array == NULL)
396 goto alloc_failure;
397
398 for (i = 1, a = array; i < tab->size; ++i)
399 {
400 e = tab->array[i];
401 if (e->refcount)
402 {
403 *a++ = e;
404 /* Adjust the length to not include the zero terminator. */
405 e->len -= 1;
406 }
407 else
408 e->len = 0;
409 }
410
411 size = a - array;
412 if (size != 0)
413 {
414 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
415
416 /* Loop over the sorted array and merge suffixes. Start from the
417 end because we want eg.
418
419 s1 -> "d"
420 s2 -> "bcd"
421 s3 -> "abcd"
422
423 to end up as
424
425 s3 -> "abcd"
426 s2 _____^
427 s1 _______^
428
429 ie. we don't want s1 pointing into the old s2. */
430 e = *--a;
431 e->len += 1;
432 while (--a >= array)
433 {
434 struct elf_strtab_hash_entry *cmp = *a;
435
436 cmp->len += 1;
437 if (is_suffix (e, cmp))
438 {
439 cmp->u.suffix = e;
440 cmp->len = -cmp->len;
441 }
442 else
443 e = cmp;
444 }
445 }
446
447 alloc_failure:
448 free (array);
449
450 /* Assign positions to the strings we want to keep. */
451 sec_size = 1;
452 for (i = 1; i < tab->size; ++i)
453 {
454 e = tab->array[i];
455 if (e->refcount && e->len > 0)
456 {
457 e->u.index = sec_size;
458 sec_size += e->len;
459 }
460 }
461
462 tab->sec_size = sec_size;
463
464 /* Adjust the rest. */
465 for (i = 1; i < tab->size; ++i)
466 {
467 e = tab->array[i];
468 if (e->refcount && e->len < 0)
469 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
470 }
471 }