Locate and fix the deeply or unboundedly recursive spot of the builtins of the VM.

RESOLVED FIXED in Future

Status

Tamarin
Virtual Machine
RESOLVED FIXED
8 years ago
7 years ago

People

(Reporter: Zsolt Vilagos, Unassigned)

Tracking

unspecified
Future
Dependency tree / graph
Bug Flags:
flashplayer-qrb +

Details

Attachments

(9 attachments, 25 obsolete attachments)

4.20 KB, patch
Details | Diff | Splinter Review
5.68 KB, text/plain
Details
3.31 KB, patch
Details | Diff | Splinter Review
5.01 KB, text/plain
Details
3.28 KB, patch
Lars T Hansen
: review+
Details | Diff | Splinter Review
3.96 KB, patch
Lars T Hansen
: review+
Details | Diff | Splinter Review
2.52 KB, patch
Details | Diff | Splinter Review
4.44 KB, patch
Details | Diff | Splinter Review
20.70 KB, patch
Lars T Hansen
: review+
Details | Diff | Splinter Review
(Reporter)

Description

8 years ago
User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1) Gecko/20090624 Firefox/3.5 (.NET CLR 3.5.30729)
Build Identifier: 

There are several functions in the VM that builds up the AS builtins. They are the native implementation of a function or they can be reached somehow from the builtins (e.g. the pcre engine via RegExp class). Some of the functions are deeply or unboundedly recursive and so, they may exceed stack space, especially on resource constrained devices (WinMo, etc.). Locate such spots and fix them with either unrecursive implementation or explicit stack checks.

Reproducible: Always

Steps to Reproduce:
N/A
(Reporter)

Comment 1

8 years ago
Created attachment 386975 [details] [diff] [review]
Stack usage monitor for Unix and Mac.

The patch enables measuring the stack usage by comparing the addresses of two local variables (one in the main function and one in the measured function).

!!! Only works with a single AvmCore instance !!!

Macro to enable the monitor: AVMPLUS_STACKPROFILE.

Makefile for Unix platform is ok, for Mac one need to include core/StackProfile.h and cpp sources in the compilation.

Prints the stack usage on every function enter and exit to std. At the end of the run, the maximum stack usage is printed on stdout.

The code is not intended to be a part of Tamarin source as it is but it is a little tool.
(Reporter)

Comment 2

8 years ago
Created attachment 386978 [details]
List of function checked against recursiveness.

The text file holds a list of functions that was checked if they are recursive and besides that if they are deeply or unboundedly recursive.

Primary focus was on the function that are native implementation of builtins or they can be reached somehow using builtins. Despite, there are several functions on the list that are not builtins but recursive.
(Reporter)

Comment 3

8 years ago
Created attachment 386979 [details]
Test cases driving the VM to use stack extensively.

Test cases that drive the functions enumerated in a previous attachment. The test cases have two purpose:
1. make the VM to go into a deep recursion. these cases enable monitoring if a non-recursive implementation does not use many stack space.
2. test the functions on various test cases to ensure that any modification to the source of the functions keeps the behaviour. so acceptance tests.

The tests are integrated into the acceptance test suite.

Updated

8 years ago
Flags: flashplayer-qrb+
Target Milestone: --- → flash10.1
(Reporter)

Comment 4

8 years ago
Created attachment 386996 [details] [diff] [review]
Non-recursive implementation of pcre's find_fixedlength.

Draft implementation of pcre/pcre_compile.cpp find_fixedlength.
The implementation uses custom allocation with malloc/free to build a stack of work items each of which represents a piece of regexp bytecode to process.

Please, comment if the use of the structure serving as the work item is ok. Also, the name of the structure may need a review. Currently, it is pi_ffl, which refers to proceccing_information_of_find_fixedlength.

The macros used to work with the stack may be used for all such stack or queue based algorithms at other function. Probably, a common implementation for such cases is required.

Measurements with pcre_findfixedlength.as (see the attachment of test cases).

The test case builds a regexp with 500 parentheses in the pattern (as same as ecma3/RegExp/eregress_119909.as does). find_fixedlength runs only when the engine finds a lookbehind assertion, therefore the pattern is surrounded by a lookbehind assertion.

The values below are relevant regarding the running of the targeted function only and not the whole program. The whole program needs more stack space because of other functions.

Original source:
  max stack usage: ~221 kilobytes
  max stack depth: 535 levels

Patched source:
  max stack usage: ~7 kilobytes
  max stack depth: 35 levels
(Reporter)

Comment 5

