Uniqtypes should be more compact

[stephenrkell]

Currently, each binary generates quite a lot of uniqtype data. This could easily be made more compact in various ways.

• remove the cache word
• don't generate anonymous subrange types for arrays
• relax the invariant that related[0] always exists
• for degree-1 pointer types, avoid storing the ultimate pointee and immediate pointee separately
• strip the -meta.so so it no longer has .symtab and .strtab
• check that the ".size" calculation is accurate (I think it might be doing extra padding)
• "short-allocate" some cases of the union, if they don't need the full amount of space
• only include make_precise if some flag (somewhere) says it's present
• do more clever string compression on subobject names, perhaps, or otherwise tweak our naming conventions to better exploit assemble- and link-time string merging

[stephenrkell]

Since uniqtypes are quite pointer-dense, the dynamic reloc info can be quite large. So another optimisation: support a custom reloc format that is optimised for this. There's no excuse for meta-objects' having a .rela.dyn section that is bigger than the .data section, as at present. E.g. we should be able to encode all pointers in at most 2 bytes, since we're unlikely to be referencing more than 64k distinct uniqtypes.

This ties in with #23 since if we're using our own dynamic linker, we have freedom to implement new flavours of reloc.

[stephenrkell]

Another one: don't generate both symbol hash tables, given that nowadays relf.h can grok the GNU-style hash table.

[stephenrkell]

See also #34 -- getting rid of array types will help a lot.

Also, the frame information is a killer because it generates large numbers of minor-variant layouts of a given frame. I am working on some clever ways to factor that, instead of just expanding every single distinct layout into a distinct uniqtype. It draws on some ideas from/following the OOPSLA 2019 paper on doing good things with frame info (by Bastian, me, Zappa Nardelli).

[stephenrkell]

To expand on the frame info idea: a BAP tool not too different from the frame info synthesis tool, could analyse use of the stack pointer and addresses derived from it. One of its functions will be to track which stack slots are issued, so that we know where the holes are... for types/sizes, this requires correlating issued address with their DWARF info. The same idea generalises to a liveness analysis, so we know which slots are dead or uninitialized (modulo lack of interprocedural knowledge, for address-taken slots).

To actually represent the frame types, I'm thinking (1) treat each one as a subset of the collected <offset,type,name> tuples seen across the whole function (or perhaps more broadly!), then (2) invent some kind of MTBDD representation of the mapping between PC and these sets.

[stephenrkell]

Another trick might be to eliminate uniqtypes from a meta-DSO if they are defined by the meta-DSO of a DSO that is DT_NEEDED by the first DSO. That requires care: the Makefile.meta rebuild rules for a meta-DSO would them have to depend on the transitive closure of its described DSO's DT_NEEDED dependencies. But it would be neat, e.g. most base types would appear in the dynamic linker DSO, then various others would appear only in the libc, and so on... each meta-DSO would be quite minimal.

[stephenrkell]

Doing the DT_NEEDED trick means we would have to be careful about loading meta-DSOs in dependency order.

[stephenrkell]

It also poses a problem for aliases: if a DSO introduces a new alias for a type defined elsewhere, its definition of that uniqtype can't be pruned, and indeed will still wrongly `win' the global-symbol race for that alias (this is #18). If ELF let us define aliases without defining the symbol itself, we would avoid this. One way to solve #18 might be to cook up some encoding of that, though it feels rank. The other way is post-hoc detection and use of the dlbind library... not much better.

[stephenrkell]

All this is departing from the 'let the linker do the uniquing' idea that was so appealing originally. I guess run-time uniquing by the ld.so is a different cost model than static uniquing.

Edit: actually the problem is 100% aliases. We still do let the (dynamic) linker do the uniquing by name (by its treatment of global symbols). But we also want to unique by alias group. We were never using the linker to do that... within a single DSO we do it by DWARF-level stuff in liballocstool, i.e. computing concrete types, names for them, keeping a 'master relation' and alias sets, etc.

[stephenrkell]

Also it wouldn't reduce the number of dynsyms, as the pruned uniqtypes would still be present as UNDs. It would reduce the number of superfluous overridden defined uniqtype objects. That is still a reduction worth having.

[stephenrkell]

There are edge cases that will break if we make non-freestanding uniqtype libs. Basically we are second-guessing the LD_LIBRARY_PATH of the user invoking the program. So it breaks e.g. if they'd get a different depended-on library that doesn't define some of the program's needed uniqtypes. Or maybe it does define them, but we haven't generated its meta-DSO. Or maybe we don't have debug info for that one, so would have generated a freestanding meta-DSO if Makefile.meta had been running with the same environment. And so on.

[stephenrkell]

One idea would be to generate freestanding meta-DSOs but heuristically place the uniqtypes so that the ones we expect to be duplicated by a depended-on library are colocated, and those that we expect to be 'in use' are also colocated, i.e. demand paging ensures we never bring the unused ones into memory.

Of course we don't save space on disk with this... but we do save RSS at run time. I guess it could be a link-time option whether to drop or include the expected-duplicate ones, for use on space-constrained platforms.