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 *
ebl_wstrtabinit(bool nullstr)90 ebl_wstrtabinit (bool nullstr)
91 {
92 struct Ebl_WStrtab *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_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab));
101 if (ret != NULL)
102 {
103 ret->nullstr = nullstr;
104 if (nullstr)
105 {
106 ret->null.len = 1;
107 ret->null.string = L"";
108 }
109 }
110 return ret;
111 }
112
113
114 static int
morememory(struct Ebl_WStrtab * st,size_t len)115 morememory (struct Ebl_WStrtab *st, size_t len)
116 {
117 struct memoryblock *newmem;
118
119 if (len < ps)
120 len = ps;
121 newmem = (struct memoryblock *) malloc (len);
122 if (newmem == NULL)
123 return 1;
124
125 newmem->next = st->memory;
126 st->memory = newmem;
127 st->backp = newmem->memory;
128 st->left = len - offsetof (struct memoryblock, memory);
129
130 return 0;
131 }
132
133
134 void
ebl_wstrtabfree(struct Ebl_WStrtab * st)135 ebl_wstrtabfree (struct Ebl_WStrtab *st)
136 {
137 struct memoryblock *mb = st->memory;
138
139 while (mb != NULL)
140 {
141 void *old = mb;
142 mb = mb->next;
143 free (old);
144 }
145
146 free (st);
147 }
148
149
150 static struct Ebl_WStrent *
newstring(struct Ebl_WStrtab * st,const wchar_t * str,size_t len)151 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 align = ((__alignof__ (struct Ebl_WStrent)
159 - (((uintptr_t) st->backp)
160 & (__alignof__ (struct Ebl_WStrent) - 1)))
161 & (__alignof__ (struct Ebl_WStrent) - 1));
162
163 /* Make sure there is enough room in the memory block. */
164 if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))
165 {
166 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 newstr = (struct Ebl_WStrent *) (st->backp + align);
175 newstr->string = str;
176 newstr->len = len;
177 newstr->next = NULL;
178 newstr->left = NULL;
179 newstr->right = NULL;
180 newstr->offset = 0;
181 for (i = len - 2; i >= 0; --i)
182 newstr->reverse[i] = str[len - 2 - i];
183 newstr->reverse[len - 1] = L'\0';
184 st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
185 st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
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_WStrent **
searchstring(struct Ebl_WStrent ** sep,struct Ebl_WStrent * newstr)195 searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *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 = wmemcmp ((*sep)->reverse, newstr->reverse,
208 MIN ((*sep)->len, newstr->len) - 1);
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_WStrent *
ebl_wstrtabadd(struct Ebl_WStrtab * st,const wchar_t * str,size_t len)221 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 if (len == 0)
228 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 if (len == 1 && st->null.string != NULL)
233 return &st->null;
234
235 /* Allocate memory for the new string and its associated information. */
236 newstr = newstring (st, str, len);
237 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 sep = searchstring (&st->root, newstr);
244 if (*sep != newstr)
245 {
246 /* This is not the same entry. This means we have a prefix match. */
247 if ((*sep)->len > newstr->len)
248 {
249 struct Ebl_WStrent *subs;
250
251 /* Check whether we already know this string. */
252 for (subs = (*sep)->next; subs != NULL; subs = subs->next)
253 if (subs->len == newstr->len)
254 {
255 /* We have an exact match with a substring. Free the memory
256 we allocated. */
257 st->left += st->backp - (char *) newstr;
258 st->backp = (char *) newstr;
259
260 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 st->backp -= newstr->len;
266 st->left += newstr->len;
267
268 newstr->next = (*sep)->next;
269 (*sep)->next = newstr;
270 }
271 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 st->total += newstr->len - (*sep)->len;
277 newstr->next = *sep;
278 newstr->left = (*sep)->left;
279 newstr->right = (*sep)->right;
280 *sep = newstr;
281 }
282 else
283 {
284 /* We have an exact match. Free the memory we allocated. */
285 st->left += st->backp - (char *) newstr;
286 st->backp = (char *) newstr;
287
288 newstr = *sep;
289 }
290 }
291 else
292 st->total += newstr->len;
293
294 return newstr;
295 }
296
297
298 static void
copystrings(struct Ebl_WStrent * nodep,wchar_t ** freep,size_t * offsetp)299 copystrings (struct Ebl_WStrent *nodep, wchar_t **freep, size_t *offsetp)
300 {
301 struct Ebl_WStrent *subs;
302
303 if (nodep->left != NULL)
304 copystrings (nodep->left, freep, offsetp);
305
306 /* Process the current node. */
307 nodep->offset = *offsetp;
308 *freep = wmempcpy (*freep, nodep->string, nodep->len);
309 *offsetp += nodep->len * sizeof (wchar_t);
310
311 for (subs = nodep->next; subs != NULL; subs = subs->next)
312 {
313 assert (subs->len < nodep->len);
314 subs->offset = nodep->offset + nodep->len - subs->len;
315 assert (subs->offset != 0 || subs->string[0] == '\0');
316 }
317
318 if (nodep->right != NULL)
319 copystrings (nodep->right, freep, offsetp);
320 }
321
322
323 void
ebl_wstrtabfinalize(struct Ebl_WStrtab * st,Elf_Data * data)324 ebl_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data)
325 {
326 size_t copylen;
327 wchar_t *endp;
328 size_t nulllen = st->nullstr ? 1 : 0;
329
330 /* Fill in the information. */
331 data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t));
332 if (data->d_buf == NULL)
333 abort ();
334
335 /* The first byte must always be zero if we created the table with a
336 null string. */
337 if (st->nullstr)
338 *((wchar_t *) data->d_buf) = L'\0';
339
340 data->d_type = ELF_T_BYTE;
341 data->d_size = st->total + nulllen;
342 data->d_off = 0;
343 data->d_align = 1;
344 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 endp = (wchar_t *) data->d_buf + nulllen;
349 copylen = sizeof (wchar_t) * nulllen;
350 copystrings (st->root, &endp, ©len);
351 assert (copylen == (st->total + nulllen) * sizeof (wchar_t));
352 }
353
354
355 size_t
ebl_wstrtaboffset(struct Ebl_WStrent * se)356 ebl_wstrtaboffset (struct Ebl_WStrent *se)
357 {
358 return se->offset;
359 }
360