1 /* CTF string table management.
2 Copyright (C) 2019-2020 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
== NULL
)
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
;
117 ctf_str_add (fp
, "");
124 ctf_dynhash_destroy (fp
->ctf_prov_strtab
);
125 fp
->ctf_prov_strtab
= NULL
;
127 ctf_dynhash_destroy (fp
->ctf_str_atoms
);
128 fp
->ctf_str_atoms
= NULL
;
132 /* Destroy the atoms table. */
134 ctf_str_free_atoms (ctf_dict_t
*fp
)
136 ctf_dynhash_destroy (fp
->ctf_prov_strtab
);
137 ctf_dynhash_destroy (fp
->ctf_str_atoms
);
140 /* Add a string to the atoms table, copying the passed-in string. Return the
141 atom added. Return NULL only when out of memory (and do not touch the
142 passed-in string in that case). Possibly augment the ref list with the
143 passed-in ref. Possibly add a provisional entry for this string to the
144 provisional strtab. */
145 static ctf_str_atom_t
*
146 ctf_str_add_ref_internal (ctf_dict_t
*fp
, const char *str
,
147 int add_ref
, int make_provisional
, uint32_t *ref
)
150 ctf_str_atom_t
*atom
= NULL
;
151 ctf_str_atom_ref_t
*aref
= NULL
;
153 atom
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, str
);
157 if ((aref
= malloc (sizeof (struct ctf_str_atom_ref
))) == NULL
)
166 ctf_list_append (&atom
->csa_refs
, aref
);
167 fp
->ctf_str_num_refs
++;
172 if ((atom
= malloc (sizeof (struct ctf_str_atom
))) == NULL
)
174 memset (atom
, 0, sizeof (struct ctf_str_atom
));
176 if ((newstr
= strdup (str
)) == NULL
)
179 if (ctf_dynhash_insert (fp
->ctf_str_atoms
, newstr
, atom
) < 0)
182 atom
->csa_str
= newstr
;
183 atom
->csa_snapshot_id
= fp
->ctf_snapshots
;
185 if (make_provisional
)
187 atom
->csa_offset
= fp
->ctf_str_prov_offset
;
189 if (ctf_dynhash_insert (fp
->ctf_prov_strtab
, (void *) (uintptr_t)
190 atom
->csa_offset
, (void *) atom
->csa_str
) < 0)
193 fp
->ctf_str_prov_offset
+= strlen (atom
->csa_str
) + 1;
198 ctf_list_append (&atom
->csa_refs
, aref
);
199 fp
->ctf_str_num_refs
++;
205 ctf_dynhash_remove (fp
->ctf_str_atoms
, newstr
);
212 /* Add a string to the atoms table, without augmenting the ref list for this
213 string: return a 'provisional offset' which can be used to return this string
214 until ctf_str_write_strtab is called, or 0 on failure. (Everywhere the
215 provisional offset is assigned to should be added as a ref using
216 ctf_str_add_ref() as well.) */
218 ctf_str_add (ctf_dict_t
*fp
, const char *str
)
220 ctf_str_atom_t
*atom
;
224 atom
= ctf_str_add_ref_internal (fp
, str
, FALSE
, TRUE
, 0);
228 return atom
->csa_offset
;
231 /* Like ctf_str_add(), but additionally augment the atom's refs list with the
232 passed-in ref, whether or not the string is already present. There is no
233 attempt to deduplicate the refs list (but duplicates are harmless). */
235 ctf_str_add_ref (ctf_dict_t
*fp
, const char *str
, uint32_t *ref
)
237 ctf_str_atom_t
*atom
;
241 atom
= ctf_str_add_ref_internal (fp
, str
, TRUE
, TRUE
, ref
);
245 return atom
->csa_offset
;
248 /* Add an external strtab reference at OFFSET. Returns zero if the addition
249 failed, nonzero otherwise. */
251 ctf_str_add_external (ctf_dict_t
*fp
, const char *str
, uint32_t offset
)
253 ctf_str_atom_t
*atom
;
257 atom
= ctf_str_add_ref_internal (fp
, str
, FALSE
, FALSE
, 0);
261 atom
->csa_external_offset
= CTF_SET_STID (offset
, CTF_STRTAB_1
);
265 /* Remove a single ref. */
267 ctf_str_remove_ref (ctf_dict_t
*fp
, const char *str
, uint32_t *ref
)
269 ctf_str_atom_ref_t
*aref
, *anext
;
270 ctf_str_atom_t
*atom
= NULL
;
272 atom
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, str
);
276 for (aref
= ctf_list_next (&atom
->csa_refs
); aref
!= NULL
; aref
= anext
)
278 anext
= ctf_list_next (aref
);
279 if (aref
->caf_ref
== ref
)
281 ctf_list_delete (&atom
->csa_refs
, aref
);
287 /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
290 ctf_str_rollback_atom (void *key _libctf_unused_
, void *value
, void *arg
)
292 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
293 ctf_snapshot_id_t
*id
= (ctf_snapshot_id_t
*) arg
;
295 return (atom
->csa_snapshot_id
> id
->snapshot_id
);
298 /* Roll back, deleting all atoms created after a particular ID. */
300 ctf_str_rollback (ctf_dict_t
*fp
, ctf_snapshot_id_t id
)
302 ctf_dynhash_iter_remove (fp
->ctf_str_atoms
, ctf_str_rollback_atom
, &id
);
305 /* An adaptor around ctf_purge_atom_refs. */
307 ctf_str_purge_one_atom_refs (void *key _libctf_unused_
, void *value
,
308 void *arg _libctf_unused_
)
310 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
311 ctf_str_purge_atom_refs (atom
);
314 /* Remove all the recorded refs from the atoms table. */
316 ctf_str_purge_refs (ctf_dict_t
*fp
)
318 if (fp
->ctf_str_num_refs
> 0)
319 ctf_dynhash_iter (fp
->ctf_str_atoms
, ctf_str_purge_one_atom_refs
, NULL
);
320 fp
->ctf_str_num_refs
= 0;
323 /* Update a list of refs to the specified value. */
325 ctf_str_update_refs (ctf_str_atom_t
*refs
, uint32_t value
)
327 ctf_str_atom_ref_t
*ref
;
329 for (ref
= ctf_list_next (&refs
->csa_refs
); ref
!= NULL
;
330 ref
= ctf_list_next (ref
))
331 *(ref
->caf_ref
) = value
;
334 /* State shared across the strtab write process. */
335 typedef struct ctf_strtab_write_state
337 /* Strtab we are writing, and the number of strings in it. */
338 ctf_strs_writable_t
*strtab
;
341 /* Pointers to (existing) atoms in the atoms table, for qsorting. */
342 ctf_str_atom_t
**sorttab
;
344 /* Loop counter for sorttab population. */
347 /* The null-string atom (skipped during population). */
348 ctf_str_atom_t
*nullstr
;
349 } ctf_strtab_write_state_t
;
351 /* Count the number of entries in the strtab, and its length. */
353 ctf_str_count_strtab (void *key _libctf_unused_
, void *value
,
356 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
357 ctf_strtab_write_state_t
*s
= (ctf_strtab_write_state_t
*) arg
;
359 /* We only factor in the length of items that have no offset and have refs:
360 other items are in the external strtab, or will simply not be written out
361 at all. They still contribute to the total count, though, because we still
362 have to sort them. We add in the null string's length explicitly, outside
363 this function, since it is explicitly written out even if it has no refs at
366 if (s
->nullstr
== atom
)
372 if (!ctf_list_empty_p (&atom
->csa_refs
))
374 if (!atom
->csa_external_offset
)
375 s
->strtab
->cts_len
+= strlen (atom
->csa_str
) + 1;
380 /* Populate the sorttab with pointers to the strtab atoms. */
382 ctf_str_populate_sorttab (void *key _libctf_unused_
, void *value
,
385 ctf_str_atom_t
*atom
= (ctf_str_atom_t
*) value
;
386 ctf_strtab_write_state_t
*s
= (ctf_strtab_write_state_t
*) arg
;
388 /* Skip the null string. */
389 if (s
->nullstr
== atom
)
392 /* Skip atoms with no refs. */
393 if (!ctf_list_empty_p (&atom
->csa_refs
))
394 s
->sorttab
[s
->i
++] = atom
;
397 /* Sort the strtab. */
399 ctf_str_sort_strtab (const void *a
, const void *b
)
401 ctf_str_atom_t
**one
= (ctf_str_atom_t
**) a
;
402 ctf_str_atom_t
**two
= (ctf_str_atom_t
**) b
;
404 return (strcmp ((*one
)->csa_str
, (*two
)->csa_str
));
407 /* Write out and return a strtab containing all strings with recorded refs,
408 adjusting the refs to refer to the corresponding string. The returned strtab
409 may be NULL on error. Also populate the synthetic strtab with mappings from
410 external strtab offsets to names, so we can look them up with ctf_strptr().
411 Only external strtab offsets with references are added. */
413 ctf_str_write_strtab (ctf_dict_t
*fp
)
415 ctf_strs_writable_t strtab
;
416 ctf_str_atom_t
*nullstr
;
417 uint32_t cur_stroff
= 0;
418 ctf_strtab_write_state_t s
;
419 ctf_str_atom_t
**sorttab
;
421 int any_external
= 0;
423 memset (&strtab
, 0, sizeof (struct ctf_strs_writable
));
424 memset (&s
, 0, sizeof (struct ctf_strtab_write_state
));
427 nullstr
= ctf_dynhash_lookup (fp
->ctf_str_atoms
, "");
430 ctf_err_warn (fp
, 0, ECTF_INTERNAL
, _("null string not found in strtab"));
431 strtab
.cts_strs
= NULL
;
436 ctf_dynhash_iter (fp
->ctf_str_atoms
, ctf_str_count_strtab
, &s
);
437 strtab
.cts_len
++; /* For the null string. */
439 ctf_dprintf ("%lu bytes of strings in strtab.\n",
440 (unsigned long) strtab
.cts_len
);
442 /* Sort the strtab. Force the null string to be first. */
443 sorttab
= calloc (s
.strtab_count
, sizeof (ctf_str_atom_t
*));
447 sorttab
[0] = nullstr
;
450 ctf_dynhash_iter (fp
->ctf_str_atoms
, ctf_str_populate_sorttab
, &s
);
452 qsort (&sorttab
[1], s
.strtab_count
- 1, sizeof (ctf_str_atom_t
*),
453 ctf_str_sort_strtab
);
455 if ((strtab
.cts_strs
= malloc (strtab
.cts_len
)) == NULL
)
458 if (!fp
->ctf_syn_ext_strtab
)
459 fp
->ctf_syn_ext_strtab
= ctf_dynhash_create (ctf_hash_integer
,
462 if (!fp
->ctf_syn_ext_strtab
)
465 /* Update all refs: also update the strtab appropriately. */
466 for (i
= 0; i
< s
.strtab_count
; i
++)
468 if (sorttab
[i
]->csa_external_offset
)
470 /* External strtab entry: populate the synthetic external strtab.
472 This is safe because you cannot ctf_rollback to before the point
473 when a ctf_update is done, and the strtab is written at ctf_update
474 time. So any atoms we reference here are sure to stick around
475 until ctf_dict_close. */
478 ctf_str_update_refs (sorttab
[i
], sorttab
[i
]->csa_external_offset
);
479 if (ctf_dynhash_insert (fp
->ctf_syn_ext_strtab
,
481 sorttab
[i
]->csa_external_offset
,
482 (void *) sorttab
[i
]->csa_str
) < 0)
484 sorttab
[i
]->csa_offset
= sorttab
[i
]->csa_external_offset
;
488 /* Internal strtab entry with refs: actually add to the string
491 ctf_str_update_refs (sorttab
[i
], cur_stroff
);
492 sorttab
[i
]->csa_offset
= cur_stroff
;
493 strcpy (&strtab
.cts_strs
[cur_stroff
], sorttab
[i
]->csa_str
);
494 cur_stroff
+= strlen (sorttab
[i
]->csa_str
) + 1;
501 ctf_dynhash_destroy (fp
->ctf_syn_ext_strtab
);
502 fp
->ctf_syn_ext_strtab
= NULL
;
505 /* All the provisional strtab entries are now real strtab entries, and
506 ctf_strptr() will find them there. The provisional offset now starts right
507 beyond the new end of the strtab. */
509 ctf_dynhash_empty (fp
->ctf_prov_strtab
);
510 fp
->ctf_str_prov_offset
= strtab
.cts_len
+ 1;
514 free (strtab
.cts_strs
);
515 strtab
.cts_strs
= NULL
;