libctf/ctf-string.c

   1 /* CTF string table management.
   2    Copyright (C) 2019-2021 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_dict_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_dict_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_dict_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_dict_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_dict_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_dict_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_dict_t *fp, const char *str)
 219 {
 220   ctf_str_atom_t *atom;
 221
 222   if (!str)
 223     str = "";
 224
 225   atom = ctf_str_add_ref_internal (fp, str, FALSE, TRUE, 0);
 226   if (!atom)
 227     return 0;
 228
 229   return atom->csa_offset;
 230 }
 231
 232 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
 233    passed-in ref, whether or not the string is already present.  There is no
 234    attempt to deduplicate the refs list (but duplicates are harmless).  */
 235 uint32_t
 236 ctf_str_add_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 237 {
 238   ctf_str_atom_t *atom;
 239
 240   if (!str)
 241     str = "";
 242
 243   atom = ctf_str_add_ref_internal (fp, str, TRUE, TRUE, ref);
 244   if (!atom)
 245     return 0;
 246
 247   return atom->csa_offset;
 248 }
 249
 250 /* Add an external strtab reference at OFFSET.  Returns zero if the addition
 251    failed, nonzero otherwise.  */
 252 int
 253 ctf_str_add_external (ctf_dict_t *fp, const char *str, uint32_t offset)
 254 {
 255   ctf_str_atom_t *atom;
 256
 257   if (!str)
 258     str = "";
 259
 260   atom = ctf_str_add_ref_internal (fp, str, FALSE, FALSE, 0);
 261   if (!atom)
 262     return 0;
 263
 264   atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
 265
 266   if (!fp->ctf_syn_ext_strtab)
 267     fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
 268                                                  ctf_hash_eq_integer,
 269                                                  NULL, NULL);
 270   if (!fp->ctf_syn_ext_strtab)
 271     {
 272       ctf_set_errno (fp, ENOMEM);
 273       return 0;
 274     }
 275
 276   if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
 277                           (void *) (uintptr_t)
 278                           atom->csa_external_offset,
 279                           (void *) atom->csa_str) < 0)
 280     {
 281       /* No need to bother freeing the syn_ext_strtab: it will get freed at
 282          ctf_str_write_strtab time if unreferenced.  */
 283       ctf_set_errno (fp, ENOMEM);
 284       return 0;
 285     }
 286
 287   return 1;
 288 }
 289
 290 /* Remove a single ref.  */
 291 void
 292 ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 293 {
 294   ctf_str_atom_ref_t *aref, *anext;
 295   ctf_str_atom_t *atom = NULL;
 296
 297   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 298   if (!atom)
 299     return;
 300
 301   for (aref = ctf_list_next (&atom->csa_refs); aref != NULL; aref = anext)
 302     {
 303       anext = ctf_list_next (aref);
 304       if (aref->caf_ref == ref)
 305         {
 306           ctf_list_delete (&atom->csa_refs, aref);
 307           free (aref);
 308         }
 309     }
 310 }
 311
 312 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
 313    snapshot ID.  External atoms are never removed, because they came from the
 314    linker string table and are still present even if you roll back type
 315    additions.  */
 316 static int
 317 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 318 {
 319   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 320   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 321
 322   return (atom->csa_snapshot_id > id->snapshot_id)
 323     && (atom->csa_external_offset == 0);
 324 }
 325
 326 /* Roll back, deleting all (internal) atoms created after a particular ID.  */
 327 void
 328 ctf_str_rollback (ctf_dict_t *fp, ctf_snapshot_id_t id)
 329 {
 330   ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
 331 }
 332
 333 /* An adaptor around ctf_purge_atom_refs.  */
 334 static void
 335 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 336                              void *arg _libctf_unused_)
 337 {
 338   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 339   ctf_str_purge_atom_refs (atom);
 340 }
 341
 342 /* Remove all the recorded refs from the atoms table.  */
 343 void
 344 ctf_str_purge_refs (ctf_dict_t *fp)
 345 {
 346   if (fp->ctf_str_num_refs > 0)
 347     ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
 348   fp->ctf_str_num_refs = 0;
 349 }
 350
 351 /* Update a list of refs to the specified value. */
 352 static void
 353 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 354 {
 355   ctf_str_atom_ref_t *ref;
 356
 357   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
 358        ref = ctf_list_next (ref))
 359       *(ref->caf_ref) = value;
 360 }
 361
 362 /* State shared across the strtab write process.  */
 363 typedef struct ctf_strtab_write_state
 364 {
 365   /* Strtab we are writing, and the number of strings in it.  */
 366   ctf_strs_writable_t *strtab;
 367   size_t strtab_count;
 368
 369   /* Pointers to (existing) atoms in the atoms table, for qsorting.  */
 370   ctf_str_atom_t **sorttab;
 371
 372   /* Loop counter for sorttab population.  */
 373   size_t i;
 374
 375   /* The null-string atom (skipped during population).  */
 376   ctf_str_atom_t *nullstr;
 377 } ctf_strtab_write_state_t;
 378
 379 /* Count the number of entries in the strtab, and its length.  */
 380 static void
 381 ctf_str_count_strtab (void *key _libctf_unused_, void *value,
 382               void *arg)
 383 {
 384   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 385   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 386
 387   /* We only factor in the length of items that have no offset and have refs:
 388      other items are in the external strtab, or will simply not be written out
 389      at all.  They still contribute to the total count, though, because we still
 390      have to sort them.  We add in the null string's length explicitly, outside
 391      this function, since it is explicitly written out even if it has no refs at
 392      all.  */
 393
 394   if (s->nullstr == atom)
 395     {
 396       s->strtab_count++;
 397       return;
 398     }
 399
 400   if (!ctf_list_empty_p (&atom->csa_refs))
 401     {
 402       if (!atom->csa_external_offset)
 403         s->strtab->cts_len += strlen (atom->csa_str) + 1;
 404       s->strtab_count++;
 405     }
 406 }
 407
 408 /* Populate the sorttab with pointers to the strtab atoms.  */
 409 static void
 410 ctf_str_populate_sorttab (void *key _libctf_unused_, void *value,
 411                   void *arg)
 412 {
 413   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 414   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 415
 416   /* Skip the null string.  */
 417   if (s->nullstr == atom)
 418     return;
 419
 420   /* Skip atoms with no refs.  */
 421   if (!ctf_list_empty_p (&atom->csa_refs))
 422     s->sorttab[s->i++] = atom;
 423 }
 424
 425 /* Sort the strtab.  */
 426 static int
 427 ctf_str_sort_strtab (const void *a, const void *b)
 428 {
 429   ctf_str_atom_t **one = (ctf_str_atom_t **) a;
 430   ctf_str_atom_t **two = (ctf_str_atom_t **) b;
 431
 432   return (strcmp ((*one)->csa_str, (*two)->csa_str));
 433 }
 434
 435 /* Write out and return a strtab containing all strings with recorded refs,
 436    adjusting the refs to refer to the corresponding string.  The returned strtab
 437    may be NULL on error.  Also populate the synthetic strtab with mappings from
 438    external strtab offsets to names, so we can look them up with ctf_strptr().
 439    Only external strtab offsets with references are added.  */
 440 ctf_strs_writable_t
 441 ctf_str_write_strtab (ctf_dict_t *fp)
 442 {
 443   ctf_strs_writable_t strtab;
 444   ctf_str_atom_t *nullstr;
 445   uint32_t cur_stroff = 0;
 446   ctf_strtab_write_state_t s;
 447   ctf_str_atom_t **sorttab;
 448   size_t i;
 449   int any_external = 0;
 450
 451   memset (&strtab, 0, sizeof (struct ctf_strs_writable));
 452   memset (&s, 0, sizeof (struct ctf_strtab_write_state));
 453   s.strtab = &strtab;
 454
 455   nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, "");
 456   if (!nullstr)
 457     {
 458       ctf_err_warn (fp, 0, ECTF_INTERNAL, _("null string not found in strtab"));
 459       strtab.cts_strs = NULL;
 460       return strtab;
 461     }
 462
 463   s.nullstr = nullstr;
 464   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s);
 465   strtab.cts_len++;                             /* For the null string.  */
 466
 467   ctf_dprintf ("%lu bytes of strings in strtab.\n",
 468                (unsigned long) strtab.cts_len);
 469
 470   /* Sort the strtab.  Force the null string to be first.  */
 471   sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *));
 472   if (!sorttab)
 473     goto oom;
 474
 475   sorttab[0] = nullstr;
 476   s.i = 1;
 477   s.sorttab = sorttab;
 478   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s);
 479
 480   qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *),
 481          ctf_str_sort_strtab);
 482
 483   if ((strtab.cts_strs = malloc (strtab.cts_len)) == NULL)
 484     goto oom_sorttab;
 485
 486   /* Update all refs: also update the strtab appropriately.  */
 487   for (i = 0; i < s.strtab_count; i++)
 488     {
 489       if (sorttab[i]->csa_external_offset)
 490         {
 491           /* External strtab entry.  */
 492
 493           any_external = 1;
 494           ctf_str_update_refs (sorttab[i], sorttab[i]->csa_external_offset);
 495           sorttab[i]->csa_offset = sorttab[i]->csa_external_offset;
 496         }
 497       else
 498         {
 499           /* Internal strtab entry with refs: actually add to the string
 500              table.  */
 501
 502           ctf_str_update_refs (sorttab[i], cur_stroff);
 503           sorttab[i]->csa_offset = cur_stroff;
 504           strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str);
 505           cur_stroff += strlen (sorttab[i]->csa_str) + 1;
 506         }
 507     }
 508   free (sorttab);
 509
 510   if (!any_external)
 511     {
 512       ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
 513       fp->ctf_syn_ext_strtab = NULL;
 514     }
 515
 516   /* All the provisional strtab entries are now real strtab entries, and
 517      ctf_strptr() will find them there.  The provisional offset now starts right
 518      beyond the new end of the strtab.  */
 519
 520   ctf_dynhash_empty (fp->ctf_prov_strtab);
 521   fp->ctf_str_prov_offset = strtab.cts_len + 1;
 522   return strtab;
 523
 524  oom_sorttab:
 525   free (sorttab);
 526  oom:
 527   return strtab;
 528 }