7 ms·

TL;DR: This is a Rust project that forces deterministic execution of arbitrary programs and acts like a reproducible container. That is, it hermetically isolate

TL;DR: This is a Rust project that forces deterministic execution of arbitrary programs and acts like a reproducible container. That is, it hermetically isolates the program from sources of non-determinism such as time, thread interleavings, random number generation, etc. Guaranteed determinism is a powerful tool and it serves as a basis for a number of applications, including concurrency stress testing, record/replay, reproducible builds, automatic diagnosis of concurrency bugs, and more. I've been on the team working on this project over the past ~2 years. AMA! Here is the GitHub repository: https://github.com/facebookexperimental/hermit https://github.com/facebookexperimental/hermit

CJefferson 4y ago
This looks cool. Personally I'd also be interested in this for academic work -- anything which makes it easier to be sure an experiment can be reproduced later (a week, year, or decade later, in increasing order of difficulty), is good to have.
- rrnewton 4y ago
  Yes, I'm very interested in that as well. I've been involved with the ACM Artifact Evaluation process which has been going on in several conferences for a while. https://www.acm.org/publications/policies/artifact-review-badging https://www.acm.org/publications/policies/artifact-review-ba... But it's been pretty frustrating. As an author, my PLDI 2014 artifact stopped working less than 5 years later (Docker image binary incompatibility). And when I was co-chair of an Artifact Evaluation Committee in 2017, there was not great reproducibilty of the artifacts that were submitted either. If you package a VM (freezing the Linux kernel), and are pretty sure that VM will run in 10 years, PLUS you determinize the execution itself... that should allow durable bitwise reproducibility. Maybe Hermit could be one ingredient of that. For scientific reproducibility, there is a lot of other tooling to build too, and I know some folks have been working in that area: https://ctuning.org/ https://ctuning.org/
