330812 - Making Array(1 << 29).sort() less problematic.

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Currently Array(1 << 29).sort() is quite effective Denial-of-Service since it not only causes browser freeze with CPU usage 100% but also triggers allocation of 2GB of memory on 32 bit platforms. That in turn lead to very heavy swapping and an unresponsive system in general unless one does have over 2GB of RAM.

This is caused by the fact that the code from array_sort in jsarray.c allocates a temporary vector for sorting with the capacity to hold array.length jsvals and clearing the vector with zeros as preparation for rooting of its elements even if the array is spare. 

With bug 311515 resolved one can avoid this heaving swapping assuming a reasonable VM implementation in OS. The idea is not to clear the whole vector before rooting it but rather set fp->nvar initially to 0 and clear elements one by one before increasing fp->nvar as necessary. In this way for a mostly spare array the code would never touch the tail of the vector corresponding to holes in the array. It allows for OS to avoid bringing the corresponding pages into memory and swapping.

Comment 1

[Igor Bukanov]

Attachment: Implementation

Comment 2

[Igor Bukanov]

Attachment: Implementation v2

The prevois patch made nbytes from array_sort unnecessary and this version removes  it.

Comment 3

[Igor Bukanov]

With the last patch applied the optimized build of js shell did finished Array(1 << 29).sort() after 10 minutes on a PC with 1GB of run with Linux kernel 2.6.15. The system was not swapping at all and was wery responsive.

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 215396 [details] [diff] [review]
Implementation v2

English nits only.

>Index: src/jsarray.c
>+     * Initialize rooting of vec.

How about 'Initialize vec as a root'.

>+        /* Clear vec[newlen] before including it to the rooted set. */

... including it *in* the rooted set ...

r=mrbkap

Comment 5

[Igor Bukanov]

Attachment: Patch to commit with nits addressed

Comment 6

[Igor Bukanov]

I committed the last patch:

Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.78; previous revision: 3.77
done

Comment 7

[Bob Clary [:bc] (inactive)]

Checking in regress-330812.js;
/cvsroot/mozilla/js/tests/js1_5/Array/regress-330812.js,v  <--  regress-330812.js
initial revision: 1.1

Comment 8

[Bob Clary [:bc] (inactive)]

verified fixed 1.9a1 win/mac/linux. Note that in 1.8.0/1.8.1 the testcase only hangs mac shell tests.

Comment 9

[Biju]

we still have some other prob. see Bug# 334935