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