123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588 |
- /* CTF string table management.
- Copyright (C) 2019-2022 Free Software Foundation, Inc.
- This file is part of libctf.
- libctf is free software; you can redistribute it and/or modify it under
- the terms of the GNU General Public License as published by the Free
- Software Foundation; either version 3, or (at your option) any later
- version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
- See the GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; see the file COPYING. If not see
- <http://www.gnu.org/licenses/>. */
- #include <ctf-impl.h>
- #include <string.h>
- #include <assert.h>
- /* Convert an encoded CTF string name into a pointer to a C string, using an
- explicit internal strtab rather than the fp-based one. */
- const char *
- ctf_strraw_explicit (ctf_dict_t *fp, uint32_t name, ctf_strs_t *strtab)
- {
- ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID (name)];
- if ((CTF_NAME_STID (name) == CTF_STRTAB_0) && (strtab != NULL))
- ctsp = strtab;
- /* If this name is in the external strtab, and there is a synthetic strtab,
- use it in preference. */
- if (CTF_NAME_STID (name) == CTF_STRTAB_1
- && fp->ctf_syn_ext_strtab != NULL)
- return ctf_dynhash_lookup (fp->ctf_syn_ext_strtab,
- (void *) (uintptr_t) name);
- /* If the name is in the internal strtab, and the offset is beyond the end of
- the ctsp->cts_len but below the ctf_str_prov_offset, this is a provisional
- string added by ctf_str_add*() but not yet built into a real strtab: get
- the value out of the ctf_prov_strtab. */
- if (CTF_NAME_STID (name) == CTF_STRTAB_0
- && name >= ctsp->cts_len && name < fp->ctf_str_prov_offset)
- return ctf_dynhash_lookup (fp->ctf_prov_strtab,
- (void *) (uintptr_t) name);
- if (ctsp->cts_strs != NULL && CTF_NAME_OFFSET (name) < ctsp->cts_len)
- return (ctsp->cts_strs + CTF_NAME_OFFSET (name));
- /* String table not loaded or corrupt offset. */
- return NULL;
- }
- /* Convert an encoded CTF string name into a pointer to a C string by looking
- up the appropriate string table buffer and then adding the offset. */
- const char *
- ctf_strraw (ctf_dict_t *fp, uint32_t name)
- {
- return ctf_strraw_explicit (fp, name, NULL);
- }
- /* Return a guaranteed-non-NULL pointer to the string with the given CTF
- name. */
- const char *
- ctf_strptr (ctf_dict_t *fp, uint32_t name)
- {
- const char *s = ctf_strraw (fp, name);
- return (s != NULL ? s : "(?)");
- }
- /* Remove all refs to a given atom. */
- static void
- ctf_str_purge_atom_refs (ctf_str_atom_t *atom)
- {
- ctf_str_atom_ref_t *ref, *next;
- for (ref = ctf_list_next (&atom->csa_refs); ref != NULL; ref = next)
- {
- next = ctf_list_next (ref);
- ctf_list_delete (&atom->csa_refs, ref);
- free (ref);
- }
- }
- /* Free an atom (only called on ctf_close().) */
- static void
- ctf_str_free_atom (void *a)
- {
- ctf_str_atom_t *atom = a;
- ctf_str_purge_atom_refs (atom);
- free (atom);
- }
- /* Create the atoms table. There is always at least one atom in it, the null
- string. */
- int
- ctf_str_create_atoms (ctf_dict_t *fp)
- {
- fp->ctf_str_atoms = ctf_dynhash_create (ctf_hash_string, ctf_hash_eq_string,
- free, ctf_str_free_atom);
- if (!fp->ctf_str_atoms)
- return -ENOMEM;
- if (!fp->ctf_prov_strtab)
- fp->ctf_prov_strtab = ctf_dynhash_create (ctf_hash_integer,
- ctf_hash_eq_integer,
- NULL, NULL);
- if (!fp->ctf_prov_strtab)
- goto oom_prov_strtab;
- if (!fp->ctf_str_pending_ref)
- fp->ctf_str_pending_ref = ctf_dynset_create (htab_hash_pointer,
- htab_eq_pointer,
- NULL);
- if (!fp->ctf_str_pending_ref)
- goto oom_str_pending_ref;
- errno = 0;
- ctf_str_add (fp, "");
- if (errno == ENOMEM)
- goto oom_str_add;
- return 0;
- oom_str_add:
- ctf_dynhash_destroy (fp->ctf_prov_strtab);
- fp->ctf_prov_strtab = NULL;
- oom_str_pending_ref:
- ctf_dynset_destroy (fp->ctf_str_pending_ref);
- fp->ctf_str_pending_ref = NULL;
- oom_prov_strtab:
- ctf_dynhash_destroy (fp->ctf_str_atoms);
- fp->ctf_str_atoms = NULL;
- return -ENOMEM;
- }
- /* Destroy the atoms table. */
- void
- ctf_str_free_atoms (ctf_dict_t *fp)
- {
- ctf_dynhash_destroy (fp->ctf_prov_strtab);
- ctf_dynhash_destroy (fp->ctf_str_atoms);
- ctf_dynset_destroy (fp->ctf_str_pending_ref);
- }
- #define CTF_STR_ADD_REF 0x1
- #define CTF_STR_MAKE_PROVISIONAL 0x2
- #define CTF_STR_PENDING_REF 0x4
- /* Add a string to the atoms table, copying the passed-in string. Return the
- atom added. Return NULL only when out of memory (and do not touch the
- passed-in string in that case). Possibly augment the ref list with the
- passed-in ref. Possibly add a provisional entry for this string to the
- provisional strtab. */
- static ctf_str_atom_t *
- ctf_str_add_ref_internal (ctf_dict_t *fp, const char *str,
- int flags, uint32_t *ref)
- {
- char *newstr = NULL;
- ctf_str_atom_t *atom = NULL;
- ctf_str_atom_ref_t *aref = NULL;
- atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
- if (flags & CTF_STR_ADD_REF)
- {
- if ((aref = malloc (sizeof (struct ctf_str_atom_ref))) == NULL)
- return NULL;
- aref->caf_ref = ref;
- }
- if (atom)
- {
- if (flags & CTF_STR_ADD_REF)
- {
- ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
- ctf_list_append (&atom->csa_refs, aref);
- fp->ctf_str_num_refs++;
- }
- return atom;
- }
- if ((atom = malloc (sizeof (struct ctf_str_atom))) == NULL)
- goto oom;
- memset (atom, 0, sizeof (struct ctf_str_atom));
- if ((newstr = strdup (str)) == NULL)
- goto oom;
- if (ctf_dynhash_insert (fp->ctf_str_atoms, newstr, atom) < 0)
- goto oom;
- atom->csa_str = newstr;
- atom->csa_snapshot_id = fp->ctf_snapshots;
- if (flags & CTF_STR_MAKE_PROVISIONAL)
- {
- atom->csa_offset = fp->ctf_str_prov_offset;
- if (ctf_dynhash_insert (fp->ctf_prov_strtab, (void *) (uintptr_t)
- atom->csa_offset, (void *) atom->csa_str) < 0)
- goto oom;
- fp->ctf_str_prov_offset += strlen (atom->csa_str) + 1;
- }
- if (flags & CTF_STR_PENDING_REF)
- {
- if (ctf_dynset_insert (fp->ctf_str_pending_ref, (void *) ref) < 0)
- goto oom;
- }
- else if (flags & CTF_STR_ADD_REF)
- {
- ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
- ctf_list_append (&atom->csa_refs, aref);
- fp->ctf_str_num_refs++;
- }
- return atom;
- oom:
- if (newstr)
- ctf_dynhash_remove (fp->ctf_str_atoms, newstr);
- free (atom);
- free (aref);
- free (newstr);
- ctf_set_errno (fp, ENOMEM);
- return NULL;
- }
- /* Add a string to the atoms table, without augmenting the ref list for this
- string: return a 'provisional offset' which can be used to return this string
- until ctf_str_write_strtab is called, or 0 on failure. (Everywhere the
- provisional offset is assigned to should be added as a ref using
- ctf_str_add_ref() as well.) */
- uint32_t
- ctf_str_add (ctf_dict_t *fp, const char *str)
- {
- ctf_str_atom_t *atom;
- if (!str)
- str = "";
- atom = ctf_str_add_ref_internal (fp, str, CTF_STR_MAKE_PROVISIONAL, 0);
- if (!atom)
- return 0;
- return atom->csa_offset;
- }
- /* Like ctf_str_add(), but additionally augment the atom's refs list with the
- passed-in ref, whether or not the string is already present. There is no
- attempt to deduplicate the refs list (but duplicates are harmless). */
- uint32_t
- ctf_str_add_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
- {
- ctf_str_atom_t *atom;
- if (!str)
- str = "";
- atom = ctf_str_add_ref_internal (fp, str, CTF_STR_ADD_REF
- | CTF_STR_MAKE_PROVISIONAL, ref);
- if (!atom)
- return 0;
- return atom->csa_offset;
- }
- /* Like ctf_str_add_ref(), but notes that this memory location must be added as
- a ref by a later serialization phase, rather than adding it itself. */
- uint32_t
- ctf_str_add_pending (ctf_dict_t *fp, const char *str, uint32_t *ref)
- {
- ctf_str_atom_t *atom;
- if (!str)
- str = "";
- atom = ctf_str_add_ref_internal (fp, str, CTF_STR_PENDING_REF
- | CTF_STR_MAKE_PROVISIONAL, ref);
- if (!atom)
- return 0;
- return atom->csa_offset;
- }
- /* Note that a pending ref now located at NEW_REF has moved by BYTES bytes. */
- int
- ctf_str_move_pending (ctf_dict_t *fp, uint32_t *new_ref, ptrdiff_t bytes)
- {
- if (bytes == 0)
- return 0;
- if (ctf_dynset_insert (fp->ctf_str_pending_ref, (void *) new_ref) < 0)
- return (ctf_set_errno (fp, ENOMEM));
- ctf_dynset_remove (fp->ctf_str_pending_ref,
- (void *) ((signed char *) new_ref - bytes));
- return 0;
- }
- /* Add an external strtab reference at OFFSET. Returns zero if the addition
- failed, nonzero otherwise. */
- int
- ctf_str_add_external (ctf_dict_t *fp, const char *str, uint32_t offset)
- {
- ctf_str_atom_t *atom;
- if (!str)
- str = "";
- atom = ctf_str_add_ref_internal (fp, str, 0, 0);
- if (!atom)
- return 0;
- atom->csa_external_offset = CTF_SET_STID (offset, CTF_STRTAB_1);
- if (!fp->ctf_syn_ext_strtab)
- fp->ctf_syn_ext_strtab = ctf_dynhash_create (ctf_hash_integer,
- ctf_hash_eq_integer,
- NULL, NULL);
- if (!fp->ctf_syn_ext_strtab)
- {
- ctf_set_errno (fp, ENOMEM);
- return 0;
- }
- if (ctf_dynhash_insert (fp->ctf_syn_ext_strtab,
- (void *) (uintptr_t)
- atom->csa_external_offset,
- (void *) atom->csa_str) < 0)
- {
- /* No need to bother freeing the syn_ext_strtab: it will get freed at
- ctf_str_write_strtab time if unreferenced. */
- ctf_set_errno (fp, ENOMEM);
- return 0;
- }
- return 1;
- }
- /* Remove a single ref. */
- void
- ctf_str_remove_ref (ctf_dict_t *fp, const char *str, uint32_t *ref)
- {
- ctf_str_atom_ref_t *aref, *anext;
- ctf_str_atom_t *atom = NULL;
- atom = ctf_dynhash_lookup (fp->ctf_str_atoms, str);
- if (!atom)
- return;
- for (aref = ctf_list_next (&atom->csa_refs); aref != NULL; aref = anext)
- {
- anext = ctf_list_next (aref);
- if (aref->caf_ref == ref)
- {
- ctf_list_delete (&atom->csa_refs, aref);
- free (aref);
- }
- }
- ctf_dynset_remove (fp->ctf_str_pending_ref, (void *) ref);
- }
- /* A ctf_dynhash_iter_remove() callback that removes atoms later than a given
- snapshot ID. External atoms are never removed, because they came from the
- linker string table and are still present even if you roll back type
- additions. */
- static int
- ctf_str_rollback_atom (void *key _libctf_unused_, void *value, void *arg)
- {
- ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
- ctf_snapshot_id_t *id = (ctf_snapshot_id_t *) arg;
- return (atom->csa_snapshot_id > id->snapshot_id)
- && (atom->csa_external_offset == 0);
- }
- /* Roll back, deleting all (internal) atoms created after a particular ID. */
- void
- ctf_str_rollback (ctf_dict_t *fp, ctf_snapshot_id_t id)
- {
- ctf_dynhash_iter_remove (fp->ctf_str_atoms, ctf_str_rollback_atom, &id);
- }
- /* An adaptor around ctf_purge_atom_refs. */
- static void
- ctf_str_purge_one_atom_refs (void *key _libctf_unused_, void *value,
- void *arg _libctf_unused_)
- {
- ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
- ctf_str_purge_atom_refs (atom);
- }
- /* Remove all the recorded refs from the atoms table. */
- void
- ctf_str_purge_refs (ctf_dict_t *fp)
- {
- if (fp->ctf_str_num_refs > 0)
- ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_purge_one_atom_refs, NULL);
- fp->ctf_str_num_refs = 0;
- }
- /* Update a list of refs to the specified value. */
- static void
- ctf_str_update_refs (ctf_str_atom_t *refs, uint32_t value)
- {
- ctf_str_atom_ref_t *ref;
- for (ref = ctf_list_next (&refs->csa_refs); ref != NULL;
- ref = ctf_list_next (ref))
- *(ref->caf_ref) = value;
- }
- /* State shared across the strtab write process. */
- typedef struct ctf_strtab_write_state
- {
- /* Strtab we are writing, and the number of strings in it. */
- ctf_strs_writable_t *strtab;
- size_t strtab_count;
- /* Pointers to (existing) atoms in the atoms table, for qsorting. */
- ctf_str_atom_t **sorttab;
- /* Loop counter for sorttab population. */
- size_t i;
- /* The null-string atom (skipped during population). */
- ctf_str_atom_t *nullstr;
- } ctf_strtab_write_state_t;
- /* Count the number of entries in the strtab, and its length. */
- static void
- ctf_str_count_strtab (void *key _libctf_unused_, void *value,
- void *arg)
- {
- ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
- ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
- /* We only factor in the length of items that have no offset and have refs:
- other items are in the external strtab, or will simply not be written out
- at all. They still contribute to the total count, though, because we still
- have to sort them. We add in the null string's length explicitly, outside
- this function, since it is explicitly written out even if it has no refs at
- all. */
- if (s->nullstr == atom)
- {
- s->strtab_count++;
- return;
- }
- if (!ctf_list_empty_p (&atom->csa_refs))
- {
- if (!atom->csa_external_offset)
- s->strtab->cts_len += strlen (atom->csa_str) + 1;
- s->strtab_count++;
- }
- }
- /* Populate the sorttab with pointers to the strtab atoms. */
- static void
- ctf_str_populate_sorttab (void *key _libctf_unused_, void *value,
- void *arg)
- {
- ctf_str_atom_t *atom = (ctf_str_atom_t *) value;
- ctf_strtab_write_state_t *s = (ctf_strtab_write_state_t *) arg;
- /* Skip the null string. */
- if (s->nullstr == atom)
- return;
- /* Skip atoms with no refs. */
- if (!ctf_list_empty_p (&atom->csa_refs))
- s->sorttab[s->i++] = atom;
- }
- /* Sort the strtab. */
- static int
- ctf_str_sort_strtab (const void *a, const void *b)
- {
- ctf_str_atom_t **one = (ctf_str_atom_t **) a;
- ctf_str_atom_t **two = (ctf_str_atom_t **) b;
- return (strcmp ((*one)->csa_str, (*two)->csa_str));
- }
- /* Write out and return a strtab containing all strings with recorded refs,
- adjusting the refs to refer to the corresponding string. The returned strtab
- may be NULL on error. Also populate the synthetic strtab with mappings from
- external strtab offsets to names, so we can look them up with ctf_strptr().
- Only external strtab offsets with references are added. */
- ctf_strs_writable_t
- ctf_str_write_strtab (ctf_dict_t *fp)
- {
- ctf_strs_writable_t strtab;
- ctf_str_atom_t *nullstr;
- uint32_t cur_stroff = 0;
- ctf_strtab_write_state_t s;
- ctf_str_atom_t **sorttab;
- size_t i;
- int any_external = 0;
- memset (&strtab, 0, sizeof (struct ctf_strs_writable));
- memset (&s, 0, sizeof (struct ctf_strtab_write_state));
- s.strtab = &strtab;
- nullstr = ctf_dynhash_lookup (fp->ctf_str_atoms, "");
- if (!nullstr)
- {
- ctf_err_warn (fp, 0, ECTF_INTERNAL, _("null string not found in strtab"));
- strtab.cts_strs = NULL;
- return strtab;
- }
- s.nullstr = nullstr;
- ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_count_strtab, &s);
- strtab.cts_len++; /* For the null string. */
- ctf_dprintf ("%lu bytes of strings in strtab.\n",
- (unsigned long) strtab.cts_len);
- /* Sort the strtab. Force the null string to be first. */
- sorttab = calloc (s.strtab_count, sizeof (ctf_str_atom_t *));
- if (!sorttab)
- goto oom;
- sorttab[0] = nullstr;
- s.i = 1;
- s.sorttab = sorttab;
- ctf_dynhash_iter (fp->ctf_str_atoms, ctf_str_populate_sorttab, &s);
- qsort (&sorttab[1], s.strtab_count - 1, sizeof (ctf_str_atom_t *),
- ctf_str_sort_strtab);
- if ((strtab.cts_strs = malloc (strtab.cts_len)) == NULL)
- goto oom_sorttab;
- /* Update all refs: also update the strtab appropriately. */
- for (i = 0; i < s.strtab_count; i++)
- {
- if (sorttab[i]->csa_external_offset)
- {
- /* External strtab entry. */
- any_external = 1;
- ctf_str_update_refs (sorttab[i], sorttab[i]->csa_external_offset);
- sorttab[i]->csa_offset = sorttab[i]->csa_external_offset;
- }
- else
- {
- /* Internal strtab entry with refs: actually add to the string
- table. */
- ctf_str_update_refs (sorttab[i], cur_stroff);
- sorttab[i]->csa_offset = cur_stroff;
- strcpy (&strtab.cts_strs[cur_stroff], sorttab[i]->csa_str);
- cur_stroff += strlen (sorttab[i]->csa_str) + 1;
- }
- }
- free (sorttab);
- if (!any_external)
- {
- ctf_dynhash_destroy (fp->ctf_syn_ext_strtab);
- fp->ctf_syn_ext_strtab = NULL;
- }
- /* All the provisional strtab entries are now real strtab entries, and
- ctf_strptr() will find them there. The provisional offset now starts right
- beyond the new end of the strtab. */
- ctf_dynhash_empty (fp->ctf_prov_strtab);
- fp->ctf_str_prov_offset = strtab.cts_len + 1;
- return strtab;
- oom_sorttab:
- free (sorttab);
- oom:
- return strtab;
- }
|