cf7ff31c376412d7bec4d1d860315eea33f9cc00
[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         static const size_t PropertyStorageNurserySize = 1024 * 1024 * 4;
50
51         struct SizeClass {
52             SizeClass();
53             void resetAllocator();
54             void canonicalizeBlock();
55
56             MarkedBlock::FreeCell* firstFreeCell;
57             MarkedBlock* currentBlock;
58             MarkedBlock* nextBlock;
59             DoublyLinkedList<MarkedBlock> blockList;
60             size_t cellSize;
61         };
62
63         NewSpace(Heap*);
64
65         SizeClass& sizeClassFor(size_t);
66         void* allocate(SizeClass&);
67         inline void* allocatePropertyStorage(size_t);
68         inline bool inPropertyStorageNursery(void* ptr);
69         inline void resetPropertyStorageNursery();
70         
71         void resetAllocator();
72
73         void addBlock(SizeClass&, MarkedBlock*);
74         void removeBlock(MarkedBlock*);
75         
76         void canonicalizeBlocks();
77
78         size_t waterMark();
79         size_t highWaterMark();
80         void setHighWaterMark(size_t);
81
82         template<typename Functor> typename Functor::ReturnType forEachBlock(Functor&); // Safe to remove the current item while iterating.
83         template<typename Functor> typename Functor::ReturnType forEachBlock();
84
85     private:
86         // [ 8, 16... 128 )
87         static const size_t preciseStep = MarkedBlock::atomSize;
88         static const size_t preciseCutoff = 128;
89         static const size_t maximumPreciseAllocationSize = preciseCutoff - preciseStep;
90         static const size_t preciseCount = preciseCutoff / preciseStep - 1;
91
92         // [ 128, 256... 1024 )
93         static const size_t impreciseStep = preciseCutoff;
94         static const size_t impreciseCutoff = maxCellSize;
95         static const size_t impreciseCount = impreciseCutoff / impreciseStep - 1;
96
97         SizeClass m_preciseSizeClasses[preciseCount];
98         SizeClass m_impreciseSizeClasses[impreciseCount];
99         char* m_propertyStorageNursery;
100         char* m_propertyStorageAllocationPoint;
101         size_t m_waterMark;
102         size_t m_highWaterMark;
103         Heap* m_heap;
104     };
105
106     inline size_t NewSpace::waterMark()
107     {
108         return m_waterMark;
109     }
110
111     inline size_t NewSpace::highWaterMark()
112     {
113         return m_highWaterMark;
114     }
115
116     inline void NewSpace::setHighWaterMark(size_t highWaterMark)
117     {
118         m_highWaterMark = highWaterMark;
119     }
120
121     inline NewSpace::SizeClass& NewSpace::sizeClassFor(size_t bytes)
122     {
123         ASSERT(bytes && bytes < maxCellSize);
124         if (bytes <= maximumPreciseAllocationSize)
125             return m_preciseSizeClasses[(bytes - 1) / preciseStep];
126         return m_impreciseSizeClasses[(bytes - 1) / impreciseStep];
127     }
128
129     inline void* NewSpace::allocate(SizeClass& sizeClass)
130     {
131         MarkedBlock::FreeCell* firstFreeCell = sizeClass.firstFreeCell;
132         if (!firstFreeCell) {
133             // There are two possibilities for why we got here:
134             // 1) We've exhausted the allocation cache for currentBlock, in which case
135             //    currentBlock == nextBlock, and we know that there is no reason to
136             //    repeat a lazy sweep of nextBlock because we won't find anything.
137             // 2) Allocation caches have been cleared, in which case nextBlock may
138             //    have (and most likely does have) free cells, so we almost certainly
139             //    should do a lazySweep for nextBlock. This also implies that
140             //    currentBlock == 0.
141             
142             if (sizeClass.currentBlock) {
143                 ASSERT(sizeClass.currentBlock == sizeClass.nextBlock);
144                 m_waterMark += sizeClass.nextBlock->capacity();
145                 sizeClass.nextBlock = sizeClass.nextBlock->next();
146                 sizeClass.currentBlock = 0;
147             }
148             
149             for (MarkedBlock*& block = sizeClass.nextBlock ; block; block = block->next()) {
150                 firstFreeCell = block->lazySweep();
151                 if (firstFreeCell) {
152                     sizeClass.firstFreeCell = firstFreeCell;
153                     sizeClass.currentBlock = block;
154                     break;
155                 }
156                 
157                 m_waterMark += block->capacity();
158             }
159             
160             if (!firstFreeCell)
161                 return 0;
162         }
163         
164         ASSERT(firstFreeCell);
165         
166         sizeClass.firstFreeCell = firstFreeCell->next;
167         return firstFreeCell;
168     }
169
170     inline void NewSpace::resetPropertyStorageNursery()
171     {
172         m_propertyStorageAllocationPoint = m_propertyStorageNursery;
173     }
174     
175     inline void* NewSpace::allocatePropertyStorage(size_t size)
176     {
177         char* result = m_propertyStorageAllocationPoint;
178         if (size > PropertyStorageNurserySize)
179             CRASH();
180         m_propertyStorageAllocationPoint += size;
181         if (static_cast<size_t>(m_propertyStorageAllocationPoint - m_propertyStorageNursery) > PropertyStorageNurserySize) {
182             m_propertyStorageAllocationPoint = result;
183             return 0;
184         }
185         return result;
186     }
187
188     inline bool NewSpace::inPropertyStorageNursery(void* ptr)
189     {
190         char* addr = static_cast<char*>(ptr);
191         return static_cast<size_t>(addr - m_propertyStorageNursery) < PropertyStorageNurserySize;
192     }
193     
194     template <typename Functor> inline typename Functor::ReturnType NewSpace::forEachBlock(Functor& functor)
195     {
196         for (size_t i = 0; i < preciseCount; ++i) {
197             SizeClass& sizeClass = m_preciseSizeClasses[i];
198             MarkedBlock* next;
199             for (MarkedBlock* block = sizeClass.blockList.head(); block; block = next) {
200                 next = block->next();
201                 functor(block);
202             }
203         }
204
205         for (size_t i = 0; i < impreciseCount; ++i) {
206             SizeClass& sizeClass = m_impreciseSizeClasses[i];
207             MarkedBlock* next;
208             for (MarkedBlock* block = sizeClass.blockList.head(); block; block = next) {
209                 next = block->next();
210                 functor(block);
211             }
212         }
213
214         return functor.returnValue();
215     }
216
217     template <typename Functor> inline typename Functor::ReturnType NewSpace::forEachBlock()
218     {
219         Functor functor;
220         return forEachBlock(functor);
221     }
222
223     inline NewSpace::SizeClass::SizeClass()
224         : firstFreeCell(0)
225         , currentBlock(0)
226         , nextBlock(0)
227         , cellSize(0)
228     {
229     }
230
231     inline void NewSpace::SizeClass::resetAllocator()
232     {
233         nextBlock = blockList.head();
234     }
235     
236     inline void NewSpace::SizeClass::canonicalizeBlock()
237     {
238         if (currentBlock) {
239             currentBlock->canonicalizeBlock(firstFreeCell);
240             firstFreeCell = 0;
241         }
242         
243         ASSERT(!firstFreeCell);
244         
245         currentBlock = 0;
246         firstFreeCell = 0;
247     }
248
249 } // namespace JSC
250
251 #endif // NewSpace_h