1  /*
  2   * Copyright (C) 2011-2019 Apple Inc. All rights reserved.
  3   *
  4   * Redistribution and use in source and binary forms, with or without
  5   * modification, are permitted provided that the following conditions
  6   * are met:
  7   * 1. Redistributions of source code must retain the above copyright
  8   *    notice, this list of conditions and the following disclaimer.
  9   * 2. Redistributions in binary form must reproduce the above copyright
 10   *    notice, this list of conditions and the following disclaimer in the
 11   *    documentation and/or other materials provided with the distribution.
 12   *
 13   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 14   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 15   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 16   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 17   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 18   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 19   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 20   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 21   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 22   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 23   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 24   */
 25  
 26  #pragma once
 27  
 28  #include "BytecodeIndex.h"
 29  
 30  #include <limits.h>
 31  #include <wtf/HashMap.h>
 32  #include <wtf/PrintStream.h>
 33  #include <wtf/StdLibExtras.h>
 34  #include <wtf/Vector.h>
 35  
 36  namespace JSC {
 37  
 38  class CodeBlock;
 39  struct DumpContext;
 40  struct InlineCallFrame;
 41  
 42  class CodeOrigin {
 43  public:
 44      CodeOrigin()
 45  #if CPU(ADDRESS64)
 46          : m_compositeValue(buildCompositeValue(nullptr, BytecodeIndex()))
 47  #else
 48          : m_inlineCallFrame(nullptr)
 49  #endif
 50      {
 51      }
 52  
 53      CodeOrigin(WTF::HashTableDeletedValueType)
 54  #if CPU(ADDRESS64)
 55          : m_compositeValue(buildCompositeValue(deletedMarker(), BytecodeIndex()))
 56  #else
 57          : m_bytecodeIndex(WTF::HashTableDeletedValue)
 58          , m_inlineCallFrame(deletedMarker())
 59  #endif
 60      {
 61      }
 62      
 63      explicit CodeOrigin(BytecodeIndex bytecodeIndex, InlineCallFrame* inlineCallFrame = nullptr)
 64  #if CPU(ADDRESS64)
 65          : m_compositeValue(buildCompositeValue(inlineCallFrame, bytecodeIndex))
 66  #else
 67          : m_bytecodeIndex(bytecodeIndex)
 68          , m_inlineCallFrame(inlineCallFrame)
 69  #endif
 70      {
 71          ASSERT(!!bytecodeIndex);
 72  #if CPU(ADDRESS64)
 73          ASSERT(!(bitwise_cast<uintptr_t>(inlineCallFrame) & ~s_maskCompositeValueForPointer));
 74  #endif
 75      }
 76      
 77  #if CPU(ADDRESS64)
 78      CodeOrigin& operator=(const CodeOrigin& other)
 79      {
 80          if (this != &other) {
 81              if (UNLIKELY(isOutOfLine()))
 82                  delete outOfLineCodeOrigin();
 83              
 84              if (UNLIKELY(other.isOutOfLine()))
 85                  m_compositeValue = buildCompositeValue(other.inlineCallFrame(), other.bytecodeIndex());
 86              else
 87                  m_compositeValue = other.m_compositeValue;
 88          }
 89          return *this;
 90      }
 91      CodeOrigin& operator=(CodeOrigin&& other)
 92      {
 93          if (this != &other) {
 94              if (UNLIKELY(isOutOfLine()))
 95                  delete outOfLineCodeOrigin();
 96  
 97              m_compositeValue = std::exchange(other.m_compositeValue, 0);
 98          }
 99          return *this;
100      }
101  
102      CodeOrigin(const CodeOrigin& other)
103      {
104          // We don't use the member initializer list because it would not let us optimize the common case where there is no out-of-line storage
105          // (in which case we don't have to extract the components of the composite value just to reassemble it).
106          if (UNLIKELY(other.isOutOfLine()))
107              m_compositeValue = buildCompositeValue(other.inlineCallFrame(), other.bytecodeIndex());
108          else
109              m_compositeValue = other.m_compositeValue;
110      }
111      CodeOrigin(CodeOrigin&& other)
112          : m_compositeValue(std::exchange(other.m_compositeValue, 0))
113      {
114      }
115  
116      ~CodeOrigin()
117      {
118          if (UNLIKELY(isOutOfLine()))
119              delete outOfLineCodeOrigin();
120      }
121  #endif
122      
123      bool isSet() const
124      {
125  #if CPU(ADDRESS64)
126          return !(m_compositeValue & s_maskIsBytecodeIndexInvalid);
127  #else
128          return !!m_bytecodeIndex;
129  #endif
130      }
131      explicit operator bool() const { return isSet(); }
132      
133      bool isHashTableDeletedValue() const
134      {
135  #if CPU(ADDRESS64)
136          return !isSet() && (m_compositeValue & s_maskCompositeValueForPointer);
137  #else
138          return m_bytecodeIndex.isHashTableDeletedValue() && !!m_inlineCallFrame;
139  #endif
140      }
141      
142      // The inline depth is the depth of the inline stack, so 1 = not inlined,
143      // 2 = inlined one deep, etc.
144      unsigned inlineDepth() const;
145      
146      // If the code origin corresponds to inlined code, gives you the heap object that
147      // would have owned the code if it had not been inlined. Otherwise returns 0.
148      CodeBlock* codeOriginOwner() const;
149      
150      int stackOffset() const;
151      
152      unsigned hash() const;
153      bool operator==(const CodeOrigin& other) const;
154      bool operator!=(const CodeOrigin& other) const { return !(*this == other); }
155      
156      // This checks if the two code origins correspond to the same stack trace snippets,
157      // but ignore whether the InlineCallFrame's are identical.
158      bool isApproximatelyEqualTo(const CodeOrigin& other, InlineCallFrame* terminal = nullptr) const;
159      
160      unsigned approximateHash(InlineCallFrame* terminal = nullptr) const;
161  
162      template <typename Function>
163      void walkUpInlineStack(const Function&) const;
164  
165      inline bool inlineStackContainsActiveCheckpoint() const;
166      
167      // Get the inline stack. This is slow, and is intended for debugging only.
168      Vector<CodeOrigin> inlineStack() const;
169      
170      JS_EXPORT_PRIVATE void dump(PrintStream&) const;
171      void dumpInContext(PrintStream&, DumpContext*) const;
172  
173      BytecodeIndex bytecodeIndex() const
174      {
175  #if CPU(ADDRESS64)
176          if (!isSet())
177              return BytecodeIndex();
178          if (UNLIKELY(isOutOfLine()))
179              return outOfLineCodeOrigin()->bytecodeIndex;
180          return BytecodeIndex::fromBits(m_compositeValue >> (64 - s_freeBitsAtTop));
181  #else
182          return m_bytecodeIndex;
183  #endif
184      }
185  
186      InlineCallFrame* inlineCallFrame() const
187      {
188  #if CPU(ADDRESS64)
189          if (UNLIKELY(isOutOfLine()))
190              return outOfLineCodeOrigin()->inlineCallFrame;
191          return bitwise_cast<InlineCallFrame*>(m_compositeValue & s_maskCompositeValueForPointer);
192  #else
193          return m_inlineCallFrame;
194  #endif
195      }
196  
197  private:
198  #if CPU(ADDRESS64)
199      static constexpr uintptr_t s_maskIsOutOfLine = 1;
200      static constexpr uintptr_t s_maskIsBytecodeIndexInvalid = 2;
201  
202      struct OutOfLineCodeOrigin {
203          WTF_MAKE_FAST_ALLOCATED;
204      public:
205          InlineCallFrame* inlineCallFrame;
206          BytecodeIndex bytecodeIndex;
207          
208          OutOfLineCodeOrigin(InlineCallFrame* inlineCallFrame, BytecodeIndex bytecodeIndex)
209              : inlineCallFrame(inlineCallFrame)
210              , bytecodeIndex(bytecodeIndex)
211          {
212          }
213      };
214      
215      bool isOutOfLine() const
216      {
217          return m_compositeValue & s_maskIsOutOfLine;
218      }
219      OutOfLineCodeOrigin* outOfLineCodeOrigin() const
220      {
221          ASSERT(isOutOfLine());
222          return bitwise_cast<OutOfLineCodeOrigin*>(m_compositeValue & s_maskCompositeValueForPointer);
223      }
224  #endif
225  
226      static InlineCallFrame* deletedMarker()
227      {
228          auto value = static_cast<uintptr_t>(1 << 3);
229  #if CPU(ADDRESS64)
230          ASSERT(value & s_maskCompositeValueForPointer);
231          ASSERT(!(value & ~s_maskCompositeValueForPointer));
232  #endif
233          return bitwise_cast<InlineCallFrame*>(value);
234      }
235  
236  #if CPU(ADDRESS64)
237      static constexpr unsigned s_freeBitsAtTop = 64 - OS_CONSTANT(EFFECTIVE_ADDRESS_WIDTH);
238      static constexpr uintptr_t s_maskCompositeValueForPointer = ((1ULL << OS_CONSTANT(EFFECTIVE_ADDRESS_WIDTH)) - 1) & ~(8ULL - 1);
239      static uintptr_t buildCompositeValue(InlineCallFrame* inlineCallFrame, BytecodeIndex bytecodeIndex)
240      {
241          if (!bytecodeIndex)
242              return bitwise_cast<uintptr_t>(inlineCallFrame) | s_maskIsBytecodeIndexInvalid;
243  
244          if (UNLIKELY(bytecodeIndex.asBits() >= 1 << s_freeBitsAtTop)) {
245              auto* outOfLine = new OutOfLineCodeOrigin(inlineCallFrame, bytecodeIndex);
246              return bitwise_cast<uintptr_t>(outOfLine) | s_maskIsOutOfLine;
247          }
248  
249          uintptr_t encodedBytecodeIndex = static_cast<uintptr_t>(bytecodeIndex.asBits()) << (64 - s_freeBitsAtTop);
250          ASSERT(!(encodedBytecodeIndex & bitwise_cast<uintptr_t>(inlineCallFrame)));
251          return encodedBytecodeIndex | bitwise_cast<uintptr_t>(inlineCallFrame);
252      }
253  
254      // The bottom bit indicates whether to look at an out-of-line implementation (because of a bytecode index which is too big for us to store).
255      // The next bit indicates whether this is an invalid bytecode (which depending on the InlineCallFrame* can either indicate an unset CodeOrigin,
256      // or a deletion marker for a hash table).
257      // The next bit is free
258      // The next 64-s_freeBitsAtTop-3 are the InlineCallFrame* or the OutOfLineCodeOrigin*
259      // Finally the last s_freeBitsAtTop are the bytecodeIndex if it is inline
260      uintptr_t m_compositeValue;
261  #else
262      BytecodeIndex m_bytecodeIndex;
263      InlineCallFrame* m_inlineCallFrame;
264  #endif
265  };
266  
267  inline unsigned CodeOrigin::hash() const
268  {
269      return WTF::IntHash<unsigned>::hash(bytecodeIndex().asBits()) +
270          WTF::PtrHash<InlineCallFrame*>::hash(inlineCallFrame());
271  }
272  
273  inline bool CodeOrigin::operator==(const CodeOrigin& other) const
274  {
275  #if CPU(ADDRESS64)
276      if (m_compositeValue == other.m_compositeValue)
277          return true;
278  #endif
279      return bytecodeIndex() == other.bytecodeIndex()
280          && inlineCallFrame() == other.inlineCallFrame();
281  }
282  
283  struct CodeOriginHash {
284      static unsigned hash(const CodeOrigin& key) { return key.hash(); }
285      static bool equal(const CodeOrigin& a, const CodeOrigin& b) { return a == b; }
286      static constexpr bool safeToCompareToEmptyOrDeleted = true;
287  };
288  
289  struct CodeOriginApproximateHash {
290      static unsigned hash(const CodeOrigin& key) { return key.approximateHash(); }
291      static bool equal(const CodeOrigin& a, const CodeOrigin& b) { return a.isApproximatelyEqualTo(b); }
292      static constexpr bool safeToCompareToEmptyOrDeleted = true;
293  };
294  
295  } // namespace JSC
296  
297  namespace WTF {
298  
299  template<typename T> struct DefaultHash;
300  template<> struct DefaultHash<JSC::CodeOrigin> : JSC::CodeOriginHash { };
301  
302  template<typename T> struct HashTraits;
303  template<> struct HashTraits<JSC::CodeOrigin> : SimpleClassHashTraits<JSC::CodeOrigin> {
304      static constexpr bool emptyValueIsZero = false;
305  };
306  
307  } // namespace WTF