Back to index

cell-binutils  2.17cvs20070401
elf-strtab.c
Go to the documentation of this file.
00001 /* ELF strtab with GC and suffix merging support.
00002    Copyright 2001, 2002, 2003, 2005, 2006 Free Software Foundation, Inc.
00003    Written by Jakub Jelinek <jakub@redhat.com>.
00004 
00005    This file is part of BFD, the Binary File Descriptor library.
00006 
00007    This program is free software; you can redistribute it and/or modify
00008    it under the terms of the GNU General Public License as published by
00009    the Free Software Foundation; either version 2 of the License, or
00010    (at your option) any later version.
00011 
00012    This program is distributed in the hope that it will be useful,
00013    but WITHOUT ANY WARRANTY; without even the implied warranty of
00014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015    GNU General Public License for more details.
00016 
00017    You should have received a copy of the GNU General Public License
00018    along with this program; if not, write to the Free Software
00019    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.  */
00020 
00021 #include "bfd.h"
00022 #include "sysdep.h"
00023 #include "libbfd.h"
00024 #include "elf-bfd.h"
00025 #include "hashtab.h"
00026 #include "libiberty.h"
00027 
00028 /* An entry in the strtab hash table.  */
00029 
00030 struct elf_strtab_hash_entry
00031 {
00032   struct bfd_hash_entry root;
00033   /* Length of this entry.  This includes the zero terminator.  */
00034   int len;
00035   unsigned int refcount;
00036   union {
00037     /* Index within the merged section.  */
00038     bfd_size_type index;
00039     /* Entry this is a suffix of (if len < 0).  */
00040     struct elf_strtab_hash_entry *suffix;
00041   } u;
00042 };
00043 
00044 /* The strtab hash table.  */
00045 
00046 struct elf_strtab_hash
00047 {
00048   struct bfd_hash_table table;
00049   /* Next available index.  */
00050   bfd_size_type size;
00051   /* Number of array entries alloced.  */
00052   bfd_size_type alloced;
00053   /* Final strtab size.  */
00054   bfd_size_type sec_size;
00055   /* Array of pointers to strtab entries.  */
00056   struct elf_strtab_hash_entry **array;
00057 };
00058 
00059 /* Routine to create an entry in a section merge hashtab.  */
00060 
00061 static struct bfd_hash_entry *
00062 elf_strtab_hash_newfunc (struct bfd_hash_entry *entry,
00063                       struct bfd_hash_table *table,
00064                       const char *string)
00065 {
00066   /* Allocate the structure if it has not already been allocated by a
00067      subclass.  */
00068   if (entry == NULL)
00069     entry = bfd_hash_allocate (table, sizeof (struct elf_strtab_hash_entry));
00070   if (entry == NULL)
00071     return NULL;
00072 
00073   /* Call the allocation method of the superclass.  */
00074   entry = bfd_hash_newfunc (entry, table, string);
00075 
00076   if (entry)
00077     {
00078       /* Initialize the local fields.  */
00079       struct elf_strtab_hash_entry *ret;
00080 
00081       ret = (struct elf_strtab_hash_entry *) entry;
00082       ret->u.index = -1;
00083       ret->refcount = 0;
00084       ret->len = 0;
00085     }
00086 
00087   return entry;
00088 }
00089 
00090 /* Create a new hash table.  */
00091 
00092 struct elf_strtab_hash *
00093 _bfd_elf_strtab_init (void)
00094 {
00095   struct elf_strtab_hash *table;
00096   bfd_size_type amt = sizeof (struct elf_strtab_hash);
00097 
00098   table = bfd_malloc (amt);
00099   if (table == NULL)
00100     return NULL;
00101 
00102   if (!bfd_hash_table_init (&table->table, elf_strtab_hash_newfunc,
00103                          sizeof (struct elf_strtab_hash_entry)))
00104     {
00105       free (table);
00106       return NULL;
00107     }
00108 
00109   table->sec_size = 0;
00110   table->size = 1;
00111   table->alloced = 64;
00112   amt = sizeof (struct elf_strtab_hasn_entry *);
00113   table->array = bfd_malloc (table->alloced * amt);
00114   if (table->array == NULL)
00115     {
00116       free (table);
00117       return NULL;
00118     }
00119 
00120   table->array[0] = NULL;
00121 
00122   return table;
00123 }
00124 
00125 /* Free a strtab.  */
00126 
00127 void
00128 _bfd_elf_strtab_free (struct elf_strtab_hash *tab)
00129 {
00130   bfd_hash_table_free (&tab->table);
00131   free (tab->array);
00132   free (tab);
00133 }
00134 
00135 /* Get the index of an entity in a hash table, adding it if it is not
00136    already present.  */
00137 
00138 bfd_size_type
00139 _bfd_elf_strtab_add (struct elf_strtab_hash *tab,
00140                    const char *str,
00141                    bfd_boolean copy)
00142 {
00143   register struct elf_strtab_hash_entry *entry;
00144 
00145   /* We handle this specially, since we don't want to do refcounting
00146      on it.  */
00147   if (*str == '\0')
00148     return 0;
00149 
00150   BFD_ASSERT (tab->sec_size == 0);
00151   entry = (struct elf_strtab_hash_entry *)
00152          bfd_hash_lookup (&tab->table, str, TRUE, copy);
00153 
00154   if (entry == NULL)
00155     return (bfd_size_type) -1;
00156 
00157   entry->refcount++;
00158   if (entry->len == 0)
00159     {
00160       entry->len = strlen (str) + 1;
00161       /* 2G strings lose.  */
00162       BFD_ASSERT (entry->len > 0);
00163       if (tab->size == tab->alloced)
00164        {
00165          bfd_size_type amt = sizeof (struct elf_strtab_hash_entry *);
00166          tab->alloced *= 2;
00167          tab->array = bfd_realloc (tab->array, tab->alloced * amt);
00168          if (tab->array == NULL)
00169            return (bfd_size_type) -1;
00170        }
00171 
00172       entry->u.index = tab->size++;
00173       tab->array[entry->u.index] = entry;
00174     }
00175   return entry->u.index;
00176 }
00177 
00178 void
00179 _bfd_elf_strtab_addref (struct elf_strtab_hash *tab, bfd_size_type idx)
00180 {
00181   if (idx == 0 || idx == (bfd_size_type) -1)
00182     return;
00183   BFD_ASSERT (tab->sec_size == 0);
00184   BFD_ASSERT (idx < tab->size);
00185   ++tab->array[idx]->refcount;
00186 }
00187 
00188 void
00189 _bfd_elf_strtab_delref (struct elf_strtab_hash *tab, bfd_size_type idx)
00190 {
00191   if (idx == 0 || idx == (bfd_size_type) -1)
00192     return;
00193   BFD_ASSERT (tab->sec_size == 0);
00194   BFD_ASSERT (idx < tab->size);
00195   BFD_ASSERT (tab->array[idx]->refcount > 0);
00196   --tab->array[idx]->refcount;
00197 }
00198 
00199 void
00200 _bfd_elf_strtab_clear_all_refs (struct elf_strtab_hash *tab)
00201 {
00202   bfd_size_type idx;
00203 
00204   for (idx = 1; idx < tab->size; ++idx)
00205     tab->array[idx]->refcount = 0;
00206 }
00207 
00208 bfd_size_type
00209 _bfd_elf_strtab_size (struct elf_strtab_hash *tab)
00210 {
00211   return tab->sec_size ? tab->sec_size : tab->size;
00212 }
00213 
00214 bfd_size_type
00215 _bfd_elf_strtab_offset (struct elf_strtab_hash *tab, bfd_size_type idx)
00216 {
00217   struct elf_strtab_hash_entry *entry;
00218 
00219   if (idx == 0)
00220     return 0;
00221   BFD_ASSERT (idx < tab->size);
00222   BFD_ASSERT (tab->sec_size);
00223   entry = tab->array[idx];
00224   BFD_ASSERT (entry->refcount > 0);
00225   entry->refcount--;
00226   return tab->array[idx]->u.index;
00227 }
00228 
00229 bfd_boolean
00230 _bfd_elf_strtab_emit (register bfd *abfd, struct elf_strtab_hash *tab)
00231 {
00232   bfd_size_type off = 1, i;
00233 
00234   if (bfd_bwrite ("", 1, abfd) != 1)
00235     return FALSE;
00236 
00237   for (i = 1; i < tab->size; ++i)
00238     {
00239       register const char *str;
00240       register unsigned int len;
00241 
00242       BFD_ASSERT (tab->array[i]->refcount == 0);
00243       len = tab->array[i]->len;
00244       if ((int) len < 0)
00245        continue;
00246 
00247       str = tab->array[i]->root.string;
00248       if (bfd_bwrite (str, len, abfd) != len)
00249        return FALSE;
00250 
00251       off += len;
00252     }
00253 
00254   BFD_ASSERT (off == tab->sec_size);
00255   return TRUE;
00256 }
00257 
00258 /* Compare two elf_strtab_hash_entry structures.  Called via qsort.  */
00259 
00260 static int
00261 strrevcmp (const void *a, const void *b)
00262 {
00263   struct elf_strtab_hash_entry *A = *(struct elf_strtab_hash_entry **) a;
00264   struct elf_strtab_hash_entry *B = *(struct elf_strtab_hash_entry **) b;
00265   unsigned int lenA = A->len;
00266   unsigned int lenB = B->len;
00267   const unsigned char *s = (const unsigned char *) A->root.string + lenA - 1;
00268   const unsigned char *t = (const unsigned char *) B->root.string + lenB - 1;
00269   int l = lenA < lenB ? lenA : lenB;
00270 
00271   while (l)
00272     {
00273       if (*s != *t)
00274        return (int) *s - (int) *t;
00275       s--;
00276       t--;
00277       l--;
00278     }
00279   return lenA - lenB;
00280 }
00281 
00282 static inline int
00283 is_suffix (const struct elf_strtab_hash_entry *A,
00284           const struct elf_strtab_hash_entry *B)
00285 {
00286   if (A->len <= B->len)
00287     /* B cannot be a suffix of A unless A is equal to B, which is guaranteed
00288        not to be equal by the hash table.  */
00289     return 0;
00290 
00291   return memcmp (A->root.string + (A->len - B->len),
00292                B->root.string, B->len - 1) == 0;
00293 }
00294 
00295 /* This function assigns final string table offsets for used strings,
00296    merging strings matching suffixes of longer strings if possible.  */
00297 
00298 void
00299 _bfd_elf_strtab_finalize (struct elf_strtab_hash *tab)
00300 {
00301   struct elf_strtab_hash_entry **array, **a, *e;
00302   bfd_size_type size, amt;
00303 
00304   /* GCC 2.91.66 (egcs-1.1.2) on i386 miscompiles this function when i is
00305      a 64-bit bfd_size_type: a 64-bit target or --enable-64-bit-bfd.
00306      Besides, indexing with a long long wouldn't give anything but extra
00307      cycles.  */
00308   size_t i;
00309 
00310   /* Sort the strings by suffix and length.  */
00311   amt = tab->size * sizeof (struct elf_strtab_hash_entry *);
00312   array = bfd_malloc (amt);
00313   if (array == NULL)
00314     goto alloc_failure;
00315 
00316   for (i = 1, a = array; i < tab->size; ++i)
00317     {
00318       e = tab->array[i];
00319       if (e->refcount)
00320        {
00321          *a++ = e;
00322          /* Adjust the length to not include the zero terminator.  */
00323          e->len -= 1;
00324        }
00325       else
00326        e->len = 0;
00327     }
00328 
00329   size = a - array;
00330   if (size != 0)
00331     {
00332       qsort (array, size, sizeof (struct elf_strtab_hash_entry *), strrevcmp);
00333 
00334       /* Loop over the sorted array and merge suffixes.  Start from the
00335         end because we want eg.
00336 
00337         s1 -> "d"
00338         s2 -> "bcd"
00339         s3 -> "abcd"
00340 
00341         to end up as
00342 
00343         s3 -> "abcd"
00344         s2 _____^
00345         s1 _______^
00346 
00347         ie. we don't want s1 pointing into the old s2.  */
00348       e = *--a;
00349       e->len += 1;
00350       while (--a >= array)
00351        {
00352          struct elf_strtab_hash_entry *cmp = *a;
00353 
00354          cmp->len += 1;
00355          if (is_suffix (e, cmp))
00356            {
00357              cmp->u.suffix = e;
00358              cmp->len = -cmp->len;
00359            }
00360          else
00361            e = cmp;
00362        }
00363     }
00364 
00365 alloc_failure:
00366   if (array)
00367     free (array);
00368 
00369   /* Assign positions to the strings we want to keep.  */
00370   size = 1;
00371   for (i = 1; i < tab->size; ++i)
00372     {
00373       e = tab->array[i];
00374       if (e->refcount && e->len > 0)
00375        {
00376          e->u.index = size;
00377          size += e->len;
00378        }
00379     }
00380 
00381   tab->sec_size = size;
00382 
00383   /* Adjust the rest.  */
00384   for (i = 1; i < tab->size; ++i)
00385     {
00386       e = tab->array[i];
00387       if (e->refcount && e->len < 0)
00388        e->u.index = e->u.suffix->u.index + (e->u.suffix->len + e->len);
00389     }
00390 }