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 : 514 : dwelf_strtab_init (bool nullstr)
86 : : {
87 [ + + ]: 514 : if (ps == 0)
88 : : {
89 : 464 : ps = sysconf (_SC_PAGESIZE);
90 [ - + ]: 464 : assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
91 : : }
92 : :
93 : 514 : Dwelf_Strtab *ret = calloc (1, sizeof (struct Dwelf_Strtab));
94 [ + - ]: 514 : if (ret != NULL)
95 : : {
96 : 514 : ret->nullstr = nullstr;
97 : :
98 [ + - ]: 514 : if (nullstr)
99 : : {
100 : 514 : ret->null.len = 1;
101 : 514 : ret->null.string = "";
102 : : }
103 : : }
104 : :
105 : 514 : return ret;
106 : : }
107 : :
108 : :
109 : : static int
110 : 7958 : morememory (Dwelf_Strtab *st, size_t len)
111 : : {
112 : 7958 : size_t overhead = offsetof (struct memoryblock, memory);
113 : 7958 : len += overhead + MALLOC_OVERHEAD;
114 : :
115 : : /* Allocate nearest multiple of pagesize >= len. */
116 : 7958 : len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
117 : :
118 : 7958 : struct memoryblock *newmem = malloc (len);
119 [ + - ]: 7958 : if (newmem == NULL)
120 : : return 1;
121 : :
122 : 7958 : newmem->next = st->memory;
123 : 7958 : st->memory = newmem;
124 : 7958 : st->backp = newmem->memory;
125 : 7958 : st->left = len - overhead;
126 : :
127 : 7958 : return 0;
128 : : }
129 : :
130 : :
131 : : void
132 : 514 : dwelf_strtab_free (Dwelf_Strtab *st)
133 : : {
134 : 514 : struct memoryblock *mb = st->memory;
135 : :
136 [ + + ]: 8472 : while (mb != NULL)
137 : : {
138 : 7958 : void *old = mb;
139 : 7958 : mb = mb->next;
140 : 7958 : free (old);
141 : : }
142 : :
143 : 514 : free (st);
144 : 514 : }
145 : :
146 : :
147 : : static Dwelf_Strent *
148 : 721102 : newstring (Dwelf_Strtab *st, const char *str, size_t len)
149 : : {
150 : : /* Compute the amount of padding needed to make the structure aligned. */
151 : 721102 : size_t align = ((__alignof__ (struct Dwelf_Strent)
152 : 721102 : - (((uintptr_t) st->backp)
153 : : & (__alignof__ (struct Dwelf_Strent) - 1)))
154 : 721102 : & (__alignof__ (struct Dwelf_Strent) - 1));
155 : :
156 : : /* Make sure there is enough room in the memory block. */
157 [ + + ]: 721102 : if (st->left < align + sizeof (struct Dwelf_Strent) + len)
158 : : {
159 [ + - ]: 7958 : if (morememory (st, sizeof (struct Dwelf_Strent) + len))
160 : : return NULL;
161 : :
162 : : align = 0;
163 : : }
164 : :
165 : : /* Create the reserved string. */
166 : 721102 : Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
167 : 721102 : newstr->string = str;
168 : 721102 : newstr->len = len;
169 : 721102 : newstr->next = NULL;
170 : 721102 : newstr->left = NULL;
171 : 721102 : newstr->right = NULL;
172 : 721102 : newstr->offset = 0;
173 [ + + ]: 6246750 : for (int i = len - 2; i >= 0; --i)
174 : 5525648 : newstr->reverse[i] = str[len - 2 - i];
175 : 721102 : newstr->reverse[len - 1] = '\0';
176 : 721102 : st->backp += align + sizeof (struct Dwelf_Strent) + len;
177 : 721102 : st->left -= align + sizeof (struct Dwelf_Strent) + len;
178 : :
179 : 721102 : 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 : 721102 : searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
188 : : {
189 : : /* More strings? */
190 [ + + ]: 12623471 : if (*sep == NULL)
191 : : {
192 : 459938 : *sep = newstr;
193 : 459938 : return sep;
194 : : }
195 : :
196 : : /* Compare the strings. */
197 : 12163533 : int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
198 : 12163533 : MIN ((*sep)->len, newstr->len) - 1);
199 [ + + ]: 12163533 : if (cmpres == 0)
200 : : /* We found a matching string. */
201 : : return sep;
202 [ + + ]: 11902369 : else if (cmpres > 0)
203 : 2238963 : return searchstring (&(*sep)->left, newstr);
204 : : else
205 : 9663406 : 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 : 721540 : 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 [ + + + - ]: 721540 : 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 : 721102 : Dwelf_Strent *newstr = newstring (st, str, len);
220 [ + - ]: 721102 : 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 : 721102 : Dwelf_Strent **sep = searchstring (&st->root, newstr);
227 [ + + ]: 721102 : if (*sep != newstr)
228 : : {
229 : : /* This is not the same entry. This means we have a prefix match. */
230 [ + + ]: 261164 : if ((*sep)->len > newstr->len)
231 : : {
232 : : /* Check whether we already know this string. */
233 [ + + ]: 661 : for (Dwelf_Strent *subs = (*sep)->next; subs != NULL;
234 : 14 : subs = subs->next)
235 [ + + ]: 30 : 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 : 631 : st->backp -= newstr->len;
248 : 631 : st->left += newstr->len;
249 : :
250 : 631 : newstr->next = (*sep)->next;
251 : 631 : (*sep)->next = newstr;
252 : : }
253 [ + + ]: 260517 : 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 : 40823 : st->total += newstr->len - (*sep)->len;
259 : 40823 : newstr->next = *sep;
260 : 40823 : newstr->left = (*sep)->left;
261 : 40823 : newstr->right = (*sep)->right;
262 : 40823 : *sep = newstr;
263 : : }
264 : : else
265 : : {
266 : : /* We have an exact match. Free the memory we allocated. */
267 : 219694 : st->left += st->backp - (char *) newstr;
268 : 219694 : st->backp = (char *) newstr;
269 : :
270 : 219694 : newstr = *sep;
271 : : }
272 : : }
273 : : else
274 : 459938 : st->total += newstr->len;
275 : :
276 : : return newstr;
277 : : }
278 : :
279 : : Dwelf_Strent *
280 : 325122 : dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
281 : : {
282 : 325122 : return strtab_add (st, str, strlen (str) + 1);
283 : : }
284 : :
285 : : Dwelf_Strent *
286 : 396418 : dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
287 : : {
288 : 396418 : return strtab_add (st, str, len);
289 : : }
290 : :
291 : : static void
292 : 93629 : copystrings (Dwelf_Strent *nodep, char **freep, size_t *offsetp)
293 : : {
294 [ + + ]: 459842 : if (nodep->left != NULL)
295 : 93127 : copystrings (nodep->left, freep, offsetp);
296 : :
297 : : /* Process the current node. */
298 : 459842 : nodep->offset = *offsetp;
299 : 459842 : *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
300 : 459842 : *offsetp += nodep->len;
301 : :
302 [ + + ]: 501288 : for (Dwelf_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
303 : : {
304 [ - + ]: 41446 : assert (subs->len < nodep->len);
305 : 41446 : subs->offset = nodep->offset + nodep->len - subs->len;
306 [ - + - - ]: 41446 : assert (subs->offset != 0 || subs->string[0] == '\0');
307 : : }
308 : :
309 [ + + ]: 459842 : if (nodep->right != NULL)
310 : : copystrings (nodep->right, freep, offsetp);
311 : 93629 : }
312 : :
313 : :
314 : : Elf_Data *
315 : 502 : dwelf_strtab_finalize (Dwelf_Strtab *st, Elf_Data *data)
316 : : {
317 : 502 : size_t nulllen = st->nullstr ? 1 : 0;
318 : :
319 : : /* Fill in the information. */
320 : 502 : data->d_buf = malloc (st->total + nulllen);
321 [ + - ]: 502 : 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 [ + - ]: 502 : if (st->nullstr)
327 : 502 : *((char *) data->d_buf) = '\0';
328 : :
329 : 502 : data->d_type = ELF_T_BYTE;
330 : 502 : data->d_size = st->total + nulllen;
331 : 502 : data->d_off = 0;
332 : 502 : data->d_align = 1;
333 : 502 : 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 : 502 : char *endp = (char *) data->d_buf + nulllen;
338 : 502 : size_t copylen = nulllen;
339 [ + - ]: 502 : if (st->root)
340 : 502 : copystrings (st->root, &endp, ©len);
341 [ - + ]: 502 : assert (copylen == st->total + nulllen);
342 : :
343 : : return data;
344 : : }
345 : :
346 : :
347 : : size_t
348 : 721632 : dwelf_strent_off (Dwelf_Strent *se)
349 : : {
350 : 721632 : return se->offset;
351 : : }
352 : :
353 : :
354 : : const char *
355 : 176010 : dwelf_strent_str (Dwelf_Strent *se)
356 : : {
357 : 176010 : return se->string;
358 : : }
|
