Closed Bug 80981 Opened 19 years ago Closed 18 years ago

Need extended jump bytecode to avoid "script too large" errors, etc.

Categories

(Core :: JavaScript Engine, defect, P2)

x86
All
defect

Tracking

()

VERIFIED FIXED
mozilla0.9.6

People

(Reporter: pschwartau, Assigned: brendan)

References

Details

(Keywords: js1.5, Whiteboard: [QA note: verify interactively in the JS shell])

Attachments

(5 files, 13 obsolete files)

3.20 KB, text/plain
Details
8.25 KB, text/plain
Details
110.60 KB, patch
jband_mozilla
: superreview+
Details | Diff | Splinter Review
10.45 KB, text/plain
Details
185.56 KB, text/plain
Details
This evolved out of bug 74474. Brendan's comment from that bug:

"I think you should file a bug: 'please add an extended jump bytecode to JS
and use it to avoid "script too large", "switch too large", etc. errors.'"
Status: NEW → ASSIGNED
Keywords: js1.5, mozilla0.9.2
Priority: -- → P2
Target Milestone: --- → mozilla0.9.2
Target Milestone: mozilla0.9.2 → mozilla0.9.3
Another js1.5 issue, but help wanted.

/be
Target Milestone: mozilla0.9.3 → mozilla0.9.4
Working on this in background mode already.

/be
Target Milestone: mozilla0.9.4 → mozilla0.9.5
There seems to be a problem with patch 49788. The following testcase
crashes when this patch is applied, on both WinNT and Linux: 


               ecma_3/Statements/regress-74474-003.js


Will attach WinNT stack trace below - 
Attached file WinNT stack trace
Note: I get the same crash by loading this testcase directly
       in the JS shell (i.e. avoiding the test driver): 

js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/shell.js')
js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/Statements/regress-74474-003.js')

Crashes with stack trace as above - 


If I do the same thing without the patch applied, I get an InternalError:

js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/shell.js')
js> load('D:/JS_TRUNK/mozilla/js/tests/ecma_3/Statements/regress-74474-003.js')
2: InternalError: switch statement too large
Attachment #48207 - Attachment is obsolete: true
Attachment #49788 - Attachment is obsolete: true
Ran JS testsuite with patch applied on Linux and WinNT. Only got the 
known failures in both the debug and optimized JS shells. In particular,
I no longer get a crash on 

               ecma_3/Statements/regress-74474-003.js


Meanwhile, I will update or remove:

               js1_5/Regress/regress-97646-001-n.js
               js1_5/Regress/regress-97646-002-n.js


They currently expect an exit code of 3. This leaves the question
of how I can test bug 97646. These two testcases used to produce
an "InternalError: (block, etc.) too large" error - but the JS shell
failed to produce an exit code of 3: that is bug 97646.

Do I simply make these two tests bigger and bigger until they DO
produce an InternalError? How big should I make them now that we 
have an extended jump bytecode? Or is this method no longer feasible?
Attachment #50363 - Attachment is obsolete: true
Ran JS testsuite successfully with patch 50612 applied on Linux and WinNT.
Again only got the known failures in both the debug and optimized JS shells. 
Attachment #50612 - Attachment is obsolete: true
Attachment #50639 - Attachment is obsolete: true
Attachment #50769 - Attachment description: remove cx->tempPool non-LIFO allocation abusage, and optimize arenas for the large-single-allocation case → Thank you, bugzilla! I got an HTTP time-out, but apparently the attachment "took".
Attachment #50769 - Attachment is obsolete: true
Cc'ing more testing buddies.  I'm hoping to get r=khanson and sr=shaver, but
more are welcome.

/be
Attachment #50671 - Attachment is obsolete: true
Attachment #50770 - Attachment is obsolete: true
Attachment #51654 - Attachment description: latest patch, a few nits picked -- diff of previous and this patch next → the money: latest patch, a few nits picked -- diff of previous and this patch next
Comment on attachment 51654 [details] [diff] [review]
the money: latest patch, a few nits picked -- diff of previous and this patch next

This patch is good, but it didn't handle the SRC_PCBASE note correctly.
See next comment in bug for more on why.

/be
Attachment #51654 - Attachment is obsolete: true
The difficulty with SRC_PCBASE is that, as with any source note, the offset
operands counted by its arity must be non-negative (due to the frequency coding
used to compress them: [0,127] fits in one byte, [128,0x7fffff] fit in three,
with the high bit set on the first byte).

But SRC_PCBASE annotates an opcode such as JSOP_GETELEM with an offset reaching
backwards, toward lower bytecode, to help js_DecompileValueGenerator report
'foo[bar() - baz.bletch] has no properties' given 'foo[bar() - baz.bletch].argh'
where no such property in foo exists -- where the .argh dereferences undefined
or null, IOW.  Could a backward SRC_PCBASE offset span a span-dependent
instruction that needed to be extended?

Only in a pathological case such as foo[bar1 ? bar2 ? ... bar10000 ? baz10000 :
 ...].argh.  There aren't any other branch/jump bearing expressions than ?: that
could be nested within the span of a SRC_PCBASE offset.  But to be completely
correct, the last patch modifies the js_SrcNoteSpec struct and table, turning
the isSpanDep packed boolean into a -1/0/1 span-direction number.  Consequently
the FindNearestLowerSpanDep call for the source note offset's target must start
from 0 if target < pivot, and not from sd - sdbase.

The only other change from the previous patch was a cosmetic one in jsinterp.c:
rename the XSEARCH_PAIRS local macro for JSOP_LOOKUPSWITCHX to have a clearer
name that didn't prefix "X" (see attachment 50858 [details] for why extended jump op and
format names suffix "X").

I hope the diff of patches helps.  Ask me anything, please help get this patch
in for 0.9.5.

