source: rtems-tools/rtemstoolkit/elftoolchain/libelftc/elftc_string_table.c @ 1f1a10f

5
Last change on this file since 1f1a10f was 1f1a10f, checked in by Chris Johns <chrisj@…>, on 05/23/18 at 08:39:54

elftoolchain: Add libelftc.
  • Property mode set to 100644
File size: 9.3 KB
Line 
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
39ELFTC_VCSID("$Id: elftc_string_table.c 2869 2013-01-06 13:29:18Z jkoshy $");
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
46struct _Elftc_String_Table_Entry {
47        int             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
66struct _Elftc_String_Table {
67        unsigned int            st_len; /* length and flags */
68        int             st_nbuckets;
69        int             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
75static struct _Elftc_String_Table_Entry *
76elftc_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 + abs(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
101static int
102elftc_string_table_add_to_pool(Elftc_String_Table *st, const char *string)
103{
104        char *newpool;
105        int 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        strcpy(st->st_string_pool + stlen, string);
123        ELFTC_STRING_TABLE_UPDATE_LENGTH(st, stlen + len);
124
125        return (stlen);
126}
127
128Elftc_String_Table *
129elftc_string_table_create(int sizehint)
130{
131        int n, nbuckets, tablesize;
132        struct _Elftc_String_Table *st;
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
162void
163elftc_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        return;
175}
176
177Elftc_String_Table *
178elftc_string_table_from_section(Elf_Scn *scn, int sizehint)
179{
180        int len;
181        Elf_Data *d;
182        GElf_Shdr sh;
183        const char *s, *end;
184        Elftc_String_Table *st;
185
186        /* Verify the type of the section passed in. */
187        if (gelf_getshdr(scn, &sh) == NULL ||
188            sh.sh_type != SHT_STRTAB) {
189                errno = EINVAL;
190                return (NULL);
191        }
192
193        if ((d = elf_getdata(scn, NULL)) == NULL ||
194            d->d_size == 0) {
195                errno = EINVAL;
196                return (NULL);
197        }
198
199        if ((st = elftc_string_table_create(sizehint)) == NULL)
200                return (NULL);
201
202        s = d->d_buf;
203
204        /*
205         * Verify that the first byte of the data buffer is '\0'.
206         */
207        if (*s != '\0') {
208                errno = EINVAL;
209                goto fail;
210        }
211
212        end = s + d->d_size;
213
214        /*
215         * Skip the first '\0' and insert the strings in the buffer,
216         * in order.
217         */
218        for (s += 1; s < end; s += len) {
219                if (elftc_string_table_insert(st, s) == 0)
220                        goto fail;
221
222                len = strlen(s) + 1; /* Include space for the trailing NUL. */
223        }
224
225        return (st);
226
227fail:
228        if (st)
229                (void) elftc_string_table_destroy(st);
230
231        return (NULL);
232}
233
234const char *
235elftc_string_table_image(Elftc_String_Table *st, size_t *size)
236{
237        char *r, *s, *end;
238        struct _Elftc_String_Table_Entry *ste;
239        struct _Elftc_String_Table_Bucket *head;
240        int copied, hashindex, offset, length, newsize;
241
242        /*
243         * For the common case of a string table has not seen
244         * a string deletion, we can just export the current
245         * pool.
246         */
247        if ((st->st_len & ELFTC_STRING_TABLE_COMPACTION_FLAG) == 0) {
248                if (size)
249                        *size = ELFTC_STRING_TABLE_LENGTH(st);
250                return (st->st_string_pool);
251        }
252
253        /*
254         * Otherwise, compact the string table in-place.
255         */
256        assert(*st->st_string_pool == '\0');
257
258        newsize = 1;
259        end = st->st_string_pool + ELFTC_STRING_TABLE_LENGTH(st);
260
261        for (r = s = st->st_string_pool + 1;
262             s < end;
263             s += length, r += copied) {
264
265                copied = 0;
266                length = strlen(s) + 1;
267
268                ste = elftc_string_table_find_hash_entry(st, s,
269                    &hashindex);
270                head = &st->st_buckets[hashindex];
271
272                assert(ste != NULL);
273
274                /* Ignore deleted strings. */
275                if (ste->ste_idx < 0) {
276                        SLIST_REMOVE(head, ste, _Elftc_String_Table_Entry,
277                            ste_next);
278                        free(ste);
279                        continue;
280                }
281
282                /* Move 'live' strings up. */
283                offset = newsize;
284                newsize += length;
285                copied = length;
286
287                if (r == s)     /* Nothing removed yet. */
288                        continue;
289
290                memmove(r, s, copied);
291
292                /* Update the index for this entry. */
293                ste->ste_idx = offset;
294        }
295
296        ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st);
297        ELFTC_STRING_TABLE_UPDATE_LENGTH(st, newsize);
298
299        if (size)
300                *size = newsize;
301
302        return (st->st_string_pool);
303}
304
305size_t
306elftc_string_table_insert(Elftc_String_Table *st, const char *string)
307{
308        int hashindex, idx;
309        struct _Elftc_String_Table_Entry *ste;
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
336size_t
337elftc_string_table_lookup(Elftc_String_Table *st, const char *string)
338{
339        int hashindex, idx;
340        struct _Elftc_String_Table_Entry *ste;
341
342        ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
343
344        assert(hashindex >= 0 && hashindex < st->st_nbuckets);
345
346        if (ste == NULL || (idx = ste->ste_idx) < 0)
347                return (0);
348
349        return (idx);
350}
351
352int
353elftc_string_table_remove(Elftc_String_Table *st, const char *string)
354{
355        int idx;
356        struct _Elftc_String_Table_Entry *ste;
357
358        ste = elftc_string_table_find_hash_entry(st, string, NULL);
359
360        if (ste == NULL || (idx = ste->ste_idx) < 0)
361                return (ELFTC_FAILURE);
362
363        assert(idx > 0 && idx < (int) ELFTC_STRING_TABLE_LENGTH(st));
364
365        ste->ste_idx = (- idx);
366
367        ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st);
368
369        return (ELFTC_SUCCESS);
370}
371
372const char *
373elftc_string_table_to_string(Elftc_String_Table *st, size_t offset)
374{
375        const char *s;
376
377        s = st->st_string_pool + offset;
378
379        /*
380         * Check for:
381         * - An offset value within pool bounds.
382         * - A non-NUL byte at the specified offset.
383         * - The end of the prior string at offset - 1.
384         */
385        if (offset == 0 || offset >= ELFTC_STRING_TABLE_LENGTH(st) ||
386            *s == '\0' || *(s - 1) != '\0') {
387                errno = EINVAL;
388                return (NULL);
389        }
390
391        return (s);
392}
Note: See TracBrowser for help on using the repository browser.