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