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 } 394