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 = calloc (1, sizeof (struct Dwelf_Strtab));
95 if (ret != NULL)
96 {
97 ret->nullstr = nullstr;
98
99 if (nullstr)
100 {
101 ret->null.len = 1;
102 ret->null.string = "";
103 }
104 }
105
106 return ret;
107 }
108
109
110 static int
morememory(Dwelf_Strtab * st,size_t len)111 morememory (Dwelf_Strtab *st, size_t len)
112 {
113 size_t overhead = offsetof (struct memoryblock, memory);
114 len += overhead + MALLOC_OVERHEAD;
115
116 /* Allocate nearest multiple of pagesize >= len. */
117 len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
118
119 struct memoryblock *newmem = malloc (len);
120 if (newmem == NULL)
121 return 1;
122
123 newmem->next = st->memory;
124 st->memory = newmem;
125 st->backp = newmem->memory;
126 st->left = len - overhead;
127
128 return 0;
129 }
130
131
132 void
dwelf_strtab_free(Dwelf_Strtab * st)133 dwelf_strtab_free (Dwelf_Strtab *st)
134 {
135 struct memoryblock *mb = st->memory;
136
137 while (mb != NULL)
138 {
139 void *old = mb;
140 mb = mb->next;
141 free (old);
142 }
143
144 free (st);
145 }
146
147
148 static Dwelf_Strent *
newstring(Dwelf_Strtab * st,const char * str,size_t len)149 newstring (Dwelf_Strtab *st, const char *str, size_t len)
150 {
151 /* Compute the amount of padding needed to make the structure aligned. */
152 size_t align = ((__alignof__ (struct Dwelf_Strent)
153 - (((uintptr_t) st->backp)
154 & (__alignof__ (struct Dwelf_Strent) - 1)))
155 & (__alignof__ (struct Dwelf_Strent) - 1));
156
157 /* Make sure there is enough room in the memory block. */
158 if (st->left < align + sizeof (struct Dwelf_Strent) + len)
159 {
160 if (morememory (st, sizeof (struct Dwelf_Strent) + len))
161 return NULL;
162
163 align = 0;
164 }
165
166 /* Create the reserved string. */
167 Dwelf_Strent *newstr = (Dwelf_Strent *) (st->backp + align);
168 newstr->string = str;
169 newstr->len = len;
170 newstr->next = NULL;
171 newstr->left = NULL;
172 newstr->right = NULL;
173 newstr->offset = 0;
174 for (int i = len - 2; i >= 0; --i)
175 newstr->reverse[i] = str[len - 2 - i];
176 newstr->reverse[len - 1] = '\0';
177 st->backp += align + sizeof (struct Dwelf_Strent) + len;
178 st->left -= align + sizeof (struct Dwelf_Strent) + len;
179
180 return newstr;
181 }
182
183
184 /* XXX This function should definitely be rewritten to use a balancing
185 tree algorithm (AVL, red-black trees). For now a simple, correct
186 implementation is enough. */
187 static Dwelf_Strent **
searchstring(Dwelf_Strent ** sep,Dwelf_Strent * newstr)188 searchstring (Dwelf_Strent **sep, Dwelf_Strent *newstr)
189 {
190 /* More strings? */
191 if (*sep == NULL)
192 {
193 *sep = newstr;
194 return sep;
195 }
196
197 /* Compare the strings. */
198 int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
199 MIN ((*sep)->len, newstr->len) - 1);
200 if (cmpres == 0)
201 /* We found a matching string. */
202 return sep;
203 else if (cmpres > 0)
204 return searchstring (&(*sep)->left, newstr);
205 else
206 return searchstring (&(*sep)->right, newstr);
207 }
208
209
210 /* Add new string. The actual string is assumed to be permanent. */
211 static Dwelf_Strent *
strtab_add(Dwelf_Strtab * st,const char * str,size_t len)212 strtab_add (Dwelf_Strtab *st, const char *str, size_t len)
213 {
214 /* Make sure all "" strings get offset 0 but only if the table was
215 created with a special null entry in mind. */
216 if (len == 1 && st->null.string != NULL)
217 return &st->null;
218
219 /* Allocate memory for the new string and its associated information. */
220 Dwelf_Strent *newstr = newstring (st, str, len);
221 if (newstr == NULL)
222 return NULL;
223
224 /* Search in the array for the place to insert the string. If there
225 is no string with matching prefix and no string with matching
226 leading substring, create a new entry. */
227 Dwelf_Strent **sep = searchstring (&st->root, newstr);
228 if (*sep != newstr)
229 {
230 /* This is not the same entry. This means we have a prefix match. */
231 if ((*sep)->len > newstr->len)
232 {
233 /* Check whether we already know this string. */
234 for (Dwelf_Strent *subs = (*sep)->next; subs != NULL;
235 subs = subs->next)
236 if (subs->len == newstr->len)
237 {
238 /* We have an exact match with a substring. Free the memory
239 we allocated. */
240 st->left += st->backp - (char *) newstr;
241 st->backp = (char *) newstr;
242
243 return subs;
244 }
245
246 /* We have a new substring. This means we don't need the reverse
247 string of this entry anymore. */
248 st->backp -= newstr->len;
249 st->left += newstr->len;
250
251 newstr->next = (*sep)->next;
252 (*sep)->next = newstr;
253 }
254 else if ((*sep)->len != newstr->len)
255 {
256 /* When we get here it means that the string we are about to
257 add has a common prefix with a string we already have but
258 it is longer. In this case we have to put it first. */
259 st->total += newstr->len - (*sep)->len;
260 newstr->next = *sep;
261 newstr->left = (*sep)->left;
262 newstr->right = (*sep)->right;
263 *sep = newstr;
264 }
265 else
266 {
267 /* We have an exact match. Free the memory we allocated. */
268 st->left += st->backp - (char *) newstr;
269 st->backp = (char *) newstr;
270
271 newstr = *sep;
272 }
273 }
274 else
275 st->total += newstr->len;
276
277 return newstr;
278 }
279
280 Dwelf_Strent *
dwelf_strtab_add(Dwelf_Strtab * st,const char * str)281 dwelf_strtab_add (Dwelf_Strtab *st, const char *str)
282 {
283 return strtab_add (st, str, strlen (str) + 1);
284 }
285
286 Dwelf_Strent *
dwelf_strtab_add_len(Dwelf_Strtab * st,const char * str,size_t len)287 dwelf_strtab_add_len (Dwelf_Strtab *st, const char *str, size_t len)
288 {
289 return strtab_add (st, str, len);
290 }
291
292 static void
copystrings(Dwelf_Strent * nodep,char ** freep,size_t * offsetp)293 copystrings (Dwelf_Strent *nodep, char **freep, size_t *offsetp)
294 {
295 if (nodep->left != NULL)
296 copystrings (nodep->left, freep, offsetp);
297
298 /* Process the current node. */
299 nodep->offset = *offsetp;
300 *freep = (char *) mempcpy (*freep, nodep->string, nodep->len);
301 *offsetp += nodep->len;
302
303 for (Dwelf_Strent *subs = nodep->next; subs != NULL; subs = subs->next)
304 {
305 assert (subs->len < nodep->len);
306 subs->offset = nodep->offset + nodep->len - subs->len;
307 assert (subs->offset != 0 || subs->string[0] == '\0');
308 }
309
310 if (nodep->right != NULL)
311 copystrings (nodep->right, freep, offsetp);
312 }
313
314
315 Elf_Data *
dwelf_strtab_finalize(Dwelf_Strtab * st,Elf_Data * data)316 dwelf_strtab_finalize (Dwelf_Strtab *st, Elf_Data *data)
317 {
318 size_t nulllen = st->nullstr ? 1 : 0;
319
320 /* Fill in the information. */
321 data->d_buf = malloc (st->total + nulllen);
322 if (data->d_buf == NULL)
323 return NULL;
324
325 /* The first byte must always be zero if we created the table with a
326 null string. */
327 if (st->nullstr)
328 *((char *) data->d_buf) = '\0';
329
330 data->d_type = ELF_T_BYTE;
331 data->d_size = st->total + nulllen;
332 data->d_off = 0;
333 data->d_align = 1;
334 data->d_version = EV_CURRENT;
335
336 /* Now run through the tree and add all the string while also updating
337 the offset members of the elfstrent records. */
338 char *endp = (char *) data->d_buf + nulllen;
339 size_t copylen = nulllen;
340 if (st->root)
341 copystrings (st->root, &endp, ©len);
342 assert (copylen == st->total + nulllen);
343
344 return data;
345 }
346
347
348 size_t
dwelf_strent_off(Dwelf_Strent * se)349 dwelf_strent_off (Dwelf_Strent *se)
350 {
351 return se->offset;
352 }
353
354
355 const char *
dwelf_strent_str(Dwelf_Strent * se)356 dwelf_strent_str (Dwelf_Strent *se)
357 {
358 return se->string;
359 }
360