The following line of code will hang WebKit. Don't even get a "Maximum call stack size exceeded" error. JSON.stringify({ toJSON: function () { return { foo: this }; } }); Reproduces in Safari Version 8.0.5 (10600.5.9), as well as nightly build r182472. Expected: a "TypeError: JSON.stringify cannot serialize cyclic structures." should be thrown.
Two problems here: (1) The stringifier checks for recursion, but not inside appendNextProperty. (2) The recursion check walks the whole stack, so it is worst case O(N^2). We should use a hash instead.
<rdar://problem/20491535>
Created attachment 397165 [details] Patch
(In reply to Chris J. Shull from comment #0) > JSON.stringify({ toJSON: function () { return { foo: this }; } }); > > Expected: a "TypeError: JSON.stringify cannot serialize cyclic structures." > should be thrown. Please note that `toJSON` creates a new object on every call, so JSON.stringify never reaches `this` to throw TypeError per spec. Proposed patch throws stack overflow error like other runtimes do. Cold runs, --outer 8: TipOfTree patch json-stringify-deep-stack 868.4032+-7.1116 833.3949+-9.5908
Comment on attachment 397165 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397165&action=review > Source/JavaScriptCore/ChangeLog:17 > + b) Significantly improves performance of cyclic structures checks by using > + HashSet: 4.2% speed-up on provided microbenchmark that tests serialization > + of deeply nested object. Before we used a MarkedArgumentBuffer. Is it OK that the HashSet is not marked? Garbage collection will scan a MarkedArgumentBuffer, but not a HashSet. If it is OK, why?
Comment on attachment 397165 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397165&action=review > Source/JavaScriptCore/runtime/JSONObject.cpp:319 > +static constexpr unsigned maximumRecursion = 40000; I don’t think we need "static" with "constexpr".
Comment on attachment 397165 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397165&action=review > Source/JavaScriptCore/runtime/JSONObject.cpp:-134 > - MarkedArgumentBuffer m_objectStack; Using MarkedArgumentBuffer is necessary. Otherwise, sophisticated input can cause GC crash.
Created attachment 397192 [details] Patch Revert HashSet change, drop `static`, and adjust StringBuilde test.
(In reply to Yusuke Suzuki from comment #7) > Using MarkedArgumentBuffer is necessary. Otherwise, sophisticated input can > cause GC crash. I had a sense there is good reason why `m_objectStack` duplicates `m_holderStack`, now I got it! I wonder if WeakSet can be used instead of MarkedArgumentBuffer here?
Comment on attachment 397192 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397192&action=review Nice, I have suggestion about this check. > Source/JavaScriptCore/runtime/JSONObject.cpp:414 > + if (UNLIKELY(m_holderStack.size() > maximumRecursion)) { > + throwStackOverflowError(m_globalObject, scope); > + return StringifyFailed; > + } > + For these entry-point of recursive calls, how about using `if (UNLIKELY(!vm.isSafeToRecurseSoft()))` check instead? Since isSafeToRecurseSoft reads current stack-pointer, it offers better stack handling I think. > Source/JavaScriptCore/runtime/JSONObject.cpp:652 > + if (UNLIKELY(markedStack.size() > maximumRecursion)) Ditto. > Source/JavaScriptCore/runtime/JSONObject.cpp:705 > + if (UNLIKELY(markedStack.size() > maximumRecursion)) Ditto.
(In reply to Yusuke Suzuki from comment #10) > For these entry-point of recursive calls, how about using `if > (UNLIKELY(!vm.isSafeToRecurseSoft()))` check instead? > Since isSafeToRecurseSoft reads current stack-pointer, it offers better > stack handling I think. I've tried vm.isSafeToRecurseSoft(), vm.isSafeToRecurse(), and m_stackCheck.isSafeToRecurse(): none of them passes the test as (I suspect) recursion happens in C++ code, while VM stack is empty.
Comment on attachment 397192 [details] Patch LGTM, but is there no test262 coverage for this?
Comment on attachment 397192 [details] Patch Oh ack, I've no idea how I missed the whole thread here. Reversing r+ just for that reason.
Comment on attachment 397192 [details] Patch Er sorry, those comments precede the current patch and are addressed. Reinstating.
Comment on attachment 397192 [details] Patch Hold on. Why doesn't the isSafeToRecurse() checks work?
(In reply to Mark Lam from comment #15) > Comment on attachment 397192 [details] > Patch > > Hold on. Why doesn't the isSafeToRecurse() checks work? Yeah, this sounds very strange. isSafeToRecurse etc. is using C stack pointer. 1123 bool isSafeToRecurse(void* stackLimit) const 1124 { 1125 void* curr = currentStackPointer(); 1126 return curr >= stackLimit; 1127 } So, it should work on C++ / JS. Can you investigate why isSafeToRecurse is not working?
(In reply to Yusuke Suzuki from comment #16) > (In reply to Mark Lam from comment #15) > > Comment on attachment 397192 [details] > > Patch > > > > Hold on. Why doesn't the isSafeToRecurse() checks work? > > Yeah, this sounds very strange. isSafeToRecurse etc. is using C stack > pointer. > > 1123 bool isSafeToRecurse(void* stackLimit) const > 1124 { > 1125 void* curr = currentStackPointer(); > 1126 return curr >= stackLimit; > 1127 } > > So, it should work on C++ / JS. Can you investigate why isSafeToRecurse is > not working? I think I know what the issue here is: you're not seeing a stack overflow with the isSafeToRecurse() check because the test never actually overflowed, and we still have ample stack to run with. V8 and FF may have placed an artificial lower bounds on the depth of the parse so that they can throw a stack overflow error even though the real stack never overflowed. With that in mind, let me think of the proper way to address this, and if we want to address it.
Comment on attachment 397192 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397192&action=review > JSTests/stress/json-stringify-stack-overflow.js:29 > +{ > + const obj = {}; > + obj.toJSON = function() { return {key: obj}; }; > + > + shouldThrow(function() { > + JSON.stringify(obj); > + }); > + > + shouldThrow(function() { > + JSON.stringify({a: {b: obj}}); > + }); > +} This case is interesting in motivating this investigation. From JS' perspective, this looks like infinite recursion. But if we look at bottom of Stringifier::appendStringifiedValue(), we'll see that we do our parsing using a side stack m_holderStack which is aches codetually a Vector. Stepping thru the code, I see that we're stuck here: do { while (m_holderStack.last().appendNextProperty(*this, builder)) // <========== this never returns false because we have an infinite number of objects to add. RETURN_IF_EXCEPTION(scope, StringifyFailed); So, this code will happily iterate in that while loop until m_holderStack overflows. Since m_holderStack is a Vector, it will only overflow when its size is > UINT_MAX. UINT_MAX is 4G worth of elements. The script can run a very long time before it gets there. With this in mind, Alexey's solution of imposing a cap on m_holderStack growth is a correct solution. However, I'd like to give a bit more thought to how and where that check should go. More feedback in a bit ...
Comment on attachment 397192 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=397192&action=review r=me with fixes. > Source/JavaScriptCore/runtime/JSONObject.cpp:319 > +constexpr unsigned maximumRecursion = 40000; Let's call this "maximumHolderStackRecursion". "maximumRecursion" can logically work, but is just too misleading as it strongly suggests that it has to do with native stack recursion instead of the side stack. > Source/JavaScriptCore/runtime/JSONObject.cpp:410 > + if (UNLIKELY(m_holderStack.size() > maximumRecursion)) { Let's make this "m_holderStack.size() >= maximumRecursion" instead of ">". The reason is that we're about to add one more entry below. If we check for "> max", then we'll end up allow max + 1 entries which is not what the name says. Technically, "== max" is sufficient, but ">= max" is a stronger guarantee in case bugs creep in later. Additionally, since Stringifier::appendStringifiedValue() can call Stringifier::Holder::appendNextProperty(), and Stringifier::Holder::appendNextProperty() can call Stringifier::appendStringifiedValue(), we have the makings of true native stack recursion. Though I don't think your tests will take this path of recursion (and I didn't work on it enough to figure out to get there), we should add a real stack recursion check. Let's add the following to the top of Stringifier::appendStringifiedValue() after the declaration of the ThrowScope: if (UNLIKELY(!vm.isSafeToRecurseSoft())) { throwStackOverflowError(m_globalObject, scope); return StringifyFailed; } Would be nice if you can figure out a test for this overflow too, but I won't insist on that. If you do add just a test, I recommend that at the top of the test JS file, insert the following line: //@ requireOptions("--maxPerThreadStackUsage=204800") That will allow the test to run with a smaller stack, and cause vm.isSafeToRecurseSoft() to return false sooner. In this example, I specified a stack size of 200 KB. Please adjust it as needed to allow your test to run (in case it's too small or too big).
Created attachment 400903 [details] Patch Rename var, use >=, add isSafeToRecurseSoft() check, and add 2 test cases.
Comment on attachment 400903 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=400903&action=review > Source/JavaScriptCore/runtime/JSONObject.cpp:652 > + if (UNLIKELY(markedStack.size() >= maximumHolderStackRecursion)) The "maximumHolderStackRecursion" name doesn't work here since there's no holderStack in this function. If you want to use this same symbol for both cases, how about renaming it to something like "maximumSideStackRecursion"?
(In reply to Ross Kirsling from comment #12) > Comment on attachment 397192 [details] > Patch > > LGTM, but is there no test262 coverage for this? Please see https://github.com/tc39/test262/pull/2517. (In reply to Mark Lam from comment #19) > Comment on attachment 397192 [details] > Patch Thank you for thorough investigation, Mark. > Would be nice if you can figure out a test for this overflow too, but I > won't insist on that. I took some time to fiddle with various inputs and am quite positive that !vm.isSafeToRecurseSoft() check never passes: Stringifier was carefully designed to prevent its methods from recursing. The check will be useful in case of refactoring though.
Created attachment 400928 [details] Patch Rename var to `maximumSideStackRecursion` and fix test.
(In reply to Alexey Shvayka from comment #22) > (In reply to Ross Kirsling from comment #12) > > Comment on attachment 397192 [details] > > Patch > > > > LGTM, but is there no test262 coverage for this? > > Please see https://github.com/tc39/test262/pull/2517. > > (In reply to Mark Lam from comment #19) > > Comment on attachment 397192 [details] > > Patch > > Thank you for thorough investigation, Mark. > > > Would be nice if you can figure out a test for this overflow too, but I > > won't insist on that. > > I took some time to fiddle with various inputs and am quite positive that > !vm.isSafeToRecurseSoft() check never passes: > Stringifier was carefully designed to prevent its methods from recursing. > The check will be useful in case of refactoring though. I can believe that though I can't say it with confidence since I don't understand yet how it achieves this. Best practices for something like this would be to explain in the ChangeLog how the mechanism works to guarantee this, and then add an ASSERT or RELEASE_ASSERT on vm.isSafeToRecurseSoft() to document and enforce that guarantee in case someone breaks the mechanism with some edit in the future. In terms of performance cost, the check you've added costs the same as the check for the assertion (unless we go with a debug ASSERT). One alternative you can do is keep the runtime check in case of bugs, and add a debug ASSERT(vm.isSafeToRecurseSoft()) before it so that if the mechanism breaks, our testing might catch it. Probably needs a brief comment there to document that the runtime check is a conservative fail safe backup in case the mechanism that enforces no runaway recursion breaks.
Created attachment 401028 [details] Patch Add ASSERT and explanation on recursion.
Committed r262727: <https://trac.webkit.org/changeset/262727> All reviewed patches have been landed. Closing bug and clearing flags on attachment 401028 [details].