MMgc/GCStack.cpp

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine.].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2004-2006
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #include "MMgc.h"
  41
  42 //#define TESTING_MARKSTACK
  43 #define MARKSTACK_ALLOWANCE  1
  44
  45 namespace MMgc
  46 {
  47 #ifdef TESTING_MARKSTACK
  48     static int markstack_allowance = 2*MARKSTACK_ALLOWANCE;     // Two stacks!
  49 #endif
  50
  51     static inline void* AllocStackSegment(bool mustSucceed)
  52     {
  53 #ifdef TESTING_MARKSTACK
  54         if (markstack_allowance == 0)
  55             return NULL;
  56         --markstack_allowance;
  57 #endif
  58         if (mustSucceed)
  59             return GCHeap::GetGCHeap()->Alloc(1, GCHeap::flags_Alloc);
  60         else
  61             return GCHeap::GetGCHeap()->AllocNoOOM(1, GCHeap::flags_Alloc | GCHeap::kCanFail);
  62     }
  63
  64     static inline void FreeStackSegment(void* p)
  65     {
  66 #ifdef TESTING_MARKSTACK
  67         ++markstack_allowance;
  68 #endif
  69         GCHeap::GetGCHeap()->FreeNoOOM(p);
  70     }
  71
  72     GCMarkStack::GCMarkStack()
  73         : m_base(NULL)
  74         , m_top(NULL)
  75         , m_limit(NULL)
  76         , m_topSegment(NULL)
  77         , m_hiddenCount(0)
  78         , m_extraSegment(NULL)
  79 #ifdef MMGC_MARKSTACK_DEPTH
  80         , m_maxDepth(0)
  81 #endif
  82     {
  83         // The value of kMarkStackItems is derived from on a block size of 4096; this
  84         // assert keeps us honest.  Talk to Lars if you get into trouble here.
  85         GCAssert(GCHeap::kBlockSize == 4096);
  86
  87         GCAssert(sizeof(GCMarkStack::GCStackSegment) <= GCHeap::kBlockSize);
  88         PushSegment(true);
  89         GCAssert(Invariants());
  90     }
  91
  92     GCMarkStack::~GCMarkStack()
  93     {
  94         while (m_topSegment != NULL)
  95             PopSegment();
  96         if (m_extraSegment)
  97             FreeStackSegment(m_extraSegment);
  98     }
  99
 100     void GCMarkStack::Clear()
 101     {
 102         // Clear out the elements
 103         while (m_topSegment->m_prev != NULL)
 104             PopSegment();
 105         m_top = m_base;
 106
 107         // Discard the cached segment
 108         if (m_extraSegment != NULL) {
 109             FreeStackSegment(m_extraSegment);
 110             m_extraSegment = NULL;
 111         }
 112         GCAssert(Invariants());
 113     }
 114
 115     bool GCMarkStack::PushSegment(bool mustSucceed)
 116     {
 117         GCAssert(sizeof(GCStackSegment) <= GCHeap::kBlockSize);
 118         GCAssert(m_top == m_limit);
 119         if (m_extraSegment == NULL) {
 120             void *memory = AllocStackSegment(mustSucceed);
 121             if (memory == NULL)
 122                 return false;
 123             m_extraSegment = new (memory) GCStackSegment();
 124         }
 125         if (m_topSegment != NULL)
 126             m_hiddenCount += kMarkStackItems;
 127         GCStackSegment* seg = m_extraSegment;
 128         m_extraSegment = NULL;
 129         seg->m_prev = m_topSegment;
 130         m_topSegment = seg;
 131         m_base = m_topSegment->m_items;
 132         m_limit = m_base + kMarkStackItems;
 133         m_top = m_base;
 134         return true;
 135     }
 136
 137     void GCMarkStack::PopSegment()
 138     {
 139         m_hiddenCount -= kMarkStackItems;
 140         GCStackSegment* seg = m_topSegment;
 141         m_topSegment = seg->m_prev;
 142         m_base = m_topSegment->m_items;
 143         m_limit = m_base + kMarkStackItems;
 144         m_top = m_limit;
 145         if (m_extraSegment == NULL) {
 146             seg->m_prev = NULL;
 147             m_extraSegment = seg;
 148         }
 149         else
 150             FreeStackSegment(seg);
 151     }
 152
 153     bool GCMarkStack::TransferOneFullSegmentFrom(GCMarkStack& other)
 154     {
 155         GCAssert(other.EntirelyFullSegments() > 0);
 156         GCStackSegment* seg;
 157
 158         if (other.m_topSegment->m_prev == NULL) {
 159             // Picking off the only segment
 160             GCAssert(other.m_top == other.m_limit);
 161             seg = other.m_topSegment;
 162             other.m_topSegment = NULL;
 163             other.m_base = NULL;
 164             other.m_top = NULL;
 165             other.m_limit = NULL;
 166             if (!other.PushSegment()) {
 167                 // Oops: couldn't push it, so undo.  We're out of memory but we
 168                 // don't want to signal OOM here, we want to recover, signal failure,
 169                 // and let the caller handle it.
 170                 other.m_topSegment = seg;
 171                 other.m_base = seg->m_items;
 172                 other.m_top = other.m_limit = other.m_base + kMarkStackItems;
 173                 return false;
 174             }
 175         }
 176         else {
 177             // Picking off the one below the top always
 178             seg = other.m_topSegment->m_prev;
 179             other.m_topSegment->m_prev = seg->m_prev;
 180             other.m_hiddenCount -= kMarkStackItems;
 181         }
 182
 183         // Insert it below our top segment
 184         seg->m_prev = m_topSegment->m_prev;
 185         m_topSegment->m_prev = seg;
 186         m_hiddenCount += kMarkStackItems;
 187
 188         // Special case that occurs if a segment was inserted into an empty stack.
 189         if (m_top == m_base)
 190             PopSegment();
 191         GCAssert(Invariants());
 192         GCAssert(other.Invariants());
 193         return true;
 194     }
 195
 196     GCWorkItem *GCMarkStack::GetItemAbove(GCWorkItem *item)
 197     {
 198         if(item == Peek())
 199             return NULL;
 200         GCStackSegment *seg = m_topSegment;
 201         GCStackSegment *last = NULL;
 202         while(seg) {
 203             if(item >= seg->m_items && item < seg->m_items + kMarkStackItems) {
 204                 if(item+1 == seg->m_items + kMarkStackItems) {
 205                     // The two items spanned a segment, above is first item in next
 206                     // segment (or "last" in the backwards traversal sense).
 207                     return &last->m_items[0];
 208                 } else {
 209                     return item+1;
 210                 }
 211             }
 212             last = seg;
 213             seg = seg->m_prev;
 214         }
 215         GCAssertMsg(false, "Invalid attempt to get the item above an item not in the stack.");
 216         return NULL;
 217     }
 218
 219 #ifdef _DEBUG
 220     bool GCMarkStack::Invariants()
 221     {
 222         GCAssert(m_base+kMarkStackItems == m_limit);
 223         GCAssert(m_top >= m_base);
 224         GCAssert(m_top <= m_limit);
 225         GCAssert(m_topSegment->m_prev == NULL || m_top > m_base);
 226         uint32_t hc = 0;
 227         uint32_t ns = 0;
 228         for ( GCStackSegment* seg=m_topSegment->m_prev ; seg != NULL ; seg = seg->m_prev ) {
 229             hc += kMarkStackItems;
 230             ns++;
 231         }
 232         GCAssert(ns == EntirelyFullSegments() || (m_top == m_limit && ns+1 == EntirelyFullSegments()));
 233         GCAssert(hc == m_hiddenCount);
 234         GCAssert(Count() == hc + (m_top - m_base));
 235         return true;
 236     }
 237 #endif
 238 }