648769 - Fix off-by-one error in Containers.cpp:BitSet::grow()

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alon Zakai (:azakai)]

Attachment: compiled FreeType

Running the attached .js file on latest tracemonkey, with |-m -j -p| will segfault. Works with all other combinations of flags.

This is a regression within the last several weeks. I will try to bisect.

Crash happens when compiled with --enable-optimize --disable-debug. All other combinations work.

Stack trace:

Program received signal SIGSEGV, Segmentation fault.
0x002e78f6 in ?? () from /lib/libc.so.6
(gdb) where
#0  0x002e78f6 in ?? () from /lib/libc.so.6
#1  0x002eae5d in free () from /lib/libc.so.6
#2  0x081aa669 in js_free (this=0x40007d8, p=0x3d43c0) at jsutil.h:252
#3  free_ (this=0x40007d8, p=0x3d43c0) at jsutil.h:491
#4  nanojit::Allocator::freeChunk (this=0x40007d8, p=0x3d43c0) at jstracer.cpp:214
#5  0x081f282e in nanojit::Allocator::reset (this=0x7d8) at ./nanojit/Allocator.cpp:62
#6  0x081b0a7e in js::TraceRecorder::~TraceRecorder (this=0xac2bbb8, __in_chrg=<value optimized out>) at jstracer.cpp:2453
#7  0x081b4c1b in delete_<js::TraceRecorder> (this=0xac2bbb8) at jscntxt.h:2059
#8  js::TraceRecorder::finishSuccessfully (this=0xac2bbb8) at jstracer.cpp:2485
#9  0x081db315 in js::TraceRecorder::closeLoop (this=0xac2bbb8) at jstracer.cpp:4991
#10 0x081e27d3 in checkTraceEnd (this=0xac2bbb8) at jstracer.cpp:5463
#11 js::TraceRecorder::ifop (this=0xac2bbb8) at jstracer.cpp:8741
#12 0x081ea194 in record_JSOP_IFNE (this=0xac2bbb8, op=JSOP_IFNE) at jstracer.cpp:10563
#13 js::TraceRecorder::monitorRecording (this=0xac2bbb8, op=JSOP_IFNE) at jsopcode.tbl:123
#14 0x08298ce3 in js::Interpret (cx=0x835c7e0, entryFrame=<value optimized out>, inlineCallCount=0, interpMode=JSINTERP_RECORD) at jsinterp.cpp:2741
#15 0x081e0613 in js::RecordTracePoint (cx=0x835c7e0, tm=0x835cdac, inlineCallCount=@0xbfffe258, blacklist=0xbfffe25f, execAllowed=true)
    at jstracer.cpp:16817
#16 0x081e0c8c in js::MonitorTracePoint (cx=0x835c7e0, inlineCallCount=@0xbfffe258, blacklist=0xbfffe25f, traceData=0xac2a9e8, traceEpoch=0xac2a9ec, 
    loopCounter=0xac2a9f0, hits=1) at jstracer.cpp:17004
