1. 14 Oct, 2020 1 commit
    • Martin Bidlingmaier's avatar
      [regexp] Use experimental engine if backtrack limit exceeded · d4febb6b
      Martin Bidlingmaier authored
      We fall back from irregexp to the experimental engine if a backtrack
      limit is exceeded and the experimental engine can handle the regexp.
      The feature can be turned on with a boolean flag, and an uint-valued
      flag controls the default backtrack limit.  For regexps that are
      constructed with an explicit backtrack limit (API,
      %NewRegExpWithBacktrackLimit), we choose the lower of the explicit and
      default backtrack limits.
      The default backtrack limit does not apply to regexps that can't be
      handled by the experimental engine, and for such regexps an explicitly
      specified backtrack limit is handled as before by returning null if we
      exceed it.
      
      Cq-Include-Trybots: luci.v8.try:v8_linux64_fyi_rel_ng
      Bug: v8:10765
      Change-Id: I580df79bd847520985b6c2c2159bc427315c89d1
      Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2436341
      Commit-Queue: Martin Bidlingmaier <mbid@google.com>
      Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
      Cr-Commit-Position: refs/heads/master@{#70500}
      d4febb6b
  2. 16 Sep, 2020 1 commit
    • Martin Bidlingmaier's avatar
      [regexp] Support capture groups in experimental engine · 98b8ca89
      Martin Bidlingmaier authored
      This commit adds support for capture groups (as in e.g. /x(123|abc)y/)
      in the experimental regexp engine.  Now every InterpreterThread owns a
      register array containing (sub)match boundaries. There is a new
      instruction to record the current input index in some register.
      
      Submatches in quantifier bodies should be reported only if they occur
      during the last repetition.  Thus we reset those registers before
      attempting to match the body of a quantifier.  This is implemented with
      another new instruction.
      
      Because of concerns for the growing sizeof the NfaInterpreter object
      (which is allocated on the stack), this commit replaces the
      `SmallVector` members of the NfaInterpreter with zone-allocated arrays.
      Register arrays, which for a fixed regexp are all the same size, are
      allocated with a RecyclingZoneAllocator for cheap memory reclamation via
      a linked list of equally-sized free blocks.
      
      Possible optimizations for management of register array memory:
      1. If there are few register per thread, then it is likely faster to
         store them inline in the InterpreterThread struct.
      2. re2 implements copy-on-write:  InterpreterThreads can share the same
         register array. If a thread attempts to write to shared register
         array, the register array is cloned first.
      3. The register at index 1 contains the end of the match; this is only
         written to right before an ACCEPT statement.  We could make ACCEPT
         equivalent to what's currently CAPTURE 1 followed by ACCEPT.  We
         could then save the memory for register 1 for threads that haven't
         finished yet.  This is particularly interesting if now optimization 1
         kicks in.
      
      Cq-Include-Trybots: luci.v8.try:v8_linux64_fyi_rel_ng
      Bug: v8:10765
      Change-Id: I2c0503206ce331e13ac9912945bb66736d740197
      Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2390770
      Commit-Queue: Martin Bidlingmaier <mbid@google.com>
      Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
      Cr-Commit-Position: refs/heads/master@{#69929}
      98b8ca89
  3. 21 Oct, 2019 2 commits
    • Jakob Gruber's avatar
      [regexp] Apply the backtrack limit in jitted code · 0089006f
      Jakob Gruber authored
      .. similar to how it is applied in the interpreter. We reserve a stack
      slot for the backtrack count, increment it on each backtrack, and fail
      if the limit is hit.
      
      Bug: v8:9695
      Change-Id: I835888c612d6c8bfa2f34e73ab8c8241dcabc6ed
      Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1864938Reviewed-by: 's avatarPeter Marshall <petermarshall@chromium.org>
      Commit-Queue: Jakob Gruber <jgruber@chromium.org>
      Cr-Commit-Position: refs/heads/master@{#64426}
      0089006f
    • Jakob Gruber's avatar
      [regexp] Add a backtracking limit in the interpreter · 48756fcf
      Jakob Gruber authored
      V8 uses a backtracking regexp engine, which has the caveat that some
      regexp patterns can have exponential runtime behavior when excessive
      backtracking is involved.
      
      Especially when regexp patterns are user-controlled, it would be useful
      to be able to set an upper limit for a single regexp execution. This CL
      takes an initial step in that direction by adding a backtracking limit
      (intended to approximate execution time):
      
      - The limit is stored in the JSRegExp's data array.
      - A limit can currently only be set through the %NewRegExpWithLimit
      runtime function.
      - The limit is applied during interpreter execution. When exceeded, the
      interpreter stops execution and returns FAILURE (even if continued
      execution would at some later point have resulted in SUCCESS).
      
      In follow-up CLs, this mechanism will be extended to work in jitted
      regexp code, and exposed through the V8 API.
      
      Bug: v8:9695
      Change-Id: Iadb5c100052f4a63b26f1ec49cf97c6713a66b9b
      Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/1864934
      Commit-Queue: Ulan Degenbaev <ulan@chromium.org>
      Auto-Submit: Jakob Gruber <jgruber@chromium.org>
      Reviewed-by: 's avatarUlan Degenbaev <ulan@chromium.org>
      Reviewed-by: 's avatarPeter Marshall <petermarshall@chromium.org>
      Cr-Commit-Position: refs/heads/master@{#64417}
      48756fcf