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