time travel

an important tenet of dynamic race condition detection is being able to selectively go back in time to an earlier point in the guest's execution and make a different decision about which thread interleaving to choose next. the set of possible execution interleavings can be thought of as a tree, where each edge/node represents a scheduling decision (which thread to run next?) at a choice point (a point at which it might be interesting to preempt the guest).

the really interesting question that I'll be tackling in the months to come is how to reduce the size of this tree to something manageable - for which I'll be borrowing ideas from dBug, possibly among other previous work - but for now, i'm setting up infrastructure that lets me explore the tree.

in order to do so productively, though, landslide needs to preserve at least some state when jumping back to an earlier point to make a different decision, or else it won't be able to do any meaningful analysis (e.g., where to prune the tree, or even where it's visited before). but, landslide also tracks a lot of information about the guest kernel's execution (so it can know, for example, which threads are runnable), and that information should not be preserved, since it's specific to each particular execution path.

what data is important to preserve when travelling "back in time", as it were, and what data should we discard? the implementation mechanism for restoring old state is already somewhat obtuse, and combined with all the different types of state that landslide manages, makes this somewhat difficult to think about.

I realised, though, that there's already been a situation where I had to solve exactly this problem...

now I need to figure out how to work the game's other mechanics into my code as well, right?