rrnewton

I thought it was very cool how gVisor is multi-backend (their “sentry” implemented vie either ptrace or kvm), which is pretty unusual with instrumentation tools.

We could maybe have shared this logic to intercept syscalls and redirect them to user space code serving as the kernel. That is, we could have shared the Reverie layer. We saw ourselves as headed towards an in-guest binary instrumentation model (like rr’s syscall buffer). And so one factor is that Rust is a better fit than Go for injecting code into guest processes.

Regarding the actual gVisor user space kernel.. we could have started with that and forked it to start adding determinism features to that kernel. At first glance that would seem to save on implementation work, but “implement futexes deterministically” is a pretty different requirement than “implement futexes”, so it’s not clear how much savings could have been had.

We could still have a go at reusing their kvm setup to implement a Reverie backend. But there’s some impedance matching to do across the FFI there, with the Reverie API relying on Rusts async concurrency mode and Tokio. Hopefully we could cleanly manage separate thread pools for the go threads taking syscalls vs the Tokio thread pool hosting Reverie handler tasks. Or maybe it would be possible to reuse their solution without delivering each syscall to Go code.

The distinction that we often have trouble getting across is between eliminating/controlling nondeterminism, vs recording what happens to occur.

Undo, like rr, and Microsoft TTD, records basically all syscalls, but doesn’t determinize anything in the original execution, only in the replay. A “hermit run” call is like a 0-byte recording —- no nondeterminism so you can “replay” by just running again.

On the overhead, the largest factor is the means of program instrumentation. I don’t know where rr sits, but I’ve heard Microsoft’s solution is quite performant on Windows.

There’s a bit of shared lineage there. Joseph Devietti and I started working in this area together around 2015. And Joe had worked on the deterministic dOS at UW during his PhD (which led to Jinx).

Another related effort is antithesis.com which also seems to use a hypervisor approach rather than Hermits Linux-syscall-API level approach.

Well, we don't prove the absence of concurrency bugs -- that would be more a job for formal verification, type systems, at the source level.

But we can tell when our `--chaos` stress tests cease to produce crashes in reasonable numbers of runs. And when we do achieve a crash we can use our analysis phase to identify the racing operations.

It's both a pro and a con of the approach that we work with real crashes/failures. This means its a less sensitive instrument than tools like TSAN (which can detect data races that never cause a failure in an actual run), but conversely we don't have to worry about false positives, because we can present evidence that a particular order of events definitely causes a failure. Also we catch a much more general category of concurrency bugs (ordering problems between arbitrary instructions/syscalls, even between processes and in multiple languages).

Yep, good point -- should have mentioned it.

That's still roughly accurate because Hermit is, today, still ptrace-powered. I'll quote my reply from elsewhere about the WIP high-perf backend:

> The `experimental/reverie-sabre` directory in the Reverie repo contains our high performance backend, but it's still work-in-progress. It uses binary instrumentation and in our early experiments is 10X faster than our current backend in the worst case (i.e. strace is >10X faster when rewritten with reverie-sabre and run on a program that does nothing but syscalls).

Indeed, releasing a faster drop-in "riptrace" strace replacement is one of the goals ;-).

Well, the starting datetime at the beginning of execution in the container is whatever you set it to:

$ hermit run --epoch=2022-01-01T00:00:00Z /bin/date

Fri Dec 31 16:00:00 PST 2021

We, somewhat eccentrically, put it in last millennium by default. It used to default to the original Unix epoch back in 12/31/1969, but that was causing some software to be very unhappy ;-).

The reproducibility guarantee is that the behavior of the program is a deterministic function of its initial configuration. The epoch setting is one aspect of that initial configuration (as are file system inputs, RNG seeds, etc).

Well, probably not on device ;-).

The underlying Reverie instrumentation layer works on ARM, but Hermit isn't ported yet, and we haven't touched RISC-V yet at all. (Contributions welcome!)

One thing we haven't tried yet is just putting a whole emulator (qemu etc) underneath Hermit. That would address any sources of irreproducibility that the emulator lets through from the host (threads, RNG, etc).

Well, gettimeofday is a syscall, and we do intercept it (along with clock_gettime, clock_gettres, time, nanosleep, and the rdtsc instruction, even though that last one is not a syscall). When we intercept it, we report virtual time back to the guest. We make sure that virtual time is deterministic, across all threads in the container, irrespective of what the wall clock time is on the host machine.

So for instance, if there are multiple threads in a chess engine, and they are racing to write search results to a data structure, these threads will interleave in a reproducible order under Hermit, and the races will resolve consistently.

