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 <sys/param.h>
27
28 #include "libebl.h"
29 #include <system.h>
30
31 #ifndef MIN
32 # define MIN(a, b) ((a) < (b) ? (a) : (b))
33 #endif
34
35
36 struct Ebl_Strent
37 {
38 const char *string;
39 size_t len;
40 struct Ebl_Strent *next;
41 struct Ebl_Strent *left;
42 struct Ebl_Strent *right;
43 size_t offset;
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_Strtab
56 {
57 struct Ebl_Strent *root;
58 struct memoryblock *memory;
59 char *backp;
60 size_t left;
61 size_t total;
62 bool nullstr;
63
64 struct Ebl_Strent null;
65 };
66
67
68 /* Cache for the pagesize. We correct this value a bit so that `malloc'
69 is not allocating more than a page. */
70 static size_t ps;
71
72
73 struct Ebl_Strtab *
ebl_strtabinit(bool nullstr)74 ebl_strtabinit (bool nullstr)
75 {
76 struct Ebl_Strtab *ret;
77
78 if (ps == 0)
79 {
80 ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *);
81 assert (sizeof (struct memoryblock) < ps);
82 }
83
84 ret = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab));
85 if (ret != NULL)
86 {
87 ret->nullstr = nullstr;
88
89 if (nullstr)
90 {
91 ret->null.len = 1;
92 ret->null.string = "";
93 }
94 }
95
96 return ret;
97 }
98
99
100 static int
morememory(struct Ebl_Strtab * st,size_t len)101 morememory (struct Ebl_Strtab *st, size_t len)
102 {
103 struct memoryblock *newmem;
104
105 if (len < ps)
106 len = ps;
107 newmem = (struct memoryblock *) malloc (len);
108 if (newmem == NULL)
109 return 1;
110
111 newmem->next = st->memory;
112 st->memory = newmem;
113 st->backp = newmem->memory;
114 st->left = len - offsetof (struct memoryblock, memory);
115
116 return 0;
117 }
118
119
120 void
ebl_strtabfree(struct Ebl_Strtab * st)121 ebl_strtabfree (struct Ebl_Strtab *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 free (st);
133 }
134
135
136 static struct Ebl_Strent *
newstring(struct Ebl_Strtab * st,const char * str,size_t len)137 newstring (struct Ebl_Strtab *st, const char *str, size_t len)
138 {
139 struct Ebl_Strent *newstr;
140 size_t align;
141 int i;
142
143 /* Compute the amount of padding needed to make the structure aligned. */
144 align = ((__alignof__ (struct Ebl_Strent)
145 - (((uintptr_t) st->backp)
146 & (__alignof__ (struct Ebl_Strent) - 1)))
147 & (__alignof__ (struct Ebl_Strent) - 1));
148
149 /* Make sure there is enough room in the memory block. */
150 if (st->left < align + sizeof (struct Ebl_Strent) + len)
151 {
152 if (morememory (st, sizeof (struct Ebl_Strent) + len))
153 return NULL;
154
155 align = 0;
156 }
157
158 /* Create the reserved string. */
159 newstr = (struct Ebl_Strent *) (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] = '\0';
169 st->backp += align + sizeof (struct Ebl_Strent) + len;
170 st->left -= align + sizeof (struct Ebl_Strent) + len;
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_Strent **
searchstring(struct Ebl_Strent ** sep,struct Ebl_Strent * newstr)180 searchstring (struct Ebl_Strent **sep, struct Ebl_Strent *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 = memcmp ((*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_Strent *
ebl_strtabadd(struct Ebl_Strtab * st,const char * str,size_t len)206 ebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len)
207 {
208 struct Ebl_Strent *newstr;
209 struct Ebl_Strent **sep;
210
211 /* Compute the string length if the caller doesn't know it. */
212 if (len == 0)
213 len = strlen (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_Strent *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_Strent * nodep,char ** freep,size_t * offsetp)284 copystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp)
285 {
286 struct Ebl_Strent *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 = (char *) mempcpy (*freep, nodep->string, nodep->len);
294 *offsetp += nodep->len;
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_strtabfinalize(struct Ebl_Strtab * st,Elf_Data * data)309 ebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data)
310 {
311 size_t copylen;
312 char *endp;
313 size_t nulllen = st->nullstr ? 1 : 0;
314
315 /* Fill in the information. */
316 data->d_buf = malloc (st->total + nulllen);
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 *((char *) data->d_buf) = '\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 = (char *) data->d_buf + nulllen;
334 copylen = nulllen;
335 copystrings (st->root, &endp, ©len);
336 assert (copylen == st->total + nulllen);
337 }
338
339
340 size_t
ebl_strtaboffset(struct Ebl_Strent * se)341 ebl_strtaboffset (struct Ebl_Strent *se)
342 {
343 return se->offset;
344 }
345
346
347 const char *
ebl_string(struct Ebl_Strent * se)348 ebl_string (struct Ebl_Strent *se)
349 {
350 assert (se->string != NULL);
351
352 return se->string;
353 }
354