The Compact C Type Format in the GNU toolchain [LWN.net]

The Compact C Type Format in the GNU toolchain

Posted Aug 6, 2019 20:26 UTC (Tue) by nix (subscriber, #2304)
Parent article: The Compact C Type Format in the GNU toolchain

btw, my next priority after getting the linker working, even before writing a proper deduplicator for the types in the .ctf section, is documentation. This *matters*.

to post comments

The Compact C Type Format in the GNU toolchain

Posted Aug 6, 2019 21:53 UTC (Tue) by roc (subscriber, #30627) [Link] (6 responses)

When writing a spec please please make sure the spec includes everything a consumer needs to know to parse all relevant versions.

I.e. don't do the DWARF thing where the latest version of the spec describes only the latest version of the format, so to write a tool that handles DWARF 2-5 you have to read multiple specs and combine them in your head.

The Compact C Type Format in the GNU toolchain

Posted Aug 6, 2019 23:05 UTC (Tue) by nix (subscriber, #2304) [Link] (5 responses)

I'm probably going to do the spec in ANTINEWS format: the latest version, and then earlier versions defined in terms of their differences from the next higher version. This seems like a joke when Emacs does it but I think for file formats it might make considerable sense and allow more flexibility than the whole-new-spec-every-time approach DWARF takes. (Also, note that if you have libctf available, in time you won't need to go through agony parsing every possible version yourself: you can just ask libctf to convert the CTF dictionary into a version you understand, and it'll tell you if it can't. Not that libctf can *do* that yet, but that's planned. It already silently upconverts from older versions into the latest at open time, so consumers only need to understand the latest version and can rely on libctf for older versions. Not back to FreeBSD/Solaris versions yet, mind you: that too is coming.)

The Compact C Type Format in the GNU toolchain

Posted Aug 6, 2019 23:16 UTC (Tue) by roc (subscriber, #30627) [Link] (4 responses)

ANTINEWS definitely sounds better than what DWARF does!

If CTF takes off people are definitely going to write consumers that don't use libctf. For one thing, I do not trust C libraries to parse possibly-malicious data so we would write a Rust library if we added CTF support to Pernosco. And inevitably there will be people who don't like libctf for *reasons* and do their own thing.

> It already silently upconverts from older versions into the latest at open time

Hmm, so in that case it parses the entire file up-front? That seems like a regression from DWARF.

The Compact C Type Format in the GNU toolchain

Posted Aug 7, 2019 0:06 UTC (Wed) by nix (subscriber, #2304) [Link] (3 responses)

If CTF takes off people are definitely going to write consumers that don't use libctf. For one thing, I do not trust C libraries to parse possibly-malicious data so we would write a Rust library if we added CTF support to Pernosco.

Errr... if your CTF is malicious, the binary is malicious. Isn't the malicious executable code likely to be a bigger worry? (But I would rejoice at the thought of a Rust libctf. It's just a shame binutils libctf wouldn't really be able to use it: I doubt Rust works on mingw. :P )

Hmm, so in that case it parses the entire file up-front? That seems like a regression from DWARF.

It has to, as a consequence of the decision to not spend space on indexes or indentifiers. On loading, we have to sweep through the type section and construct a mapping of type ID -> file offset, intern type names in various hashes etc (we sweep through the two symbol-related sections too, constructing a symbol number -> file offset mapping). Given that we have to sweep through the file to decompress it anyway, the thing is almost always already in L2 cache in any case so the cost is in the noise. Back when I had a deduplicator so the files were small, I literally could not measure the cost of doing this, nor the cost of doing aggressive upgrading of the entire file. And it's far simpler than doing it lazily.

In any case, one of the planned revisions for v4 is a proper intermediate representation inside libctf whereby we unpack individual types into their largest possible form on the fly for internal processing, then pack them back down into their maximally compact form for storage (even just in memory), which lets us eliminate a lot of ugly redundancy in libctf. With this in place, we can shift from aggressive upgrading to literally storing in whatever old format people want. (But we'll still need to sweep through the file at open time to construct that mapping. And this is all months away in any case.)

The Compact C Type Format in the GNU toolchain

Posted Aug 7, 2019 0:24 UTC (Wed) by roc (subscriber, #30627) [Link] (2 responses)

> Errr... if your CTF is malicious, the binary is malicious. Isn't the malicious executable code likely to be a bigger worry?

Not necessarily. For example you might want to run `objdump` on a possibly-malicious executable and not get owned.

Alternatively, you might have a debugger that runs the debuggee code in a sandbox but where you want to process debuginfo outside that sandbox. This is our situation.

> It has to, as a consequence of the decision to not spend space on indexes or indentifiers.

Hmm. You should probably highlight this tradeoff, because it is significant.

> Back when I had a deduplicator so the files were small, I literally could not measure the cost of doing this, nor the cost of doing aggressive upgrading of the entire file.

OK but how big was that binary? Things that work well for reasonable-sized programs don't necessarily work well for Firefox or Chromium. If you want people to use CTF to generate FFI glue at runtime, for example, even a small startup penalty is going to cause people to look for alternatives.

The Compact C Type Format in the GNU toolchain

Posted Aug 7, 2019 0:55 UTC (Wed) by nix (subscriber, #2304) [Link] (1 responses)

OK but how big was that binary? Things that work well for reasonable-sized programs don't necessarily work well for Firefox or Chromium. If you want people to use CTF to generate FFI glue at runtime, for example, even a small startup penalty is going to cause people to look for alternatives.

Let's try it for an enterprise Linux kernel (because I've got one sitting here waiting). The kernel splits its CTF unusually: let's try the output of the old deduplicator, vmlinux.ctf (types only used by the core kernel) plus its parent shared_ctf.ctf (types used by more than one module, or by at least one module and the core kernel). Put together these are 1509340 bytes compressed, 4267753 bytes uncompressed. With a good deduplicator you need a *big* program for that, though no doubt a C++-capable CTF would find Chromium to be just such.

A thousand cats:

1.26user 0.33system 0:01.52elapsed 104%CPU (0avgtext+0avgdata 3320maxresident)k

A thousand uncompresses (done by hacking libctf to abort on error and free everything immediately after uncompressing). Unsurprisingly gunzip is not free:

34.42user 3.64system 0:38.03elapsed 100%CPU (0avgtext+0avgdata 9472maxresident)k

A thousand dumps of the CTF header redirected to /dev/null (which roughly involves open, decompress, and sweep for indexes etc, do almost no work, close):

35.28user 2.97system 0:38.23elapsed 100%CPU (0avgtext+0avgdata 9468maxresident)k

That's in the noise: if it costs anything, the indexing costs well under 1% of the cost of decompression: and since it increases the efficiency of compression to do this sort of thing, it may in the end *save* time as well as space. (I also tried this with an old-format file: the transparent upgrade pass was also in the noise.)

Note that the CTF link section merging machinery almost entirely resides in libctf and is intended to be reusable by other projects: it's not ld-specific, and you're not restricted to doing CTF merging the exact same way ld does it. Things like Chromium and Firefox might well elect to postprocess themselves and split up their CTF differently, yielding smaller CTF dictionaries customized for their use. (Right now, you can choose to split along boundaries different from translation unit boundaries, lumping TUs together into bigger units, and you can choose an alternative conflict-resolution strategy where rather than placing all types in one big dictionary unless they conflict, we place all types in per-TU subdictionaries unless they are used by more than one TU: so the parent TU gets a lot smaller. The linker doesn't use any of this stuff yet, but in time it might grow options controlling some of this. There's no point yet since most of that depends on a good deduplicator. The one I haven't written yet. :) )

... also of course we'd need clang support for CTF generation and gold and lld support for .ctf section merging *and* C++ support for CTF before Chromium or Firefox would become likely users. That's some way off, I think.

The Compact C Type Format in the GNU toolchain

Posted Aug 7, 2019 1:05 UTC (Wed) by roc (subscriber, #30627) [Link]

Those are certainly encouraging results.