Unreviewed, rolling out r94445 and r94448.
[WebKit-https.git] / Source / JavaScriptCore / heap / NewSpace.h
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, 2011 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 NewSpace_h
23 #define NewSpace_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) < NewSpace::maxCellSize, class_fits_in_cell)
36
37 namespace JSC {
38
39     class Heap;
40     class JSCell;
41     class LiveObjectIterator;
42     class WeakGCHandle;
43     class SlotVisitor;
44
45     class NewSpace {
46         WTF_MAKE_NONCOPYABLE(NewSpace);
47     public:
48         static const size_t maxCellSize = 1024;
49
50         struct SizeClass {
51             SizeClass();
52             void resetAllocator();
53             void canonicalizeBlock();
54
55             MarkedBlock::FreeCell* firstFreeCell;
56             MarkedBlock* currentBlock;
57             MarkedBlock* nextBlock;
58             DoublyLinkedList<MarkedBlock> blockList;
59             size_t cellSize;
60         };
61
62         NewSpace(Heap*);
63
64         SizeClass& sizeClassFor(size_t);
65         void* allocate(SizeClass&);
66         void resetAllocator();
67
68         void addBlock(SizeClass&, MarkedBlock*);
69         void removeBlock(MarkedBlock*);
70         
71         void canonicalizeBlocks();
72
73         size_t waterMark();
74         size_t highWaterMark();
75         void setHighWaterMark(size_t);
76
77         template<typename Functor> typename Functor::ReturnType forEachBlock(Functor&); // Safe to remove the current item while iterating.
78         template<typename Functor> typename Functor::ReturnType forEachBlock();
79
80     private:
81         // [ 8, 16... 128 )
82         static const size_t preciseStep = MarkedBlock::atomSize;
83         static const size_t preciseCutoff = 128;
84         static const size_t maximumPreciseAllocationSize = preciseCutoff - preciseStep;
85         static const size_t preciseCount = preciseCutoff / preciseStep - 1;
86
87         // [ 128, 256... 1024 )
88         static const size_t impreciseStep = preciseCutoff;
89         static const size_t impreciseCutoff = maxCellSize;
90         static const size_t impreciseCount = impreciseCutoff / impreciseStep - 1;
91
92         SizeClass m_preciseSizeClasses[preciseCount];
93         SizeClass m_impreciseSizeClasses[impreciseCount];
94         size_t m_waterMark;
95         size_t m_highWaterMark;
96         Heap* m_heap;
97     };
98
99     inline size_t NewSpace::waterMark()
100     {
101         return m_waterMark;
102     }
103
104     inline size_t NewSpace::highWaterMark()
105     {
106         return m_highWaterMark;
107     }
108
109     inline void NewSpace::setHighWaterMark(size_t highWaterMark)
110     {
111         m_highWaterMark = highWaterMark;
112     }
113
114     inline NewSpace::SizeClass& NewSpace::sizeClassFor(size_t bytes)
115     {
116         ASSERT(bytes && bytes < maxCellSize);
117         if (bytes <= maximumPreciseAllocationSize)
118             return m_preciseSizeClasses[(bytes - 1) / preciseStep];
119         return m_impreciseSizeClasses[(bytes - 1) / impreciseStep];
120     }
121
122     inline void* NewSpace::allocate(SizeClass& sizeClass)
123     {
124         MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell;
125         if (!firstFreeCell) {
126             // There are two possibilities for why we got here:
127             // 1) We've exhausted the allocation cache for currentBlock, in which case
128             //    currentBlock == nextBlock, and we know that there is no reason to
129             //    repeat a lazy sweep of nextBlock because we won't find anything.
130             // 2) Allocation caches have been cleared, in which case nextBlock may
131             //    have (and most likely does have) free cells, so we almost certainly
132             //    should do a lazySweep for nextBlock. This also implies that
133             //    currentBlock == 0.
134             
135             if (sizeClass.currentBlock) {
136                 ASSERT(sizeClass.currentBlock == sizeClass.nextBlock);
137                 m_waterMark += sizeClass.nextBlock->capacity();
138                 sizeClass.nextBlock = sizeClass.nextBlock->next();
139                 sizeClass.currentBlock = 0;
140             }
141             
142             for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) {
143                 firstFreeCell = block->lazySweep();
144                 if (firstFreeCell) {
145                     sizeClass.firstFreeCell = firstFreeCell;
146                     sizeClass.currentBlock = block;
147                     break;
148                 }
149                 
150                 m_waterMark += block->capacity();
151             }
152             
153             if (!firstFreeCell)
154                 return 0;
155         }
156         
157         ASSERT(firstFreeCell);
158         
159         sizeClass.firstFreeCell = firstFreeCell->next;
160         return firstFreeCell;
161     }
162
163     template <typename Functor> inline typename Functor::ReturnType NewSpace::forEachBlock(Functor& functor)
164     {
165         for (size_t i = 0; i < preciseCount; ++i) {
166             SizeClass& sizeClass = m_preciseSizeClasses[i];
167             MarkedBlock* next;
168             for (MarkedBlock* block = sizeClass.blockList.head(); block; block = next) {
169                 next = block->next();
170                 functor(block);
171             }
172         }
173
174         for (size_t i = 0; i < impreciseCount; ++i) {
175             SizeClass& sizeClass = m_impreciseSizeClasses[i];
176             MarkedBlock* next;
177             for (MarkedBlock* block = sizeClass.blockList.head(); block; block = next) {
178                 next = block->next();
179                 functor(block);
180             }
181         }
182
183         return functor.returnValue();
184     }
185
186     template <typename Functor> inline typename Functor::ReturnType NewSpace::forEachBlock()
187     {
188         Functor functor;
189         return forEachBlock(functor);
190     }
191
192     inline NewSpace::SizeClass::SizeClass()
193         : firstFreeCell(0)
194         , currentBlock(0)
195         , nextBlock(0)
196         , cellSize(0)
197     {
198     }
199
200     inline void NewSpace::SizeClass::resetAllocator()
201     {
202         nextBlock = blockList.head();
203     }
204     
205     inline void NewSpace::SizeClass::canonicalizeBlock()
206     {
207         if (currentBlock) {
208             currentBlock->canonicalizeBlock(firstFreeCell);
209             firstFreeCell = 0;
210         }
211         
212         ASSERT(!firstFreeCell);
213         
214         currentBlock = 0;
215         firstFreeCell = 0;
216     }
217
218 } // namespace JSC
219
220 #endif // NewSpace_h