#17 0x0826e709 in RunTracer (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:979
#18 0x0826f30f in js::mjit::stubs::InvokeTracer (f=..., ic=0x40007d8) at ./methodjit/InvokeHelpers.cpp:1070
#19 0x00522855 in ?? ()
#20 0x082064f5 in EnterMethodJIT (cx=0xffff0001, safePoint=0x513756) at ./methodjit/MethodJIT.cpp:683
#21 CheckStackAndEnterMethodJIT (cx=0xffff0001, safePoint=0x513756) at ./methodjit/MethodJIT.cpp:712
#22 js::mjit::JaegerShotAtSafePoint (cx=0xffff0001, safePoint=0x513756) at ./methodjit/MethodJIT.cpp:739
#23 0x0829d7fb in js::Interpret (cx=0x835c7e0, entryFrame=<value optimized out>, inlineCallCount=0, interpMode=JSINTERP_NORMAL) at jsinterp.cpp:6408
#24 0x0826dc20 in UncachedInlineCall (f=..., argc=3, ucr=0xbfffe720) at ./methodjit/InvokeHelpers.cpp:393
#25 js::mjit::stubs::UncachedCallHelper (f=..., argc=3, ucr=0xbfffe720) at ./methodjit/InvokeHelpers.cpp:464
#26 0x0825440b in update (f=..., ic=<value optimized out>) at ./methodjit/MonoIC.cpp:958
#27 js::mjit::ic::Call (f=..., ic=<value optimized out>) at ./methodjit/MonoIC.cpp:1012
#28 0x004e78d4 in ?? ()
#29 0x082064f5 in EnterMethodJIT (cx=0xb604efa0, safePoint=0x4ceacc) at ./methodjit/MethodJIT.cpp:683
#30 CheckStackAndEnterMethodJIT (cx=0xb604efa0, safePoint=0x4ceacc) at ./methodjit/MethodJIT.cpp:712
#31 js::mjit::JaegerShotAtSafePoint (cx=0xb604efa0, safePoint=0x4ceacc) at ./methodjit/MethodJIT.cpp:739
#32 0x0829d7fb in js::Interpret (cx=0x835c7e0, entryFrame=<value optimized out>, inlineCallCount=2, interpMode=JSINTERP_NORMAL) at jsinterp.cpp:6408
#33 0x0826dc20 in UncachedInlineCall (f=..., argc=6, ucr=0xbfffebe0) at ./methodjit/InvokeHelpers.cpp:393
#34 js::mjit::stubs::UncachedCallHelper (f=..., argc=6, ucr=0xbfffebe0) at ./methodjit/InvokeHelpers.cpp:464
#35 0x0825440b in update (f=..., ic=<value optimized out>) at ./methodjit/MonoIC.cpp:958
---Type <return> to continue, or q <return> to quit---
#36 js::mjit::ic::Call (f=..., ic=<value optimized out>) at ./methodjit/MonoIC.cpp:1012
#37 0x0045ae51 in ?? ()
#38 0x082064f5 in EnterMethodJIT (cx=0xb7863050, safePoint=0x44cb8f) at ./methodjit/MethodJIT.cpp:683
#39 CheckStackAndEnterMethodJIT (cx=0xb7863050, safePoint=0x44cb8f) at ./methodjit/MethodJIT.cpp:712
#40 js::mjit::JaegerShotAtSafePoint (cx=0xb7863050, safePoint=0x44cb8f) at ./methodjit/MethodJIT.cpp:739
#41 0x0826eb2b in EvaluateExcessFrame (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:839
#42 FinishExcessFrames (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:859
#43 RunTracer (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:1035
#44 0x0826f30f in js::mjit::stubs::InvokeTracer (f=..., ic=0x40007d8) at ./methodjit/InvokeHelpers.cpp:1070
#45 0x00433475 in ?? ()
#46 0x082064f5 in EnterMethodJIT (cx=0x42, safePoint=0x42808a) at ./methodjit/MethodJIT.cpp:683
#47 CheckStackAndEnterMethodJIT (cx=0x42, safePoint=0x42808a) at ./methodjit/MethodJIT.cpp:712
#48 js::mjit::JaegerShotAtSafePoint (cx=0x42, safePoint=0x42808a) at ./methodjit/MethodJIT.cpp:739
#49 0x0829d7fb in js::Interpret (cx=0x835c7e0, entryFrame=<value optimized out>, inlineCallCount=3, interpMode=JSINTERP_NORMAL) at jsinterp.cpp:6408
#50 0x080cd3e1 in js::RunScript (cx=0x835c7e0, script=0xc74ae78, fp=0xb79e8030) at jsinterp.cpp:636
#51 0x080cea3d in js::Execute (cx=0x835c7e0, chain=0xb7802028, script=0xc74ae78, prev=0x0, flags=0, result=0x0) at jsinterp.cpp:996
#52 0x0805bbf1 in JS_ExecuteScript (cx=0x835c7e0, obj=0xb7802028, scriptObj=0xb7802640, rval=0x0) at jsapi.cpp:4996
#53 0x0804edc8 in Process (cx=0x835c7e0, obj=<value optimized out>, filename=0xbffff600 "src.cpp.o.js", forceTTY=0) at js.cpp:456
#54 0x0804f7f8 in ProcessArgs (cx=0x835c7e0, argc=9, argv=0xbffff448, envp=0xbffff448) at js.cpp:964
#55 Shell (cx=0x835c7e0, argc=9, argv=0xbffff448, envp=0xbffff448) at js.cpp:5819
#56 0x0804fa08 in main (argc=10, argv=0xbffff444, envp=0xbffff470) at js.cpp:5941

Comment 1

[Alon Zakai (:azakai)]

Possibly this is the root cause of bug 643805 in TI. There is some partial work in that bug to get a reduced testcase.

