Branch data Line data Source code
1 : : /* ELF string table handling.
2 : : Copyright (C) 2000, 2001, 2002 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 <wchar.h>
42 : : #include <sys/param.h>
43 : :
44 : : #include "libebl.h"
45 : : #include <system.h>
46 : :
47 : : #ifndef MIN
48 : : # define MIN(a, b) ((a) < (b) ? (a) : (b))
49 : : #endif
50 : :
51 : :
52 : : struct Ebl_WStrent
53 : : {
54 : : const wchar_t *string;
55 : : size_t len;
56 : : struct Ebl_WStrent *next;
57 : : struct Ebl_WStrent *left;
58 : : struct Ebl_WStrent *right;
59 : : size_t offset;
60 : : wchar_t reverse[0];
61 : : };
62 : :
63 : :
64 : : struct memoryblock
65 : : {
66 : : struct memoryblock *next;
67 : : char memory[0];
68 : : };
69 : :
70 : :
71 : : struct Ebl_WStrtab
72 : : {
73 : : struct Ebl_WStrent *root;
74 : : struct memoryblock *memory;
75 : : char *backp;
76 : : size_t left;
77 : : size_t total;
78 : : bool nullstr;
79 : :
80 : : struct Ebl_WStrent 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_WStrtab *
90 : 0 : ebl_wstrtabinit (bool nullstr)
91 : : {
92 : : struct Ebl_WStrtab *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_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab));
101 [ # # ]: 0 : if (ret != NULL)
102 : : {
103 : 0 : ret->nullstr = nullstr;
104 [ # # ]: 0 : if (nullstr)
105 : : {
106 : 0 : ret->null.len = 1;
107 : 0 : ret->null.string = L"";
108 : : }
109 : : }
110 : 0 : return ret;
111 : : }
112 : :
113 : :
114 : : static int
115 : 0 : morememory (struct Ebl_WStrtab *st, size_t len)
116 : : {
117 : : struct memoryblock *newmem;
118 : :
119 [ # # ]: 0 : if (len < ps)
120 : 0 : len = ps;
121 : 0 : newmem = (struct memoryblock *) malloc (len);
122 [ # # ]: 0 : if (newmem == NULL)
123 : : return 1;
124 : :
125 : 0 : newmem->next = st->memory;
126 : 0 : st->memory = newmem;
127 : 0 : st->backp = newmem->memory;
128 : 0 : st->left = len - offsetof (struct memoryblock, memory);
129 : :
130 : 0 : return 0;
131 : : }
132 : :
133 : :
134 : : void
135 : 0 : ebl_wstrtabfree (struct Ebl_WStrtab *st)
136 : : {
137 : 0 : struct memoryblock *mb = st->memory;
138 : :
139 [ # # ]: 0 : while (mb != NULL)
140 : : {
141 : 0 : void *old = mb;
142 : 0 : mb = mb->next;
143 : 0 : free (old);
144 : : }
145 : :
146 : 0 : free (st);
147 : 0 : }
148 : :
149 : :
150 : : static struct Ebl_WStrent *
151 : 0 : newstring (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
152 : : {
153 : : struct Ebl_WStrent *newstr;
154 : : size_t align;
155 : : int i;
156 : :
157 : : /* Compute the amount of padding needed to make the structure aligned. */
158 : 0 : align = ((__alignof__ (struct Ebl_WStrent)
159 : 0 : - (((uintptr_t) st->backp)
160 : : & (__alignof__ (struct Ebl_WStrent) - 1)))
161 : 0 : & (__alignof__ (struct Ebl_WStrent) - 1));
162 : :
163 : : /* Make sure there is enough room in the memory block. */
164 [ # # ]: 0 : if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))
165 : : {
166 [ # # ]: 0 : if (morememory (st,
167 : : sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t)))
168 : : return NULL;
169 : :
170 : : align = 0;
171 : : }
172 : :
173 : : /* Create the reserved string. */
174 : 0 : newstr = (struct Ebl_WStrent *) (st->backp + align);
175 : 0 : newstr->string = str;
176 : 0 : newstr->len = len;
177 : 0 : newstr->next = NULL;
178 : 0 : newstr->left = NULL;
179 : 0 : newstr->right = NULL;
180 : 0 : newstr->offset = 0;
181 [ # # ]: 0 : for (i = len - 2; i >= 0; --i)
182 : 0 : newstr->reverse[i] = str[len - 2 - i];
183 : 0 : newstr->reverse[len - 1] = L'\0';
184 : 0 : st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
185 : 0 : st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
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_WStrent **
195 : 0 : searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *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 = wmemcmp ((*sep)->reverse, newstr->reverse,
208 : 0 : MIN ((*sep)->len, newstr->len) - 1);
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_WStrent *
221 : 0 : ebl_wstrtabadd (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
222 : : {
223 : : struct Ebl_WStrent *newstr;
224 : : struct Ebl_WStrent **sep;
225 : :
226 : : /* Compute the string length if the caller doesn't know it. */
227 [ # # ]: 0 : if (len == 0)
228 : 0 : len = wcslen (str) + 1;
229 : :
230 : : /* Make sure all "" strings get offset 0 but only if the table was
231 : : created with a special null entry in mind. */
232 [ # # ][ # # ]: 0 : if (len == 1 && st->null.string != NULL)
233 : 0 : return &st->null;
234 : :
235 : : /* Allocate memory for the new string and its associated information. */
236 : 0 : newstr = newstring (st, str, len);
237 [ # # ]: 0 : if (newstr == NULL)
238 : : return NULL;
239 : :
240 : : /* Search in the array for the place to insert the string. If there
241 : : is no string with matching prefix and no string with matching
242 : : leading substring, create a new entry. */
243 : 0 : sep = searchstring (&st->root, newstr);
244 [ # # ]: 0 : if (*sep != newstr)
245 : : {
246 : : /* This is not the same entry. This means we have a prefix match. */
247 [ # # ]: 0 : if ((*sep)->len > newstr->len)
248 : : {
249 : : struct Ebl_WStrent *subs;
250 : :
251 : : /* Check whether we already know this string. */
252 [ # # ]: 0 : for (subs = (*sep)->next; subs != NULL; subs = subs->next)
253 [ # # ]: 0 : if (subs->len == newstr->len)
254 : : {
255 : : /* We have an exact match with a substring. Free the memory
256 : : we allocated. */
257 : 0 : st->left += st->backp - (char *) newstr;
258 : 0 : st->backp = (char *) newstr;
259 : :
260 : 0 : return subs;
261 : : }
262 : :
263 : : /* We have a new substring. This means we don't need the reverse
264 : : string of this entry anymore. */
265 : 0 : st->backp -= newstr->len;
266 : 0 : st->left += newstr->len;
267 : :
268 : 0 : newstr->next = (*sep)->next;
269 : 0 : (*sep)->next = newstr;
270 : : }
271 [ # # ]: 0 : else if ((*sep)->len != newstr->len)
272 : : {
273 : : /* When we get here it means that the string we are about to
274 : : add has a common prefix with a string we already have but
275 : : it is longer. In this case we have to put it first. */
276 : 0 : st->total += newstr->len - (*sep)->len;
277 : 0 : newstr->next = *sep;
278 : 0 : newstr->left = (*sep)->left;
279 : 0 : newstr->right = (*sep)->right;
280 : 0 : *sep = newstr;
281 : : }
282 : : else
283 : : {
284 : : /* We have an exact match. Free the memory we allocated. */
285 : 0 : st->left += st->backp - (char *) newstr;
286 : 0 : st->backp = (char *) newstr;
287 : :
288 : 0 : newstr = *sep;
289 : : }
290 : : }
291 : : else
292 : 0 : st->total += newstr->len;
293 : :
294 : 0 : return newstr;
295 : : }
296 : :
297 : :
298 : : static void
299 : 0 : copystrings (struct Ebl_WStrent *nodep, wchar_t **freep, size_t *offsetp)
300 : : {
301 : : struct Ebl_WStrent *subs;
302 : :
303 [ # # ]: 0 : if (nodep->left != NULL)
304 : 0 : copystrings (nodep->left, freep, offsetp);
305 : :
306 : : /* Process the current node. */
307 : 0 : nodep->offset = *offsetp;
308 : 0 : *freep = wmempcpy (*freep, nodep->string, nodep->len);
309 : 0 : *offsetp += nodep->len * sizeof (wchar_t);
310 : :
311 [ # # ]: 0 : for (subs = nodep->next; subs != NULL; subs = subs->next)
312 : : {
313 [ # # ]: 0 : assert (subs->len < nodep->len);
314 : 0 : subs->offset = nodep->offset + nodep->len - subs->len;
315 [ # # ][ # # ]: 0 : assert (subs->offset != 0 || subs->string[0] == '\0');
316 : : }
317 : :
318 [ # # ]: 0 : if (nodep->right != NULL)
319 : : copystrings (nodep->right, freep, offsetp);
320 : 0 : }
321 : :
322 : :
323 : : void
324 : 0 : ebl_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data)
325 : : {
326 : : size_t copylen;
327 : : wchar_t *endp;
328 : 0 : size_t nulllen = st->nullstr ? 1 : 0;
329 : :
330 : : /* Fill in the information. */
331 : 0 : data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t));
332 [ # # ]: 0 : if (data->d_buf == NULL)
333 : 0 : abort ();
334 : :
335 : : /* The first byte must always be zero if we created the table with a
336 : : null string. */
337 [ # # ]: 0 : if (st->nullstr)
338 : 0 : *((wchar_t *) data->d_buf) = L'\0';
339 : :
340 : 0 : data->d_type = ELF_T_BYTE;
341 : 0 : data->d_size = st->total + nulllen;
342 : 0 : data->d_off = 0;
343 : 0 : data->d_align = 1;
344 : 0 : data->d_version = EV_CURRENT;
345 : :
346 : : /* Now run through the tree and add all the string while also updating
347 : : the offset members of the elfstrent records. */
348 : 0 : endp = (wchar_t *) data->d_buf + nulllen;
349 : 0 : copylen = sizeof (wchar_t) * nulllen;
350 : 0 : copystrings (st->root, &endp, ©len);
351 [ # # ]: 0 : assert (copylen == (st->total + nulllen) * sizeof (wchar_t));
352 : 0 : }
353 : :
354 : :
355 : : size_t
356 : 0 : ebl_wstrtaboffset (struct Ebl_WStrent *se)
357 : : {
358 : 0 : return se->offset;
359 : : }
|
