Closed Bug 1115043 Opened 5 years ago Closed 5 years ago

Odin x86: partial OOBs load/stores happening

Categories

(Core :: JavaScript Engine: JIT, defect)

x86
Linux
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla37

People

(Reporter: bbouvier, Assigned: bbouvier)

Details

Attachments

(1 file, 1 obsolete file)

While working on bug 1113338, I've gone through some code on dxr and found that we have special code for removing bounds of AsmJSLoadHeap/AsmJSStoreHeap in Range Analysis. Contrarily to the jitted bounds checks which take element size into account (as SIMD load/store can be unaligned and don't have the pointer clearing effect), range analysis doesn't.

I have a patch for that.

(to anyone in security teams being worried: SIMD in asm.js is only in Nightlies and this will happen only under x86 or x64 without signals (which is not the default))
With a test case in testSIMD.js exhibiting the problem.
Attachment #8540790 - Flags: review?(luke)
Comment on attachment 8540790 [details] [diff] [review]
Ensure that range analysis takes size of element into account when removing bounds checks of AsmJS{Load/Store}Heap

Review of attachment 8540790 [details] [diff] [review]:
-----------------------------------------------------------------

D'oh!

::: js/src/jit/RangeAnalysis.cpp
@@ +2202,5 @@
>                  uint32_t minHeapLength = mir->minAsmJSHeapLength();
>                  if (iter->isAsmJSLoadHeap()) {
>                      MAsmJSLoadHeap *ins = iter->toAsmJSLoadHeap();
>                      Range *range = ins->ptr()->range();
> +                    uint32_t elemSize = 1 << TypedArrayShift(ins->viewType());

I can count 4 other places where we compute size via (1 << shift), so perhaps we could add a TypedArrayElemSize next to TypedArrayShift and use that everywhere instead?
Attachment #8540790 - Flags: review?(luke) → review+
* Would it be correct to just add (elemSize - 1) rather than elemSize?

* The original code was taking advantage of the known pointer alignment and might it be possible to retain this logic?  E.g rather than just adding the '(elemSize - 1)', add '(elemSize - 1) & alignmentMask' where the alignmentMask would be -1 for the unaligned SIMD accesses but ~0, ~1, ~3, ~7 for aligned viewTypes?

* Could a TypedArrayAlignmentMask method be added if not already available as it will probably be needed more than once (or some other appropriately named method).

* Are there actually SIMD typed arrays, or are there just SIMD viewTypes? If the later then it might be clearer to name methods as ViewTypeAlignmentMask etc.

* Ion might have some affected paths too, see MLoadTypedArrayElementStatic::collectRangeInfoPreTrunc() and MStoreTypedArrayElementStatic::collectRangeInfoPreTrunc() although these are currently unused.

* There is some Ion bounds check hoisting code that might need scrutiny wrt this issue too when the Ion support is being added.
https://hg.mozilla.org/mozilla-central/rev/da15e3989bb9
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla37
(In reply to Douglas Crosher [:dougc] from comment #4)
> * Would it be correct to just add (elemSize - 1) rather than elemSize?
We don't want upperBound + elemSize >= minHeapLength (which is 1 position after the last in-bounds index), so by negating the previous inequality, we want upperBound + elemSize < minHeapLength, which is what's tested in this patch. Double check me if something is wrong.

> 
> * The original code was taking advantage of the known pointer alignment and
> might it be possible to retain this logic?  E.g rather than just adding the
> '(elemSize - 1)', add '(elemSize - 1) & alignmentMask' where the
> alignmentMask would be -1 for the unaligned SIMD accesses but ~0, ~1, ~3, ~7
> for aligned viewTypes?
I guess this depends on the consumers of the asm.js API for SIMD, i.e. emscripten et al. In this case, Dan should chime in, but I think the idea is that most accesses are unaligned. At some point, Dan wanted to add an API for aligned accesses (which would be fast if the array + index are really aligned, and awfully slow otherwise, but that would be part of the API).

> 
> * Could a TypedArrayAlignmentMask method be added if not already available
> as it will probably be needed more than once (or some other appropriately
> named method).
Why not, I don't have a strong opinion here. If you feel so, feel free to open a follow up.

> 
> * Are there actually SIMD typed arrays, or are there just SIMD viewTypes? If
> the later then it might be clearer to name methods as ViewTypeAlignmentMask
> etc.
There will probably be SIMD typed arrays in the future, see specification at https://github.com/johnmccutchan/ecmascript_simd

> 
> * Ion might have some affected paths too, see
> MLoadTypedArrayElementStatic::collectRangeInfoPreTrunc() and
> MStoreTypedArrayElementStatic::collectRangeInfoPreTrunc() although these are
> currently unused.
> 
> * There is some Ion bounds check hoisting code that might need scrutiny wrt
> this issue too when the Ion support is being added.
Indeed, and now that I'm aware of such an issue, I'll make my best to take care of it and avoid these issues in the Ion SIMD implementation.
(In reply to Benjamin Bouvier [:bbouvier] from comment #6)
> (In reply to Douglas Crosher [:dougc] from comment #4)
> > * Would it be correct to just add (elemSize - 1) rather than elemSize?
> We don't want upperBound + elemSize >= minHeapLength (which is 1 position
> after the last in-bounds index), so by negating the previous inequality, we
> want upperBound + elemSize < minHeapLength, which is what's tested in this
> patch. Double check me if something is wrong.

Perhaps I've missed something. An example might help:
 Let: minHeapLength = 4096
      upperBound = 4095
      elemSize = 1
 Then: 4095 + 1 < 4096  is false, but this is within bounds.

whereas adding (elemSize - 1):
 4095 + 0 < 4096  is true.

> > * The original code was taking advantage of the known pointer alignment and
> > might it be possible to retain this logic?  E.g rather than just adding the
> > '(elemSize - 1)', add '(elemSize - 1) & alignmentMask' where the
> > alignmentMask would be -1 for the unaligned SIMD accesses but ~0, ~1, ~3, ~7
> > for aligned viewTypes?
> I guess this depends on the consumers of the asm.js API for SIMD, i.e.
> emscripten et al. In this case, Dan should chime in, but I think the idea is
> that most accesses are unaligned. At some point, Dan wanted to add an API
> for aligned accesses (which would be fast if the array + index are really
> aligned, and awfully slow otherwise, but that would be part of the API).

I thought fast accesses would need to be aligned for the benefit of the ARM. This might be done by recognising a pattern with an explicit index mask rather than adding a new API, e.g. load(u8, i & ~0xf). This is in part what I hope bug 870743 can help with,
(In reply to Douglas Crosher [:dougc] from comment #7)
> (In reply to Benjamin Bouvier [:bbouvier] from comment #6)
> > (In reply to Douglas Crosher [:dougc] from comment #4)
> > > * Would it be correct to just add (elemSize - 1) rather than elemSize?
> > We don't want upperBound + elemSize >= minHeapLength (which is 1 position
> > after the last in-bounds index), so by negating the previous inequality, we
> > want upperBound + elemSize < minHeapLength, which is what's tested in this
> > patch. Double check me if something is wrong.
> 
> Perhaps I've missed something. An example might help:
>  Let: minHeapLength = 4096
>       upperBound = 4095
>       elemSize = 1
>  Then: 4095 + 1 < 4096  is false, but this is within bounds.
> 
> whereas adding (elemSize - 1):
>  4095 + 0 < 4096  is true.

Yes, classic off-by-one mistake. I'll put up a patch for this. Thanks for providing an example. In my previous comment, what we don't want is upperBound + elemSize >= minHeapLength (note the >= instead of >), hence the off by one.

> 
> > > * The original code was taking advantage of the known pointer alignment and
> > > might it be possible to retain this logic?  E.g rather than just adding the
> > > '(elemSize - 1)', add '(elemSize - 1) & alignmentMask' where the
> > > alignmentMask would be -1 for the unaligned SIMD accesses but ~0, ~1, ~3, ~7
> > > for aligned viewTypes?
> > I guess this depends on the consumers of the asm.js API for SIMD, i.e.
> > emscripten et al. In this case, Dan should chime in, but I think the idea is
> > that most accesses are unaligned. At some point, Dan wanted to add an API
> > for aligned accesses (which would be fast if the array + index are really
> > aligned, and awfully slow otherwise, but that would be part of the API).
> 
> I thought fast accesses would need to be aligned for the benefit of the ARM.
> This might be done by recognising a pattern with an explicit index mask
> rather than adding a new API, e.g. load(u8, i & ~0xf). This is in part what
> I hope bug 870743 can help with,

Regular JS (not asm.js) also wants fast aligned accesses. We expect JS SIMD code to be hand-written, and developers might not know about the masking pattern, so providing a new API makes sense.
See previous comments..
Attachment #8543996 - Flags: review?(luke)
Attachment #8540790 - Attachment is obsolete: true
Attachment #8543996 - Flags: review?(luke) → review+
You need to log in before you can comment on or make changes to this bug.