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-2011
  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 namespace MMgc
  43 {
  44 #ifdef MMGC_MARKSTACK_ALLOWANCE
  45     GCMarkStack::GCMarkStack(int32_t allowance)
  46 #else
  47     GCMarkStack::GCMarkStack()
  48 #endif
  49         : m_base(NULL)
  50         , m_top(NULL)
  51         , m_limit(NULL)
  52         , m_topSegment(NULL)
  53         , m_hiddenCount(0)
  54         , m_hiddenSegments(0)
  55         , m_extraSegment(NULL)
  56         , m_deadItem(0)
  57 #ifdef MMGC_MARKSTACK_ALLOWANCE
  58         , m_allowance(allowance > 0 ? allowance : 2147483647)
  59 #endif
  60 #ifdef MMGC_MARKSTACK_DEPTH
  61         , m_maxDepth(0)
  62 #endif
  63     {
  64         PushSegment(true);
  65         GCAssert(Invariants());
  66     }
  67
  68     GCMarkStack::~GCMarkStack()
  69     {
  70         while (m_topSegment != NULL)
  71             PopSegment();
  72         if (m_extraSegment)
  73             FreeStackSegment(m_extraSegment);
  74     }
  75
  76     void GCMarkStack::SetDeadItem(void* item)
  77     {
  78         GCAssert(item != NULL);
  79         m_deadItem = uintptr_t(item);
  80     }
  81
  82     bool GCMarkStack::Push_LargeExactObjectTail(const void* p, size_t cursor)
  83     {
  84         uintptr_t* top = allocSpace(3);
  85         if (top == NULL)
  86             return false;
  87         top[0] = (kLargeExactObjectTail << 2) | kFirstWord;
  88         top[-1] = uintptr_t(p) | kMiddleWord;
  89         top[-2] = (uintptr_t(cursor) << 2) | kLastWord;
  90         return true;
  91     }
  92
  93     void GCMarkStack::Pop_LargeExactObjectTail(const void* &p, size_t &cursor)
  94     {
  95         GCAssert(PeekTypetag() == kLargeExactObjectTail);
  96
  97         uintptr_t* top = m_top-1;
  98         p = (void*)(top[-1] & ~3);
  99         cursor = size_t(top[-2] & ~3) >> 2;
 100         freeSpace(3);
 101     }
 102
 103     bool GCMarkStack::Push_StackMemory(const void* p, uint32_t size, const void* baseptr)
 104     {
 105         uintptr_t* top = allocSpace(4);
 106         if (top == NULL)
 107             return false;
 108         top[0] = (kStackMemory << 2) | kFirstWord;
 109         top[-1] = uintptr_t(p) | kMiddleWord;
 110         top[-2] = uintptr_t(size) | kMiddleWord;
 111         top[-3] = uintptr_t(baseptr) | kLastWord;
 112         return true;
 113     }
 114
 115     void GCMarkStack::Pop_StackMemory(const void* &p, uint32_t &size, const void* &baseptr)
 116     {
 117         GCAssert(PeekTypetag() == kStackMemory);
 118
 119         uintptr_t* top = m_top-1;
 120         p = (void*)(top[-1] & ~3);
 121         size = uint32_t(top[-2] & ~3);
 122         baseptr = (void*)(top[-3] & ~3);
 123         freeSpace(4);
 124     }
 125
 126     bool GCMarkStack::Push_LargeObjectChunk(const void* p, uint32_t size, const void* baseptr)
 127     {
 128         uintptr_t* top = allocSpace(4);
 129         if (top == NULL)
 130             return false;
 131         top[0] = (kLargeObjectChunk << 2) | kFirstWord;
 132         top[-1] = uintptr_t(p) | kMiddleWord;
 133         top[-2] = uintptr_t(size) | kMiddleWord;
 134         top[-3] = uintptr_t(baseptr) | kLastWord;
 135         return true;
 136     }
 137
 138     void GCMarkStack::Pop_LargeObjectChunk(const void* &p, uint32_t &size, const void* &baseptr)
 139     {
 140         GCAssert(PeekTypetag() == kLargeObjectChunk);
 141
 142         uintptr_t* top = m_top-1;
 143         p = (void*)(top[-1] & ~3);
 144         size = uint32_t(top[-2] & ~3);
 145         baseptr = (void*)(top[-3] & ~3);
 146         freeSpace(4);
 147     }
 148
 149     bool GCMarkStack::Push_LargeRootChunk(const void* p, uint32_t size, const void* baseptr)
 150     {
 151         uintptr_t* top = allocSpace(4);
 152         if (top == NULL)
 153             return false;
 154         top[0] = (kLargeRootChunk << 2) | kFirstWord;
 155         top[-1] = uintptr_t(p) | kMiddleWord;
 156         top[-2] = uintptr_t(size) | kMiddleWord;
 157         top[-3] = uintptr_t(baseptr) | kLastWord;
 158         return true;
 159     }
 160
 161     void GCMarkStack::Pop_LargeRootChunk(const void* &p, uint32_t &size, const void* &baseptr)
 162     {
 163         GCAssert(PeekTypetag() == kLargeRootChunk);
 164
 165         uintptr_t* top = m_top-1;
 166         p = (void*)(top[-1] & ~3);
 167         size = uint32_t(top[-2] & ~3);
 168         baseptr = (void*)(top[-3] & ~3);
 169         freeSpace(4);
 170     }
 171
 172     bool GCMarkStack::Push_LargeObjectProtector(const void* p)
 173     {
 174         uintptr_t* top = allocSpace(2);
 175         if (top == NULL)
 176             return false;
 177         top[0] = (kLargeObjectProtector << 2) | kFirstWord;
 178         top[-1] = uintptr_t(p) | kLastWord;
 179         return true;
 180     }
 181
 182     void GCMarkStack::Pop_LargeObjectProtector(const void* &p)
 183     {
 184         GCAssert(PeekTypetag() == kLargeObjectProtector);
 185
 186         uintptr_t* top = m_top-1;
 187         p = (void*)(top[-1] & ~3);
 188         freeSpace(2);
 189     }
 190
 191     bool GCMarkStack::Push_RootProtector(const void* p)
 192     {
 193         uintptr_t* top = allocSpace(2);
 194         if (top == NULL)
 195             return false;
 196         top[0] = (kRootProtector << 2) | kFirstWord;
 197         top[-1] = uintptr_t(p) | kLastWord;
 198         return true;
 199     }
 200
 201     void GCMarkStack::Pop_RootProtector(const void* &p)
 202     {
 203         GCAssert(PeekTypetag() == kRootProtector);
 204
 205         uintptr_t* top = m_top-1;
 206         p = (void*)(top[-1] & ~3);
 207         freeSpace(2);
 208     }
 209
 210     void GCMarkStack::ClearRootProtectorAndChunkAbove(uintptr_t index, const void* rootptr)
 211     {
 212 #ifdef DEBUG
 213         uintptr_t* top = (uintptr_t*)index;
 214         GCAssert(top[0] == ((kRootProtector << 2) | kFirstWord));
 215         GCAssert((void*)(top[-1] & ~3) == rootptr);
 216 #endif
 217
 218         ClearItemAt(index);
 219
 220         uintptr_t* itemptr = (uintptr_t*)index;
 221         while ((itemptr = GetNextItemAbove(itemptr)) != NULL) {
 222             if (*itemptr == ((kLargeRootChunk << 2) | kFirstWord)) {
 223                 const void* baseptr = (void*)(itemptr[-3] & ~3);
 224                 if (baseptr == rootptr) {
 225                     ClearItemAt((uintptr_t)itemptr);
 226                     return;
 227                 }
 228             }
 229         }
 230     }
 231
 232     void GCMarkStack::Clear()
 233     {
 234         // Clear out the elements
 235         while (m_topSegment->m_prev != NULL)
 236             PopSegment();
 237         m_top = m_base;
 238
 239         // Discard the cached segment
 240         if (m_extraSegment != NULL) {
 241             FreeStackSegment(m_extraSegment);
 242             m_extraSegment = NULL;
 243         }
 244         GCAssert(Invariants());
 245     }
 246
 247     inline uintptr_t* GCMarkStack::items(GCMarkStack::StackSegment* seg)
 248     {
 249         GCAssert(sizeof(StackSegment) % sizeof(uintptr_t) == 0);
 250         return (uintptr_t*)seg + sizeof(StackSegment)/sizeof(uintptr_t);
 251     }
 252
 253     inline uintptr_t* GCMarkStack::limit(GCMarkStack::StackSegment* seg)
 254     {
 255         static const size_t kMarkStackItems = (GCHeap::kBlockSize - sizeof(StackSegment)) / sizeof(uintptr_t);
 256 #ifdef DEBUG
 257         return items(seg) + kMarkStackItems - 2;    // Two sentinel words at the end
 258 #else
 259         return items(seg) + kMarkStackItems;
 260 #endif
 261     }
 262
 263     inline GCMarkStack::StackSegment::StackSegment()
 264     {
 265         m_savedTop = NULL;
 266         m_prev = NULL;
 267 #ifdef DEBUG
 268         sentinel1 = 0;            // catch overwrites
 269         sentinel2 = 0;            //   as soon as they happen
 270         limit(this)[0] = 0;       // also
 271         limit(this)[1] = 0;       //   at the end
 272 #endif
 273     }
 274
 275     bool GCMarkStack::PopulateExtraSegment(bool mustSucceed)
 276     {
 277         if (m_extraSegment == NULL) {
 278             void *memory = AllocStackSegment(mustSucceed);
 279             if (memory == NULL)
 280                 return false;
 281             m_extraSegment = new (memory) StackSegment();
 282         }
 283         return true;
 284     }
 285
 286     bool GCMarkStack::PushSegment(bool mustSucceed)
 287     {
 288         GCAssert(sizeof(StackSegment) <= GCHeap::kBlockSize);
 289         if (!PopulateExtraSegment(mustSucceed))
 290             return false;
 291         if (m_topSegment != NULL) {
 292             m_hiddenSegments++;
 293             m_hiddenCount += uint32_t(m_top - m_base);
 294             m_topSegment->m_savedTop = m_top;
 295         }
 296         StackSegment* seg = m_extraSegment;
 297         m_extraSegment = NULL;
 298         seg->m_prev = m_topSegment;
 299         m_topSegment = seg;
 300         m_base = items(m_topSegment);
 301         m_limit = limit(m_topSegment);
 302         m_top = m_base;
 303         return true;
 304     }
 305
 306     void GCMarkStack::PopSegment_UnlessLast()
 307     {
 308         if (m_topSegment->m_prev != NULL)
 309             PopSegment();
 310     }
 311
 312     void GCMarkStack::PopSegment()
 313     {
 314         StackSegment* seg = m_topSegment;
 315         m_topSegment = seg->m_prev;
 316
 317         if (m_topSegment != NULL) {
 318             m_base = items(m_topSegment);
 319             m_limit = limit(m_topSegment);
 320             m_top = m_topSegment->m_savedTop;
 321             m_hiddenCount -= uint32_t(m_top - m_base);
 322             m_hiddenSegments--;
 323             m_topSegment->m_savedTop = NULL;
 324         }
 325         else {
 326             m_base = m_top = m_limit = NULL;
 327             GCAssert(m_hiddenCount == 0);
 328             GCAssert(m_hiddenSegments == 0);
 329         }
 330
 331         if (m_extraSegment == NULL) {
 332             seg->m_prev = NULL;
 333             m_extraSegment = seg;
 334         }
 335         else
 336             FreeStackSegment(seg);
 337     }
 338
 339     GCMarkStack::StackSegment* GCMarkStack::FindLastSegment(StackSegment* first)
 340     {
 341         while (first->m_prev != NULL)
 342             first = first->m_prev;
 343         return first;
 344     }
 345
 346 #ifdef MMGC_MARKSTACK_ALLOWANCE
 347     bool GCMarkStack::MakeSpaceForSegments(int32_t nseg)
 348     {
 349         // If we have no space, and aren't going to pop a segment that's empty
 350         // before we return, and there's not an extra segment to give up, then
 351         // we fail.
 352                 if (m_allowance >= nseg)
 353                         return true;
 354                 if (m_allowance+1 == nseg && m_top == m_base)
 355                         return true;
 356                 if (m_allowance+1 == nseg && m_extraSegment != NULL) {
 357             FreeStackSegment(m_extraSegment);
 358             m_extraSegment = NULL;
 359                         return true;
 360                 }
 361                 return false;
 362     }
 363 #endif
 364
 365     void GCMarkStack::TransferOneInactiveSegmentFrom(GCMarkStack& other)
 366     {
 367         GCAssert(other.InactiveSegments() > 0);
 368
 369 #ifdef MMGC_MARKSTACK_ALLOWANCE
 370         if (!MakeSpaceForSegments(1))
 371             return;
 372 #endif
 373
 374         // Pick off the one below the top always.
 375
 376         StackSegment* subject = other.m_topSegment->m_prev;
 377         uint32_t subject_hc = uint32_t(subject->m_savedTop - items(subject));
 378
 379         other.m_topSegment->m_prev = subject->m_prev;
 380         other.m_hiddenCount -= subject_hc;
 381         other.m_hiddenSegments--;
 382 #ifdef MMGC_MARKSTACK_ALLOWANCE
 383         other.m_allowance++;
 384 #endif
 385
 386         FindLastSegment(m_topSegment)->m_prev = subject;
 387         subject->m_prev = NULL;
 388
 389         m_hiddenCount += subject_hc;
 390         m_hiddenSegments++;
 391 #ifdef MMGC_MARKSTACK_ALLOWANCE
 392         // The allowance may temporarily go negative until we pop a segment below.
 393         m_allowance--;
 394 #endif
 395
 396         // If a segment was inserted into an empty stack then pop the now empty top segment.
 397         if (m_top == m_base)
 398             PopSegment();
 399
 400         GCAssert(Invariants());
 401         GCAssert(other.Invariants());
 402     }
 403
 404     // Move all the segments from the other stack into the bottom of
 405     // this stack.
 406
 407     bool GCMarkStack::TransferEverythingFrom(GCMarkStack& other)
 408     {
 409         if (other.IsEmpty())
 410             return true;
 411
 412         uint32_t incoming_segments = other.m_hiddenSegments + 1;
 413
 414 #ifdef MMGC_MARKSTACK_ALLOWANCE
 415         if (!MakeSpaceForSegments(incoming_segments))
 416             return false;
 417 #endif
 418
 419         // Make sure we have a segment in the other stack with which to reestablish invariants.
 420 #ifdef MMGC_MARKSTACK_ALLOWANCE
 421         // Optimistically assume we'll succeed so that there will be an allowance for the other
 422         // stack to allocate in.
 423         other.m_allowance += incoming_segments;
 424         if (!other.PopulateExtraSegment(false)) {
 425             other.m_allowance -= incoming_segments; // Won't be moving anything after all
 426             return false;
 427         }
 428 #else
 429         if (!other.PopulateExtraSegment(false))
 430             return false;
 431 #endif
 432
 433         // Seal the other stack and obtain its data
 434         other.m_topSegment->m_savedTop = other.m_top;
 435         StackSegment* subject = other.m_topSegment;
 436         uint32_t subject_hc = other.m_hiddenCount + uint32_t(other.m_topSegment->m_savedTop - items(other.m_topSegment));
 437         uint32_t subject_hs = incoming_segments;
 438
 439         // Reestablish the null state in the other stack
 440         GCAssert(other.m_extraSegment != NULL);
 441         other.m_topSegment = other.m_extraSegment;
 442         other.m_extraSegment = NULL;
 443         other.m_hiddenCount = 0;
 444         other.m_hiddenSegments = 0;
 445         other.m_base = items(other.m_topSegment);
 446         other.m_limit = limit(other.m_topSegment);
 447         other.m_top = other.m_base;
 448
 449         // Link the segments into our stack and update our state
 450         FindLastSegment(m_topSegment)->m_prev = subject;
 451         m_hiddenCount += subject_hc;
 452         m_hiddenSegments += subject_hs;
 453 #ifdef MMGC_MARKSTACK_ALLOWANCE
 454         // The allowance may temporarily go negative until we pop a segment below.
 455         m_allowance -= incoming_segments;
 456 #endif
 457
 458         // If the segments were inserted into an empty stack then pop the now empty top segment.
 459         if (m_top == m_base)
 460             PopSegment();
 461
 462         GCAssert(Invariants());
 463         GCAssert(other.Invariants());
 464
 465         return true;
 466     }
 467
 468     uintptr_t* GCMarkStack::GetNextItemAbove(uintptr_t* item)
 469     {
 470         if (item == m_top-1)
 471             return NULL;
 472
 473         m_topSegment->m_savedTop = m_top;
 474         StackSegment* seg = m_topSegment;
 475         StackSegment* prev = NULL;
 476         while (seg != NULL) {
 477             if(item >= items(seg) && item < seg->m_savedTop) {
 478                 // If the current item is the top item in the segment then the item
 479                 // above is in the segment above, otherwise it's in this segment
 480                 uintptr_t* p = (item == seg->m_savedTop-1) ? items(prev) : item+1;
 481
 482                 // Scan forward in the item to find the top word.
 483                 while ((*p & 1) != 0)
 484                     p++;
 485                 return p;
 486             }
 487             prev = seg;
 488             seg = seg->m_prev;
 489         }
 490         return NULL;
 491     }
 492
 493     // About overwriting dead items with a distinguished non-NULL GC object pointer:
 494     //
 495     // It's not strictly necessary to do it this way.  The two alternatives are to use
 496     // a distinguished type of stack item (kDeadItem), or using a NULL pointer.  A kDeadItem
 497     // type could be used at zero cost, dead items would be handled on the slow path.
 498     // However a kDeadItem would always be at least two words long and could not be used
 499     // to clear out a GCObject.  Also, a kDeadItem would be variable-length, complicating
 500     // code that parses stack items.  A NULL GCObject pointer is possible as the current
 501     // marker architecture would just divert those items onto the slow path at zero cost.
 502     // However, the invariant that there are no NULL pointers on the stack is worth more
 503     // to me at present.
 504
 505     void GCMarkStack::ClearItemAt(uintptr_t index)
 506     {
 507         GCAssert(m_deadItem != 0);
 508         uintptr_t* p = (uintptr_t*)index;
 509         uintptr_t w = *p;
 510         p[0] = m_deadItem;
 511         if ((w & 3) != 0) {
 512             switch (TypeTag(w >> 2)) {
 513                 default:
 514                     GCAssert(!"Unknown TypeTag in ClearItemAt");
 515                     break;
 516                 case kStackMemory:
 517                 case kLargeObjectChunk:
 518                 case kLargeRootChunk:
 519                     p[-3] = m_deadItem;
 520                 case kLargeExactObjectTail:
 521                     p[-2] = m_deadItem;
 522                 case kRootProtector:
 523                 case kLargeObjectProtector:
 524                     p[-1] = m_deadItem;
 525             }
 526         }
 527         GCAssert(Invariants());
 528     }
 529
 530     inline void* GCMarkStack::AllocStackSegment(bool mustSucceed)
 531     {
 532 #ifdef MMGC_MARKSTACK_ALLOWANCE
 533         if (m_allowance == 0) {
 534             // This is fine, mustSucceed is only used for the first segment in
 535             // a stack, and the allowance is per-stack.
 536             GCAssert(!mustSucceed);
 537             return NULL;
 538         }
 539         --m_allowance;
 540 #endif
 541         if (mustSucceed)
 542             return GCHeap::GetGCHeap()->Alloc(1, GCHeap::flags_Alloc);
 543         else
 544             return GCHeap::GetGCHeap()->AllocNoOOM(1, GCHeap::flags_Alloc | GCHeap::kCanFail);
 545     }
 546
 547     inline void GCMarkStack::FreeStackSegment(void* p)
 548     {
 549 #ifdef MMGC_MARKSTACK_ALLOWANCE
 550         ++m_allowance;
 551 #endif
 552         GCHeap::GetGCHeap()->FreeNoOOM(p);
 553     }
 554
 555 #ifdef _DEBUG
 556     bool GCMarkStack::Invariants()
 557     {
 558 #ifdef MMGC_MARKSTACK_ALLOWANCE
 559         GCAssert(m_allowance >= 0);
 560 #endif
 561         GCAssert(m_topSegment->sentinel1 == 0);
 562         GCAssert(m_topSegment->sentinel2 == 0);
 563         GCAssert(limit(m_topSegment)[0] == 0);
 564         GCAssert(limit(m_topSegment)[1] == 0);
 565         GCAssert(limit(m_topSegment) == m_limit);
 566         GCAssert(m_top >= m_base);
 567         GCAssert(m_top <= m_limit);
 568         GCAssert(m_topSegment->m_prev == NULL || m_top > m_base);
 569         uint32_t hc = 0;
 570         uint32_t ns = 0;
 571         for ( StackSegment* seg=m_topSegment->m_prev ; seg != NULL ; seg = seg->m_prev ) {
 572             GCAssert(seg->sentinel1 == 0);
 573             GCAssert(seg->sentinel2 == 0);
 574             GCAssert(limit(seg)[0] == 0);
 575             GCAssert(limit(seg)[1] == 0);
 576             hc += uint32_t(seg->m_savedTop - items(seg));
 577             ns++;
 578         }
 579         GCAssert(ns == InactiveSegments());
 580         GCAssert(hc == m_hiddenCount);
 581         GCAssert(Count() == hc + (m_top - m_base));
 582         return true;
 583     }
 584 #endif
 585 }