Possible memory leak in Ap_sort

[Hanseltu]

Hi,

The following test input (input.js) causes the possible memory leaks.

$cat input.js
c = 30000;
a = [];
for (i = 0; i < 2 * c; i += 1) {
  a.push(i%c);
}
a.sort(function (x, y) { return_x -=y; });
print(a[2 * c - 2]);

$./mujs input.js
ReferenceError: 'return_x' is not defined
    at input.js:6
    at Array.prototype.sort (native)
    at input.js:6

=================================================================
==26067==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 1440000 byte(s) in 1 object(s) allocated from:
    #0 0x7ffff6ef6b40 in __interceptor_malloc (/usr/lib/x86_64-linux-gnu/libasan.so.4+0xdeb40)
    #1 0x7ffff64825af in qsort_r (/lib/x86_64-linux-gnu/libc.so.6+0x425af)
    #2 0x555555568f47 in Ap_sort /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsarray.c:313
    #3 0x5555555ad432 in jsR_callcfunction /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsrun.c:1249
    #4 0x5555555adf31 in js_call /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsrun.c:1299
    #5 0x5555555b297d in jsR_run /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsrun.c:1810
    #6 0x5555555ad18a in jsR_callscript /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsrun.c:1230
    #7 0x5555555adde6 in js_call /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsrun.c:1295
    #8 0x5555555b5455 in js_dofile /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/jsstate.c:249
    #9 0x555555567b9d in main /home/haoxin/disk-smu/research/structured-fuzz/experiments/mujs-1.3.5/main.c:363
    #10 0x7ffff6461c86 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21c86)

SUMMARY: AddressSanitizer: 1440000 byte(s) leaked in 1 allocation(s).

Compilation command: add -fsanitize=address into CFLGAS in Makefile. Compiler version: gcc-7.5.0. System: ubuntu 18.04. mujs version: 1.3.5.

Thanks.

[avih]

I don't think I see the leak at the code.

Ap_sort does make an allocation which the VM is not aware of (note: can it be a userdata object?), but it's inside try/catch, and it's freed at the catch part, and the pointer variable is appropriately volatile. So it's not immediately obvious to me why it would leak.