But the downside is that Hermit does sequentialize execution onto one core. So in the current version, a multithreaded program doesn't get actual wall-clock speedup from its parallelism. (The earlier dettrace did allow some limited guest parallelism, and we plan to bring that back.) For this reason, Hermit's good for consistent testing multithreaded software, but you wouldn't want to run parallel software under it outside of testing.

Alas the performance overhead in realtime is not great yet. It still uses ptrace currently, which often results in a multiple-X slowdown (but at least it doesn't "subscribe" to every syscall like strace does, because some are naturally deterministic). Reverie's whole design is to make it support swappable backends, and this ptrace backend is just the reference implementation. The `experimental/reverie-sabre` directory in the Reverie repo contains our high performance backend, but it's still work-in-progress. It uses binary instrumentation and in our early experiments is 10X faster than our current backend in the worst case (i.e. strace is >10X faster when rewritten with reverie-sabre and run on a program that does nothing but syscalls).

But to the second part of your question about deterministic benchmarking, that is really a separate question. Hermit defines a deterministic notion of virtual time, which is based on the branches retired and system calls executed by all threads. When you run hermit with `--summary`, it reports a total "Elasped virtual global time", which is completely deterministic:

$ hermit run --summary /bin/date

...

Elapsed virtual global (cpu) time: 5_039_700ns

Therefore, any program that runs under hermit can get this deterministic notion of performance. We figured that could be useful for setting performance regression tests with very small regression margins (<1%), which you can't do on normal noisy systems. Compilers are one place I've worked where we wanted smaller performance regression alarms (for generated code) than we could achieve in practice. We haven't actually explored this application yet though. There's a whole small field of people studying performance modeling and prediction, and if one wanted to try this deterministic benchmarking approach, they might want take some of that knowledge and build a more accurate (correlated with wall time) performance model, more realistic than Hermit's current virtual time that is.

Sure! So it really breaks down into two cases: internal and external networking relative to the container Hermit creates.

(1) internal networking

If you run a test like `rust/network_hello_world.rs` under Hermit, then the communication between threads is part of the "deterministic bubble" that we're running inside of. When one thread blocks on a network call, the Hermit scheduler takes the thread out of the run pool, and it has to deterministically decide when it is ready to rejoin the run-pool by waking up. The scheduler proceeds in linear turns (labeled "COMMIT" in the logs), and if thread 5 unblocks from a network read at turn 100 in one run, it must unblock at that same point in time in all other runs.

Sometimes we use a precise model of the blocking operation (like with futexes) and other times we depend on sending Linux a non-blocking version of the syscall as a way to poll the IO and see if it is ready to complete (given the history of every operation that has committed on turns 1..N-1).

(2) external networking

This is impossible to determinize, of course. Unless you suck the whole network including both hosts into the deterministic bubble, as the DDOS fork of Linux experimented with in ~2013. That was kind of a negative result IMO because performance was pretty bad, but the paper is here:

  https://www.dcc.fc.up.pt/~ines/aulas/1314/SDM/papers/DDOS.pdf

That's where record-replay comes in. `hermit record` can record network calls, but is in a pretty early state and doesn't support many programs. `hermit run` can just allow networking through and hope for the best, but in the future we plan to add features to record just network calls (and no other syscalls), so that you can mix and match different external-network-responses with different thread schedules. That is, you could "pin" the network responses with network-only recording, and then mess around with other parameters or even modify the program.

Sure! I think underpinning your question is a really subtle point there. And I think the answer is in the different purposes of regression testing and bug finding. In regression testing (CI), you're testing if the code introduced new problems. You don't at that point in time really want to know that someone else's test downstream from your component fails when given a new thread schedule that it has not previously seen. Wherease if you're stress testing (including fuzzing and concurrency testing) you probably want to torture the program overnight to see if you can turn up new failures.

The Coyote project at Microsoft is a concurrency testing project with some similarities to Hermit. For the reasons above, they say in their docs to use a constant seed for CI regression testing, but use random exploration for bug finding:

  https://www.microsoft.com/en-us/research/project/coyote/

Still, it does feel like wasted resources to test the same points in the (exponentially large) schedule space again and again. Kind of like some exploration/exploitation tradeoff.

We don't do it yet, but I would consider doing a randomized exploration during CI, but making the observable semantics the fixed version. If the randomized one fails, send that over to the "bug finding" component for further study, while quickly retrying with the known-good seed for the CI visible regression test results.

I don't think there's one right policy here. But having control over these knobs lets us be intentional about it.

P.S. Taking the random schedules the OS gives us is kind of "free fuzzing", but it is very BAD free fuzzing. It over-samples the probable, boring schedules and under-samples the more extreme corner cases. Hence concurrency bugs lurk until the machine is under load in production and edge cases emerge.