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