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 : : #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 : 217 : dwelf_strtab_init (bool nullstr)
87 : : {
88 [ + + ]: 217 : if (ps == 0)
89 : : {
90 : 192 : ps = sysconf (_SC_PAGESIZE);
91 [ - + ]: 192 : assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
92 : : }
93 : :
94 : 217 : Dwelf_Strtab *ret
95 : 217 : = (Dwelf_Strtab *) calloc (1, sizeof (struct Dwelf_Strtab));
96 [ + - ]: 217 : if (ret != NULL)
97 : : {
98 : 217 : ret->nullstr = nullstr;
99 : :
100 [ + - ]: 217 : if (nullstr)
101 : : {
102 : 217 : ret->null.len = 1;
103 : 217 : ret->null.string = "";
104 : : }
105 : : }
106 : :
107 : 217 : return ret;
108 : : }
109 : :
110 : :
111 : : static int
112 : 3928 : morememory (Dwelf_Strtab *st, size_t len)
113 : : {
114 : 3928 : size_t overhead = offsetof (struct memoryblock, memory);
115 : 3928 : len += overhead + MALLOC_OVERHEAD;
116 : :
117 : : /* Allocate nearest multiple of pagesize >= len. */
118 : 3928 : len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
119 : :
120 : 3928 : struct memoryblock *newmem = (struct memoryblock *) malloc (len);
121 [ + - ]: 3928 : if (newmem == NULL)
122 : : return 1;
123 : :
124 : 3928 : newmem->next = st->memory;
125 : 3928 : st->memory = newmem;
126 : 3928 : st->backp = newmem->memory;
127 : 3928 : st->left = len - overhead;
128 : :
129 : 3928 : return 0;
130 : : }
131 : :
132 : :
133 : : void
134 : 217 : dwelf_strtab_free (Dwelf_Strtab *st)
135 : : {
136 : 217 : struct memoryblock *mb = st->memory;
137 : :
138 [ + + ]: 4145 : while (mb != NULL)
139 : : {
140 : 3928 : void *old = mb;
141 : 3928 : mb = mb->next;
142 : 3928 : free (old);
143 : : }
144 : :
145 : 217 : free (st);
146 : 217 : }
147 : :
148 : :
149 : : static Dwelf_Strent *
150 : 359617 : newstring (Dwelf_Strtab *st, const char *str, size_t len)
151 : : {
152 : : /* Compute the amount of padding needed to make the structure aligned. */
153 : 359617 : size_t align = ((__alignof__ (struct Dwelf_Strent)
154 : 359617 : - (((uintptr_t) st->backp)
155 : : & (__alignof__ (struct Dwelf_Strent) - 1)))
156 : 359617 : & (__alignof__ (struct Dwelf_Strent) - 1));
157 : :
158 : : /* Make sure there is enough room in the memory block. */
159 [ + + ]: 359617 : if (st->left < align + sizeof (struct Dwelf_Strent) + len)
160 : : {
161 [ + - ]: 3928 : if (morememory (st, sizeof (struct Dwelf_Strent) + len))
162 : : return NULL;
163 : :
164 : : align = 0;
165 : : }
166 : :
167 : : /* Create the reserved string. */
168 : 359617 : Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
169 : 359617 : newstr->string = str;
170 : 359617 : newstr->len = len;
171 : 359617 : newstr->next = NULL;
172 : 359617 : newstr->left = NULL;
173 : 359617 : newstr->right = NULL;
174 : 359617 : newstr->offset = 0;
175 [ + + ]: 3105416 : for (int i = len - 2; i >= 0; --i)
176 : 2745799 : newstr->reverse[i] = str[len - 2 - i];
177 : 359617 : newstr->reverse[len - 1] = '\0';
178 : 359617 : st->backp += align + sizeof (struct Dwelf_Strent) + len;
179 : 359617 : st->left -= align + sizeof (struct Dwelf_Strent) + len;
180 : :
181 : 359617 : return newstr;
182 : : }
183 : :
184 : :
185 : : /* XXX This function should definitely be rewritten to use a balancing
186 : : tree algorithm (AVL, red-black trees). For now a simple, correct
187 : : implementation is enough. */
188 : : static Dwelf_Strent **
189 : 359617 : searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
190 : : {
191 : : /* More strings? */
192 [ + + ]: 6304646 : if (*sep == NULL)
193 : : {
194 : 228572 : *sep = newstr;
195 : 228572 : return sep;
196 : : }
197 : :
198 : : /* Compare the strings. */
199 : 6076074 : int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
200 : 6076074 : MIN ((*sep)->len, newstr->len) - 1);
201 [ + + ]: 6076074 : if (cmpres == 0)
202 : : /* We found a matching string. */
203 : : return sep;
204 [ + + ]: 5945029 : else if (cmpres > 0)
205 : 1115640 : return searchstring (&(*sep)->left, newstr);
206 : : else
207 : 4829389 : 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 : 359840 : 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 [ + + + - ]: 359840 : if (len == 1 && st->null.string != NULL)
218 : 223 : return &st->null;
219 : :
220 : : /* Allocate memory for the new string and its associated information. */
221 : 359617 : Dwelf_Strent *newstr = newstring (st, str, len);
222 [ + - ]: 359617 : 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 : 359617 : Dwelf_Strent **sep = searchstring (&st->root, newstr);
229 [ + + ]: 359617 : if (*sep != newstr)
230 : : {
231 : : /* This is not the same entry. This means we have a prefix match. */
232 [ + + ]: 131045 : 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 [ + + ]: 130762 : 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 : 20353 : st->total += newstr->len - (*sep)->len;
261 : 20353 : newstr->next = *sep;
262 : 20353 : newstr->left = (*sep)->left;
263 : 20353 : newstr->right = (*sep)->right;
264 : 20353 : *sep = newstr;
265 : : }
266 : : else
267 : : {
268 : : /* We have an exact match. Free the memory we allocated. */
269 : 110409 : st->left += st->backp - (char *) newstr;
270 : 110409 : st->backp = (char *) newstr;
271 : :
272 : 110409 : newstr = *sep;
273 : : }
274 : : }
275 : : else
276 : 228572 : st->total += newstr->len;
277 : :
278 : : return newstr;
279 : : }
280 : :
281 : : Dwelf_Strent *
282 : 161662 : dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
283 : : {
284 : 161662 : return strtab_add (st, str, strlen (str) + 1);
285 : : }
286 : :
287 : : Dwelf_Strent *
288 : 198178 : dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
289 : : {
290 : 198178 : return strtab_add (st, str, len);
291 : : }
292 : :
293 : : static void
294 : 46152 : copystrings (Dwelf_Strent *nodep, char **freep, size_t *offsetp)
295 : : {
296 [ + + ]: 228524 : if (nodep->left != NULL)
297 : 45941 : copystrings (nodep->left, freep, offsetp);
298 : :
299 : : /* Process the current node. */
300 : 228524 : nodep->offset = *offsetp;
301 : 228524 : *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
302 : 228524 : *offsetp += nodep->len;
303 : :
304 [ + + ]: 249150 : for (Dwelf_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
305 : : {
306 [ - + ]: 20626 : assert (subs->len < nodep->len);
307 : 20626 : subs->offset = nodep->offset + nodep->len - subs->len;
308 [ - + - - ]: 20626 : assert (subs->offset != 0 || subs->string[0] == '\0');
309 : : }
310 : :
311 [ + + ]: 228524 : if (nodep->right != NULL)
312 : : copystrings (nodep->right, freep, offsetp);
313 : 46152 : }
314 : :
315 : :
316 : : Elf_Data *
317 : 211 : dwelf_strtab_finalize (Dwelf_Strtab *st, Elf_Data *data)
318 : : {
319 : 211 : size_t nulllen = st->nullstr ? 1 : 0;
320 : :
321 : : /* Fill in the information. */
322 : 211 : data->d_buf = malloc (st->total + nulllen);
323 [ + - ]: 211 : 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 [ + - ]: 211 : if (st->nullstr)
329 : 211 : *((char *) data->d_buf) = '\0';
330 : :
331 : 211 : data->d_type = ELF_T_BYTE;
332 : 211 : data->d_size = st->total + nulllen;
333 : 211 : data->d_off = 0;
334 : 211 : data->d_align = 1;
335 : 211 : 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 : 211 : char *endp = (char *) data->d_buf + nulllen;
340 : 211 : size_t copylen = nulllen;
341 [ + - ]: 211 : if (st->root)
342 : 211 : copystrings (st->root, &endp, ©len);
343 [ - + ]: 211 : assert (copylen == st->total + nulllen);
344 : :
345 : : return data;
346 : : }
347 : :
348 : :
349 : : size_t
350 : 359864 : dwelf_strent_off (Dwelf_Strent *se)
351 : : {
352 : 359864 : return se->offset;
353 : : }
354 : :
355 : :
356 : : const char *
357 : 88005 : dwelf_strent_str (Dwelf_Strent *se)
358 : : {
359 : 88005 : return se->string;
360 : : }
|
