Implement Auto Splitting

[CryZe]

I'm surprised there's no issue about this. Apparently I only ever created a Pull Request that I closed for it. So this serves as the tracking issue for the auto splitters.

We are using WebAssembly as the "scripting language" of choice for livesplit-core's auto splitting. We initially were choosing among various Rust and C based scripting languages (see #27) but ultimately decided against any specific one of them due to either immaturity, security or other limitations of those languages. By choosing WebAssembly the auto splitter scripts run in a fully sandboxed environment where they can not escape and we can gracefully shut them down if they either crash or hang. We specify clearly the APIs they can use, unlike the Auto Splitters in the original LiveSplit that had full access to all our internals. In addition WebAssembly allows you to choose any language that you'd like to use for writing your script in, which allows us to have a highly domain specific high level language such as the original ASL again, but also allow for the option of using Rust, C, C++ or any other low level language, which can now even statically link all kinds of helper libraries for full low level control over the memory they are reading from the game's process. Also there's the option of using higher level scripting languages such as TypeScript / JavaScript or Python. So there's a lot of possibilites in this space.

As the library of choice we started out with wasmi (the wasm interpreter), which is fast enough for most use cases, but especially when using Python as the language for implementing the scripts, it begins to show some slowdowns. That's why we are slowly gravitating towards wasmer + cranelift which so far seems to be a great choice for actually compiled wasm code. However there's some issues (such as calling conventions on Windows) that still need to be figured out until we can make the full switch here.

Also so far all of this only compiles on Windows, so some of the process / memory APIs need to be implemented for macOS and Linux as well.

[rhelmot]

Hi! I'm interested in working on this, specifically to add the linux apis. I only know a little rust but I have a lot of systems background. I read over your branches and I think I get the gist of how this all works.

Do you have any advice in terms of how to design a generic environment interface that doesn't require too much code reuse?

Also, where are you keeping the autosplitters that you've been testing with?

[CryZe]

Hey, I'll try to get back to you on the weekend. At the moment I have like three different branches that all are kinda messy and very different. So it's hard for you to contribute here. I'll clean it up and then try to give you some instructions on how you can help.

[kitlith]

I would also like to help with this, especially with making it work on linux. ptrace should easily cover most use cases, which happens to already be nicely wrapped in rust in the nix crate: https://docs.rs/nix/0.14.1/nix/sys/ptrace/index.html

However, for programs running under wine, something else may be necessary since wine already uses ptrace, according to some sources? Maybe attaching with winedbg, etc? (I'd like to support applications running under wine so I don't have to use a timer running under wine for some games and a native timer for other games.)

[kitlith]

Alternatively, we could try using gdb/mi in both cases, meaning we already have a high level interface for watchpoints and such. The downside is that gdb would have to be installed.

[CryZe]

I don't think we need ptrace at all initially. Auto Splitters usually just need to read memory and you can do so through other means. Although ptrace may actually be interesting for auto splitters to use as well.

http://man7.org/linux/man-pages/man2/process_vm_readv.2.html
https://docs.rs/read-process-memory/0.1.2/read_process_memory/

[kitlith]

made a PR against your wasmer branch. Still need to reimplement with_name, but other than that it compiles on linux now.

[MarkMcCaskey]

Just stopping by to say that this is awesome! Let me know if there's anything I can do to help with this. We discussed the WASI part on wasmerio/wasmer#583 but I can probably also help with the design and implementation too!

[kitlith]

I've been working on it over here, I'd be glad to have your feedback: CryZe#1

It's a bit rough at the moment, mainly because I've been focusing on getting something that works well enough over having a good API, for the most part.

[kitlith]

Might i suggest a slight orginizational change @CryZe? Instead of having the autosplitting branch on a personal fork, put it on this repo, then perhaps open a pull request against master. Other people can PR against the autosplitting branch, etc, and it's all kept more central/visible.

I feel like it's going to take awhile before we have an API that we consider mergable into master, and the more people that see the progress/comment, the better.

[kitlith]

Something for the future (probably not immediately): livesplit-core tries to be no-std compatible (and CryZe has previously demo'd it running under Wind Waker). Therefore, we may want to allow for the option of statically linked autosplitters to reduce overhead and requirements for those applications. (you wouldn't interpret wasm under wind waker... would you?)

[DarkRTA]

Something else that should be added is the ability to monitor a log file.

Some games output info to a log file that is useful for auto-splitting.

[CryZe]

Auto Splitting, just like all the networking (splits.io, speedrun.com) is optional, so it only gets compiled in when needed. So it doesn‘t clash with the no_std support.

[CryZe]

Reading a log file shouldn‘t be a problem with WASI. No idea if they are planning for an inotify API though. If not, we can provide one.

[kitlith]

I'm trying to suggest autosplitters on no_std (just without wasm, so more limited language selection) so that when you run livesplit under wind waker you can embed the autosplitter for it without much overhead.

Again, not as important as the base autosplitting support.

