1 // Copyright 2009 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_REGEXP_REGEXP_STACK_H_ 6 #define V8_REGEXP_REGEXP_STACK_H_ 7 8 #include "src/base/logging.h" 9 #include "src/base/macros.h" 10 #include "src/common/globals.h" 11 12 namespace v8 { 13 namespace internal { 14 15 class RegExpStack; 16 17 // Maintains a per-v8thread stack area that can be used by irregexp 18 // implementation for its backtracking stack. 19 class V8_NODISCARD RegExpStackScope final { 20 public: 21 // Create and delete an instance to control the life-time of a growing stack. 22 23 // Initializes the stack memory area if necessary. 24 explicit RegExpStackScope(Isolate* isolate); 25 ~RegExpStackScope(); // Releases the stack if it has grown. 26 RegExpStackScope(const RegExpStackScope&) = delete; 27 RegExpStackScope& operator=(const RegExpStackScope&) = delete; 28 stack()29 RegExpStack* stack() const { return regexp_stack_; } 30 31 private: 32 RegExpStack* const regexp_stack_; 33 const ptrdiff_t old_sp_top_delta_; 34 }; 35 36 class RegExpStack final { 37 public: 38 RegExpStack(); 39 ~RegExpStack(); 40 RegExpStack(const RegExpStack&) = delete; 41 RegExpStack& operator=(const RegExpStack&) = delete; 42 43 // Number of allocated locations on the stack below the limit. No sequence of 44 // pushes must be longer than this without doing a stack-limit check. 45 static constexpr int kStackLimitSlack = 32; 46 memory_top()47 Address memory_top() const { 48 DCHECK_NE(0, thread_local_.memory_size_); 49 DCHECK_EQ(thread_local_.memory_top_, 50 thread_local_.memory_ + thread_local_.memory_size_); 51 return reinterpret_cast<Address>(thread_local_.memory_top_); 52 } 53 stack_pointer()54 Address stack_pointer() const { 55 return reinterpret_cast<Address>(thread_local_.stack_pointer_); 56 } 57 memory_size()58 size_t memory_size() const { return thread_local_.memory_size_; } 59 60 // If the stack pointer gets below the limit, we should react and 61 // either grow the stack or report an out-of-stack exception. 62 // There is only a limited number of locations below the stack limit, 63 // so users of the stack should check the stack limit during any 64 // sequence of pushes longer that this. limit_address_address()65 Address* limit_address_address() { return &thread_local_.limit_; } 66 67 // Ensures that there is a memory area with at least the specified size. 68 // If passing zero, the default/minimum size buffer is allocated. 69 Address EnsureCapacity(size_t size); 70 71 // Thread local archiving. ArchiveSpacePerThread()72 static constexpr int ArchiveSpacePerThread() { 73 return static_cast<int>(kThreadLocalSize); 74 } 75 char* ArchiveStack(char* to); 76 char* RestoreStack(char* from); FreeThreadResources()77 void FreeThreadResources() { thread_local_.ResetToStaticStack(this); } 78 79 // Maximal size of allocated stack area. 80 static constexpr size_t kMaximumStackSize = 64 * MB; 81 82 private: 83 // Artificial limit used when the thread-local state has been destroyed. 84 static const Address kMemoryTop = 85 static_cast<Address>(static_cast<uintptr_t>(-1)); 86 87 // Minimal size of dynamically-allocated stack area. 88 static constexpr size_t kMinimumDynamicStackSize = 1 * KB; 89 90 // In addition to dynamically-allocated, variable-sized stacks, we also have 91 // a statically allocated and sized area that is used whenever no dynamic 92 // stack is allocated. This guarantees that a stack is always available and 93 // we can skip availability-checks later on. 94 // It's double the slack size to ensure that we have a bit of breathing room 95 // before NativeRegExpMacroAssembler::GrowStack must be called. 96 static constexpr size_t kStaticStackSize = 97 2 * kStackLimitSlack * kSystemPointerSize; 98 byte static_stack_[kStaticStackSize] = {0}; 99 100 STATIC_ASSERT(kStaticStackSize <= kMaximumStackSize); 101 102 // Structure holding the allocated memory, size and limit. Thread switching 103 // archives and restores this struct. 104 struct ThreadLocal { ThreadLocalThreadLocal105 explicit ThreadLocal(RegExpStack* regexp_stack) { 106 ResetToStaticStack(regexp_stack); 107 } 108 109 // If memory_size_ > 0 then 110 // - memory_, memory_top_, stack_pointer_ must be non-nullptr 111 // - memory_top_ = memory_ + memory_size_ 112 // - memory_ <= stack_pointer_ <= memory_top_ 113 byte* memory_ = nullptr; 114 byte* memory_top_ = nullptr; 115 size_t memory_size_ = 0; 116 byte* stack_pointer_ = nullptr; 117 Address limit_ = kNullAddress; 118 bool owns_memory_ = false; // Whether memory_ is owned and must be freed. 119 120 void ResetToStaticStack(RegExpStack* regexp_stack); ResetToStaticStackIfEmptyThreadLocal121 void ResetToStaticStackIfEmpty(RegExpStack* regexp_stack) { 122 if (stack_pointer_ == memory_top_) ResetToStaticStack(regexp_stack); 123 } 124 void FreeAndInvalidate(); 125 }; 126 static constexpr size_t kThreadLocalSize = sizeof(ThreadLocal); 127 memory_top_address_address()128 Address memory_top_address_address() { 129 return reinterpret_cast<Address>(&thread_local_.memory_top_); 130 } 131 stack_pointer_address()132 Address stack_pointer_address() { 133 return reinterpret_cast<Address>(&thread_local_.stack_pointer_); 134 } 135 136 // A position-independent representation of the stack pointer. sp_top_delta()137 ptrdiff_t sp_top_delta() const { 138 ptrdiff_t result = 139 reinterpret_cast<intptr_t>(thread_local_.stack_pointer_) - 140 reinterpret_cast<intptr_t>(thread_local_.memory_top_); 141 DCHECK_LE(result, 0); 142 return result; 143 } 144 145 // Resets the buffer if it has grown beyond the default/minimum size and is 146 // empty. ResetIfEmpty()147 void ResetIfEmpty() { thread_local_.ResetToStaticStackIfEmpty(this); } 148 149 // Whether the ThreadLocal storage has been invalidated. IsValid()150 bool IsValid() const { return thread_local_.memory_ != nullptr; } 151 152 ThreadLocal thread_local_; 153 154 friend class ExternalReference; 155 friend class RegExpStackScope; 156 }; 157 158 } // namespace internal 159 } // namespace v8 160 161 #endif // V8_REGEXP_REGEXP_STACK_H_ 162