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