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