1 /* 2 * Copyright (C) 2009 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 #ifndef MarkStack_h 27 #define MarkStack_h 28 29 #include "JSValue.h" 30 31 #include <wtf/Noncopyable.h> 32 33 namespace JSC { 34 class Register; 35 36 enum MarkSetProperties { MayContainNullValues, NoNullValues }; 37 38 class MarkStack : Noncopyable { 39 public: MarkStack()40 MarkStack() 41 : m_markSets() 42 , m_values() 43 { 44 } 45 append(JSValue value)46 ALWAYS_INLINE void append(JSValue value) 47 { 48 ASSERT(value); 49 if (value.marked()) 50 return; 51 value.markDirect(); 52 if (value.hasChildren()) 53 m_values.append(value.asCell()); 54 } 55 56 ALWAYS_INLINE void append(JSCell* cell); 57 58 ALWAYS_INLINE void appendValues(Register* values, size_t count, MarkSetProperties properties = NoNullValues) 59 { 60 appendValues(reinterpret_cast<JSValue*>(values), count, properties); 61 } 62 63 ALWAYS_INLINE void appendValues(JSValue* values, size_t count, MarkSetProperties properties = NoNullValues) 64 { 65 if (count) 66 m_markSets.append(MarkSet(values, values + count, properties)); 67 } 68 69 inline void drain(); 70 void compact(); 71 ~MarkStack()72 ~MarkStack() 73 { 74 ASSERT(m_markSets.isEmpty()); 75 ASSERT(m_values.isEmpty()); 76 } 77 78 private: 79 struct MarkSet { MarkSetMarkSet80 MarkSet(JSValue* values, JSValue* end, MarkSetProperties properties) 81 : m_values(values) 82 , m_end(end) 83 , m_properties(properties) 84 { 85 } 86 JSValue* m_values; 87 JSValue* m_end; 88 MarkSetProperties m_properties; 89 }; 90 91 static void* allocateStack(size_t size); 92 static void releaseStack(void* addr, size_t size); 93 94 static void initializePagesize(); pageSize()95 static size_t pageSize() 96 { 97 if (!s_pageSize) 98 initializePagesize(); 99 return s_pageSize; 100 } 101 102 template <typename T> struct MarkStackArray { MarkStackArrayMarkStackArray103 MarkStackArray() 104 : m_top(0) 105 , m_allocated(MarkStack::pageSize()) 106 , m_capacity(m_allocated / sizeof(T)) 107 { 108 m_data = reinterpret_cast<T*>(allocateStack(m_allocated)); 109 } 110 ~MarkStackArrayMarkStackArray111 ~MarkStackArray() 112 { 113 releaseStack(m_data, m_allocated); 114 } 115 expandMarkStackArray116 void expand() 117 { 118 size_t oldAllocation = m_allocated; 119 m_allocated *= 2; 120 m_capacity = m_allocated / sizeof(T); 121 void* newData = allocateStack(m_allocated); 122 memcpy(newData, m_data, oldAllocation); 123 releaseStack(m_data, oldAllocation); 124 m_data = reinterpret_cast<T*>(newData); 125 } 126 appendMarkStackArray127 inline void append(const T& v) 128 { 129 if (m_top == m_capacity) 130 expand(); 131 m_data[m_top++] = v; 132 } 133 removeLastMarkStackArray134 inline T removeLast() 135 { 136 ASSERT(m_top); 137 return m_data[--m_top]; 138 } 139 isEmptyMarkStackArray140 inline bool isEmpty() 141 { 142 return m_top == 0; 143 } 144 sizeMarkStackArray145 inline size_t size() { return m_top; } 146 shrinkAllocationMarkStackArray147 inline void shrinkAllocation(size_t size) 148 { 149 ASSERT(size <= m_allocated); 150 ASSERT(0 == (size % MarkStack::pageSize())); 151 if (size == m_allocated) 152 return; 153 releaseStack(reinterpret_cast<char*>(m_data) + size, m_allocated - size); 154 m_allocated = size; 155 m_capacity = m_allocated / sizeof(T); 156 } 157 158 private: 159 size_t m_top; 160 size_t m_allocated; 161 size_t m_capacity; 162 T* m_data; 163 }; 164 165 MarkStackArray<MarkSet> m_markSets; 166 MarkStackArray<JSCell*> m_values; 167 static size_t s_pageSize; 168 }; 169 } 170 171 #endif 172