libctf/ctf-string.c

   1 /* CTF string table management.
   2    Copyright (C) 2019-2024 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 <assert.h>
  21 #include <ctf-impl.h>
  22 #include <string.h>
  23
  24 static ctf_str_atom_t *
  25 ctf_str_add_ref_internal (ctf_dict_t *fp, const char *str,
  26                           int flags, uint32_t *ref);
  27
  28 /* Convert an encoded CTF string name into a pointer to a C string, possibly
  29   using an explicit internal provisional strtab rather than the fp-based
  30   one.  */
  31 const char *
  32 ctf_strraw_explicit (ctf_dict_t *fp, uint32_t name, ctf_strs_t *strtab)
  33 {
  34   ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)];
  35
  36   if ((CTF_NAME_STID (name) == CTF_STRTAB_0) && (strtab != NULL))
  37     ctsp = strtab;
  38
  39   /* If this name is in the external strtab, and there is a synthetic
  40      strtab, use it in preference.  (This is used to add the set of strings
  41      -- symbol names, etc -- the linker knows about before the strtab is
  42      written out.)  */
  43
  44   if (CTF_NAME_STID (name) == CTF_STRTAB_1
  45       && fp->ctf_syn_ext_strtab != NULL)
  46     return ctf_dynhash_lookup (fp->ctf_syn_ext_strtab,
  47                                (void *) (uintptr_t) name);
  48
  49   /* If the name is in the internal strtab, and the name offset is beyond
  50      the end of the ctsp->cts_len but below the ctf_str_prov_offset, this is
  51      a provisional string added by ctf_str_add*() but not yet built into a
  52      real strtab: get the value out of the ctf_prov_strtab.  */
  53
  54   if (CTF_NAME_STID (name) == CTF_STRTAB_0
  55       && name >= ctsp->cts_len && name < fp->ctf_str_prov_offset)
  56       return ctf_dynhash_lookup (fp->ctf_prov_strtab,
  57                                  (void *) (uintptr_t) name);
  58
  59   if (ctsp->cts_strs != NULL && CTF_NAME_OFFSET (name) < ctsp->cts_len)
  60     return (ctsp->cts_strs + CTF_NAME_OFFSET (name));
  61
  62   /* String table not loaded or corrupt offset.  */
  63   return NULL;
  64 }
  65
  66 /* Convert an encoded CTF string name into a pointer to a C string by looking
  67   up the appropriate string table buffer and then adding the offset.  */
  68 const char *
  69 ctf_strraw (ctf_dict_t *fp, uint32_t name)
  70 {
  71   return ctf_strraw_explicit (fp, name, NULL);
  72 }
  73
  74 /* Return a guaranteed-non-NULL pointer to the string with the given CTF
  75    name.  */
  76 const char *
  77 ctf_strptr (ctf_dict_t *fp, uint32_t name)
  78 {
  79   const char *s = ctf_strraw (fp, name);
  80   return (s != NULL ? s : "(?)");
  81 }
  82
  83 /* As above, but return info on what is wrong in more detail.
  84    (Used for type lookups.) */
  85
  86 const char *
  87 ctf_strptr_validate (ctf_dict_t *fp, uint32_t name)
  88 {
  89   const char *str = ctf_strraw (fp, name);
  90
  91   if (str == NULL)
  92     {
  93       if (CTF_NAME_STID (name) == CTF_STRTAB_1
  94           && fp->ctf_syn_ext_strtab == NULL
  95           && fp->ctf_str[CTF_NAME_STID (name)].cts_strs == NULL)
  96         {
  97           ctf_set_errno (fp, ECTF_STRTAB);
  98           return NULL;
  99         }
 100
 101       ctf_set_errno (fp, ECTF_BADNAME);
 102       return NULL;
 103     }
 104   return str;
 105 }
 106
 107 /* Remove all refs to a given atom.  */
 108 static void
 109 ctf_str_purge_atom_refs (ctf_str_atom_t *atom)
 110 {
 111   ctf_str_atom_ref_t *ref, *next;
 112   ctf_str_atom_ref_movable_t *movref, *movnext;
 113
 114   for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next)
 115     {
 116       next = ctf_list_next (ref);
 117       ctf_list_delete (&atom->csa_refs, ref);
 118       free (ref);
 119     }
 120
 121   for (movref = ctf_list_next (&atom->csa_movable_refs);
 122        movref != NULL; movref = movnext)
 123     {
 124       movnext = ctf_list_next (movref);
 125       ctf_list_delete (&atom->csa_movable_refs, movref);
 126
 127       ctf_dynhash_remove (movref->caf_movable_refs, movref);
 128
 129       free (movref);
 130     }
 131 }
 132
 133 /* Free an atom.  */
 134 static void
 135 ctf_str_free_atom (void *a)
 136 {
 137   ctf_str_atom_t *atom = a;
 138
 139   ctf_str_purge_atom_refs (atom);
 140
 141   if (atom->csa_flags & CTF_STR_ATOM_FREEABLE)
 142     free (atom->csa_str);
 143
 144   free (atom);
 145 }
 146
 147 /* Create the atoms table.  There is always at least one atom in it, the null
 148    string: but also pull in atoms from the internal strtab.  (We rely on
 149    calls to ctf_str_add_external to populate external strtab entries, since
 150    these are often not quite the same as what appears in any external
 151    strtab, and the external strtab is often huge and best not aggressively
 152    pulled in.)  */
 153 int
 154 ctf_str_create_atoms (ctf_dict_t *fp)
 155 {
 156   size_t i;
 157
 158   fp->ctf_str_atoms = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
 159                                           NULL, ctf_str_free_atom);
 160   if (!fp->ctf_str_atoms)
 161     return -ENOMEM;
 162
 163   if (!fp->ctf_prov_strtab)
 164     fp->ctf_prov_strtab = ctf_dynhash_create (ctf_hash_integer,
 165                                               ctf_hash_eq_integer,
 166                                               NULL, NULL);
 167   if (!fp->ctf_prov_strtab)
 168     goto oom_prov_strtab;
 169
 170   fp->ctf_str_movable_refs = ctf_dynhash_create (ctf_hash_integer,
 171                                                  ctf_hash_eq_integer,
 172                                                  NULL, NULL);
 173   if (!fp->ctf_str_movable_refs)
 174     goto oom_movable_refs;
 175
 176   errno = 0;
 177   ctf_str_add (fp, "");
 178   if (errno == ENOMEM)
 179     goto oom_str_add;
 180
 181   /* Pull in all the strings in the strtab as new atoms.  The provisional
 182      strtab must be empty at this point, so there is no need to populate
 183      atoms from it as well.  Types in this subset are frozen and readonly,
 184      so the refs list and movable refs list need not be populated.  */
 185
 186   for (i = 0; i < fp->ctf_str[CTF_STRTAB_0].cts_len;
 187        i += strlen (&fp->ctf_str[CTF_STRTAB_0].cts_strs[i]) + 1)
 188     {
 189       ctf_str_atom_t *atom;
 190
 191       if (fp->ctf_str[CTF_STRTAB_0].cts_strs[i] == 0)
 192         continue;
 193
 194       atom = ctf_str_add_ref_internal (fp, &fp->ctf_str[CTF_STRTAB_0].cts_strs[i],
 195                                        0, 0);
 196
 197       if (!atom)
 198         goto oom_str_add;
 199
 200       atom->csa_offset = i;
 201     }
 202
 203   fp->ctf_str_prov_offset = fp->ctf_str[CTF_STRTAB_0].cts_len + 1;
 204
 205   return 0;
 206
 207  oom_str_add:
 208   ctf_dynhash_destroy (fp->ctf_str_movable_refs);
 209   fp->ctf_str_movable_refs = NULL;
 210  oom_movable_refs:
 211   ctf_dynhash_destroy (fp->ctf_prov_strtab);
 212   fp->ctf_prov_strtab = NULL;
 213  oom_prov_strtab:
 214   ctf_dynhash_destroy (fp->ctf_str_atoms);
 215   fp->ctf_str_atoms = NULL;
 216   return -ENOMEM;
 217 }
 218
 219 /* Destroy the atoms table and associated refs.  */
 220 void
 221 ctf_str_free_atoms (ctf_dict_t *fp)
 222 {
 223   ctf_dynhash_destroy (fp->ctf_prov_strtab);
 224   ctf_dynhash_destroy (fp->ctf_str_atoms);
 225   ctf_dynhash_destroy (fp->ctf_str_movable_refs);
 226   if (fp->ctf_dynstrtab)
 227     {
 228       free (fp->ctf_dynstrtab->cts_strs);
 229       free (fp->ctf_dynstrtab);
 230     }
 231 }
 232
 233 #define CTF_STR_ADD_REF 0x1
 234 #define CTF_STR_PROVISIONAL 0x2
 235 #define CTF_STR_MOVABLE 0x4
 236
 237 /* Allocate a ref and bind it into a ref list.  */
 238
 239 static ctf_str_atom_ref_t *
 240 aref_create (ctf_dict_t *fp, ctf_str_atom_t *atom, uint32_t *ref, int flags)
 241 {
 242   ctf_str_atom_ref_t *aref;
 243   size_t s = sizeof (struct ctf_str_atom_ref);
 244
 245   if (flags & CTF_STR_MOVABLE)
 246     s = sizeof (struct ctf_str_atom_ref_movable);
 247
 248   aref = malloc (s);
 249
 250   if (!aref)
 251     return NULL;
 252
 253   aref->caf_ref = ref;
 254
 255   /* Movable refs get a backpointer to them in ctf_str_movable_refs, and a
 256      pointer to ctf_str_movable_refs itself in the ref, for use when freeing
 257      refs: they can be moved later in batches via a call to
 258      ctf_str_move_refs.  */
 259
 260   if (flags & CTF_STR_MOVABLE)
 261     {
 262       ctf_str_atom_ref_movable_t *movref = (ctf_str_atom_ref_movable_t *) aref;
 263
 264       movref->caf_movable_refs = fp->ctf_str_movable_refs;
 265
 266       if (ctf_dynhash_insert (fp->ctf_str_movable_refs, ref, aref) < 0)
 267         {
 268           free (aref);
 269           return NULL;
 270         }
 271       ctf_list_append (&atom->csa_movable_refs, movref);
 272     }
 273   else
 274     ctf_list_append (&atom->csa_refs, aref);
 275
 276   return aref;
 277 }
 278
 279 /* Add a string to the atoms table, copying the passed-in string if
 280    necessary.  Return the atom added. Return NULL only when out of memory
 281    (and do not touch the passed-in string in that case).
 282
 283    Possibly add a provisional entry for this string to the provisional
 284    strtab.  If the string is in the provisional strtab, update its ref list
 285    with the passed-in ref, causing the ref to be updated when the strtab is
 286    written out.  */
 287
 288 static ctf_str_atom_t *
 289 ctf_str_add_ref_internal (ctf_dict_t *fp, const char *str,
 290                           int flags, uint32_t *ref)
 291 {
 292   char *newstr = NULL;
 293   ctf_str_atom_t *atom = NULL;
 294   int added = 0;
 295
 296   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 297
 298   /* Existing atoms get refs added only if they are provisional:
 299      non-provisional strings already have a fixed strtab offset, and just
 300      get their ref updated immediately, since its value cannot change.  */
 301
 302   if (atom)
 303     {
 304       if (!ctf_dynhash_lookup (fp->ctf_prov_strtab, (void *) (uintptr_t)
 305                                atom->csa_offset))
 306         {
 307           if (flags & CTF_STR_ADD_REF)
 308             {
 309               if (atom->csa_external_offset)
 310                 *ref = atom->csa_external_offset;
 311               else
 312                 *ref = atom->csa_offset;
 313             }
 314           return atom;
 315         }
 316
 317       if (flags & CTF_STR_ADD_REF)
 318         {
 319           if (!aref_create (fp, atom, ref, flags))
 320             {
 321               ctf_set_errno (fp, ENOMEM);
 322               return NULL;
 323             }
 324         }
 325
 326       return atom;
 327     }
 328
 329   /* New atom.  */
 330
 331   if ((atom = malloc (sizeof (struct ctf_str_atom))) == NULL)
 332     goto oom;
 333   memset (atom, 0, sizeof (struct ctf_str_atom));
 334
 335   /* Don't allocate new strings if this string is within an mmapped
 336      strtab.  */
 337
 338   if ((unsigned char *) str < (unsigned char *) fp->ctf_data_mmapped
 339       || (unsigned char *) str > (unsigned char *) fp->ctf_data_mmapped + fp->ctf_data_mmapped_len)
 340     {
 341       if ((newstr = strdup (str)) == NULL)
 342         goto oom;
 343       atom->csa_flags |= CTF_STR_ATOM_FREEABLE;
 344       atom->csa_str = newstr;
 345     }
 346   else
 347     atom->csa_str = (char *) str;
 348
 349   if (ctf_dynhash_insert (fp->ctf_str_atoms, atom->csa_str, atom) < 0)
 350     goto oom;
 351   added = 1;
 352
 353   atom->csa_snapshot_id = fp->ctf_snapshots;
 354
 355   /* New atoms marked provisional go into the provisional strtab, and get a
 356      ref added.  */
 357
 358   if (flags & CTF_STR_PROVISIONAL)
 359     {
 360       atom->csa_offset = fp->ctf_str_prov_offset;
 361
 362       if (ctf_dynhash_insert (fp->ctf_prov_strtab, (void *) (uintptr_t)
 363                               atom->csa_offset, (void *) atom->csa_str) < 0)
 364         goto oom;
 365
 366       fp->ctf_str_prov_offset += strlen (atom->csa_str) + 1;
 367
 368       if (flags & CTF_STR_ADD_REF)
 369       {
 370         if (!aref_create (fp, atom, ref, flags))
 371           goto oom;
 372       }
 373     }
 374
 375   return atom;
 376
 377  oom:
 378   if (added)
 379     ctf_dynhash_remove (fp->ctf_str_atoms, atom->csa_str);
 380   free (atom);
 381   free (newstr);
 382   ctf_set_errno (fp, ENOMEM);
 383   return NULL;
 384 }
 385
 386 /* Add a string to the atoms table, without augmenting the ref list for this
 387    string: return a 'provisional offset' which can be used to return this string
 388    until ctf_str_write_strtab is called, or 0 on failure.  (Everywhere the
 389    provisional offset is assigned to should be added as a ref using
 390    ctf_str_add_ref() as well.) */
 391 uint32_t
 392 ctf_str_add (ctf_dict_t *fp, const char *str)
 393 {
 394   ctf_str_atom_t *atom;
 395
 396   if (!str)
 397     str = "";
 398
 399   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_PROVISIONAL, 0);
 400   if (!atom)
 401     return 0;
 402
 403   return atom->csa_offset;
 404 }
 405
 406 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
 407    passed-in ref, whether or not the string is already present.  There is no
 408    attempt to deduplicate the refs list (but duplicates are harmless).  */
 409 uint32_t
 410 ctf_str_add_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 411 {
 412   ctf_str_atom_t *atom;
 413
 414   if (!str)
 415     str = "";
 416
 417   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_ADD_REF
 418                                    | CTF_STR_PROVISIONAL, ref);
 419   if (!atom)
 420     return 0;
 421
 422   return atom->csa_offset;
 423 }
 424
 425 /* Like ctf_str_add_ref(), but note that the ref may be moved later on.  */
 426 uint32_t
 427 ctf_str_add_movable_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 428 {
 429   ctf_str_atom_t *atom;
 430
 431   if (!str)
 432     str = "";
 433
 434   atom = ctf_str_add_ref_internal (fp, str, CTF_STR_ADD_REF
 435                                    | CTF_STR_PROVISIONAL
 436                                    | CTF_STR_MOVABLE, ref);
 437   if (!atom)
 438     return 0;
 439
 440   return atom->csa_offset;
 441 }
 442
 443 /* Add an external strtab reference at OFFSET.  Returns zero if the addition
 444    failed, nonzero otherwise.  */
 445 int
 446 ctf_str_add_external (ctf_dict_t *fp, const char *str, uint32_t offset)
 447 {
 448   ctf_str_atom_t *atom;
 449
 450   if (!str)
 451     str = "";
 452
 453   atom = ctf_str_add_ref_internal (fp, str, 0, 0);
 454   if (!atom)
 455     return 0;
 456
 457   atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
 458
 459   if (!fp->ctf_syn_ext_strtab)
 460     fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
 461                                                  ctf_hash_eq_integer,
 462                                                  NULL, NULL);
 463   if (!fp->ctf_syn_ext_strtab)
 464     {
 465       ctf_set_errno (fp, ENOMEM);
 466       return 0;
 467     }
 468
 469   if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
 470                           (void *) (uintptr_t)
 471                           atom->csa_external_offset,
 472                           (void *) atom->csa_str) < 0)
 473     {
 474       /* No need to bother freeing the syn_ext_strtab: it will get freed at
 475          ctf_str_write_strtab time if unreferenced.  */
 476       ctf_set_errno (fp, ENOMEM);
 477       return 0;
 478     }
 479
 480   return 1;
 481 }
 482
 483 /* Note that refs have moved from (SRC, LEN) to DEST.  We use the movable
 484    refs backpointer for this, because it is done an amortized-constant
 485    number of times during structure member and enumerand addition, and if we
 486    did a linear search this would turn such addition into an O(n^2)
 487    operation.  Even this is not linear, but it's better than that.  */
 488 int
 489 ctf_str_move_refs (ctf_dict_t *fp, void *src, size_t len, void *dest)
 490 {
 491   uintptr_t p;
 492
 493   if (src == dest)
 494     return 0;
 495
 496   for (p = (uintptr_t) src; p - (uintptr_t) src < len; p++)
 497     {
 498       ctf_str_atom_ref_movable_t *ref;
 499
 500       if ((ref = ctf_dynhash_lookup (fp->ctf_str_movable_refs,
 501                                      (ctf_str_atom_ref_t *) p)) != NULL)
 502         {
 503           int out_of_memory;
 504
 505           ref->caf_ref = (uint32_t *) (((uintptr_t) ref->caf_ref +
 506                                         (uintptr_t) dest - (uintptr_t) src));
 507           ctf_dynhash_remove (fp->ctf_str_movable_refs,
 508                               (ctf_str_atom_ref_t *) p);
 509           out_of_memory = ctf_dynhash_insert (fp->ctf_str_movable_refs,
 510                                               ref->caf_ref, ref);
 511           assert (out_of_memory == 0);
 512         }
 513     }
 514
 515   return 0;
 516 }
 517
 518 /* Remove a single ref.  */
 519 void
 520 ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
 521 {
 522   ctf_str_atom_ref_t *aref, *anext;
 523   ctf_str_atom_ref_movable_t *amovref, *amovnext;
 524   ctf_str_atom_t *atom = NULL;
 525
 526   atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 527   if (!atom)
 528     return;
 529
 530   for (aref = ctf_list_next (&atom->csa_refs); aref != NULL; aref = anext)
 531     {
 532       anext = ctf_list_next (aref);
 533       if (aref->caf_ref == ref)
 534         {
 535           ctf_list_delete (&atom->csa_refs, aref);
 536           free (aref);
 537         }
 538     }
 539
 540   for (amovref = ctf_list_next (&atom->csa_movable_refs);
 541        amovref != NULL; amovref = amovnext)
 542     {
 543       amovnext = ctf_list_next (amovref);
 544       if (amovref->caf_ref == ref)
 545         {
 546           ctf_list_delete (&atom->csa_movable_refs, amovref);
 547           ctf_dynhash_remove (fp->ctf_str_movable_refs, ref);
 548           free (amovref);
 549         }
 550     }
 551 }
 552
 553 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
 554    snapshot ID.  External atoms are never removed, because they came from the
 555    linker string table and are still present even if you roll back type
 556    additions.  */
 557 static int
 558 ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
 559 {
 560   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 561   ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
 562
 563   return (atom->csa_snapshot_id > id->snapshot_id)
 564     && (atom->csa_external_offset == 0);
 565 }
 566
 567 /* Roll back, deleting all (internal) atoms created after a particular ID.  */
 568 void
 569 ctf_str_rollback (ctf_dict_t *fp, ctf_snapshot_id_t id)
 570 {
 571   ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
 572 }
 573
 574 /* An adaptor around ctf_purge_atom_refs.  */
 575 static void
 576 ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
 577                              void *arg _libctf_unused_)
 578 {
 579   ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
 580
 581   ctf_str_purge_atom_refs (atom);
 582 }
 583
 584 /* Remove all the recorded refs from the atoms table.  */
 585 static void
 586 ctf_str_purge_refs (ctf_dict_t *fp)
 587 {
 588   ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
 589 }
 590
 591 /* Update a list of refs to the specified value. */
 592 static void
 593 ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
 594 {
 595   ctf_str_atom_ref_t *ref;
 596   ctf_str_atom_ref_movable_t *movref;
 597
 598   for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
 599        ref = ctf_list_next (ref))
 600     *(ref->caf_ref) = value;
 601
 602   for (movref = ctf_list_next (&refs->csa_movable_refs);
 603        movref != NULL; movref = ctf_list_next (movref))
 604     *(movref->caf_ref) = value;
 605 }
 606
 607 /* Sort the strtab.  */
 608 static int
 609 ctf_str_sort_strtab (const void *a, const void *b)
 610 {
 611   ctf_str_atom_t **one = (ctf_str_atom_t **) a;
 612   ctf_str_atom_t **two = (ctf_str_atom_t **) b;
 613
 614   return (strcmp ((*one)->csa_str, (*two)->csa_str));
 615 }
 616
 617 /* Write out and return a strtab containing all strings with recorded refs,
 618    adjusting the refs to refer to the corresponding string.  The returned
 619    strtab is already assigned to strtab 0 in this dict, is owned by this
 620    dict, and may be NULL on error.  Also populate the synthetic strtab with
 621    mappings from external strtab offsets to names, so we can look them up
 622    with ctf_strptr().  Only external strtab offsets with references are
 623    added.
 624
 625    As a side effect, replaces the strtab of the current dict with the newly-
 626    generated strtab.  This is an exception to the general rule that
 627    serialization does not change the dict passed in, because the alternative
 628    is to copy the entire atoms table on every reserialization just to avoid
 629    modifying the original, which is excessively costly for minimal gain.
 630
 631    We use the lazy man's approach and double memory costs by always storing
 632    atoms as individually allocated entities whenever they come from anywhere
 633    but a freshly-opened, mmapped dict, even though after serialization there
 634    is another copy in the strtab; this ensures that ctf_strptr()-returned
 635    pointers to them remain valid for the lifetime of the dict.
 636
 637    This is all rendered more complex because if a dict is ctf_open()ed it
 638    will have a bunch of strings in its strtab already, and their strtab
 639    offsets can never change (without piles of complexity to rescan the
 640    entire dict just to get all the offsets to all of them into the atoms
 641    table).  Entries below the existing strtab limit are just copied into the
 642    new dict: entries above it are new, and are are sorted first, then
 643    appended to it.  The sorting is purely a compression-efficiency
 644    improvement, and we get nearly as good an improvement from sorting big
 645    chunks like this as we would from sorting the whole thing.  */
 646
 647 const ctf_strs_writable_t *
 648 ctf_str_write_strtab (ctf_dict_t *fp)
 649 {
 650   ctf_strs_writable_t *strtab;
 651   size_t strtab_count = 0;
 652   uint32_t cur_stroff = 0;
 653   ctf_str_atom_t **sorttab;
 654   ctf_next_t *it = NULL;
 655   size_t i;
 656   void *v;
 657   int err;
 658   int new_strtab = 0;
 659   int any_external = 0;
 660
 661   strtab = calloc (1, sizeof (ctf_strs_writable_t));
 662   if (!strtab)
 663     return NULL;
 664
 665   /* The strtab contains the existing string table at its start: figure out
 666      how many new strings we need to add.  We only need to add new strings
 667      that have no external offset, that have refs, and that are found in the
 668      provisional strtab.  If the existing strtab is empty we also need to
 669      add the null string at its start.  */
 670
 671   strtab->cts_len = fp->ctf_str[CTF_STRTAB_0].cts_len;
 672
 673   if (strtab->cts_len == 0)
 674     {
 675       new_strtab = 1;
 676       strtab->cts_len++;                        /* For the \0.  */
 677     }
 678
 679   /* Count new entries in the strtab: i.e. entries in the provisional
 680      strtab.  Ignore any entry for \0, entries which ended up in the
 681      external strtab, and unreferenced entries.  */
 682
 683   while ((err = ctf_dynhash_next (fp->ctf_prov_strtab, &it, NULL, &v)) == 0)
 684     {
 685       const char *str = (const char *) v;
 686       ctf_str_atom_t *atom;
 687
 688       atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
 689       if (!ctf_assert (fp, atom))
 690         goto err_strtab;
 691
 692       if (atom->csa_str[0] == 0 || atom->csa_external_offset
 693           || (ctf_list_empty_p (&atom->csa_refs)
 694               && ctf_list_empty_p (&atom->csa_movable_refs)))
 695         continue;
 696
 697       strtab->cts_len += strlen (atom->csa_str) + 1;
 698       strtab_count++;
 699     }
 700   if (err != ECTF_NEXT_END)
 701     {
 702       ctf_dprintf ("ctf_str_write_strtab: error counting strtab entries: %s\n",
 703                    ctf_errmsg (err));
 704       goto err_strtab;
 705     }
 706
 707   ctf_dprintf ("%lu bytes of strings in strtab: %lu pre-existing.\n",
 708                (unsigned long) strtab->cts_len,
 709                (unsigned long) fp->ctf_str[CTF_STRTAB_0].cts_len);
 710
 711   /* Sort the new part of the strtab.  */
 712
 713   sorttab = calloc (strtab_count, sizeof (ctf_str_atom_t *));
 714   if (!sorttab)
 715     {
 716       ctf_set_errno (fp, ENOMEM);
 717       goto err_strtab;
 718     }
 719
 720   i = 0;
 721   while ((err = ctf_dynhash_next (fp->ctf_prov_strtab, &it, NULL, &v)) == 0)
 722     {
 723       ctf_str_atom_t *atom;
 724
 725       atom = ctf_dynhash_lookup (fp->ctf_str_atoms, v);
 726       if (!ctf_assert (fp, atom))
 727         goto err_sorttab;
 728
 729       if (atom->csa_str[0] == 0 || atom->csa_external_offset
 730           || (ctf_list_empty_p (&atom->csa_refs)
 731               && ctf_list_empty_p (&atom->csa_movable_refs)))
 732         continue;
 733
 734       sorttab[i++] = atom;
 735     }
 736
 737   qsort (sorttab, strtab_count, sizeof (ctf_str_atom_t *),
 738          ctf_str_sort_strtab);
 739
 740   if ((strtab->cts_strs = malloc (strtab->cts_len)) == NULL)
 741     goto err_sorttab;
 742
 743   cur_stroff = fp->ctf_str[CTF_STRTAB_0].cts_len;
 744
 745   if (new_strtab)
 746     {
 747       strtab->cts_strs[0] = 0;
 748       cur_stroff++;
 749     }
 750   else
 751     memcpy (strtab->cts_strs, fp->ctf_str[CTF_STRTAB_0].cts_strs,
 752             fp->ctf_str[CTF_STRTAB_0].cts_len);
 753
 754   /* Work over the sorttab, add its strings to the strtab, and remember
 755      where they are in the csa_offset for the appropriate atom.  No ref
 756      updating is done at this point, because refs might well relate to
 757      already-existing strings, or external strings, which do not need adding
 758      to the strtab and may not be in the sorttab.  */
 759
 760   for (i = 0; i < strtab_count; i++)
 761     {
 762       sorttab[i]->csa_offset = cur_stroff;
 763       strcpy (&strtab->cts_strs[cur_stroff], sorttab[i]->csa_str);
 764       cur_stroff += strlen (sorttab[i]->csa_str) + 1;
 765     }
 766   free (sorttab);
 767   sorttab = NULL;
 768
 769   /* Update all refs, then purge them as no longer necessary: also update
 770      the strtab appropriately.  */
 771
 772   while ((err = ctf_dynhash_next (fp->ctf_str_atoms, &it, NULL, &v)) == 0)
 773     {
 774       ctf_str_atom_t *atom = (ctf_str_atom_t *) v;
 775       uint32_t offset;
 776
 777       if (ctf_list_empty_p (&atom->csa_refs) &&
 778           ctf_list_empty_p (&atom->csa_movable_refs))
 779         continue;
 780
 781       if (atom->csa_external_offset)
 782         {
 783           any_external = 1;
 784           offset = atom->csa_external_offset;
 785         }
 786       else
 787         offset = atom->csa_offset;
 788       ctf_str_update_refs (atom, offset);
 789     }
 790   if (err != ECTF_NEXT_END)
 791     {
 792       ctf_dprintf ("ctf_str_write_strtab: error iterating over atoms while updating refs: %s\n",
 793                    ctf_errmsg (err));
 794       goto err_strtab;
 795     }
 796   ctf_str_purge_refs (fp);
 797
 798   if (!any_external)
 799     {
 800       ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
 801       fp->ctf_syn_ext_strtab = NULL;
 802     }
 803
 804   /* Replace the old strtab with the new one in this dict.  */
 805
 806   if (fp->ctf_dynstrtab)
 807     {
 808       free (fp->ctf_dynstrtab->cts_strs);
 809       free (fp->ctf_dynstrtab);
 810     }
 811
 812   fp->ctf_dynstrtab = strtab;
 813   fp->ctf_str[CTF_STRTAB_0].cts_strs = strtab->cts_strs;
 814   fp->ctf_str[CTF_STRTAB_0].cts_len = strtab->cts_len;
 815
 816   /* All the provisional strtab entries are now real strtab entries, and
 817      ctf_strptr() will find them there.  The provisional offset now starts right
 818      beyond the new end of the strtab.  */
 819
 820   ctf_dynhash_empty (fp->ctf_prov_strtab);
 821   fp->ctf_str_prov_offset = strtab->cts_len + 1;
 822   return strtab;
 823
 824  err_sorttab:
 825   free (sorttab);
 826  err_strtab:
 827   free (strtab);
 828   return NULL;
 829 }