ctf: speed up dwarf2ctf by avoiding ctf_update() calls

ctf: speed up dwarf2ctf by avoiding ctf_update() calls

By far the slowest operation in dwarf2ctf is ctf_update().  This operation
serializes all CTF data then essentially reopens the CTF file using that data.
For large CTF files like the vmlinux and shared type repositories this is
extremely slow, yet we do it between every top-level type and variable and
sometimes even more often than that.  We are doing this for three reasons:

 - firstly, in case of error we want to be able to throw away the erroneous
   type and any new types we may have added that it depends on but nothing
   else does.  libdtrace-ctf's only API for this is ctf_discard(), which
   throws away all types added since the most recent ctf_update(): so we
   must call ctf_update() frequently just to give a point to discard to.

 - secondly, whenever a new structure is encountered we need to count the number
   of members in it to tell whether it is at least as large as any
   previously-encountered instance in scope in this CTF file or the shared one,
   and if it is, to note that the already-existing structure should be updated
   rather than creating a new one: we did this by iterating over the members in
   the DWARF and in the previously-encountered instance in the CTF.  That meant
   the CTF type had to be lookable-up... and you can't look up newly-added types
   in CTF until you've called ctf_update() on the CTF file containing those
   types.

 - thirdly, libdtrace-ctf internally looks up the type of structure members to
   determine their size (and thus the offset of the next element).

We avoid the first requirement by using the new ctf_snapshot()/ctf_rollback()
machinery.  ctf_snapshot() is radically faster than ctf_update(): it just grabs
a couple of integers, increments one, and returns them.  So we can usually avoid
calling ctf_update() between every emitted type, though we do then have to call
it for all the CTF files just before we emit them. (But that happens only once
for a given file.)

We avoid the second requirement by maintaining our own count of structure and
union members in the recently-added per_module hash: this count is itself a hash
mapping a variant of CTF structure names (an "s" or "u", then a space, then the
name) to a structure containing the CTF file that contains this structure
definition, its type ID, and a count of its members.  (We use this notation
because we want to know if a structure has the same C name as another structure,
even if its type ID differs because it was declared in a different place).  We
can then check this structure's count to see if a structure of this name already
exists, and return its CTF ID (recorded when the structure was emitted for the
first time).  The member-emission code, obviously, has to pull out this count
and increment it whenever it emits a new member (even a blacklisted one which is
otherwise ignored, since we are interested in the size of the original
structure *in the DWARF*).  This data is never thrown away, because built-in
modules can come in and out of scope, interspersed with each other and with
always-built-in kernel code, as we walk through vmlinux.o.

The third requirement, alas, cannot be avoided, but we can reduce the overhead
of it somewhat.  Rather than unconditionally doing a ctf_update() whenever we
insert a new type and whenever we insert a new structure tag (just in case this
structure refers to its own tag), we err on the side of optimism and try to
insert the member anyway, and *only if it fails* with a bad ID error do we do an
update.  The bad ID might happen because the type of a member is not known, or
because a type that member depends upon is not known: either of these might be
in the shared type repository.  Again, we err on the side of optimism and
ctf_update() the non-shared CTF file first -- it's probably much smaller and
will update faster.  Then we try adding the member again, and only if *that*
fails do we ctf_update() the share repository.  If insertion still fails after
that, it's a real error, and is treated as such.

This third requirement conflicts with the first a bit -- we have now called
ctf_update() after a ctf_snapshot() was carried out, which prevents us from
rolling back in case of error.  So we look for an ECTF_OVERROLLBACK error from
ctf_rollback(), and if one happens, we do a ctf_discard() instead, throwing away
all the types inserted after that ctf_update().  This will leave some redundant
types around (those inserted before the ctf_update()), but now they are
ctf_update()d there's no way we can get rid of them: this is only an error case
anyway.

The net effect of this is a radical speedup of dwarf2ctf: in my testing my draft
UEK4 merge tree sees this speedup:

user 563 / sys 173 / elapsed 10:09
 ->
user 272 / sys 10  / elapsed 4:56

We update the documentation at the same time.

This does change the set of dependent types, but only from one buggy set to
another (a fix to that bug is next on the agenda: the bug only affects a
limited subset of modules, which is why nobody has ever noticed it before).

Orabug: 20229506

Signed-off-by: Nick Alcock <nick.alcock@oracle.com>
Acked-by: Kris Van Hees <kris.van.hees@oracle.com>