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