165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch/* 265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Copyright (C) 2001 Peter Kelly (pmk@post.com) 465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved. 565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * This library is free software; you can redistribute it and/or 765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * modify it under the terms of the GNU Lesser General Public 865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * License as published by the Free Software Foundation; either 965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * version 2 of the License, or (at your option) any later version. 1065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 1165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * This library is distributed in the hope that it will be useful, 1265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * but WITHOUT ANY WARRANTY; without even the implied warranty of 1365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Lesser General Public License for more details. 1565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 1665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * You should have received a copy of the GNU Lesser General Public 1765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * License along with this library; if not, write to the Free Software 1865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 1965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 2065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch */ 2165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 2265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#ifndef MarkedSpace_h 2365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#define MarkedSpace_h 2465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 2565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "MachineStackMarker.h" 262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "MarkedBlock.h" 2765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "PageAllocationAligned.h" 282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/Bitmap.h> 2981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#include <wtf/DoublyLinkedList.h> 3065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include <wtf/FixedArray.h> 3181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#include <wtf/HashSet.h> 3265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include <wtf/Noncopyable.h> 3365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include <wtf/Vector.h> 3465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 352bde8e466a4451c7319e3a072d118917957d6554Steve Block#define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) < MarkedSpace::maxCellSize, class_fits_in_cell) 3681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 3765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochnamespace JSC { 3865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 3965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class Heap; 4065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class JSCell; 4165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class JSGlobalData; 4265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class LiveObjectIterator; 4365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class MarkStack; 4465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch class WeakGCHandle; 4565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 46ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch class MarkedSpace { 47ab9e7a118cf1ea2e3a93dce683b2ded3e7291ddbBen Murdoch WTF_MAKE_NONCOPYABLE(MarkedSpace); 4865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch public: 4981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // Currently public for use in assertions. 502bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t maxCellSize = 1024; 5181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 5265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch static Heap* heap(JSCell*); 5365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static bool isMarked(const JSCell*); 552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static bool testAndSetMarked(const JSCell*); 562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static void setMarked(const JSCell*); 5765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block MarkedSpace(JSGlobalData*); 592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void destroy(); 6065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 6165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch JSGlobalData* globalData() { return m_globalData; } 6265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t highWaterMark() { return m_highWaterMark; } 642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setHighWaterMark(size_t highWaterMark) { m_highWaterMark = highWaterMark; } 652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void* allocate(size_t); 6765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void clearMarks(); 692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void markRoots(); 7065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch void reset(); 7165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch void sweep(); 722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void shrink(); 7365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t size() const; 752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t capacity() const; 762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t objectCount() const; 7765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool contains(const void*); 7965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block template<typename Functor> void forEach(Functor&); 8165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 8265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch private: 832bde8e466a4451c7319e3a072d118917957d6554Steve Block // [ 8, 16... 128 ) 8481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch static const size_t preciseStep = MarkedBlock::atomSize; 852bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t preciseCutoff = 128; 862bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t preciseCount = preciseCutoff / preciseStep - 1; 872bde8e466a4451c7319e3a072d118917957d6554Steve Block 882bde8e466a4451c7319e3a072d118917957d6554Steve Block // [ 128, 256... 1024 ) 892bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t impreciseStep = preciseCutoff; 902bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t impreciseCutoff = maxCellSize; 912bde8e466a4451c7319e3a072d118917957d6554Steve Block static const size_t impreciseCount = impreciseCutoff / impreciseStep - 1; 9281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch typedef HashSet<MarkedBlock*>::iterator BlockIterator; 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch struct SizeClass { 9681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch SizeClass(); 9781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void reset(); 9881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock* nextBlock; 10081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DoublyLinkedList<MarkedBlock> blockList; 10181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch size_t cellSize; 10281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch }; 10381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock* allocateBlock(SizeClass&); 10581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void freeBlocks(DoublyLinkedList<MarkedBlock>&); 10681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch SizeClass& sizeClassFor(size_t); 10881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch void* allocateFromSizeClass(SizeClass&); 10965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void clearMarks(MarkedBlock*); 11165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 11281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch SizeClass m_preciseSizeClasses[preciseCount]; 1132bde8e466a4451c7319e3a072d118917957d6554Steve Block SizeClass m_impreciseSizeClasses[impreciseCount]; 11481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch HashSet<MarkedBlock*> m_blocks; 1152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t m_waterMark; 1162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t m_highWaterMark; 1172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block JSGlobalData* m_globalData; 11865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch }; 11965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline Heap* MarkedSpace::heap(JSCell* cell) 1212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return MarkedBlock::blockFor(cell)->heap(); 1232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline bool MarkedSpace::isMarked(const JSCell* cell) 12665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch { 1272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return MarkedBlock::blockFor(cell)->isMarked(cell); 12865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 12965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline bool MarkedSpace::testAndSetMarked(const JSCell* cell) 13165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch { 1322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return MarkedBlock::blockFor(cell)->testAndSetMarked(cell); 13365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 13465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline void MarkedSpace::setMarked(const JSCell* cell) 13665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch { 1372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block MarkedBlock::blockFor(cell)->setMarked(cell); 13865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 13965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block inline bool MarkedSpace::contains(const void* x) 14165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch { 14281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (!MarkedBlock::isAtomAligned(x)) 1432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return false; 1442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block MarkedBlock* block = MarkedBlock::blockFor(x); 14681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (!block || !m_blocks.contains(block)) 1472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return false; 1482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 14981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return block->contains(x); 15065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 15165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block template <typename Functor> inline void MarkedSpace::forEach(Functor& functor) 15365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch { 15481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 15581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 15681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch (*it)->forEach(functor); 15781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 15881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 15981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline MarkedSpace::SizeClass::SizeClass() 16081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch : nextBlock(0) 16181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch , cellSize(0) 16281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 16381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 16481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 16581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch inline void MarkedSpace::SizeClass::reset() 16681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch { 16781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch nextBlock = blockList.head(); 16865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 16965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 17065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} // namespace JSC 17165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 17265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#endif // MarkedSpace_h 173