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
 175 Elftc_String_Table *
 176 elftc_string_table_from_section(Elf_Scn *scn, int sizehint)
 177 {
 178         int len;
 179         Elf_Data *d;
 180         GElf_Shdr sh;
 181         const char *s, *end;
 182         Elftc_String_Table *st;
 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 *
 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         int copied, hashindex, offset, length, newsize;
 239
 240         /*
 241          * For the common case of a string table has not seen
 242          * a string deletion, we can just export the current
 243          * pool.
 244          */
 245         if ((st->st_len & ELFTC_STRING_TABLE_COMPACTION_FLAG) == 0) {
 246                 if (size)
 247                         *size = ELFTC_STRING_TABLE_LENGTH(st);
 248                 return (st->st_string_pool);
 249         }
 250
 251         /*
 252          * Otherwise, compact the string table in-place.
 253          */
 254         assert(*st->st_string_pool == '\0');
 255
 256         newsize = 1;
 257         end = st->st_string_pool + ELFTC_STRING_TABLE_LENGTH(st);
 258
 259         for (r = s = st->st_string_pool + 1;
 260              s < end;
 261              s += length, r += copied) {
 262
 263                 copied = 0;
 264                 length = strlen(s) + 1;
 265
 266                 ste = elftc_string_table_find_hash_entry(st, s,
 267                     &hashindex);
 268                 head = &st->st_buckets[hashindex];
 269
 270                 assert(ste != NULL);
 271
 272                 /* Ignore deleted strings. */
 273                 if (ste->ste_idx < 0) {
 274                         SLIST_REMOVE(head, ste, _Elftc_String_Table_Entry,
 275                             ste_next);
 276                         free(ste);
 277                         continue;
 278                 }
 279
 280                 /* Move 'live' strings up. */
 281                 offset = newsize;
 282                 newsize += length;
 283                 copied = length;
 284
 285                 if (r == s)     /* Nothing removed yet. */
 286                         continue;
 287
 288                 memmove(r, s, copied);
 289
 290                 /* Update the index for this entry. */
 291                 ste->ste_idx = offset;
 292         }
 293
 294         ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st);
 295         ELFTC_STRING_TABLE_UPDATE_LENGTH(st, newsize);
 296
 297         if (size)
 298                 *size = newsize;
 299
 300         return (st->st_string_pool);
 301 }
 302
 303 size_t
 304 elftc_string_table_insert(Elftc_String_Table *st, const char *string)
 305 {
 306         int hashindex, idx;
 307         struct _Elftc_String_Table_Entry *ste;
 308
 309         hashindex = 0;
 310
 311         ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
 312
 313         assert(hashindex >= 0 && hashindex < st->st_nbuckets);
 314
 315         if (ste == NULL) {
 316                 if ((ste = malloc(sizeof(*ste))) == NULL)
 317                         return (0);
 318                 if ((ste->ste_idx = elftc_string_table_add_to_pool(st,
 319                     string)) == 0) {
 320                         free(ste);
 321                         return (0);
 322                 }
 323
 324                 SLIST_INSERT_HEAD(&st->st_buckets[hashindex], ste, ste_next);
 325         }
 326
 327         idx = ste->ste_idx;
 328         if (idx < 0)            /* Undelete. */
 329                 ste->ste_idx = idx = (- idx);
 330
 331         return (idx);
 332 }
 333
 334 size_t
 335 elftc_string_table_lookup(Elftc_String_Table *st, const char *string)
 336 {
 337         int hashindex, idx;
 338         struct _Elftc_String_Table_Entry *ste;
 339
 340         ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
 341
 342         assert(hashindex >= 0 && hashindex < st->st_nbuckets);
 343
 344         if (ste == NULL || (idx = ste->ste_idx) < 0)
 345                 return (0);
 346
 347         return (idx);
 348 }
 349
 350 int
 351 elftc_string_table_remove(Elftc_String_Table *st, const char *string)
 352 {
 353         int idx;
 354         struct _Elftc_String_Table_Entry *ste;
 355
 356         ste = elftc_string_table_find_hash_entry(st, string, NULL);
 357
 358         if (ste == NULL || (idx = ste->ste_idx) < 0)
 359                 return (ELFTC_FAILURE);
 360
 361         assert(idx > 0 && idx < (int) ELFTC_STRING_TABLE_LENGTH(st));
 362
 363         ste->ste_idx = (- idx);
 364
 365         ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st);
 366
 367         return (ELFTC_SUCCESS);
 368 }
 369
 370 const char *
 371 elftc_string_table_to_string(Elftc_String_Table *st, size_t offset)
 372 {
 373         const char *s;
 374
 375         s = st->st_string_pool + offset;
 376
 377         /*
 378          * Check for:
 379          * - An offset value within pool bounds.
 380          * - A non-NUL byte at the specified offset.
 381          * - The end of the prior string at offset - 1.
 382          */
 383         if (offset == 0 || offset >= ELFTC_STRING_TABLE_LENGTH(st) ||
 384             *s == '\0' || *(s - 1) != '\0') {
 385                 errno = EINVAL;
 386                 return (NULL);
 387         }
 388
 389         return (s);
 390 }