summaryrefslogtreecommitdiffstats
path: root/js/src/irregexp/imported/regexp-stack.h
blob: fc8827116bdeaa7b40bde3b2112da73a3141addf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// Copyright 2009 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_REGEXP_REGEXP_STACK_H_
#define V8_REGEXP_REGEXP_STACK_H_

#include "irregexp/RegExpShim.h"

namespace v8 {
namespace internal {

class RegExpStack;

// Maintains a per-v8thread stack area that can be used by irregexp
// implementation for its backtracking stack.
class V8_NODISCARD RegExpStackScope final {
 public:
  // Create and delete an instance to control the life-time of a growing stack.

  // Initializes the stack memory area if necessary.
  explicit RegExpStackScope(Isolate* isolate);
  ~RegExpStackScope();  // Releases the stack if it has grown.
  RegExpStackScope(const RegExpStackScope&) = delete;
  RegExpStackScope& operator=(const RegExpStackScope&) = delete;

  RegExpStack* stack() const { return regexp_stack_; }

 private:
  RegExpStack* const regexp_stack_;
  const ptrdiff_t old_sp_top_delta_;
};

class RegExpStack final {
 public:
  RegExpStack();
  ~RegExpStack();
  RegExpStack(const RegExpStack&) = delete;
  RegExpStack& operator=(const RegExpStack&) = delete;

  // Number of allocated locations on the stack below the limit. No sequence of
  // pushes must be longer than this without doing a stack-limit check.
  static constexpr int kStackLimitSlack = 32;

  Address memory_top() const {
    DCHECK_NE(0, thread_local_.memory_size_);
    DCHECK_EQ(thread_local_.memory_top_,
              thread_local_.memory_ + thread_local_.memory_size_);
    return reinterpret_cast<Address>(thread_local_.memory_top_);
  }

  Address stack_pointer() const {
    return reinterpret_cast<Address>(thread_local_.stack_pointer_);
  }

  size_t memory_size() const { return thread_local_.memory_size_; }

  // If the stack pointer gets below the limit, we should react and
  // either grow the stack or report an out-of-stack exception.
  // There is only a limited number of locations below the stack limit,
  // so users of the stack should check the stack limit during any
  // sequence of pushes longer that this.
  Address* limit_address_address() { return &thread_local_.limit_; }

  // Ensures that there is a memory area with at least the specified size.
  // If passing zero, the default/minimum size buffer is allocated.
  Address EnsureCapacity(size_t size);

  // Thread local archiving.
  static constexpr int ArchiveSpacePerThread() {
    return static_cast<int>(kThreadLocalSize);
  }
  char* ArchiveStack(char* to);
  char* RestoreStack(char* from);
  void FreeThreadResources() { thread_local_.ResetToStaticStack(this); }

  // Maximal size of allocated stack area.
  static constexpr size_t kMaximumStackSize = 64 * MB;

 private:
  // Artificial limit used when the thread-local state has been destroyed.
  static const Address kMemoryTop =
      static_cast<Address>(static_cast<uintptr_t>(-1));

  // Minimal size of dynamically-allocated stack area.
  static constexpr size_t kMinimumDynamicStackSize = 1 * KB;

  // In addition to dynamically-allocated, variable-sized stacks, we also have
  // a statically allocated and sized area that is used whenever no dynamic
  // stack is allocated. This guarantees that a stack is always available and
  // we can skip availability-checks later on.
  // It's double the slack size to ensure that we have a bit of breathing room
  // before NativeRegExpMacroAssembler::GrowStack must be called.
  static constexpr size_t kStaticStackSize =
      2 * kStackLimitSlack * kSystemPointerSize;
  uint8_t static_stack_[kStaticStackSize] = {0};

  static_assert(kStaticStackSize <= kMaximumStackSize);

  // Structure holding the allocated memory, size and limit. Thread switching
  // archives and restores this struct.
  struct ThreadLocal {
    explicit ThreadLocal(RegExpStack* regexp_stack) {
      ResetToStaticStack(regexp_stack);
    }

    // If memory_size_ > 0 then
    //  - memory_, memory_top_, stack_pointer_ must be non-nullptr
    //  - memory_top_ = memory_ + memory_size_
    //  - memory_ <= stack_pointer_ <= memory_top_
    uint8_t* memory_ = nullptr;
    uint8_t* memory_top_ = nullptr;
    size_t memory_size_ = 0;
    uint8_t* stack_pointer_ = nullptr;
    Address limit_ = kNullAddress;
    bool owns_memory_ = false;  // Whether memory_ is owned and must be freed.

    void ResetToStaticStack(RegExpStack* regexp_stack);
    void ResetToStaticStackIfEmpty(RegExpStack* regexp_stack) {
      if (stack_pointer_ == memory_top_) ResetToStaticStack(regexp_stack);
    }
    void FreeAndInvalidate();
  };
  static constexpr size_t kThreadLocalSize = sizeof(ThreadLocal);

  Address memory_top_address_address() {
    return reinterpret_cast<Address>(&thread_local_.memory_top_);
  }

  Address stack_pointer_address() {
    return reinterpret_cast<Address>(&thread_local_.stack_pointer_);
  }

  // A position-independent representation of the stack pointer.
  ptrdiff_t sp_top_delta() const {
    ptrdiff_t result =
        reinterpret_cast<intptr_t>(thread_local_.stack_pointer_) -
        reinterpret_cast<intptr_t>(thread_local_.memory_top_);
    DCHECK_LE(result, 0);
    return result;
  }

  // Resets the buffer if it has grown beyond the default/minimum size and is
  // empty.
  void ResetIfEmpty() { thread_local_.ResetToStaticStackIfEmpty(this); }

  // Whether the ThreadLocal storage has been invalidated.
  bool IsValid() const { return thread_local_.memory_ != nullptr; }

  ThreadLocal thread_local_;

  friend class ExternalReference;
  friend class RegExpStackScope;
};

}  // namespace internal
}  // namespace v8

#endif  // V8_REGEXP_REGEXP_STACK_H_