1 /* Generic 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 30 #ifndef MIN 31 # define MIN(a, b) ((a) < (b) ? (a) : (b)) 32 #endif 33 34 35 struct Ebl_GStrent 36 { 37 const char *string; 38 size_t len; 39 struct Ebl_GStrent *next; 40 struct Ebl_GStrent *left; 41 struct Ebl_GStrent *right; 42 size_t offset; 43 unsigned int width; 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_GStrtab 56 { 57 struct Ebl_GStrent *root; 58 struct memoryblock *memory; 59 char *backp; 60 size_t left; 61 size_t total; 62 unsigned int width; 63 bool nullstr; 64 65 struct Ebl_GStrent null; 66 }; 67 68 69 /* Cache for the pagesize. We correct this value a bit so that `malloc' 70 is not allocating more than a page. */ 71 static size_t ps; 72 73 74 struct Ebl_GStrtab * 75 ebl_gstrtabinit (unsigned int width, bool nullstr) 76 { 77 struct Ebl_GStrtab *ret; 78 79 if (ps == 0) 80 { 81 ps = sysconf (_SC_PAGESIZE) - 2 * sizeof (void *); 82 assert (sizeof (struct memoryblock) < ps); 83 } 84 85 ret = (struct Ebl_GStrtab *) calloc (1, sizeof (struct Ebl_GStrtab)); 86 if (ret != NULL) 87 { 88 ret->width = width; 89 ret->nullstr = nullstr; 90 91 if (nullstr) 92 { 93 ret->null.len = 1; 94 ret->null.string = (char *) calloc (1, width); 95 } 96 } 97 98 return ret; 99 } 100 101 102 static void 103 morememory (struct Ebl_GStrtab *st, size_t len) 104 { 105 struct memoryblock *newmem; 106 107 if (len < ps) 108 len = ps; 109 newmem = (struct memoryblock *) malloc (len); 110 if (newmem == NULL) 111 abort (); 112 113 newmem->next = st->memory; 114 st->memory = newmem; 115 st->backp = newmem->memory; 116 st->left = len - offsetof (struct memoryblock, memory); 117 } 118 119 120 void 121 ebl_gstrtabfree (struct Ebl_GStrtab *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 if (st->null.string != NULL) 133 free ((char *) st->null.string); 134 135 free (st); 136 } 137 138 139 static struct Ebl_GStrent * 140 newstring (struct Ebl_GStrtab *st, const char *str, size_t len) 141 { 142 struct Ebl_GStrent *newstr; 143 size_t align; 144 size_t i; 145 size_t j; 146 147 /* Compute the amount of padding needed to make the structure aligned. */ 148 align = ((__alignof__ (struct Ebl_GStrent) 149 - (((uintptr_t) st->backp) 150 & (__alignof__ (struct Ebl_GStrent) - 1))) 151 & (__alignof__ (struct Ebl_GStrent) - 1)); 152 153 /* Make sure there is enough room in the memory block. */ 154 if (st->left < align + sizeof (struct Ebl_GStrent) + len * st->width) 155 { 156 morememory (st, sizeof (struct Ebl_GStrent) + len * st->width); 157 align = 0; 158 } 159 160 /* Create the reserved string. */ 161 newstr = (struct Ebl_GStrent *) (st->backp + align); 162 newstr->string = str; 163 newstr->len = len; 164 newstr->width = st->width; 165 newstr->next = NULL; 166 newstr->left = NULL; 167 newstr->right = NULL; 168 newstr->offset = 0; 169 for (i = len - 2; i >= 0; --i) 170 for (j = st->width - 1; j >= 0; --j) 171 newstr->reverse[i * st->width + j] = str[(len - 2 - i) * st->width + j]; 172 for (j = 0; j < st->width; ++j) 173 newstr->reverse[(len - 1) * st->width + j] = '\0'; 174 st->backp += align + sizeof (struct Ebl_GStrent) + len * st->width; 175 st->left -= align + sizeof (struct Ebl_GStrent) + len * st->width; 176 177 return newstr; 178 } 179 180 181 /* XXX This function should definitely be rewritten to use a balancing 182 tree algorith (AVL, red-black trees). For now a simple, correct 183 implementation is enough. */ 184 static struct Ebl_GStrent ** 185 searchstring (struct Ebl_GStrent **sep, struct Ebl_GStrent *newstr) 186 { 187 int cmpres; 188 189 /* More strings? */ 190 if (*sep == NULL) 191 { 192 *sep = newstr; 193 return sep; 194 } 195 196 /* Compare the strings. */ 197 cmpres = memcmp ((*sep)->reverse, newstr->reverse, 198 (MIN ((*sep)->len, newstr->len) - 1) * (*sep)->width); 199 if (cmpres == 0) 200 /* We found a matching string. */ 201 return sep; 202 else if (cmpres > 0) 203 return searchstring (&(*sep)->left, newstr); 204 else 205 return searchstring (&(*sep)->right, newstr); 206 } 207 208 209 /* Add new string. The actual string is assumed to be permanent. */ 210 struct Ebl_GStrent * 211 ebl_gstrtabadd (struct Ebl_GStrtab *st, const char *str, size_t len) 212 { 213 struct Ebl_GStrent *newstr; 214 struct Ebl_GStrent **sep; 215 216 /* Compute the string length if the caller doesn't know it. */ 217 if (len == 0) 218 { 219 size_t j; 220 221 do 222 for (j = 0; j < st->width; ++j) 223 if (str[len * st->width + j] != '\0') 224 break; 225 while (j == st->width && ++len); 226 } 227 228 /* Make sure all "" strings get offset 0 but only if the table was 229 created with a special null entry in mind. */ 230 if (len == 1 && st->null.string != NULL) 231 return &st->null; 232 233 /* Allocate memory for the new string and its associated information. */ 234 newstr = newstring (st, str, len); 235 236 /* Search in the array for the place to insert the string. If there 237 is no string with matching prefix and no string with matching 238 leading substring, create a new entry. */ 239 sep = searchstring (&st->root, newstr); 240 if (*sep != newstr) 241 { 242 /* This is not the same entry. This means we have a prefix match. */ 243 if ((*sep)->len > newstr->len) 244 { 245 struct Ebl_GStrent *subs; 246 247 /* Check whether we already know this string. */ 248 for (subs = (*sep)->next; subs != NULL; subs = subs->next) 249 if (subs->len == newstr->len) 250 { 251 /* We have an exact match with a substring. Free the memory 252 we allocated. */ 253 st->left += (st->backp - (char *) newstr) * st->width; 254 st->backp = (char *) newstr; 255 256 return subs; 257 } 258 259 /* We have a new substring. This means we don't need the reverse 260 string of this entry anymore. */ 261 st->backp -= newstr->len; 262 st->left += newstr->len; 263 264 newstr->next = (*sep)->next; 265 (*sep)->next = newstr; 266 } 267 else if ((*sep)->len != newstr->len) 268 { 269 /* When we get here it means that the string we are about to 270 add has a common prefix with a string we already have but 271 it is longer. In this case we have to put it first. */ 272 st->total += newstr->len - (*sep)->len; 273 newstr->next = *sep; 274 newstr->left = (*sep)->left; 275 newstr->right = (*sep)->right; 276 *sep = newstr; 277 } 278 else 279 { 280 /* We have an exact match. Free the memory we allocated. */ 281 st->left += (st->backp - (char *) newstr) * st->width; 282 st->backp = (char *) newstr; 283 284 newstr = *sep; 285 } 286 } 287 else 288 st->total += newstr->len; 289 290 return newstr; 291 } 292 293 294 static void 295 copystrings (struct Ebl_GStrent *nodep, char **freep, size_t *offsetp) 296 { 297 struct Ebl_GStrent *subs; 298 299 if (nodep->left != NULL) 300 copystrings (nodep->left, freep, offsetp); 301 302 /* Process the current node. */ 303 nodep->offset = *offsetp; 304 *freep = (char *) mempcpy (*freep, nodep->string, nodep->len * nodep->width); 305 *offsetp += nodep->len * nodep->width; 306 307 for (subs = nodep->next; subs != NULL; subs = subs->next) 308 { 309 assert (subs->len < nodep->len); 310 subs->offset = nodep->offset + (nodep->len - subs->len) * nodep->width; 311 assert (subs->offset != 0 || subs->string[0] == '\0'); 312 } 313 314 if (nodep->right != NULL) 315 copystrings (nodep->right, freep, offsetp); 316 } 317 318 319 void 320 ebl_gstrtabfinalize (struct Ebl_GStrtab *st, Elf_Data *data) 321 { 322 size_t copylen; 323 char *endp; 324 size_t nulllen = st->nullstr ? st->width : 0; 325 326 /* Fill in the information. */ 327 data->d_buf = malloc (st->total + nulllen); 328 if (data->d_buf == NULL) 329 abort (); 330 331 /* The first byte must always be zero if we created the table with a 332 null string. */ 333 if (st->nullstr) 334 memset (data->d_buf, '\0', st->width); 335 336 data->d_type = ELF_T_BYTE; 337 data->d_size = st->total + nulllen; 338 data->d_off = 0; 339 data->d_align = 1; 340 data->d_version = EV_CURRENT; 341 342 /* Now run through the tree and add all the string while also updating 343 the offset members of the elfstrent records. */ 344 endp = (char *) data->d_buf + nulllen; 345 copylen = nulllen; 346 copystrings (st->root, &endp, ©len); 347 assert (copylen == st->total * st->width + nulllen); 348 } 349 350 351 size_t 352 ebl_gstrtaboffset (struct Ebl_GStrent *se) 353 { 354 return se->offset; 355 } 356
