heap/MarkStack.h

   1 /*
   2  * Copyright (C) 2009, 2011 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 "HandleTypes.h"
  30 #include "JSValue.h"
  31 #include "Register.h"
  32 #include <wtf/HashSet.h>
  33 #include <wtf/Vector.h>
  34 #include <wtf/Noncopyable.h>
  35 #include <wtf/OSAllocator.h>
  36
  37 namespace JSC {
  38
  39     class ConservativeRoots;
  40     class JSGlobalData;
  41     class Register;
  42     template<typename T> class WriteBarrierBase;
  43     template<typename T> class JITWriteBarrier;
  44
  45     enum MarkSetProperties { MayContainNullValues, NoNullValues };
  46
  47     class MarkStack {
  48         WTF_MAKE_NONCOPYABLE(MarkStack);
  49     public:
  50         MarkStack(void* jsArrayVPtr)
  51             : m_jsArrayVPtr(jsArrayVPtr)
  52             , m_shouldUnlinkCalls(false)
  53 #if !ASSERT_DISABLED
  54             , m_isCheckingForDefaultMarkViolation(false)
  55             , m_isDraining(false)
  56 #endif
  57         {
  58         }
  59
  60         ~MarkStack()
  61         {
  62             ASSERT(m_markSets.isEmpty());
  63             ASSERT(m_values.isEmpty());
  64         }
  65
  66         template<typename T> inline void append(JITWriteBarrier<T>*);
  67         template<typename T> inline void append(WriteBarrierBase<T>*);
  68         inline void appendValues(WriteBarrierBase<Unknown>*, size_t count, MarkSetProperties = NoNullValues);
  69
  70         void append(ConservativeRoots&);
  71
  72         bool addOpaqueRoot(void* root) { return m_opaqueRoots.add(root).second; }
  73         bool containsOpaqueRoot(void* root) { return m_opaqueRoots.contains(root); }
  74         int opaqueRootCount() { return m_opaqueRoots.size(); }
  75
  76         void drain();
  77         void reset();
  78
  79         bool shouldUnlinkCalls() const { return m_shouldUnlinkCalls; }
  80         void setShouldUnlinkCalls(bool shouldUnlinkCalls) { m_shouldUnlinkCalls = shouldUnlinkCalls; }
  81
  82     private:
  83         friend class HeapRootVisitor; // Allowed to mark a JSValue* or JSCell** directly.
  84
  85 #if ENABLE(GC_VALIDATION)
  86         static void validateSet(JSValue*, size_t);
  87         static void validateValue(JSValue);
  88 #endif
  89
  90         void append(JSValue*);
  91         void append(JSValue*, size_t count);
  92         void append(JSCell**);
  93
  94         void internalAppend(JSCell*);
  95         void internalAppend(JSValue);
  96         void visitChildren(JSCell*);
  97
  98         struct MarkSet {
  99             MarkSet(JSValue* values, JSValue* end, MarkSetProperties properties)
 100                 : m_values(values)
 101                 , m_end(end)
 102                 , m_properties(properties)
 103             {
 104                 ASSERT(values);
 105             }
 106             JSValue* m_values;
 107             JSValue* m_end;
 108             MarkSetProperties m_properties;
 109         };
 110
 111         static void* allocateStack(size_t size) { return OSAllocator::reserveAndCommit(size); }
 112         static void releaseStack(void* addr, size_t size) { OSAllocator::decommitAndRelease(addr, size); }
 113
 114         static void initializePagesize();
 115         static size_t pageSize()
 116         {
 117             if (!s_pageSize)
 118                 initializePagesize();
 119             return s_pageSize;
 120         }
 121
 122         template<typename T> struct MarkStackArray {
 123             MarkStackArray()
 124                 : m_top(0)
 125                 , m_allocated(MarkStack::pageSize())
 126                 , m_capacity(m_allocated / sizeof(T))
 127             {
 128                 m_data = reinterpret_cast<T*>(allocateStack(m_allocated));
 129             }
 130
 131             ~MarkStackArray()
 132             {
 133                 releaseStack(m_data, m_allocated);
 134             }
 135
 136             void expand()
 137             {
 138                 size_t oldAllocation = m_allocated;
 139                 m_allocated *= 2;
 140                 m_capacity = m_allocated / sizeof(T);
 141                 void* newData = allocateStack(m_allocated);
 142                 memcpy(newData, m_data, oldAllocation);
 143                 releaseStack(m_data, oldAllocation);
 144                 m_data = reinterpret_cast<T*>(newData);
 145             }
 146
 147             inline void append(const T& v)
 148             {
 149                 if (m_top == m_capacity)
 150                     expand();
 151                 m_data[m_top++] = v;
 152             }
 153
 154             inline T removeLast()
 155             {
 156                 ASSERT(m_top);
 157                 return m_data[--m_top];
 158             }
 159
 160             inline T& last()
 161             {
 162                 ASSERT(m_top);
 163                 return m_data[m_top - 1];
 164             }
 165
 166             inline bool isEmpty()
 167             {
 168                 return m_top == 0;
 169             }
 170
 171             inline size_t size() { return m_top; }
 172
 173             inline void shrinkAllocation(size_t size)
 174             {
 175                 ASSERT(size <= m_allocated);
 176                 ASSERT(0 == (size % MarkStack::pageSize()));
 177                 if (size == m_allocated)
 178                     return;
 179 #if OS(WINDOWS) || OS(SYMBIAN) || PLATFORM(BREWMP)
 180                 // We cannot release a part of a region with VirtualFree.  To get around this,
 181                 // we'll release the entire region and reallocate the size that we want.
 182                 releaseStack(m_data, m_allocated);
 183                 m_data = reinterpret_cast<T*>(allocateStack(size));
 184 #else
 185                 releaseStack(reinterpret_cast<char*>(m_data) + size, m_allocated - size);
 186 #endif
 187                 m_allocated = size;
 188                 m_capacity = m_allocated / sizeof(T);
 189             }
 190
 191         private:
 192             size_t m_top;
 193             size_t m_allocated;
 194             size_t m_capacity;
 195             T* m_data;
 196         };
 197
 198         void* m_jsArrayVPtr;
 199         MarkStackArray<MarkSet> m_markSets;
 200         MarkStackArray<JSCell*> m_values;
 201         static size_t s_pageSize;
 202         HashSet<void*> m_opaqueRoots; // Handle-owning data structures not visible to the garbage collector.
 203         bool m_shouldUnlinkCalls;
 204
 205 #if !ASSERT_DISABLED
 206     public:
 207         bool m_isCheckingForDefaultMarkViolation;
 208         bool m_isDraining;
 209 #endif
 210     };
 211
 212     typedef MarkStack SlotVisitor;
 213
 214     inline void MarkStack::append(JSValue* slot, size_t count)
 215     {
 216         if (!count)
 217             return;
 218 #if ENABLE(GC_VALIDATION)
 219         validateSet(slot, count);
 220 #endif
 221         m_markSets.append(MarkSet(slot, slot + count, NoNullValues));
 222     }
 223
 224     ALWAYS_INLINE void MarkStack::append(JSValue* value)
 225     {
 226         ASSERT(value);
 227         internalAppend(*value);
 228     }
 229
 230     ALWAYS_INLINE void MarkStack::append(JSCell** value)
 231     {
 232         ASSERT(value);
 233         internalAppend(*value);
 234     }
 235
 236     ALWAYS_INLINE void MarkStack::internalAppend(JSValue value)
 237     {
 238         ASSERT(value);
 239 #if ENABLE(GC_VALIDATION)
 240         validateValue(value);
 241 #endif
 242         if (value.isCell())
 243             internalAppend(value.asCell());
 244     }
 245
 246     // Privileged class for marking JSValues directly. It is only safe to use
 247     // this class to mark direct heap roots that are marked during every GC pass.
 248     // All other references should be wrapped in WriteBarriers and marked through
 249     // the MarkStack.
 250     class HeapRootVisitor {
 251     private:
 252         friend class Heap;
 253         HeapRootVisitor(SlotVisitor&);
 254
 255     public:
 256         void mark(JSValue*);
 257         void mark(JSValue*, size_t);
 258         void mark(JSString**);
 259         void mark(JSCell**);
 260
 261         SlotVisitor& visitor();
 262
 263     private:
 264         SlotVisitor& m_visitor;
 265     };
 266
 267     inline HeapRootVisitor::HeapRootVisitor(SlotVisitor& visitor)
 268         : m_visitor(visitor)
 269     {
 270     }
 271
 272     inline void HeapRootVisitor::mark(JSValue* slot)
 273     {
 274         m_visitor.append(slot);
 275     }
 276
 277     inline void HeapRootVisitor::mark(JSValue* slot, size_t count)
 278     {
 279         m_visitor.append(slot, count);
 280     }
 281
 282     inline void HeapRootVisitor::mark(JSString** slot)
 283     {
 284         m_visitor.append(reinterpret_cast<JSCell**>(slot));
 285     }
 286
 287     inline void HeapRootVisitor::mark(JSCell** slot)
 288     {
 289         m_visitor.append(slot);
 290     }
 291
 292     inline SlotVisitor& HeapRootVisitor::visitor()
 293     {
 294         return m_visitor;
 295     }
 296
 297 } // namespace JSC
 298
 299 #endif