LCOV - code coverage report
Current view: top level - elfutils/libebl - eblgstrtab.c (source / functions) Hit Total Coverage
Test: lcov.out Lines: 0 128 0.0 %
Date: 2013-03-08 Functions: 0 9 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 74 0.0 %

           Branch data     Line data    Source code
       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@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                 :          0 : ebl_gstrtabinit (unsigned int width, bool nullstr)
      91                 :            : {
      92                 :            :   struct Ebl_GStrtab *ret;
      93                 :            : 
      94         [ #  # ]:          0 :   if (ps == 0)
      95                 :            :     {
      96                 :          0 :       ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
      97         [ #  # ]:          0 :       assert (sizeof (struct memoryblock) < ps);
      98                 :            :     }
      99                 :            : 
     100                 :          0 :   ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab));
     101         [ #  # ]:          0 :   if (ret != NULL)
     102                 :            :     {
     103                 :          0 :       ret->width = width;
     104                 :          0 :       ret->nullstr = nullstr;
     105                 :            : 
     106         [ #  # ]:          0 :       if (nullstr)
     107                 :            :         {
     108                 :          0 :           ret->null.len = 1;
     109                 :          0 :           ret->null.string = (char *) calloc (1, width);
     110                 :            :         }
     111                 :            :     }
     112                 :            : 
     113                 :          0 :   return ret;
     114                 :            : }
     115                 :            : 
     116                 :            : 
     117                 :            : static void
     118                 :          0 : morememory (struct Ebl_GStrtab *st, size_t len)
     119                 :            : {
     120                 :            :   struct memoryblock *newmem;
     121                 :            : 
     122         [ #  # ]:          0 :   if (len < ps)
     123                 :          0 :     len = ps;
     124                 :          0 :   newmem = (struct memoryblock *) malloc (len);
     125         [ #  # ]:          0 :   if (newmem == NULL)
     126                 :          0 :     abort ();
     127                 :            : 
     128                 :          0 :   newmem->next = st->memory;
     129                 :          0 :   st->memory = newmem;
     130                 :          0 :   st->backp = newmem->memory;
     131                 :          0 :   st->left = len - offsetof (struct memoryblock, memory);
     132                 :          0 : }
     133                 :            : 
     134                 :            : 
     135                 :            : void
     136                 :          0 : ebl_gstrtabfree (struct Ebl_GStrtab *st)
     137                 :            : {
     138                 :          0 :   struct memoryblock *mb = st->memory;
     139                 :            : 
     140         [ #  # ]:          0 :   while (mb != NULL)
     141                 :            :     {
     142                 :          0 :       void *old = mb;
     143                 :          0 :       mb = mb->next;
     144                 :          0 :       free (old);
     145                 :            :     }
     146                 :            : 
     147         [ #  # ]:          0 :   if (st->null.string != NULL)
     148                 :          0 :     free ((char *) st->null.string);
     149                 :            : 
     150                 :          0 :   free (st);
     151                 :          0 : }
     152                 :            : 
     153                 :            : 
     154                 :            : static struct Ebl_GStrent *
     155                 :          0 : 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                 :          0 :   size_t align = ((__alignof__ (struct Ebl_GStrent)
     159                 :          0 :                    - (((uintptr_t) st->backp)
     160                 :            :                       & (__alignof__ (struct Ebl_GStrent) - 1)))
     161                 :          0 :                   & (__alignof__ (struct Ebl_GStrent) - 1));
     162                 :            : 
     163                 :            :   /* Make sure there is enough room in the memory block.  */
     164         [ #  # ]:          0 :   if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width)
     165                 :            :     {
     166                 :          0 :       morememory (st, sizeof (struct Ebl_GStrent) + len * st->width);
     167                 :          0 :       align = 0;
     168                 :            :     }
     169                 :            : 
     170                 :            :   /* Create the reserved string.  */
     171                 :          0 :   struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align);
     172                 :          0 :   newstr->string = str;
     173                 :          0 :   newstr->len = len;
     174                 :          0 :   newstr->width = st->width;
     175                 :          0 :   newstr->next = NULL;
     176                 :          0 :   newstr->left = NULL;
     177                 :          0 :   newstr->right = NULL;
     178                 :          0 :   newstr->offset = 0;
     179         [ #  # ]:          0 :   for (int i = len - 2; i >= 0; --i)
     180         [ #  # ]:          0 :     for (int j = st->width - 1; j >= 0; --j)
     181                 :          0 :       newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j];
     182         [ #  # ]:          0 :   for (size_t j = 0; j < st->width; ++j)
     183                 :          0 :     newstr->reverse[(len - 1) * st->width + j] = '\0';
     184                 :          0 :   st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width;
     185                 :          0 :   st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width;
     186                 :            : 
     187                 :          0 :   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                 :          0 : searchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr)
     196                 :            : {
     197                 :            :   int cmpres;
     198                 :            : 
     199                 :            :   /* More strings?  */
     200         [ #  # ]:          0 :   if (*sep == NULL)
     201                 :            :     {
     202                 :          0 :       *sep = newstr;
     203                 :          0 :       return sep;
     204                 :            :     }
     205                 :            : 
     206                 :            :   /* Compare the strings.  */
     207                 :          0 :   cmpres = memcmp ((*sep)->reverse, newstr->reverse,
     208                 :          0 :                    (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width);
     209         [ #  # ]:          0 :   if (cmpres == 0)
     210                 :            :     /* We found a matching string.  */
     211                 :            :     return sep;
     212         [ #  # ]:          0 :   else if (cmpres > 0)
     213                 :          0 :     return searchstring (&(*sep)->left, newstr);
     214                 :            :   else
     215                 :          0 :     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                 :          0 : 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         [ #  # ]:          0 :   if (len == 0)
     228                 :            :     {
     229                 :            :       size_t j;
     230                 :            : 
     231                 :            :       do
     232         [ #  # ]:          0 :         for (j = 0; j < st->width; ++j)
     233         [ #  # ]:          0 :           if (str[len * st->width + j] != '\0')
     234                 :            :             break;
     235 [ #  # ][ #  # ]:          0 :       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 [ #  # ][ #  # ]:          0 :   if (len == 1 && st->null.string != NULL)
     241                 :          0 :     return &st->null;
     242                 :            : 
     243                 :            :   /* Allocate memory for the new string and its associated information.  */
     244                 :          0 :   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                 :          0 :   sep = searchstring (&st->root, newstr);
     250         [ #  # ]:          0 :   if (*sep != newstr)
     251                 :            :     {
     252                 :            :       /* This is not the same entry.  This means we have a prefix match.  */
     253         [ #  # ]:          0 :       if ((*sep)->len > newstr->len)
     254                 :            :         {
     255                 :            :           struct Ebl_GStrent *subs;
     256                 :            : 
     257                 :            :           /* Check whether we already know this string.  */
     258         [ #  # ]:          0 :           for (subs = (*sep)->next; subs != NULL; subs = subs->next)
     259         [ #  # ]:          0 :             if (subs->len == newstr->len)
     260                 :            :               {
     261                 :            :                 /* We have an exact match with a substring.  Free the memory
     262                 :            :                    we allocated.  */
     263                 :          0 :                 st->left += (st->backp - (char *) newstr) * st->width;
     264                 :          0 :                 st->backp = (char *) newstr;
     265                 :            : 
     266                 :          0 :                 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                 :          0 :           st->backp -= newstr->len;
     272                 :          0 :           st->left += newstr->len;
     273                 :            : 
     274                 :          0 :           newstr->next = (*sep)->next;
     275                 :          0 :           (*sep)->next = newstr;
     276                 :            :         }
     277         [ #  # ]:          0 :       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                 :          0 :           st->total += newstr->len - (*sep)->len;
     283                 :          0 :           newstr->next = *sep;
     284                 :          0 :           newstr->left = (*sep)->left;
     285                 :          0 :           newstr->right = (*sep)->right;
     286                 :          0 :           *sep = newstr;
     287                 :            :         }
     288                 :            :       else
     289                 :            :         {
     290                 :            :           /* We have an exact match.  Free the memory we allocated.  */
     291                 :          0 :           st->left += (st->backp - (char *) newstr) * st->width;
     292                 :          0 :           st->backp = (char *) newstr;
     293                 :            : 
     294                 :          0 :           newstr = *sep;
     295                 :            :         }
     296                 :            :     }
     297                 :            :   else
     298                 :          0 :     st->total += newstr->len;
     299                 :            : 
     300                 :          0 :   return newstr;
     301                 :            : }
     302                 :            : 
     303                 :            : 
     304                 :            : static void
     305                 :          0 : copystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp)
     306                 :            : {
     307                 :            :   struct Ebl_GStrent *subs;
     308                 :            : 
     309         [ #  # ]:          0 :   if (nodep->left != NULL)
     310                 :          0 :     copystrings (nodep->left, freep, offsetp);
     311                 :            : 
     312                 :            :   /* Process the current node.  */
     313                 :          0 :   nodep->offset = *offsetp;
     314                 :          0 :   *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width);
     315                 :          0 :   *offsetp += nodep->len * nodep->width;
     316                 :            : 
     317         [ #  # ]:          0 :   for (subs = nodep->next; subs != NULL; subs = subs->next)
     318                 :            :     {
     319         [ #  # ]:          0 :       assert (subs->len < nodep->len);
     320                 :          0 :       subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width;
     321 [ #  # ][ #  # ]:          0 :       assert (subs->offset != 0 || subs->string[0] == '\0');
     322                 :            :     }
     323                 :            : 
     324         [ #  # ]:          0 :   if (nodep->right != NULL)
     325                 :            :     copystrings (nodep->right, freep, offsetp);
     326                 :          0 : }
     327                 :            : 
     328                 :            : 
     329                 :            : void
     330                 :          0 : ebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data)
     331                 :            : {
     332                 :            :   size_t copylen;
     333                 :            :   char *endp;
     334         [ #  # ]:          0 :   size_t nulllen = st->nullstr ? st->width : 0;
     335                 :            : 
     336                 :            :   /* Fill in the information.  */
     337                 :          0 :   data->d_buf = malloc (st->total + nulllen);
     338         [ #  # ]:          0 :   if (data->d_buf == NULL)
     339                 :          0 :     abort ();
     340                 :            : 
     341                 :            :   /* The first byte must always be zero if we created the table with a
     342                 :            :      null string.  */
     343         [ #  # ]:          0 :   if (st->nullstr)
     344                 :          0 :     memset (data->d_buf, '\0', st->width);
     345                 :            : 
     346                 :          0 :   data->d_type = ELF_T_BYTE;
     347                 :          0 :   data->d_size = st->total + nulllen;
     348                 :          0 :   data->d_off = 0;
     349                 :          0 :   data->d_align = 1;
     350                 :          0 :   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                 :          0 :   endp = (char *) data->d_buf + nulllen;
     355                 :          0 :   copylen = nulllen;
     356                 :          0 :   copystrings (st->root, &endp, &copylen);
     357         [ #  # ]:          0 :   assert (copylen == st->total * st->width + nulllen);
     358                 :          0 : }
     359                 :            : 
     360                 :            : 
     361                 :            : size_t
     362                 :          0 : ebl_gstrtaboffset (struct Ebl_GStrent *se)
     363                 :            : {
     364                 :          0 :   return se->offset;
     365                 :            : }

Generated by: LCOV version 1.9