1 /* ELF strtab with GC and suffix merging support.
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Written by Jakub Jelinek <jakub@redhat.com>.
5 This file is part of BFD, the Binary File Descriptor library.
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 3 of the License, or
10 (at your option) any later version.
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.
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., 51 Franklin Street - Fifth Floor, Boston,
20 MA 02110-1301, USA. */
27 #include "libiberty.h"
29 /* An entry in the strtab hash table. */
31 struct elf_strtab_hash_entry
33 struct bfd_hash_entry root
;
34 /* Length of this entry. This includes the zero terminator. */
36 unsigned int refcount
;
38 /* Index within the merged section. */
40 /* Entry this is a suffix of (if len < 0). */
41 struct elf_strtab_hash_entry
*suffix
;
45 /* The strtab hash table. */
47 struct elf_strtab_hash
49 struct bfd_hash_table table
;
50 /* Next available index. */
52 /* Number of array entries 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
;
60 /* Routine to create an entry in a section merge hashtab. */
62 static struct bfd_hash_entry
*
63 elf_strtab_hash_newfunc (struct bfd_hash_entry
*entry
,
64 struct bfd_hash_table
*table
,
67 /* Allocate the structure if it has not already been allocated by a
70 entry
= (struct bfd_hash_entry
*)
71 bfd_hash_allocate (table
, sizeof (struct elf_strtab_hash_entry
));
75 /* Call the allocation method of the superclass. */
76 entry
= bfd_hash_newfunc (entry
, table
, string
);
80 /* Initialize the local fields. */
81 struct elf_strtab_hash_entry
*ret
;
83 ret
= (struct elf_strtab_hash_entry
*) entry
;
92 /* Create a new hash table. */
94 struct elf_strtab_hash
*
95 _bfd_elf_strtab_init (void)
97 struct elf_strtab_hash
*table
;
98 bfd_size_type amt
= sizeof (struct elf_strtab_hash
);
100 table
= (struct elf_strtab_hash
*) bfd_malloc (amt
);
104 if (!bfd_hash_table_init (&table
->table
, elf_strtab_hash_newfunc
,
105 sizeof (struct elf_strtab_hash_entry
)))
114 amt
= sizeof (struct elf_strtab_hasn_entry
*);
115 table
->array
= ((struct elf_strtab_hash_entry
**)
116 bfd_malloc (table
->alloced
* amt
));
117 if (table
->array
== NULL
)
123 table
->array
[0] = NULL
;
131 _bfd_elf_strtab_free (struct elf_strtab_hash
*tab
)
133 bfd_hash_table_free (&tab
->table
);
138 /* Get the index of an entity in a hash table, adding it if it is not
142 _bfd_elf_strtab_add (struct elf_strtab_hash
*tab
,
146 register struct elf_strtab_hash_entry
*entry
;
148 /* We handle this specially, since we don't want to do refcounting
153 BFD_ASSERT (tab
->sec_size
== 0);
154 entry
= (struct elf_strtab_hash_entry
*)
155 bfd_hash_lookup (&tab
->table
, str
, TRUE
, copy
);
163 entry
->len
= strlen (str
) + 1;
164 /* 2G strings lose. */
165 BFD_ASSERT (entry
->len
> 0);
166 if (tab
->size
== tab
->alloced
)
168 bfd_size_type amt
= sizeof (struct elf_strtab_hash_entry
*);
170 tab
->array
= (struct elf_strtab_hash_entry
**)
171 bfd_realloc_or_free (tab
->array
, tab
->alloced
* amt
);
172 if (tab
->array
== NULL
)
176 entry
->u
.index
= tab
->size
++;
177 tab
->array
[entry
->u
.index
] = entry
;
179 return entry
->u
.index
;
183 _bfd_elf_strtab_addref (struct elf_strtab_hash
*tab
, size_t idx
)
185 if (idx
== 0 || idx
== (size_t) -1)
187 BFD_ASSERT (tab
->sec_size
== 0);
188 BFD_ASSERT (idx
< tab
->size
);
189 ++tab
->array
[idx
]->refcount
;
193 _bfd_elf_strtab_delref (struct elf_strtab_hash
*tab
, size_t idx
)
195 if (idx
== 0 || idx
== (size_t) -1)
197 BFD_ASSERT (tab
->sec_size
== 0);
198 BFD_ASSERT (idx
< tab
->size
);
199 BFD_ASSERT (tab
->array
[idx
]->refcount
> 0);
200 --tab
->array
[idx
]->refcount
;
204 _bfd_elf_strtab_refcount (struct elf_strtab_hash
*tab
, size_t idx
)
206 return tab
->array
[idx
]->refcount
;
210 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash
*tab
)
214 for (idx
= 1; idx
< tab
->size
; idx
++)
215 tab
->array
[idx
]->refcount
= 0;
218 /* Save strtab refcounts prior to adding --as-needed library. */
223 unsigned int refcount
[1];
227 _bfd_elf_strtab_save (struct elf_strtab_hash
*tab
)
229 struct strtab_save
*save
;
232 size
= sizeof (*save
) + (tab
->size
- 1) * sizeof (save
->refcount
[0]);
233 save
= bfd_malloc (size
);
237 save
->size
= tab
->size
;
238 for (idx
= 1; idx
< tab
->size
; idx
++)
239 save
->refcount
[idx
] = tab
->array
[idx
]->refcount
;
243 /* Restore strtab refcounts on finding --as-needed library not needed. */
246 _bfd_elf_strtab_restore (struct elf_strtab_hash
*tab
, void *buf
)
248 size_t idx
, curr_size
= tab
->size
;
249 struct strtab_save
*save
= (struct strtab_save
*) buf
;
251 BFD_ASSERT (tab
->sec_size
== 0);
252 BFD_ASSERT (save
->size
<= curr_size
);
253 tab
->size
= save
->size
;
254 for (idx
= 1; idx
< save
->size
; ++idx
)
255 tab
->array
[idx
]->refcount
= save
->refcount
[idx
];
257 for (; idx
< curr_size
; ++idx
)
259 /* We don't remove entries from the hash table, just set their
260 REFCOUNT to zero. Setting LEN zero will result in the size
261 growing if the entry is added again. See _bfd_elf_strtab_add. */
262 tab
->array
[idx
]->refcount
= 0;
263 tab
->array
[idx
]->len
= 0;
268 _bfd_elf_strtab_size (struct elf_strtab_hash
*tab
)
270 return tab
->sec_size
? tab
->sec_size
: tab
->size
;
274 _bfd_elf_strtab_offset (struct elf_strtab_hash
*tab
, size_t idx
)
276 struct elf_strtab_hash_entry
*entry
;
280 BFD_ASSERT (idx
< tab
->size
);
281 BFD_ASSERT (tab
->sec_size
);
282 entry
= tab
->array
[idx
];
283 BFD_ASSERT (entry
->refcount
> 0);
285 return tab
->array
[idx
]->u
.index
;
289 _bfd_elf_strtab_emit (register bfd
*abfd
, struct elf_strtab_hash
*tab
)
291 bfd_size_type off
= 1;
294 if (bfd_bwrite ("", 1, abfd
) != 1)
297 for (i
= 1; i
< tab
->size
; ++i
)
299 register const char *str
;
300 register unsigned int len
;
302 BFD_ASSERT (tab
->array
[i
]->refcount
== 0);
303 len
= tab
->array
[i
]->len
;
307 str
= tab
->array
[i
]->root
.string
;
308 if (bfd_bwrite (str
, len
, abfd
) != len
)
314 BFD_ASSERT (off
== tab
->sec_size
);
318 /* Compare two elf_strtab_hash_entry structures. Called via qsort. */
321 strrevcmp (const void *a
, const void *b
)
323 struct elf_strtab_hash_entry
*A
= *(struct elf_strtab_hash_entry
**) a
;
324 struct elf_strtab_hash_entry
*B
= *(struct elf_strtab_hash_entry
**) b
;
325 unsigned int lenA
= A
->len
;
326 unsigned int lenB
= B
->len
;
327 const unsigned char *s
= (const unsigned char *) A
->root
.string
+ lenA
- 1;
328 const unsigned char *t
= (const unsigned char *) B
->root
.string
+ lenB
- 1;
329 int l
= lenA
< lenB
? lenA
: lenB
;
334 return (int) *s
- (int) *t
;
343 is_suffix (const struct elf_strtab_hash_entry
*A
,
344 const struct elf_strtab_hash_entry
*B
)
346 if (A
->len
<= B
->len
)
347 /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
348 not to be equal by the hash table. */
351 return memcmp (A
->root
.string
+ (A
->len
- B
->len
),
352 B
->root
.string
, B
->len
- 1) == 0;
355 /* This function assigns final string table offsets for used strings,
356 merging strings matching suffixes of longer strings if possible. */
359 _bfd_elf_strtab_finalize (struct elf_strtab_hash
*tab
)
361 struct elf_strtab_hash_entry
**array
, **a
, *e
;
362 bfd_size_type amt
, sec_size
;
365 /* Sort the strings by suffix and length. */
367 amt
*= sizeof (struct elf_strtab_hash_entry
*);
368 array
= (struct elf_strtab_hash_entry
**) bfd_malloc (amt
);
372 for (i
= 1, a
= array
; i
< tab
->size
; ++i
)
378 /* Adjust the length to not include the zero terminator. */
388 qsort (array
, size
, sizeof (struct elf_strtab_hash_entry
*), strrevcmp
);
390 /* Loop over the sorted array and merge suffixes. Start from the
391 end because we want eg.
403 ie. we don't want s1 pointing into the old s2. */
408 struct elf_strtab_hash_entry
*cmp
= *a
;
411 if (is_suffix (e
, cmp
))
414 cmp
->len
= -cmp
->len
;
425 /* Assign positions to the strings we want to keep. */
427 for (i
= 1; i
< tab
->size
; ++i
)
430 if (e
->refcount
&& e
->len
> 0)
432 e
->u
.index
= sec_size
;
437 tab
->sec_size
= sec_size
;
439 /* Adjust the rest. */
440 for (i
= 1; i
< tab
->size
; ++i
)
443 if (e
->refcount
&& e
->len
< 0)
444 e
->u
.index
= e
->u
.suffix
->u
.index
+ (e
->u
.suffix
->len
+ e
->len
);
This page took 0.039286 seconds and 4 git commands to generate.