Korona wrote:
Yes, B-trees are generally faster than BSTs (unless the keys are really huge) in benchmarks due to their better caching behavior.
The depth of AVL trees (or red-black trees) grows logarithmically - doubling the number of intervals only increases the depth by 1. The locking might be more problematic. You could partition the virtual address space (say, in 4 GiB blocks) and use a radix tree for the first few levels (but radix trees do not efficiently support interval operations).
I've been thinking about partitioning. I don't know how to determine the "optimal" partition size, I guess it differs on what you run so it's not really possible to determine.
Korona wrote:
Regarding software isolation: Note that most kinds of software isolation are broken by Spectre/Meltdown (and this will be even easier in the kernel where you cannot really defend against Meltdown). Browsers generally run wasm code of different origins in different virtual address spaces.
Yeah, I'm aware of the issue. I believe Spectre v2 could be mitigated against using retpoline, but I need to read up on that again.
As for spectre v1 & meltdown, this is afaik not fixable in this case.
There are CPUs now with some of these side channels fixed, but ofc most CPUs are older than that.
Since this is not a serious project and since they would be fixed in hardware in the future eventually, I'm not really going to bother with it.