multi-memory VS reference-crdts

Support for multi-memory to deal with multiple memories in Wasm.

> You can do attacks that most people haven't been able to do for 20+ years.

This is a bad and roundabout way to say that vulnerabilities in WebAssembly modules may cause a corruption in their linear memory. Which is absolutely true, but those attacks still matter today (not everyone turns ASLR on) and similar defences also apply. In the future multiple memories [1] should make it much easier to guard against remaining issues. WebAssembly is a lucrative target only because it is so widespread, not because it has horrible security (you don't know what the actually horrible security looks like).

[1] https://github.com/WebAssembly/multi-memory/blob/main/propos...

Thanks! These claims are really interesting.

- WASM has no ASLR.

So I guess if a buffer overrun lets you modify a function pointer, you could replace that function pointer with another pointer to execute different code. As you say, this is hard in native linux programs because ASLR and NX. You need a pointer to some code thats loaded in memory and you need to know where it is. In wasm, the "pointer" isn't a pointer at all. indirect_call takes an index into the jump table. Yes, this makes it easier to find other valid function pointers. But wasm also has some advantages here. Unlike in native code, you can't "call" arbitrary locations in memory. And indirect_call is also runtime typechecked. So you can't call functions with an unexpected type signature. Also (I think) the jump table itself can't be edited by the running wasm module. So there's no way to inject code into the module and run it.

I could be wrong, but I wouldn't be surprised if on balance wasm still ends up safer than native code here. I'm sure there will be more than zero wasm sandbox escapes made by abusing this, but I haven't heard of any so far.

Docs: https://developer.mozilla.org/en-US/docs/WebAssembly/Underst...

- WASM allows writing to 0x0.

You're probably right about this. To be clear, it means if pointers are set to 0 then dereferenced, the program might continue before crashing. And the memory around 0 may be overwritten by an attacker. How bad this is in practice depends on the prevelance of use-after-free bugs (common in C / C++) and what ends up near 0 in memory. In rust, these sort of software bugs seem incredibly rare. And I wouldn't be surprised if wasm compilers for C/C++ start making a memory deadzone here - if they aren't doing that already.

- wasm can easily overflow buffers

Sure, but so can native C code. And unlike native code, wasm can't overflow buffers outside of the data section. So you can't overwrite methods or modify the memory of any other loaded modules. So on net, wasm is still marginally safer than native code here. If you're worried about buffer overflows, use a safer language.

- wasm doesn't have the concept of read-only memory

Interesting! I can see this definitely being useful for system libraries like mmap. This would definitely be nice to have, and it looks like the wasm authors agree with you.

https://github.com/WebAssembly/multi-memory/issues/15

There are stray references to the concept of multiple address spaces (or 'memories') in the wasm spec at present, and I recall at one point you may have always been passing 'memory #0' to your load/store opcodes. It looks like people are still working on that as the solution.

https://github.com/WebAssembly/multi-memory

It's not segmented, so no... or rather, not yet.

The wasm spec already accommodates to some extent the notion of multiple "memories" (i.e. distinct flat heaps), although it only allows for one in practice:

https://webassembly.github.io/spec/core/syntax/modules.html#...

And there's an active proposal to allow for multiple memories:

https://github.com/WebAssembly/multi-memory/blob/main/propos...

In an environment like that, you'd need full-fledged pointers to carry both the memory index and the offset; and then you might want a non-fat "pointer to same memory" alternative for perf. Might as well call them far and near.

> The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client.

Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse!

Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop:

1. Generates some random changes on some fake "peers"

2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm

3. Assert that the state has converged between the peers

I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this.

When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word.

As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4...

The code is so small it almost fits on my laptop screen.

> In this case, the bottleneck at 9 million LoC is not CPU cycles but memory usage. That's where I am considering pushing down into WebAssembly

How often does this come up in practice? I can't think of many files I've opened which were 9 million lines long. And you say "LoC" (lines of code). Are you doing syntax highlighting on 9 million lines of source code in javascript? Thats impressive!

> I guess my point is why do you need balanced trees? Is this a CRDT specific thing? Can you implement CRDT with just an array of lines / gap buffer?

Of course! Its just going to be slower. I made a simple reference implementation of Yjs, Automerge and Sync9's list types in javascript here[1]. This code is not optimized, and it takes 30 seconds to process an editing trace that diamond types (in native rust) takes 0.01 seconds to process. We could speed that up - yjs does the same thing in 1 second. But I don't think javascript will ever run as fast as optimized rust code.

The b-tree in diamond types is used for merging. If you're merging 2 branches, we need to map insert locations from the incoming branch into positions in the target (merged) branch. As items are inserted, the mapping changes dynamically. The benchmark I've been using for this is how long it takes to replay (and re-merge) all the changes in the most edited file in the nodejs git repository. That file has just shy of 1M single character insert / delete operations. If you're curious, the causal graph of changes looks like this[2].

Currently it takes 250ms to re-merge the entire causal graph. This is much slower than I'd like, but we can cache the merged positions in about 4kb on disk or something so we only need to do it once. I also want to replace the b-tree with a skip list. I think that'll make the code faster and smaller.

A gap buffer in javascript might work ok... if you're keen, I'd love to see that benchmark. The code to port is here: [3]

> Undo support -> In which case, you only have to stack / remember the set of commands and not have to store the state on every change. I'm not sure if this overlaps with the data structure choice, other than implementation details.

Yeah, I basically never store a snapshot of the state. Not on every change. Not really at all. Everything involves sending around patches. But you can't just roll back the changes when you undo.

Eg: I type "aaa" at position 0 (the start of the document). You type "bbb" at the start of the document. The document is now "bbbaaa". I hit undo. What should happen? Surely, we delete the "aaa" - now at position 3.

Translating from position 0 to position 3 is essentially the same algorithm we need to run in order to merge.

> I was just looking into TypedArrays.

I tried optimizing a physics library a few years ago by putting everything in typedarrays and it was weirdly slower than using raw javascript arrays. I have no idea why - but maybe thats fixed now.

TypedArrays are useful, but they're no panacea. You could probably write a custom b-tree on top of a typedarray in javascript if you really want to - assuming your data also fits into typedarrays. But at that point you may as well just use wasm. It'll be way faster and more ergonomic.

[1] https://github.com/josephg/reference-crdts

[2] https://home.seph.codes/public/node_graph.svg

[3] https://github.com/josephg/diamond-types/tree/master/src/lis...