165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch/* 265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved. 365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Copyright (C) 2007 Eric Seidel <eric@webkit.org> 465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * This library is free software; you can redistribute it and/or 665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * modify it under the terms of the GNU Lesser General Public 765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * License as published by the Free Software Foundation; either 865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * version 2 of the License, or (at your option) any later version. 965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 1065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * This library is distributed in the hope that it will be useful, 1165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * but WITHOUT ANY WARRANTY; without even the implied warranty of 1265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Lesser General Public License for more details. 1465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 1565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * You should have received a copy of the GNU Lesser General Public 1665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * License along with this library; if not, write to the Free Software 1765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 1865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch * 1965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch */ 2065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 2165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "config.h" 2265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "MarkedSpace.h" 2365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 2465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "JSCell.h" 2565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "JSGlobalData.h" 2665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch#include "JSLock.h" 272bde8e466a4451c7319e3a072d118917957d6554Steve Block#include "JSObject.h" 2881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#include "ScopeChain.h" 2965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 3065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochnamespace JSC { 3165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 3265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochclass Structure; 3365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 3465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben MurdochMarkedSpace::MarkedSpace(JSGlobalData* globalData) 352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : m_waterMark(0) 362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_highWaterMark(0) 372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_globalData(globalData) 3865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 392bde8e466a4451c7319e3a072d118917957d6554Steve Block for (size_t cellSize = preciseStep; cellSize < preciseCutoff; cellSize += preciseStep) 402bde8e466a4451c7319e3a072d118917957d6554Steve Block sizeClassFor(cellSize).cellSize = cellSize; 412bde8e466a4451c7319e3a072d118917957d6554Steve Block 422bde8e466a4451c7319e3a072d118917957d6554Steve Block for (size_t cellSize = impreciseStep; cellSize < impreciseCutoff; cellSize += impreciseStep) 4381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClassFor(cellSize).cellSize = cellSize; 4465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 4565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 462fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid MarkedSpace::destroy() 4765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 4881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch clearMarks(); 4981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch shrink(); 5081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(!size()); 5165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 5265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 5381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen MurdochMarkedBlock* MarkedSpace::allocateBlock(SizeClass& sizeClass) 5465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 5581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock* block = MarkedBlock::create(globalData(), sizeClass.cellSize); 5681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClass.blockList.append(block); 5781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClass.nextBlock = block; 5881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_blocks.add(block); 5981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 6065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch return block; 6165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 6265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 6381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochvoid MarkedSpace::freeBlocks(DoublyLinkedList<MarkedBlock>& blocks) 6465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 6581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock* next; 6681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (MarkedBlock* block = blocks.head(); block; block = next) { 6781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch next = block->next(); 6865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 6981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch blocks.remove(block); 7081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch m_blocks.remove(block); 7181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock::destroy(block); 7281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 7365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 7465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 7581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdochvoid* MarkedSpace::allocateFromSizeClass(SizeClass& sizeClass) 7665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 7781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) { 7881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (void* result = block->allocate()) 792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return result; 8065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_waterMark += block->capacity(); 8281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 8365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_waterMark < m_highWaterMark) 8581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch return allocateBlock(sizeClass)->allocate(); 8665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return 0; 8865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 8965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 902fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid MarkedSpace::shrink() 9165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 9281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch // We record a temporary list of empties to avoid modifying m_blocks while iterating it. 9381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch DoublyLinkedList<MarkedBlock> empties; 9481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 9581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 9681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) { 9781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch MarkedBlock* block = *it; 9881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch if (block->isEmpty()) { 9981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch SizeClass& sizeClass = sizeClassFor(block->cellSize()); 10081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClass.blockList.remove(block); 10181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClass.nextBlock = sizeClass.blockList.head(); 10281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch empties.append(block); 10381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch } 10465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch } 10581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 10681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch freeBlocks(empties); 10781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch ASSERT(empties.isEmpty()); 10865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 10965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1102fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid MarkedSpace::clearMarks() 11165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 11281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 11381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 11481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch (*it)->clearMarks(); 11565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 11665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 11765f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochvoid MarkedSpace::sweep() 11865f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 11981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 12081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 12181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch (*it)->sweep(); 12265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 12365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 12465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochsize_t MarkedSpace::objectCount() const 12565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 1262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t result = 0; 12781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 12881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 12981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch result += (*it)->markCount(); 1302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return result; 13165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 13265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1332fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocksize_t MarkedSpace::size() const 13465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 1352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t result = 0; 13681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 13781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 13881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch result += (*it)->size(); 1392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return result; 14065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 14165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 1422fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocksize_t MarkedSpace::capacity() const 14365f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 1442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block size_t result = 0; 14581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 14681bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 14781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch result += (*it)->capacity(); 1482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return result; 14965f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 15065f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 15165f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdochvoid MarkedSpace::reset() 15265f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch{ 1532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_waterMark = 0; 15481bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 1552bde8e466a4451c7319e3a072d118917957d6554Steve Block for (size_t cellSize = preciseStep; cellSize < preciseCutoff; cellSize += preciseStep) 1562bde8e466a4451c7319e3a072d118917957d6554Steve Block sizeClassFor(cellSize).reset(); 1572bde8e466a4451c7319e3a072d118917957d6554Steve Block 1582bde8e466a4451c7319e3a072d118917957d6554Steve Block for (size_t cellSize = impreciseStep; cellSize < impreciseCutoff; cellSize += impreciseStep) 15981bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch sizeClassFor(cellSize).reset(); 16081bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch 16181bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch BlockIterator end = m_blocks.end(); 16281bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch for (BlockIterator it = m_blocks.begin(); it != end; ++it) 16381bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch (*it)->reset(); 16465f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} 16565f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch 16665f03d4f644ce73618e5f4f50dd694b26f55ae12Ben Murdoch} // namespace JSC 167