1322397 - AsmJS -> Wasm translator can generate huge switches for tiny inputs

Status: RESOLVED WONTFIX

(Core :: JavaScript: WebAssembly, defect, P3)

Description

[Lars T Hansen [:lth]]

I'm not sure how much this matters but the translator generates a switch with table size 133742 for the following switch (test case from asm.js/testControlFlow.js):

function f(i) {
 i=i|0;
 switch(i|0) { 
   case 1: i=-1; break; 
   case 133742: i=2; break; 
   default: i=42; break
 }
 return i|0
}

In principle there is a risk here for unnecessary OOM and for some DOS scenarios perhaps: fairly small inputs can turn into very large intermediate representations.

Comment 1

[Hannes Verschore [:h4writer]]

Good find. Currently marking P3. Feel free to mark it P1-P2 if we need to have this fixed this or next release.

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

Thanks for opening a bug. I think that in principle, this means we can create a large amount of wasm bytecode when converting from asmjs to wasm, but that shouldn't have an effect on the MSwitchTable created in MIR later.

I can look into reducing the wasm bytecode size when I come back from PTO, unless somebody beats me to it </hint>.

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Actually, do we have a choice here? The br_table expr is [i - low], where low is the low end of the range (= 1 in this example), and we have to enumerate all the values in [0, high - low]. So we have to enumerate all the relative depths for all values of i in [1, 133742], hence the current behavior.

Ideally, such a switch would be broken into ifs, so we can just test zero against |i - 1| and |i - 133742|. It could be an optimization for the asmjs->wasm frontend, or even in ion (if it's not done already).

Am I missing something? Maybe you saw something else that I am not seeing...

Comment 4

[Lars T Hansen [:lth]]

Well, one always has a choice :)  The question really is whether Odin should implement some switch optimization or not, in order to safeguard against performance cliffs or DOS scenarios, or if it should completely defer that to Baldr / Rabaldr.  In the latter case we're done.  In the former there are all manner of standard optimizations to consider.  If the switch is fairly dense we're done.  If not, split it into denser switches and then match the index expression against those switches' ranges (binary search, whatever - the usual calculus).  Presumably Ion already does that and Baldr might benefit from it, at the cost of Ion having to process a lot of switch cases.  Rabaldr does not benefit from it.  That is not a problem per se because the switch is degenerate and not very likely to occur in real code (hence my introductory comment "I'm not sure how much this matters") but there may still be DOS scenarios to consider.

(For "DOS" also read "not very clever front-end".)

Comment 5

[Benjamin Bouvier [:bbouvier] (inactive)]

Agreed. I'd like to see some data saying this is a problem before spending time on it. Our general assumption towards the frontend is that it is clever and does these pre-optimizations for us.

Comment 6

[Lars T Hansen [:lth]]

It's probably not much of a concern, esp since it's asm.js specific.  I see Odin has a cutoff for the switch table size at 1,000,000 which is a reasonable check on completely nutty behavior.  *Some* code, perhaps notably computer-generated code but it could be hand-written, may hit this limit, but again, this is asm.js-only.

(An obvious non-abusive hand-written asm.js case might for example use a switch to switch on a sparse set of large values that may be magic numbers or hashes or things like that.  The range could easily exceed 10e6.  This would fail the compilation.)

Comment 7

[BMO Automation]

Per policy at https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Inactive_Bugs. If this bug is not an enhancement request or a bug not present in a supported release of Firefox, then it may be reopened.

Comment 8

[Lars T Hansen [:lth]]

Let's not worry about this.