1 /* ELF strtab with GC and suffix merging support.
2 Copyright 2001, 2002, 2003, 2005, 2006, 2007
3 Free Software Foundation, Inc.
4 Written by Jakub Jelinek <jakub@redhat.com>.
5
6 This file is part of BFD, the Binary File Descriptor library.
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 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 bfd_size_type size;
52 /* Number of array entries alloced. */
53 bfd_size_type 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 *
elf_strtab_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string)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 = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
71 if (entry == NULL)
72 return NULL;
73
74 /* Call the allocation method of the superclass. */
75 entry = bfd_hash_newfunc (entry, table, string);
76
77 if (entry)
78 {
79 /* Initialize the local fields. */
80 struct elf_strtab_hash_entry *ret;
81
82 ret = (struct elf_strtab_hash_entry *) entry;
83 ret->u.index = -1;
84 ret->refcount = 0;
85 ret->len = 0;
86 }
87
88 return entry;
89 }
90
91 /* Create a new hash table. */
92
93 struct elf_strtab_hash *
_bfd_elf_strtab_init(void)94 _bfd_elf_strtab_init (void)
95 {
96 struct elf_strtab_hash *table;
97 bfd_size_type amt = sizeof (struct elf_strtab_hash);
98
99 table = bfd_malloc (amt);
100 if (table == NULL)
101 return NULL;
102
103 if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
104 sizeof (struct elf_strtab_hash_entry)))
105 {
106 free (table);
107 return NULL;
108 }
109
110 table->sec_size = 0;
111 table->size = 1;
112 table->alloced = 64;
113 amt = sizeof (struct elf_strtab_hasn_entry *);
114 table->array = bfd_malloc (table->alloced * amt);
115 if (table->array == NULL)
116 {
117 free (table);
118 return NULL;
119 }
120
121 table->array[0] = NULL;
122
123 return table;
124 }
125
126 /* Free a strtab. */
127
128 void
_bfd_elf_strtab_free(struct elf_strtab_hash * tab)129 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
130 {
131 bfd_hash_table_free (&tab->table);
132 free (tab->array);
133 free (tab);
134 }
135
136 /* Get the index of an entity in a hash table, adding it if it is not
137 already present. */
138
139 bfd_size_type
_bfd_elf_strtab_add(struct elf_strtab_hash * tab,const char * str,bfd_boolean copy)140 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
141 const char *str,
142 bfd_boolean copy)
143 {
144 register struct elf_strtab_hash_entry *entry;
145
146 /* We handle this specially, since we don't want to do refcounting
147 on it. */
148 if (*str == '\0')
149 return 0;
150
151 BFD_ASSERT (tab->sec_size == 0);
152 entry = (struct elf_strtab_hash_entry *)
153 bfd_hash_lookup (&tab->table, str, TRUE, copy);
154
155 if (entry == NULL)
156 return (bfd_size_type) -1;
157
158 entry->refcount++;
159 if (entry->len == 0)
160 {
161 entry->len = strlen (str) + 1;
162 /* 2G strings lose. */
163 BFD_ASSERT (entry->len > 0);
164 if (tab->size == tab->alloced)
165 {
166 bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
167 tab->alloced *= 2;
168 tab->array = bfd_realloc (tab->array, tab->alloced * amt);
169 if (tab->array == NULL)
170 return (bfd_size_type) -1;
171 }
172
173 entry->u.index = tab->size++;
174 tab->array[entry->u.index] = entry;
175 }
176 return entry->u.index;
177 }
178
179 void
_bfd_elf_strtab_addref(struct elf_strtab_hash * tab,bfd_size_type idx)180 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
181 {
182 if (idx == 0 || idx == (bfd_size_type) -1)
183 return;
184 BFD_ASSERT (tab->sec_size == 0);
185 BFD_ASSERT (idx < tab->size);
186 ++tab->array[idx]->refcount;
187 }
188
189 void
_bfd_elf_strtab_delref(struct elf_strtab_hash * tab,bfd_size_type idx)190 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
191 {
192 if (idx == 0 || idx == (bfd_size_type) -1)
193 return;
194 BFD_ASSERT (tab->sec_size == 0);
195 BFD_ASSERT (idx < tab->size);
196 BFD_ASSERT (tab->array[idx]->refcount > 0);
197 --tab->array[idx]->refcount;
198 }
199
200 void
_bfd_elf_strtab_clear_all_refs(struct elf_strtab_hash * tab)201 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
202 {
203 bfd_size_type idx;
204
205 for (idx = 1; idx < tab->size; ++idx)
206 tab->array[idx]->refcount = 0;
207 }
208
209 bfd_size_type
_bfd_elf_strtab_size(struct elf_strtab_hash * tab)210 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
211 {
212 return tab->sec_size ? tab->sec_size : tab->size;
213 }
214
215 bfd_size_type
_bfd_elf_strtab_offset(struct elf_strtab_hash * tab,bfd_size_type idx)216 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
217 {
218 struct elf_strtab_hash_entry *entry;
219
220 if (idx == 0)
221 return 0;
222 BFD_ASSERT (idx < tab->size);
223 BFD_ASSERT (tab->sec_size);
224 entry = tab->array[idx];
225 BFD_ASSERT (entry->refcount > 0);
226 entry->refcount--;
227 return tab->array[idx]->u.index;
228 }
229
230 bfd_boolean
_bfd_elf_strtab_emit(register bfd * abfd,struct elf_strtab_hash * tab)231 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
232 {
233 bfd_size_type off = 1, i;
234
235 if (bfd_bwrite ("", 1, abfd) != 1)
236 return FALSE;
237
238 for (i = 1; i < tab->size; ++i)
239 {
240 register const char *str;
241 register unsigned int len;
242
243 BFD_ASSERT (tab->array[i]->refcount == 0);
244 len = tab->array[i]->len;
245 if ((int) len < 0)
246 continue;
247
248 str = tab->array[i]->root.string;
249 if (bfd_bwrite (str, len, abfd) != len)
250 return FALSE;
251
252 off += len;
253 }
254
255 BFD_ASSERT (off == tab->sec_size);
256 return TRUE;
257 }
258
259 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */
260
261 static int
strrevcmp(const void * a,const void * b)262 strrevcmp (const void *a, const void *b)
263 {
264 struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
265 struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
266 unsigned int lenA = A->len;
267 unsigned int lenB = B->len;
268 const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
269 const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
270 int l = lenA < lenB ? lenA : lenB;
271
272 while (l)
273 {
274 if (*s != *t)
275 return (int) *s - (int) *t;
276 s--;
277 t--;
278 l--;
279 }
280 return lenA - lenB;
281 }
282
283 static inline int
is_suffix(const struct elf_strtab_hash_entry * A,const struct elf_strtab_hash_entry * B)284 is_suffix (const struct elf_strtab_hash_entry *A,
285 const struct elf_strtab_hash_entry *B)
286 {
287 if (A->len <= B->len)
288 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
289 not to be equal by the hash table. */
290 return 0;
291
292 return memcmp (A->root.string + (A->len - B->len),
293 B->root.string, B->len - 1) == 0;
294 }
295
296 /* This function assigns final string table offsets for used strings,
297 merging strings matching suffixes of longer strings if possible. */
298
299 void
_bfd_elf_strtab_finalize(struct elf_strtab_hash * tab)300 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
301 {
302 struct elf_strtab_hash_entry **array, **a, *e;
303 bfd_size_type size, amt;
304
305 /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
306 a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
307 Besides, indexing with a long long wouldn't give anything but extra
308 cycles. */
309 size_t i;
310
311 /* Sort the strings by suffix and length. */
312 amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
313 array = bfd_malloc (amt);
314 if (array == NULL)
315 goto alloc_failure;
316
317 for (i = 1, a = array; i < tab->size; ++i)
318 {
319 e = tab->array[i];
320 if (e->refcount)
321 {
322 *a++ = e;
323 /* Adjust the length to not include the zero terminator. */
324 e->len -= 1;
325 }
326 else
327 e->len = 0;
328 }
329
330 size = a - array;
331 if (size != 0)
332 {
333 qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
334
335 /* Loop over the sorted array and merge suffixes. Start from the
336 end because we want eg.
337
338 s1 -> "d"
339 s2 -> "bcd"
340 s3 -> "abcd"
341
342 to end up as
343
344 s3 -> "abcd"
345 s2 _____^
346 s1 _______^
347
348 ie. we don't want s1 pointing into the old s2. */
349 e = *--a;
350 e->len += 1;
351 while (--a >= array)
352 {
353 struct elf_strtab_hash_entry *cmp = *a;
354
355 cmp->len += 1;
356 if (is_suffix (e, cmp))
357 {
358 cmp->u.suffix = e;
359 cmp->len = -cmp->len;
360 }
361 else
362 e = cmp;
363 }
364 }
365
366 alloc_failure:
367 if (array)
368 free (array);
369
370 /* Assign positions to the strings we want to keep. */
371 size = 1;
372 for (i = 1; i < tab->size; ++i)
373 {
374 e = tab->array[i];
375 if (e->refcount && e->len > 0)
376 {
377 e->u.index = size;
378 size += e->len;
379 }
380 }
381
382 tab->sec_size = size;
383
384 /* Adjust the rest. */
385 for (i = 1; i < tab->size; ++i)
386 {
387 e = tab->array[i];
388 if (e->refcount && e->len < 0)
389 e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
390 }
391 }
392