1 /* ELF string table handling.
2 Copyright (C) 2000, 2001, 2002, 2005 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 #include <sys/param.h>
42
43 #include "libebl.h"
44 #include <system.h>
45
46 #ifndef MIN
47 # define MIN(a, b) ((a) < (b) ? (a) : (b))
48 #endif
49
50
51 struct Ebl_Strent
52 {
53 const char *string;
54 size_t len;
55 struct Ebl_Strent *next;
56 struct Ebl_Strent *left;
57 struct Ebl_Strent *right;
58 size_t offset;
59 char reverse[0];
60 };
61
62
63 struct memoryblock
64 {
65 struct memoryblock *next;
66 char memory[0];
67 };
68
69
70 struct Ebl_Strtab
71 {
72 struct Ebl_Strent *root;
73 struct memoryblock *memory;
74 char *backp;
75 size_t left;
76 size_t total;
77 bool nullstr;
78
79 struct Ebl_Strent null;
80 };
81
82
83 /* Cache for the pagesize. */
84 static size_t ps;
85 /* We correct this value a bit so that `malloc' is not allocating more
86 than a page. */
87 #define MALLOC_OVERHEAD (2 * sizeof (void *))
88
89
90 struct Ebl_Strtab *
ebl_strtabinit(bool nullstr)91 ebl_strtabinit (bool nullstr)
92 {
93 if (ps == 0)
94 {
95 ps = sysconf (_SC_PAGESIZE);
96 assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD);
97 }
98
99 struct Ebl_Strtab *ret
100 = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab));
101 if (ret != NULL)
102 {
103 ret->nullstr = nullstr;
104
105 if (nullstr)
106 {
107 ret->null.len = 1;
108 ret->null.string = "";
109 }
110 }
111
112 return ret;
113 }
114
115
116 static int
morememory(struct Ebl_Strtab * st,size_t len)117 morememory (struct Ebl_Strtab *st, size_t len)
118 {
119 size_t overhead = offsetof (struct memoryblock, memory);
120 len += overhead + MALLOC_OVERHEAD;
121
122 /* Allocate nearest multiple of pagesize >= len. */
123 len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD;
124
125 struct memoryblock *newmem = (struct memoryblock *) malloc (len);
126 if (newmem == NULL)
127 return 1;
128
129 newmem->next = st->memory;
130 st->memory = newmem;
131 st->backp = newmem->memory;
132 st->left = len - overhead;
133
134 return 0;
135 }
136
137
138 void
ebl_strtabfree(struct Ebl_Strtab * st)139 ebl_strtabfree (struct Ebl_Strtab *st)
140 {
141 struct memoryblock *mb = st->memory;
142
143 while (mb != NULL)
144 {
145 void *old = mb;
146 mb = mb->next;
147 free (old);
148 }
149
150 free (st);
151 }
152
153
154 static struct Ebl_Strent *
newstring(struct Ebl_Strtab * st,const char * str,size_t len)155 newstring (struct Ebl_Strtab *st, const char *str, size_t len)
156 {
157 /* Compute the amount of padding needed to make the structure aligned. */
158 size_t align = ((__alignof__ (struct Ebl_Strent)
159 - (((uintptr_t) st->backp)
160 & (__alignof__ (struct Ebl_Strent) - 1)))
161 & (__alignof__ (struct Ebl_Strent) - 1));
162
163 /* Make sure there is enough room in the memory block. */
164 if (st->left < align + sizeof (struct Ebl_Strent) + len)
165 {
166 if (morememory (st, sizeof (struct Ebl_Strent) + len))
167 return NULL;
168
169 align = 0;
170 }
171
172 /* Create the reserved string. */
173 struct Ebl_Strent *newstr = (struct Ebl_Strent *) (st->backp + align);
174 newstr->string = str;
175 newstr->len = len;
176 newstr->next = NULL;
177 newstr->left = NULL;
178 newstr->right = NULL;
179 newstr->offset = 0;
180 for (int i = len - 2; i >= 0; --i)
181 newstr->reverse[i] = str[len - 2 - i];
182 newstr->reverse[len - 1] = '\0';
183 st->backp += align + sizeof (struct Ebl_Strent) + len;
184 st->left -= align + sizeof (struct Ebl_Strent) + len;
185
186 return newstr;
187 }
188
189
190 /* XXX This function should definitely be rewritten to use a balancing
191 tree algorith (AVL, red-black trees). For now a simple, correct
192 implementation is enough. */
193 static struct Ebl_Strent **
searchstring(struct Ebl_Strent ** sep,struct Ebl_Strent * newstr)194 searchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr)
195 {
196 /* More strings? */
197 if (*sep == NULL)
198 {
199 *sep = newstr;
200 return sep;
201 }
202
203 /* Compare the strings. */
204 int cmpres = memcmp ((*sep)->reverse, newstr->reverse,
205 MIN ((*sep)->len, newstr->len) - 1);
206 if (cmpres == 0)
207 /* We found a matching string. */
208 return sep;
209 else if (cmpres > 0)
210 return searchstring (&(*sep)->left, newstr);
211 else
212 return searchstring (&(*sep)->right, newstr);
213 }
214
215
216 /* Add new string. The actual string is assumed to be permanent. */
217 struct Ebl_Strent *
ebl_strtabadd(struct Ebl_Strtab * st,const char * str,size_t len)218 ebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len)
219 {
220 /* Compute the string length if the caller doesn't know it. */
221 if (len == 0)
222 len = strlen (str) + 1;
223
224 /* Make sure all "" strings get offset 0 but only if the table was
225 created with a special null entry in mind. */
226 if (len == 1 && st->null.string != NULL)
227 return &st->null;
228
229 /* Allocate memory for the new string and its associated information. */
230 struct Ebl_Strent *newstr = newstring (st, str, len);
231 if (newstr == NULL)
232 return NULL;
233
234 /* Search in the array for the place to insert the string. If there
235 is no string with matching prefix and no string with matching
236 leading substring, create a new entry. */
237 struct Ebl_Strent **sep = searchstring (&st->root, newstr);
238 if (*sep != newstr)
239 {
240 /* This is not the same entry. This means we have a prefix match. */
241 if ((*sep)->len > newstr->len)
242 {
243 /* Check whether we already know this string. */
244 for (struct Ebl_Strent *subs = (*sep)->next; subs != NULL;
245 subs = subs->next)
246 if (subs->len == newstr->len)
247 {
248 /* We have an exact match with a substring. Free the memory
249 we allocated. */
250 st->left += st->backp - (char *) newstr;
251 st->backp = (char *) newstr;
252
253 return subs;
254 }
255
256 /* We have a new substring. This means we don't need the reverse
257 string of this entry anymore. */
258 st->backp -= newstr->len;
259 st->left += newstr->len;
260
261 newstr->next = (*sep)->next;
262 (*sep)->next = newstr;
263 }
264 else if ((*sep)->len != newstr->len)
265 {
266 /* When we get here it means that the string we are about to
267 add has a common prefix with a string we already have but
268 it is longer. In this case we have to put it first. */
269 st->total += newstr->len - (*sep)->len;
270 newstr->next = *sep;
271 newstr->left = (*sep)->left;
272 newstr->right = (*sep)->right;
273 *sep = newstr;
274 }
275 else
276 {
277 /* We have an exact match. Free the memory we allocated. */
278 st->left += st->backp - (char *) newstr;
279 st->backp = (char *) newstr;
280
281 newstr = *sep;
282 }
283 }
284 else
285 st->total += newstr->len;
286
287 return newstr;
288 }
289
290
291 static void
copystrings(struct Ebl_Strent * nodep,char ** freep,size_t * offsetp)292 copystrings (struct Ebl_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 (struct Ebl_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 void
ebl_strtabfinalize(struct Ebl_Strtab * st,Elf_Data * data)315 ebl_strtabfinalize (struct Ebl_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 abort ();
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
344
345 size_t
ebl_strtaboffset(struct Ebl_Strent * se)346 ebl_strtaboffset (struct Ebl_Strent *se)
347 {
348 return se->offset;
349 }
350
351
352 const char *
ebl_string(struct Ebl_Strent * se)353 ebl_string (struct Ebl_Strent *se)
354 {
355 assert (se->string != NULL);
356
357 return se->string;
358 }
359