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 *
dwelf_strtab_init(bool nullstr)85 dwelf_strtab_init (bool nullstr)
86 {
87 if (ps == 0)
88 {
89 ps = sysconf (_SC_PAGESIZE);
90 assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
91 }
92
93 Dwelf_Strtab *ret = calloc (1, sizeof (struct Dwelf_Strtab));
94 if (ret != NULL)
95 {
96 ret->nullstr = nullstr;
97
98 if (nullstr)
99 {
100 ret->null.len = 1;
101 ret->null.string = "";
102 }
103 }
104
105 return ret;
106 }
107
108
109 static int
morememory(Dwelf_Strtab * st,size_t len)110 morememory (Dwelf_Strtab *st, size_t len)
111 {
112 size_t overhead = offsetof (struct memoryblock, memory);
113 len += overhead + MALLOC_OVERHEAD;
114
115 /* Allocate nearest multiple of pagesize >= len. */
116 len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
117
118 struct memoryblock *newmem = malloc (len);
119 if (newmem == NULL)
120 return 1;
121
122 newmem->next = st->memory;
123 st->memory = newmem;
124 st->backp = newmem->memory;
125 st->left = len - overhead;
126
127 return 0;
128 }
129
130
131 void
dwelf_strtab_free(Dwelf_Strtab * st)132 dwelf_strtab_free (Dwelf_Strtab *st)
133 {
134 struct memoryblock *mb = st->memory;
135
136 while (mb != NULL)
137 {
138 void *old = mb;
139 mb = mb->next;
140 free (old);
141 }
142
143 free (st);
144 }
145
146
147 static Dwelf_Strent *
newstring(Dwelf_Strtab * st,const char * str,size_t len)148 newstring (Dwelf_Strtab *st, const char *str, size_t len)
149 {
150 /* Compute the amount of padding needed to make the structure aligned. */
151 size_t align = ((__alignof__ (struct Dwelf_Strent)
152 - (((uintptr_t) st->backp)
153 & (__alignof__ (struct Dwelf_Strent) - 1)))
154 & (__alignof__ (struct Dwelf_Strent) - 1));
155
156 /* Make sure there is enough room in the memory block. */
157 if (st->left < align + sizeof (struct Dwelf_Strent) + len)
158 {
159 if (morememory (st, sizeof (struct Dwelf_Strent) + len))
160 return NULL;
161
162 align = 0;
163 }
164
165 /* Create the reserved string. */
166 Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
167 newstr->string = str;
168 newstr->len = len;
169 newstr->next = NULL;
170 newstr->left = NULL;
171 newstr->right = NULL;
172 newstr->offset = 0;
173 for (int i = len - 2; i >= 0; --i)
174 newstr->reverse[i] = str[len - 2 - i];
175 newstr->reverse[len - 1] = '\0';
176 st->backp += align + sizeof (struct Dwelf_Strent) + len;
177 st->left -= align + sizeof (struct Dwelf_Strent) + len;
178
179 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 **
searchstring(Dwelf_Strent ** sep,Dwelf_Strent * newstr)187 searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
188 {
189 /* More strings? */
190 if (*sep == NULL)
191 {
192 *sep = newstr;
193 return sep;
194 }
195
196 /* Compare the strings. */
197 int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
198 MIN ((*sep)->len, newstr->len) - 1);
199 if (cmpres == 0)
200 /* We found a matching string. */
201 return sep;
202 else if (cmpres > 0)
203 return searchstring (&(*sep)->left, newstr);
204 else
205 return searchstring (&(*sep)->right, newstr);
206 }
207
208
209 /* Add new string. The actual string is assumed to be permanent. */
210 static Dwelf_Strent *
strtab_add(Dwelf_Strtab * st,const char * str,size_t len)211 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 if (len == 1 && st->null.string != NULL)
216 return &st->null;
217
218 /* Allocate memory for the new string and its associated information. */
219 Dwelf_Strent *newstr = newstring (st, str, len);
220 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 Dwelf_Strent **sep = searchstring (&st->root, newstr);
227 if (*sep != newstr)
228 {
229 /* This is not the same entry. This means we have a prefix match. */
230 if ((*sep)->len > newstr->len)
231 {
232 /* Check whether we already know this string. */
233 for (Dwelf_Strent *subs = (*sep)->next; subs != NULL;
234 subs = subs->next)
235 if (subs->len == newstr->len)
236 {
237 /* We have an exact match with a substring. Free the memory
238 we allocated. */
239 st->left += st->backp - (char *) newstr;
240 st->backp = (char *) newstr;
241
242 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 st->backp -= newstr->len;
248 st->left += newstr->len;
249
250 newstr->next = (*sep)->next;
251 (*sep)->next = newstr;
252 }
253 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 st->total += newstr->len - (*sep)->len;
259 newstr->next = *sep;
260 newstr->left = (*sep)->left;
261 newstr->right = (*sep)->right;
262 *sep = newstr;
263 }
264 else
265 {
266 /* We have an exact match. Free the memory we allocated. */
267 st->left += st->backp - (char *) newstr;
268 st->backp = (char *) newstr;
269
270 newstr = *sep;
271 }
272 }
273 else
274 st->total += newstr->len;
275
276 return newstr;
277 }
278
279 Dwelf_Strent *
dwelf_strtab_add(Dwelf_Strtab * st,const char * str)280 dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
281 {
282 return strtab_add (st, str, strlen (str) + 1);
283 }
284
285 Dwelf_Strent *
dwelf_strtab_add_len(Dwelf_Strtab * st,const char * str,size_t len)286 dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
287 {
288 return strtab_add (st, str, len);
289 }
290
291 static void
copystrings(Dwelf_Strent * nodep,char ** freep,size_t * offsetp)292 copystrings (Dwelf_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 (Dwelf_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 Elf_Data *
dwelf_strtab_finalize(Dwelf_Strtab * st,Elf_Data * data)315 dwelf_strtab_finalize (Dwelf_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 return NULL;
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, ©len);
341 assert (copylen == st->total + nulllen);
342
343 return data;
344 }
345
346
347 size_t
dwelf_strent_off(Dwelf_Strent * se)348 dwelf_strent_off (Dwelf_Strent *se)
349 {
350 return se->offset;
351 }
352
353
354 const char *
dwelf_strent_str(Dwelf_Strent * se)355 dwelf_strent_str (Dwelf_Strent *se)
356 {
357 return se->string;
358 }
359