Deduplicator improvements
Multithread hashing phase
This phase often consumes 80%+ of the time needed to dedup. Adding threading support to libctf itself is really hard because we'd have to make it work on mingw, etc, but we can implement hooks that ctf_link users can call to invoke threading functions to speed up hashing. GNU ld, as one such consumer, can probably use those too, on platforms we know support pthreads (which are most ELF platforms we care about, these days, thus most which have linker CTF support at all right now). With no more than pthread_create, pthread_join, and a couple of mutexes, we can do hashing in parallel and override the populate_fun to just store a linked list of arguments to the *real* populate_fun, which is called in the main thread directly from ctf_dedup, after hashing is complete.
A few things (like decorated name construction etc) are inserted into dynhashes during the hashing phase, but even those get exponentially less common as time goes by (since ctf_decorate_type_name only inserts names it doesn't already know about, and most names are duplicated many times over in different TUs). The only really expensive one is the citers population, since that's done for every hashing phase -- it should probably be rethought as something else, or emitted into per-thread dynhashes and then merged post facto (a trivial operation).
Erasure of unreferenced nameless types
Implement a GC pass so that unreferenced types with no name and all types that depend on them are erased. (May conflict with using nameless types as a substitute hidden bit...)
Deduplicator cycle detection
The dedup machinery can still get stuck in a cycle if the compiler emits corrupted CTF, e.g. a cycle of reference types (e.g. volatile -> const -> volatile) pointing to each other, or a cycle that contains only non-tagged structs/unions (maybe a tag got lost, one null byte in the wrong place could do it). Hellman came up with an algorithm we can adjust to spot this case very cheaply.
We keep a cycle-detection slot in which we remember a single GID. Every time the recursion depth in the hashing machinery passes 2^n, either when winding or unwinding, we blank that GID. Whenever we recurse downwards, and we are not looking at a stub (which, obviously, might be a cycle member legitimately, and we're going to break it), if the slot is not blank and is the same as the GID we are looking at now, this is a cycle. If the slot is blank, fill it out.
That suffices. It can take up to half the current recursion depth to spot a cycle, but it will always spot it in the end.
Use this in ctf_type_rvisit et al as well, so that we return a nice error (or stop recursing?) if we hit a cycle.
Reduce spurious forward creation
Currently we create forwards in the shared dict whenever anything refers to a conflicted type for which stubs are creatable at all. But in share-duplicated mode, we are sometimes creating these when the "conflicted" type actually has only one reference and should be in the shared dict. Investigate why and fix it. (Example: the kernel's struct mnt_namespace.)
Deduplicate on addition to dynamic dicts
It would be easy to hash types on addition to dynamic dicts using the exact same code that the deduplicator already uses to hash types during deduplication. We can store those and then automatically return existing types if a hash matches, giving us immediate dedup of things like cvr-qual and pointer chains and a possible large memory saving for some use cases.
Enum improvements
Our handling of enums is still a bit limited: we consider an enum conflicting whenever any enumerator within it appears in any other enum, even if that other enumerator has the same value. We should probably track enum values and mark enumerators conflicting only if an enumerator appearing within it appears within another enum with a different value.
Complete
Consider enumerators with conflicting enumerands to be conflicting (pushed 2024-06-18)
Right now we don't consider enumerands at all: but if two enumerators have the same enumerand with different values, no C translation unit could include both and references to the enumerand would have unclear value. Clearly this is conflicting!
(Modified on 2024-07-31: now rolled back slightly, since some callers actually expect to be able to create enums with conflicting enumerators: by default this is now permitted unless a new call ctf_dict_set_flag (fp, CTF_STRICT_NO_DUP_ENUMERATORS, 1) is issued.)