1 /* ELF string table handling. 2 Copyright (C) 2000, 2001, 2002 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 <wchar.h> 42 #include <sys/param.h> 43 44 #include "libebl.h" 45 #include <system.h> 46 47 #ifndef MIN 48 # define MIN(a, b) ((a) < (b) ? (a) : (b)) 49 #endif 50 51 52 struct Ebl_WStrent 53 { 54 const wchar_t *string; 55 size_t len; 56 struct Ebl_WStrent *next; 57 struct Ebl_WStrent *left; 58 struct Ebl_WStrent *right; 59 size_t offset; 60 wchar_t reverse[0]; 61 }; 62 63 64 struct memoryblock 65 { 66 struct memoryblock *next; 67 char memory[0]; 68 }; 69 70 71 struct Ebl_WStrtab 72 { 73 struct Ebl_WStrent *root; 74 struct memoryblock *memory; 75 char *backp; 76 size_t left; 77 size_t total; 78 bool nullstr; 79 80 struct Ebl_WStrent 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_WStrtab * 90 ebl_wstrtabinit (bool nullstr) 91 { 92 struct Ebl_WStrtab *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_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab)); 101 if (ret != NULL) 102 { 103 ret->nullstr = nullstr; 104 if (nullstr) 105 { 106 ret->null.len = 1; 107 ret->null.string = L""; 108 } 109 } 110 return ret; 111 } 112 113 114 static int 115 morememory (struct Ebl_WStrtab *st, size_t len) 116 { 117 struct memoryblock *newmem; 118 119 if (len < ps) 120 len = ps; 121 newmem = (struct memoryblock *) malloc (len); 122 if (newmem == NULL) 123 return 1; 124 125 newmem->next = st->memory; 126 st->memory = newmem; 127 st->backp = newmem->memory; 128 st->left = len - offsetof (struct memoryblock, memory); 129 130 return 0; 131 } 132 133 134 void 135 ebl_wstrtabfree (struct Ebl_WStrtab *st) 136 { 137 struct memoryblock *mb = st->memory; 138 139 while (mb != NULL) 140 { 141 void *old = mb; 142 mb = mb->next; 143 free (old); 144 } 145 146 free (st); 147 } 148 149 150 static struct Ebl_WStrent * 151 newstring (struct Ebl_WStrtab *st, const wchar_t *str, size_t len) 152 { 153 struct Ebl_WStrent *newstr; 154 size_t align; 155 int i; 156 157 /* Compute the amount of padding needed to make the structure aligned. */ 158 align = ((__alignof__ (struct Ebl_WStrent) 159 - (((uintptr_t) st->backp) 160 & (__alignof__ (struct Ebl_WStrent) - 1))) 161 & (__alignof__ (struct Ebl_WStrent) - 1)); 162 163 /* Make sure there is enough room in the memory block. */ 164 if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t)) 165 { 166 if (morememory (st, 167 sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))) 168 return NULL; 169 170 align = 0; 171 } 172 173 /* Create the reserved string. */ 174 newstr = (struct Ebl_WStrent *) (st->backp + align); 175 newstr->string = str; 176 newstr->len = len; 177 newstr->next = NULL; 178 newstr->left = NULL; 179 newstr->right = NULL; 180 newstr->offset = 0; 181 for (i = len - 2; i >= 0; --i) 182 newstr->reverse[i] = str[len - 2 - i]; 183 newstr->reverse[len - 1] = L'\0'; 184 st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t); 185 st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t); 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_WStrent ** 195 searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *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 = wmemcmp ((*sep)->reverse, newstr->reverse, 208 MIN ((*sep)->len, newstr->len) - 1); 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_WStrent * 221 ebl_wstrtabadd (struct Ebl_WStrtab *st, const wchar_t *str, size_t len) 222 { 223 struct Ebl_WStrent *newstr; 224 struct Ebl_WStrent **sep; 225 226 /* Compute the string length if the caller doesn't know it. */ 227 if (len == 0) 228 len = wcslen (str) + 1; 229 230 /* Make sure all "" strings get offset 0 but only if the table was 231 created with a special null entry in mind. */ 232 if (len == 1 && st->null.string != NULL) 233 return &st->null; 234 235 /* Allocate memory for the new string and its associated information. */ 236 newstr = newstring (st, str, len); 237 if (newstr == NULL) 238 return NULL; 239 240 /* Search in the array for the place to insert the string. If there 241 is no string with matching prefix and no string with matching 242 leading substring, create a new entry. */ 243 sep = searchstring (&st->root, newstr); 244 if (*sep != newstr) 245 { 246 /* This is not the same entry. This means we have a prefix match. */ 247 if ((*sep)->len > newstr->len) 248 { 249 struct Ebl_WStrent *subs; 250 251 /* Check whether we already know this string. */ 252 for (subs = (*sep)->next; subs != NULL; subs = subs->next) 253 if (subs->len == newstr->len) 254 { 255 /* We have an exact match with a substring. Free the memory 256 we allocated. */ 257 st->left += st->backp - (char *) newstr; 258 st->backp = (char *) newstr; 259 260 return subs; 261 } 262 263 /* We have a new substring. This means we don't need the reverse 264 string of this entry anymore. */ 265 st->backp -= newstr->len; 266 st->left += newstr->len; 267 268 newstr->next = (*sep)->next; 269 (*sep)->next = newstr; 270 } 271 else if ((*sep)->len != newstr->len) 272 { 273 /* When we get here it means that the string we are about to 274 add has a common prefix with a string we already have but 275 it is longer. In this case we have to put it first. */ 276 st->total += newstr->len - (*sep)->len; 277 newstr->next = *sep; 278 newstr->left = (*sep)->left; 279 newstr->right = (*sep)->right; 280 *sep = newstr; 281 } 282 else 283 { 284 /* We have an exact match. Free the memory we allocated. */ 285 st->left += st->backp - (char *) newstr; 286 st->backp = (char *) newstr; 287 288 newstr = *sep; 289 } 290 } 291 else 292 st->total += newstr->len; 293 294 return newstr; 295 } 296 297 298 static void 299 copystrings (struct Ebl_WStrent *nodep, wchar_t **freep, size_t *offsetp) 300 { 301 struct Ebl_WStrent *subs; 302 303 if (nodep->left != NULL) 304 copystrings (nodep->left, freep, offsetp); 305 306 /* Process the current node. */ 307 nodep->offset = *offsetp; 308 *freep = wmempcpy (*freep, nodep->string, nodep->len); 309 *offsetp += nodep->len * sizeof (wchar_t); 310 311 for (subs = nodep->next; subs != NULL; subs = subs->next) 312 { 313 assert (subs->len < nodep->len); 314 subs->offset = nodep->offset + nodep->len - subs->len; 315 assert (subs->offset != 0 || subs->string[0] == '\0'); 316 } 317 318 if (nodep->right != NULL) 319 copystrings (nodep->right, freep, offsetp); 320 } 321 322 323 void 324 ebl_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data) 325 { 326 size_t copylen; 327 wchar_t *endp; 328 size_t nulllen = st->nullstr ? 1 : 0; 329 330 /* Fill in the information. */ 331 data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t)); 332 if (data->d_buf == NULL) 333 abort (); 334 335 /* The first byte must always be zero if we created the table with a 336 null string. */ 337 if (st->nullstr) 338 *((wchar_t *) data->d_buf) = L'\0'; 339 340 data->d_type = ELF_T_BYTE; 341 data->d_size = st->total + nulllen; 342 data->d_off = 0; 343 data->d_align = 1; 344 data->d_version = EV_CURRENT; 345 346 /* Now run through the tree and add all the string while also updating 347 the offset members of the elfstrent records. */ 348 endp = (wchar_t *) data->d_buf + nulllen; 349 copylen = sizeof (wchar_t) * nulllen; 350 copystrings (st->root, &endp, ©len); 351 assert (copylen == (st->total + nulllen) * sizeof (wchar_t)); 352 } 353 354 355 size_t 356 ebl_wstrtaboffset (struct Ebl_WStrent *se) 357 { 358 return se->offset; 359 } 360
