Home | History | Annotate | Download | only in libebl
      1 /* Generic 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 (at) 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 
     45 #ifndef MIN
     46 # define MIN(a, b) ((a) < (b) ? (a) : (b))
     47 #endif
     48 
     49 
     50 struct Ebl_GStrent
     51 {
     52   const char *string;
     53   size_t len;
     54   struct Ebl_GStrent *next;
     55   struct Ebl_GStrent *left;
     56   struct Ebl_GStrent *right;
     57   size_t offset;
     58   unsigned int width;
     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_GStrtab
     71 {
     72   struct Ebl_GStrent *root;
     73   struct memoryblock *memory;
     74   char *backp;
     75   size_t left;
     76   size_t total;
     77   unsigned int width;
     78   bool nullstr;
     79 
     80   struct Ebl_GStrent 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_GStrtab *
     90 ebl_gstrtabinit (unsigned int width, bool nullstr)
     91 {
     92   struct Ebl_GStrtab *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_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab));
    101   if (ret != NULL)
    102     {
    103       ret->width = width;
    104       ret->nullstr = nullstr;
    105 
    106       if (nullstr)
    107 	{
    108 	  ret->null.len = 1;
    109 	  ret->null.string = (char *) calloc (1, width);
    110 	}
    111     }
    112 
    113   return ret;
    114 }
    115 
    116 
    117 static void
    118 morememory (struct Ebl_GStrtab *st, size_t len)
    119 {
    120   struct memoryblock *newmem;
    121 
    122   if (len < ps)
    123     len = ps;
    124   newmem = (struct memoryblock *) malloc (len);
    125   if (newmem == NULL)
    126     abort ();
    127 
    128   newmem->next = st->memory;
    129   st->memory = newmem;
    130   st->backp = newmem->memory;
    131   st->left = len - offsetof (struct memoryblock, memory);
    132 }
    133 
    134 
    135 void
    136 ebl_gstrtabfree (struct Ebl_GStrtab *st)
    137 {
    138   struct memoryblock *mb = st->memory;
    139 
    140   while (mb != NULL)
    141     {
    142       void *old = mb;
    143       mb = mb->next;
    144       free (old);
    145     }
    146 
    147   if (st->null.string != NULL)
    148     free ((char *) st->null.string);
    149 
    150   free (st);
    151 }
    152 
    153 
    154 static struct Ebl_GStrent *
    155 newstring (struct Ebl_GStrtab *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_GStrent)
    159 		   - (((uintptr_t) st->backp)
    160 		      & (__alignof__ (struct Ebl_GStrent) - 1)))
    161 		  & (__alignof__ (struct Ebl_GStrent) - 1));
    162 
    163   /* Make sure there is enough room in the memory block.  */
    164   if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width)
    165     {
    166       morememory (st, sizeof (struct Ebl_GStrent) + len * st->width);
    167       align = 0;
    168     }
    169 
    170   /* Create the reserved string.  */
    171   struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align);
    172   newstr->string = str;
    173   newstr->len = len;
    174   newstr->width = st->width;
    175   newstr->next = NULL;
    176   newstr->left = NULL;
    177   newstr->right = NULL;
    178   newstr->offset = 0;
    179   for (int i = len - 2; i >= 0; --i)
    180     for (int j = st->width - 1; j >= 0; --j)
    181       newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j];
    182   for (size_t j = 0; j < st->width; ++j)
    183     newstr->reverse[(len - 1) * st->width + j] = '\0';
    184   st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width;
    185   st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width;
    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_GStrent **
    195 searchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *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 = memcmp ((*sep)->reverse, newstr->reverse,
    208 		   (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width);
    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_GStrent *
    221 ebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len)
    222 {
    223   struct Ebl_GStrent *newstr;
    224   struct Ebl_GStrent **sep;
    225 
    226   /* Compute the string length if the caller doesn't know it.  */
    227   if (len == 0)
    228     {
    229       size_t j;
    230 
    231       do
    232 	for (j = 0; j < st->width; ++j)
    233 	  if (str[len * st->width + j] != '\0')
    234 	    break;
    235       while (j == st->width && ++len);
    236     }
    237 
    238   /* Make sure all "" strings get offset 0 but only if the table was
    239      created with a special null entry in mind.  */
    240   if (len == 1 && st->null.string != NULL)
    241     return &st->null;
    242 
    243   /* Allocate memory for the new string and its associated information.  */
    244   newstr = newstring (st, str, len);
    245 
    246   /* Search in the array for the place to insert the string.  If there
    247      is no string with matching prefix and no string with matching
    248      leading substring, create a new entry.  */
    249   sep = searchstring (&st->root, newstr);
    250   if (*sep != newstr)
    251     {
    252       /* This is not the same entry.  This means we have a prefix match.  */
    253       if ((*sep)->len > newstr->len)
    254 	{
    255 	  struct Ebl_GStrent *subs;
    256 
    257 	  /* Check whether we already know this string.  */
    258 	  for (subs = (*sep)->next; subs != NULL; subs = subs->next)
    259 	    if (subs->len == newstr->len)
    260 	      {
    261 		/* We have an exact match with a substring.  Free the memory
    262 		   we allocated.  */
    263 		st->left += (st->backp - (char *) newstr) * st->width;
    264 		st->backp = (char *) newstr;
    265 
    266 		return subs;
    267 	      }
    268 
    269 	  /* We have a new substring.  This means we don't need the reverse
    270 	     string of this entry anymore.  */
    271 	  st->backp -= newstr->len;
    272 	  st->left += newstr->len;
    273 
    274 	  newstr->next = (*sep)->next;
    275 	  (*sep)->next = newstr;
    276 	}
    277       else if ((*sep)->len != newstr->len)
    278 	{
    279 	  /* When we get here it means that the string we are about to
    280 	     add has a common prefix with a string we already have but
    281 	     it is longer.  In this case we have to put it first.  */
    282 	  st->total += newstr->len - (*sep)->len;
    283 	  newstr->next = *sep;
    284 	  newstr->left = (*sep)->left;
    285 	  newstr->right = (*sep)->right;
    286 	  *sep = newstr;
    287 	}
    288       else
    289 	{
    290 	  /* We have an exact match.  Free the memory we allocated.  */
    291 	  st->left += (st->backp - (char *) newstr) * st->width;
    292 	  st->backp = (char *) newstr;
    293 
    294 	  newstr = *sep;
    295 	}
    296     }
    297   else
    298     st->total += newstr->len;
    299 
    300   return newstr;
    301 }
    302 
    303 
    304 static void
    305 copystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp)
    306 {
    307   struct Ebl_GStrent *subs;
    308 
    309   if (nodep->left != NULL)
    310     copystrings (nodep->left, freep, offsetp);
    311 
    312   /* Process the current node.  */
    313   nodep->offset = *offsetp;
    314   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width);
    315   *offsetp += nodep->len * nodep->width;
    316 
    317   for (subs = nodep->next; subs != NULL; subs = subs->next)
    318     {
    319       assert (subs->len < nodep->len);
    320       subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width;
    321       assert (subs->offset != 0 || subs->string[0] == '\0');
    322     }
    323 
    324   if (nodep->right != NULL)
    325     copystrings (nodep->right, freep, offsetp);
    326 }
    327 
    328 
    329 void
    330 ebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data)
    331 {
    332   size_t copylen;
    333   char *endp;
    334   size_t nulllen = st->nullstr ? st->width : 0;
    335 
    336   /* Fill in the information.  */
    337   data->d_buf = malloc (st->total + nulllen);
    338   if (data->d_buf == NULL)
    339     abort ();
    340 
    341   /* The first byte must always be zero if we created the table with a
    342      null string.  */
    343   if (st->nullstr)
    344     memset (data->d_buf, '\0', st->width);
    345 
    346   data->d_type = ELF_T_BYTE;
    347   data->d_size = st->total + nulllen;
    348   data->d_off = 0;
    349   data->d_align = 1;
    350   data->d_version = EV_CURRENT;
    351 
    352   /* Now run through the tree and add all the string while also updating
    353      the offset members of the elfstrent records.  */
    354   endp = (char *) data->d_buf + nulllen;
    355   copylen = nulllen;
    356   copystrings (st->root, &endp, &copylen);
    357   assert (copylen == st->total * st->width + nulllen);
    358 }
    359 
    360 
    361 size_t
    362 ebl_gstrtaboffset (struct Ebl_GStrent *se)
    363 {
    364   return se->offset;
    365 }
    366