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