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