4 ms·

Can't the same trick be used for slightly more bits? 64-bit uses 48 bits nowadays AFAIK, which is 256 TB. It's usually 50/50 for user/kernel mode. If, say, WASM

Can't the same trick be used for slightly more bits? 64-bit uses 48 bits nowadays AFAIK, which is 256 TB. It's usually 50/50 for user/kernel mode. If, say, WASM takes half of the user mode address space, it's still 46 bits which is 64 TB (ought to be enough for anybody?). Or maybe I'm way off, I don't really know the specifics of the trick you're referring to.

jsheard 2y ago
The problem is you need the virtual memory allocation to span every possible address the untrusted WASM code might try to access, so that any possible OOB operation lands in an unmapped page and triggers a fault. That's only feasible if the WASM address space is a lot smaller than the host address space. I suppose there might be a compromise where you cap a 64bit WASM instance to (for example) an effective 35bit address space, allocate 32GB of virtual memory and then generate code which masks off the top bits of pointers so OOB operations safely wrap around without having to branch, but I'm not sure if the spec allows that. IIRC illegal operations are required to throw an exception.
Findecanor 2y ago
The trick takes advantage of 32-bit registers automatically being zero-extended to 64. It actually uses 8GB of allocated address space because WASM's address mode takes both a "pointer" and a 32-bit offset, making the effective index 33 bits. On x86-64, there are address modes that can add those and the base address in a single instruction. When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. On x86-64 and ARM that would be done with a `cmp`and a conditional move. RISC-V (RVA22 profile and up) has a `max` instruction. That would be typically one additional cycle. The new proposal is for using a 64-bit pointer and a 64-bit offset, which would create a 65-bit effective index. So neither method above could be used. I think each address calculation would first have to add and check for overflow, then do the bounds-check, and then add the base address to the linear memory.
- deleted 2y ago
  [deleted]
- Retr0id 2y ago
  A saturating add instruction could help do the same trick without checking for overflows first, although they seem fairly uncommon outside of SIMD instruction sets (aarch64 has UQADD for example)
- BeeOnRope 2y ago
  > When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. If you are already doing a cmp + cmov, wouldn't you be better off just doing a cmp + jmp (to OOB handler)? The cmp + jmp can fuse, so it's probably strictly better in an execution cost sense, plus it doesn't add to the critical data-dependent chain of the load address, which would otherwise add a couple of cycles to the address data chain. Of course, it does require you have these landing pads for the jmp.
  - lossolo 2y ago
    CMP + JMP have a branch, which can be mispredicted and then you may pay 5-10x more than for cmp + cmov.
    - BeeOnRope 2y ago
      They won't be mispredicted nor take predictor resources since the default prediction is "not taken" and these branches are never taken (except perhaps once immediately before an OOB crash if that occurs). So they are free in that sense.
- Joker_vD 2y ago
  > RISC-V (RVA22 profile and up) has a `max` instruction. You know, it's kind of insane that things like this are nigh impossible to learn from the RISC-V official site. Googling on the site itself doesn't yield anything; you have to go to the "Technical > Specifications" page which has PDFs on the basic ISA from 2019, but not on the newer frozen/ratified extensions, and a link to the "RISC-V Technical Specifications" page on their Attlassian subdomain, where you can find a link to a Google doc "RISC-V profiles" and there you will learn that, indeed Zbb extension is mandatory for RVA22U64 profile (and that, apparently, there is no RVA22U32 profile). And of course, you have to know that Zbb extension is the one that has max/min/minu/maxu instructions in it; grepping for "min" or "max" won't find you anything. Because why bother listing all the mnemonics of the mandatorily supported function in a document about the sets of instructions with mandatory support? If someone's reading a RISC-V document, they obviously have already read all the other RISC-V docs that predate it, that's the target audience, after all.

jsheard 2y ago

The problem is you need the virtual memory allocation to span every possible address the untrusted WASM code might try to access, so that any possible OOB operation lands in an unmapped page and triggers a fault. That's only feasible if the WASM address space is a lot smaller than the host address space. I suppose there might be a compromise where you cap a 64bit WASM instance to (for example) an effective 35bit address space, allocate 32GB of virtual memory and then generate code which masks off the top bits of pointers so OOB operations safely wrap around without having to branch, but I'm not sure if the spec allows that. IIRC illegal operations are required to throw an exception.

Findecanor 2y ago

The trick takes advantage of 32-bit registers automatically being zero-extended to 64. It actually uses 8GB of allocated address space because WASM's address mode takes both a "pointer" and a 32-bit offset, making the effective index 33 bits. On x86-64, there are address modes that can add those and the base address in a single instruction. When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. On x86-64 and ARM that would be done with a `cmp`and a conditional move. RISC-V (RVA22 profile and up) has a `max` instruction. That would be typically one additional cycle. The new proposal is for using a 64-bit pointer and a 64-bit offset, which would create a 65-bit effective index. So neither method above could be used. I think each address calculation would first have to add and check for overflow, then do the bounds-check, and then add the base address to the linear memory.

deleted 2y ago
[deleted]
Retr0id 2y ago
A saturating add instruction could help do the same trick without checking for overflows first, although they seem fairly uncommon outside of SIMD instruction sets (aarch64 has UQADD for example)
BeeOnRope 2y ago
> When that trick can't be used, I think the most efficient method would be to clamp the top of the address so that the max would land on a single guard page. If you are already doing a cmp + cmov, wouldn't you be better off just doing a cmp + jmp (to OOB handler)? The cmp + jmp can fuse, so it's probably strictly better in an execution cost sense, plus it doesn't add to the critical data-dependent chain of the load address, which would otherwise add a couple of cycles to the address data chain. Of course, it does require you have these landing pads for the jmp.
- lossolo 2y ago
  CMP + JMP have a branch, which can be mispredicted and then you may pay 5-10x more than for cmp + cmov.
  - BeeOnRope 2y ago
    They won't be mispredicted nor take predictor resources since the default prediction is "not taken" and these branches are never taken (except perhaps once immediately before an OOB crash if that occurs). So they are free in that sense.
Joker_vD 2y ago
> RISC-V (RVA22 profile and up) has a `max` instruction. You know, it's kind of insane that things like this are nigh impossible to learn from the RISC-V official site. Googling on the site itself doesn't yield anything; you have to go to the "Technical > Specifications" page which has PDFs on the basic ISA from 2019, but not on the newer frozen/ratified extensions, and a link to the "RISC-V Technical Specifications" page on their Attlassian subdomain, where you can find a link to a Google doc "RISC-V profiles" and there you will learn that, indeed Zbb extension is mandatory for RVA22U64 profile (and that, apparently, there is no RVA22U32 profile). And of course, you have to know that Zbb extension is the one that has max/min/minu/maxu instructions in it; grepping for "min" or "max" won't find you anything. Because why bother listing all the mnemonics of the mandatorily supported function in a document about the sets of instructions with mandatory support? If someone's reading a RISC-V document, they obviously have already read all the other RISC-V docs that predate it, that's the target audience, after all.