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 <wchar.h> 27 #include <sys/param.h> 28 29 #include "libebl.h" 30 #include <system.h> 31 32 #ifndef MIN 33 # define MIN(a, b) ((a) < (b) ? (a) : (b)) 34 #endif 35 36 37 struct Ebl_WStrent 38 { 39 const wchar_t *string; 40 size_t len; 41 struct Ebl_WStrent *next; 42 struct Ebl_WStrent *left; 43 struct Ebl_WStrent *right; 44 size_t offset; 45 wchar_t reverse[0]; 46 }; 47 48 49 struct memoryblock 50 { 51 struct memoryblock *next; 52 char memory[0]; 53 }; 54 55 56 struct Ebl_WStrtab 57 { 58 struct Ebl_WStrent *root; 59 struct memoryblock *memory; 60 char *backp; 61 size_t left; 62 size_t total; 63 bool nullstr; 64 65 struct Ebl_WStrent 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_WStrtab * 75 ebl_wstrtabinit (bool nullstr) 76 { 77 struct Ebl_WStrtab *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_WStrtab *) calloc (1, sizeof (struct Ebl_WStrtab)); 86 if (ret != NULL) 87 { 88 ret->nullstr = nullstr; 89 if (nullstr) 90 { 91 ret->null.len = 1; 92 ret->null.string = L""; 93 } 94 } 95 return ret; 96 } 97 98 99 static int 100 morememory (struct Ebl_WStrtab *st, size_t len) 101 { 102 struct memoryblock *newmem; 103 104 if (len < ps) 105 len = ps; 106 newmem = (struct memoryblock *) malloc (len); 107 if (newmem == NULL) 108 return 1; 109 110 newmem->next = st->memory; 111 st->memory = newmem; 112 st->backp = newmem->memory; 113 st->left = len - offsetof (struct memoryblock, memory); 114 115 return 0; 116 } 117 118 119 void 120 ebl_wstrtabfree (struct Ebl_WStrtab *st) 121 { 122 struct memoryblock *mb = st->memory; 123 124 while (mb != NULL) 125 { 126 void *old = mb; 127 mb = mb->next; 128 free (old); 129 } 130 131 free (st); 132 } 133 134 135 static struct Ebl_WStrent * 136 newstring (struct Ebl_WStrtab *st, const wchar_t *str, size_t len) 137 { 138 struct Ebl_WStrent *newstr; 139 size_t align; 140 int i; 141 142 /* Compute the amount of padding needed to make the structure aligned. */ 143 align = ((__alignof__ (struct Ebl_WStrent) 144 - (((uintptr_t) st->backp) 145 & (__alignof__ (struct Ebl_WStrent) - 1))) 146 & (__alignof__ (struct Ebl_WStrent) - 1)); 147 148 /* Make sure there is enough room in the memory block. */ 149 if (st->left < align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t)) 150 { 151 if (morememory (st, 152 sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t))) 153 return NULL; 154 155 align = 0; 156 } 157 158 /* Create the reserved string. */ 159 newstr = (struct Ebl_WStrent *) (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] = L'\0'; 169 st->backp += align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t); 170 st->left -= align + sizeof (struct Ebl_WStrent) + len * sizeof (wchar_t); 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_WStrent ** 180 searchstring (struct Ebl_WStrent **sep, struct Ebl_WStrent *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 = wmemcmp ((*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_WStrent * 206 ebl_wstrtabadd (struct Ebl_WStrtab *st, const wchar_t *str, size_t len) 207 { 208 struct Ebl_WStrent *newstr; 209 struct Ebl_WStrent **sep; 210 211 /* Compute the string length if the caller doesn't know it. */ 212 if (len == 0) 213 len = wcslen (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_WStrent *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_WStrent *nodep, wchar_t **freep, size_t *offsetp) 285 { 286 struct Ebl_WStrent *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 = wmempcpy (*freep, nodep->string, nodep->len); 294 *offsetp += nodep->len * sizeof (wchar_t); 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_wstrtabfinalize (struct Ebl_WStrtab *st, Elf_Data *data) 310 { 311 size_t copylen; 312 wchar_t *endp; 313 size_t nulllen = st->nullstr ? 1 : 0; 314 315 /* Fill in the information. */ 316 data->d_buf = malloc ((st->total + nulllen) * sizeof (wchar_t)); 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 *((wchar_t *) data->d_buf) = L'\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 = (wchar_t *) data->d_buf + nulllen; 334 copylen = sizeof (wchar_t) * nulllen; 335 copystrings (st->root, &endp, ©len); 336 assert (copylen == (st->total + nulllen) * sizeof (wchar_t)); 337 } 338 339 340 size_t 341 ebl_wstrtaboffset (struct Ebl_WStrent *se) 342 { 343 return se->offset; 344 } 345