Comment 2

[Alon Zakai (:azakai)]

Bisecting on tracemonkey, I get that the regression begins at

http://hg.mozilla.org/tracemonkey/rev/3d0784802ce6

which is a merge, so I am not sure how useful this is. Is there a way to get better information?

Comment 3

[David Mandelin [:dmandelin]]

(In reply to comment #2)
> Bisecting on tracemonkey, I get that the regression begins at
> 
> http://hg.mozilla.org/tracemonkey/rev/3d0784802ce6
> 
> which is a merge, so I am not sure how useful this is. Is there a way to get
> better information?

Are you saying that the bug is not present in both parents of the merge?

Comment 4

[Alon Zakai (:azakai)]

Ok, after some offline discussion and additional bisecting, the problem occurs for the first time at

http://hg.mozilla.org/tracemonkey/rev/1c3246c67c63

Comment 5

[Nicholas Nethercote [inactive]]

(In reply to comment #4)
> Ok, after some offline discussion and additional bisecting, the problem occurs
> for the first time at
> 
> http://hg.mozilla.org/tracemonkey/rev/1c3246c67c63

That smelled funny to me -- that was a change in the JS scanner, which runs the same no matter which combination of -j/-m/-p is given.

I tried with Valgrind and we're getting a heap of warnings, starting during a GC:

==27787== Warning: set address range perms: large range [0x38cb0028, 0x51cb0028) (defined)
==27787== Conditional jump or move depends on uninitialised value(s)
==27787==    at 0x80C6867: js::MarkIfGCThingWord(JSTracer*, unsigned int, unsigned int&) (in /home/njn/moz/ws3/js/src/opt32/shell/js)
==27787== 
==27787== Conditional jump or move depends on uninitialised value(s)
==27787==    at 0x80C688E: js::MarkIfGCThingWord(JSTracer*, unsigned int, unsigned int&) (in /home/njn/moz/ws3/js/src/opt32/shell/js)
==27787== 
==27787== Use of uninitialised value of size 4
==27787==    at 0x80C68AE: js::MarkIfGCThingWord(JSTracer*, unsigned int, unsigned int&) (in /home/njn/moz/ws3/js/src/opt32/shell/js)
==27787== 
==27787== Conditional jump or move depends on uninitialised value(s)
==27787==    at 0x80C68C1: js::MarkIfGCThingWord(JSTracer*, unsigned int, unsigned int&) (in /home/njn/moz/ws3/js/src/opt32/shell/js)
==27787== 
[heaps more like this]

(Note that the first one about address range perms isn't a problem per se, it's just saying that a very large chunk of memory got mapped in.)

Looks like some memory corruption is happening.  I think your bisection result above is unreliable because this crash is non-deterministic.

I did a bisection based on the Valgrind results:

The first bad revision is:
changeset:   61610:84c8b33619e0
user:        Vladimir Vukicevic <[e-mail]>
date:        Tue Feb 01 15:08:57 2011 -0800
summary:     b=630117, rename typed array slice() -> subset(); r=jwalden, a=block

That's weird, because that change looked like it just renamed some stuff.  But I retested before and after numerous times and it was consistent.  For an opt32 build, that is... with a debug32 build I haven't managed to get the Valgrind errors for any build.

Comment 6

[Nicholas Nethercote [inactive]]

If someone else could try to replicate my bisection with Valgrind, that would be helpful.

Comment 7

[Alon Zakai (:azakai)]

> For an opt32 build, that is... with a debug32 build
> I haven't managed to get the Valgrind
> errors for any build.

I can only reproduce the crash in opt builds, not debug ones.

Comment 8

[Jan de Mooij [:jandem]]

I can't reproduce a crash with the attached file, output is also correct. 32-bit TM (tip) opt build, -m -j -p, OS X.

Comment 9

[Alon Zakai (:azakai)]

(In reply to comment #6)
> If someone else could try to replicate my bisection with Valgrind, that would
> be helpful.

I actually get the crash on that revision and its parent (I didn't try valgrind yet).

This led me into some more bisection, and so far I see the crash as early as

http://hg.mozilla.org/tracemonkey/rev/a5d0ccdb9985

Comment 10

[Alon Zakai (:azakai)]

Finished this bisection at

http://hg.mozilla.org/tracemonkey/rev/5d3b8f835242

which actually changes the files that appear in the stack trace.

Here is a stack trace in that revision:

Program received signal SIGSEGV, Segmentation fault.
0xb7d87917 in _int_free (av=<value optimized out>, p=0x8fad688) at malloc.c:4952
4952	malloc.c: No such file or directory.
	in malloc.c
(gdb) where
#0  0xb7d87917 in _int_free (av=<value optimized out>, p=0x8fad688) at malloc.c:4952
#1  0xb7d8aecd in *__GI___libc_free (mem=0x8fad690) at malloc.c:3738
#2  0x0819c9b6 in js_free (this=0xb7616008, p=0xb7e723c0) at jsutil.h:221
#3  nanojit::Allocator::freeChunk (this=0xb7616008, p=0xb7e723c0) at jstracer.cpp:157
#4  0x081e4f5e in nanojit::Allocator::reset (this=0xb7616008) at ./nanojit/Allocator.cpp:62
#5  0x081a347e in ~TraceRecorder (this=0x9bf72d0, __in_chrg=<value optimized out>) at jstracer.cpp:2413
#6  0x081a713e in js::TraceRecorder::finishSuccessfully (this=0x9bf72d0) at jstracer.cpp:2445
#7  0x081c8671 in js::TraceRecorder::closeLoop (this=0x9bf72d0) at jstracer.cpp:4981
#8  0x081cf523 in js::TraceRecorder::checkTraceEnd (this=0x9bf72d0) at jstracer.cpp:5450
#9  js::TraceRecorder::ifop (this=0x9bf72d0) at jstracer.cpp:8647
#10 0x081dbefd in js::TraceRecorder::record_JSOP_IFNE (this=0x9bf72d0, op=JSOP_IFNE) at jstracer.cpp:10533
#11 js::TraceRecorder::monitorRecording (this=0x9bf72d0, op=JSOP_IFNE) at jsopcode.tbl:123
#12 0x0828926b in js::Interpret (cx=0x833b0e0, entryFrame=0xb76de708, inlineCallCount=0, interpMode=JSINTERP_RECORD) at jsinterp.cpp:2714
#13 0x081d9578 in js::RecordTracePoint (cx=0x833b0e0, inlineCallCount=@0xbfffeb88, blacklist=0xbfffeb8f, execAllowed=true)
    at jstracer.cpp:16503
#14 0x081d9b65 in js::MonitorTracePoint (cx=0x833b0e0, inlineCallCount=@0xbfffeb88, blacklist=0xbfffeb8f, traceData=0x9bf6100, 
    traceEpoch=0x9bf6104, loopCounter=0x9bf6108, hits=1) at jstracer.cpp:16675
#15 0x0825e7eb in RunTracer (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:1015
#16 0x0825f51f in js::mjit::stubs::InvokeTracer (f=..., ic=0x40007d8) at ./methodjit/InvokeHelpers.cpp:1106
#17 0xb70e0855 in ?? ()
#18 0x081f7761 in EnterMethodJIT (cx=0xffff0001) at ./methodjit/MethodJIT.cpp:748
#19 CheckStackAndEnterMethodJIT (cx=0xffff0001) at ./methodjit/MethodJIT.cpp:774
#20 js::mjit::JaegerShot (cx=0xffff0001) at ./methodjit/MethodJIT.cpp:791
#21 0x082890e9 in js::Interpret (cx=0x833b0e0, entryFrame=0xb76d9160, inlineCallCount=1, interpMode=JSINTERP_RECORD) at jsinterp.cpp:4766
#22 0x081d9578 in js::RecordTracePoint (cx=0x833b0e0, inlineCallCount=@0xbffff0d8, blacklist=0xbffff0df, execAllowed=true)
    at jstracer.cpp:16503
#23 0x081d9b65 in js::MonitorTracePoint (cx=0x833b0e0, inlineCallCount=@0xbffff0d8, blacklist=0xbffff0df, traceData=0x8896580, 
    traceEpoch=0x8896584, loopCounter=0x8896588, hits=1) at jstracer.cpp:16675
#24 0x0825e7eb in RunTracer (f=..., ic=...) at ./methodjit/InvokeHelpers.cpp:1015
#25 0x0825f51f in js::mjit::stubs::InvokeTracer (f=..., ic=0x40007d8) at ./methodjit/InvokeHelpers.cpp:1106
#26 0xb7257475 in ?? ()
#27 0x081f7761 in EnterMethodJIT (cx=0x42) at ./methodjit/MethodJIT.cpp:748
#28 CheckStackAndEnterMethodJIT (cx=0x42) at ./methodjit/MethodJIT.cpp:774
#29 js::mjit::JaegerShot (cx=0x42) at ./methodjit/MethodJIT.cpp:791
#30 0x080cb238 in RunScript (cx=0x833b0e0, chain=0xb7502028, script=0xce4c528, prev=0x0, flags=<value optimized out>, result=0x0)
    at jsinterp.cpp:654
#31 js::Execute (cx=0x833b0e0, chain=0xb7502028, script=0xce4c528, prev=0x0, flags=<value optimized out>, result=0x0) at jsinterp.cpp:1023
#32 0x0805a60e in JS_ExecuteScript (cx=0x833b0e0, obj=0xb7502028, script=0xce4c528, rval=0x0) at jsapi.cpp:4883
#33 0x0804f141 in Process (cx=0x833b0e0, obj=<value optimized out>, filename=0x80500ba "\203\304\020\213\203\364h", forceTTY=0)
    at js.cpp:453
---Type <return> to continue, or q <return> to quit---
#34 0x080500ba in ProcessArgs (cx=0x833b0e0, argc=4, argv=0xbffff4a8, envp=0xbffff4a8) at js.cpp:951
#35 Shell (cx=0x833b0e0, argc=4, argv=0xbffff4a8, envp=0xbffff4a8) at js.cpp:5444
#36 0x080502d1 in main (argc=5, argv=0xbffff4a4, envp=0xbffff4bc) at js.cpp:5552
(gdb)

Comment 11

[David Mandelin [:dmandelin]]

Marking sg:critical due to unsafe writes to memory.

Comment 12

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Attachment: patch

This fixes it for me.

The problem was just confusion about the meaning of the parameter to BitSet::grow. For the callers, the parameter means "make the bitset big enough to accommodate this bit". But grow thinks the parameter means "grow to at least this many bits", which is one fewer than what's needed.

Comment 13

[Alon Zakai (:azakai)]

Attachment: valgrind output

Definitely looks like a memory corruption.

1. The crash occurs in free(), in a correct call (it matches a previous call to malloc()).

2. This changeset crashes when run normally. It doesn't crash in valgrind (valgrind -v --smc-check=all COMMAND), but this changeset introduces a few new valgrind errors which look suspicious (none of those errors appear in the previous changeset). Attached is valgrind output.

Comment 14

[Alon Zakai (:azakai)]

Ah, my last comment may already be unneeded :) ...

Comment 15

[Nicholas Nethercote [inactive]]

Comment on attachment 526331 [details] [diff] [review]
patch

Nice work, azakai and billm.

billm, this will have to land on nanojit-central and then get merged to TM.  https://developer.mozilla.org/en/NanojitMerge has instructions for this (which I recently updated!) if you want to do it, or I can do it for you on Monday.

Comment 16

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

(In reply to comment #15)
> billm, this will have to land on nanojit-central and then get merged to TM. 
> https://developer.mozilla.org/en/NanojitMerge has instructions for this (which
> I recently updated!) if you want to do it, or I can do it for you on Monday.

I'd really appreciate it if you could do this. It sounds complicated and scary.

Comment 17

[Alon Zakai (:azakai)]

Attachment: compiled openjpeg

I found another case where the same bug happens, the attachment is openjpeg. Same stack trace (when run with |js -m -j -p tmp/src.c.o.js -i image.j2k -o image.raw|), and it is fixed by the patch as well.

Not sure if this is useful or not at this point. But this is much smaller than the previous case, so if we want to reduce and add an automatic test, this would be faster.

Comment 18

[Nicholas Nethercote [inactive]]

Turns out we have two BitSet implementations (see bug 552355) and I confirmed that the other one, in avmplus.h, is not affected by this bug.  Woo.

http://hg.mozilla.org/projects/nanojit-central/rev/74e1b2344f72

billm, how did you debug this?

Comment 19

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Thanks, Nick!

(In reply to comment #18)
> billm, how did you debug this?

Running in Valgrind pointed it out. I didn't get all the GC-related warnings you got, for some reason.

Comment 20

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/1ee418d71b1b

Comment 21

[Chris Leary [:cdleary] (not checking bugmail)]

http://hg.mozilla.org/mozilla-central/rev/1ee418d71b1b