Fix array allocation overflow check on arm/arm64/mips.

Fix array allocation overflow check on arm/arm64/mips.

When adding an object size in bytes to the allocation top address,
we must check for *unsigned* overflow, not signed overflow. 32-bit example:
if top is 0xfffff000 and size is 0x1008, then top + size is an unsigned,
but not a signed, overflow.

Add similar unit test for typed data (same issue).

BUG=23254
R=regis@google.com

Committed: https://code.google.com/p/dart/source/detail?r=45354

[koda, 2015-04-21 13:32:01]

koda@google.com changed reviewers:
+ regis@google.com

[koda, 2015-04-21 13:41:20]

Note: Whether we hit this issue depends highly on where the new space section of
the heap is located within the address space.

Being able to ask the OS for particular a placement might help improve our test
coverage for similar issues.

[zra, 2015-04-21 14:55:26]

zra@google.com changed reviewers:
+ zra@google.com

[zra, 2015-04-21 14:55:27]

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm.cc:3391: AddImmediate(instance_reg, instance_size);
Assembler::AddImmediateSetFlags(instance_reg, instance_reg, instance_size);

Why is this TODO? Can't you just b(failure, CS) like elsewhere?

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm.cc:3438: AddImmediate(end_address, instance,
instance_size);
AddImmediateSetFlags

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.cc:1377: AddImmediate(instance_reg, instance_reg,
instance_size, pp);
AddImmediateSetFlags

Why TODO?

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.cc:1422: AddImmediate(end_address, instance,
instance_size, PP);
AddImmediateSetFlags

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_m...
File runtime/vm/assembler_mips.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_m...
runtime/vm/assembler_mips.cc:875: // TODO(koda): Protect against unsigned
overflow here.
Why TODO?

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm.cc:213: __ add(R1, R0, Operand(R2));                
                                \
adds

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm64.cc:223: __ add(R1, R0, Operand(R2));              
                                  \
adds

[koda, 2015-04-21 16:08:46]

Fixed setting of flags. Thanks, Zach. This further shows that test coverage is
still lacking.

Regarding the TODOs, those theoretical overflows are currently much less likely
(since we have limits on the size of instances we allocate inline), and I wanted
to keep the CL minimal in complexity and potential performance impact, in order
to have it be cherry-picked for 1.10.

That said, I now realize that the extra overflow checks can be quite elegantly
folded into the existing ones using conditional execution on ARM/ARM64, so I'll
send out an updated version.

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm.cc:3438: AddImmediate(end_address, instance,
instance_size);
On 2015/04/21 14:55:27, zra wrote:
> AddImmediateSetFlags

Done.

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.cc:1422: AddImmediate(end_address, instance,
instance_size, PP);
On 2015/04/21 14:55:27, zra wrote:
> AddImmediateSetFlags

Done.

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm.cc:213: __ add(R1, R0, Operand(R2));                
                                \
On 2015/04/21 14:55:27, zra wrote:
> adds

Done.

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/1096063002/diff/100001/runtime/vm/intrinsifie...
runtime/vm/intrinsifier_arm64.cc:223: __ add(R1, R0, Operand(R2));              
                                  \
On 2015/04/21 14:55:27, zra wrote:
> adds

Done.

[regis, 2015-04-21 17:10:30]

lgtm

I'll have another look once you upload you next version.

Note that it may be simpler to have a single unsigned comparison:
address of new instance - heap top address < heap end address

[koda, 2015-04-21 20:47:34]

Actually, I've changed my mind back.

I think we should instead have a system-wide guarantee that heap addresses are
never closer than, say 64K, from either boundary of the address space.

We can then safely avoid emitting overflow checks for sizes/offsets that are
known at compile time to be small enough. Case in point: We currently only
inline allocation of instances with at most 12 fields. Since the inline
allocation is performance-sensitive, avoiding the overflow check is worth the
slight complexity of ensuring the invariant (which we are currently relying on,
just without actually enforcing it).

On most platforms, there are already such guarantees due to special reservations
at the top and bottom of the address space. But to be safe, we can simply waste
a few K of memory if the heap spaces ever receive such addresses from
VirtualMemory (there are very few, obvious places to check).

Thus, I will leave the TODOs for now.

Any thoughts on this?

[regis, 2015-04-22 00:54:18]

lgtm in case you want to submit as-is for now, since you fix some bugs.
A later cl doing the right check would be nice, though.

[regis, 2015-04-22 01:06:49]

On 2015/04/21 17:10:30, regis wrote:
> lgtm
> 
> I'll have another look once you upload you next version.
> 
> Note that it may be simpler to have a single unsigned comparison:
> address of new instance - heap top address < heap end address

As Daniel pointed out, I meant of course
address of new instance - heap top address < heap end address - heap top address
with heap top address before the allocation.

[koda, 2015-04-22 18:32:51]

Committed patchset #8 (id:140001) manually as r45354 (presubmit successful).