1 /*-
2 * Copyright (c) 2013, Joseph Koshy
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer
10 * in this position and unchanged.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #include <sys/param.h>
28 #include <sys/queue.h>
29
30 #include <assert.h>
31 #include <errno.h>
32 #include <gelf.h>
33 #include <stdlib.h>
34 #include <string.h>
35
36 #include "libelftc.h"
37 #include "_libelftc.h"
38
39 ELFTC_VCSID("$Id: elftc_string_table.c 3750 2019-06-28 01:12:10Z emaste $");
40
41 #define ELFTC_STRING_TABLE_DEFAULT_SIZE (4*1024)
42 #define ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE 16
43 #define ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH 8
44 #define ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT (4*1024)
45
46 struct _Elftc_String_Table_Entry {
47 ssize_t ste_idx;
48 SLIST_ENTRY(_Elftc_String_Table_Entry) ste_next;
49 };
50
51 #define ELFTC_STRING_TABLE_COMPACTION_FLAG 0x1
52 #define ELFTC_STRING_TABLE_LENGTH(st) ((st)->st_len >> 1)
53 #define ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st) do { \
54 (st)->st_len &= ~ELFTC_STRING_TABLE_COMPACTION_FLAG; \
55 } while (0)
56 #define ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st) do { \
57 (st)->st_len |= ELFTC_STRING_TABLE_COMPACTION_FLAG; \
58 } while (0)
59 #define ELFTC_STRING_TABLE_UPDATE_LENGTH(st, len) do { \
60 (st)->st_len = \
61 ((st)->st_len & \
62 ELFTC_STRING_TABLE_COMPACTION_FLAG) | \
63 ((len) << 1); \
64 } while (0)
65
66 struct _Elftc_String_Table {
67 size_t st_len; /* length and flags */
68 int st_nbuckets;
69 size_t st_string_pool_size;
70 char *st_string_pool;
71 SLIST_HEAD(_Elftc_String_Table_Bucket,
72 _Elftc_String_Table_Entry) st_buckets[];
73 };
74
75 static struct _Elftc_String_Table_Entry *
elftc_string_table_find_hash_entry(Elftc_String_Table * st,const char * string,int * rhashindex)76 elftc_string_table_find_hash_entry(Elftc_String_Table *st, const char *string,
77 int *rhashindex)
78 {
79 struct _Elftc_String_Table_Entry *ste;
80 int hashindex;
81 char *s;
82
83 hashindex = libelftc_hash_string(string) % st->st_nbuckets;
84
85 if (rhashindex)
86 *rhashindex = hashindex;
87
88 SLIST_FOREACH(ste, &st->st_buckets[hashindex], ste_next) {
89 s = st->st_string_pool + labs(ste->ste_idx);
90
91 assert(s > st->st_string_pool &&
92 s < st->st_string_pool + st->st_string_pool_size);
93
94 if (strcmp(s, string) == 0)
95 return (ste);
96 }
97
98 return (NULL);
99 }
100
101 static int
elftc_string_table_add_to_pool(Elftc_String_Table * st,const char * string)102 elftc_string_table_add_to_pool(Elftc_String_Table *st, const char *string)
103 {
104 char *newpool;
105 size_t len, newsize, stlen;
106
107 len = strlen(string) + 1; /* length, including the trailing NUL */
108 stlen = ELFTC_STRING_TABLE_LENGTH(st);
109
110 /* Resize the pool, if needed. */
111 if (stlen + len >= st->st_string_pool_size) {
112 newsize = roundup(st->st_string_pool_size +
113 ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT,
114 ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT);
115 if ((newpool = realloc(st->st_string_pool, newsize)) ==
116 NULL)
117 return (0);
118 st->st_string_pool = newpool;
119 st->st_string_pool_size = newsize;
120 }
121
122 memcpy(st->st_string_pool + stlen, string, len);
123 ELFTC_STRING_TABLE_UPDATE_LENGTH(st, stlen + len);
124
125 return (stlen);
126 }
127
128 Elftc_String_Table *
elftc_string_table_create(size_t sizehint)129 elftc_string_table_create(size_t sizehint)
130 {
131 struct _Elftc_String_Table *st;
132 int n, nbuckets, tablesize;
133
134 if (sizehint < ELFTC_STRING_TABLE_DEFAULT_SIZE)
135 sizehint = ELFTC_STRING_TABLE_DEFAULT_SIZE;
136
137 nbuckets = sizehint / (ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH *
138 ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE);
139
140 tablesize = sizeof(struct _Elftc_String_Table) +
141 nbuckets * sizeof(struct _Elftc_String_Table_Bucket);
142
143 if ((st = malloc(tablesize)) == NULL)
144 return (NULL);
145 if ((st->st_string_pool = malloc(sizehint)) == NULL) {
146 free(st);
147 return (NULL);
148 }
149
150 for (n = 0; n < nbuckets; n++)
151 SLIST_INIT(&st->st_buckets[n]);
152
153 st->st_len = 0;
154 st->st_nbuckets = nbuckets;
155 st->st_string_pool_size = sizehint;
156 *st->st_string_pool = '\0';
157 ELFTC_STRING_TABLE_UPDATE_LENGTH(st, 1);
158
159 return (st);
160 }
161
162 void
elftc_string_table_destroy(Elftc_String_Table * st)163 elftc_string_table_destroy(Elftc_String_Table *st)
164 {
165 int n;
166 struct _Elftc_String_Table_Entry *s, *t;
167
168 for (n = 0; n < st->st_nbuckets; n++)
169 SLIST_FOREACH_SAFE(s, &st->st_buckets[n], ste_next, t)
170 free(s);
171 free(st->st_string_pool);
172 free(st);
173 }
174
175 Elftc_String_Table *
elftc_string_table_from_section(Elf_Scn * scn,size_t sizehint)176 elftc_string_table_from_section(Elf_Scn *scn, size_t sizehint)
177 {
178 Elf_Data *d;
179 GElf_Shdr sh;
180 const char *s, *end;
181 Elftc_String_Table *st;
182 size_t len;
183
184 /* Verify the type of the section passed in. */
185 if (gelf_getshdr(scn, &sh) == NULL ||
186 sh.sh_type != SHT_STRTAB) {
187 errno = EINVAL;
188 return (NULL);
189 }
190
191 if ((d = elf_getdata(scn, NULL)) == NULL ||
192 d->d_size == 0) {
193 errno = EINVAL;
194 return (NULL);
195 }
196
197 if ((st = elftc_string_table_create(sizehint)) == NULL)
198 return (NULL);
199
200 s = d->d_buf;
201
202 /*
203 * Verify that the first byte of the data buffer is '\0'.
204 */
205 if (*s != '\0') {
206 errno = EINVAL;
207 goto fail;
208 }
209
210 end = s + d->d_size;
211
212 /*
213 * Skip the first '\0' and insert the strings in the buffer,
214 * in order.
215 */
216 for (s += 1; s < end; s += len) {
217 if (elftc_string_table_insert(st, s) == 0)
218 goto fail;
219
220 len = strlen(s) + 1; /* Include space for the trailing NUL. */
221 }
222
223 return (st);
224
225 fail:
226 if (st)
227 (void) elftc_string_table_destroy(st);
228
229 return (NULL);
230 }
231
232 const char *
elftc_string_table_image(Elftc_String_Table * st,size_t * size)233 elftc_string_table_image(Elftc_String_Table *st, size_t *size)
234 {
235 char *r, *s, *end;
236 struct _Elftc_String_Table_Entry *ste;
237 struct _Elftc_String_Table_Bucket *head;
238 size_t copied, offset, length, newsize;
239 int hashindex;
240
241 /*
242 * For the common case of a string table has not seen
243 * a string deletion, we can just export the current
244 * pool.
245 */
246 if ((st->st_len & ELFTC_STRING_TABLE_COMPACTION_FLAG) == 0) {
247 if (size)
248 *size = ELFTC_STRING_TABLE_LENGTH(st);
249 return (st->st_string_pool);
250 }
251
252 /*
253 * Otherwise, compact the string table in-place.
254 */
255 assert(*st->st_string_pool == '\0');
256
257 newsize = 1;
258 end = st->st_string_pool + ELFTC_STRING_TABLE_LENGTH(st);
259
260 for (r = s = st->st_string_pool + 1;
261 s < end;
262 s += length, r += copied) {
263
264 copied = 0;
265 length = strlen(s) + 1;
266
267 ste = elftc_string_table_find_hash_entry(st, s,
268 &hashindex);
269 head = &st->st_buckets[hashindex];
270
271 assert(ste != NULL);
272
273 /* Ignore deleted strings. */
274 if (ste->ste_idx < 0) {
275 SLIST_REMOVE(head, ste, _Elftc_String_Table_Entry,
276 ste_next);
277 free(ste);
278 continue;
279 }
280
281 /* Move 'live' strings up. */
282 offset = newsize;
283 newsize += length;
284 copied = length;
285
286 if (r == s) /* Nothing removed yet. */
287 continue;
288
289 memmove(r, s, copied);
290
291 /* Update the index for this entry. */
292 ste->ste_idx = offset;
293 }
294
295 ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st);
296 ELFTC_STRING_TABLE_UPDATE_LENGTH(st, newsize);
297
298 if (size)
299 *size = newsize;
300
301 return (st->st_string_pool);
302 }
303
304 size_t
elftc_string_table_insert(Elftc_String_Table * st,const char * string)305 elftc_string_table_insert(Elftc_String_Table *st, const char *string)
306 {
307 struct _Elftc_String_Table_Entry *ste;
308 ssize_t idx;
309 int hashindex;
310
311 hashindex = 0;
312
313 ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
314
315 assert(hashindex >= 0 && hashindex < st->st_nbuckets);
316
317 if (ste == NULL) {
318 if ((ste = malloc(sizeof(*ste))) == NULL)
319 return (0);
320 if ((ste->ste_idx = elftc_string_table_add_to_pool(st,
321 string)) == 0) {
322 free(ste);
323 return (0);
324 }
325
326 SLIST_INSERT_HEAD(&st->st_buckets[hashindex], ste, ste_next);
327 }
328
329 idx = ste->ste_idx;
330 if (idx < 0) /* Undelete. */
331 ste->ste_idx = idx = -idx;
332
333 return (idx);
334 }
335
336 size_t
elftc_string_table_lookup(Elftc_String_Table * st,const char * string)337 elftc_string_table_lookup(Elftc_String_Table *st, const char *string)
338 {
339 struct _Elftc_String_Table_Entry *ste;
340 ssize_t idx;
341 int hashindex;
342
343 ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
344
345 assert(hashindex >= 0 && hashindex < st->st_nbuckets);
346
347 if (ste == NULL || (idx = ste->ste_idx) < 0)
348 return (0);
349
350 return (idx);
351 }
352
353 int
elftc_string_table_remove(Elftc_String_Table * st,const char * string)354 elftc_string_table_remove(Elftc_String_Table *st, const char *string)
355 {
356 struct _Elftc_String_Table_Entry *ste;
357 ssize_t idx;
358
359 ste = elftc_string_table_find_hash_entry(st, string, NULL);
360
361 if (ste == NULL || (idx = ste->ste_idx) < 0)
362 return (ELFTC_FAILURE);
363
364 assert(idx > 0 && (size_t)idx < ELFTC_STRING_TABLE_LENGTH(st));
365
366 ste->ste_idx = -idx;
367
368 ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st);
369
370 return (ELFTC_SUCCESS);
371 }
372
373 const char *
elftc_string_table_to_string(Elftc_String_Table * st,size_t offset)374 elftc_string_table_to_string(Elftc_String_Table *st, size_t offset)
375 {
376 const char *s;
377
378 s = st->st_string_pool + offset;
379
380 /*
381 * Check for:
382 * - An offset value within pool bounds.
383 * - A non-NUL byte at the specified offset.
384 * - The end of the prior string at offset - 1.
385 */
386 if (offset == 0 || offset >= ELFTC_STRING_TABLE_LENGTH(st) ||
387 *s == '\0' || *(s - 1) != '\0') {
388 errno = EINVAL;
389 return (NULL);
390 }
391
392 return (s);
393 }
394