heap/MarkStack.cpp

   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 #include "config.h"
  27 #include "MarkStack.h"
  28
  29 #include "ConservativeRoots.h"
  30 #include "Heap.h"
  31 #include "JSArray.h"
  32 #include "JSCell.h"
  33 #include "JSObject.h"
  34 #include "ScopeChain.h"
  35 #include "Structure.h"
  36
  37 namespace JSC {
  38
  39 size_t MarkStack::s_pageSize = 0;
  40
  41 void MarkStack::reset()
  42 {
  43     ASSERT(s_pageSize);
  44     m_values.shrinkAllocation(s_pageSize);
  45     m_markSets.shrinkAllocation(s_pageSize);
  46     m_opaqueRoots.clear();
  47 }
  48
  49 void MarkStack::append(ConservativeRoots& conservativeRoots)
  50 {
  51     JSCell** roots = conservativeRoots.roots();
  52     size_t size = conservativeRoots.size();
  53     for (size_t i = 0; i < size; ++i)
  54         internalAppend(roots[i]);
  55 }
  56
  57 inline void MarkStack::visitChildren(JSCell* cell)
  58 {
  59     ASSERT(Heap::isMarked(cell));
  60     if (cell->structure()->typeInfo().type() < CompoundType) {
  61         cell->JSCell::visitChildren(*this);
  62         return;
  63     }
  64
  65     if (!cell->structure()->typeInfo().overridesVisitChildren()) {
  66         ASSERT(cell->isObject());
  67 #ifdef NDEBUG
  68         asObject(cell)->visitChildrenDirect(*this);
  69 #else
  70         ASSERT(!m_isCheckingForDefaultMarkViolation);
  71         m_isCheckingForDefaultMarkViolation = true;
  72         cell->visitChildren(*this);
  73         ASSERT(m_isCheckingForDefaultMarkViolation);
  74         m_isCheckingForDefaultMarkViolation = false;
  75 #endif
  76         return;
  77     }
  78     if (cell->vptr() == m_jsArrayVPtr) {
  79         asArray(cell)->visitChildrenDirect(*this);
  80         return;
  81     }
  82     cell->visitChildren(*this);
  83 }
  84
  85 void MarkStack::drain()
  86 {
  87 #if !ASSERT_DISABLED
  88     ASSERT(!m_isDraining);
  89     m_isDraining = true;
  90 #endif
  91     while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
  92         while (!m_markSets.isEmpty() && m_values.size() < 50) {
  93             ASSERT(!m_markSets.isEmpty());
  94             MarkSet& current = m_markSets.last();
  95             ASSERT(current.m_values);
  96             JSValue* end = current.m_end;
  97             ASSERT(current.m_values);
  98             ASSERT(current.m_values != end);
  99         findNextUnmarkedNullValue:
 100             ASSERT(current.m_values != end);
 101             JSValue value = *current.m_values;
 102             current.m_values++;
 103
 104             JSCell* cell;
 105             if (!value || !value.isCell() || Heap::testAndSetMarked(cell = value.asCell())) {
 106                 if (current.m_values == end) {
 107                     m_markSets.removeLast();
 108                     continue;
 109                 }
 110                 goto findNextUnmarkedNullValue;
 111             }
 112
 113             if (cell->structure()->typeInfo().type() < CompoundType) {
 114                 cell->JSCell::visitChildren(*this);
 115                 if (current.m_values == end) {
 116                     m_markSets.removeLast();
 117                     continue;
 118                 }
 119                 goto findNextUnmarkedNullValue;
 120             }
 121
 122             if (current.m_values == end)
 123                 m_markSets.removeLast();
 124
 125             visitChildren(cell);
 126         }
 127         while (!m_values.isEmpty())
 128             visitChildren(m_values.removeLast());
 129     }
 130 #if !ASSERT_DISABLED
 131     m_isDraining = false;
 132 #endif
 133 }
 134
 135 #if ENABLE(GC_VALIDATION)
 136 void MarkStack::validateSet(JSValue* values, size_t count)
 137 {
 138     for (size_t i = 0; i < count; i++) {
 139         if (values[i])
 140             validateValue(values[i]);
 141     }
 142 }
 143
 144 void MarkStack::validateValue(JSValue value)
 145 {
 146     if (!value)
 147         CRASH();
 148     if (!value.isCell())
 149         return;
 150     JSCell* cell = value.asCell();
 151     if (!cell)
 152         CRASH();
 153
 154     if (!cell->structure())
 155         CRASH();
 156
 157     // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
 158     // I hate this sentence.
 159     if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo())
 160         CRASH();
 161 }
 162 #endif
 163
 164 } // namespace JSC