https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109161
Nix <nix at esperi dot org.uk> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |nix at esperi dot org.uk
--- Comment #2 from Nix <nix at esperi dot org.uk> ---
It definitely shouldn't hang for invalid input, but that sort of proof against
invalid input isn't even implemented for the deduplicator yet, let alone every
other thing that recurses over the type graph. It's on the todo list... and
it's not specific to objdump at all: ctf_dump (objdump/readelf),
ctf_type_rvisit, ctf_type_compat, even foundational libctf stuff like
ctf_type_resolve would hang if, say, we had a CTF_K_CONST node pointing to
itself, even indirectly. This does mean that anything we use to detect cycles
must be *cheap*.
Now I was assuming I could only implement cycle-detection efficiently for the
deduplicator (which would usually suffice, since linking is the first thing
that is usually done to compiler-generated CTF) -- but it occurs to me now that
I could use a similar technique in ctf_type_rvisit, which will handle ctf_dump:
I can probably do the same for the other recursive type-traversing functions,
and handle all of them with the same cycle-detection code, and then CTF
manipulation on raw object files would be safe against cycles too. The
algorithm in question (one of Hellman's more obscure) cannot guarantee
immediate detection of cycles, but it will always detect them eventually, which
is good enough for this application. That's the price we pay for spotting
cycles in constant space with almost no time overhead for the common, acyclic
case.