rrnewton 4y ago
Note that this is a follow-on project from the earlier Dettrace system, which was applied mainly to reproducible builds (as in the academic paper, https://dl.acm.org/doi/10.1145/3373376.3378519 https://dl.acm.org/doi/10.1145/3373376.3378519, and presented to the Debian Reproducible Builds summit): - https://github.com/dettrace/dettrace https://github.com/dettrace/dettrace And one cool part of it is this Rust program instrumentation layer: - https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie It's good for building OS-emulator style projects or tracing tools.
wyldfire 4y ago
> thread interleavings I was going to ask if it could do the flip side - instead of stabilizing the scheduler, make it less predictable. AFAICT, it can! Awesome, looking forward to giving it a try. hermit run --chaos --seed-from=SystemRandom ./target/debug/hello_race;
- rrnewton 4y ago
  Yes indeed. That concurrency testing capability is a pretty well-studied area and we implement a couple existing algorithms. The first is our adaptation of the PCT algorithm (ASPLOS'10 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos277-pct.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...). That's what you get by default with `--chaos`. But we also have variations on straight up randomized scheduler (random thread selection at each time step). rr chaos mode has its own take on this: https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mode.html https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo... This study compares a few approaches - http://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2016/TOPC.pdf http://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2016/TOPC....
mtlmtlmtlmtl 4y ago
This is exactly the type of thing I've been wanting for testing my chess engine. Parallelism is based on emergent pseudorandom effects of things like interleaving causing searcher threads to mostly end up in non-overlapping parts of the search tree. One question: How do you avoid the program being affected by things like overall system load and memory pressure?
- jasonwhite 4y ago
  Since CPU is a "compressible" resource, system load doesn't affect the determinism. It'll make it slower of course. Since memory is a non-compressible resource, things can start getting killed by the OOM-killer and there's nothing we can do about it. There are also certainly things like external network communication and file system access that are non-deterministic that must be handled at a higher level (e.g., with a reproducible FS image or by recording & replaying network traffic).
  - mtlmtlmtlmtl 4y ago
    The idea of CPU being compressible is very insightful, thanks. I'm curious about what happens with time control though. Engines can be given a time constraint and will use various heuristics to allocate that time. How does Hermit intercept gettimeofday()?
    - rrnewton 4y ago
      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.
comex 4y ago
Nice. Some questions: - How does this compare with rr? - Out of curiosity, have you ever looked at libTAS? (I realize it has a very different intended use case.) - Have you had an issues with behavior differences between CPUs? I know there is architecture-level undefined behavior that can differ between CPUs; on the other hand, it sounds like you’re primarily interested in running well-behaved executables that wouldn’t intentionally invoke such behavior.
- jasonwhite 4y ago
  - We've taken a lot of inspiration from RR and it is very good at what it does (record/replay + randomizing thread schedules). This project diverges a bit from RR in that we focus more on the concurrency testing application of determinism. I wrote the toy record/replay system that sits on top of the determinism layer (so that we don't have to record as much stuff), but it's a long way from being complete. - I haven't seen libTAS until now, so I can't comment on it much. At first glance, it does look similar! - See @rrnewton's reply on this one.
- rrnewton 4y ago
  (1) rr [formerly Mozilla rr] We're big fans of rr! Hermit is different in that creating a deterministic OS semantics is different than recording whatever nondeterministic behavior occurs under normal Linux. BUT, there's a lot of overlap. And indeed `hermit record` is straight up RnR (record & replay). But hermit for RnR but is not nearly as developed as rr. We integrate with gdb/lldb as an (RSP) debugger backend, just like rr. Any failing execution you can create with hermit, you can attach a debugger. But our support is very preliminary, and you'll probably find rough edges. Also, we don't support backwards stepping yet (except by running again). If we invest more in using Hermit as a debugger (rather than for finding and analyzing concurrency bugs), then there should be some advantages over traditional RnR. These would relate to the fact that deterministically executing is different than recording. For example, process and thread IDs, and memory addresses all stay the same across multiple runs of the program, even as you begin adding printfs and modifying the program to fix the bug. With traditional RnR, you can play the same recording as many times as you like, but as soon as you take a second recording all bets are off wrt what is the same or different compared to the prior recording. (That includes losing the "mental state" of things like tids & memory addresses, which is a good point Robert O Callahan makes about the benefits of RnR when accessing the same recording multiple times.) (2) libTAS - no we haven't! Checking it out now. (3) Yes, definitely issues with CPU portability. In general, we are interested in not just determinism on the same machine, but portability between machines in our fleet. As with any tech company that uses the cloud, at Meta people are usually trying to debug an issue on a different machine than where the problem occurred. I.e. taking a crash from a production or CI machine to a local dev machine. The way we do this is that we mostly report a fairly old CPU to the guest, which disables certain features IF the guest is well behaved. With the current processor tech, I don't think there's any way we can stop an adversarial program, which, for example, would execute CPUID, find that RDRAND is not supported on the processor, but then execute RDRAND anyway. We could build a much more invasive binary-instrumentation based emulator that would be able to enforce these kinds of rules at the instruction granularity, but it would have higher overhead, especially startup overhead. The nice thing about Reverie though is that we (or others) can add different instrumentation backends while keeping the same programming instrumentation API. So we could have a "hardened" backend that was more about sandboxing and reverse-engineering adversarial software, making a different tradeoff with respect to performance overhead.
wyldfire 4y ago
> AMA! Eager to try it but encountering the build error here - https://github.com/facebookexperimental/hermit/issues/11 https://github.com/facebookexperimental/hermit/issues/11 Do you have a reference build log / environment you can share? Last known good commit sha and/or output from "rustup show"?
- jasonwhite 4y ago
  We're working on it! Should be fixed soon.
  - rrnewton 4y ago
    Reverted a badly-timed breaking change that came through the sync system. Will fix it properly shortly (and add a Dockerfile and release tag). But for now you may have better luck on the main branch after that reversion, which yielded 6cb5575ffd287289769144ec82e2900cbf6cd1ad. Let's discuss further on that issue #11.
oulipo 4y ago
Would something like this work for embedded code, like ESP32?
- rrnewton 4y ago
  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).
gmartres 4y ago
Thanks for open-sourcing this! Roughly, what's the performance overhead from running code under hermit? I'm wondering if this could be used for doing benchmarking with less variance on non-deterministic platforms such as the JVM (I assume hermit is "deterministic enough" that the JIT and GC threads of the JVM will run the same code on every execution?)
- rrnewton 4y ago
  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.
  - dekhn 4y ago
