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 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 *
  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
 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 *
 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
 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, 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 *
 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
 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
 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
 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 *
 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 }