LCOV - code coverage report
Current view: top level - libdwelf - dwelf_strtab.c (source / functions) Coverage Total Hit
Test: elfutils-0.193 Lines: 100.0 % 123 123
Test Date: 2025-08-30 14:31:09 Functions: 100.0 % 12 12
Legend: Lines:     hit not hit
Branches: + taken - not taken # not executed
Branches: 75.0 % 60 45

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

Generated by: LCOV version 2.0-1