wizeman 4y ago
> AMA! I have a few questions. Hermit's README says: > Instead, in order to provide complete determinism, the user should provide a fixed file system base image (e.g., with Docker) How are you sanitizing the result of stat(), for example? I'm guessing you're already aware of this, but fixed file system images are not sufficient to guarantee deterministic behavior by filesystems. Specifically, inode numbers are not guaranteed to be assigned in any order. So how do you return deterministic inode numbers in stat() calls? I'm sure you're also aware of this, but other filesystem results are also not guaranteed to be deterministic. For example, the `st_nblocks` and `st_blksize` fields in `struct stat` can change in-between stat() calls when nothing else happens from the user-space point of view except time passing (this happens in ZFS, for example, due to delayed allocation). statvfs() is another problematic call which would have to be heavily sanitized. As another example, there are filesystems that generate a random seed for every directory that is created, to prevent applications from exploiting hash table weaknesses and causing a denial-of-service when creating many directory entries that hash to the same value. This random seed can have the side effect of readdir() calls returning directory entries in a different order based on the seed, even if the directory was created in the exact same way (with identical directory entries, created in the same order). It seems like this would require reading the entire directory and then sorting the results, even when doing a single readdir() call to read a single directory entry. Similarly, telldir() / seekdir() can also be problematic because the cookie value returned by the filesystem in telldir() is opaque and would be different for different directory seed values. This seems like it would require Hermit to maintain a full in-memory view of all the directory entries of a directory that is opened and is being read, which also means that this in-memory view can become out-of-date in-between readdir() / telldir() / seekdir() calls by one process and calls that modify the directory by another process (Edit: I guess Hermit can synchronize this view easily since it can assume it has full control of all processes inside the container). It also seems like Hermit would also need to re-read the entire directory when rewinddir() is called, to avoid introducing non-previously-existing concurrency bugs like described in the above paragraph (Edit: again, this is probably not necessary since Hermit can maintain a synchronized view of a directory on its own). Reading the directory also seems to imply that you'd have to assign deterministic inode numbers for all directory entries, which also seems non-trivial. Do you think this is an accurate assessment of the situation? How does Hermit handle all of this? Also, CPUs can (according to the manuals, at least) behave non-deterministically when executing instructions in certain undefined conditions. How do you handle this? Last question: how do you sanitize the RDTSC CPU instruction?
wyldfire 4y ago
Are there any limitations regarding hermit running programs which emit code at runtime?
- jasonwhite 4y ago
  There shouldn't be! We don't do any sort of binary rewriting, which is the typical problem with JITed code.
wizeman 4y ago
Sorry, just an additional question as this project is so interesting: Does Hermit support running different processes in parallel in certain situations? It seems like this should be possible to do as long as they are appropriately isolated from each other. Specifically, if two processes don't share any writable memory mappings then I'm thinking it might be possible for Hermit to exploit the underlying existing isolation between them so that they could run code in-between system calls in parallel (while still making sure that the actual system calls happen in a deterministic order). Perhaps it would even be possible for the two processes to execute system calls in parallel if they are unrelated and they do not affect deterministic execution (such as if they are doing I/O to different files or directories, or one process doing I/O while another is doing something completely unrelated like getting the time, etc). Although I guess this latter point (of executing syscalls in parallel) would require doing rewind/replay because it wouldn't be possible to know in advance whether the system calls are going to be related or not, as the two processes might not do the syscalls at exactly the same time. Is Hermit doing this (executing code in-between syscalls in parallel, at least)? Or do you think it would be possible to do it? This could significantly increase the usefulness of Hermit for distros that want to do deterministic builds of packages, as most compilation could happen in parallel / i.e. use several cores at the same time! I'm thinking about huge package builds such as Chromium, Firefox, the Linux kernel, etc. which would perhaps take days to build if they were completely serialized into a single CPU core.
- rrnewton2 4y ago
  [Caught by the no-procrastination feature by accident.] Our earlier (dettrace) prototype allowed syscall-free regions in separate processes to run physically in parallel. Hermit actually hasn't added any process parallelism yet, but it's designed to actually go further than dettrace in this respect. Specifically, Hermit is architected so that the thread-local syscall handler "checks out" resources from the central scheduler. Resources include things like paths on the file system, contents of files, shared memory, and permission to perform external side effects. Right now, all requests wait for the scheduler to background all other threads and make the current thread the only runnable. But the idea is: in the future we will keep the semantical identical log of linear "commits" (linearization), but will simply background the current thread while it uses the resources they checked out, move forward to the next scheduler iteration, and only block the next runnable thread until its requested resources are freed, not until ALL other threads have finished their timeslice and gone back to waiting on the scheduler.

