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

RESOLVED FIXED

Status

()

defect
RESOLVED FIXED
8 years ago
4 years ago

People

(Reporter: azakai, Assigned: billm)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:critical?], fixed-in-nanojit, fixed-in-tracemonkey)

Attachments

(4 attachments)

Posted file 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
Possibly this is the root cause of bug 643805 in TI. There is some partial work in that bug to get a reduced testcase.
Blocks: 643805
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?
(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?
Ok, after some offline discussion and additional bisecting, the problem occurs for the first time at

http://hg.mozilla.org/tracemonkey/rev/1c3246c67c63
Depends on: 639420
(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 <vladimir@pobox.com>
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.
If someone else could try to replicate my bisection with Valgrind, that would be helpful.
> 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.
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.
(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
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)
Depends on: 623050
No longer depends on: 639420
Marking sg:critical due to unsafe writes to memory.
Group: core-security
Whiteboard: [sg:critical?]
Posted patch patchSplinter Review
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.
Assignee: general → wmccloskey
Status: NEW → ASSIGNED
Attachment #526331 - Flags: review?(nnethercote)
Posted file 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.
Ah, my last comment may already be unneeded :) ...
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.
Attachment #526331 - Flags: review?(nnethercote) → review+
(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.
Posted file 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.
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?
Summary: Segfault in compiled FreeType → Fix off-by-one error in Containers.cpp:BitSet::grow()
Whiteboard: [sg:critical?] → [sg:critical?], fixed-in-nanojit
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.
http://hg.mozilla.org/tracemonkey/rev/1ee418d71b1b
Whiteboard: [sg:critical?], fixed-in-nanojit → [sg:critical?], fixed-in-nanojit, fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/1ee418d71b1b
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Group: core-security
You need to log in before you can comment on or make changes to this bug.