array overflow

[xeioex]

> var z = new Array(0x08000000)
undefined
> z.concat(z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z)
Segmentation fault

[hongzhidao]

@xeioex

The problem is the max size of nxt_array_t and njs_array_t is not equal.
But in JS the max length is 2^32 - 1.
The length property of an object which is an instance of type Array sets or returns the number of elements in that array. The value is an unsigned, 32-bit integer that is always numerically greater than the highest index in the array.

typedef struct {
    void              *start;
    /*
     * A array can hold no more than 65536 items.
     * The item size is no more than 64K.
     */
    uint16_t          items;
    uint16_t          avalaible;
    uint16_t          item_size;

    uint8_t           pointer;
    uint8_t           separate;
} nxt_array_t;

struct njs_array_s {
    njs_object_t                      object;
    uint32_t                          size;          
    uint32_t                          length;     
    njs_value_t                       *start;
    njs_value_t                       *data;
};

[drsm]

@xeioex

> var z = new Array(0x08000000)
undefined
> z.concat(z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z)
Segmentation fault

the strange thing is that the proper implementation should skip arrays containing empty items after the resulting length reaches 2^32 - 1 up to 2^53 -1:

$ node --use-strict
> var z = new Array(0x08000000)
undefined
> var y = z.concat(z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z.slice(0, -2), 1)
undefined
> y
[ <4294967294 empty items>, 1 ]
> 2**32 - 1
4294967295
> y.concat(z)
[ <4294967294 empty items>, 1 ]
> y.concat(1)
RangeError: Invalid array length
    at Array.concat (<anonymous>)
>

[drsm]

some updates

the strange thing is that the proper implementation should skip arrays containing empty items after the resulting length reaches 2^32 - 1 up to 2^53 -1:

there is a bug in V8, so, it just enough to throw exception on 32 bit overflow:

root@node:~# eshost -h v8,jsc,sm -s -x 'var z = Array(0x08000000); var x = z.concat(z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z,z); print(x.length)'
#### jsc

RangeError: Length exceeded the maximum array length

#### sm

RangeError: invalid array length

#### v8
4294967295

here is the patch:

# HG changeset patch
# User Artem S. Povalyukhin <artem.povaluhin@gmail.com>
# Date 1555356746 -10800
#      Mon Apr 15 22:32:26 2019 +0300
# Node ID 2f0f794f04b267ff048924703c0aa2aa8f8bfd0c
# Parent  381086beb15f6dd82b0d76d7556ced8fb16fd732
Fixed overflow in Array.prototype.concat().

diff -r 381086beb15f -r 2f0f794f04b2 njs/njs_array.c
--- a/njs/njs_array.c	Mon Apr 15 17:23:02 2019 +0300
+++ b/njs/njs_array.c	Mon Apr 15 22:32:26 2019 +0300
@@ -1115,7 +1115,7 @@
 njs_array_prototype_concat(njs_vm_t *vm, njs_value_t *args, nxt_uint_t nargs,
     njs_index_t unused)
 {
-    size_t       length;
+    uint64_t     length;
     nxt_uint_t   i;
     njs_value_t  *value;
     njs_array_t  *array;
@@ -1131,6 +1131,11 @@
         }
     }
 
+    if (length > UINT32_MAX) {
+        njs_range_error(vm, "Invalid array length");
+        return NXT_ERROR;
+    }
+
     array = njs_array_alloc(vm, length, NJS_ARRAY_SPARE);
     if (nxt_slow_path(array == NULL)) {
         return NXT_ERROR;
diff -r 381086beb15f -r 2f0f794f04b2 njs/test/njs_unit_test.c
--- a/njs/test/njs_unit_test.c	Mon Apr 15 17:23:02 2019 +0300
+++ b/njs/test/njs_unit_test.c	Mon Apr 15 22:32:26 2019 +0300
@@ -3565,6 +3565,10 @@
     { nxt_string("var a = [1,2,3]; a.concat(4, [5, 6, 7], 8)"),
       nxt_string("1,2,3,4,5,6,7,8") },
 
+    { nxt_string("var x = Array(2**27), y = Array(2**5).fill(x);"
+                 "Array.prototype.concat.apply(y[0], y.slice(1));"),
+      nxt_string("RangeError: Invalid array length") },
+
     { nxt_string("var a = []; a[100] = a.length; a[100] +' '+ a.length"),
       nxt_string("0 101") },
 

[lexborisov]

@drsm

Artem, thank you for the patch, but the problem is a bit different.
Please, try this patch.

[drsm]

@lexborisov
The patch works fine for me, thanks!

BTW, I was thinking about placing the check inside the loop, but for "performance" reasons didn't do it ).

[lexborisov]

@drsm

In the final patch unnecessary check removed.