1/*
2 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
4 *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
5 *
6 *  This library is free software; you can redistribute it and/or
7 *  modify it under the terms of the GNU Lesser General Public
8 *  License as published by the Free Software Foundation; either
9 *  version 2 of the License, or (at your option) any later version.
10 *
11 *  This library is distributed in the hope that it will be useful,
12 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 *  Lesser General Public License for more details.
15 *
16 *  You should have received a copy of the GNU Lesser General Public
17 *  License along with this library; if not, write to the Free Software
18 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19 *
20 */
21
22#ifndef MarkedSpace_h
23#define MarkedSpace_h
24
25#include "MachineStackMarker.h"
26#include "MarkedBlock.h"
27#include "PageAllocationAligned.h"
28#include <wtf/Bitmap.h>
29#include <wtf/DoublyLinkedList.h>
30#include <wtf/FixedArray.h>
31#include <wtf/HashSet.h>
32#include <wtf/Noncopyable.h>
33#include <wtf/Vector.h>
34
35#define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) < MarkedSpace::maxCellSize, class_fits_in_cell)
36
37namespace JSC {
38
39    class Heap;
40    class JSCell;
41    class JSGlobalData;
42    class LiveObjectIterator;
43    class MarkStack;
44    class WeakGCHandle;
45
46    class MarkedSpace {
47        WTF_MAKE_NONCOPYABLE(MarkedSpace);
48    public:
49        // Currently public for use in assertions.
50        static const size_t maxCellSize = 1024;
51
52        static Heap* heap(JSCell*);
53
54        static bool isMarked(const JSCell*);
55        static bool testAndSetMarked(const JSCell*);
56        static void setMarked(const JSCell*);
57
58        MarkedSpace(JSGlobalData*);
59        void destroy();
60
61        JSGlobalData* globalData() { return m_globalData; }
62
63        size_t highWaterMark() { return m_highWaterMark; }
64        void setHighWaterMark(size_t highWaterMark) { m_highWaterMark = highWaterMark; }
65
66        void* allocate(size_t);
67
68        void clearMarks();
69        void markRoots();
70        void reset();
71        void sweep();
72        void shrink();
73
74        size_t size() const;
75        size_t capacity() const;
76        size_t objectCount() const;
77
78        bool contains(const void*);
79
80        template<typename Functor> void forEach(Functor&);
81
82    private:
83        // [ 8, 16... 128 )
84        static const size_t preciseStep = MarkedBlock::atomSize;
85        static const size_t preciseCutoff = 128;
86        static const size_t preciseCount = preciseCutoff / preciseStep - 1;
87
88        // [ 128, 256... 1024 )
89        static const size_t impreciseStep = preciseCutoff;
90        static const size_t impreciseCutoff = maxCellSize;
91        static const size_t impreciseCount = impreciseCutoff / impreciseStep - 1;
92
93        typedef HashSet<MarkedBlock*>::iterator BlockIterator;
94
95        struct SizeClass {
96            SizeClass();
97            void reset();
98
99            MarkedBlock* nextBlock;
100            DoublyLinkedList<MarkedBlock> blockList;
101            size_t cellSize;
102        };
103
104        MarkedBlock* allocateBlock(SizeClass&);
105        void freeBlocks(DoublyLinkedList<MarkedBlock>&);
106
107        SizeClass& sizeClassFor(size_t);
108        void* allocateFromSizeClass(SizeClass&);
109
110        void clearMarks(MarkedBlock*);
111
112        SizeClass m_preciseSizeClasses[preciseCount];
113        SizeClass m_impreciseSizeClasses[impreciseCount];
114        HashSet<MarkedBlock*> m_blocks;
115        size_t m_waterMark;
116        size_t m_highWaterMark;
117        JSGlobalData* m_globalData;
118    };
119
120    inline Heap* MarkedSpace::heap(JSCell* cell)
121    {
122        return MarkedBlock::blockFor(cell)->heap();
123    }
124
125    inline bool MarkedSpace::isMarked(const JSCell* cell)
126    {
127        return MarkedBlock::blockFor(cell)->isMarked(cell);
128    }
129
130    inline bool MarkedSpace::testAndSetMarked(const JSCell* cell)
131    {
132        return MarkedBlock::blockFor(cell)->testAndSetMarked(cell);
133    }
134
135    inline void MarkedSpace::setMarked(const JSCell* cell)
136    {
137        MarkedBlock::blockFor(cell)->setMarked(cell);
138    }
139
140    inline bool MarkedSpace::contains(const void* x)
141    {
142        if (!MarkedBlock::isAtomAligned(x))
143            return false;
144
145        MarkedBlock* block = MarkedBlock::blockFor(x);
146        if (!block || !m_blocks.contains(block))
147            return false;
148
149        return block->contains(x);
150    }
151
152    template <typename Functor> inline void MarkedSpace::forEach(Functor& functor)
153    {
154        BlockIterator end = m_blocks.end();
155        for (BlockIterator it = m_blocks.begin(); it != end; ++it)
156            (*it)->forEach(functor);
157    }
158
159    inline MarkedSpace::SizeClass::SizeClass()
160        : nextBlock(0)
161        , cellSize(0)
162    {
163    }
164
165    inline void MarkedSpace::SizeClass::reset()
166    {
167        nextBlock = blockList.head();
168    }
169
170} // namespace JSC
171
172#endif // MarkedSpace_h
173