contrib/elftoolchain/libelftc/elftc_string_table.c

   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 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
  46 struct _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
  66 struct _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
  75 static struct _Elftc_String_Table_Entry *
  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 + 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
 101 static int
 102 elftc_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
 128 Elftc_String_Table *
 129 elftc_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
 162 void
 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         return;
 175 }
 176
 177 Elftc_String_Table *
 178 elftc_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
 227 fail:
 228         if (st)
 229                 (void) elftc_string_table_destroy(st);
 230
 231         return (NULL);
 232 }
 233
 234 const char *
 235 elftc_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
 305 size_t
 306 elftc_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
 336 size_t
 337 elftc_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
 352 int
 353 elftc_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
 372 const char *
 373 elftc_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 }