libebl/eblstrtab.c

   1 /* ELF string table handling.
   2    Copyright (C) 2000, 2001, 2002, 2005 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 #include <sys/param.h>
  42
  43 #include "libebl.h"
  44 #include <system.h>
  45
  46 #ifndef MIN
  47 # define MIN(a, b) ((a) < (b) ? (a) : (b))
  48 #endif
  49
  50
  51 struct Ebl_Strent
  52 {
  53   const char *string;
  54   size_t len;
  55   struct Ebl_Strent *next;
  56   struct Ebl_Strent *left;
  57   struct Ebl_Strent *right;
  58   size_t offset;
  59   char reverse[0];
  60 };
  61
  62
  63 struct memoryblock
  64 {
  65   struct memoryblock *next;
  66   char memory[0];
  67 };
  68
  69
  70 struct Ebl_Strtab
  71 {
  72   struct Ebl_Strent *root;
  73   struct memoryblock *memory;
  74   char *backp;
  75   size_t left;
  76   size_t total;
  77   bool nullstr;
  78
  79   struct Ebl_Strent null;
  80 };
  81
  82
  83 /* Cache for the pagesize.  */
  84 static size_t ps;
  85 /* We correct this value a bit so that `malloc' is not allocating more
  86    than a page. */
  87 #define MALLOC_OVERHEAD (2 * sizeof (void *))
  88
  89
  90 struct Ebl_Strtab *
  91 ebl_strtabinit (bool nullstr)
  92 {
  93   if (ps == 0)
  94     {
  95       ps = sysconf (_SC_PAGESIZE);
  96       assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
  97     }
  98
  99   struct Ebl_Strtab *ret
 100     = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab));
 101   if (ret != NULL)
 102     {
 103       ret->nullstr = nullstr;
 104
 105       if (nullstr)
 106         {
 107           ret->null.len = 1;
 108           ret->null.string = "";
 109         }
 110     }
 111
 112   return ret;
 113 }
 114
 115
 116 static int
 117 morememory (struct Ebl_Strtab *st, size_t len)
 118 {
 119   size_t overhead = offsetof (struct memoryblock, memory);
 120   len += overhead + MALLOC_OVERHEAD;
 121
 122   /* Allocate nearest multiple of pagesize >= len.  */
 123   len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
 124
 125   struct memoryblock *newmem = (struct memoryblock *) malloc (len);
 126   if (newmem == NULL)
 127     return 1;
 128
 129   newmem->next = st->memory;
 130   st->memory = newmem;
 131   st->backp = newmem->memory;
 132   st->left = len - overhead;
 133
 134   return 0;
 135 }
 136
 137
 138 void
 139 ebl_strtabfree (struct Ebl_Strtab *st)
 140 {
 141   struct memoryblock *mb = st->memory;
 142
 143   while (mb != NULL)
 144     {
 145       void *old = mb;
 146       mb = mb->next;
 147       free (old);
 148     }
 149
 150   free (st);
 151 }
 152
 153
 154 static struct Ebl_Strent *
 155 newstring (struct Ebl_Strtab *st, const char *str, size_t len)
 156 {
 157   /* Compute the amount of padding needed to make the structure aligned.  */
 158   size_t align = ((__alignof__ (struct Ebl_Strent)
 159                    - (((uintptr_t) st->backp)
 160                       & (__alignof__ (struct Ebl_Strent) - 1)))
 161                   & (__alignof__ (struct Ebl_Strent) - 1));
 162
 163   /* Make sure there is enough room in the memory block.  */
 164   if (st->left < align + sizeof (struct Ebl_Strent) + len)
 165     {
 166       if (morememory (st, sizeof (struct Ebl_Strent) + len))
 167         return NULL;
 168
 169       align = 0;
 170     }
 171
 172   /* Create the reserved string.  */
 173   struct Ebl_Strent *newstr = (struct Ebl_Strent *) (st->backp + align);
 174   newstr->string = str;
 175   newstr->len = len;
 176   newstr->next = NULL;
 177   newstr->left = NULL;
 178   newstr->right = NULL;
 179   newstr->offset = 0;
 180   for (int i = len - 2; i >= 0; --i)
 181     newstr->reverse[i] = str[len - 2 - i];
 182   newstr->reverse[len - 1] = '\0';
 183   st->backp += align + sizeof (struct Ebl_Strent) + len;
 184   st->left -= align + sizeof (struct Ebl_Strent) + len;
 185
 186   return newstr;
 187 }
 188
 189
 190 /* XXX This function should definitely be rewritten to use a balancing
 191    tree algorith (AVL, red-black trees).  For now a simple, correct
 192    implementation is enough.  */
 193 static struct Ebl_Strent **
 194 searchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr)
 195 {
 196   /* More strings?  */
 197   if (*sep == NULL)
 198     {
 199       *sep = newstr;
 200       return sep;
 201     }
 202
 203   /* Compare the strings.  */
 204   int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
 205                        MIN ((*sep)->len, newstr->len) - 1);
 206   if (cmpres == 0)
 207     /* We found a matching string.  */
 208     return sep;
 209   else if (cmpres > 0)
 210     return searchstring (&(*sep)->left, newstr);
 211   else
 212     return searchstring (&(*sep)->right, newstr);
 213 }
 214
 215
 216 /* Add new string.  The actual string is assumed to be permanent.  */
 217 struct Ebl_Strent *
 218 ebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len)
 219 {
 220   /* Compute the string length if the caller doesn't know it.  */
 221   if (len == 0)
 222     len = strlen (str) + 1;
 223
 224   /* Make sure all "" strings get offset 0 but only if the table was
 225      created with a special null entry in mind.  */
 226   if (len == 1 && st->null.string != NULL)
 227     return &st->null;
 228
 229   /* Allocate memory for the new string and its associated information.  */
 230   struct Ebl_Strent *newstr = newstring (st, str, len);
 231   if (newstr == NULL)
 232     return NULL;
 233
 234   /* Search in the array for the place to insert the string.  If there
 235      is no string with matching prefix and no string with matching
 236      leading substring, create a new entry.  */
 237   struct Ebl_Strent **sep = searchstring (&st->root, newstr);
 238   if (*sep != newstr)
 239     {
 240       /* This is not the same entry.  This means we have a prefix match.  */
 241       if ((*sep)->len > newstr->len)
 242         {
 243           /* Check whether we already know this string.  */
 244           for (struct Ebl_Strent *subs = (*sep)->next; subs != NULL;
 245                subs = subs->next)
 246             if (subs->len == newstr->len)
 247               {
 248                 /* We have an exact match with a substring.  Free the memory
 249                    we allocated.  */
 250                 st->left += st->backp - (char *) newstr;
 251                 st->backp = (char *) newstr;
 252
 253                 return subs;
 254               }
 255
 256           /* We have a new substring.  This means we don't need the reverse
 257              string of this entry anymore.  */
 258           st->backp -= newstr->len;
 259           st->left += newstr->len;
 260
 261           newstr->next = (*sep)->next;
 262           (*sep)->next = newstr;
 263         }
 264       else if ((*sep)->len != newstr->len)
 265         {
 266           /* When we get here it means that the string we are about to
 267              add has a common prefix with a string we already have but
 268              it is longer.  In this case we have to put it first.  */
 269           st->total += newstr->len - (*sep)->len;
 270           newstr->next = *sep;
 271           newstr->left = (*sep)->left;
 272           newstr->right = (*sep)->right;
 273           *sep = newstr;
 274         }
 275       else
 276         {
 277           /* We have an exact match.  Free the memory we allocated.  */
 278           st->left += st->backp - (char *) newstr;
 279           st->backp = (char *) newstr;
 280
 281           newstr = *sep;
 282         }
 283     }
 284   else
 285     st->total += newstr->len;
 286
 287   return newstr;
 288 }
 289
 290
 291 static void
 292 copystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp)
 293 {
 294   if (nodep->left != NULL)
 295     copystrings (nodep->left, freep, offsetp);
 296
 297   /* Process the current node.  */
 298   nodep->offset = *offsetp;
 299   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
 300   *offsetp += nodep->len;
 301
 302   for (struct Ebl_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
 303     {
 304       assert (subs->len < nodep->len);
 305       subs->offset = nodep->offset + nodep->len - subs->len;
 306       assert (subs->offset != 0 || subs->string[0] == '\0');
 307     }
 308
 309   if (nodep->right != NULL)
 310     copystrings (nodep->right, freep, offsetp);
 311 }
 312
 313
 314 void
 315 ebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data)
 316 {
 317   size_t nulllen = st->nullstr ? 1 : 0;
 318
 319   /* Fill in the information.  */
 320   data->d_buf = malloc (st->total + nulllen);
 321   if (data->d_buf == NULL)
 322     abort ();
 323
 324   /* The first byte must always be zero if we created the table with a
 325      null string.  */
 326   if (st->nullstr)
 327     *((char *) data->d_buf) = '\0';
 328
 329   data->d_type = ELF_T_BYTE;
 330   data->d_size = st->total + nulllen;
 331   data->d_off = 0;
 332   data->d_align = 1;
 333   data->d_version = EV_CURRENT;
 334
 335   /* Now run through the tree and add all the string while also updating
 336      the offset members of the elfstrent records.  */
 337   char *endp = (char *) data->d_buf + nulllen;
 338   size_t copylen = nulllen;
 339   if (st->root)
 340     copystrings (st->root, &endp, &copylen);
 341   assert (copylen == st->total + nulllen);
 342 }
 343
 344
 345 size_t
 346 ebl_strtaboffset (struct Ebl_Strent *se)
 347 {
 348   return se->offset;
 349 }
 350
 351
 352 const char *
 353 ebl_string (struct Ebl_Strent *se)
 354 {
 355   assert (se->string != NULL);
 356
 357   return se->string;
 358 }