1/* ELF strtab with GC and suffix merging support.
2   Copyright 2001, 2002, 2003, 2005, 2006, 2007, 2008
3   Free Software Foundation, Inc.
4   Written by Jakub Jelinek <jakub@redhat.com>.
5
6   This file is part of BFD, the Binary File Descriptor library.
7
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
10   the Free Software Foundation; either version 3 of the License, or
11   (at your option) any later version.
12
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.
17
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
20   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21   MA 02110-1301, USA.  */
22
23#include "sysdep.h"
24#include "bfd.h"
25#include "libbfd.h"
26#include "elf-bfd.h"
27#include "hashtab.h"
28#include "libiberty.h"
29
30/* An entry in the strtab hash table.  */
31
32struct elf_strtab_hash_entry
33{
34  struct bfd_hash_entry root;
35  /* Length of this entry.  This includes the zero terminator.  */
36  int len;
37  unsigned int refcount;
38  union {
39    /* Index within the merged section.  */
40    bfd_size_type index;
41    /* Entry this is a suffix of (if len < 0).  */
42    struct elf_strtab_hash_entry *suffix;
43  } u;
44};
45
46/* The strtab hash table.  */
47
48struct 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
61/* Routine to create an entry in a section merge hashtab.  */
62
63static struct bfd_hash_entry *
64elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
65			 struct bfd_hash_table *table,
66			 const char *string)
67{
68  /* Allocate the structure if it has not already been allocated by a
69     subclass.  */
70  if (entry == NULL)
71    entry = (struct bfd_hash_entry *)
72        bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
73  if (entry == NULL)
74    return NULL;
75
76  /* Call the allocation method of the superclass.  */
77  entry = bfd_hash_newfunc (entry, table, string);
78
79  if (entry)
80    {
81      /* Initialize the local fields.  */
82      struct elf_strtab_hash_entry *ret;
83
84      ret = (struct elf_strtab_hash_entry *) entry;
85      ret->u.index = -1;
86      ret->refcount = 0;
87      ret->len = 0;
88    }
89
90  return entry;
91}
92
93/* Create a new hash table.  */
94
95struct elf_strtab_hash *
96_bfd_elf_strtab_init (void)
97{
98  struct elf_strtab_hash *table;
99  bfd_size_type amt = sizeof (struct elf_strtab_hash);
100
101  table = (struct elf_strtab_hash *) bfd_malloc (amt);
102  if (table == NULL)
103    return NULL;
104
105  if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
106			    sizeof (struct elf_strtab_hash_entry)))
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 *);
116  table->array = (struct elf_strtab_hash_entry **)
117      bfd_malloc (table->alloced * amt);
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
131void
132_bfd_elf_strtab_free (struct elf_strtab_hash *tab)
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
142bfd_size_type
143_bfd_elf_strtab_add (struct elf_strtab_hash *tab,
144		     const char *str,
145		     bfd_boolean copy)
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 *)
156	  bfd_hash_lookup (&tab->table, str, TRUE, copy);
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;
165      /* 2G strings lose.  */
166      BFD_ASSERT (entry->len > 0);
167      if (tab->size == tab->alloced)
168	{
169	  bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
170	  tab->alloced *= 2;
171	  tab->array = (struct elf_strtab_hash_entry **)
172              bfd_realloc_or_free (tab->array, tab->alloced * amt);
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
183void
184_bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
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
193void
194_bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
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
204void
205_bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
206{
207  bfd_size_type idx;
208
209  for (idx = 1; idx < tab->size; ++idx)
210    tab->array[idx]->refcount = 0;
211}
212
213bfd_size_type
214_bfd_elf_strtab_size (struct elf_strtab_hash *tab)
215{
216  return tab->sec_size ? tab->sec_size : tab->size;
217}
218
219bfd_size_type
220_bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
221{
222  struct elf_strtab_hash_entry *entry;
223
224  if (idx == 0)
225    return 0;
226  BFD_ASSERT (idx < tab->size);
227  BFD_ASSERT (tab->sec_size);
228  entry = tab->array[idx];
229  BFD_ASSERT (entry->refcount > 0);
230  entry->refcount--;
231  return tab->array[idx]->u.index;
232}
233
234bfd_boolean
235_bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
236{
237  bfd_size_type off = 1, i;
238
239  if (bfd_bwrite ("", 1, abfd) != 1)
240    return FALSE;
241
242  for (i = 1; i < tab->size; ++i)
243    {
244      register const char *str;
245      register unsigned int len;
246
247      BFD_ASSERT (tab->array[i]->refcount == 0);
248      len = tab->array[i]->len;
249      if ((int) len < 0)
250	continue;
251
252      str = tab->array[i]->root.string;
253      if (bfd_bwrite (str, len, abfd) != len)
254	return FALSE;
255
256      off += len;
257    }
258
259  BFD_ASSERT (off == tab->sec_size);
260  return TRUE;
261}
262
263/* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
264
265static int
266strrevcmp (const void *a, const void *b)
267{
268  struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
269  struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
270  unsigned int lenA = A->len;
271  unsigned int lenB = B->len;
272  const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
273  const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
274  int l = lenA < lenB ? lenA : lenB;
275
276  while (l)
277    {
278      if (*s != *t)
279	return (int) *s - (int) *t;
280      s--;
281      t--;
282      l--;
283    }
284  return lenA - lenB;
285}
286
287static inline int
288is_suffix (const struct elf_strtab_hash_entry *A,
289	   const struct elf_strtab_hash_entry *B)
290{
291  if (A->len <= B->len)
292    /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
293       not to be equal by the hash table.  */
294    return 0;
295
296  return memcmp (A->root.string + (A->len - B->len),
297		 B->root.string, B->len - 1) == 0;
298}
299
300/* This function assigns final string table offsets for used strings,
301   merging strings matching suffixes of longer strings if possible.  */
302
303void
304_bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
305{
306  struct elf_strtab_hash_entry **array, **a, *e;
307  bfd_size_type size, amt;
308
309  /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
310     a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
311     Besides, indexing with a long long wouldn't give anything but extra
312     cycles.  */
313  size_t i;
314
315  /* Sort the strings by suffix and length.  */
316  amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
317  array = (struct elf_strtab_hash_entry **) bfd_malloc (amt);
318  if (array == NULL)
319    goto alloc_failure;
320
321  for (i = 1, a = array; i < tab->size; ++i)
322    {
323      e = tab->array[i];
324      if (e->refcount)
325	{
326	  *a++ = e;
327	  /* Adjust the length to not include the zero terminator.  */
328	  e->len -= 1;
329	}
330      else
331	e->len = 0;
332    }
333
334  size = a - array;
335  if (size != 0)
336    {
337      qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
338
339      /* Loop over the sorted array and merge suffixes.  Start from the
340	 end because we want eg.
341
342	 s1 -> "d"
343	 s2 -> "bcd"
344	 s3 -> "abcd"
345
346	 to end up as
347
348	 s3 -> "abcd"
349	 s2 _____^
350	 s1 _______^
351
352	 ie. we don't want s1 pointing into the old s2.  */
353      e = *--a;
354      e->len += 1;
355      while (--a >= array)
356	{
357	  struct elf_strtab_hash_entry *cmp = *a;
358
359	  cmp->len += 1;
360	  if (is_suffix (e, cmp))
361	    {
362	      cmp->u.suffix = e;
363	      cmp->len = -cmp->len;
364	    }
365	  else
366	    e = cmp;
367	}
368    }
369
370alloc_failure:
371  if (array)
372    free (array);
373
374  /* Assign positions to the strings we want to keep.  */
375  size = 1;
376  for (i = 1; i < tab->size; ++i)
377    {
378      e = tab->array[i];
379      if (e->refcount && e->len > 0)
380	{
381	  e->u.index = size;
382	  size += e->len;
383	}
384    }
385
386  tab->sec_size = size;
387
388  /* Adjust the rest.  */
389  for (i = 1; i < tab->size; ++i)
390    {
391      e = tab->array[i];
392      if (e->refcount && e->len < 0)
393	e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
394    }
395}
396