libctf/ctf-string.c

   1 /* CTF string table management.
   2    Copyright (C) 2019 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 (ctsp->cts_strs != NULL && CTF_NAME_OFFSET (name) < ctsp->cts_len)
  42     return (ctsp->cts_strs + CTF_NAME_OFFSET (name));
  43
  44   /* String table not loaded or corrupt offset.  */
  45   return NULL;
  46 }
  47
  48 /* Convert an encoded CTF string name into a pointer to a C string by looking
  49   up the appropriate string table buffer and then adding the offset.  */
  50 const char *
  51 ctf_strraw (ctf_file_t *fp, uint32_t name)
  52 {
  53   return ctf_strraw_explicit (fp, name, NULL);
  54 }
  55
  56 /* Return a guaranteed-non-NULL pointer to the string with the given CTF
  57    name.  */
  58 const char *
  59 ctf_strptr (ctf_file_t *fp, uint32_t name)
  60 {
  61   const char *s = ctf_strraw (fp, name);
  62   return (s != NULL ? s : "(?)");
  63 }
  64
  65 /* Remove all refs to a given atom.  */
  66 static void
  67 ctf_str_purge_atom_refs (ctf_str_atom_t *atom)
  68 {
  69   ctf_str_atom_ref_t *ref, *next;
  70
  71   for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next)
  72     {
  73       next = ctf_list_next (ref);
  74       ctf_list_delete (&atom->csa_refs, ref);
  75       ctf_free (ref);
  76     }
  77 }
  78
  79 /* Free an atom (only called on ctf_close().)  */
  80 static void
  81 ctf_str_free_atom (void *a)
  82 {
  83   ctf_str_atom_t *atom = a;
  84
  85   ctf_str_purge_atom_refs (atom);
  86   ctf_free (atom);
  87 }
  88
  89 /* Create the atoms table.  There is always at least one atom in it, the null
  90    string.  */
  91 int
  92 ctf_str_create_atoms (ctf_file_t *fp)
  93 {
  94   fp->ctf_str_atoms = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
  95                                           ctf_free, ctf_str_free_atom);
  96   if (fp->ctf_str_atoms == NULL)
  97     return -ENOMEM;
  98
  99   ctf_str_add (fp, "");
 100   return 0;
 101 }
 102
 103 /* Destroy the atoms table.  */
 104 void
 105 ctf_str_free_atoms (ctf_file_t *fp)
 106 {
 107   ctf_dynhash_destroy (fp->ctf_str_atoms);
 108 }
 109
 110 /* Add a string to the atoms table, copying the passed-in string.  Return the
 111    atom added. Return NULL only when out of memory (and do not touch the
 112    passed-in string in that case).  Possibly augment the ref list with the
 113    passed-in ref.  */
 114 static ctf_str_atom_t *
 115 ctf_str_add_ref_internal (ctf_file_t *fp, const char *str,
 116                           int add_ref, uint32_t *ref)
 117 {
 118   char *newstr = NULL;
 119   ctf_str_atom_t *atom = NULL;
 120   ctf_str_atom_ref_t *aref = NULL;
 121
 122   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 123
 124   if (add_ref)
 125     {
 126       if ((aref = ctf_alloc (sizeof (struct ctf_str_atom_ref))) == NULL)
 127         return NULL;
 128       aref->caf_ref = ref;
 129     }
 130
 131   if (atom)
 132     {
 133       if (add_ref)
 134         {
 135           ctf_list_append (&atom->csa_refs, aref);
 136           fp->ctf_str_num_refs++;
 137         }
 138       return atom;
 139     }
 140
 141   if ((atom = ctf_alloc (sizeof (struct ctf_str_atom))) == NULL)
 142     goto oom;
 143   memset (atom, 0, sizeof (struct ctf_str_atom));
 144
 145   if ((newstr = ctf_strdup (str)) == NULL)
 146     goto oom;
 147
 148   if (ctf_dynhash_insert (fp->ctf_str_atoms, newstr, atom) < 0)
 149     goto oom;
 150
 151   atom->csa_str = newstr;
 152   atom->csa_snapshot_id = fp->ctf_snapshots;
 153   if (add_ref)
 154     {
 155       ctf_list_append (&atom->csa_refs, aref);
 156       fp->ctf_str_num_refs++;
 157     }
 158   return atom;
 159
 160  oom:
 161   ctf_free (atom);
 162   ctf_free (aref);
 163   ctf_free (newstr);
 164   return NULL;
 165 }
 166
 167 /* Add a string to the atoms table and return it, without augmenting the ref
 168    list for this string.  */
 169 const char *
 170 ctf_str_add (ctf_file_t *fp, const char *str)
 171 {
 172   ctf_str_atom_t *atom;
 173   if (!str)
 174     return NULL;
 175
 176   atom = ctf_str_add_ref_internal (fp, str, FALSE, 0);
 177   if (!atom)
 178     return NULL;
 179
 180   return atom->csa_str;
 181 }
 182
 183 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
 184    passed-in ref, whether or not the string is already present.  There is no
 185    attempt to deduplicate the refs list (but duplicates are harmless).  */
 186 const char *
 187 ctf_str_add_ref (ctf_file_t *fp, const char *str, uint32_t *ref)
 188 {
 189   ctf_str_atom_t *atom;
 190   if (!str)
 191     return NULL;
 192
 193   atom = ctf_str_add_ref_internal (fp, str, TRUE, ref);
 194   if (!atom)
 195     return NULL;
 196
 197   return atom->csa_str;
 198 }
 199
 200 /* Add an external strtab reference at OFFSET.  */
 201 const char *
 202 ctf_str_add_external (ctf_file_t *fp, const char *str, uint32_t offset)
 203 {
 204   ctf_str_atom_t *atom;
 205   if (!str)
 206     return NULL;
 207
 208   atom = ctf_str_add_ref_internal (fp, str, FALSE, 0);
 209   if (!atom)
 210     return NULL;
 211
 212   atom->csa_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
 213   return atom->csa_str;
 214 }
 215
 216 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
 217    snapshot ID.  */
 218 static int
 219 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 220 {
 221   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 222   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 223
 224   return (atom->csa_snapshot_id > id->snapshot_id);
 225 }
 226
 227 /* Roll back, deleting all atoms created after a particular ID.  */
 228 void
 229 ctf_str_rollback (ctf_file_t *fp, ctf_snapshot_id_t id)
 230 {
 231   ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
 232 }
 233
 234 /* An adaptor around ctf_purge_atom_refs.  */
 235 static void
 236 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 237                              void *arg _libctf_unused_)
 238 {
 239   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 240   ctf_str_purge_atom_refs (atom);
 241 }
 242
 243 /* Remove all the recorded refs from the atoms table.  */
 244 void
 245 ctf_str_purge_refs (ctf_file_t *fp)
 246 {
 247   if (fp->ctf_str_num_refs > 0)
 248     ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
 249   fp->ctf_str_num_refs = 0;
 250 }
 251
 252 /* Update a list of refs to the specified value. */
 253 static void
 254 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 255 {
 256   ctf_str_atom_ref_t *ref;
 257
 258   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
 259        ref = ctf_list_next (ref))
 260       *(ref->caf_ref) = value;
 261 }
 262
 263 /* State shared across the strtab write process.  */
 264 typedef struct ctf_strtab_write_state
 265 {
 266   /* Strtab we are writing, and the number of strings in it.  */
 267   ctf_strs_writable_t *strtab;
 268   size_t strtab_count;
 269
 270   /* Pointers to (existing) atoms in the atoms table, for qsorting.  */
 271   ctf_str_atom_t **sorttab;
 272
 273   /* Loop counter for sorttab population.  */
 274   size_t i;
 275
 276   /* The null-string atom (skipped during population).  */
 277   ctf_str_atom_t *nullstr;
 278 } ctf_strtab_write_state_t;
 279
 280 /* Count the number of entries in the strtab, and its length.  */
 281 static void
 282 ctf_str_count_strtab (void *key _libctf_unused_, void *value,
 283               void *arg)
 284 {
 285   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 286   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 287
 288   /* We only factor in the length of items that have no offset:
 289      other items are in the external strtab.  They still contribute to the
 290      total count, though, because we still have to sort them.  */
 291   if (!atom->csa_offset)
 292     s->strtab->cts_len += strlen (atom->csa_str) + 1;
 293   s->strtab_count++;
 294 }
 295
 296 /* Populate the sorttab with pointers to the strtab atoms.  */
 297 static void
 298 ctf_str_populate_sorttab (void *key _libctf_unused_, void *value,
 299                   void *arg)
 300 {
 301   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 302   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 303
 304   /* Skip the null string.  */
 305   if (s->nullstr == atom)
 306     return;
 307
 308   s->sorttab[s->i++] = atom;
 309 }
 310
 311 /* Sort the strtab.  */
 312 static int
 313 ctf_str_sort_strtab (const void *a, const void *b)
 314 {
 315   ctf_str_atom_t **one = (ctf_str_atom_t **) a;
 316   ctf_str_atom_t **two = (ctf_str_atom_t **) b;
 317
 318   return (strcmp ((*one)->csa_str, (*two)->csa_str));
 319 }
 320
 321 /* Write out and return a strtab containing all strings with recorded refs,
 322    adjusting the refs to refer to the corresponding string.  The returned strtab
 323    may be NULL on error.  Also populate the synthetic strtab with mappings from
 324    external strtab offsets to names, so we can look them up with ctf_strptr().
 325    Only external strtab offsets with references are added.  */
 326 ctf_strs_writable_t
 327 ctf_str_write_strtab (ctf_file_t *fp)
 328 {
 329   ctf_strs_writable_t strtab;
 330   ctf_str_atom_t *nullstr;
 331   uint32_t cur_stroff = 0;
 332   ctf_strtab_write_state_t s;
 333   ctf_str_atom_t **sorttab;
 334   size_t i;
 335   int any_external = 0;
 336
 337   memset (&strtab, 0, sizeof (struct ctf_strs_writable));
 338   memset (&s, 0, sizeof (struct ctf_strtab_write_state));
 339   s.strtab = &strtab;
 340
 341   nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, "");
 342   if (!nullstr)
 343     {
 344       ctf_dprintf ("Internal error: null string not found in strtab.\n");
 345       strtab.cts_strs = NULL;
 346       return strtab;
 347     }
 348
 349   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s);
 350
 351   ctf_dprintf ("%lu bytes of strings in strtab.\n",
 352                (unsigned long) strtab.cts_len);
 353
 354   /* Sort the strtab.  Force the null string to be first.  */
 355   sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *));
 356   if (!sorttab)
 357     goto oom;
 358
 359   sorttab[0] = nullstr;
 360   s.i = 1;
 361   s.sorttab = sorttab;
 362   s.nullstr = nullstr;
 363   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s);
 364
 365   qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *),
 366          ctf_str_sort_strtab);
 367
 368   if ((strtab.cts_strs = ctf_alloc (strtab.cts_len)) == NULL)
 369     goto oom_sorttab;
 370
 371   if (!fp->ctf_syn_ext_strtab)
 372     fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
 373                                                  ctf_hash_eq_integer,
 374                                                  NULL, NULL);
 375   if (!fp->ctf_syn_ext_strtab)
 376     goto oom_strtab;
 377
 378   /* Update all refs: also update the strtab appropriately.  */
 379   for (i = 0; i < s.strtab_count; i++)
 380     {
 381       if (sorttab[i]->csa_offset)
 382         {
 383           /* External strtab entry: populate the synthetic external strtab.
 384
 385              This is safe because you cannot ctf_rollback to before the point
 386              when a ctf_update is done, and the strtab is written at ctf_update
 387              time.  So any atoms we reference here are sure to stick around
 388              until ctf_file_close.  */
 389
 390           any_external = 1;
 391           ctf_str_update_refs (sorttab[i], sorttab[i]->csa_offset);
 392           if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
 393                                   (void *) (uintptr_t) sorttab[i]->csa_offset,
 394                                   (void *) sorttab[i]->csa_str) < 0)
 395             goto oom_strtab;
 396         }
 397       else
 398         {
 399           /* Internal strtab entry: actually add to the string table.  */
 400
 401           ctf_str_update_refs (sorttab[i], cur_stroff);
 402           strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str);
 403           cur_stroff += strlen (sorttab[i]->csa_str) + 1;
 404         }
 405     }
 406   free (sorttab);
 407
 408   if (!any_external)
 409     {
 410       ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
 411       fp->ctf_syn_ext_strtab = NULL;
 412     }
 413
 414   return strtab;
 415
 416  oom_strtab:
 417   free (strtab.cts_strs);
 418   strtab.cts_strs = NULL;
 419  oom_sorttab:
 420   free (sorttab);
 421  oom:
 422   return strtab;
 423 }