CJefferson 4y ago

This looks cool. Personally I'd also be interested in this for academic work -- anything which makes it easier to be sure an experiment can be reproduced later (a week, year, or decade later, in increasing order of difficulty), is good to have.

rrnewton 4y ago
Yes, I'm very interested in that as well. I've been involved with the ACM Artifact Evaluation process which has been going on in several conferences for a while. https://www.acm.org/publications/policies/artifact-review-badging https://www.acm.org/publications/policies/artifact-review-ba... But it's been pretty frustrating. As an author, my PLDI 2014 artifact stopped working less than 5 years later (Docker image binary incompatibility). And when I was co-chair of an Artifact Evaluation Committee in 2017, there was not great reproducibilty of the artifacts that were submitted either. If you package a VM (freezing the Linux kernel), and are pretty sure that VM will run in 10 years, PLUS you determinize the execution itself... that should allow durable bitwise reproducibility. Maybe Hermit could be one ingredient of that. For scientific reproducibility, there is a lot of other tooling to build too, and I know some folks have been working in that area: https://ctuning.org/ https://ctuning.org/

rrnewton 4y ago

Note that this is a follow-on project from the earlier Dettrace system, which was applied mainly to reproducible builds (as in the academic paper, https://dl.acm.org/doi/10.1145/3373376.3378519 https://dl.acm.org/doi/10.1145/3373376.3378519, and presented to the Debian Reproducible Builds summit): - https://github.com/dettrace/dettrace https://github.com/dettrace/dettrace And one cool part of it is this Rust program instrumentation layer: - https://github.com/facebookexperimental/reverie https://github.com/facebookexperimental/reverie It's good for building OS-emulator style projects or tracing tools.

wyldfire 4y ago

> thread interleavings I was going to ask if it could do the flip side - instead of stabilizing the scheduler, make it less predictable. AFAICT, it can! Awesome, looking forward to giving it a try. hermit run --chaos --seed-from=SystemRandom ./target/debug/hello_race;

rrnewton 4y ago
Yes indeed. That concurrency testing capability is a pretty well-studied area and we implement a couple existing algorithms. The first is our adaptation of the PCT algorithm (ASPLOS'10 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos277-pct.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...). That's what you get by default with `--chaos`. But we also have variations on straight up randomized scheduler (random thread selection at each time step). rr chaos mode has its own take on this: https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mode.html https://robert.ocallahan.org/2016/02/introducing-rr-chaos-mo... This study compares a few approaches - http://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2016/TOPC.pdf http://www.doc.ic.ac.uk/~afd/homepages/papers/pdfs/2016/TOPC....

mtlmtlmtlmtl 4y ago

This is exactly the type of thing I've been wanting for testing my chess engine. Parallelism is based on emergent pseudorandom effects of things like interleaving causing searcher threads to mostly end up in non-overlapping parts of the search tree. One question: How do you avoid the program being affected by things like overall system load and memory pressure?

jasonwhite 4y ago
Since CPU is a "compressible" resource, system load doesn't affect the determinism. It'll make it slower of course. Since memory is a non-compressible resource, things can start getting killed by the OOM-killer and there's nothing we can do about it. There are also certainly things like external network communication and file system access that are non-deterministic that must be handled at a higher level (e.g., with a reproducible FS image or by recording & replaying network traffic).
- mtlmtlmtlmtl 4y ago
  The idea of CPU being compressible is very insightful, thanks. I'm curious about what happens with time control though. Engines can be given a time constraint and will use various heuristics to allocate that time. How does Hermit intercept gettimeofday()?
  - rrnewton 4y ago
    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.

comex 4y ago

Nice. Some questions: - How does this compare with rr? - Out of curiosity, have you ever looked at libTAS? (I realize it has a very different intended use case.) - Have you had an issues with behavior differences between CPUs? I know there is architecture-level undefined behavior that can differ between CPUs; on the other hand, it sounds like you’re primarily interested in running well-behaved executables that wouldn’t intentionally invoke such behavior.

jasonwhite 4y ago
- We've taken a lot of inspiration from RR and it is very good at what it does (record/replay + randomizing thread schedules). This project diverges a bit from RR in that we focus more on the concurrency testing application of determinism. I wrote the toy record/replay system that sits on top of the determinism layer (so that we don't have to record as much stuff), but it's a long way from being complete. - I haven't seen libTAS until now, so I can't comment on it much. At first glance, it does look similar! - See @rrnewton's reply on this one.
rrnewton 4y ago
(1) rr [formerly Mozilla rr] We're big fans of rr! Hermit is different in that creating a deterministic OS semantics is different than recording whatever nondeterministic behavior occurs under normal Linux. BUT, there's a lot of overlap. And indeed `hermit record` is straight up RnR (record & replay). But hermit for RnR but is not nearly as developed as rr. We integrate with gdb/lldb as an (RSP) debugger backend, just like rr. Any failing execution you can create with hermit, you can attach a debugger. But our support is very preliminary, and you'll probably find rough edges. Also, we don't support backwards stepping yet (except by running again). If we invest more in using Hermit as a debugger (rather than for finding and analyzing concurrency bugs), then there should be some advantages over traditional RnR. These would relate to the fact that deterministically executing is different than recording. For example, process and thread IDs, and memory addresses all stay the same across multiple runs of the program, even as you begin adding printfs and modifying the program to fix the bug. With traditional RnR, you can play the same recording as many times as you like, but as soon as you take a second recording all bets are off wrt what is the same or different compared to the prior recording. (That includes losing the "mental state" of things like tids & memory addresses, which is a good point Robert O Callahan makes about the benefits of RnR when accessing the same recording multiple times.) (2) libTAS - no we haven't! Checking it out now. (3) Yes, definitely issues with CPU portability. In general, we are interested in not just determinism on the same machine, but portability between machines in our fleet. As with any tech company that uses the cloud, at Meta people are usually trying to debug an issue on a different machine than where the problem occurred. I.e. taking a crash from a production or CI machine to a local dev machine. The way we do this is that we mostly report a fairly old CPU to the guest, which disables certain features IF the guest is well behaved. With the current processor tech, I don't think there's any way we can stop an adversarial program, which, for example, would execute CPUID, find that RDRAND is not supported on the processor, but then execute RDRAND anyway. We could build a much more invasive binary-instrumentation based emulator that would be able to enforce these kinds of rules at the instruction granularity, but it would have higher overhead, especially startup overhead. The nice thing about Reverie though is that we (or others) can add different instrumentation backends while keeping the same programming instrumentation API. So we could have a "hardened" backend that was more about sandboxing and reverse-engineering adversarial software, making a different tradeoff with respect to performance overhead.

wyldfire 4y ago

> AMA! Eager to try it but encountering the build error here - https://github.com/facebookexperimental/hermit/issues/11 https://github.com/facebookexperimental/hermit/issues/11 Do you have a reference build log / environment you can share? Last known good commit sha and/or output from "rustup show"?

jasonwhite 4y ago
We're working on it! Should be fixed soon.
- rrnewton 4y ago
  Reverted a badly-timed breaking change that came through the sync system. Will fix it properly shortly (and add a Dockerfile and release tag). But for now you may have better luck on the main branch after that reversion, which yielded 6cb5575ffd287289769144ec82e2900cbf6cd1ad. Let's discuss further on that issue #11.

oulipo 4y ago

Would something like this work for embedded code, like ESP32?

rrnewton 4y ago
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).