[CryZe]

I guess we can have the rough logic in livesplit-core and then support plugging in the underlying implementation via a trait that you implement. The WASM based runtime would then also implement this trait. idk if this is actually all that necessary though, as the Timer type already provides all the things you would need to control everything an auto splitter would do.

What would be possible though is that we could compile a Rust auto splitter that we would usually compile to WASM, to an implementation of the trait. Definitely worth considering.

[kitlith]

Something we may want to consider API wise: autosplitters that work for multiple routes/with multiple possible event types? I'm mainly thinking of antitimer here, which lets you set splits on e.g. gun color, if a certain sign has been activated, if a certain sound is played (game completion), etc.

Currently, antitimer hooks into livesplit via livesplit server, i assume there'll be (if there isn't already) an equivilant for livesplit-core. My question is: would it be reasonable to have this kind of abstraction in livesplit itself? i.e. autosplitters send events with associated data, and splits can have events associated with them, so a split is triggered if the event an autosplitter sends matches the event associated with a split?

This may be overcomplicating things. Just had the idea pop up.

[CryZe]

I guess there's two parts to this.

One would be to allow running auto splitters that are not running directly within LSO. livesplit-core itself is flexible in that it can handle setting game time and co. from a source that is not the auto splitter runtime. And the auto splitter runtime is also capable of running outside of LiveSplit. But more importantly we need some kind of protocol for supporting networking across the network. I guess this should probably be part of #260. At the moment the protocol is mostly designed for observing, but we should probably extend it to support controlling as well (as an optional thing). Though maybe controlling is just LSO observing the auto splitter's timer? Not sure.

The other is part of how you "parse segments". We have this problem not only for auto spltitting but also for importing comparisons and doing live race comparisons. There you need to have a reasonably good understanding of how a foreign list of splits correlates with your local knowledge. So yeah I believe we want to have a better, more unified story there of how we want to approach this.

[DarkRTA]

We've made a lot of progress planning-wise with this, and I'm going to compile a list of various things that need to be addressed

