Size limit for memories with 1-byte-pages ?

[wingo]

It would be nice to be able to bounds-check accesses in a single operation. For example, an i32.load access at address 5 to a memory with length 7 must trap, and it would be nice to just be able to compare 5 to a limit instead of separately comparing 5 and 5+sizeof(u32) to a limit. I am assuming that with 1-byte pages, we get no OS support.

@eqrion suggested having an instance store memory limits for different-sized accesses, so in our example the limit for 32-bit accesses on a memory with length 7 would be 3; you just compare 5 against 3. This is a neat solution that works as long as the length is at least as long as the access size, or if the max size is set such that we can do signed comparisons. However I think as written the spec supports length=0, length=1, length=2^32-1, and also length=2^64-1 for memory64 configurations.

I have a terrible proposal :) Perhaps people have already considered it. Anyway, considering that the JS embedding specifies a max page count of 65536 (for memory32), I propose to keep the max page count to that size for 1-byte pages. It minimizes complexity for bounds checks, because we can do a simple signed comparison in all cases. If it is too constraining, we can raise it, but perhaps not to the whole address space.

[wingo]

@eqrion kindly points out to me that there is no need for two bounds checks in any case; for a memory of size LEN and an access size of M bytes, there are LEN - M + 1 valid addresses, and my concern about wraparound is moot. However the proposal should probably include an update to the JS embedding specification, if that is its intention!

[fitzgen]

(Apologies for the delayed response! Missed this somehow.)

---

This idea has not been proposed before.

And the JS embedding has not been discussed in too much detail either, although there is an issue on file: #33

I don't personally have any strong opinions on the JS/Web API or limits.

A small tweak that would enable the described optimization (if I understand it correctly) but be a little less constraining would be to limit the max pages at 2^31 - 1. This way the sign bit will never be set on the maximum so you can use signed comparisons, but larger memories are also supported.

---

FWIW, with ISAs that support negative displacements (at least all of x86, aarch64, riscv) you should be able to fold an ALU operation into the address mode and remove an instruction from the bounds-check-and-load sequence, something like

r0, r1 = add_immediate_with_overflow r_index, 4 ; size_of(i32)
br_if r1, trap_label
r2 = unsigned_gt_eq r0, r_bound
br_if r2, trap_label
r3 = i32.load r0 + r_base - 4

Of course, that arithmetic operation still needs to happen, but it should be a bit cheaper than it otherwise would be.