libdwelf/dwelf_strtab.c

   1 /* ELF/DWARF string table handling.
   2    Copyright (C) 2000, 2001, 2002, 2005, 2016 Red Hat, Inc.
   3    This file is part of elfutils.
   4    Written by Ulrich Drepper <drepper@redhat.com>, 2000.
   5
   6    This file is free software; you can redistribute it and/or modify
   7    it under the terms of either
   8
   9      * the GNU Lesser General Public License as published by the Free
  10        Software Foundation; either version 3 of the License, or (at
  11        your option) any later version
  12
  13    or
  14
  15      * the GNU General Public License as published by the Free
  16        Software Foundation; either version 2 of the License, or (at
  17        your option) any later version
  18
  19    or both in parallel, as here.
  20
  21    elfutils is distributed in the hope that it will be useful, but
  22    WITHOUT ANY WARRANTY; without even the implied warranty of
  23    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  24    General Public License for more details.
  25
  26    You should have received copies of the GNU General Public License and
  27    the GNU Lesser General Public License along with this program.  If
  28    not, see <http://www.gnu.org/licenses/>.  */
  29
  30 #ifdef HAVE_CONFIG_H
  31 # include <config.h>
  32 #endif
  33
  34 #include <assert.h>
  35 #include <inttypes.h>
  36 #include <libelf.h>
  37 #include <stddef.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include <unistd.h>
  41
  42 #include "libdwelfP.h"
  43 #include <system.h>
  44
  45
  46 struct Dwelf_Strent
  47 {
  48   const char *string;
  49   size_t len;
  50   struct Dwelf_Strent *next;
  51   struct Dwelf_Strent *left;
  52   struct Dwelf_Strent *right;
  53   size_t offset;
  54   char reverse[0];
  55 };
  56
  57
  58 struct memoryblock
  59 {
  60   struct memoryblock *next;
  61   char memory[0];
  62 };
  63
  64
  65 struct Dwelf_Strtab
  66 {
  67   struct Dwelf_Strent *root;
  68   struct memoryblock *memory;
  69   char *backp;
  70   size_t left;
  71   size_t total;
  72   bool nullstr;
  73
  74   struct Dwelf_Strent null;
  75 };
  76
  77
  78 /* Cache for the pagesize.  */
  79 static size_t ps;
  80 /* We correct this value a bit so that `malloc' is not allocating more
  81    than a page. */
  82 #define MALLOC_OVERHEAD (2 * sizeof (void *))
  83
  84
  85 Dwelf_Strtab *
  86 dwelf_strtab_init (bool nullstr)
  87 {
  88   if (ps == 0)
  89     {
  90       ps = sysconf (_SC_PAGESIZE);
  91       assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
  92     }
  93
  94   Dwelf_Strtab *ret
  95     = (Dwelf_Strtab *) calloc (1, sizeof (struct Dwelf_Strtab));
  96   if (ret != NULL)
  97     {
  98       ret->nullstr = nullstr;
  99
 100       if (nullstr)
 101         {
 102           ret->null.len = 1;
 103           ret->null.string = "";
 104         }
 105     }
 106
 107   return ret;
 108 }
 109
 110
 111 static int
 112 morememory (Dwelf_Strtab *st, size_t len)
 113 {
 114   size_t overhead = offsetof (struct memoryblock, memory);
 115   len += overhead + MALLOC_OVERHEAD;
 116
 117   /* Allocate nearest multiple of pagesize >= len.  */
 118   len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
 119
 120   struct memoryblock *newmem = (struct memoryblock *) malloc (len);
 121   if (newmem == NULL)
 122     return 1;
 123
 124   newmem->next = st->memory;
 125   st->memory = newmem;
 126   st->backp = newmem->memory;
 127   st->left = len - overhead;
 128
 129   return 0;
 130 }
 131
 132
 133 void
 134 dwelf_strtab_free (Dwelf_Strtab *st)
 135 {
 136   struct memoryblock *mb = st->memory;
 137
 138   while (mb != NULL)
 139     {
 140       void *old = mb;
 141       mb = mb->next;
 142       free (old);
 143     }
 144
 145   free (st);
 146 }
 147
 148
 149 static Dwelf_Strent *
 150 newstring (Dwelf_Strtab *st, const char *str, size_t len)
 151 {
 152   /* Compute the amount of padding needed to make the structure aligned.  */
 153   size_t align = ((__alignof__ (struct Dwelf_Strent)
 154                    - (((uintptr_t) st->backp)
 155                       & (__alignof__ (struct Dwelf_Strent) - 1)))
 156                   & (__alignof__ (struct Dwelf_Strent) - 1));
 157
 158   /* Make sure there is enough room in the memory block.  */
 159   if (st->left < align + sizeof (struct Dwelf_Strent) + len)
 160     {
 161       if (morememory (st, sizeof (struct Dwelf_Strent) + len))
 162         return NULL;
 163
 164       align = 0;
 165     }
 166
 167   /* Create the reserved string.  */
 168   Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
 169   newstr->string = str;
 170   newstr->len = len;
 171   newstr->next = NULL;
 172   newstr->left = NULL;
 173   newstr->right = NULL;
 174   newstr->offset = 0;
 175   for (int i = len - 2; i >= 0; --i)
 176     newstr->reverse[i] = str[len - 2 - i];
 177   newstr->reverse[len - 1] = '\0';
 178   st->backp += align + sizeof (struct Dwelf_Strent) + len;
 179   st->left -= align + sizeof (struct Dwelf_Strent) + len;
 180
 181   return newstr;
 182 }
 183
 184
 185 /* XXX This function should definitely be rewritten to use a balancing
 186    tree algorith (AVL, red-black trees).  For now a simple, correct
 187    implementation is enough.  */
 188 static Dwelf_Strent **
 189 searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
 190 {
 191   /* More strings?  */
 192   if (*sep == NULL)
 193     {
 194       *sep = newstr;
 195       return sep;
 196     }
 197
 198   /* Compare the strings.  */
 199   int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
 200                        MIN ((*sep)->len, newstr->len) - 1);
 201   if (cmpres == 0)
 202     /* We found a matching string.  */
 203     return sep;
 204   else if (cmpres > 0)
 205     return searchstring (&(*sep)->left, newstr);
 206   else
 207     return searchstring (&(*sep)->right, newstr);
 208 }
 209
 210
 211 /* Add new string.  The actual string is assumed to be permanent.  */
 212 static Dwelf_Strent *
 213 strtab_add (Dwelf_Strtab *st, const char *str, size_t len)
 214 {
 215   /* Make sure all "" strings get offset 0 but only if the table was
 216      created with a special null entry in mind.  */
 217   if (len == 1 && st->null.string != NULL)
 218     return &st->null;
 219
 220   /* Allocate memory for the new string and its associated information.  */
 221   Dwelf_Strent *newstr = newstring (st, str, len);
 222   if (newstr == NULL)
 223     return NULL;
 224
 225   /* Search in the array for the place to insert the string.  If there
 226      is no string with matching prefix and no string with matching
 227      leading substring, create a new entry.  */
 228   Dwelf_Strent **sep = searchstring (&st->root, newstr);
 229   if (*sep != newstr)
 230     {
 231       /* This is not the same entry.  This means we have a prefix match.  */
 232       if ((*sep)->len > newstr->len)
 233         {
 234           /* Check whether we already know this string.  */
 235           for (Dwelf_Strent *subs = (*sep)->next; subs != NULL;
 236                subs = subs->next)
 237             if (subs->len == newstr->len)
 238               {
 239                 /* We have an exact match with a substring.  Free the memory
 240                    we allocated.  */
 241                 st->left += st->backp - (char *) newstr;
 242                 st->backp = (char *) newstr;
 243
 244                 return subs;
 245               }
 246
 247           /* We have a new substring.  This means we don't need the reverse
 248              string of this entry anymore.  */
 249           st->backp -= newstr->len;
 250           st->left += newstr->len;
 251
 252           newstr->next = (*sep)->next;
 253           (*sep)->next = newstr;
 254         }
 255       else if ((*sep)->len != newstr->len)
 256         {
 257           /* When we get here it means that the string we are about to
 258              add has a common prefix with a string we already have but
 259              it is longer.  In this case we have to put it first.  */
 260           st->total += newstr->len - (*sep)->len;
 261           newstr->next = *sep;
 262           newstr->left = (*sep)->left;
 263           newstr->right = (*sep)->right;
 264           *sep = newstr;
 265         }
 266       else
 267         {
 268           /* We have an exact match.  Free the memory we allocated.  */
 269           st->left += st->backp - (char *) newstr;
 270           st->backp = (char *) newstr;
 271
 272           newstr = *sep;
 273         }
 274     }
 275   else
 276     st->total += newstr->len;
 277
 278   return newstr;
 279 }
 280
 281 Dwelf_Strent *
 282 dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
 283 {
 284   return strtab_add (st, str, strlen (str) + 1);
 285 }
 286
 287 Dwelf_Strent *
 288 dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
 289 {
 290   return strtab_add (st, str, len);
 291 }
 292
 293 static void
 294 copystrings (Dwelf_Strent *nodep, char **freep, size_t *offsetp)
 295 {
 296   if (nodep->left != NULL)
 297     copystrings (nodep->left, freep, offsetp);
 298
 299   /* Process the current node.  */
 300   nodep->offset = *offsetp;
 301   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
 302   *offsetp += nodep->len;
 303
 304   for (Dwelf_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
 305     {
 306       assert (subs->len < nodep->len);
 307       subs->offset = nodep->offset + nodep->len - subs->len;
 308       assert (subs->offset != 0 || subs->string[0] == '\0');
 309     }
 310
 311   if (nodep->right != NULL)
 312     copystrings (nodep->right, freep, offsetp);
 313 }
 314
 315
 316 Elf_Data *
 317 dwelf_strtab_finalize (Dwelf_Strtab *st, Elf_Data *data)
 318 {
 319   size_t nulllen = st->nullstr ? 1 : 0;
 320
 321   /* Fill in the information.  */
 322   data->d_buf = malloc (st->total + nulllen);
 323   if (data->d_buf == NULL)
 324     return NULL;
 325
 326   /* The first byte must always be zero if we created the table with a
 327      null string.  */
 328   if (st->nullstr)
 329     *((char *) data->d_buf) = '\0';
 330
 331   data->d_type = ELF_T_BYTE;
 332   data->d_size = st->total + nulllen;
 333   data->d_off = 0;
 334   data->d_align = 1;
 335   data->d_version = EV_CURRENT;
 336
 337   /* Now run through the tree and add all the string while also updating
 338      the offset members of the elfstrent records.  */
 339   char *endp = (char *) data->d_buf + nulllen;
 340   size_t copylen = nulllen;
 341   if (st->root)
 342     copystrings (st->root, &endp, &copylen);
 343   assert (copylen == st->total + nulllen);
 344
 345   return data;
 346 }
 347
 348
 349 size_t
 350 dwelf_strent_off (Dwelf_Strent *se)
 351 {
 352   return se->offset;
 353 }
 354
 355
 356 const char *
 357 dwelf_strent_str (Dwelf_Strent *se)
 358 {
 359   return se->string;
 360 }