8 years ago
Created attachment 387869 [details] [diff] [review]
Non-recursive implementation of xml getDescendants

Stack usage stats with xmlfunctions.as (see test cases attachment)

the test creates a xml tree of 1000 levels depth

original: around ~100k
patched: around ~3-4k
Attachment #387869 - Flags: review?
(Reporter)

Comment 6

8 years ago
getdescendants.patch is the work of Peter Varga (pvarga@inf.u-szeged.hu). I just uploaded it.

Updated

8 years ago
Attachment #387869 - Flags: review? → review?(lhansen)
(Reporter)

Comment 7

8 years ago
Created attachment 388455 [details] [diff] [review]
Non-recursive implementation of pcre/pcre_compile.cpp::is_anchored

Some notes about the implementation:
The implementation of the function uses similar stack handling infrastructure as find_fixedlength. The two stack handling may be unified. But I put the stack handling defines before the function and I undef'ed them right after the function which makes it a unit in the code, so that other functions may not use these defines. So, unification might not be the best to do.

About the testing of the implementation:
This memop is a bt long but I need to make it clear how I tested the implementation, because it cannot be tested by using tamarin only.

I have run the ATS with the new code, there was no failues. The result was the same when I modified is_anchored to return TRUE/FALSE always. The ATS is not capable of testing this function correctly.

I have some hand-made test cases that cover (I think) the code paths of is_anchored function. By returning TRUE/FALSE always, none of my lil' test failed.

I have noticed that there are test cases in pcre itself. Lars Hansen told me that those test cases are not imported to ATS, therefore I began to play with them.

I was not able to build a pcre standalone to perform the pcre tests, the build files were missing. Finally, I downloaded pcre 7.3 from sourceforge, the same version tamarin has. That source compiles and build flawlessly, the test cases included succeed. Because the is_anchored implementation is the same in tamarin and sourceforge pcre 7.3, I put my implementation in the sf version. With the non-recursive is_anchored function, the downloaded version builds fine. None of the tests failed.

Finally and again, I returned TRUE/FALSE always from the downloaded-modified version, and some of the test failed. Consequently, my implementation is correct. At least there is not a test case in (tamarin + pcre) that makes it fail.

Last sentence, I talked with Lars about the need to import pcre test cases into ATS. Lars told me, that it may be of great importance to do that if we really want to modifiy pcre. Comments requested, please.
Attachment #388455 - Flags: review?
(Reporter)

Updated

8 years ago
Attachment #386996 - Flags: review?(lhansen)
(Reporter)

Updated

8 years ago
Attachment #388455 - Flags: review? → review?(lhansen)
(Reporter)

Comment 8

8 years ago
Measurements with the test case pcre_is_anchored.as attached to the bugreport.
Regexp with 500 parentheses:
original max stack usage : ~30k
patches max stack usage  : ~7k

The max stack usage is contrained to this function. Other function during the running of the test cases is not concerned.
(Reporter)

Comment 9

8 years ago
Comment on attachment 388455 [details] [diff] [review]
Non-recursive implementation of pcre/pcre_compile.cpp::is_anchored

propert freeing of memory of the stack data structure is missing.
Attachment #388455 - Flags: review?(lhansen)
(Reporter)

Comment 10

8 years ago
Created attachment 388688 [details] [diff] [review]
Non-recursive implementation of pcre/pcre_compile.cpp::is_anchored

Corrected deallocation of the work items used in the function.

Comment:
If you don't understand this, I think it is okay. I am not so verbose concerning the info below. This just a warning, using tamarin only and not the pcre sources downloadeable from pcre.org everything is okay.

changing malloc to pcre_malloc is useful, cause pcre_malloc is backed by mmgc which in turn checks for correct alloc/dealloc and therefore it helps writing leak-free code.

But using pcre_malloc and pcre_free in standalone pcre (see the comment for the first and now obsoleted attachment) is wring. pcretest.c changes the pcre_malloc and new_free pointer to new_malloc and new_free (both is in the pcretest.c file). new_malloc stores the size of the allocated block requested from elsewhere. Some time it compares the allocated size of is_anchored with the free'd size of somethin else which produces a false positive bug.
Attachment #388455 - Attachment is obsolete: true
Attachment #388688 - Flags: review?
(Reporter)

Updated

8 years ago
Attachment #388688 - Flags: review? → review?(lhansen)

Comment 11

8 years ago
Created attachment 389101 [details] [diff] [review]
Non-recursive implementation of xml deepCopy

Comment 12

8 years ago
Comment on attachment 386996 [details] [diff] [review]
Non-recursive implementation of pcre's find_fixedlength.

