[webkit-changes] [WebKit/WebKit] 076218: JSON FastStringifier should adapt its buffer capac...

[EWS]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: 0762185035ffd66ed5e546b9dad4e97a22dac591
      https://github.com/WebKit/WebKit/commit/0762185035ffd66ed5e546b9dad4e97a22dac591
  Author: Mark Lam <mark.lam at apple.com>
  Date:   2022-10-31 (Mon, 31 Oct 2022)

  Changed paths:
    A JSTests/stress/json-fast-stringifier-on-cyclic-structure.js
    M Source/JavaScriptCore/runtime/JSONObject.cpp

  Log Message:
  -----------
  JSON FastStringifier should adapt its buffer capacity based on remaining stack capacity.
https://bugs.webkit.org/show_bug.cgi?id=244323
<rdar://problem/99064587>

Reviewed by Darin Adler and Yusuke Suzuki.

FastStringifier relies on remainingCapacity() in m_buffer to limit recursion.

Since it is possible for a JS program to recurse very deep until it is near the bottom of the stack
before calling JSON.stringify(), it is incorrect for FastStringifier to assume that there will always
be enough remaining stack for it to parse and generate sizeof(m_buffer) worth of string.  Instead,
FastStringifier should reduce the amount of useable buffer space based on the amount of remaining
stack capacity available.

In this patch, we do the following:

1. Introduce a m_useableEnd to indicates where in m_buffer we can fill characters up to.
   This is how we reduce the amount of useable buffer space that FastStringifier can use.

2. Adds the computation of m_useableEnd in FastStringifier's constructor based on remaining
   available stack space.

3. Replace remainingCapacity() with hasRemainingCapacity(), which will:
   a. Check m_length + requested size against m_useableEnd.  Returns true if there's sufficient capacity.
   b. Else, call hasRemainingCapacitySlow() to recompute m_useableEnd based on actual unused buffer
      space (if necessary), and recompute the capacity check result in (a).
   Without this dynamic adaption of m_useableEnd based on real remaining stack space, Speedometer 2.1
   shows a regression on iOS where stacks are more shallow where the estimate causes us to bail out of
   FastStringifier too eagerly.

Note: we've also previously tried a different algorithm where we track a m_cursor and m_cursorStart to
manage where we start filling in content in m_buffer (instead of tracking a m_useableEnd).  That
algorithm requires hasRemainingCapacitySlow() to memmove the filled in portion of m_buffer to shift the
content down every time we need to allow for more capacity in m_buffer.  While this algorithm appears to
be performance neutral, we learn that hasRemainingCapacitySlow() is called many times in the course of
normal operations for any reasonably sized stack.  Hence, we're potentially doing a lot more memmoves
with this algorithm.

Since both algorithms are performance neutral, we're going with the one that doesn't need all the memmoves.

* JSTests/stress/json-fast-stringifier-on-cyclic-structure.js: Added.
(catch):
* Source/JavaScriptCore/runtime/JSONObject.cpp:
(JSC::FastStringifier::length const):
(JSC::FastStringifier::useableBufferSize):
(JSC::FastStringifier::FastStringifier):
(JSC::FastStringifier::haveFailure const):
(JSC::FastStringifier::result const):
(JSC::FastStringifier::hasRemainingCapacity):
(JSC::FastStringifier::hasRemainingCapacitySlow):
(JSC::FastStringifier::append):
(JSC::FastStringifier::remainingCapacity const): Deleted.

Canonical link: https://commits.webkit.org/256154@main