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