The code needs to use pcre_malloc and pcre_free rather than pure malloc and free.  See pcre_globals.cpp.
Attachment #386996 - Flags: superreview?(edwsmith)
Attachment #386996 - Flags: review?(lhansen)
Attachment #386996 - Flags: review+

Updated

8 years ago
Attachment #387869 - Flags: review?(lhansen) → review-

Comment 13

8 years ago
Comment on attachment 387869 [details] [diff] [review]
Non-recursive implementation of xml getDescendants

The logic is basically sound but there are a couple of other issues.

XMLObject::getParent() is called twice near the end; this function always allocates a new object, so this is wasteful.  Ditto, childIndex performs a full traversal of the child list and should probably not be called repeatedly like it is.

There are other cases of missing common subexpression elimination that are probably not expensive (eg, curr->m_node) but that cause clutter in the code.

Comment 14

8 years ago
Comment on attachment 388688 [details] [diff] [review]
Non-recursive implementation of pcre/pcre_compile.cpp::is_anchored

Generally OK, with the following remarks.

The assert() needs to be removed - we don't allow it in Tamarin; use AvmAssert() instead (no header required).

As a stylistic issue, the mapping from old code to new code would have been cleaner if you had not merged three cases, but I can live with this.

Is the memset() really needed?  memset() is incorrect for NULL values, and you are initializing all fields anyway.
Attachment #388688 - Flags: review?(lhansen) → review+
(Reporter)

Comment 15

8 years ago
Created attachment 389471 [details] [diff] [review]
refined implementation of non-recursive pcre find_fixedlength

Using pcre_malloc and pcre_free rather standard malloc and free.
Attachment #386996 - Attachment is obsolete: true
Attachment #389471 - Flags: review?(lhansen)
Attachment #386996 - Flags: superreview?(edwsmith)
(Reporter)

Comment 16

8 years ago
Created attachment 389474 [details] [diff] [review]
refined implementation of non-recursive pcre is_anchored

- Using pcre_malloc and pcre_free rather standard malloc and free.
- Leaving the same structure as the original imeplemtation of if'ed code parts for the different kinds of brackets.
- Using the indentation rules of the pcre lib. (no tabs, two spaces, three spaces at do-while, beginning code at the very first column).
- No memset.
- using AvmAssert instead of assert
Attachment #388688 - Attachment is obsolete: true
Attachment #389474 - Flags: review?(lhansen)

Comment 17

8 years ago
Created attachment 389498 [details] [diff] [review]
Non-recursive implementation of xml getDescendants v2

Comment 18

8 years ago
Created attachment 389499 [details] [diff] [review]
Non-recursive implementation of xml deepCopy v2
Attachment #389101 - Attachment is obsolete: true

Updated

8 years ago
Attachment #389498 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #389499 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #389474 - Flags: review?(lhansen) → review+

Comment 19

8 years ago
Comment on attachment 389471 [details] [diff] [review]
refined implementation of non-recursive pcre find_fixedlength

Looks OK; there's a FIX comment that indicates unfinished work?
Attachment #389471 - Flags: review?(lhansen) → review+

Comment 20

8 years ago
Comment on attachment 389498 [details] [diff] [review]
Non-recursive implementation of xml getDescendants v2

Nice!

Can probably optimize even more: lift CoerceE4XMultiname out of the loop.

Updated

8 years ago
Attachment #389498 - Flags: review?(lhansen) → review+

Comment 21

8 years ago
Comment on attachment 389499 [details] [diff] [review]
Non-recursive implementation of xml deepCopy v2

This is good; straightforward code.  You may wish to address some of the following though.

numSibling should be called numSiblings (since it's the number of siblings, not the
index of a particular sibling).

Initial add on parent_list should be NULL, not 0

In the loop that pushes siblings you could do 

  for ( uint32 siblingOffset = currIndex+1 ; siblingOffset < numSibling ; ++siblingOffset )
  
and then use just siblingOffset in the call to _getAt.

work_list is really a work_stack

parent_list is really a parent_stack

regarding the change to getIndex, I have to see if that API is used externally to tamarin,
eg by the Flash Player, but I'll consider it OK for the time being.
Attachment #389499 - Flags: review?(lhansen) → review+

Updated

8 years ago
Attachment #387869 - Attachment is obsolete: true

Comment 22

8 years ago
Created attachment 390206 [details] [diff] [review]
Non-recursive implementation of xml getDescendants v3
Attachment #389498 - Attachment is obsolete: true
Attachment #390206 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #390206 - Flags: review?(lhansen) → review+
(Reporter)