gmartres 4y ago

Thanks for open-sourcing this! Roughly, what's the performance overhead from running code under hermit? I'm wondering if this could be used for doing benchmarking with less variance on non-deterministic platforms such as the JVM (I assume hermit is "deterministic enough" that the JIT and GC threads of the JVM will run the same code on every execution?)

rrnewton 4y ago
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.
- dekhn 4y ago

wizeman 4y ago

> AMA! I have a few questions. Hermit's README says: > Instead, in order to provide complete determinism, the user should provide a fixed file system base image (e.g., with Docker) How are you sanitizing the result of stat(), for example? I'm guessing you're already aware of this, but fixed file system images are not sufficient to guarantee deterministic behavior by filesystems. Specifically, inode numbers are not guaranteed to be assigned in any order. So how do you return deterministic inode numbers in stat() calls? I'm sure you're also aware of this, but other filesystem results are also not guaranteed to be deterministic. For example, the `st_nblocks` and `st_blksize` fields in `struct stat` can change in-between stat() calls when nothing else happens from the user-space point of view except time passing (this happens in ZFS, for example, due to delayed allocation). statvfs() is another problematic call which would have to be heavily sanitized. As another example, there are filesystems that generate a random seed for every directory that is created, to prevent applications from exploiting hash table weaknesses and causing a denial-of-service when creating many directory entries that hash to the same value. This random seed can have the side effect of readdir() calls returning directory entries in a different order based on the seed, even if the directory was created in the exact same way (with identical directory entries, created in the same order). It seems like this would require reading the entire directory and then sorting the results, even when doing a single readdir() call to read a single directory entry. Similarly, telldir() / seekdir() can also be problematic because the cookie value returned by the filesystem in telldir() is opaque and would be different for different directory seed values. This seems like it would require Hermit to maintain a full in-memory view of all the directory entries of a directory that is opened and is being read, which also means that this in-memory view can become out-of-date in-between readdir() / telldir() / seekdir() calls by one process and calls that modify the directory by another process (Edit: I guess Hermit can synchronize this view easily since it can assume it has full control of all processes inside the container). It also seems like Hermit would also need to re-read the entire directory when rewinddir() is called, to avoid introducing non-previously-existing concurrency bugs like described in the above paragraph (Edit: again, this is probably not necessary since Hermit can maintain a synchronized view of a directory on its own). Reading the directory also seems to imply that you'd have to assign deterministic inode numbers for all directory entries, which also seems non-trivial. Do you think this is an accurate assessment of the situation? How does Hermit handle all of this? Also, CPUs can (according to the manuals, at least) behave non-deterministically when executing instructions in certain undefined conditions. How do you handle this? Last question: how do you sanitize the RDTSC CPU instruction?

