1 /* ELF string table handling.
2 Copyright (C) 2000, 2001, 2002 Red Hat, Inc.
3 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
4
5 This program is Open Source software; you can redistribute it and/or
6 modify it under the terms of the Open Software License version 1.0 as
7 published by the Open Source Initiative.
8
9 You should have received a copy of the Open Software License along
10 with this program; if not, you may obtain a copy of the Open Software
11 License version 1.0 from http://www.opensource.org/licenses/osl.php or
12 by writing the Open Source Initiative c/o Lawrence Rosen, Esq.,
13 3001 King Ranch Road, Ukiah, CA 95482. */
14
15 #ifdef HAVE_CONFIG_H
16 # include <config.h>
17 #endif
18
19 #include <assert.h>
20 #include <inttypes.h>
21 #include <libelf.h>
22 #include <stddef.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <unistd.h>
26 #include <wchar.h>
27 #include <sys/param.h>
28
29 #include "libebl.h"
30 #include <system.h>
31
32 #ifndef MIN
33 # define MIN(a, b) ((a) < (b) ? (a) : (b))
34 #endif
35
36
37 struct Ebl_WStrent
38 {
39 const wchar_t *string;
40 size_t len;
41 struct Ebl_WStrent *next;
42 struct Ebl_WStrent *left;
43 struct Ebl_WStrent *right;
44 size_t offset;
45 wchar_t reverse[0];
46 };
47
48
49 struct memoryblock
50 {
51 struct memoryblock *next;
52 char memory[0];
53 };
54
55
56 struct Ebl_WStrtab
57 {
58 struct Ebl_WStrent *root;
59 struct memoryblock *memory;
60 char *backp;
61 size_t left;
62 size_t total;
63 bool nullstr;
64
65 struct Ebl_WStrent null;
66 };
67
68
69 /* Cache for the pagesize. We correct this value a bit so that `malloc'
70 is not allocating more than a page. */
71 static size_t ps;
72
73
74 struct Ebl_WStrtab *
ebl_wstrtabinit(bool nullstr)75 ebl_wstrtabinit (bool nullstr)
76 {
77 struct Ebl_WStrtab *ret;
78
79 if (ps == 0)
80 {
81 ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
82 assert (sizeof (struct memoryblock) < ps);
83 }
84
85 ret = (struct Ebl_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab));
86 if (ret != NULL)
87 {
88 ret->nullstr = nullstr;
89 if (nullstr)
90 {
91 ret->null.len = 1;
92 ret->null.string = L"";
93 }
94 }
95 return ret;
96 }
97
98
99 static int
morememory(struct Ebl_WStrtab * st,size_t len)100 morememory (struct Ebl_WStrtab *st, size_t len)
101 {
102 struct memoryblock *newmem;
103
104 if (len < ps)
105 len = ps;
106 newmem = (struct memoryblock *) malloc (len);
107 if (newmem == NULL)
108 return 1;
109
110 newmem->next = st->memory;
111 st->memory = newmem;
112 st->backp = newmem->memory;
113 st->left = len - offsetof (struct memoryblock, memory);
114
115 return 0;
116 }
117
118
119 void
ebl_wstrtabfree(struct Ebl_WStrtab * st)120 ebl_wstrtabfree (struct Ebl_WStrtab *st)
121 {
122 struct memoryblock *mb = st->memory;
123
124 while (mb != NULL)
125 {
126 void *old = mb;
127 mb = mb->next;
128 free (old);
129 }
130
131 free (st);
132 }
133
134
135 static struct Ebl_WStrent *
newstring(struct Ebl_WStrtab * st,const wchar_t * str,size_t len)136 newstring (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
137 {
138 struct Ebl_WStrent *newstr;
139 size_t align;
140 int i;
141
142 /* Compute the amount of padding needed to make the structure aligned. */
143 align = ((__alignof__ (struct Ebl_WStrent)
144 - (((uintptr_t) st->backp)
145 & (__alignof__ (struct Ebl_WStrent) - 1)))
146 & (__alignof__ (struct Ebl_WStrent) - 1));
147
148 /* Make sure there is enough room in the memory block. */
149 if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))
150 {
151 if (morememory (st,
152 sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t)))
153 return NULL;
154
155 align = 0;
156 }
157
158 /* Create the reserved string. */
159 newstr = (struct Ebl_WStrent *) (st->backp + align);
160 newstr->string = str;
161 newstr->len = len;
162 newstr->next = NULL;
163 newstr->left = NULL;
164 newstr->right = NULL;
165 newstr->offset = 0;
166 for (i = len - 2; i >= 0; --i)
167 newstr->reverse[i] = str[len - 2 - i];
168 newstr->reverse[len - 1] = L'\0';
169 st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
170 st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t);
171
172 return newstr;
173 }
174
175
176 /* XXX This function should definitely be rewritten to use a balancing
177 tree algorith (AVL, red-black trees). For now a simple, correct
178 implementation is enough. */
179 static struct Ebl_WStrent **
searchstring(struct Ebl_WStrent ** sep,struct Ebl_WStrent * newstr)180 searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *newstr)
181 {
182 int cmpres;
183
184 /* More strings? */
185 if (*sep == NULL)
186 {
187 *sep = newstr;
188 return sep;
189 }
190
191 /* Compare the strings. */
192 cmpres = wmemcmp ((*sep)->reverse, newstr->reverse,
193 MIN ((*sep)->len, newstr->len) - 1);
194 if (cmpres == 0)
195 /* We found a matching string. */
196 return sep;
197 else if (cmpres > 0)
198 return searchstring (&(*sep)->left, newstr);
199 else
200 return searchstring (&(*sep)->right, newstr);
201 }
202
203
204 /* Add new string. The actual string is assumed to be permanent. */
205 struct Ebl_WStrent *
ebl_wstrtabadd(struct Ebl_WStrtab * st,const wchar_t * str,size_t len)206 ebl_wstrtabadd (struct Ebl_WStrtab *st, const wchar_t *str, size_t len)
207 {
208 struct Ebl_WStrent *newstr;
209 struct Ebl_WStrent **sep;
210
211 /* Compute the string length if the caller doesn't know it. */
212 if (len == 0)
213 len = wcslen (str) + 1;
214
215 /* Make sure all "" strings get offset 0 but only if the table was
216 created with a special null entry in mind. */
217 if (len == 1 && st->null.string != NULL)
218 return &st->null;
219
220 /* Allocate memory for the new string and its associated information. */
221 newstr = newstring (st, str, len);
222 if (newstr == NULL)
223 return NULL;
224
225 /* Search in the array for the place to insert the string. If there
226 is no string with matching prefix and no string with matching
227 leading substring, create a new entry. */
228 sep = searchstring (&st->root, newstr);
229 if (*sep != newstr)
230 {
231 /* This is not the same entry. This means we have a prefix match. */
232 if ((*sep)->len > newstr->len)
233 {
234 struct Ebl_WStrent *subs;
235
236 /* Check whether we already know this string. */
237 for (subs = (*sep)->next; subs != NULL; subs = subs->next)
238 if (subs->len == newstr->len)
239 {
240 /* We have an exact match with a substring. Free the memory
241 we allocated. */
242 st->left += st->backp - (char *) newstr;
243 st->backp = (char *) newstr;
244
245 return subs;
246 }
247
248 /* We have a new substring. This means we don't need the reverse
249 string of this entry anymore. */
250 st->backp -= newstr->len;
251 st->left += newstr->len;
252
253 newstr->next = (*sep)->next;
254 (*sep)->next = newstr;
255 }
256 else if ((*sep)->len != newstr->len)
257 {
258 /* When we get here it means that the string we are about to
259 add has a common prefix with a string we already have but
260 it is longer. In this case we have to put it first. */
261 st->total += newstr->len - (*sep)->len;
262 newstr->next = *sep;
263 newstr->left = (*sep)->left;
264 newstr->right = (*sep)->right;
265 *sep = newstr;
266 }
267 else
268 {
269 /* We have an exact match. Free the memory we allocated. */
270 st->left += st->backp - (char *) newstr;
271 st->backp = (char *) newstr;
272
273 newstr = *sep;
274 }
275 }
276 else
277 st->total += newstr->len;
278
279 return newstr;
280 }
281
282
283 static void
copystrings(struct Ebl_WStrent * nodep,wchar_t ** freep,size_t * offsetp)284 copystrings (struct Ebl_WStrent *nodep, wchar_t **freep, size_t *offsetp)
285 {
286 struct Ebl_WStrent *subs;
287
288 if (nodep->left != NULL)
289 copystrings (nodep->left, freep, offsetp);
290
291 /* Process the current node. */
292 nodep->offset = *offsetp;
293 *freep = wmempcpy (*freep, nodep->string, nodep->len);
294 *offsetp += nodep->len * sizeof (wchar_t);
295
296 for (subs = nodep->next; subs != NULL; subs = subs->next)
297 {
298 assert (subs->len < nodep->len);
299 subs->offset = nodep->offset + nodep->len - subs->len;
300 assert (subs->offset != 0 || subs->string[0] == '\0');
301 }
302
303 if (nodep->right != NULL)
304 copystrings (nodep->right, freep, offsetp);
305 }
306
307
308 void
ebl_wstrtabfinalize(struct Ebl_WStrtab * st,Elf_Data * data)309 ebl_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data)
310 {
311 size_t copylen;
312 wchar_t *endp;
313 size_t nulllen = st->nullstr ? 1 : 0;
314
315 /* Fill in the information. */
316 data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t));
317 if (data->d_buf == NULL)
318 abort ();
319
320 /* The first byte must always be zero if we created the table with a
321 null string. */
322 if (st->nullstr)
323 *((wchar_t *) data->d_buf) = L'\0';
324
325 data->d_type = ELF_T_BYTE;
326 data->d_size = st->total + nulllen;
327 data->d_off = 0;
328 data->d_align = 1;
329 data->d_version = EV_CURRENT;
330
331 /* Now run through the tree and add all the string while also updating
332 the offset members of the elfstrent records. */
333 endp = (wchar_t *) data->d_buf + nulllen;
334 copylen = sizeof (wchar_t) * nulllen;
335 copystrings (st->root, &endp, ©len);
336 assert (copylen == (st->total + nulllen) * sizeof (wchar_t));
337 }
338
339
340 size_t
ebl_wstrtaboffset(struct Ebl_WStrent * se)341 ebl_wstrtaboffset (struct Ebl_WStrent *se)
342 {
343 return se->offset;
344 }
345