1a1ba9ba4Schristos /* ELF strtab with GC and suffix merging support.
2*184b2d41Schristos Copyright (C) 2001-2020 Free Software Foundation, Inc.
3a1ba9ba4Schristos Written by Jakub Jelinek <jakub@redhat.com>.
4a1ba9ba4Schristos
5a1ba9ba4Schristos This file is part of BFD, the Binary File Descriptor library.
6a1ba9ba4Schristos
7a1ba9ba4Schristos This program is free software; you can redistribute it and/or modify
8a1ba9ba4Schristos it under the terms of the GNU General Public License as published by
9a1ba9ba4Schristos the Free Software Foundation; either version 3 of the License, or
10a1ba9ba4Schristos (at your option) any later version.
11a1ba9ba4Schristos
12a1ba9ba4Schristos This program is distributed in the hope that it will be useful,
13a1ba9ba4Schristos but WITHOUT ANY WARRANTY; without even the implied warranty of
14a1ba9ba4Schristos MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15a1ba9ba4Schristos GNU General Public License for more details.
16a1ba9ba4Schristos
17a1ba9ba4Schristos You should have received a copy of the GNU General Public License
18a1ba9ba4Schristos along with this program; if not, write to the Free Software
19a1ba9ba4Schristos Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
20a1ba9ba4Schristos MA 02110-1301, USA. */
21a1ba9ba4Schristos
22a1ba9ba4Schristos #include "sysdep.h"
23a1ba9ba4Schristos #include "bfd.h"
24a1ba9ba4Schristos #include "libbfd.h"
25a1ba9ba4Schristos #include "elf-bfd.h"
26a1ba9ba4Schristos #include "hashtab.h"
27a1ba9ba4Schristos #include "libiberty.h"
28a1ba9ba4Schristos
29a1ba9ba4Schristos /* An entry in the strtab hash table. */
30a1ba9ba4Schristos
31a1ba9ba4Schristos struct elf_strtab_hash_entry
32a1ba9ba4Schristos {
33a1ba9ba4Schristos struct bfd_hash_entry root;
34a1ba9ba4Schristos /* Length of this entry. This includes the zero terminator. */
35a1ba9ba4Schristos int len;
36a1ba9ba4Schristos unsigned int refcount;
37a1ba9ba4Schristos union {
38a1ba9ba4Schristos /* Index within the merged section. */
39a1ba9ba4Schristos bfd_size_type index;
40a1ba9ba4Schristos /* Entry this is a suffix of (if len < 0). */
41a1ba9ba4Schristos struct elf_strtab_hash_entry *suffix;
42a1ba9ba4Schristos } u;
43a1ba9ba4Schristos };
44a1ba9ba4Schristos
45a1ba9ba4Schristos /* The strtab hash table. */
46a1ba9ba4Schristos
47a1ba9ba4Schristos struct elf_strtab_hash
48a1ba9ba4Schristos {
49a1ba9ba4Schristos struct bfd_hash_table table;
50a1ba9ba4Schristos /* Next available index. */
51b2396a7bSchristos size_t size;
52a1ba9ba4Schristos /* Number of array entries alloced. */
53b2396a7bSchristos size_t alloced;
54a1ba9ba4Schristos /* Final strtab size. */
55a1ba9ba4Schristos bfd_size_type sec_size;
56a1ba9ba4Schristos /* Array of pointers to strtab entries. */
57a1ba9ba4Schristos struct elf_strtab_hash_entry **array;
58a1ba9ba4Schristos };
59a1ba9ba4Schristos
60a1ba9ba4Schristos /* Routine to create an entry in a section merge hashtab. */
61a1ba9ba4Schristos
62a1ba9ba4Schristos static struct bfd_hash_entry *
elf_strtab_hash_newfunc(struct bfd_hash_entry * entry,struct bfd_hash_table * table,const char * string)63a1ba9ba4Schristos elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
64a1ba9ba4Schristos struct bfd_hash_table *table,
65a1ba9ba4Schristos const char *string)
66a1ba9ba4Schristos {
67a1ba9ba4Schristos /* Allocate the structure if it has not already been allocated by a
68a1ba9ba4Schristos subclass. */
69a1ba9ba4Schristos if (entry == NULL)
70a1ba9ba4Schristos entry = (struct bfd_hash_entry *)
71a1ba9ba4Schristos bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
72a1ba9ba4Schristos if (entry == NULL)
73a1ba9ba4Schristos return NULL;
74a1ba9ba4Schristos
75a1ba9ba4Schristos /* Call the allocation method of the superclass. */
76a1ba9ba4Schristos entry = bfd_hash_newfunc (entry, table, string);
77a1ba9ba4Schristos
78a1ba9ba4Schristos if (entry)
79a1ba9ba4Schristos {
80a1ba9ba4Schristos /* Initialize the local fields. */
81a1ba9ba4Schristos struct elf_strtab_hash_entry *ret;
82a1ba9ba4Schristos
83a1ba9ba4Schristos ret = (struct elf_strtab_hash_entry *) entry;
84a1ba9ba4Schristos ret->u.index = -1;
85a1ba9ba4Schristos ret->refcount = 0;
86a1ba9ba4Schristos ret->len = 0;
87a1ba9ba4Schristos }
88a1ba9ba4Schristos
89a1ba9ba4Schristos return entry;
90a1ba9ba4Schristos }
91a1ba9ba4Schristos
92a1ba9ba4Schristos /* Create a new hash table. */
93a1ba9ba4Schristos
94a1ba9ba4Schristos struct elf_strtab_hash *
_bfd_elf_strtab_init(void)95a1ba9ba4Schristos _bfd_elf_strtab_init (void)
96a1ba9ba4Schristos {
97a1ba9ba4Schristos struct elf_strtab_hash *table;
98*184b2d41Schristos size_t amt = sizeof (struct elf_strtab_hash);
99a1ba9ba4Schristos
100a1ba9ba4Schristos table = (struct elf_strtab_hash *) bfd_malloc (amt);
101a1ba9ba4Schristos if (table == NULL)
102a1ba9ba4Schristos return NULL;
103a1ba9ba4Schristos
104a1ba9ba4Schristos if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
105a1ba9ba4Schristos sizeof (struct elf_strtab_hash_entry)))
106a1ba9ba4Schristos {
107a1ba9ba4Schristos free (table);
108a1ba9ba4Schristos return NULL;
109a1ba9ba4Schristos }
110a1ba9ba4Schristos
111a1ba9ba4Schristos table->sec_size = 0;
112a1ba9ba4Schristos table->size = 1;
113a1ba9ba4Schristos table->alloced = 64;
114a1ba9ba4Schristos amt = sizeof (struct elf_strtab_hasn_entry *);
115b2396a7bSchristos table->array = ((struct elf_strtab_hash_entry **)
116b2396a7bSchristos bfd_malloc (table->alloced * amt));
117a1ba9ba4Schristos if (table->array == NULL)
118a1ba9ba4Schristos {
119a1ba9ba4Schristos free (table);
120a1ba9ba4Schristos return NULL;
121a1ba9ba4Schristos }
122a1ba9ba4Schristos
123a1ba9ba4Schristos table->array[0] = NULL;
124a1ba9ba4Schristos
125a1ba9ba4Schristos return table;
126a1ba9ba4Schristos }
127a1ba9ba4Schristos
128a1ba9ba4Schristos /* Free a strtab. */
129a1ba9ba4Schristos
130a1ba9ba4Schristos void
_bfd_elf_strtab_free(struct elf_strtab_hash * tab)131a1ba9ba4Schristos _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
132a1ba9ba4Schristos {
133a1ba9ba4Schristos bfd_hash_table_free (&tab->table);
134a1ba9ba4Schristos free (tab->array);
135a1ba9ba4Schristos free (tab);
136a1ba9ba4Schristos }
137a1ba9ba4Schristos
138a1ba9ba4Schristos /* Get the index of an entity in a hash table, adding it if it is not
139a1ba9ba4Schristos already present. */
140a1ba9ba4Schristos
141b2396a7bSchristos size_t
_bfd_elf_strtab_add(struct elf_strtab_hash * tab,const char * str,bfd_boolean copy)142a1ba9ba4Schristos _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
143a1ba9ba4Schristos const char *str,
144a1ba9ba4Schristos bfd_boolean copy)
145a1ba9ba4Schristos {
146a1ba9ba4Schristos register struct elf_strtab_hash_entry *entry;
147a1ba9ba4Schristos
148a1ba9ba4Schristos /* We handle this specially, since we don't want to do refcounting
149a1ba9ba4Schristos on it. */
150a1ba9ba4Schristos if (*str == '\0')
151a1ba9ba4Schristos return 0;
152a1ba9ba4Schristos
153a1ba9ba4Schristos BFD_ASSERT (tab->sec_size == 0);
154a1ba9ba4Schristos entry = (struct elf_strtab_hash_entry *)
155a1ba9ba4Schristos bfd_hash_lookup (&tab->table, str, TRUE, copy);
156a1ba9ba4Schristos
157a1ba9ba4Schristos if (entry == NULL)
158b2396a7bSchristos return (size_t) -1;
159a1ba9ba4Schristos
160a1ba9ba4Schristos entry->refcount++;
161a1ba9ba4Schristos if (entry->len == 0)
162a1ba9ba4Schristos {
163a1ba9ba4Schristos entry->len = strlen (str) + 1;
164a1ba9ba4Schristos /* 2G strings lose. */
165a1ba9ba4Schristos BFD_ASSERT (entry->len > 0);
166a1ba9ba4Schristos if (tab->size == tab->alloced)
167a1ba9ba4Schristos {
168a1ba9ba4Schristos bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
169a1ba9ba4Schristos tab->alloced *= 2;
170a1ba9ba4Schristos tab->array = (struct elf_strtab_hash_entry **)
171a1ba9ba4Schristos bfd_realloc_or_free (tab->array, tab->alloced * amt);
172a1ba9ba4Schristos if (tab->array == NULL)
173b2396a7bSchristos return (size_t) -1;
174a1ba9ba4Schristos }
175a1ba9ba4Schristos
176a1ba9ba4Schristos entry->u.index = tab->size++;
177a1ba9ba4Schristos tab->array[entry->u.index] = entry;
178a1ba9ba4Schristos }
179a1ba9ba4Schristos return entry->u.index;
180a1ba9ba4Schristos }
181a1ba9ba4Schristos
182a1ba9ba4Schristos void
_bfd_elf_strtab_addref(struct elf_strtab_hash * tab,size_t idx)183b2396a7bSchristos _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, size_t idx)
184a1ba9ba4Schristos {
185b2396a7bSchristos if (idx == 0 || idx == (size_t) -1)
186a1ba9ba4Schristos return;
187a1ba9ba4Schristos BFD_ASSERT (tab->sec_size == 0);
188a1ba9ba4Schristos BFD_ASSERT (idx < tab->size);
189a1ba9ba4Schristos ++tab->array[idx]->refcount;
190a1ba9ba4Schristos }
191a1ba9ba4Schristos
192a1ba9ba4Schristos void
_bfd_elf_strtab_delref(struct elf_strtab_hash * tab,size_t idx)193b2396a7bSchristos _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, size_t idx)
194a1ba9ba4Schristos {
195b2396a7bSchristos if (idx == 0 || idx == (size_t) -1)
196a1ba9ba4Schristos return;
197a1ba9ba4Schristos BFD_ASSERT (tab->sec_size == 0);
198a1ba9ba4Schristos BFD_ASSERT (idx < tab->size);
199a1ba9ba4Schristos BFD_ASSERT (tab->array[idx]->refcount > 0);
200a1ba9ba4Schristos --tab->array[idx]->refcount;
201a1ba9ba4Schristos }
202a1ba9ba4Schristos
203a1ba9ba4Schristos unsigned int
_bfd_elf_strtab_refcount(struct elf_strtab_hash * tab,size_t idx)204b2396a7bSchristos _bfd_elf_strtab_refcount (struct elf_strtab_hash *tab, size_t idx)
205a1ba9ba4Schristos {
206a1ba9ba4Schristos return tab->array[idx]->refcount;
207a1ba9ba4Schristos }
208a1ba9ba4Schristos
209a1ba9ba4Schristos void
_bfd_elf_strtab_clear_all_refs(struct elf_strtab_hash * tab)210a1ba9ba4Schristos _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
211a1ba9ba4Schristos {
212b2396a7bSchristos size_t idx;
213a1ba9ba4Schristos
214a1ba9ba4Schristos for (idx = 1; idx < tab->size; idx++)
215a1ba9ba4Schristos tab->array[idx]->refcount = 0;
216a1ba9ba4Schristos }
217a1ba9ba4Schristos
218b2396a7bSchristos /* Save strtab refcounts prior to adding --as-needed library. */
219b2396a7bSchristos
220b2396a7bSchristos struct strtab_save
221a1ba9ba4Schristos {
222b2396a7bSchristos size_t size;
223b2396a7bSchristos unsigned int refcount[1];
224b2396a7bSchristos };
225b2396a7bSchristos
226b2396a7bSchristos void *
_bfd_elf_strtab_save(struct elf_strtab_hash * tab)227b2396a7bSchristos _bfd_elf_strtab_save (struct elf_strtab_hash *tab)
228b2396a7bSchristos {
229b2396a7bSchristos struct strtab_save *save;
230b2396a7bSchristos size_t idx, size;
231b2396a7bSchristos
232b2396a7bSchristos size = sizeof (*save) + (tab->size - 1) * sizeof (save->refcount[0]);
233b2396a7bSchristos save = bfd_malloc (size);
234b2396a7bSchristos if (save == NULL)
235b2396a7bSchristos return save;
236b2396a7bSchristos
237b2396a7bSchristos save->size = tab->size;
238b2396a7bSchristos for (idx = 1; idx < tab->size; idx++)
239b2396a7bSchristos save->refcount[idx] = tab->array[idx]->refcount;
240b2396a7bSchristos return save;
241b2396a7bSchristos }
242b2396a7bSchristos
243b2396a7bSchristos /* Restore strtab refcounts on finding --as-needed library not needed. */
244b2396a7bSchristos
245b2396a7bSchristos void
_bfd_elf_strtab_restore(struct elf_strtab_hash * tab,void * buf)246b2396a7bSchristos _bfd_elf_strtab_restore (struct elf_strtab_hash *tab, void *buf)
247b2396a7bSchristos {
248*184b2d41Schristos size_t idx, curr_size = tab->size, save_size;
249b2396a7bSchristos struct strtab_save *save = (struct strtab_save *) buf;
250a1ba9ba4Schristos
251a1ba9ba4Schristos BFD_ASSERT (tab->sec_size == 0);
252*184b2d41Schristos save_size = 1;
253*184b2d41Schristos if (save != NULL)
254*184b2d41Schristos save_size = save->size;
255*184b2d41Schristos BFD_ASSERT (save_size <= curr_size);
256*184b2d41Schristos tab->size = save_size;
257*184b2d41Schristos for (idx = 1; idx < save_size; ++idx)
258b2396a7bSchristos tab->array[idx]->refcount = save->refcount[idx];
259b2396a7bSchristos
260a1ba9ba4Schristos for (; idx < curr_size; ++idx)
261a1ba9ba4Schristos {
262a1ba9ba4Schristos /* We don't remove entries from the hash table, just set their
263a1ba9ba4Schristos REFCOUNT to zero. Setting LEN zero will result in the size
264a1ba9ba4Schristos growing if the entry is added again. See _bfd_elf_strtab_add. */
265a1ba9ba4Schristos tab->array[idx]->refcount = 0;
266a1ba9ba4Schristos tab->array[idx]->len = 0;
267a1ba9ba4Schristos }
268a1ba9ba4Schristos }
269a1ba9ba4Schristos
270a1ba9ba4Schristos bfd_size_type
_bfd_elf_strtab_size(struct elf_strtab_hash * tab)271a1ba9ba4Schristos _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
272a1ba9ba4Schristos {
273a1ba9ba4Schristos return tab->sec_size ? tab->sec_size : tab->size;
274a1ba9ba4Schristos }
275a1ba9ba4Schristos
276a1ba9ba4Schristos bfd_size_type
_bfd_elf_strtab_len(struct elf_strtab_hash * tab)277*184b2d41Schristos _bfd_elf_strtab_len (struct elf_strtab_hash *tab)
278*184b2d41Schristos {
279*184b2d41Schristos return tab->size;
280*184b2d41Schristos }
281*184b2d41Schristos
282*184b2d41Schristos bfd_size_type
_bfd_elf_strtab_offset(struct elf_strtab_hash * tab,size_t idx)283b2396a7bSchristos _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, size_t idx)
284a1ba9ba4Schristos {
285a1ba9ba4Schristos struct elf_strtab_hash_entry *entry;
286a1ba9ba4Schristos
287a1ba9ba4Schristos if (idx == 0)
288a1ba9ba4Schristos return 0;
289a1ba9ba4Schristos BFD_ASSERT (idx < tab->size);
290a1ba9ba4Schristos BFD_ASSERT (tab->sec_size);
291a1ba9ba4Schristos entry = tab->array[idx];
292a1ba9ba4Schristos BFD_ASSERT (entry->refcount > 0);
293a1ba9ba4Schristos entry->refcount--;
294a1ba9ba4Schristos return tab->array[idx]->u.index;
295a1ba9ba4Schristos }
296a1ba9ba4Schristos
297*184b2d41Schristos const char *
_bfd_elf_strtab_str(struct elf_strtab_hash * tab,size_t idx,bfd_size_type * offset)298*184b2d41Schristos _bfd_elf_strtab_str (struct elf_strtab_hash *tab, size_t idx,
299*184b2d41Schristos bfd_size_type *offset)
300*184b2d41Schristos {
301*184b2d41Schristos if (idx == 0)
302*184b2d41Schristos return 0;
303*184b2d41Schristos BFD_ASSERT (idx < tab->size);
304*184b2d41Schristos BFD_ASSERT (tab->sec_size);
305*184b2d41Schristos if (offset)
306*184b2d41Schristos *offset = tab->array[idx]->u.index;
307*184b2d41Schristos return tab->array[idx]->root.string;
308*184b2d41Schristos }
309*184b2d41Schristos
310a1ba9ba4Schristos bfd_boolean
_bfd_elf_strtab_emit(register bfd * abfd,struct elf_strtab_hash * tab)311a1ba9ba4Schristos _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
312a1ba9ba4Schristos {
313b2396a7bSchristos bfd_size_type off = 1;
314b2396a7bSchristos size_t i;
315a1ba9ba4Schristos
316a1ba9ba4Schristos if (bfd_bwrite ("", 1, abfd) != 1)
317a1ba9ba4Schristos return FALSE;
318a1ba9ba4Schristos
319a1ba9ba4Schristos for (i = 1; i < tab->size; ++i)
320a1ba9ba4Schristos {
321a1ba9ba4Schristos register const char *str;
322a1ba9ba4Schristos register unsigned int len;
323a1ba9ba4Schristos
324a1ba9ba4Schristos BFD_ASSERT (tab->array[i]->refcount == 0);
325a1ba9ba4Schristos len = tab->array[i]->len;
326a1ba9ba4Schristos if ((int) len < 0)
327a1ba9ba4Schristos continue;
328a1ba9ba4Schristos
329a1ba9ba4Schristos str = tab->array[i]->root.string;
330a1ba9ba4Schristos if (bfd_bwrite (str, len, abfd) != len)
331a1ba9ba4Schristos return FALSE;
332a1ba9ba4Schristos
333a1ba9ba4Schristos off += len;
334a1ba9ba4Schristos }
335a1ba9ba4Schristos
336a1ba9ba4Schristos BFD_ASSERT (off == tab->sec_size);
337a1ba9ba4Schristos return TRUE;
338a1ba9ba4Schristos }
339a1ba9ba4Schristos
340*184b2d41Schristos /* Compare two elf_strtab_hash_entry structures. Called via qsort.
341*184b2d41Schristos Won't ever return zero as all entries differ, so there is no issue
342*184b2d41Schristos with qsort stability here. */
343a1ba9ba4Schristos
344a1ba9ba4Schristos static int
strrevcmp(const void * a,const void * b)345a1ba9ba4Schristos strrevcmp (const void *a, const void *b)
346a1ba9ba4Schristos {
347a1ba9ba4Schristos struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
348a1ba9ba4Schristos struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
349a1ba9ba4Schristos unsigned int lenA = A->len;
350a1ba9ba4Schristos unsigned int lenB = B->len;
351a1ba9ba4Schristos const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
352a1ba9ba4Schristos const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
353a1ba9ba4Schristos int l = lenA < lenB ? lenA : lenB;
354a1ba9ba4Schristos
355a1ba9ba4Schristos while (l)
356a1ba9ba4Schristos {
357a1ba9ba4Schristos if (*s != *t)
358a1ba9ba4Schristos return (int) *s - (int) *t;
359a1ba9ba4Schristos s--;
360a1ba9ba4Schristos t--;
361a1ba9ba4Schristos l--;
362a1ba9ba4Schristos }
363a1ba9ba4Schristos return lenA - lenB;
364a1ba9ba4Schristos }
365a1ba9ba4Schristos
366a1ba9ba4Schristos static inline int
is_suffix(const struct elf_strtab_hash_entry * A,const struct elf_strtab_hash_entry * B)367a1ba9ba4Schristos is_suffix (const struct elf_strtab_hash_entry *A,
368a1ba9ba4Schristos const struct elf_strtab_hash_entry *B)
369a1ba9ba4Schristos {
370a1ba9ba4Schristos if (A->len <= B->len)
371a1ba9ba4Schristos /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
372a1ba9ba4Schristos not to be equal by the hash table. */
373a1ba9ba4Schristos return 0;
374a1ba9ba4Schristos
375a1ba9ba4Schristos return memcmp (A->root.string + (A->len - B->len),
376a1ba9ba4Schristos B->root.string, B->len - 1) == 0;
377a1ba9ba4Schristos }
378a1ba9ba4Schristos
379a1ba9ba4Schristos /* This function assigns final string table offsets for used strings,
380a1ba9ba4Schristos merging strings matching suffixes of longer strings if possible. */
381a1ba9ba4Schristos
382a1ba9ba4Schristos void
_bfd_elf_strtab_finalize(struct elf_strtab_hash * tab)383a1ba9ba4Schristos _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
384a1ba9ba4Schristos {
385a1ba9ba4Schristos struct elf_strtab_hash_entry **array, **a, *e;
386b2396a7bSchristos bfd_size_type amt, sec_size;
387b2396a7bSchristos size_t size, i;
388a1ba9ba4Schristos
389a1ba9ba4Schristos /* Sort the strings by suffix and length. */
390b2396a7bSchristos amt = tab->size;
391b2396a7bSchristos amt *= sizeof (struct elf_strtab_hash_entry *);
392a1ba9ba4Schristos array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
393a1ba9ba4Schristos if (array == NULL)
394a1ba9ba4Schristos goto alloc_failure;
395a1ba9ba4Schristos
396a1ba9ba4Schristos for (i = 1, a = array; i < tab->size; ++i)
397a1ba9ba4Schristos {
398a1ba9ba4Schristos e = tab->array[i];
399a1ba9ba4Schristos if (e->refcount)
400a1ba9ba4Schristos {
401a1ba9ba4Schristos *a++ = e;
402a1ba9ba4Schristos /* Adjust the length to not include the zero terminator. */
403a1ba9ba4Schristos e->len -= 1;
404a1ba9ba4Schristos }
405a1ba9ba4Schristos else
406a1ba9ba4Schristos e->len = 0;
407a1ba9ba4Schristos }
408a1ba9ba4Schristos
409a1ba9ba4Schristos size = a - array;
410a1ba9ba4Schristos if (size != 0)
411a1ba9ba4Schristos {
412a1ba9ba4Schristos qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
413a1ba9ba4Schristos
414a1ba9ba4Schristos /* Loop over the sorted array and merge suffixes. Start from the
415a1ba9ba4Schristos end because we want eg.
416a1ba9ba4Schristos
417a1ba9ba4Schristos s1 -> "d"
418a1ba9ba4Schristos s2 -> "bcd"
419a1ba9ba4Schristos s3 -> "abcd"
420a1ba9ba4Schristos
421a1ba9ba4Schristos to end up as
422a1ba9ba4Schristos
423a1ba9ba4Schristos s3 -> "abcd"
424a1ba9ba4Schristos s2 _____^
425a1ba9ba4Schristos s1 _______^
426a1ba9ba4Schristos
427a1ba9ba4Schristos ie. we don't want s1 pointing into the old s2. */
428a1ba9ba4Schristos e = *--a;
429a1ba9ba4Schristos e->len += 1;
430a1ba9ba4Schristos while (--a >= array)
431a1ba9ba4Schristos {
432a1ba9ba4Schristos struct elf_strtab_hash_entry *cmp = *a;
433a1ba9ba4Schristos
434a1ba9ba4Schristos cmp->len += 1;
435a1ba9ba4Schristos if (is_suffix (e, cmp))
436a1ba9ba4Schristos {
437a1ba9ba4Schristos cmp->u.suffix = e;
438a1ba9ba4Schristos cmp->len = -cmp->len;
439a1ba9ba4Schristos }
440a1ba9ba4Schristos else
441a1ba9ba4Schristos e = cmp;
442a1ba9ba4Schristos }
443a1ba9ba4Schristos }
444a1ba9ba4Schristos
445a1ba9ba4Schristos alloc_failure:
446a1ba9ba4Schristos free (array);
447a1ba9ba4Schristos
448a1ba9ba4Schristos /* Assign positions to the strings we want to keep. */
449b2396a7bSchristos sec_size = 1;
450a1ba9ba4Schristos for (i = 1; i < tab->size; ++i)
451a1ba9ba4Schristos {
452a1ba9ba4Schristos e = tab->array[i];
453a1ba9ba4Schristos if (e->refcount && e->len > 0)
454a1ba9ba4Schristos {
455b2396a7bSchristos e->u.index = sec_size;
456b2396a7bSchristos sec_size += e->len;
457a1ba9ba4Schristos }
458a1ba9ba4Schristos }
459a1ba9ba4Schristos
460b2396a7bSchristos tab->sec_size = sec_size;
461a1ba9ba4Schristos
462a1ba9ba4Schristos /* Adjust the rest. */
463a1ba9ba4Schristos for (i = 1; i < tab->size; ++i)
464a1ba9ba4Schristos {
465a1ba9ba4Schristos e = tab->array[i];
466a1ba9ba4Schristos if (e->refcount && e->len < 0)
467a1ba9ba4Schristos e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
468a1ba9ba4Schristos }
469a1ba9ba4Schristos }
470