364836 - Assert fail in JS_ArenaRealloc (alignment issues)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Gavin Reaney]

I've encountered the following assert fail in JS_ArenaRealloc when using picsel's embedding of spidermonkey:

    JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);

The scenario that leads to the failure depends on a couple of factors:

- the alignment requirement of the arena pool
- the target alignment of the addresses returned from malloc

In the failing case, the arena has 8 byte alignment but malloc has returned an address that is 4 byte aligned (but not on an 8 byte boundary). I don't think this particular scenario can arise with firefox/mozilla because windows/wince/linux implementations of malloc always return 8 byte aligned addresses.

In order to reproduce the bug on windows/wince/linux we need to use a pool with an alignment of 16 (any value greater than the malloc target alignment will do).

Stack trace and code to reproduce the problem will follow shortly.

Comment 1

[Gavin Reaney]

Attachment: JS_ArenaRealloc assert fail (for windows/linux js shell)

Here's some example code that initialises a few arenas and reallocs them in such a way as to show the problem.

I've created three arenas to make the problem more likely to happen (it only happens when realloc returns an address that isn't a multiple of 16 for this example).

Comment 2

[Gavin Reaney]

Attachment: Stack trace and some debug

Stack trace for assert fail.

The fix for this particular issue seems relatively easy. The relevant part of JS_ArenaRealloc is here:

    a->base = ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
    a->limit = (jsuword)a + gross;
    a->avail = JS_ARENA_ALIGN(pool, a->base + aoff);

The issue is that when we align 'a->base + aoff' this can take it beyond a->limit. To prevent this from happening we must add some alignment slop onto gross.

Apart from this, a couple of related issues are:

1) we should perhaps modify jsopcode to grow the arena exponentially since many reallocs are bad for performance. Or modify JS_ArenaRealloc to do this instead.

2) for the given stack trace, the header has 8 bytes of unused space (prior to the back pointer) that appear not to be necessary (the alignment requirements would still be met without this padding). I'll consider whether there is another/simpler way to derive the correct offset for a->base.

Comment 3

[Gavin Reaney]

Attachment: Fix for assert fail

Proposed fix. Brendan, feel free to deflect the reviewing duties elsewhere. I'll probably not be around until next Wednesday or so.

I'll consider some simplifications to the arena header calculations later, but just in case it's of interest, the basic idea I had in mind was to calculate the (overallocation) header size as follows:

hdrsz   = sizeof(JSArena) + sizeof(JSArena**) + HEADER_BASE_MASK(pool);
a->base = ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);

This feels more intuitive to me and I think it works (when the assert fix is also applied), but I may have missed something.

Comment 4

[Gavin Reaney]

This is most likely a dup of bug 239721 (the fix here is still required though).

The suggestions for changes to header padding in comment 3 are equivalent to attachment 149872 [details] [diff] [review] from bug 239721.

Comment 5

[Brendan Eich [:brendan]]

Thanks, I should have kept working on that bug, it was mouldering on my list. Marking it blocked by this bug -- we can DUP it if appropriate, or just verify it as FIXED when this is fixed.

/be

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #2)
> Apart from this, a couple of related issues are:
> 
> 1) we should perhaps modify jsopcode to grow the arena exponentially since many
> reallocs are bad for performance. Or modify JS_ArenaRealloc to do this instead.

Could you file a separate bug on this?  It hasn't been reported as a problem, but it's an O(n^2) hazard and we tend to get burned by those at the worst times, after years of getting by on luck.  Note that only expressions require the sprint stack, so unless you make very large expressions and decompile them, you'll tend not to use more than a buffer or two.

> 2) for the given stack trace, the header has 8 bytes of unused space (prior to
> the back pointer) that appear not to be necessary (the alignment requirements
> would still be met without this padding). I'll consider whether there is
> another/simpler way to derive the correct offset for a->base.

This was what I remember trying to finesse when I last looked at bug 239721, but we can fix it in a separate bug too, if you are willing to file one.  Thanks,

/be

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #4)
> This is most likely a dup of bug 239721 (the fix here is still required
> though).
> 
> The suggestions for changes to header padding in comment 3 are equivalent to
> attachment 149872 [details] [diff] [review] from bug 239721.

Or, if you are game, feel free to merge that patch into the one for this bug.

/be

Comment 8

[Gavin Reaney]

Attachment: Fix for assert fail and header padding

Merged the patches as suggested and retested. I'll file a new bug for the sprint stack issue soon.

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 250067 [details] [diff] [review]
Fix for assert fail and header padding

r=me, thanks.

/be

Comment 10

[Brendan Eich [:brendan]]

Fixed on trunk:

Checking in jsarena.c;
/cvsroot/mozilla/js/src/jsarena.c,v  <--  jsarena.c
new revision: 3.32; previous revision: 3.31
done

Checking branch applicability of patch....

/be

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 250067 [details] [diff] [review]
Fix for assert fail and header padding

Applies (with hunk skew for 1.8.0) to both 1.8* branches without problems.

/be

Comment 12

[Daniel Veditz [:dveditz]]

Comment on attachment 250067 [details] [diff] [review]
Fix for assert fail and header padding

approved for 1.8/1.8.0 branches, a=dveditz for drivers

Comment 13

[Brendan Eich [:brendan]]

Fixed on the branches:

1.8:   new revision: 3.28.8.4; previous revision: 3.28.8.3
1.8.0: new revision: 3.28.16.3; previous revision: 3.28.16.2

/be

Comment 14

[Tony Chung [:tchung]]

Please add testcases to this bug so QA can verify the bug.  Thanks.

Comment 15

[Brendan Eich [:brendan]]

(In reply to comment #14)
> Please add testcases to this bug so QA can verify the bug.  Thanks.

The first attachment is a patch to the js shell, but you have to apply it, rebuild the shell using js/src/Makefile.ref, and run it.  This test requires C coding, it can't be written using just JS or other web content.

/be