[foreign-memaccess] creating memory access handles

[Maurizio Cimadamore]

Hi,
Last week we had a great patch from Jorn which implements a new, more 
basic way to get at the memory access handles; the basic idea is to 
start from simple carriers (e.g. an 'int' accesor) and _combine_ them 
together. There are basically two ways in which you can combine: (i) add 
offset to the base address (useful for accessing struct elements) or 
(ii) add an extra access dimension (useful for array indexing). There's 
also an extra combinator which can be used to force a certain alignment, 
more on that later.

When a memory access VarHandle is built, it will have three important 
properties:

* the displacement
* the number of 'free variables' in it (and their 'scales' in bytes)
* the alignment (either derived from the carrier, or forced with the 
combinator method)
* carrier type (e.g. int.class)

All these info is used in order to compute a single offset which is 
applied on top of the MemoryAddress that is passed as argument to the 
VH; the formula would look something like this:

offset = c_0 + (x_1 * s_1 + c_1) + (x_2 * s_2 + c_2) + ... + (x_n * s_n 
+ c_n)

That is, it's a sum of many components, a constant one (c_0) and some 
indexed one, where x_1, x_2 ... x_n are free variables that are bound by 
the VH call.

With this formula it is easy to see that:

* VH.displacement = c_0 + c_1 + c_2 + ... + c_n
* VH.scales = { s_1, s_2 ... s_n }

This is all good. But I found myself asking: what are the conditions 
under which a VH combinator call is well-formed? Is it possible to 
construct stuff with the combinator API which doesn't make sense?

I think that is currently the case - that is, the combinator API is 
'less safe' than its LayoutPath-based cousin. While some of that is 
unavoidable (LayoutPath works on Layout, so it has more info), some of 
that is also purely accidental. I've identified two category where I 
found the combinator API too weak: array VH creation and alignment 
enforcing.

*** array indexing ***

Let's start with arrays. In general, with the combinator API, you start 
off with a simple accessor - e.g. something for:

i32

and then you build up from there - e.g. we can add some displacement:

[x64 i32]

And then we can wrap it all into an array indexing:

[5 : [x64 i32]]

And we can add even more indexing:

[10 : [5 : [x64 i32]]]

Now, each array indexing is done with this API call:

VarHandle elementHandle(VarHandle handle, long scale)

the 'scale' here is, essentially, the size of the element type of the 
array being considered.

I think this imposes a requirement on which 'scale' numbers we can use - 
that is, if 'handle' is a VH whose carrier is 4 bytes and displacement 
is 10 - then the scale we use must be greater/equal than 10 + 4. A 
failure to meet this requirement will mean that indexing the VH with an 
index > 0 will possibly still point to a location inside the array. 
While this restriction doesn't completely remove this possibility (there 
could always be 'stuff' after the 'i32' we want to access), I think it 
might be sensible to try and enforce this.

This also means that, going back to our formula, all the scales are 
'sorted' that is:

s_1 >= s_2 >= ... >= s_n

This corresponds to the principle that the first index dimensions in the 
VarHandle should correspond to the 'outermost' sequence in the layout.

So, concluding, when calling the above combinator method 
(elementHandle), we have to make sure that:

scale >= handle.displacement + sizeof(handle.carrier)

*** alignment enforcing ***

When combining together VH, we must make sure that we respect alignment 
constraints that might appear on these VH. So, if we start from a simple 
VH which access something like this:

i32

the constraint is easily resolved - after all, i32 has a natural 
alignment (4 bytes), so the VH is well-formed (this of course doesn't 
mean we're 100% safe - at runtime we should still check that the address 
passed to the VH is compatible with that alignment, but that's a 
_dynamic_ requirement, not a _static_ one).

Now, suppose we want to add some displacement:

x64 i32

Is this still good? The resulting VH will have these properties:

* displacement = 8
* scales = {}
* carrier = int.class
* alignment = 4

here we have to check that (8 + 4) % 4 = 0. It can be seen that this is 
always the case, and, in particular, the alignment constraints are 
satisfied as long as the offset we pass to the combinator is a multiple 
of the alignment constraint. That is, when we call:

VarHandle offsetHandle(VarHandle handle, long offset)

This has to hold:

offset % handle.alignment = 0

Ok, but what if I create an array VH ? How do I enforce alignment 
constraints in that case?

[ 5 : [ x64 i32 ] ]

So, things are more tricky here - and it is helpful to appeal to our 
mathematical formulation; we can model the above as:

offset = 12 * x_i + 8

and, of course we want this offset to be aligned, so:

(12 * x_i + 8) % handle.alignment = 0

Here we can note that 'x_i' is an integral constant, and we also now 
that the displacement must already be a multiple of the alignment (see 
above).

So, for this formula to hold, we need to make sure that the scale (12 
here) is a multiple of the alignment (in this case 4, so ok). In fact we 
can show that, when this is the case, the static alignment constraints 
are _always_ guaranteed:

((scale * x_i + handle.displacement) % handle.alignment) = 0

but, if scale is a multiple of handle.alignment, then we have:

((N * handle.alignment * x_i + handle.displacement) % handle.alignment) = 0

But wait, handle.displacement is also a multiple of the alignment (as 
per above):

((N * handle.alignment * x_i + (M * handle.alignment)) % 
handle.alignment) = 0

So we can factor:

(handle.alignment * ((N * x_i) + M)) % handle.alignment = 0

which is trivially true.


So, concluding, I think that we should do the following:

1) MemoryAccessVarHandles::elementHandle(handle, displacement) must 
check that displacement >= handle.displacement + sizeof(handle.carrier)

2) MemoryAccessVarHandles::offsetHandle(handle, offset) must check that: 
offset % handle.alignment == 0

3) MemoryAccessVarHandles::elementHandle(handle, scale) must check that: 
scale % handle.alignment == 0


As for MemoryAccessVarHandles::alignAccess - I see two options:

1) We remove it, and enforce alignment to be specified when you create 
the leaf VH (preferred option)
2) We keep it, but then we must re-validate existing scales/displacement 
against the new alignment constraint


Maurizio