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)
 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   if (!fp->ctf_str_pending_ref)
 117     fp->ctf_str_pending_ref = ctf_dynset_create (htab_hash_pointer,
 118                                                  htab_eq_pointer,
 119                                                  NULL);
 120   if (!fp->ctf_str_pending_ref)
 121     goto oom_str_pending_ref;
 122
 123   errno = 0;
 124   ctf_str_add (fp, "");
 125   if (errno == ENOMEM)
 126     goto oom_str_add;
 127
 128   return 0;
 129
 130  oom_str_add:
 131   ctf_dynhash_destroy (fp->ctf_prov_strtab);
 132   fp->ctf_prov_strtab = NULL;
 133  oom_str_pending_ref:
 134   ctf_dynset_destroy (fp->ctf_str_pending_ref);
 135   fp->ctf_str_pending_ref = NULL;
 136  oom_prov_strtab:
 137   ctf_dynhash_destroy (fp->ctf_str_atoms);
 138   fp->ctf_str_atoms = NULL;
 139   return -ENOMEM;
 140 }
 141
 142 /* Destroy the atoms table.  */
 143 void
 144 ctf_str_free_atoms (ctf_dict_t *fp)
 145 {
 146   ctf_dynhash_destroy (fp->ctf_prov_strtab);
 147   ctf_dynhash_destroy (fp->ctf_str_atoms);
 148   ctf_dynset_destroy (fp->ctf_str_pending_ref);
 149 }
 150
 151 #define CTF_STR_ADD_REF 0x1
 152 #define CTF_STR_MAKE_PROVISIONAL 0x2
 153 #define CTF_STR_PENDING_REF 0x4
 154
 155 /* Add a string to the atoms table, copying the passed-in string.  Return the
 156    atom added. Return NULL only when out of memory (and do not touch the
 157    passed-in string in that case).  Possibly augment the ref list with the
 158    passed-in ref.  Possibly add a provisional entry for this string to the
 159    provisional strtab.   */
 160 static ctf_str_atom_t *
 161 ctf_str_add_ref_internal (ctf_dict_t *fp, const char *str,
 162                           int flags, uint32_t *ref)
 163 {
 164   char *newstr = NULL;
 165   ctf_str_atom_t *atom = NULL;
 166   ctf_str_atom_ref_t *aref = NULL;
 167
 168   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 169
 170   if (flags & CTF_STR_ADD_REF)
 171     {
 172       if ((aref = malloc (sizeof (struct ctf_str_atom_ref))) == NULL)
 173         return NULL;
 174       aref->caf_ref = ref;
 175     }
 176
 177   if (atom)
 178     {
 179       if (flags & CTF_STR_ADD_REF)
 180         {
 181           ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
 182           ctf_list_append (&atom->csa_refs, aref);
 183           fp->ctf_str_num_refs++;
 184         }
 185       return atom;
 186     }
 187
 188   if ((atom = malloc (sizeof (struct ctf_str_atom))) == NULL)
 189     goto oom;
 190   memset (atom, 0, sizeof (struct ctf_str_atom));
 191
 192   if ((newstr = strdup (str)) == NULL)
 193     goto oom;
 194
 195   if (ctf_dynhash_insert (fp->ctf_str_atoms, newstr, atom) < 0)
 196     goto oom;
 197
 198   atom->csa_str = newstr;
 199   atom->csa_snapshot_id = fp->ctf_snapshots;
 200
 201   if (flags & CTF_STR_MAKE_PROVISIONAL)
 202     {
 203       atom->csa_offset = fp->ctf_str_prov_offset;
 204
 205       if (ctf_dynhash_insert (fp->ctf_prov_strtab, (void *) (uintptr_t)
 206                               atom->csa_offset, (void *) atom->csa_str) < 0)
 207         goto oom;
 208
 209       fp->ctf_str_prov_offset += strlen (atom->csa_str) + 1;
 210     }
 211
 212   if (flags & CTF_STR_PENDING_REF)
 213     {
 214       if (ctf_dynset_insert (fp->ctf_str_pending_ref, (void *) ref) < 0)
 215         goto oom;
 216     }
 217   else if (flags & CTF_STR_ADD_REF)
 218     {
 219       ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
 220       ctf_list_append (&atom->csa_refs, aref);
 221       fp->ctf_str_num_refs++;
 222     }
 223   return atom;
 224
 225  oom:
 226   if (newstr)
 227     ctf_dynhash_remove (fp->ctf_str_atoms, newstr);
 228   free (atom);
 229   free (aref);
 230   free (newstr);
 231   return NULL;
 232 }
 233
 234 /* Add a string to the atoms table, without augmenting the ref list for this
 235    string: return a 'provisional offset' which can be used to return this string
 236    until ctf_str_write_strtab is called, or 0 on failure.  (Everywhere the
 237    provisional offset is assigned to should be added as a ref using
 238    ctf_str_add_ref() as well.) */
 239 uint32_t
 240 ctf_str_add (ctf_dict_t *fp, const char *str)
 241 {
 242   ctf_str_atom_t *atom;
 243
 244   if (!str)
 245     str = "";
 246
 247   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_MAKE_PROVISIONAL, 0);
 248   if (!atom)
 249     return 0;
 250
 251   return atom->csa_offset;
 252 }
 253
 254 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
 255    passed-in ref, whether or not the string is already present.  There is no
 256    attempt to deduplicate the refs list (but duplicates are harmless).  */
 257 uint32_t
 258 ctf_str_add_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 259 {
 260   ctf_str_atom_t *atom;
 261
 262   if (!str)
 263     str = "";
 264
 265   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_ADD_REF
 266                                    | CTF_STR_MAKE_PROVISIONAL, ref);
 267   if (!atom)
 268     return 0;
 269
 270   return atom->csa_offset;
 271 }
 272
 273 /* Like ctf_str_add_ref(), but notes that this memory location must be added as
 274    a ref by a later serialization phase, rather than adding it itself.  */
 275 uint32_t
 276 ctf_str_add_pending (ctf_dict_t *fp, const char *str, uint32_t *ref)
 277 {
 278   ctf_str_atom_t *atom;
 279
 280   if (!str)
 281     str = "";
 282
 283   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_PENDING_REF
 284                                    | CTF_STR_MAKE_PROVISIONAL, ref);
 285   if (!atom)
 286     return 0;
 287
 288   return atom->csa_offset;
 289 }
 290
 291 /* Add an external strtab reference at OFFSET.  Returns zero if the addition
 292    failed, nonzero otherwise.  */
 293 int
 294 ctf_str_add_external (ctf_dict_t *fp, const char *str, uint32_t offset)
 295 {
 296   ctf_str_atom_t *atom;
 297
 298   if (!str)
 299     str = "";
 300
 301   atom = ctf_str_add_ref_internal (fp, str, 0, 0);
 302   if (!atom)
 303     return 0;
 304
 305   atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
 306
 307   if (!fp->ctf_syn_ext_strtab)
 308     fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
 309                                                  ctf_hash_eq_integer,
 310                                                  NULL, NULL);
 311   if (!fp->ctf_syn_ext_strtab)
 312     {
 313       ctf_set_errno (fp, ENOMEM);
 314       return 0;
 315     }
 316
 317   if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
 318                           (void *) (uintptr_t)
 319                           atom->csa_external_offset,
 320                           (void *) atom->csa_str) < 0)
 321     {
 322       /* No need to bother freeing the syn_ext_strtab: it will get freed at
 323          ctf_str_write_strtab time if unreferenced.  */
 324       ctf_set_errno (fp, ENOMEM);
 325       return 0;
 326     }
 327
 328   return 1;
 329 }
 330
 331 /* Remove a single ref.  */
 332 void
 333 ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 334 {
 335   ctf_str_atom_ref_t *aref, *anext;
 336   ctf_str_atom_t *atom = NULL;
 337
 338   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 339   if (!atom)
 340     return;
 341
 342   for (aref = ctf_list_next (&atom->csa_refs); aref != NULL; aref = anext)
 343     {
 344       anext = ctf_list_next (aref);
 345       if (aref->caf_ref == ref)
 346         {
 347           ctf_list_delete (&atom->csa_refs, aref);
 348           free (aref);
 349         }
 350     }
 351
 352   ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
 353 }
 354
 355 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
 356    snapshot ID.  External atoms are never removed, because they came from the
 357    linker string table and are still present even if you roll back type
 358    additions.  */
 359 static int
 360 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 361 {
 362   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 363   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 364
 365   return (atom->csa_snapshot_id > id->snapshot_id)
 366     && (atom->csa_external_offset == 0);
 367 }
 368
 369 /* Roll back, deleting all (internal) atoms created after a particular ID.  */
 370 void
 371 ctf_str_rollback (ctf_dict_t *fp, ctf_snapshot_id_t id)
 372 {
 373   ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
 374 }
 375
 376 /* An adaptor around ctf_purge_atom_refs.  */
 377 static void
 378 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 379                              void *arg _libctf_unused_)
 380 {
 381   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 382   ctf_str_purge_atom_refs (atom);
 383 }
 384
 385 /* Remove all the recorded refs from the atoms table.  */
 386 void
 387 ctf_str_purge_refs (ctf_dict_t *fp)
 388 {
 389   if (fp->ctf_str_num_refs > 0)
 390     ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
 391   fp->ctf_str_num_refs = 0;
 392 }
 393
 394 /* Update a list of refs to the specified value. */
 395 static void
 396 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 397 {
 398   ctf_str_atom_ref_t *ref;
 399
 400   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
 401        ref = ctf_list_next (ref))
 402       *(ref->caf_ref) = value;
 403 }
 404
 405 /* State shared across the strtab write process.  */
 406 typedef struct ctf_strtab_write_state
 407 {
 408   /* Strtab we are writing, and the number of strings in it.  */
 409   ctf_strs_writable_t *strtab;
 410   size_t strtab_count;
 411
 412   /* Pointers to (existing) atoms in the atoms table, for qsorting.  */
 413   ctf_str_atom_t **sorttab;
 414
 415   /* Loop counter for sorttab population.  */
 416   size_t i;
 417
 418   /* The null-string atom (skipped during population).  */
 419   ctf_str_atom_t *nullstr;
 420 } ctf_strtab_write_state_t;
 421
 422 /* Count the number of entries in the strtab, and its length.  */
 423 static void
 424 ctf_str_count_strtab (void *key _libctf_unused_, void *value,
 425               void *arg)
 426 {
 427   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 428   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 429
 430   /* We only factor in the length of items that have no offset and have refs:
 431      other items are in the external strtab, or will simply not be written out
 432      at all.  They still contribute to the total count, though, because we still
 433      have to sort them.  We add in the null string's length explicitly, outside
 434      this function, since it is explicitly written out even if it has no refs at
 435      all.  */
 436
 437   if (s->nullstr == atom)
 438     {
 439       s->strtab_count++;
 440       return;
 441     }
 442
 443   if (!ctf_list_empty_p (&atom->csa_refs))
 444     {
 445       if (!atom->csa_external_offset)
 446         s->strtab->cts_len += strlen (atom->csa_str) + 1;
 447       s->strtab_count++;
 448     }
 449 }
 450
 451 /* Populate the sorttab with pointers to the strtab atoms.  */
 452 static void
 453 ctf_str_populate_sorttab (void *key _libctf_unused_, void *value,
 454                   void *arg)
 455 {
 456   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 457   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 458
 459   /* Skip the null string.  */
 460   if (s->nullstr == atom)
 461     return;
 462
 463   /* Skip atoms with no refs.  */
 464   if (!ctf_list_empty_p (&atom->csa_refs))
 465     s->sorttab[s->i++] = atom;
 466 }
 467
 468 /* Sort the strtab.  */
 469 static int
 470 ctf_str_sort_strtab (const void *a, const void *b)
 471 {
 472   ctf_str_atom_t **one = (ctf_str_atom_t **) a;
 473   ctf_str_atom_t **two = (ctf_str_atom_t **) b;
 474
 475   return (strcmp ((*one)->csa_str, (*two)->csa_str));
 476 }
 477
 478 /* Write out and return a strtab containing all strings with recorded refs,
 479    adjusting the refs to refer to the corresponding string.  The returned strtab
 480    may be NULL on error.  Also populate the synthetic strtab with mappings from
 481    external strtab offsets to names, so we can look them up with ctf_strptr().
 482    Only external strtab offsets with references are added.  */
 483 ctf_strs_writable_t
 484 ctf_str_write_strtab (ctf_dict_t *fp)
 485 {
 486   ctf_strs_writable_t strtab;
 487   ctf_str_atom_t *nullstr;
 488   uint32_t cur_stroff = 0;
 489   ctf_strtab_write_state_t s;
 490   ctf_str_atom_t **sorttab;
 491   size_t i;
 492   int any_external = 0;
 493
 494   memset (&strtab, 0, sizeof (struct ctf_strs_writable));
 495   memset (&s, 0, sizeof (struct ctf_strtab_write_state));
 496   s.strtab = &strtab;
 497
 498   nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, "");
 499   if (!nullstr)
 500     {
 501       ctf_err_warn (fp, 0, ECTF_INTERNAL, _("null string not found in strtab"));
 502       strtab.cts_strs = NULL;
 503       return strtab;
 504     }
 505
 506   s.nullstr = nullstr;
 507   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s);
 508   strtab.cts_len++;                             /* For the null string.  */
 509
 510   ctf_dprintf ("%lu bytes of strings in strtab.\n",
 511                (unsigned long) strtab.cts_len);
 512
 513   /* Sort the strtab.  Force the null string to be first.  */
 514   sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *));
 515   if (!sorttab)
 516     goto oom;
 517
 518   sorttab[0] = nullstr;
 519   s.i = 1;
 520   s.sorttab = sorttab;
 521   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s);
 522
 523   qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *),
 524          ctf_str_sort_strtab);
 525
 526   if ((strtab.cts_strs = malloc (strtab.cts_len)) == NULL)
 527     goto oom_sorttab;
 528
 529   /* Update all refs: also update the strtab appropriately.  */
 530   for (i = 0; i < s.strtab_count; i++)
 531     {
 532       if (sorttab[i]->csa_external_offset)
 533         {
 534           /* External strtab entry.  */
 535
 536           any_external = 1;
 537           ctf_str_update_refs (sorttab[i], sorttab[i]->csa_external_offset);
 538           sorttab[i]->csa_offset = sorttab[i]->csa_external_offset;
 539         }
 540       else
 541         {
 542           /* Internal strtab entry with refs: actually add to the string
 543              table.  */
 544
 545           ctf_str_update_refs (sorttab[i], cur_stroff);
 546           sorttab[i]->csa_offset = cur_stroff;
 547           strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str);
 548           cur_stroff += strlen (sorttab[i]->csa_str) + 1;
 549         }
 550     }
 551   free (sorttab);
 552
 553   if (!any_external)
 554     {
 555       ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
 556       fp->ctf_syn_ext_strtab = NULL;
 557     }
 558
 559   /* All the provisional strtab entries are now real strtab entries, and
 560      ctf_strptr() will find them there.  The provisional offset now starts right
 561      beyond the new end of the strtab.  */
 562
 563   ctf_dynhash_empty (fp->ctf_prov_strtab);
 564   fp->ctf_str_prov_offset = strtab.cts_len + 1;
 565   return strtab;
 566
 567  oom_sorttab:
 568   free (sorttab);
 569  oom:
 570   return strtab;
 571 }