wyldfire 4y ago

Are there any limitations regarding hermit running programs which emit code at runtime?

jasonwhite 4y ago
There shouldn't be! We don't do any sort of binary rewriting, which is the typical problem with JITed code.

wizeman 4y ago

Sorry, just an additional question as this project is so interesting: Does Hermit support running different processes in parallel in certain situations? It seems like this should be possible to do as long as they are appropriately isolated from each other. Specifically, if two processes don't share any writable memory mappings then I'm thinking it might be possible for Hermit to exploit the underlying existing isolation between them so that they could run code in-between system calls in parallel (while still making sure that the actual system calls happen in a deterministic order). Perhaps it would even be possible for the two processes to execute system calls in parallel if they are unrelated and they do not affect deterministic execution (such as if they are doing I/O to different files or directories, or one process doing I/O while another is doing something completely unrelated like getting the time, etc). Although I guess this latter point (of executing syscalls in parallel) would require doing rewind/replay because it wouldn't be possible to know in advance whether the system calls are going to be related or not, as the two processes might not do the syscalls at exactly the same time. Is Hermit doing this (executing code in-between syscalls in parallel, at least)? Or do you think it would be possible to do it? This could significantly increase the usefulness of Hermit for distros that want to do deterministic builds of packages, as most compilation could happen in parallel / i.e. use several cores at the same time! I'm thinking about huge package builds such as Chromium, Firefox, the Linux kernel, etc. which would perhaps take days to build if they were completely serialized into a single CPU core.

rrnewton2 4y ago
[Caught by the no-procrastination feature by accident.] Our earlier (dettrace) prototype allowed syscall-free regions in separate processes to run physically in parallel. Hermit actually hasn't added any process parallelism yet, but it's designed to actually go further than dettrace in this respect. Specifically, Hermit is architected so that the thread-local syscall handler "checks out" resources from the central scheduler. Resources include things like paths on the file system, contents of files, shared memory, and permission to perform external side effects. Right now, all requests wait for the scheduler to background all other threads and make the current thread the only runnable. But the idea is: in the future we will keep the semantical identical log of linear "commits" (linearization), but will simply background the current thread while it uses the resources they checked out, move forward to the next scheduler iteration, and only block the next runnable thread until its requested resources are freed, not until ALL other threads have finished their timeslice and gone back to waiting on the scheduler.