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