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