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 by looking
  24   up the appropriate string table buffer and then adding the offset.  */
  25 const char *
  26 ctf_strraw (ctf_file_t *fp, uint32_t name)
  27 {
  28   ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)];
  29
  30   if (ctsp->cts_strs != NULL && CTF_NAME_OFFSET (name) < ctsp->cts_len)
  31     return (ctsp->cts_strs + CTF_NAME_OFFSET (name));
  32
  33   /* String table not loaded or corrupt offset.  */
  34   return NULL;
  35 }
  36
  37 /* Return a guaranteed-non-NULL pointer to the string with the given CTF
  38    name.  */
  39 const char *
  40 ctf_strptr (ctf_file_t *fp, uint32_t name)
  41 {
  42   const char *s = ctf_strraw (fp, name);
  43   return (s != NULL ? s : "(?)");
  44 }
  45
  46 /* Remove all refs to a given atom.  */
  47 static void
  48 ctf_str_purge_atom_refs (ctf_str_atom_t *atom)
  49 {
  50   ctf_str_atom_ref_t *ref, *next;
  51
  52   for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next)
  53     {
  54       next = ctf_list_next (ref);
  55       ctf_list_delete (&atom->csa_refs, ref);
  56       ctf_free (ref);
  57     }
  58 }
  59
  60 /* Free an atom (only called on ctf_close().)  */
  61 static void
  62 ctf_str_free_atom (void *a)
  63 {
  64   ctf_str_atom_t *atom = a;
  65
  66   ctf_str_purge_atom_refs (atom);
  67   ctf_free (atom);
  68 }
  69
  70 /* Create the atoms table.  There is always at least one atom in it, the null
  71    string.  */
  72 int
  73 ctf_str_create_atoms (ctf_file_t *fp)
  74 {
  75   fp->ctf_str_atoms = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
  76                                           ctf_free, ctf_str_free_atom);
  77   if (fp->ctf_str_atoms == NULL)
  78     return -ENOMEM;
  79
  80   ctf_str_add (fp, "");
  81   return 0;
  82 }
  83
  84 /* Destroy the atoms table.  */
  85 void
  86 ctf_str_free_atoms (ctf_file_t *fp)
  87 {
  88   ctf_dynhash_destroy (fp->ctf_str_atoms);
  89 }
  90
  91 /* Add a string to the atoms table and return it, or return an existing string
  92    if present, copying the passed-in string.  Returns NULL only when out of
  93    memory (and do not touch the passed-in string in that case).  Possibly
  94    augment the ref list with the passed-in ref.  */
  95 static const char *
  96 ctf_str_add_ref_internal (ctf_file_t *fp, const char *str,
  97                           int add_ref, uint32_t *ref)
  98 {
  99   char *newstr = NULL;
 100   ctf_str_atom_t *atom = NULL;
 101   ctf_str_atom_ref_t *aref = NULL;
 102
 103   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 104
 105   if (add_ref)
 106     {
 107       if ((aref = ctf_alloc (sizeof (struct ctf_str_atom_ref))) == NULL)
 108         return NULL;
 109       aref->caf_ref = ref;
 110     }
 111
 112   if (atom)
 113     {
 114       if (add_ref)
 115         {
 116           ctf_list_append (&atom->csa_refs, aref);
 117           fp->ctf_str_num_refs++;
 118         }
 119       return atom->csa_str;
 120     }
 121
 122   if ((atom = ctf_alloc (sizeof (struct ctf_str_atom))) == NULL)
 123     goto oom;
 124   memset (atom, 0, sizeof (struct ctf_str_atom));
 125
 126   if ((newstr = ctf_strdup (str)) == NULL)
 127     goto oom;
 128
 129   if (ctf_dynhash_insert (fp->ctf_str_atoms, newstr, atom) < 0)
 130     goto oom;
 131
 132   atom->csa_str = newstr;
 133   atom->csa_snapshot_id = fp->ctf_snapshots;
 134   if (add_ref)
 135     {
 136       ctf_list_append (&atom->csa_refs, aref);
 137       fp->ctf_str_num_refs++;
 138     }
 139   return newstr;
 140
 141  oom:
 142   ctf_free (atom);
 143   ctf_free (aref);
 144   ctf_free (newstr);
 145   return NULL;
 146 }
 147
 148 /* Add a string to the atoms table and return it, without augmenting the ref
 149    list for this string.  */
 150 const char *
 151 ctf_str_add (ctf_file_t *fp, const char *str)
 152 {
 153   if (str)
 154     return ctf_str_add_ref_internal (fp, str, FALSE, 0);
 155   return NULL;
 156 }
 157
 158 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
 159    snapshot ID.  */
 160 static int
 161 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 162 {
 163   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 164   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 165
 166   return (atom->csa_snapshot_id > id->snapshot_id);
 167 }
 168
 169 /* Roll back, deleting all atoms created after a particular ID.  */
 170 void
 171 ctf_str_rollback (ctf_file_t *fp, ctf_snapshot_id_t id)
 172 {
 173   ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
 174 }
 175
 176 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
 177    passed-in ref, whether or not the string is already present.  There is no
 178    attempt to deduplicate the refs list (but duplicates are harmless).  */
 179 const char *
 180 ctf_str_add_ref (ctf_file_t *fp, const char *str, uint32_t *ref)
 181 {
 182   if (str)
 183     return ctf_str_add_ref_internal (fp, str, TRUE, ref);
 184   return NULL;
 185 }
 186
 187 /* An adaptor around ctf_purge_atom_refs.  */
 188 static void
 189 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 190                              void *arg _libctf_unused_)
 191 {
 192   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 193   ctf_str_purge_atom_refs (atom);
 194 }
 195
 196 /* Remove all the recorded refs from the atoms table.  */
 197 void
 198 ctf_str_purge_refs (ctf_file_t *fp)
 199 {
 200   if (fp->ctf_str_num_refs > 0)
 201     ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
 202   fp->ctf_str_num_refs = 0;
 203 }
 204
 205 /* Update a list of refs to the specified value. */
 206 static void
 207 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 208 {
 209   ctf_str_atom_ref_t *ref;
 210
 211   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
 212        ref = ctf_list_next (ref))
 213       *(ref->caf_ref) = value;
 214 }
 215
 216 /* State shared across the strtab write process.  */
 217 typedef struct ctf_strtab_write_state
 218 {
 219   /* Strtab we are writing, and the number of strings in it.  */
 220   ctf_strs_writable_t *strtab;
 221   size_t strtab_count;
 222
 223   /* Pointers to (existing) atoms in the atoms table, for qsorting.  */
 224   ctf_str_atom_t **sorttab;
 225
 226   /* Loop counter for sorttab population.  */
 227   size_t i;
 228
 229   /* The null-string atom (skipped during population).  */
 230   ctf_str_atom_t *nullstr;
 231 } ctf_strtab_write_state_t;
 232
 233 /* Count the number of entries in the strtab, and its length.  */
 234 static void
 235 ctf_str_count_strtab (void *key _libctf_unused_, void *value,
 236               void *arg)
 237 {
 238   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 239   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 240
 241   s->strtab->cts_len += strlen (atom->csa_str) + 1;
 242   s->strtab_count++;
 243 }
 244
 245 /* Populate the sorttab with pointers to the strtab atoms.  */
 246 static void
 247 ctf_str_populate_sorttab (void *key _libctf_unused_, void *value,
 248                   void *arg)
 249 {
 250   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 251   ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
 252
 253   /* Skip the null string.  */
 254   if (s->nullstr == atom)
 255     return;
 256
 257   s->sorttab[s->i++] = atom;
 258 }
 259
 260 /* Sort the strtab.  */
 261 static int
 262 ctf_str_sort_strtab (const void *a, const void *b)
 263 {
 264   ctf_str_atom_t **one = (ctf_str_atom_t **) a;
 265   ctf_str_atom_t **two = (ctf_str_atom_t **) b;
 266
 267   return (strcmp ((*one)->csa_str, (*two)->csa_str));
 268 }
 269
 270 /* Write out and return a strtab containing all strings with recorded refs,
 271    adjusting the refs to refer to the corresponding string.  The returned
 272    strtab may be NULL on error.  */
 273 ctf_strs_writable_t
 274 ctf_str_write_strtab (ctf_file_t *fp)
 275 {
 276   ctf_strs_writable_t strtab;
 277   ctf_str_atom_t *nullstr;
 278   uint32_t cur_stroff = 0;
 279   ctf_strtab_write_state_t s;
 280   ctf_str_atom_t **sorttab;
 281   size_t i;
 282
 283   memset (&strtab, 0, sizeof (struct ctf_strs_writable));
 284   memset (&s, 0, sizeof (struct ctf_strtab_write_state));
 285   s.strtab = &strtab;
 286
 287   nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, "");
 288   if (!nullstr)
 289     {
 290       ctf_dprintf ("Internal error: null string not found in strtab.\n");
 291       strtab.cts_strs = NULL;
 292       return strtab;
 293     }
 294
 295   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s);
 296
 297   ctf_dprintf ("%lu bytes of strings in strtab.\n",
 298                (unsigned long) strtab.cts_len);
 299
 300   /* Sort the strtab.  Force the null string to be first.  */
 301   sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *));
 302   if (!sorttab)
 303       return strtab;
 304
 305   sorttab[0] = nullstr;
 306   s.i = 1;
 307   s.sorttab = sorttab;
 308   s.nullstr = nullstr;
 309   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s);
 310
 311   qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *),
 312          ctf_str_sort_strtab);
 313
 314   if ((strtab.cts_strs = ctf_alloc (strtab.cts_len)) == NULL)
 315     {
 316       free (sorttab);
 317       return strtab;
 318     }
 319
 320   /* Update the strtab, and all refs.  */
 321   for (i = 0; i < s.strtab_count; i++)
 322     {
 323       strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str);
 324       ctf_str_update_refs (sorttab[i], cur_stroff);
 325       cur_stroff += strlen (sorttab[i]->csa_str) + 1;
 326     }
 327   free (sorttab);
 328
 329   return strtab;
 330 }