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