Comment 23

8 years ago
Created attachment 390212 [details] [diff] [review]
Non-recursive implementation of pcre/pcre_compile.cpp::find_fixedlength

Removed the FIX from the patch. I investigated the issue.
I didn't know if the code that is passed to find_fixedlegth is always ended with OP_END. In case when OP_KET ends the code, I dereference the parent work item of the actual work item which may be null. But, when pcre calls find_fixedlength, it always sets the last opcode to OP_END. Therefore it can never happen that the first work item which has no parent is ended with OP_KET.
Attachment #389471 - Attachment is obsolete: true
(Reporter)

Updated

8 years ago
Attachment #390212 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #390212 - Flags: review?(lhansen) → review+

Comment 24

8 years ago
Created attachment 390223 [details] [diff] [review]
Non-recursive implementation of xml deepCopy v3
Attachment #389499 - Attachment is obsolete: true
Attachment #390223 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #390223 - Flags: review?(lhansen) → review+
(Reporter)

Comment 25

8 years ago
Lars, are there any barriers before these patches can land?
thx in advance.

Comment 26

8 years ago
(In reply to comment #25)
> Lars, are there any barriers before these patches can land?
> thx in advance.

Ah, thanks for asking.  In principle they need superreview from Ed, but he's away on summer holiday for the next couple of weeks.  I'll ask around and find out who's available to do that review in Ed's place.

Comment 27

8 years ago
Created attachment 391015 [details] [diff] [review]
Non-recursive implementation of xml toXMLString

This solution of the toXMLString non-recursive implementation is probably a bit confusing. What do you think, is it a good idea to separate that for some methods which are part of the new class (XMLStringInfo), or would be better to avoid more function calls ?
Attachment #391015 - Flags: review?(lhansen)

Comment 28

8 years ago
Created attachment 391038 [details] [diff] [review]
Performance test case for recursive xml functions

This testcase generates an xml tree with a pseudo random width (max. 3) and a depth of 29. On the generated tree three recursive functions are run where the depth of recursion depends on the depth of the xml tree.
These functions:
- XML.copy()
- XML.descendants()
- XML.toXMLString()

Updated

8 years ago
Attachment #389474 - Flags: superreview?(rreitmai)

Updated

8 years ago
Attachment #390206 - Flags: superreview?(rreitmai)

Updated

8 years ago
Attachment #390212 - Flags: superreview?(rreitmai)

Updated

8 years ago
Attachment #390223 - Flags: superreview?(rreitmai)

Comment 29

8 years ago
Created attachment 391056 [details]
recursive vs non-recursive xml functions performance results

Results of a performance test which configuration is "language" and that extended with an own recursiveXMLFuncs ( https://bug502589.bugzilla.mozilla.org/attachment.cgi?id=391038 )test case.
The reference is a virgin tamarin-redux. The modified tamarin-redux is patched with non-recursive getDescendants ( https://bugzilla.mozilla.org/attachment.cgi?id=390206 ), deepCopy (https://bugzilla.mozilla.org/attachment.cgi?id=390223 ) and XMLToString ( https://bugzilla.mozilla.org/attachment.cgi?id=391015 ) patches.

Comment 30

8 years ago
(In reply to comment #29)
> Created an attachment (id=391056) [details]
> recursive vs non-recursive xml functions performance results

Excellent work.  I'm a little bit worried about the 7% slowdown on concatenatingStringsFromE4X but otherwise it looks good.  An investigation of that particular one through a profiler seems important.

(I've been wondering if these patches could benefit from a simple untyped stack data structure so that it does not have to malloc/free each individual node.  I don't know if that's where the bottleneck is, though.)

Comment 31

8 years ago
Comment on attachment 390206 [details] [diff] [review]
Non-recursive implementation of xml getDescendants v3

+'d based on wsharp@adobe.com review.
Attachment #390206 - Flags: superreview?(rreitmai) → superreview+

Comment 32

8 years ago
Comment on attachment 390223 [details] [diff] [review]
Non-recursive implementation of xml deepCopy v3

+'d based on wsharp@adobe.com review.
Attachment #390223 - Flags: superreview?(rreitmai) → superreview+

Comment 33

8 years ago
(In reply to comment #27)
> Created an attachment (id=391015) [details]
> Non-recursive implementation of xml toXMLString
> 
> This solution of the toXMLString non-recursive implementation is probably a bit
> confusing. What do you think, is it a good idea to separate that for some
> methods which are part of the new class (XMLStringInfo), or would be better to
> avoid more function calls ?

I think even the old code is confusing!  Whatever happened to procedural abstraction?  :-/

Is there some way for us to approach this differently?  I'm thinking, maybe we can disentangle control (recursion) from formatting by factoring formatting out into a separate function or even several functions.  This could be done in the old code, probably.  Then maybe adding non-recursive control to the resulting code is easier.
Status: UNCONFIRMED → NEW
Ever confirmed: true

Comment 34

8 years ago
Comment on attachment 391015 [details] [diff] [review]
Non-recursive implementation of xml toXMLString

Removing self from review, pending structural changes.
Attachment #391015 - Flags: review?(lhansen)

Comment 35

8 years ago
Created attachment 392478 [details] [diff] [review]
Non-recursive implementation of XMLList _resolveValue
Attachment #392478 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #392478 - Flags: review?(lhansen) → review?

Comment 36

8 years ago
(In reply to comment #35)
> Created an attachment (id=392478) [details]
> Non-recursive implementation of XMLList _resolveValue

Lars is on vacation until August 24 or so -- you should probably choose someone else to review :-)

Comment 37

8 years ago
Created attachment 393747 [details] [diff] [review]
Non-recursive implementation of xml toXMLString v2
Attachment #391015 - Attachment is obsolete: true
Attachment #393747 - Flags: review?

Comment 38

8 years ago
Comment on attachment 390223 [details] [diff] [review]
Non-recursive implementation of xml deepCopy v3

push needed please

Updated

8 years ago
Attachment #390212 - Flags: superreview?(rreitmai) → superreview+

Updated

8 years ago
Attachment #389474 - Flags: superreview?(rreitmai) → superreview+

Comment 39

8 years ago
Created attachment 399471 [details] [diff] [review]
Non-recursive implementation of pcre is_startline and is_anchored

This patch unifies the data structures used by is_anchored and is_startline, that why this patch includes the patch for is_anchored.

Updated

8 years ago
Attachment #399471 - Flags: review?(lhansen)

Updated

8 years ago
Attachment #393747 - Flags: review? → review?(lhansen)

Updated

8 years ago
Attachment #392478 - Flags: review? → review?(lhansen)

Comment 40

8 years ago
Created attachment 401217 [details] [diff] [review]
Non-recursive implementation of pcre find_firstassertedchar
Attachment #401217 - Flags: review?(lhansen)

Comment 41

8 years ago
Comment on attachment 392478 [details] [diff] [review]
Non-recursive implementation of XMLList _resolveValue

My fault for taking so long: the patch no longer applies, there are changes in Tamarin.  Please regenerate patch.
Attachment #392478 - Flags: review?(lhansen) → review-

Comment 42

8 years ago
Comment on attachment 393747 [details] [diff] [review]
Non-recursive implementation of xml toXMLString v2

The two static variables in XMLToStringInfo are not acceptable; there will be multiple instances of the VM running in the same process and writable statics are not allowed unless they are carefully controlled singletons.

What is your estimate of the number of XMLToStringInfo instances that will be constructed as a function of the size of the graph?  The node is quite large.
Attachment #393747 - Flags: review?(lhansen) → review-

Comment 43

8 years ago
Comment on attachment 399471 [details] [diff] [review]
Non-recursive implementation of pcre is_startline and is_anchored

The rewrite is beautifully done, but is it quite right?  The way I read it, there needs to be a 'break' following each instance of IA_IS_PUSH in both the new functions, because that's the effect of the recursive call: break out of the do-while loop, and jump back to the dispatch in the while loop.  What do you think?  Am I not understanding the mechanism?

Comment 44

8 years ago
Created attachment 402298 [details] [diff] [review]
Non-recursive implementation of XMLList _resolveValue v2
Attachment #392478 - Attachment is obsolete: true
Attachment #402298 - Flags: review?(lhansen)

Comment 45

8 years ago
Created attachment 402817 [details] [diff] [review]
Non-recursive implementation of pcre is_startline and is_anchored v2

I investigated your question and I created some experiments...
The question was whether OP_BRA, OP_CBRA, OP_ASSERT, OP_ONCE and OP_COND opcodes can be followed by an OP_ALT opcode, because in this case the breaks (what you mentioned) corrupt the correct working.
I think this case isn't possible (I couldn't create a pattern that would have  caused these order of opcodes and I didn't found it in the test cases either), thus putting breaks after IA_IS_PUSH macros is reasonable.
Attachment #399471 - Attachment is obsolete: true
Attachment #402817 - Flags: review?(lhansen)
Attachment #399471 - Flags: review?(lhansen)

Comment 46

8 years ago
Created attachment 403239 [details] [diff] [review]
Non-recursive implementation of xml _equals
Attachment #403239 - Flags: review?(lhansen)

Updated

8 years ago
Blocks: 458055

Updated

8 years ago
Assignee: nobody → lhansen

Updated

8 years ago
Priority: -- → P3

Updated

8 years ago
Duplicate of this bug: 458055

Updated

8 years ago
Attachment #402817 - Flags: review?(lhansen) → review+

Comment 48

8 years ago
Comment on attachment 403239 [details] [diff] [review]
Non-recursive implementation of xml _equals

This is correct.  I am however concerned about the space usage; the old algorithm used space proportional to the depth of the XML terms, the new one uses space proportional to the product of the depth of the XML term and the maximum width of one term.  The simple fix for this is to not expand each term onto the work stacks but to maintain one additional piece of state, the position within a term on the work stack.
Attachment #403239 - Flags: review?(lhansen) → review+

Comment 49

8 years ago
Comment on attachment 402298 [details] [diff] [review]
Non-recursive implementation of XMLList _resolveValue v2

Dense stuff but this looks good to me.
Attachment #402298 - Flags: review?(lhansen) → review+

Updated

8 years ago
Attachment #401217 - Flags: review?(lhansen) → review+

Comment 50

8 years ago
As a general remark, I will implement a simple "local stack storage" data structure that all these patches can share so that we avoid individual malloc/free calls.  Doing so will be a local fix on top of the patches; none of them need change structure in significant ways.
Status: NEW → ASSIGNED

Comment 51

8 years ago
(In reply to comment #50)
> As a general remark, I will implement a simple "local stack storage" data
> structure that all these patches can share so that we avoid individual
> malloc/free calls.  Doing so will be a local fix on top of the patches; none of
> them need change structure in significant ways.

Seems likely that we may be able to use the VMPI_alloca infrastructure for this, though it is tied to a specific GC and thus may be a little tricky to use from within the pcre code.  Investigations ongoing.

Updated

8 years ago
Attachment #389474 - Attachment is obsolete: true

Comment 52

8 years ago
Created attachment 405252 [details] [diff] [review]
Cumulative PCRE patch, slightly reorganized

The slight reorganization consists in moving common code for is_startline and is_anchored out of pcre_internal.h and into pcre_compile.cpp, which is the only place they're used.  (The next patch removes that code in any case.)
Attachment #390212 - Attachment is obsolete: true
Attachment #401217 - Attachment is obsolete: true
Attachment #402817 - Attachment is obsolete: true

Comment 53

8 years ago
Created attachment 405253 [details] [diff] [review]
Cumulative PCRE patch, stack memory reengineered

Should be ready to land.  This code is like the patch it replaces except that the hand-managed stacks are replaced by a simple templated stack type; as a result, most macros introduced by the previous patch go away and storage management becomes cleaner.

Ed, I'd like a review of at the stack data type and a superreview on the patch in general: the code has been through a couple of rounds of review and passes all tests, but we still have to choose whether to land this patch (my choice) or just introduce stack limit checking in the recursive functions.  Your call.
Attachment #405252 - Attachment is obsolete: true
Attachment #405253 - Flags: superreview?(edwsmith)

Comment 54

8 years ago
Created attachment 405269 [details] [diff] [review]
xml getDescendants v4, restructured to fit current code

Pretty much ready to land I think; I optimized slightly (got rid of intermediate lists).
Attachment #390206 - Attachment is obsolete: true

Comment 55

8 years ago
Created attachment 405421 [details] [diff] [review]
xml deepCopy v4, restructured to fit current code
Attachment #390223 - Attachment is obsolete: true

Comment 56

8 years ago
Comment on attachment 405253 [details] [diff] [review]
Cumulative PCRE patch, stack memory reengineered

pcre_compile.cpp:

line 1181: should memory[20] be [TYPED_SEGMENT_SIZE] or is 20 in both places just a coincidence.

how hot are the TypedStack methods? should spot-check generated code for TypedStack<T>::invariants() in release builds to ensure it goes away and inline or #ifdef to make sure.  if it goes away, great and nice to keep the code uncluttered by #ifdefs.

potential performance pitfall if a stack hovers back and forth from 19 to 21, hysteresis to remember and re-use one or more TypedSegment's would fix it.  (no idea if this happens).

I looked at each of the recursive call sites and checked that the parameters made their way into the work item instances.  Not all of the parameters get modifed in the recursive call paths and the ones that dont get modified, arent in work items.  (cool).  I didn't see them get modified anywhere else, but if one was modified and not copied into a work item, it would be a hard to spot bug.  making all non-workitem arguments const might mitigate risk.

... so if the code worked before, it looks like it still should.
Attachment #405253 - Flags: superreview?(edwsmith) → superreview+

Comment 57

8 years ago
(In reply to comment #56)
> (From update of attachment 405253 [details] [diff] [review])
> pcre_compile.cpp:
> 
> line 1181: should memory[20] be [TYPED_SEGMENT_SIZE] or is 20 in both places
> just a coincidence.

Good catch, it should be [TYPED_SEGMENT_SIZE].

> how hot are the TypedStack methods? should spot-check generated code for
> TypedStack<T>::invariants() in release builds to ensure it goes away and 
> inline or #ifdef to make sure.  if it goes away, great and nice to keep
> the code uncluttered by #ifdefs.

They should be moderately hot, will look to see what GCC does here.

> potential performance pitfall if a stack hovers back and forth from 19 to 21,
> hysteresis to remember and re-use one or more TypedSegment's would fix it.
> (no idea if this happens).

Would be surprising if the recursion goes that deep very often, but I will check.

> I looked at each of the recursive call sites and checked that the parameters
> made their way into the work item instances.  Not all of the parameters get
> modifed in the recursive call paths and the ones that dont get modified, arent
> in work items.  (cool).  I didn't see them get modified anywhere else, but if
> one was modified and not copied into a work item, it would be a hard to spot
> bug.  making all non-workitem arguments const might mitigate risk.

Good idea.

Comment 58

8 years ago
(In reply to comment #57)
> 
> > how hot are the TypedStack methods? should spot-check generated code for
> > TypedStack<T>::invariants() in release builds to ensure it goes away and 
> > inline or #ifdef to make sure.  if it goes away, great and nice to keep
> > the code uncluttered by #ifdefs.
> 
> They should be moderately hot, will look to see what GCC does here.

GCC inlines the TypedStack methods and everything pretty much boils away in the process.

> > potential performance pitfall if a stack hovers back and forth from 19 to
> > 21, hysteresis to remember and re-use one or more TypedSegment's would
> > fix it. (no idea if this happens).
> 
> Would be surprising if the recursion goes that deep very often, but I will
> check.

Instrumentation shows that the typical depth is 1, only a single case in our RegExp regression tests went to 2.  On Zsolt's tests we see more variation, but they were meant to stress the recursion, and even there all but one test stays below 7.  (The outlier has 501 :-)

BTW will land the recursion tests along with the patch.

Updated

8 years ago
Attachment #405253 - Attachment is obsolete: true

Comment 59

8 years ago
Comment on attachment 405253 [details] [diff] [review]
Cumulative PCRE patch, stack memory reengineered

redux changeset:   2751:cfe9cd7c8813

Comment 60

8 years ago
Comment on attachment 386979 [details]
Test cases driving the VM to use stack extensively.

redux changeset:   2751:cfe9cd7c8813
Attachment #386979 - Attachment is obsolete: true

Comment 61

8 years ago
Created attachment 405488 [details] [diff] [review]
Initial patch

Overflow checking from unrewritable PCRE functions.  Uses a thread-local for storing a Toplevel* across a call to PCRE code; the PCRE code calls back to the AvmCore to check the stack.

This is less a patch than something to start talking about... it duplicates several code paths in the system, only because the existing code paths take a MethodEnv, which is not available to me.  It turns out that in the last instance that MethodEnv is never required by the existing code paths; we want the AvmCore and Toplevel linked from it, and those /are/ available to me.
Attachment #405488 - Flags: review?(edwsmith)

Updated

8 years ago
Depends on: 521551

Comment 62

8 years ago
Created attachment 405729 [details] [diff] [review]
PCRE overflow handing v2

Simplified somewhat.  This could still be cleaner - if the jitted code that calls handleInterrupt and handleStackOverflow would pass a Toplevel* instead of a MethodEnv*.
Attachment #405488 - Attachment is obsolete: true
Attachment #405729 - Flags: review?(edwsmith)
Attachment #405488 - Flags: review?(edwsmith)

Comment 63

8 years ago
Created attachment 405829 [details] [diff] [review]
Non-recursive implementation of xml toXMLString v3
Attachment #393747 - Attachment is obsolete: true
Attachment #405829 - Flags: review?(lhansen)

Updated

8 years ago
Blocks: 521551
No longer depends on: 521551

Updated

8 years ago
Attachment #405829 - Flags: review?(lhansen) → review+

Comment 64

8 years ago
Comment on attachment 405829 [details] [diff] [review]
Non-recursive implementation of xml toXMLString v3

Nice refactoring.  I need to make another pass before landing but I consider this good enough for r+.

Comment 65

8 years ago
Created attachment 407036 [details] [diff] [review]
XML overflow handling (using stack checks)

Low-risk implementation of recursion handling for XML code based on explicit stack checking; locations checked are those identified by Peter.  Lands on top of the PCRE overflow handling v2 (uses the AvmCore functions introduced by that patch).  Intended as stopgap measure.
Attachment #407036 - Flags: review?(edwsmith)

Updated

8 years ago
Whiteboard: Has patch

Comment 66

8 years ago
On one of the brew platforms, the pcre_compile is crashing for the file
eregress_119909_.swf as the assigned stack is just 128KB and compile_regex and
compile_branch are recursively calling each other. Are there any fixes for this
case or is it under investigation?

Comment 67

8 years ago
(In reply to comment #66)
> On one of the brew platforms, the pcre_compile is crashing for the file
> eregress_119909_.swf as the assigned stack is just 128KB and compile_regex and
> compile_branch are recursively calling each other. Are there any fixes for this
> case or is it under investigation?

The fix for that is pending, should land this week.

Comment 68

8 years ago
Comment on attachment 405729 [details] [diff] [review]
PCRE overflow handing v2

The tension over MethodEnv* vs Toplevel* happens a lot; C++ native methods typically want to get Toplevel* via their own ScriptObject, whereas jit code wants to use MethodEnv* since the 3 additional loads to get Toplevel usually aren't worth inlining.
Attachment #405729 - Flags: review?(edwsmith) → review+

Updated

8 years ago
Attachment #407036 - Flags: review?(edwsmith) → review+

Comment 69

8 years ago
(In reply to comment #62)
> Created an attachment (id=405729) [details]
> PCRE overflow handing v2
> 
> Simplified somewhat.  This could still be cleaner - if the jitted code that
> calls handleInterrupt and handleStackOverflow would pass a Toplevel* instead
> of a MethodEnv*.

With this fix in place we discover something we should have realized a long time ago: even though many of the subroutines are now iterative, pcre_compile itself remains recursive and will be recursive in those cases where the rewritten subroutines were also recursive.  The explicit stack overflow check in pcre_compile will cause a stack overflow to be signaled reliably; however, the end result is that we derive no benefit from the rewritten subroutines - all test cases fail with stack overflow errors.

Comment 70

8 years ago
Created attachment 407997 [details] [diff] [review]
PCRE overflow handling v3

Rebased to redux 2854.
Attachment #405729 - Attachment is obsolete: true

Comment 71

8 years ago
Comment on attachment 407997 [details] [diff] [review]
PCRE overflow handling v3

redux changeset:   2887:fec599faa108
Attachment #407997 - Attachment is obsolete: true

Comment 72

8 years ago
Comment on attachment 407036 [details] [diff] [review]
XML overflow handling (using stack checks)

redux changeset:   2888:a34e717a8864
Attachment #407036 - Attachment is obsolete: true

Comment 73

8 years ago
Remaining work on this bug: Rebase, clean up, and land the rewritten XML code (attachment #405829 [details] [diff] [review]).  Not urgent, as there's a stopgap solution in place with stack checks.
Assignee: lhansen → nobody
No longer blocks: 521551
Status: ASSIGNED → NEW
Priority: P3 → --
Whiteboard: Has patch
Target Milestone: flash10.1 → Future

Comment 74

8 years ago
more unwanted recursion:

 * Traits::resolveSignatures recurses up the inheritance and the interface dag
 * Traits::countInterfaces and addInterfaces recurse up the interface dag, too.

Simple but somewhat heavy fix for each case is a working queue of Traits* to visit.

Updated

8 years ago
Depends on: 529540

Updated

8 years ago
Depends on: 532906

Updated

8 years ago
Depends on: 551004

Updated

8 years ago
Depends on: 556874

Updated

7 years ago
Status: NEW → RESOLVED
Last Resolved: 7 years ago
Resolution: --- → FIXED

Comment 75

7 years ago
This has been used as a tracker of sorts (although it's not marked as such).  I'm a bit uncomfortable closing it w/out a global audit of the code, but with or without this bug, we can still open bugs for specific cases.
You need to log in before you can comment on or make changes to this bug.