libebl/eblwstrtab.c

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