Integrate chronicle-recorder

The goal is to record a crash / whatever at event Y, then replay up to event X that's "far enough" before Y and generate a "supertrace" of the execution in (X, Y) using chronicle-recorder. That supertrace lets other tools answer questions like, "where was the last write to addr A".

It's going to be rather nontrivial to get rr to spit out these DBs. A few ideas that don't look feasible

• stepi through execution and generate the DB from effects. This is prohibitively expensive (~4500x, in an underestimating experiment). We could also be forced to duplicate the logic that a tool like libvex or Pin already have.
• step through store insns. Sells ourselves short and also has instrumentation-logic-duplication problem.
• recast problem as "valgrind attach" --- have rr hand off tracees to valgrind and valgrind instrument existing processes. There are a few reasons why this doesn't look feasible, chief among them that the instrumentation would share the tracee's address space, which opens a can of worms. Also, ~all existing tools assume they start running at process start, so we wouldn't be able to use them "out of the box".
• roll-our-own valgrind-alike using some instrumentation library other than libvex. The popular ones I looked at are either non-free, don't have the on-demand model required, don't support non-x86(-64), or some combination thereof.

So I think we're down to roll-our-own valgrind-alike with libvex.

While writing this though, I just had another idea: if we implement a persistent checkpoint operation that additionally stores "resume-replay" information (trace-file offsets etc.), then we could theoretically chronicle-record a tool that consumes that checkpoint and resumes replay. That is, the resume operation and rr replay code would be recorded into the chronicle DB along with tracee execution. We run into #16 trying to do that though, in addition to the "wasted" rr traces in the DB (although that would be jaw-droppingly awesome for rr devs ... ;) ).

We've tentatively settled on an approach in which we

• fork a 64-bit chronicle process
• run a mini-valgrind-alike in that process: use the rr trace to schedule threads and replay syscall outparam writes, but otherwise follow the valgrind model pretty closely, except
• allocate 4GB of address space per tracee process (really, 3GB if we wanted to get cute) in the chronicle process
• add virtual "offset register" to the emulated CPU, where the offset points at the start of tracee's memory area. Add that offset to all read/write operations.
• when a page is first accessed, "fault" it in by reading the tracee process's /proc/mem

... I just realized while writing this that this scheme won't handle shmem properly, and can't easily be fixed to do so. D'oh!

There were two other ideas we floated for memory operations for the virtual CPU

• emulate load/store by read(mem-fd)/write(mem-fd). Make it faster by emulating a cache hierarchy, where actual read()/write() only happen on cache miss/eviction, munmap, and process context switch (not thread). Load/store would manipulate the in-process cache. Avoids the shmem problem by directly manipulating (eventually, at cache flush time) the tracee's original memory mappings. The chronicle process in this model could be 32 or 64 bit, doesn't particularly matter.
• 64-bit chronicle process. give each process an array of pages. On first access, "fault" in the page and add it to the array. Emulate load/store by looking up the page by address. Make it faster by e.g. multi-level hierarchy. Avoids the mmap problem because (in theory) shared pages can be detected and multiple process's page arrays can point at the same memory.

I think as far as emulated load/store are concerned, the performance of both approaches should be about the same because they both boil down to a fast address->mem-chunk look-up. The first approach has to flush, and therefore would fault more. But the second approach pays for that in extra complexity in detecting shared pages and updating appropriately on munmap etc. (The first approach may be friendlier to real CPU cache, but I don't think we're going to be anywhere near the level of caring.) We probably want to use the existing shared trace and util code in the chronicle process, and it would be much more convenient do so if the image were 32-bit, which could do with the first approach.

My gut tells me the first way would be simpler, so I lean towards that. @rocallahan thoughts?

Start by reviewing rr's replay and checkpoint behavior alongside the chronicle-recorder goal described here. Compare the proposed emulated memory approaches, including shared-memory handling and /proc/mem page loading, before choosing an implementation path. Done means rr can produce a chronicle database and a supertrace for the execution interval before a crash or selected event.