Which version of mujs are you testing? Can you try with current master if you were testing with an older version? (I don't have the bandwidth to look into it myself, so these are just thoughts)

[ccxvii]

The leak happens because the callback throws an exception, which longjmps out of the qsort function.

On GNU libc, qsort is implemented as a mergesort with temporary storage allocated with malloc. When the callback jumps out with an exception, libc leaks that storage.

We can replace the use of system qsort with our own implementation of an in-place sorting algorithm, such as heapsort (which is approx 2x slower than gnu libc's mergesort on a large arrays).

[avih]

libc leaks that storage.

Interesting.

Long while ago I experimented with different sorts.

I think this is a minimal implementation of mujs heap sort, and as far as I recall it was on par with glibc - not slower than x1.3 or some such, but there could be classes of input which I didn't test. (I also have similar code with other "base" sort functions, like quicksort and other types, some surprisingly tiny).

It has two siftdown functions, and I don't recall which is better/faster (I'm pretty sure both work, and I have few more which I didn't copy here, some faster than others, and other variables).

Hopefully it's complete, but I extracted it manually from an old large file with lots of experiments, so hopefully I got the right parts. Maybe it can be reused. I didn't try to compile it now:

heap sort for mujs

```c // compatible with qsort_r (linux/bsd libc) static int sortcmp_r(const void *va, const void *vb, void *ctx) { // if (va == vb || memcmp(va, vb, sizeof(js_Value)) == 0) // return 0; js_State *J = ctx; const js_Value *a = va, *b = vb; const char *sx, *sy; double v; int c; int unx = (a->type == JS_TUNDEFINED); int uny = (b->type == JS_TUNDEFINED); if (unx) return !uny; if (uny) return -1; if (js_iscallable(J, 1)) { js_copy(J, 1); /* copy function */ js_pushundefined(J); js_pushvalue(J, *a); js_pushvalue(J, *b); js_call(J, 2); v = js_tonumber(J, -1); c = (v == 0) ? 0 : (v < 0) ? -1 : 1; js_pop(J, 1); } else { js_pushvalue(J, *a); js_pushvalue(J, *b); sx = js_tostring(J, -2); sy = js_tostring(J, -1); c = strcmp(sx, sy); js_pop(J, 2); } return c; } #define JS_VSWAP(a, b) do { js_Value tmp__ = a; a = b; b = tmp__; } while (0) // parent/left-child of i in array-as-heap. i/end are [unsigned] integrals // PARENT expects i>0, LCHILD expects end>0 and evaluates to 0 if no l-child // RCHILD(i) exists and is LCHILD(i)+1 if and only if (0 < LCHILD(i) < end) #define PARENT(i) (((i) - 1) / 2) #define LCHILD(i, end) ((i) <= PARENT(end) ? (i) * 2 + 1 : 0) // expects end > 0 ("bottom-up"/bounce sift down) static void xsiftdown(js_State *J, js_Value *arr, size_t i, size_t end) { size_t j = i, lc; // seek down a leaf j at the end of a path-of-biggest-siblings from i while ((lc = LCHILD(j, end))) j = lc < end && sortcmp_r(arr+lc, arr+lc+1, J) <= 0 ? lc + 1 : lc; // right if have both and L<=R, else left // seek up to target position j while (i < j && sortcmp_r(arr+i, arr+j, J) > 0) j = PARENT(j); // rotate the branch a[i]...a[j] one level up (and a[i] to j) while (i < j) { JS_VSWAP(arr[i], arr[j]); j = PARENT(j); } } static void siftdown(js_State *J, js_Value *arr, size_t i, size_t end) { js_Value arri = arr[i]; size_t j = i, x; // move up by 1 level a path-of-biggest-siblings from i to a leaf j for ( ; (x = LCHILD(j, end)); j = x) { if (x < end && sortcmp_r(arr+x, arr+x+1, J) <= 0) ++x; // right if have both L,R and L<=R arr[j] = arr[x]; } // if needed, move back down nodes smaller than a[i] on our path for ( ; x = PARENT(j), i < j && sortcmp_r(&arri, arr+x, J) > 0; j = x) arr[j] = arr[x]; arr[j] = arri; // in the hole } static void js_heapsort(js_State *J, js_Value *arr, size_t n) { size_t i; for (i = PARENT(n - 1); i; --i) // sans sift(0, n-1) siftdown(J, arr, i, n - 1); for (i = n - 1; i; --i) { // starts with sift(0, n-1) siftdown(J, arr, 0, i); JS_VSWAP(arr[0], arr[i]); } } static void sort_r(void *arr, size_t n, size_t size, cmp_ft cmp, void *J) { // size assumed of js_Value, cmp hardcoded if (n > 1) js_heapsort(J, arr, n); } static void Ap_sort(js_State *J) { int i, n, len; len = js_getlength(J, 0); if (len < 2) goto done; n = 0; js_newarray(J); // flat array copy which we'd sort for (i = 0; i < len; ++i) if (js_hasindex(J, 0, i)) js_setindex(J, -2, n++); js_Value *v = js_tovalue(J, -1); assert (v->type == JS_TOBJECT && v->u.object->type == JS_CARRAY); if (!v->u.object->u.a.simple) js_rangeerror(J, "array is too large to sort"); js_Value *arr = v->u.object->u.a.array; sort_r(arr, n, sizeof *arr, sortcmp_r, J); for (i = 0; i < n; ++i) { js_pushvalue(J, arr[i]); js_setindex(J, 0, i); } for (i = n; i < len; ++i) { js_delindex(J, 0, i); } done: js_copy(J, 0); } ```

[ccxvii]

I found some of our old sorting experiments on various branches (including your heapsort, and an in-place quicksort implementation). I'll see if I can revive one of those to fix this issue.

[avih]

Added to the code above a missing tiny intermediate function (copied from the same old experiments file):

static void sort_r(void *arr, size_t n, size_t size, cmp_ft cmp, void *J)
{
        // size assumed of js_Value, cmp hardcoded
        if (n > 1)
                js_heapsort(J, arr, n);
}

[avih]

It has two siftdown functions, and I don't recall which is better/faster (I'm pretty sure both work

I think I remember now. The xsiftdown function is more generic and uses only swaps. and it doesn't know the size of an element (so it can't keep a copy of an element outside the array), while the siftdown function is (more?) mujs-specific, and uses js_Value to hold an element outside the array, and it can assign arrays elements directly from place to place, and therefore should be faster (and because of that, uses a very slightly different approach, which typically results in less iterations and much less assignments. both are "bottom up" sift-down).

It doesn't even need to pause the GC or use try/catch, no allocations outside of the VM, because it uses the flat array mode.