LCOV - code coverage report
Current view: top level - libdwelf - dwelf_strtab.c (source / functions) Hit Total Coverage
Test: elfutils-0.177 Lines: 124 124 100.0 %
Date: 2019-08-14 14:28:26 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13