Commit | Line | Data |
---|---|---|
2b0f7ef9 | 1 | /* ELF strtab with GC and suffix merging support. |
66eb6687 | 2 | Copyright 2001, 2002, 2003, 2005, 2006 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 | |
3e110533 | 19 | Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, 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; | |
ddb2b442 AM |
33 | /* Length of this entry. This includes the zero terminator. */ |
34 | int len; | |
2b0f7ef9 JJ |
35 | unsigned int refcount; |
36 | union { | |
37 | /* Index within the merged section. */ | |
38 | bfd_size_type index; | |
ddb2b442 | 39 | /* Entry this is a suffix of (if len < 0). */ |
2b0f7ef9 JJ |
40 | struct elf_strtab_hash_entry *suffix; |
41 | } u; | |
42 | }; | |
43 | ||
44 | /* The strtab hash table. */ | |
45 | ||
46 | struct elf_strtab_hash | |
47 | { | |
48 | struct bfd_hash_table table; | |
49 | /* Next available index. */ | |
50 | bfd_size_type size; | |
51 | /* Number of array entries alloced. */ | |
52 | bfd_size_type alloced; | |
53 | /* Final strtab size. */ | |
54 | bfd_size_type sec_size; | |
55 | /* Array of pointers to strtab entries. */ | |
56 | struct elf_strtab_hash_entry **array; | |
57 | }; | |
58 | ||
2b0f7ef9 JJ |
59 | /* Routine to create an entry in a section merge hashtab. */ |
60 | ||
61 | static struct bfd_hash_entry * | |
c39a58e6 AM |
62 | elf_strtab_hash_newfunc (struct bfd_hash_entry *entry, |
63 | struct bfd_hash_table *table, | |
64 | const char *string) | |
2b0f7ef9 | 65 | { |
2b0f7ef9 JJ |
66 | /* Allocate the structure if it has not already been allocated by a |
67 | subclass. */ | |
c39a58e6 AM |
68 | if (entry == NULL) |
69 | entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry)); | |
70 | if (entry == NULL) | |
2b0f7ef9 JJ |
71 | return NULL; |
72 | ||
73 | /* Call the allocation method of the superclass. */ | |
c39a58e6 | 74 | entry = bfd_hash_newfunc (entry, table, string); |
2b0f7ef9 | 75 | |
c39a58e6 | 76 | if (entry) |
2b0f7ef9 JJ |
77 | { |
78 | /* Initialize the local fields. */ | |
c39a58e6 AM |
79 | struct elf_strtab_hash_entry *ret; |
80 | ||
81 | ret = (struct elf_strtab_hash_entry *) entry; | |
2b0f7ef9 JJ |
82 | ret->u.index = -1; |
83 | ret->refcount = 0; | |
84 | ret->len = 0; | |
85 | } | |
86 | ||
c39a58e6 | 87 | return entry; |
2b0f7ef9 JJ |
88 | } |
89 | ||
90 | /* Create a new hash table. */ | |
91 | ||
92 | struct elf_strtab_hash * | |
c39a58e6 | 93 | _bfd_elf_strtab_init (void) |
2b0f7ef9 JJ |
94 | { |
95 | struct elf_strtab_hash *table; | |
96 | bfd_size_type amt = sizeof (struct elf_strtab_hash); | |
97 | ||
c39a58e6 | 98 | table = bfd_malloc (amt); |
2b0f7ef9 JJ |
99 | if (table == NULL) |
100 | return NULL; | |
101 | ||
66eb6687 AM |
102 | if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc, |
103 | sizeof (struct elf_strtab_hash_entry))) | |
2b0f7ef9 JJ |
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; | |
ddb2b442 AM |
161 | /* 2G strings lose. */ |
162 | BFD_ASSERT (entry->len > 0); | |
2b0f7ef9 JJ |
163 | if (tab->size == tab->alloced) |
164 | { | |
165 | bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *); | |
166 | tab->alloced *= 2; | |
c39a58e6 | 167 | tab->array = bfd_realloc (tab->array, tab->alloced * amt); |
2b0f7ef9 JJ |
168 | if (tab->array == NULL) |
169 | return (bfd_size_type) -1; | |
170 | } | |
171 | ||
172 | entry->u.index = tab->size++; | |
173 | tab->array[entry->u.index] = entry; | |
174 | } | |
175 | return entry->u.index; | |
176 | } | |
177 | ||
178 | void | |
c39a58e6 | 179 | _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
180 | { |
181 | if (idx == 0 || idx == (bfd_size_type) -1) | |
182 | return; | |
183 | BFD_ASSERT (tab->sec_size == 0); | |
184 | BFD_ASSERT (idx < tab->size); | |
185 | ++tab->array[idx]->refcount; | |
186 | } | |
187 | ||
188 | void | |
c39a58e6 | 189 | _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
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 | BFD_ASSERT (tab->array[idx]->refcount > 0); | |
196 | --tab->array[idx]->refcount; | |
197 | } | |
198 | ||
199 | void | |
c39a58e6 | 200 | _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
201 | { |
202 | bfd_size_type idx; | |
203 | ||
204 | for (idx = 1; idx < tab->size; ++idx) | |
205 | tab->array[idx]->refcount = 0; | |
206 | } | |
207 | ||
208 | bfd_size_type | |
c39a58e6 | 209 | _bfd_elf_strtab_size (struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
210 | { |
211 | return tab->sec_size ? tab->sec_size : tab->size; | |
212 | } | |
213 | ||
214 | bfd_size_type | |
c39a58e6 | 215 | _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx) |
2b0f7ef9 JJ |
216 | { |
217 | struct elf_strtab_hash_entry *entry; | |
218 | ||
219 | if (idx == 0) | |
220 | return 0; | |
221 | BFD_ASSERT (idx < tab->size); | |
222 | BFD_ASSERT (tab->sec_size); | |
223 | entry = tab->array[idx]; | |
224 | BFD_ASSERT (entry->refcount > 0); | |
225 | entry->refcount--; | |
226 | return tab->array[idx]->u.index; | |
227 | } | |
228 | ||
b34976b6 | 229 | bfd_boolean |
c39a58e6 | 230 | _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab) |
2b0f7ef9 JJ |
231 | { |
232 | bfd_size_type off = 1, i; | |
233 | ||
234 | if (bfd_bwrite ("", 1, abfd) != 1) | |
b34976b6 | 235 | return FALSE; |
2b0f7ef9 JJ |
236 | |
237 | for (i = 1; i < tab->size; ++i) | |
238 | { | |
239 | register const char *str; | |
ddb2b442 | 240 | register unsigned int len; |
2b0f7ef9 | 241 | |
2b0f7ef9 | 242 | BFD_ASSERT (tab->array[i]->refcount == 0); |
ddb2b442 AM |
243 | len = tab->array[i]->len; |
244 | if ((int) len < 0) | |
2b0f7ef9 JJ |
245 | continue; |
246 | ||
ddb2b442 | 247 | str = tab->array[i]->root.string; |
c39a58e6 | 248 | if (bfd_bwrite (str, len, abfd) != len) |
b34976b6 | 249 | return FALSE; |
2b0f7ef9 JJ |
250 | |
251 | off += len; | |
252 | } | |
253 | ||
254 | BFD_ASSERT (off == tab->sec_size); | |
b34976b6 | 255 | return TRUE; |
2b0f7ef9 JJ |
256 | } |
257 | ||
ddb2b442 | 258 | /* Compare two elf_strtab_hash_entry structures. Called via qsort. */ |
2b0f7ef9 JJ |
259 | |
260 | static int | |
ddb2b442 | 261 | strrevcmp (const void *a, const void *b) |
2b0f7ef9 | 262 | { |
c39a58e6 AM |
263 | struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a; |
264 | struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b; | |
ddb2b442 AM |
265 | unsigned int lenA = A->len; |
266 | unsigned int lenB = B->len; | |
f075ee0c AM |
267 | const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1; |
268 | const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1; | |
ddb2b442 | 269 | int l = lenA < lenB ? lenA : lenB; |
2b0f7ef9 | 270 | |
ddb2b442 AM |
271 | while (l) |
272 | { | |
273 | if (*s != *t) | |
274 | return (int) *s - (int) *t; | |
275 | s--; | |
276 | t--; | |
277 | l--; | |
278 | } | |
279 | return lenA - lenB; | |
2b0f7ef9 JJ |
280 | } |
281 | ||
ddb2b442 AM |
282 | static inline int |
283 | is_suffix (const struct elf_strtab_hash_entry *A, | |
284 | const struct elf_strtab_hash_entry *B) | |
2b0f7ef9 | 285 | { |
2b0f7ef9 JJ |
286 | if (A->len <= B->len) |
287 | /* B cannot be a suffix of A unless A is equal to B, which is guaranteed | |
288 | not to be equal by the hash table. */ | |
289 | return 0; | |
290 | ||
291 | return memcmp (A->root.string + (A->len - B->len), | |
ddb2b442 | 292 | B->root.string, B->len - 1) == 0; |
2b0f7ef9 JJ |
293 | } |
294 | ||
2b0f7ef9 JJ |
295 | /* This function assigns final string table offsets for used strings, |
296 | merging strings matching suffixes of longer strings if possible. */ | |
297 | ||
298 | void | |
c39a58e6 | 299 | _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab) |
2b0f7ef9 | 300 | { |
ddb2b442 | 301 | struct elf_strtab_hash_entry **array, **a, *e; |
b959dc73 HPN |
302 | bfd_size_type size, amt; |
303 | ||
304 | /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is | |
305 | a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd. | |
306 | Besides, indexing with a long long wouldn't give anything but extra | |
307 | cycles. */ | |
308 | size_t i; | |
2b0f7ef9 | 309 | |
ddb2b442 | 310 | /* Sort the strings by suffix and length. */ |
2b0f7ef9 | 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 | ||
316 | for (i = 1, a = array; i < tab->size; ++i) | |
ddb2b442 AM |
317 | { |
318 | e = tab->array[i]; | |
319 | if (e->refcount) | |
320 | { | |
321 | *a++ = e; | |
322 | /* Adjust the length to not include the zero terminator. */ | |
323 | e->len -= 1; | |
324 | } | |
325 | else | |
326 | e->len = 0; | |
327 | } | |
2b0f7ef9 JJ |
328 | |
329 | size = a - array; | |
ddb2b442 AM |
330 | if (size != 0) |
331 | { | |
332 | qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp); | |
2b0f7ef9 | 333 | |
ddb2b442 AM |
334 | /* Loop over the sorted array and merge suffixes. Start from the |
335 | end because we want eg. | |
2b0f7ef9 | 336 | |
ddb2b442 AM |
337 | s1 -> "d" |
338 | s2 -> "bcd" | |
339 | s3 -> "abcd" | |
2b0f7ef9 | 340 | |
ddb2b442 | 341 | to end up as |
2b0f7ef9 | 342 | |
ddb2b442 AM |
343 | s3 -> "abcd" |
344 | s2 _____^ | |
345 | s1 _______^ | |
2b0f7ef9 | 346 | |
ddb2b442 AM |
347 | ie. we don't want s1 pointing into the old s2. */ |
348 | e = *--a; | |
349 | e->len += 1; | |
350 | while (--a >= array) | |
351 | { | |
352 | struct elf_strtab_hash_entry *cmp = *a; | |
53c3f2be | 353 | |
ddb2b442 AM |
354 | cmp->len += 1; |
355 | if (is_suffix (e, cmp)) | |
53c3f2be | 356 | { |
ddb2b442 AM |
357 | cmp->u.suffix = e; |
358 | cmp->len = -cmp->len; | |
53c3f2be | 359 | } |
ddb2b442 AM |
360 | else |
361 | e = cmp; | |
2b0f7ef9 | 362 | } |
2b0f7ef9 JJ |
363 | } |
364 | ||
365 | alloc_failure: | |
366 | if (array) | |
367 | free (array); | |
2b0f7ef9 | 368 | |
ddb2b442 | 369 | /* Assign positions to the strings we want to keep. */ |
2b0f7ef9 JJ |
370 | size = 1; |
371 | for (i = 1; i < tab->size; ++i) | |
372 | { | |
373 | e = tab->array[i]; | |
ddb2b442 | 374 | if (e->refcount && e->len > 0) |
2b0f7ef9 JJ |
375 | { |
376 | e->u.index = size; | |
377 | size += e->len; | |
378 | } | |
379 | } | |
380 | ||
381 | tab->sec_size = size; | |
382 | ||
ddb2b442 | 383 | /* Adjust the rest. */ |
2b0f7ef9 JJ |
384 | for (i = 1; i < tab->size; ++i) |
385 | { | |
386 | e = tab->array[i]; | |
ddb2b442 AM |
387 | if (e->refcount && e->len < 0) |
388 | e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len); | |
2b0f7ef9 JJ |
389 | } |
390 | } |