1 /* ELF string table handling. 2 Copyright (C) 2000, 2001, 2002, 2005 Red Hat, Inc. 3 This file is part of elfutils. 4 Written by Ulrich Drepper <drepper (at) redhat.com>, 2000. 5 6 This file is free software; you can redistribute it and/or modify 7 it under the terms of either 8 9 * the GNU Lesser General Public License as published by the Free 10 Software Foundation; either version 3 of the License, or (at 11 your option) any later version 12 13 or 14 15 * the GNU General Public License as published by the Free 16 Software Foundation; either version 2 of the License, or (at 17 your option) any later version 18 19 or both in parallel, as here. 20 21 elfutils is distributed in the hope that it will be useful, but 22 WITHOUT ANY WARRANTY; without even the implied warranty of 23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 24 General Public License for more details. 25 26 You should have received copies of the GNU General Public License and 27 the GNU Lesser General Public License along with this program. If 28 not, see <http://www.gnu.org/licenses/>. */ 29 30 #ifdef HAVE_CONFIG_H 31 # include <config.h> 32 #endif 33 34 #include <assert.h> 35 #include <inttypes.h> 36 #include <libelf.h> 37 #include <stddef.h> 38 #include <stdlib.h> 39 #include <string.h> 40 #include <unistd.h> 41 #include <sys/param.h> 42 43 #include "libebl.h" 44 #include <system.h> 45 46 #ifndef MIN 47 # define MIN(a, b) ((a) < (b) ? (a) : (b)) 48 #endif 49 50 51 struct Ebl_Strent 52 { 53 const char *string; 54 size_t len; 55 struct Ebl_Strent *next; 56 struct Ebl_Strent *left; 57 struct Ebl_Strent *right; 58 size_t offset; 59 char reverse[0]; 60 }; 61 62 63 struct memoryblock 64 { 65 struct memoryblock *next; 66 char memory[0]; 67 }; 68 69 70 struct Ebl_Strtab 71 { 72 struct Ebl_Strent *root; 73 struct memoryblock *memory; 74 char *backp; 75 size_t left; 76 size_t total; 77 bool nullstr; 78 79 struct Ebl_Strent null; 80 }; 81 82 83 /* Cache for the pagesize. */ 84 static size_t ps; 85 /* We correct this value a bit so that `malloc' is not allocating more 86 than a page. */ 87 #define MALLOC_OVERHEAD (2 * sizeof (void *)) 88 89 90 struct Ebl_Strtab * 91 ebl_strtabinit (bool nullstr) 92 { 93 if (ps == 0) 94 { 95 ps = sysconf (_SC_PAGESIZE); 96 assert (sizeof (struct memoryblock) < ps - MALLOC_OVERHEAD); 97 } 98 99 struct Ebl_Strtab *ret 100 = (struct Ebl_Strtab *) calloc (1, sizeof (struct Ebl_Strtab)); 101 if (ret != NULL) 102 { 103 ret->nullstr = nullstr; 104 105 if (nullstr) 106 { 107 ret->null.len = 1; 108 ret->null.string = ""; 109 } 110 } 111 112 return ret; 113 } 114 115 116 static int 117 morememory (struct Ebl_Strtab *st, size_t len) 118 { 119 size_t overhead = offsetof (struct memoryblock, memory); 120 len += overhead + MALLOC_OVERHEAD; 121 122 /* Allocate nearest multiple of pagesize >= len. */ 123 len = ((len / ps) + (len % ps != 0)) * ps - MALLOC_OVERHEAD; 124 125 struct memoryblock *newmem = (struct memoryblock *) malloc (len); 126 if (newmem == NULL) 127 return 1; 128 129 newmem->next = st->memory; 130 st->memory = newmem; 131 st->backp = newmem->memory; 132 st->left = len - overhead; 133 134 return 0; 135 } 136 137 138 void 139 ebl_strtabfree (struct Ebl_Strtab *st) 140 { 141 struct memoryblock *mb = st->memory; 142 143 while (mb != NULL) 144 { 145 void *old = mb; 146 mb = mb->next; 147 free (old); 148 } 149 150 free (st); 151 } 152 153 154 static struct Ebl_Strent * 155 newstring (struct Ebl_Strtab *st, const char *str, size_t len) 156 { 157 /* Compute the amount of padding needed to make the structure aligned. */ 158 size_t align = ((__alignof__ (struct Ebl_Strent) 159 - (((uintptr_t) st->backp) 160 & (__alignof__ (struct Ebl_Strent) - 1))) 161 & (__alignof__ (struct Ebl_Strent) - 1)); 162 163 /* Make sure there is enough room in the memory block. */ 164 if (st->left < align + sizeof (struct Ebl_Strent) + len) 165 { 166 if (morememory (st, sizeof (struct Ebl_Strent) + len)) 167 return NULL; 168 169 align = 0; 170 } 171 172 /* Create the reserved string. */ 173 struct Ebl_Strent *newstr = (struct Ebl_Strent *) (st->backp + align); 174 newstr->string = str; 175 newstr->len = len; 176 newstr->next = NULL; 177 newstr->left = NULL; 178 newstr->right = NULL; 179 newstr->offset = 0; 180 for (int i = len - 2; i >= 0; --i) 181 newstr->reverse[i] = str[len - 2 - i]; 182 newstr->reverse[len - 1] = '\0'; 183 st->backp += align + sizeof (struct Ebl_Strent) + len; 184 st->left -= align + sizeof (struct Ebl_Strent) + len; 185 186 return newstr; 187 } 188 189 190 /* XXX This function should definitely be rewritten to use a balancing 191 tree algorith (AVL, red-black trees). For now a simple, correct 192 implementation is enough. */ 193 static struct Ebl_Strent ** 194 searchstring (struct Ebl_Strent **sep, struct Ebl_Strent *newstr) 195 { 196 /* More strings? */ 197 if (*sep == NULL) 198 { 199 *sep = newstr; 200 return sep; 201 } 202 203 /* Compare the strings. */ 204 int cmpres = memcmp ((*sep)->reverse, newstr->reverse, 205 MIN ((*sep)->len, newstr->len) - 1); 206 if (cmpres == 0) 207 /* We found a matching string. */ 208 return sep; 209 else if (cmpres > 0) 210 return searchstring (&(*sep)->left, newstr); 211 else 212 return searchstring (&(*sep)->right, newstr); 213 } 214 215 216 /* Add new string. The actual string is assumed to be permanent. */ 217 struct Ebl_Strent * 218 ebl_strtabadd (struct Ebl_Strtab *st, const char *str, size_t len) 219 { 220 /* Compute the string length if the caller doesn't know it. */ 221 if (len == 0) 222 len = strlen (str) + 1; 223 224 /* Make sure all "" strings get offset 0 but only if the table was 225 created with a special null entry in mind. */ 226 if (len == 1 && st->null.string != NULL) 227 return &st->null; 228 229 /* Allocate memory for the new string and its associated information. */ 230 struct Ebl_Strent *newstr = newstring (st, str, len); 231 if (newstr == NULL) 232 return NULL; 233 234 /* Search in the array for the place to insert the string. If there 235 is no string with matching prefix and no string with matching 236 leading substring, create a new entry. */ 237 struct Ebl_Strent **sep = searchstring (&st->root, newstr); 238 if (*sep != newstr) 239 { 240 /* This is not the same entry. This means we have a prefix match. */ 241 if ((*sep)->len > newstr->len) 242 { 243 /* Check whether we already know this string. */ 244 for (struct Ebl_Strent *subs = (*sep)->next; subs != NULL; 245 subs = subs->next) 246 if (subs->len == newstr->len) 247 { 248 /* We have an exact match with a substring. Free the memory 249 we allocated. */ 250 st->left += st->backp - (char *) newstr; 251 st->backp = (char *) newstr; 252 253 return subs; 254 } 255 256 /* We have a new substring. This means we don't need the reverse 257 string of this entry anymore. */ 258 st->backp -= newstr->len; 259 st->left += newstr->len; 260 261 newstr->next = (*sep)->next; 262 (*sep)->next = newstr; 263 } 264 else if ((*sep)->len != newstr->len) 265 { 266 /* When we get here it means that the string we are about to 267 add has a common prefix with a string we already have but 268 it is longer. In this case we have to put it first. */ 269 st->total += newstr->len - (*sep)->len; 270 newstr->next = *sep; 271 newstr->left = (*sep)->left; 272 newstr->right = (*sep)->right; 273 *sep = newstr; 274 } 275 else 276 { 277 /* We have an exact match. Free the memory we allocated. */ 278 st->left += st->backp - (char *) newstr; 279 st->backp = (char *) newstr; 280 281 newstr = *sep; 282 } 283 } 284 else 285 st->total += newstr->len; 286 287 return newstr; 288 } 289 290 291 static void 292 copystrings (struct Ebl_Strent *nodep, char **freep, size_t *offsetp) 293 { 294 if (nodep->left != NULL) 295 copystrings (nodep->left, freep, offsetp); 296 297 /* Process the current node. */ 298 nodep->offset = *offsetp; 299 *freep = (char *) mempcpy (*freep, nodep->string, nodep->len); 300 *offsetp += nodep->len; 301 302 for (struct Ebl_Strent *subs = nodep->next; subs != NULL; subs = subs->next) 303 { 304 assert (subs->len < nodep->len); 305 subs->offset = nodep->offset + nodep->len - subs->len; 306 assert (subs->offset != 0 || subs->string[0] == '\0'); 307 } 308 309 if (nodep->right != NULL) 310 copystrings (nodep->right, freep, offsetp); 311 } 312 313 314 void 315 ebl_strtabfinalize (struct Ebl_Strtab *st, Elf_Data *data) 316 { 317 size_t nulllen = st->nullstr ? 1 : 0; 318 319 /* Fill in the information. */ 320 data->d_buf = malloc (st->total + nulllen); 321 if (data->d_buf == NULL) 322 abort (); 323 324 /* The first byte must always be zero if we created the table with a 325 null string. */ 326 if (st->nullstr) 327 *((char *) data->d_buf) = '\0'; 328 329 data->d_type = ELF_T_BYTE; 330 data->d_size = st->total + nulllen; 331 data->d_off = 0; 332 data->d_align = 1; 333 data->d_version = EV_CURRENT; 334 335 /* Now run through the tree and add all the string while also updating 336 the offset members of the elfstrent records. */ 337 char *endp = (char *) data->d_buf + nulllen; 338 size_t copylen = nulllen; 339 if (st->root) 340 copystrings (st->root, &endp, ©len); 341 assert (copylen == st->total + nulllen); 342 } 343 344 345 size_t 346 ebl_strtaboffset (struct Ebl_Strent *se) 347 { 348 return se->offset; 349 } 350 351 352 const char * 353 ebl_string (struct Ebl_Strent *se) 354 { 355 assert (se->string != NULL); 356 357 return se->string; 358 } 359
