Branch data Line data Source code
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 *
91 : 44 : ebl_strtabinit (bool nullstr)
92 : : {
93 [ + + ]: 44 : if (ps == 0)
94 : : {
95 : 35 : ps = sysconf (_SC_PAGESIZE);
96 [ - + ]: 35 : assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
97 : : }
98 : :
99 : 44 : struct Ebl_Strtab *ret
100 : : = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab));
101 [ + - ]: 44 : if (ret != NULL)
102 : : {
103 : 44 : ret->nullstr = nullstr;
104 : :
105 [ + - ]: 44 : if (nullstr)
106 : : {
107 : 44 : ret->null.len = 1;
108 : 44 : ret->null.string = "";
109 : : }
110 : : }
111 : :
112 : 44 : return ret;
113 : : }
114 : :
115 : :
116 : : static int
117 : 3703 : morememory (struct Ebl_Strtab *st, size_t len)
118 : : {
119 : 3703 : size_t overhead = offsetof (struct memoryblock, memory);
120 : 3703 : len += overhead + MALLOC_OVERHEAD;
121 : :
122 : : /* Allocate nearest multiple of pagesize >= len. */
123 : 3703 : len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
124 : :
125 : 3703 : struct memoryblock *newmem = (struct memoryblock *) malloc (len);
126 [ + - ]: 3703 : if (newmem == NULL)
127 : : return 1;
128 : :
129 : 3703 : newmem->next = st->memory;
130 : 3703 : st->memory = newmem;
131 : 3703 : st->backp = newmem->memory;
132 : 3703 : st->left = len - overhead;
133 : :
134 : 3703 : return 0;
135 : : }
136 : :
137 : :
138 : : void
139 : 44 : ebl_strtabfree (struct Ebl_Strtab *st)
140 : : {
141 : 44 : struct memoryblock *mb = st->memory;
142 : :
143 [ + + ]: 3747 : while (mb != NULL)
144 : : {
145 : 3703 : void *old = mb;
146 : 3703 : mb = mb->next;
147 : 3703 : free (old);
148 : : }
149 : :
150 : 44 : free (st);
151 : 44 : }
152 : :
153 : :
154 : : static struct Ebl_Strent *
155 : 286539 : 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 : 286539 : size_t align = ((__alignof__ (struct Ebl_Strent)
159 : 286539 : - (((uintptr_t) st->backp)
160 : : & (__alignof__ (struct Ebl_Strent) - 1)))
161 : 286539 : & (__alignof__ (struct Ebl_Strent) - 1));
162 : :
163 : : /* Make sure there is enough room in the memory block. */
164 [ + + ]: 286539 : if (st->left < align + sizeof (struct Ebl_Strent) + len)
165 : : {
166 [ + - ]: 3703 : if (morememory (st, sizeof (struct Ebl_Strent) + len))
167 : : return NULL;
168 : :
169 : : align = 0;
170 : : }
171 : :
172 : : /* Create the reserved string. */
173 : 286539 : struct Ebl_Strent *newstr = (struct Ebl_Strent *) (st->backp + align);
174 : 286539 : newstr->string = str;
175 : 286539 : newstr->len = len;
176 : 286539 : newstr->next = NULL;
177 : 286539 : newstr->left = NULL;
178 : 286539 : newstr->right = NULL;
179 : 286539 : newstr->offset = 0;
180 [ + + ]: 2546071 : for (int i = len - 2; i >= 0; --i)
181 : 2259532 : newstr->reverse[i] = str[len - 2 - i];
182 : 286539 : newstr->reverse[len - 1] = '\0';
183 : 286539 : st->backp += align + sizeof (struct Ebl_Strent) + len;
184 : 286539 : st->left -= align + sizeof (struct Ebl_Strent) + len;
185 : :
186 : 286539 : 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 **
194 : 5923574 : searchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr)
195 : : {
196 : : /* More strings? */
197 [ + + ]: 5923574 : if (*sep == NULL)
198 : : {
199 : 222480 : *sep = newstr;
200 : 222480 : return sep;
201 : : }
202 : :
203 : : /* Compare the strings. */
204 : 5701094 : int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
205 : 5701094 : MIN ((*sep)->len, newstr->len) - 1);
206 [ + + ]: 5701094 : if (cmpres == 0)
207 : : /* We found a matching string. */
208 : : return sep;
209 [ + + ]: 5637035 : else if (cmpres > 0)
210 : 831769 : return searchstring (&(*sep)->left, newstr);
211 : : else
212 : 5091805 : return searchstring (&(*sep)->right, newstr);
213 : : }
214 : :
215 : :
216 : : /* Add new string. The actual string is assumed to be permanent. */
217 : : struct Ebl_Strent *
218 : 286567 : 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 [ + + ]: 286567 : if (len == 0)
222 : 88502 : 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 [ + + ][ + - ]: 286567 : if (len == 1 && st->null.string != NULL)
227 : 28 : return &st->null;
228 : :
229 : : /* Allocate memory for the new string and its associated information. */
230 : 286539 : struct Ebl_Strent *newstr = newstring (st, str, len);
231 [ + - ]: 286539 : 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 : 286539 : struct Ebl_Strent **sep = searchstring (&st->root, newstr);
238 [ + + ]: 286539 : if (*sep != newstr)
239 : : {
240 : : /* This is not the same entry. This means we have a prefix match. */
241 [ + + ]: 64059 : if ((*sep)->len > newstr->len)
242 : : {
243 : : /* Check whether we already know this string. */
244 [ + + ]: 8 : for (struct Ebl_Strent *subs = (*sep)->next; subs != NULL;
245 : 1 : subs = subs->next)
246 [ - + ]: 1 : if (subs->len == newstr->len)
247 : : {
248 : : /* We have an exact match with a substring. Free the memory
249 : : we allocated. */
250 : 0 : st->left += st->backp - (char *) newstr;
251 : 0 : st->backp = (char *) newstr;
252 : :
253 : 0 : 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 : 7 : st->backp -= newstr->len;
259 : 7 : st->left += newstr->len;
260 : :
261 : 7 : newstr->next = (*sep)->next;
262 : 7 : (*sep)->next = newstr;
263 : : }
264 [ + + ]: 64052 : 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 : 20053 : st->total += newstr->len - (*sep)->len;
270 : 20053 : newstr->next = *sep;
271 : 20053 : newstr->left = (*sep)->left;
272 : 20053 : newstr->right = (*sep)->right;
273 : 20053 : *sep = newstr;
274 : : }
275 : : else
276 : : {
277 : : /* We have an exact match. Free the memory we allocated. */
278 : 43999 : st->left += st->backp - (char *) newstr;
279 : 43999 : st->backp = (char *) newstr;
280 : :
281 : 43999 : newstr = *sep;
282 : : }
283 : : }
284 : : else
285 : 222480 : st->total += newstr->len;
286 : :
287 : 286567 : return newstr;
288 : : }
289 : :
290 : :
291 : : static void
292 : 43234 : copystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp)
293 : : {
294 [ + + ]: 222480 : if (nodep->left != NULL)
295 : 43194 : copystrings (nodep->left, freep, offsetp);
296 : :
297 : : /* Process the current node. */
298 : 222480 : nodep->offset = *offsetp;
299 : 222480 : *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
300 : 222480 : *offsetp += nodep->len;
301 : :
302 [ + + ]: 242540 : for (struct Ebl_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
303 : : {
304 [ - + ]: 20060 : assert (subs->len < nodep->len);
305 : 20060 : subs->offset = nodep->offset + nodep->len - subs->len;
306 [ - + ][ # # ]: 20060 : assert (subs->offset != 0 || subs->string[0] == '\0');
307 : : }
308 : :
309 [ + + ]: 222480 : if (nodep->right != NULL)
310 : : copystrings (nodep->right, freep, offsetp);
311 : 43234 : }
312 : :
313 : :
314 : : void
315 : 40 : ebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data)
316 : : {
317 : 40 : size_t nulllen = st->nullstr ? 1 : 0;
318 : :
319 : : /* Fill in the information. */
320 : 40 : data->d_buf = malloc (st->total + nulllen);
321 [ - + ]: 40 : if (data->d_buf == NULL)
322 : 0 : abort ();
323 : :
324 : : /* The first byte must always be zero if we created the table with a
325 : : null string. */
326 [ + - ]: 40 : if (st->nullstr)
327 : 40 : *((char *) data->d_buf) = '\0';
328 : :
329 : 40 : data->d_type = ELF_T_BYTE;
330 : 40 : data->d_size = st->total + nulllen;
331 : 40 : data->d_off = 0;
332 : 40 : data->d_align = 1;
333 : 40 : 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 : 40 : char *endp = (char *) data->d_buf + nulllen;
338 : 40 : size_t copylen = nulllen;
339 [ + - ]: 40 : if (st->root)
340 : 40 : copystrings (st->root, &endp, ©len);
341 [ - + ]: 40 : assert (copylen == st->total + nulllen);
342 : 40 : }
343 : :
344 : :
345 : : size_t
346 : 286567 : ebl_strtaboffset (struct Ebl_Strent *se)
347 : : {
348 : 286567 : return se->offset;
349 : : }
350 : :
351 : :
352 : : const char *
353 : 88005 : ebl_string (struct Ebl_Strent *se)
354 : : {
355 [ - + ]: 88005 : assert (se->string != NULL);
356 : :
357 : 88005 : return se->string;
358 : : }
|
