Branch data Line data Source code
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 *
90 : 0 : ebl_gstrtabinit (unsigned int width, bool nullstr)
91 : : {
92 : : struct Ebl_GStrtab *ret;
93 : :
94 [ # # ]: 0 : if (ps == 0)
95 : : {
96 : 0 : ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
97 [ # # ]: 0 : assert (sizeof (struct memoryblock) < ps);
98 : : }
99 : :
100 : 0 : ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab));
101 [ # # ]: 0 : if (ret != NULL)
102 : : {
103 : 0 : ret->width = width;
104 : 0 : ret->nullstr = nullstr;
105 : :
106 [ # # ]: 0 : if (nullstr)
107 : : {
108 : 0 : ret->null.len = 1;
109 : 0 : ret->null.string = (char *) calloc (1, width);
110 : : }
111 : : }
112 : :
113 : 0 : return ret;
114 : : }
115 : :
116 : :
117 : : static void
118 : 0 : morememory (struct Ebl_GStrtab *st, size_t len)
119 : : {
120 : : struct memoryblock *newmem;
121 : :
122 [ # # ]: 0 : if (len < ps)
123 : 0 : len = ps;
124 : 0 : newmem = (struct memoryblock *) malloc (len);
125 [ # # ]: 0 : if (newmem == NULL)
126 : 0 : abort ();
127 : :
128 : 0 : newmem->next = st->memory;
129 : 0 : st->memory = newmem;
130 : 0 : st->backp = newmem->memory;
131 : 0 : st->left = len - offsetof (struct memoryblock, memory);
132 : 0 : }
133 : :
134 : :
135 : : void
136 : 0 : ebl_gstrtabfree (struct Ebl_GStrtab *st)
137 : : {
138 : 0 : struct memoryblock *mb = st->memory;
139 : :
140 [ # # ]: 0 : while (mb != NULL)
141 : : {
142 : 0 : void *old = mb;
143 : 0 : mb = mb->next;
144 : 0 : free (old);
145 : : }
146 : :
147 [ # # ]: 0 : if (st->null.string != NULL)
148 : 0 : free ((char *) st->null.string);
149 : :
150 : 0 : free (st);
151 : 0 : }
152 : :
153 : :
154 : : static struct Ebl_GStrent *
155 : 0 : 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 : 0 : size_t align = ((__alignof__ (struct Ebl_GStrent)
159 : 0 : - (((uintptr_t) st->backp)
160 : : & (__alignof__ (struct Ebl_GStrent) - 1)))
161 : 0 : & (__alignof__ (struct Ebl_GStrent) - 1));
162 : :
163 : : /* Make sure there is enough room in the memory block. */
164 [ # # ]: 0 : if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width)
165 : : {
166 : 0 : morememory (st, sizeof (struct Ebl_GStrent) + len * st->width);
167 : 0 : align = 0;
168 : : }
169 : :
170 : : /* Create the reserved string. */
171 : 0 : struct Ebl_GStrent *newstr = (struct Ebl_GStrent *) (st->backp + align);
172 : 0 : newstr->string = str;
173 : 0 : newstr->len = len;
174 : 0 : newstr->width = st->width;
175 : 0 : newstr->next = NULL;
176 : 0 : newstr->left = NULL;
177 : 0 : newstr->right = NULL;
178 : 0 : newstr->offset = 0;
179 [ # # ]: 0 : for (int i = len - 2; i >= 0; --i)
180 [ # # ]: 0 : for (int j = st->width - 1; j >= 0; --j)
181 : 0 : newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j];
182 [ # # ]: 0 : for (size_t j = 0; j < st->width; ++j)
183 : 0 : newstr->reverse[(len - 1) * st->width + j] = '\0';
184 : 0 : st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width;
185 : 0 : st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width;
186 : :
187 : 0 : 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 **
195 : 0 : searchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr)
196 : : {
197 : : int cmpres;
198 : :
199 : : /* More strings? */
200 [ # # ]: 0 : if (*sep == NULL)
201 : : {
202 : 0 : *sep = newstr;
203 : 0 : return sep;
204 : : }
205 : :
206 : : /* Compare the strings. */
207 : 0 : cmpres = memcmp ((*sep)->reverse, newstr->reverse,
208 : 0 : (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width);
209 [ # # ]: 0 : if (cmpres == 0)
210 : : /* We found a matching string. */
211 : : return sep;
212 [ # # ]: 0 : else if (cmpres > 0)
213 : 0 : return searchstring (&(*sep)->left, newstr);
214 : : else
215 : 0 : return searchstring (&(*sep)->right, newstr);
216 : : }
217 : :
218 : :
219 : : /* Add new string. The actual string is assumed to be permanent. */
220 : : struct Ebl_GStrent *
221 : 0 : 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 [ # # ]: 0 : if (len == 0)
228 : : {
229 : : size_t j;
230 : :
231 : : do
232 [ # # ]: 0 : for (j = 0; j < st->width; ++j)
233 [ # # ]: 0 : if (str[len * st->width + j] != '\0')
234 : : break;
235 [ # # ][ # # ]: 0 : 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 [ # # ][ # # ]: 0 : if (len == 1 && st->null.string != NULL)
241 : 0 : return &st->null;
242 : :
243 : : /* Allocate memory for the new string and its associated information. */
244 : 0 : 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 : 0 : sep = searchstring (&st->root, newstr);
250 [ # # ]: 0 : if (*sep != newstr)
251 : : {
252 : : /* This is not the same entry. This means we have a prefix match. */
253 [ # # ]: 0 : if ((*sep)->len > newstr->len)
254 : : {
255 : : struct Ebl_GStrent *subs;
256 : :
257 : : /* Check whether we already know this string. */
258 [ # # ]: 0 : for (subs = (*sep)->next; subs != NULL; subs = subs->next)
259 [ # # ]: 0 : if (subs->len == newstr->len)
260 : : {
261 : : /* We have an exact match with a substring. Free the memory
262 : : we allocated. */
263 : 0 : st->left += (st->backp - (char *) newstr) * st->width;
264 : 0 : st->backp = (char *) newstr;
265 : :
266 : 0 : 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 : 0 : st->backp -= newstr->len;
272 : 0 : st->left += newstr->len;
273 : :
274 : 0 : newstr->next = (*sep)->next;
275 : 0 : (*sep)->next = newstr;
276 : : }
277 [ # # ]: 0 : 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 : 0 : st->total += newstr->len - (*sep)->len;
283 : 0 : newstr->next = *sep;
284 : 0 : newstr->left = (*sep)->left;
285 : 0 : newstr->right = (*sep)->right;
286 : 0 : *sep = newstr;
287 : : }
288 : : else
289 : : {
290 : : /* We have an exact match. Free the memory we allocated. */
291 : 0 : st->left += (st->backp - (char *) newstr) * st->width;
292 : 0 : st->backp = (char *) newstr;
293 : :
294 : 0 : newstr = *sep;
295 : : }
296 : : }
297 : : else
298 : 0 : st->total += newstr->len;
299 : :
300 : 0 : return newstr;
301 : : }
302 : :
303 : :
304 : : static void
305 : 0 : copystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp)
306 : : {
307 : : struct Ebl_GStrent *subs;
308 : :
309 [ # # ]: 0 : if (nodep->left != NULL)
310 : 0 : copystrings (nodep->left, freep, offsetp);
311 : :
312 : : /* Process the current node. */
313 : 0 : nodep->offset = *offsetp;
314 : 0 : *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width);
315 : 0 : *offsetp += nodep->len * nodep->width;
316 : :
317 [ # # ]: 0 : for (subs = nodep->next; subs != NULL; subs = subs->next)
318 : : {
319 [ # # ]: 0 : assert (subs->len < nodep->len);
320 : 0 : subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width;
321 [ # # ][ # # ]: 0 : assert (subs->offset != 0 || subs->string[0] == '\0');
322 : : }
323 : :
324 [ # # ]: 0 : if (nodep->right != NULL)
325 : : copystrings (nodep->right, freep, offsetp);
326 : 0 : }
327 : :
328 : :
329 : : void
330 : 0 : ebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data)
331 : : {
332 : : size_t copylen;
333 : : char *endp;
334 [ # # ]: 0 : size_t nulllen = st->nullstr ? st->width : 0;
335 : :
336 : : /* Fill in the information. */
337 : 0 : data->d_buf = malloc (st->total + nulllen);
338 [ # # ]: 0 : if (data->d_buf == NULL)
339 : 0 : abort ();
340 : :
341 : : /* The first byte must always be zero if we created the table with a
342 : : null string. */
343 [ # # ]: 0 : if (st->nullstr)
344 : 0 : memset (data->d_buf, '\0', st->width);
345 : :
346 : 0 : data->d_type = ELF_T_BYTE;
347 : 0 : data->d_size = st->total + nulllen;
348 : 0 : data->d_off = 0;
349 : 0 : data->d_align = 1;
350 : 0 : 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 : 0 : endp = (char *) data->d_buf + nulllen;
355 : 0 : copylen = nulllen;
356 : 0 : copystrings (st->root, &endp, ©len);
357 [ # # ]: 0 : assert (copylen == st->total * st->width + nulllen);
358 : 0 : }
359 : :
360 : :
361 : : size_t
362 : 0 : ebl_gstrtaboffset (struct Ebl_GStrent *se)
363 : : {
364 : 0 : return se->offset;
365 : : }
|
