1 /* CTF string table management. 2 Copyright (C) 2019-2020 Free Software Foundation, Inc. 3 4 This file is part of libctf. 5 6 libctf is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 This program is distributed in the hope that it will be useful, but 12 WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 14 See the GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; see the file COPYING. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include <ctf-impl.h> 21 #include <string.h> 22 23 /* Convert an encoded CTF string name into a pointer to a C string, using an 24 explicit internal strtab rather than the fp-based one. */ 25 const char * 26 ctf_strraw_explicit (ctf_file_t *fp, uint32_t name, ctf_strs_t *strtab) 27 { 28 ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)]; 29 30 if ((CTF_NAME_STID (name) == CTF_STRTAB_0) && (strtab != NULL)) 31 ctsp = strtab; 32 33 /* If this name is in the external strtab, and there is a synthetic strtab, 34 use it in preference. */ 35 36 if (CTF_NAME_STID (name) == CTF_STRTAB_1 37 && fp->ctf_syn_ext_strtab != NULL) 38 return ctf_dynhash_lookup (fp->ctf_syn_ext_strtab, 39 (void *) (uintptr_t) name); 40 41 /* If the name is in the internal strtab, and the offset is beyond the end of 42 the ctsp->cts_len but below the ctf_str_prov_offset, this is a provisional 43 string added by ctf_str_add*() but not yet built into a real strtab: get 44 the value out of the ctf_prov_strtab. */ 45 46 if (CTF_NAME_STID (name) == CTF_STRTAB_0 47 && name >= ctsp->cts_len && name < fp->ctf_str_prov_offset) 48 return ctf_dynhash_lookup (fp->ctf_prov_strtab, 49 (void *) (uintptr_t) name); 50 51 if (ctsp->cts_strs != NULL && CTF_NAME_OFFSET (name) < ctsp->cts_len) 52 return (ctsp->cts_strs + CTF_NAME_OFFSET (name)); 53 54 /* String table not loaded or corrupt offset. */ 55 return NULL; 56 } 57 58 /* Convert an encoded CTF string name into a pointer to a C string by looking 59 up the appropriate string table buffer and then adding the offset. */ 60 const char * 61 ctf_strraw (ctf_file_t *fp, uint32_t name) 62 { 63 return ctf_strraw_explicit (fp, name, NULL); 64 } 65 66 /* Return a guaranteed-non-NULL pointer to the string with the given CTF 67 name. */ 68 const char * 69 ctf_strptr (ctf_file_t *fp, uint32_t name) 70 { 71 const char *s = ctf_strraw (fp, name); 72 return (s != NULL ? s : "(?)"); 73 } 74 75 /* Remove all refs to a given atom. */ 76 static void 77 ctf_str_purge_atom_refs (ctf_str_atom_t *atom) 78 { 79 ctf_str_atom_ref_t *ref, *next; 80 81 for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next) 82 { 83 next = ctf_list_next (ref); 84 ctf_list_delete (&atom->csa_refs, ref); 85 free (ref); 86 } 87 } 88 89 /* Free an atom (only called on ctf_close().) */ 90 static void 91 ctf_str_free_atom (void *a) 92 { 93 ctf_str_atom_t *atom = a; 94 95 ctf_str_purge_atom_refs (atom); 96 free (atom); 97 } 98 99 /* Create the atoms table. There is always at least one atom in it, the null 100 string. */ 101 int 102 ctf_str_create_atoms (ctf_file_t *fp) 103 { 104 fp->ctf_str_atoms = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string, 105 free, ctf_str_free_atom); 106 if (fp->ctf_str_atoms == NULL) 107 return -ENOMEM; 108 109 if (!fp->ctf_prov_strtab) 110 fp->ctf_prov_strtab = ctf_dynhash_create (ctf_hash_integer, 111 ctf_hash_eq_integer, 112 NULL, NULL); 113 if (!fp->ctf_prov_strtab) 114 goto oom_prov_strtab; 115 116 errno = 0; 117 ctf_str_add (fp, ""); 118 if (errno == ENOMEM) 119 goto oom_str_add; 120 121 return 0; 122 123 oom_str_add: 124 ctf_dynhash_destroy (fp->ctf_prov_strtab); 125 fp->ctf_prov_strtab = NULL; 126 oom_prov_strtab: 127 ctf_dynhash_destroy (fp->ctf_str_atoms); 128 fp->ctf_str_atoms = NULL; 129 return -ENOMEM; 130 } 131 132 /* Destroy the atoms table. */ 133 void 134 ctf_str_free_atoms (ctf_file_t *fp) 135 { 136 ctf_dynhash_destroy (fp->ctf_prov_strtab); 137 ctf_dynhash_destroy (fp->ctf_str_atoms); 138 } 139 140 /* Add a string to the atoms table, copying the passed-in string. Return the 141 atom added. Return NULL only when out of memory (and do not touch the 142 passed-in string in that case). Possibly augment the ref list with the 143 passed-in ref. Possibly add a provisional entry for this string to the 144 provisional strtab. */ 145 static ctf_str_atom_t * 146 ctf_str_add_ref_internal (ctf_file_t *fp, const char *str, 147 int add_ref, int make_provisional, uint32_t *ref) 148 { 149 char *newstr = NULL; 150 ctf_str_atom_t *atom = NULL; 151 ctf_str_atom_ref_t *aref = NULL; 152 153 atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str); 154 155 if (add_ref) 156 { 157 if ((aref = malloc (sizeof (struct ctf_str_atom_ref))) == NULL) 158 return NULL; 159 aref->caf_ref = ref; 160 } 161 162 if (atom) 163 { 164 if (add_ref) 165 { 166 ctf_list_append (&atom->csa_refs, aref); 167 fp->ctf_str_num_refs++; 168 } 169 return atom; 170 } 171 172 if ((atom = malloc (sizeof (struct ctf_str_atom))) == NULL) 173 goto oom; 174 memset (atom, 0, sizeof (struct ctf_str_atom)); 175 176 if ((newstr = strdup (str)) == NULL) 177 goto oom; 178 179 if (ctf_dynhash_insert (fp->ctf_str_atoms, newstr, atom) < 0) 180 goto oom; 181 182 atom->csa_str = newstr; 183 atom->csa_snapshot_id = fp->ctf_snapshots; 184 185 if (make_provisional) 186 { 187 atom->csa_offset = fp->ctf_str_prov_offset; 188 189 if (ctf_dynhash_insert (fp->ctf_prov_strtab, (void *) (uintptr_t) 190 atom->csa_offset, (void *) atom->csa_str) < 0) 191 goto oom; 192 193 fp->ctf_str_prov_offset += strlen (atom->csa_str) + 1; 194 } 195 196 if (add_ref) 197 { 198 ctf_list_append (&atom->csa_refs, aref); 199 fp->ctf_str_num_refs++; 200 } 201 return atom; 202 203 oom: 204 if (newstr) 205 ctf_dynhash_remove (fp->ctf_str_atoms, newstr); 206 free (atom); 207 free (aref); 208 free (newstr); 209 return NULL; 210 } 211 212 /* Add a string to the atoms table, without augmenting the ref list for this 213 string: return a 'provisional offset' which can be used to return this string 214 until ctf_str_write_strtab is called, or 0 on failure. (Everywhere the 215 provisional offset is assigned to should be added as a ref using 216 ctf_str_add_ref() as well.) */ 217 uint32_t 218 ctf_str_add (ctf_file_t *fp, const char *str) 219 { 220 ctf_str_atom_t *atom; 221 if (!str) 222 return 0; 223 224 atom = ctf_str_add_ref_internal (fp, str, FALSE, TRUE, 0); 225 if (!atom) 226 return 0; 227 228 return atom->csa_offset; 229 } 230 231 /* Like ctf_str_add(), but additionally augment the atom's refs list with the 232 passed-in ref, whether or not the string is already present. There is no 233 attempt to deduplicate the refs list (but duplicates are harmless). */ 234 uint32_t 235 ctf_str_add_ref (ctf_file_t *fp, const char *str, uint32_t *ref) 236 { 237 ctf_str_atom_t *atom; 238 if (!str) 239 return 0; 240 241 atom = ctf_str_add_ref_internal (fp, str, TRUE, TRUE, ref); 242 if (!atom) 243 return 0; 244 245 return atom->csa_offset; 246 } 247 248 /* Add an external strtab reference at OFFSET. Returns zero if the addition 249 failed, nonzero otherwise. */ 250 int 251 ctf_str_add_external (ctf_file_t *fp, const char *str, uint32_t offset) 252 { 253 ctf_str_atom_t *atom; 254 if (!str) 255 return 0; 256 257 atom = ctf_str_add_ref_internal (fp, str, FALSE, FALSE, 0); 258 if (!atom) 259 return 0; 260 261 atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1); 262 return 1; 263 } 264 265 /* Remove a single ref. */ 266 void 267 ctf_str_remove_ref (ctf_file_t *fp, const char *str, uint32_t *ref) 268 { 269 ctf_str_atom_ref_t *aref, *anext; 270 ctf_str_atom_t *atom = NULL; 271 272 atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str); 273 if (!atom) 274 return; 275 276 for (aref = ctf_list_next (&atom->csa_refs); aref != NULL; aref = anext) 277 { 278 anext = ctf_list_next (aref); 279 if (aref->caf_ref == ref) 280 { 281 ctf_list_delete (&atom->csa_refs, aref); 282 free (aref); 283 } 284 } 285 } 286 287 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given 288 snapshot ID. */ 289 static int 290 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg) 291 { 292 ctf_str_atom_t *atom = (ctf_str_atom_t *) value; 293 ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg; 294 295 return (atom->csa_snapshot_id > id->snapshot_id); 296 } 297 298 /* Roll back, deleting all atoms created after a particular ID. */ 299 void 300 ctf_str_rollback (ctf_file_t *fp, ctf_snapshot_id_t id) 301 { 302 ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id); 303 } 304 305 /* An adaptor around ctf_purge_atom_refs. */ 306 static void 307 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value, 308 void *arg _libctf_unused_) 309 { 310 ctf_str_atom_t *atom = (ctf_str_atom_t *) value; 311 ctf_str_purge_atom_refs (atom); 312 } 313 314 /* Remove all the recorded refs from the atoms table. */ 315 void 316 ctf_str_purge_refs (ctf_file_t *fp) 317 { 318 if (fp->ctf_str_num_refs > 0) 319 ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL); 320 fp->ctf_str_num_refs = 0; 321 } 322 323 /* Update a list of refs to the specified value. */ 324 static void 325 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value) 326 { 327 ctf_str_atom_ref_t *ref; 328 329 for (ref = ctf_list_next (&refs->csa_refs); ref != NULL; 330 ref = ctf_list_next (ref)) 331 *(ref->caf_ref) = value; 332 } 333 334 /* State shared across the strtab write process. */ 335 typedef struct ctf_strtab_write_state 336 { 337 /* Strtab we are writing, and the number of strings in it. */ 338 ctf_strs_writable_t *strtab; 339 size_t strtab_count; 340 341 /* Pointers to (existing) atoms in the atoms table, for qsorting. */ 342 ctf_str_atom_t **sorttab; 343 344 /* Loop counter for sorttab population. */ 345 size_t i; 346 347 /* The null-string atom (skipped during population). */ 348 ctf_str_atom_t *nullstr; 349 } ctf_strtab_write_state_t; 350 351 /* Count the number of entries in the strtab, and its length. */ 352 static void 353 ctf_str_count_strtab (void *key _libctf_unused_, void *value, 354 void *arg) 355 { 356 ctf_str_atom_t *atom = (ctf_str_atom_t *) value; 357 ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg; 358 359 /* We only factor in the length of items that have no offset and have refs: 360 other items are in the external strtab, or will simply not be written out 361 at all. They still contribute to the total count, though, because we still 362 have to sort them. We add in the null string's length explicitly, outside 363 this function, since it is explicitly written out even if it has no refs at 364 all. */ 365 366 if (s->nullstr == atom) 367 { 368 s->strtab_count++; 369 return; 370 } 371 372 if (!ctf_list_empty_p (&atom->csa_refs)) 373 { 374 if (!atom->csa_external_offset) 375 s->strtab->cts_len += strlen (atom->csa_str) + 1; 376 s->strtab_count++; 377 } 378 } 379 380 /* Populate the sorttab with pointers to the strtab atoms. */ 381 static void 382 ctf_str_populate_sorttab (void *key _libctf_unused_, void *value, 383 void *arg) 384 { 385 ctf_str_atom_t *atom = (ctf_str_atom_t *) value; 386 ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg; 387 388 /* Skip the null string. */ 389 if (s->nullstr == atom) 390 return; 391 392 /* Skip atoms with no refs. */ 393 if (!ctf_list_empty_p (&atom->csa_refs)) 394 s->sorttab[s->i++] = atom; 395 } 396 397 /* Sort the strtab. */ 398 static int 399 ctf_str_sort_strtab (const void *a, const void *b) 400 { 401 ctf_str_atom_t **one = (ctf_str_atom_t **) a; 402 ctf_str_atom_t **two = (ctf_str_atom_t **) b; 403 404 return (strcmp ((*one)->csa_str, (*two)->csa_str)); 405 } 406 407 /* Write out and return a strtab containing all strings with recorded refs, 408 adjusting the refs to refer to the corresponding string. The returned strtab 409 may be NULL on error. Also populate the synthetic strtab with mappings from 410 external strtab offsets to names, so we can look them up with ctf_strptr(). 411 Only external strtab offsets with references are added. */ 412 ctf_strs_writable_t 413 ctf_str_write_strtab (ctf_file_t *fp) 414 { 415 ctf_strs_writable_t strtab; 416 ctf_str_atom_t *nullstr; 417 uint32_t cur_stroff = 0; 418 ctf_strtab_write_state_t s; 419 ctf_str_atom_t **sorttab; 420 size_t i; 421 int any_external = 0; 422 423 memset (&strtab, 0, sizeof (struct ctf_strs_writable)); 424 memset (&s, 0, sizeof (struct ctf_strtab_write_state)); 425 s.strtab = &strtab; 426 427 nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, ""); 428 if (!nullstr) 429 { 430 ctf_dprintf ("Internal error: null string not found in strtab.\n"); 431 strtab.cts_strs = NULL; 432 return strtab; 433 } 434 435 s.nullstr = nullstr; 436 ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s); 437 strtab.cts_len++; /* For the null string. */ 438 439 ctf_dprintf ("%lu bytes of strings in strtab.\n", 440 (unsigned long) strtab.cts_len); 441 442 /* Sort the strtab. Force the null string to be first. */ 443 sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *)); 444 if (!sorttab) 445 goto oom; 446 447 sorttab[0] = nullstr; 448 s.i = 1; 449 s.sorttab = sorttab; 450 ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s); 451 452 qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *), 453 ctf_str_sort_strtab); 454 455 if ((strtab.cts_strs = malloc (strtab.cts_len)) == NULL) 456 goto oom_sorttab; 457 458 if (!fp->ctf_syn_ext_strtab) 459 fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer, 460 ctf_hash_eq_integer, 461 NULL, NULL); 462 if (!fp->ctf_syn_ext_strtab) 463 goto oom_strtab; 464 465 /* Update all refs: also update the strtab appropriately. */ 466 for (i = 0; i < s.strtab_count; i++) 467 { 468 if (sorttab[i]->csa_external_offset) 469 { 470 /* External strtab entry: populate the synthetic external strtab. 471 472 This is safe because you cannot ctf_rollback to before the point 473 when a ctf_update is done, and the strtab is written at ctf_update 474 time. So any atoms we reference here are sure to stick around 475 until ctf_file_close. */ 476 477 any_external = 1; 478 ctf_str_update_refs (sorttab[i], sorttab[i]->csa_external_offset); 479 if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab, 480 (void *) (uintptr_t) 481 sorttab[i]->csa_external_offset, 482 (void *) sorttab[i]->csa_str) < 0) 483 goto oom_strtab; 484 sorttab[i]->csa_offset = sorttab[i]->csa_external_offset; 485 } 486 else 487 { 488 /* Internal strtab entry with refs: actually add to the string 489 table. */ 490 491 ctf_str_update_refs (sorttab[i], cur_stroff); 492 sorttab[i]->csa_offset = cur_stroff; 493 strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str); 494 cur_stroff += strlen (sorttab[i]->csa_str) + 1; 495 } 496 } 497 free (sorttab); 498 499 if (!any_external) 500 { 501 ctf_dynhash_destroy (fp->ctf_syn_ext_strtab); 502 fp->ctf_syn_ext_strtab = NULL; 503 } 504 505 /* All the provisional strtab entries are now real strtab entries, and 506 ctf_strptr() will find them there. The provisional offset now starts right 507 beyond the new end of the strtab. */ 508 509 ctf_dynhash_empty (fp->ctf_prov_strtab); 510 fp->ctf_str_prov_offset = strtab.cts_len + 1; 511 return strtab; 512 513 oom_strtab: 514 free (strtab.cts_strs); 515 strtab.cts_strs = NULL; 516 oom_sorttab: 517 free (sorttab); 518 oom: 519 return strtab; 520 } 521