• Make my branch with all existing work rebased on top of master a branch in this repo. (https://github.com/DarkRTA/livesplit-core/tree/wasmtime)
• Rewrite a tool needed to get auto splitting to work properly on Linux in Rust as we probably do not want very much C code. (Add a Linux-only tool needed for Auto Splitting to work correctly. #356 )
• Fix the issue where livesplit-core will not detect an unhook without a pointer path. (Auto-splitting for Linux CryZe/livesplit-core#2 (comment))
• Figure out why the SAR auto splitter just randomly dies during signature scanning (might not be an issue with livesplit-core)
• Figure out how to adequately sandbox the autosplitter.
• Expose auto splitting to the C API. Add support for Auto Splitting to the c api.  #355

If anyone has anything else to add, feel free to let me know.

[CryZe]

This branch is now the official branch that we are working on. Feel free to do PRs against it:

https://github.com/LiveSplit/livesplit-core/tree/auto-splitting

[kitlith]

RE: the C program, std has https://doc.rust-lang.org/std/os/unix/process/trait.CommandExt.html#tymethod.exec to wrap execvp, libc has raw bindings to ptrace, nix and ptracer have various levels of more idomatic bindings to ptrace though i'm not sure they include the specific usage that we want.

The LD_PRELOAD stuff we may want to just leave in C if we're going to keep it, but there is a ld_preload crate with a few possibly helpful macros?

Also, I think there's another possible workaround to forking losing the relevant ptrace flag that we could use. If we started the game as a child process instead of execvp-ing into it, then the parent process can still ptrace into the child processes and thus can pass file descriptors via unix domain sockets. But. That's more complicated, and can be left to another time.

If all goes well, and I get a couple of other things done today, I can start on that program. We'll see what happens.

[DarkRTA]

I don't see much harm in leaving the tool in C as its only about 80 lines with no external dependencies, but it would be nice to have it be a proper rust crate.

All the tool really does is call prctl() then exec(), and sets LD_PRELOAD if desired. Reimplementing it in rust isn't going to be a huge challenge.

The LD_PRELOAD stuff we may want to just leave in C if we're going to keep it, but there is a ld_preload crate with a few possibly helpful macros?

LD_PRELOAD doesn't need anything special to get working besides just exposing a function like we'd do in our c bindings, and then compiling the resulting code as a shared library for both x86 and x86_64

#[no_mangle]
pub extern "C" fn fork() -> i32 {
    // call the real fork then run prctl in the child process,
    // returning the result from the fork system call
}

The only major roadblock might be getting a function pointer to the real fork()

---

Also @CryZe, do you mind removing the stalled label as this isn't really stalled anymore.

[kitlith]

It's going to be a call to dlsym, just like in the C version. There doesn't seem to be an existing crate that performs RTLD_NEXT, but shrug.

I agree that it's not a big deal if we leave it in C, just figured that we could check it off.

[DarkRTA]

@kitlith I've just finished rewriting it in rust and it seems to work fine.

You'll just have to build for both x86_64 and i686 and copy the shared objects into the right places.

I'll open a PR for it later.

[thecodewarrior]

Edit: removed two-weeks-ago me barging in and telling everyone how to solve their problem

I look forward to seeing how this goes! I've already created a bit of an autosplitter prototype for Celeste, so after a bit more proper research into how you're doing things I might be able to help with macOS support. :)

Edit 2: I just finished the autosplitter, SwiftSplit. Came to find out LiveSplit One already has a WebSocket API that's precisely what I was imagining in my previous reply, and exactly what I needed!

[thecodewarrior]

The main wrinkle when it comes to reading other process' memory on macOS is that you either have to run as root or be a signed, notarized app with a "Hardened Runtime" and the "debugging tool" access.

It might be feasible to have a small embedded app that provides access to the necessary memory reading APIs, but that would require a separate file be distributed alongside livesplit-core.

The main autosplitter hitch, and the thing that really threw a spanner in SwiftSplit's development, is macOS's address space layout randomization. The Windows autosplitter for Celeste has a few hard-coded signatures corresponding to the AutoSplitterInfo's object header (from what I can tell), but on macOS the object header is different every time you launch the game.

I solved this by listening for the game to launch, immediately scanning for the uninitialized state (which by some miracle is unique enough), then I back up and grab the object header in case it moves at some point. I'm not familiar with the built-in methods for doing this in LiveSplit, but they would have to at least support things like listening for app launches.

[kitlith]

@thecodewarrior re "small embedded app" that's basically the situation we're in with #356 which is basically a workaround for a mitigation commonly used on linux.

do you think a similar approach could be used for macOS? (i.e. if a process on macOS can ptrace/read its own memory without these special considerations, then we can make the tool in #356 do the relevant thing for macOS, too.)

from my observations, ASLR with livesplit in general is handled either with the already noted signature scan or through (module relative) pointer paths, my guess is that you want to make some new(?) signatures for macOS that don't have requirements on the bytes in the object header that are changing. (basically dump the initialized object header a few times, and observe what bytes are changing, and replace those bytes with "??" iirc in the signature)

[thecodewarrior]

If you want to go the route of having a custom launcher process, I found this rust crate a while ago. I haven't tested it, but if it works then we shouldn't need any extra permissions.

[thecodewarrior]

my guess is that you want to make some new(?) signatures for macOS that don't have requirements on the bytes in the object header that are changing.

If it isn't possible to ignore bytes in a signature right now then yes that would be vital. It would also be important to be able to create a signature programmatically based upon the resulting data (potentially even the data around the signature).

As an example of what I would be doing, here's how SwiftSplit does this for Celeste:

Here's my breakdown of what the AutoSplitterData object looks like. It includes the placeholders I used to figure out the memory layout (I created a custom mod that created instances and logged their addresses so I could inspect them), as well as the "uninitialized" state when the game launches and before any saves are loaded.

10b212968c7f0000 00000000 00000000 b83c632d01000000 f1aaaa1f f1bbbb1f 01010100 00000000 - placeholders
--------######## -------- ######## --------######## -------- ######## -------- ########
0       4        8        12       16      20       24       28       32       36
10e28b84a07f0000 00000000 00000000 b009150f01000000 ffffffff ffffffff 00000000 00000000 - Fresh launch state

11ffeeddccbbaa11 f1cccc1f 01010000 11addeefbeadde11 f1dddd1f f1eeee1f f1ffff1f 00000000 - placeholders
--------######## -------- ######## --------######## -------- ######## -------- ########
40      44       48       52       56      60       64       68       72       76
0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 00000000 00000000 - Fresh launch state

Based upon that, I first scan for the "uninitialized" state of the object using this signature (I include the 7f at the start because it seems constant enough and it makes my scanning algorithm not backtrack constantly whenever there's a long series of zeros):

          7f00000000000000000000????????????????ffffffffffffffff0000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000

I then back up and grab the actual C# object header:

10b212968c7f0000 

From that point onward I use the object header to verify that the object hasn't been moved, and to find it again if it has.

[thecodewarrior]

Now in terms of the API, I have a few thoughts.

#176 (comment)

Something we may want to consider API wise: autosplitters that work for multiple routes/with multiple possible event types?

I feel like at least having the option of using events would be nice. SwiftSplit uses these already, and I think it could be improved beyond simple string equality.

I don't know how much of this, if any, is on LiveSplit itself, but after looking at LiveSplit.Celeste's split code I feel like using events is simpler (e.g. SwiftSplit's split code) and more flexible.

#176 (comment)

One would be to allow running auto splitters that are not running directly within LSO.

I think having a network API for controlling livesplit-core would be useful for the flexibility it offers, and if we use an event-based system it would probably be pretty easy to implement. As I mentioned in LiveSplit/LiveSplitOne#459, it would also be convenient if livesplit-core could communicate custom settings data with external autosplitters.