Commit | Line | Data |
---|---|---|
2b0f7ef9 | 1 | /* ELF strtab with GC and suffix merging support. |
7217313c | 2 | Copyright 2001, 2002 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 | |
9 | the Free Software Foundation; either version 2 of the License, or | |
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 | |
19 | Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ | |
2b0f7ef9 JJ |
20 | |
21 | #include "bfd.h" | |
22 | #include "sysdep.h" | |
23 | #include "libbfd.h" | |
24 | #include "elf-bfd.h" | |
25 | #include "hashtab.h" | |
7217313c | 26 | #include "libiberty.h" |
2b0f7ef9 JJ |
27 | |
28 | /* An entry in the strtab hash table. */ | |
29 | ||
30 | struct elf_strtab_hash_entry | |
31 | { | |
32 | struct bfd_hash_entry root; | |
33 | /* Length of this entry. */ | |
34 | unsigned int len; | |
35 | unsigned int refcount; | |
36 | union { | |
37 | /* Index within the merged section. */ | |
38 | bfd_size_type index; | |
39 | /* Entry this is a suffix of (if len is 0). */ | |
40 | struct elf_strtab_hash_entry *suffix; | |
53c3f2be | 41 | struct elf_strtab_hash_entry *next; |
2b0f7ef9 JJ |
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 | ||
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 AM |
69 | if (entry == NULL) |
70 | entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); | |
71 | if (entry == NULL) | |
2b0f7ef9 JJ |
72 | return NULL; |
73 | ||
74 | /* Call the allocation method of the superclass. */ | |
c39a58e6 | 75 | entry = bfd_hash_newfunc (entry, table, string); |
2b0f7ef9 | 76 | |
c39a58e6 | 77 | if (entry) |
2b0f7ef9 JJ |
78 | { |
79 | /* Initialize the local fields. */ | |
c39a58e6 AM |
80 | struct elf_strtab_hash_entry *ret; |
81 | ||
82 | ret = (struct elf_strtab_hash_entry *) entry; | |
2b0f7ef9 JJ |
83 | ret->u.index = -1; |
84 | ret->refcount = 0; | |
85 | ret->len = 0; | |
86 | } | |
87 | ||
c39a58e6 | 88 | return entry; |
2b0f7ef9 JJ |
89 | } |
90 | ||
91 | /* Create a new hash table. */ | |
92 | ||
93 | struct elf_strtab_hash * | |
c39a58e6 | 94 | _bfd_elf_strtab_init (void) |
2b0f7ef9 JJ |
95 | { |
96 | struct elf_strtab_hash *table; | |
97 | bfd_size_type amt = sizeof (struct elf_strtab_hash); | |
98 | ||
c39a58e6 | 99 | table = bfd_malloc (amt); |
2b0f7ef9 JJ |
100 | if (table == NULL) |
101 | return NULL; | |
102 | ||
103 | if (! bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc)) | |
104 | { | |
105 | free (table); | |
106 | return NULL; | |
107 | } | |
108 | ||
109 | table->sec_size = 0; | |
110 | table->size = 1; | |
111 | table->alloced = 64; | |
112 | amt = sizeof (struct elf_strtab_hasn_entry *); | |
c39a58e6 | 113 | table->array = bfd_malloc (table->alloced * amt); |
2b0f7ef9 JJ |
114 | if (table->array == NULL) |
115 | { | |
116 | free (table); | |
117 | return NULL; | |
118 | } | |
119 | ||
120 | table->array[0] = NULL; | |
121 | ||
122 | return table; | |
123 | } | |
124 | ||
125 | /* Free a strtab. */ | |
126 | ||
127 | void | |
c39a58e6 | 128 | _bfd_elf_strtab_free (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
129 | { |
130 | bfd_hash_table_free (&tab->table); | |
131 | free (tab->array); | |
132 | free (tab); | |
133 | } | |
134 | ||
135 | /* Get the index of an entity in a hash table, adding it if it is not | |
136 | already present. */ | |
137 | ||
138 | bfd_size_type | |
c39a58e6 AM |
139 | _bfd_elf_strtab_add (struct elf_strtab_hash *tab, |
140 | const char *str, | |
141 | bfd_boolean copy) | |
2b0f7ef9 JJ |
142 | { |
143 | register struct elf_strtab_hash_entry *entry; | |
144 | ||
145 | /* We handle this specially, since we don't want to do refcounting | |
146 | on it. */ | |
147 | if (*str == '\0') | |
148 | return 0; | |
149 | ||
150 | BFD_ASSERT (tab->sec_size == 0); | |
151 | entry = (struct elf_strtab_hash_entry *) | |
b34976b6 | 152 | bfd_hash_lookup (&tab->table, str, TRUE, copy); |
2b0f7ef9 JJ |
153 | |
154 | if (entry == NULL) | |
155 | return (bfd_size_type) -1; | |
156 | ||
157 | entry->refcount++; | |
158 | if (entry->len == 0) | |
159 | { | |
160 | entry->len = strlen (str) + 1; | |
161 | if (tab->size == tab->alloced) | |
162 | { | |
163 | bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); | |
164 | tab->alloced *= 2; | |
c39a58e6 | 165 | tab->array = bfd_realloc (tab->array, tab->alloced * amt); |
2b0f7ef9 JJ |
166 | if (tab->array == NULL) |
167 | return (bfd_size_type) -1; | |
168 | } | |
169 | ||
170 | entry->u.index = tab->size++; | |
171 | tab->array[entry->u.index] = entry; | |
172 | } | |
173 | return entry->u.index; | |
174 | } | |
175 | ||
176 | void | |
c39a58e6 | 177 | _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
178 | { |
179 | if (idx == 0 || idx == (bfd_size_type) -1) | |
180 | return; | |
181 | BFD_ASSERT (tab->sec_size == 0); | |
182 | BFD_ASSERT (idx < tab->size); | |
183 | ++tab->array[idx]->refcount; | |
184 | } | |
185 | ||
186 | void | |
c39a58e6 | 187 | _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
188 | { |
189 | if (idx == 0 || idx == (bfd_size_type) -1) | |
190 | return; | |
191 | BFD_ASSERT (tab->sec_size == 0); | |
192 | BFD_ASSERT (idx < tab->size); | |
193 | BFD_ASSERT (tab->array[idx]->refcount > 0); | |
194 | --tab->array[idx]->refcount; | |
195 | } | |
196 | ||
197 | void | |
c39a58e6 | 198 | _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
199 | { |
200 | bfd_size_type idx; | |
201 | ||
202 | for (idx = 1; idx < tab->size; ++idx) | |
203 | tab->array[idx]->refcount = 0; | |
204 | } | |
205 | ||
206 | bfd_size_type | |
c39a58e6 | 207 | _bfd_elf_strtab_size (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
208 | { |
209 | return tab->sec_size ? tab->sec_size : tab->size; | |
210 | } | |
211 | ||
212 | bfd_size_type | |
c39a58e6 | 213 | _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
214 | { |
215 | struct elf_strtab_hash_entry *entry; | |
216 | ||
217 | if (idx == 0) | |
218 | return 0; | |
219 | BFD_ASSERT (idx < tab->size); | |
220 | BFD_ASSERT (tab->sec_size); | |
221 | entry = tab->array[idx]; | |
222 | BFD_ASSERT (entry->refcount > 0); | |
223 | entry->refcount--; | |
224 | return tab->array[idx]->u.index; | |
225 | } | |
226 | ||
b34976b6 | 227 | bfd_boolean |
c39a58e6 | 228 | _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
229 | { |
230 | bfd_size_type off = 1, i; | |
231 | ||
232 | if (bfd_bwrite ("", 1, abfd) != 1) | |
b34976b6 | 233 | return FALSE; |
2b0f7ef9 JJ |
234 | |
235 | for (i = 1; i < tab->size; ++i) | |
236 | { | |
237 | register const char *str; | |
238 | register size_t len; | |
239 | ||
240 | str = tab->array[i]->root.string; | |
241 | len = tab->array[i]->len; | |
242 | BFD_ASSERT (tab->array[i]->refcount == 0); | |
243 | if (len == 0) | |
244 | continue; | |
245 | ||
c39a58e6 | 246 | if (bfd_bwrite (str, len, abfd) != len) |
b34976b6 | 247 | return FALSE; |
2b0f7ef9 JJ |
248 | |
249 | off += len; | |
250 | } | |
251 | ||
252 | BFD_ASSERT (off == tab->sec_size); | |
b34976b6 | 253 | return TRUE; |
2b0f7ef9 JJ |
254 | } |
255 | ||
256 | /* Compare two elf_strtab_hash_entry structures. This is called via qsort. */ | |
257 | ||
258 | static int | |
c39a58e6 | 259 | cmplengthentry (const void *a, const void *b) |
2b0f7ef9 | 260 | { |
c39a58e6 AM |
261 | struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; |
262 | struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; | |
2b0f7ef9 JJ |
263 | |
264 | if (A->len < B->len) | |
265 | return 1; | |
266 | else if (A->len > B->len) | |
267 | return -1; | |
268 | ||
269 | return memcmp (A->root.string, B->root.string, A->len); | |
270 | } | |
271 | ||
272 | static int | |
c39a58e6 | 273 | last4_eq (const void *a, const void *b) |
2b0f7ef9 | 274 | { |
c39a58e6 AM |
275 | const struct elf_strtab_hash_entry *A = a; |
276 | const struct elf_strtab_hash_entry *B = b; | |
2b0f7ef9 JJ |
277 | |
278 | if (memcmp (A->root.string + A->len - 5, B->root.string + B->len - 5, 4) | |
279 | != 0) | |
280 | /* This was a hashtable collision. */ | |
281 | return 0; | |
282 | ||
283 | if (A->len <= B->len) | |
284 | /* B cannot be a suffix of A unless A is equal to B, which is guaranteed | |
285 | not to be equal by the hash table. */ | |
286 | return 0; | |
287 | ||
288 | return memcmp (A->root.string + (A->len - B->len), | |
289 | B->root.string, B->len - 5) == 0; | |
290 | } | |
291 | ||
2b0f7ef9 JJ |
292 | /* This function assigns final string table offsets for used strings, |
293 | merging strings matching suffixes of longer strings if possible. */ | |
294 | ||
295 | void | |
c39a58e6 | 296 | _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
297 | { |
298 | struct elf_strtab_hash_entry **array, **a, **end, *e; | |
53c3f2be | 299 | htab_t last4tab = NULL; |
b959dc73 | 300 | bfd_size_type size, amt; |
53c3f2be | 301 | struct elf_strtab_hash_entry *last[256], **last_ptr[256]; |
b959dc73 HPN |
302 | |
303 | /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is | |
304 | a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd. | |
305 | Besides, indexing with a long long wouldn't give anything but extra | |
306 | cycles. */ | |
307 | size_t i; | |
2b0f7ef9 JJ |
308 | |
309 | /* Now sort the strings by length, longest first. */ | |
310 | array = NULL; | |
311 | amt = tab->size * sizeof (struct elf_strtab_hash_entry *); | |
c39a58e6 | 312 | array = bfd_malloc (amt); |
2b0f7ef9 JJ |
313 | if (array == NULL) |
314 | goto alloc_failure; | |
315 | ||
53c3f2be JJ |
316 | memset (last, 0, sizeof (last)); |
317 | for (i = 0; i < 256; ++i) | |
318 | last_ptr[i] = &last[i]; | |
2b0f7ef9 JJ |
319 | for (i = 1, a = array; i < tab->size; ++i) |
320 | if (tab->array[i]->refcount) | |
321 | *a++ = tab->array[i]; | |
322 | else | |
323 | tab->array[i]->len = 0; | |
324 | ||
325 | size = a - array; | |
326 | ||
327 | qsort (array, size, sizeof (struct elf_strtab_hash_entry *), cmplengthentry); | |
328 | ||
ebe3e2d1 | 329 | last4tab = htab_create_alloc (size * 4, NULL, last4_eq, NULL, calloc, free); |
53c3f2be | 330 | if (last4tab == NULL) |
2b0f7ef9 JJ |
331 | goto alloc_failure; |
332 | ||
333 | /* Now insert the strings into hash tables (strings with last 4 characters | |
334 | and strings with last character equal), look for longer strings which | |
335 | we're suffix of. */ | |
336 | for (a = array, end = array + size; a < end; a++) | |
337 | { | |
338 | register hashval_t hash; | |
339 | unsigned int c; | |
b959dc73 | 340 | unsigned int j; |
2b0f7ef9 | 341 | const unsigned char *s; |
c39a58e6 | 342 | void **p; |
2b0f7ef9 JJ |
343 | |
344 | e = *a; | |
345 | if (e->len > 4) | |
346 | { | |
347 | s = e->root.string + e->len - 1; | |
348 | hash = 0; | |
b959dc73 | 349 | for (j = 0; j < 4; j++) |
2b0f7ef9 JJ |
350 | { |
351 | c = *--s; | |
352 | hash += c + (c << 17); | |
353 | hash ^= hash >> 2; | |
354 | } | |
355 | p = htab_find_slot_with_hash (last4tab, e, hash, INSERT); | |
356 | if (p == NULL) | |
357 | goto alloc_failure; | |
358 | if (*p) | |
359 | { | |
360 | struct elf_strtab_hash_entry *ent; | |
361 | ||
c39a58e6 | 362 | ent = *p; |
2b0f7ef9 JJ |
363 | e->u.suffix = ent; |
364 | e->len = 0; | |
365 | continue; | |
366 | } | |
367 | else | |
c39a58e6 | 368 | *p = e; |
2b0f7ef9 | 369 | } |
53c3f2be | 370 | else |
2b0f7ef9 | 371 | { |
53c3f2be | 372 | struct elf_strtab_hash_entry *tem; |
2b0f7ef9 | 373 | |
53c3f2be JJ |
374 | c = e->root.string[e->len - 2] & 0xff; |
375 | ||
376 | for (tem = last[c]; tem; tem = tem->u.next) | |
377 | if (tem->len > e->len | |
378 | && memcmp (tem->root.string + (tem->len - e->len), | |
379 | e->root.string, e->len - 1) == 0) | |
380 | break; | |
381 | if (tem) | |
382 | { | |
383 | e->u.suffix = tem; | |
384 | e->len = 0; | |
385 | continue; | |
386 | } | |
2b0f7ef9 | 387 | } |
53c3f2be JJ |
388 | |
389 | c = e->root.string[e->len - 2] & 0xff; | |
390 | /* Put longest strings first. */ | |
391 | *last_ptr[c] = e; | |
392 | last_ptr[c] = &e->u.next; | |
393 | e->u.next = NULL; | |
2b0f7ef9 JJ |
394 | } |
395 | ||
396 | alloc_failure: | |
397 | if (array) | |
398 | free (array); | |
2b0f7ef9 JJ |
399 | if (last4tab) |
400 | htab_delete (last4tab); | |
401 | ||
402 | /* Now assign positions to the strings we want to keep. */ | |
403 | size = 1; | |
404 | for (i = 1; i < tab->size; ++i) | |
405 | { | |
406 | e = tab->array[i]; | |
407 | if (e->refcount && e->len) | |
408 | { | |
409 | e->u.index = size; | |
410 | size += e->len; | |
411 | } | |
412 | } | |
413 | ||
414 | tab->sec_size = size; | |
415 | ||
416 | /* And now adjust the rest. */ | |
417 | for (i = 1; i < tab->size; ++i) | |
418 | { | |
419 | e = tab->array[i]; | |
420 | if (e->refcount && ! e->len) | |
421 | e->u.index = e->u.suffix->u.index | |
422 | + (e->u.suffix->len - strlen (e->root.string) - 1); | |
423 | } | |
424 | } |