libctf, string: split the movable refs out of the ref list

In commit 149ce5c263616e65 we introduced the concept of "movable" refs,
which are refs that can be moved in batches, to let us maintain valid ref
lists even when adding refs to blocks of memory that can be realloced (which
is any type containing a vlen which can expand, like names contained within
enum or struct members).  Movable refs need a backpointer to the movable
refs dynhash for this dict; since non-movable refs are very common, we tried
to save memory by having a slightly bigger struct for moveable refs with a
backpointer in it, and casting appropriately, indicating which sort of ref
we were dealing with via a flag on the atom.

Unfortunately this doesn't work reliably, because you can perfectly well
have a string ("foo", say) which has both non-movable refs (say, an external
symbol and a variable name) and movable refs (say, a structure member name)
to the same atom.  Indicate which struct we're dealing with with an atom
flag and suddenly you're casting a ctf_str_atom_ref to a
ctf_str_atom_ref_movable (which is bigger) and dereferencing random memory
off the end of it and interpreting it as a backpointer to the movable refs
dynhash.  This is unlikely to work well.

So bite the bullet and split refs into two separate lists, one for movable
refs, one for immovable refs. It means some annoying code duplication, but
there's not very much of it, and it means we can keep the movable refs
hashtab (which in turn means we don't have to do linear searches to find all
relevant refs when moving refs, which in turn means that
structure/union/enum member additions remain amortized O(n) time, not
O(n^2).

Callers can now purge movable and non-movable refs independently of each
other.  We don't use this yet, but a use is coming.

libctf/
	* ctf-impl.h (CTF_STR_ATOM_MOVABLE): Delete.
        (struct ctf_str_atom) [csa_movable_refs]: New.
	(struct ctf_dict): Adjust comment.
	(ctf_str_purge_refs): Add MOVABLE arg.
	* ctf-string.c (ctf_str_purge_movable_atom_refs): Split out of...
        (ctf_str_purge_atom_refs): ... this.
	(ctf_str_free_atom): Call it.
	(ctf_str_purge_one_atom_refs): Likewise.
	(aref_create): Adjust accordingly.
	(ctf_str_move_refs): Likewise.
	(ctf_str_remove_ref): Remove movable refs too, including
	deleting the ref from ctf_str_movable_refs.
	(ctf_str_purge_refs): Add MOVABLE arg.
	(ctf_str_update_refs): Update movable refs.
	(ctf_str_write_strtab): Check, and purge, movable refs.

0 files changed, 0 insertions, 0 deletions