/be
Still awaiting review.

/be
Target Milestone: mozilla0.9.5 → mozilla0.9.6
I'm early in my puzzling (so this is perhaps a stupid question), but are these 
really supposed to all be '8's?

+#define GET_JUMPX_OFFSET(pc)    ((int32)(((((((pc)[1] << 8) | (pc)[2]) << 8)  \
+                                           | (pc)[3]) << 8) | (pc)[4]))
Brendan kindly pointed out that I was misreading the paren grouping.
But maybe my use of Horner's rule is wrong-headed.  Are there CPUs that can
issue two or more independent loads and shifts in a super-scalar or otherwise
instruction-level-parallel fashion?  Then

+#define GET_JUMPX_OFFSET(pc)    ((int32)(((pc)[1] << 24) | ((pc)[2] << 16)    \
+                                         | ((pc)[3] << 8) | (pc)[4]))


would be better.

/be
Comment on attachment 51886 [details] [diff] [review]
most money: same as last patch, but merged up to top of trunk (bug 99663's fix was checked in last night, touching files in this patch)

sr=jband.
I'm good for an sr here. But someone prepared to dig deeper into the code than I ought to be giving a primary review. I didn't see anything objectionable, but I don't claim to have it all figured out.

I'd love to see some test coverage that specificly exercises these cases - maybe even with some errors to check decompile. 

I'll run with this in my tree and make noise if I see anything bad come up.
Attachment #51886 - Flags: superreview+
Having lost the race for the cushy high-level-sr stamp, I guess I have to duel
to the death with rogerl and khanson to see who gets to spend time in a debugger
analyzing this monster.

Draw, gentlemen!
I lost the duel!  I will spend some serious time looking at and testing this 
patch.

=Kenton=
I changed the GET_JUMPX_OFFSET macro to use parallelizable shifts.  Today I
learned that P4 can do several such operations at once, but only if they are
optimized into multiplies (!).  I'll leave them coded as shifts and let the
various compilers worry about selecting mul instructions.

/be
Attachment #51656 - Attachment is obsolete: true
Attachment #51720 - Attachment description: more money: copy with non-negative yet backwards offset of SRC_PCBASE → more money: cope with non-negative yet backwards offset of SRC_PCBASE
Attachment #51720 - Attachment is obsolete: true
Attachment #51721 - Attachment is obsolete: true
Attachment #51886 - Attachment is obsolete: true
Comment on attachment 53656 [details]
new-on-left plain diff of previous patch with latest

Not a patch, just an aid to reviewers doing re-review.

shaver, can you re-sr=?  khanson, how's it going?

/be
Attachment #53656 - Attachment is patch: false
Comment on attachment 53654 [details] [diff] [review]
patch for final review, fixes "off-by-one" error inherent in FindNearestLowerSpanDep

sr=jband
ditto everything I said on my sr of the previous patch.
Attachment #53654 - Flags: superreview+
I have examined the diff file in detail.  The only nit I found was in AddSpanDep 
where the line "if (index + 1 == 0)" where index is declared an unsigned int.
I've been through several portions of the code in the debugger.  Haven't seen 
anythng unusual.  Wrote a test program that breaks the prepatch version but runs 
correctly in the patched version. I am ok with the patch, but willing to further 
examine any areas of concern.  r=khanson

Kenton Hanson
kenton, thanks -- good test, we need many more such.  Maybe we can auto-generate
travesties with long basic blocks and/or lots of basic blocks, to test all the
combinations.  Hmmm.

The 'if (index + 1 == 0)' test is checking for unsigned int overflow -- it
seemed cheaper and more portable than testing against a UINT_MAX.  It worksforme
on many architectures, and I believe/wish/hope the C and C++ standards mandate
such wrap around (but IANALL [IAmNotALanguageLawyer]).

/be
I'm being aggressive, this scary patch has been through enough delay! :-)  Any
new (post-checkin, I mean) probs, please file new bugs.

/be
Status: ASSIGNED → RESOLVED
Closed: 18 years ago
Resolution: --- → FIXED
Kenton's testcase added to JS testsuite: 

          mozilla/js/tests/js1_5/Regress/regress-80981.js

Marking VERIFIED FIXED. Testcase passes in the debug and optimized
JS shells on WinNT, Linux, and Mac 9.1. It passes either when loaded
by the Perl test driver, or interactively in the JS shell via load().
Status: RESOLVED → VERIFIED
Whiteboard: [QA note: verify interactively in the JS shell]
> Meanwhile, I will update or remove:

>         js1_5/Regress/regress-97646-001-n.js
>         js1_5/Regress/regress-97646-002-n.js


I have CVS-deleted these two tests. They contain very large blocks.
But because of the fix to this bug, these are no longer large enough
to trigger the internal error and exit code 3 that the tests looked for.
Per attachment 50858 [details],

We now ReportStatementTooLarge only if
- a jump offset overflows 32 bits, signed;
- there are 2**32 or more span dependencies in a script;
- a backpatch chain link is more than (2**30 - 1) bytecodes long;
- a source note's distance from the last note, or from script main entry
  point, is > 0x7fffff bytes.

It will be hard to come up with a testcase that produces "Statement too large"
or a kindred error report.  Your best bet short of configuring a 64-bit-CPU
system with > 4GB of memory is to attack the last item.  Since each source line
gets a SRC_NEWLINE note, you'll need to make the attacking script fit on one
huge line!

Seriously, this isn't worth doing.  A travesty generator that triggers the span
dependent instruction selection for various kinds of jumps is likelier to be
fruitful.  Or just more hand-written big scripts that mix different kinds of
control flow constructs.

/be
*** Bug 97920 has been marked as a duplicate of this bug. ***
Flags: testcase+
You need to log in before you can comment on or make changes to this bug.