1 /* CTF string table management.
2 Copyright (C) 2019-2021 Free Software Foundation, Inc.
4 This file is part of libctf.
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
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.
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/>. */
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. */
26 ctf_strraw_explicit (ctf_dict_t
*fp
, uint32_t name
, ctf_strs_t
*strtab
)
28 ctf_strs_t
*ctsp
= &fp
->ctf_str
[CTF_NAME_STID (name
)];
30 if ((CTF_NAME_STID (name
) == CTF_STRTAB_0
) && (strtab
!= NULL
))
33 /* If this name is in the external strtab, and there is a synthetic strtab,
34 use it in preference. */
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
);
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. */
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
);
51 if (ctsp
->cts_strs
!= NULL
&& CTF_NAME_OFFSET (name
) < ctsp
->cts_len
)
52 return (ctsp
->cts_strs
+ CTF_NAME_OFFSET (name
));
54 /* String table not loaded or corrupt offset. */
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. */
61 ctf_strraw (ctf_dict_t
*fp
, uint32_t name
)
63 return ctf_strraw_explicit (fp
, name
, NULL
);
66 /* Return a guaranteed-non-NULL pointer to the string with the given CTF
69 ctf_strptr (ctf_dict_t
*fp
, uint32_t name
)
71 const char *s
= ctf_strraw (fp
, name
);
72 return (s
!= NULL
? s
: "(?)");
75 /* Remove all refs to a given atom. */
77 ctf_str_purge_atom_refs (ctf_str_atom_t
*atom
)
79 ctf_str_atom_ref_t
*ref
, *next
;
81 for (ref
= ctf_list_next (&atom
->csa_refs
); ref
!= NULL
; ref
= next
)
83 next
= ctf_list_next (ref
);
84 ctf_list_delete (&atom
->csa_refs
, ref
);
89 /* Free an atom (only called on ctf_close().) */
91 ctf_str_free_atom (void *a
)
93 ctf_str_atom_t
*atom
= a
;
95 ctf_str_purge_atom_refs (atom
);
99 /* Create the atoms table. There is always at least one atom in it, the null
102 ctf_str_create_atoms (ctf_dict_t
*fp
)
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
)
109 if (!fp
->ctf_prov_strtab
)
110 fp
->ctf_prov_strtab
= ctf_dynhash_create (ctf_hash_integer
,
113 if (!fp
->ctf_prov_strtab
)
114 goto oom_prov_strtab
;
116 if (!fp
->ctf_str_pending_ref
)
117 fp
->ctf_str_pending_ref
= ctf_dynset_create (htab_hash_pointer
,
120 if (!fp
->ctf_str_pending_ref
)
121 goto oom_str_pending_ref
;
124 ctf_str_add (fp
, "");
131 ctf_dynhash_destroy (fp
->ctf_prov_strtab
);
132 fp
->ctf_prov_strtab
= NULL
;
134 ctf_dynset_destroy (fp
->ctf_str_pending_ref
);
135 fp
->ctf_str_pending_ref
= NULL
;
137 ctf_dynhash_destroy (fp
->ctf_str_atoms
);
138 fp
->ctf_str_atoms
= NULL
;
142 /* Destroy the atoms table. */
144 ctf_str_free_atoms (ctf_dict_t
*fp
)
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
);
151 #define CTF_STR_ADD_REF 0x1
152 #define CTF_STR_MAKE_PROVISIONAL 0x2
153 #define CTF_STR_PENDING_REF 0x4
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
)
165 ctf_str_atom_t
*atom
= NULL
;
166 ctf_str_atom_ref_t
*aref
= NULL
;
168 atom
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, str
);
170 if (flags
& CTF_STR_ADD_REF
)
172 if ((aref
= malloc (sizeof (struct ctf_str_atom_ref
))) == NULL
)
179 if (flags
& CTF_STR_ADD_REF
)
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
++;
188 if ((atom
= malloc (sizeof (struct ctf_str_atom
))) == NULL
)
190 memset (atom
, 0, sizeof (struct ctf_str_atom
));
192 if ((newstr
= strdup (str
)) == NULL
)
195 if (ctf_dynhash_insert (fp
->ctf_str_atoms
, newstr
, atom
) < 0)
198 atom
->csa_str
= newstr
;
199 atom
->csa_snapshot_id
= fp
->ctf_snapshots
;
201 if (flags
& CTF_STR_MAKE_PROVISIONAL
)
203 atom
->csa_offset
= fp
->ctf_str_prov_offset
;
205 if (ctf_dynhash_insert (fp
->ctf_prov_strtab
, (void *) (uintptr_t)
206 atom
->csa_offset
, (void *) atom
->csa_str
) < 0)
209 fp
->ctf_str_prov_offset
+= strlen (atom
->csa_str
) + 1;
212 if (flags
& CTF_STR_PENDING_REF
)
214 if (ctf_dynset_insert (fp
->ctf_str_pending_ref
, (void *) ref
) < 0)
217 else if (flags
& CTF_STR_ADD_REF
)
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
++;
227 ctf_dynhash_remove (fp
->ctf_str_atoms
, newstr
);
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.) */
240 ctf_str_add (ctf_dict_t
*fp
, const char *str
)
242 ctf_str_atom_t
*atom
;
247 atom
= ctf_str_add_ref_internal (fp
, str
, CTF_STR_MAKE_PROVISIONAL
, 0);
251 return atom
->csa_offset
;
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). */
258 ctf_str_add_ref (ctf_dict_t
*fp
, const char *str
, uint32_t *ref
)
260 ctf_str_atom_t
*atom
;
265 atom
= ctf_str_add_ref_internal (fp
, str
, CTF_STR_ADD_REF
266 | CTF_STR_MAKE_PROVISIONAL
, ref
);
270 return atom
->csa_offset
;
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. */
276 ctf_str_add_pending (ctf_dict_t
*fp
, const char *str
, uint32_t *ref
)
278 ctf_str_atom_t
*atom
;
283 atom
= ctf_str_add_ref_internal (fp
, str
, CTF_STR_PENDING_REF
284 | CTF_STR_MAKE_PROVISIONAL
, ref
);
288 return atom
->csa_offset
;
291 /* Add an external strtab reference at OFFSET. Returns zero if the addition
292 failed, nonzero otherwise. */
294 ctf_str_add_external (ctf_dict_t
*fp
, const char *str
, uint32_t offset
)
296 ctf_str_atom_t
*atom
;
301 atom
= ctf_str_add_ref_internal (fp
, str
, 0, 0);
305 atom
->csa_external_offset
= CTF_SET_STID (offset
, CTF_STRTAB_1
);
307 if (!fp
->ctf_syn_ext_strtab
)
308 fp
->ctf_syn_ext_strtab
= ctf_dynhash_create (ctf_hash_integer
,
311 if (!fp
->ctf_syn_ext_strtab
)
313 ctf_set_errno (fp
, ENOMEM
);
317 if (ctf_dynhash_insert (fp
->ctf_syn_ext_strtab
,
319 atom
->csa_external_offset
,
320 (void *) atom
->csa_str
) < 0)
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
);
331 /* Remove a single ref. */
333 ctf_str_remove_ref (ctf_dict_t
*fp
, const char *str
, uint32_t *ref
)
335 ctf_str_atom_ref_t
*aref
, *anext
;
336 ctf_str_atom_t
*atom
= NULL
;
338 atom
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, str
);
342 for (aref
= ctf_list_next (&atom
->csa_refs
); aref
!= NULL
; aref
= anext
)
344 anext
= ctf_list_next (aref
);
345 if (aref
->caf_ref
== ref
)
347 ctf_list_delete (&atom
->csa_refs
, aref
);
352 ctf_dynset_remove (fp
->ctf_str_pending_ref
, (void *) ref
);
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
360 ctf_str_rollback_atom (void *key _libctf_unused_
, void *value
, void *arg
)
362 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
363 ctf_snapshot_id_t
*id
= (ctf_snapshot_id_t
*) arg
;
365 return (atom
->csa_snapshot_id
> id
->snapshot_id
)
366 && (atom
->csa_external_offset
== 0);
369 /* Roll back, deleting all (internal) atoms created after a particular ID. */
371 ctf_str_rollback (ctf_dict_t
*fp
, ctf_snapshot_id_t id
)
373 ctf_dynhash_iter_remove (fp
->ctf_str_atoms
, ctf_str_rollback_atom
, &id
);
376 /* An adaptor around ctf_purge_atom_refs. */
378 ctf_str_purge_one_atom_refs (void *key _libctf_unused_
, void *value
,
379 void *arg _libctf_unused_
)
381 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
382 ctf_str_purge_atom_refs (atom
);
385 /* Remove all the recorded refs from the atoms table. */
387 ctf_str_purge_refs (ctf_dict_t
*fp
)
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;
394 /* Update a list of refs to the specified value. */
396 ctf_str_update_refs (ctf_str_atom_t
*refs
, uint32_t value
)
398 ctf_str_atom_ref_t
*ref
;
400 for (ref
= ctf_list_next (&refs
->csa_refs
); ref
!= NULL
;
401 ref
= ctf_list_next (ref
))
402 *(ref
->caf_ref
) = value
;
405 /* State shared across the strtab write process. */
406 typedef struct ctf_strtab_write_state
408 /* Strtab we are writing, and the number of strings in it. */
409 ctf_strs_writable_t
*strtab
;
412 /* Pointers to (existing) atoms in the atoms table, for qsorting. */
413 ctf_str_atom_t
**sorttab
;
415 /* Loop counter for sorttab population. */
418 /* The null-string atom (skipped during population). */
419 ctf_str_atom_t
*nullstr
;
420 } ctf_strtab_write_state_t
;
422 /* Count the number of entries in the strtab, and its length. */
424 ctf_str_count_strtab (void *key _libctf_unused_
, void *value
,
427 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
428 ctf_strtab_write_state_t
*s
= (ctf_strtab_write_state_t
*) arg
;
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
437 if (s
->nullstr
== atom
)
443 if (!ctf_list_empty_p (&atom
->csa_refs
))
445 if (!atom
->csa_external_offset
)
446 s
->strtab
->cts_len
+= strlen (atom
->csa_str
) + 1;
451 /* Populate the sorttab with pointers to the strtab atoms. */
453 ctf_str_populate_sorttab (void *key _libctf_unused_
, void *value
,
456 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
457 ctf_strtab_write_state_t
*s
= (ctf_strtab_write_state_t
*) arg
;
459 /* Skip the null string. */
460 if (s
->nullstr
== atom
)
463 /* Skip atoms with no refs. */
464 if (!ctf_list_empty_p (&atom
->csa_refs
))
465 s
->sorttab
[s
->i
++] = atom
;
468 /* Sort the strtab. */
470 ctf_str_sort_strtab (const void *a
, const void *b
)
472 ctf_str_atom_t
**one
= (ctf_str_atom_t
**) a
;
473 ctf_str_atom_t
**two
= (ctf_str_atom_t
**) b
;
475 return (strcmp ((*one
)->csa_str
, (*two
)->csa_str
));
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. */
484 ctf_str_write_strtab (ctf_dict_t
*fp
)
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
;
492 int any_external
= 0;
494 memset (&strtab
, 0, sizeof (struct ctf_strs_writable
));
495 memset (&s
, 0, sizeof (struct ctf_strtab_write_state
));
498 nullstr
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, "");
501 ctf_err_warn (fp
, 0, ECTF_INTERNAL
, _("null string not found in strtab"));
502 strtab
.cts_strs
= NULL
;
507 ctf_dynhash_iter (fp
->ctf_str_atoms
, ctf_str_count_strtab
, &s
);
508 strtab
.cts_len
++; /* For the null string. */
510 ctf_dprintf ("%lu bytes of strings in strtab.\n",
511 (unsigned long) strtab
.cts_len
);
513 /* Sort the strtab. Force the null string to be first. */
514 sorttab
= calloc (s
.strtab_count
, sizeof (ctf_str_atom_t
*));
518 sorttab
[0] = nullstr
;
521 ctf_dynhash_iter (fp
->ctf_str_atoms
, ctf_str_populate_sorttab
, &s
);
523 qsort (&sorttab
[1], s
.strtab_count
- 1, sizeof (ctf_str_atom_t
*),
524 ctf_str_sort_strtab
);
526 if ((strtab
.cts_strs
= malloc (strtab
.cts_len
)) == NULL
)
529 /* Update all refs: also update the strtab appropriately. */
530 for (i
= 0; i
< s
.strtab_count
; i
++)
532 if (sorttab
[i
]->csa_external_offset
)
534 /* External strtab entry. */
537 ctf_str_update_refs (sorttab
[i
], sorttab
[i
]->csa_external_offset
);
538 sorttab
[i
]->csa_offset
= sorttab
[i
]->csa_external_offset
;
542 /* Internal strtab entry with refs: actually add to the string
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;
555 ctf_dynhash_destroy (fp
->ctf_syn_ext_strtab
);
556 fp
->ctf_syn_ext_strtab
= NULL
;
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. */
563 ctf_dynhash_empty (fp
->ctf_prov_strtab
);
564 fp
->ctf_str_prov_offset
= strtab
.cts_len
+ 1;