Removed some public data and casting from the Heap
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedBlock.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 MarkedBlock_h
23 #define MarkedBlock_h
24
25 #include "CardSet.h"
26 #include "HeapBlock.h"
27
28 #include "WeakSet.h"
29 #include <wtf/Bitmap.h>
30 #include <wtf/DataLog.h>
31 #include <wtf/DoublyLinkedList.h>
32 #include <wtf/HashFunctions.h>
33 #include <wtf/PageAllocationAligned.h>
34 #include <wtf/StdLibExtras.h>
35 #include <wtf/Vector.h>
36
37 // Set to log state transitions of blocks.
38 #define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
39
40 #if HEAP_LOG_BLOCK_STATE_TRANSITIONS
41 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) do {                     \
42         dataLog(                                                    \
43             "%s:%d %s: block %s = %p, %d\n",                            \
44             __FILE__, __LINE__, __FUNCTION__,                           \
45             #block, (block), (block)->m_state);                         \
46     } while (false)
47 #else
48 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) ((void)0)
49 #endif
50
51 namespace JSC {
52     
53     class Heap;
54     class JSCell;
55
56     typedef uintptr_t Bits;
57
58     static const size_t MB = 1024 * 1024;
59     
60     bool isZapped(const JSCell*);
61     
62     // A marked block is a page-aligned container for heap-allocated objects.
63     // Objects are allocated within cells of the marked block. For a given
64     // marked block, all cells have the same size. Objects smaller than the
65     // cell size may be allocated in the marked block, in which case the
66     // allocation suffers from internal fragmentation: wasted space whose
67     // size is equal to the difference between the cell size and the object
68     // size.
69
70     class MarkedBlock : public HeapBlock<MarkedBlock> {
71     public:
72         // Ensure natural alignment for native types whilst recognizing that the smallest
73         // object the heap will commonly allocate is four words.
74         static const size_t atomSize = 4 * sizeof(void*);
75         static const size_t atomShift = 5;
76         static const size_t blockSize = 64 * KB;
77         static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
78
79         static const size_t atomsPerBlock = blockSize / atomSize; // ~0.4% overhead
80         static const size_t atomMask = atomsPerBlock - 1;
81         static const int cardShift = 8; // This is log2 of bytes per card.
82         static const size_t bytesPerCard = 1 << cardShift;
83         static const int cardCount = blockSize / bytesPerCard;
84         static const int cardMask = cardCount - 1;
85
86         struct FreeCell {
87             FreeCell* next;
88         };
89         
90         struct FreeList {
91             FreeCell* head;
92             size_t bytes;
93
94             FreeList();
95             FreeList(FreeCell*, size_t);
96         };
97
98         struct VoidFunctor {
99             typedef void ReturnType;
100             void returnValue() { }
101         };
102
103         class CountFunctor {
104         public:
105             typedef size_t ReturnType;
106
107             CountFunctor() : m_count(0) { }
108             void count(size_t count) { m_count += count; }
109             ReturnType returnValue() { return m_count; }
110
111         private:
112             ReturnType m_count;
113         };
114
115         static MarkedBlock* create(const PageAllocationAligned&, Heap*, size_t cellSize, bool cellsNeedDestruction, bool onlyContainsStructures);
116
117         static bool isAtomAligned(const void*);
118         static MarkedBlock* blockFor(const void*);
119         static size_t firstAtom();
120         
121         void lastChanceToFinalize();
122
123         Heap* heap() const;
124         WeakSet& weakSet();
125         
126         enum SweepMode { SweepOnly, SweepToFreeList };
127         FreeList sweep(SweepMode = SweepOnly);
128
129         void shrink();
130
131         void visitWeakSet(HeapRootVisitor&);
132         void reapWeakSet();
133
134         // While allocating from a free list, MarkedBlock temporarily has bogus
135         // cell liveness data. To restore accurate cell liveness data, call one
136         // of these functions:
137         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
138         void zapFreeList(const FreeList&); // Call this to undo the free list.
139
140         void clearMarks();
141         size_t markCount();
142         bool isEmpty();
143
144         size_t cellSize();
145         bool cellsNeedDestruction();
146         bool onlyContainsStructures();
147
148         size_t size();
149         size_t capacity();
150
151         bool isMarked(const void*);
152         bool testAndSetMarked(const void*);
153         bool isLive(const JSCell*);
154         bool isLiveCell(const void*);
155         void setMarked(const void*);
156         
157         bool needsSweeping();
158
159 #if ENABLE(GGC)
160         void setDirtyObject(const void* atom)
161         {
162             ASSERT(MarkedBlock::blockFor(atom) == this);
163             m_cards.markCardForAtom(atom);
164         }
165
166         uint8_t* addressOfCardFor(const void* atom)
167         {
168             ASSERT(MarkedBlock::blockFor(atom) == this);
169             return &m_cards.cardForAtom(atom);
170         }
171
172         static inline size_t offsetOfCards()
173         {
174             return OBJECT_OFFSETOF(MarkedBlock, m_cards);
175         }
176
177         static inline size_t offsetOfMarks()
178         {
179             return OBJECT_OFFSETOF(MarkedBlock, m_marks);
180         }
181
182         typedef Vector<JSCell*, 32> DirtyCellVector;
183         inline void gatherDirtyCells(DirtyCellVector&);
184         template <int size> inline void gatherDirtyCellsWithSize(DirtyCellVector&);
185 #endif
186
187         template <typename Functor> void forEachCell(Functor&);
188
189     private:
190         static const size_t atomAlignmentMask = atomSize - 1; // atomSize must be a power of two.
191
192         enum BlockState { New, FreeListed, Allocated, Marked, Zapped };
193         template<bool destructorCallNeeded> FreeList sweepHelper(SweepMode = SweepOnly);
194
195         typedef char Atom[atomSize];
196
197         MarkedBlock(const PageAllocationAligned&, Heap*, size_t cellSize, bool cellsNeedDestruction, bool onlyContainsStructures);
198         Atom* atoms();
199         size_t atomNumber(const void*);
200         void callDestructor(JSCell*);
201         template<BlockState, SweepMode, bool destructorCallNeeded> FreeList specializedSweep();
202         
203 #if ENABLE(GGC)
204         CardSet<bytesPerCard, blockSize> m_cards;
205 #endif
206
207         size_t m_atomsPerCell;
208         size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
209 #if ENABLE(PARALLEL_GC)
210         WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic> m_marks;
211 #else
212         WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic> m_marks;
213 #endif
214         bool m_cellsNeedDestruction;
215         bool m_onlyContainsStructures;
216         BlockState m_state;
217         WeakSet m_weakSet;
218     };
219
220     inline MarkedBlock::FreeList::FreeList()
221         : head(0)
222         , bytes(0)
223     {
224     }
225
226     inline MarkedBlock::FreeList::FreeList(FreeCell* head, size_t bytes)
227         : head(head)
228         , bytes(bytes)
229     {
230     }
231
232     inline size_t MarkedBlock::firstAtom()
233     {
234         return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
235     }
236
237     inline MarkedBlock::Atom* MarkedBlock::atoms()
238     {
239         return reinterpret_cast<Atom*>(this);
240     }
241
242     inline bool MarkedBlock::isAtomAligned(const void* p)
243     {
244         return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
245     }
246
247     inline MarkedBlock* MarkedBlock::blockFor(const void* p)
248     {
249         return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
250     }
251
252     inline void MarkedBlock::lastChanceToFinalize()
253     {
254         m_weakSet.lastChanceToFinalize();
255
256         clearMarks();
257         sweep();
258     }
259
260     inline Heap* MarkedBlock::heap() const
261     {
262         return m_weakSet.heap();
263     }
264
265     inline WeakSet& MarkedBlock::weakSet()
266     {
267         return m_weakSet;
268     }
269
270     inline void MarkedBlock::shrink()
271     {
272         m_weakSet.shrink();
273     }
274
275     inline void MarkedBlock::visitWeakSet(HeapRootVisitor& heapRootVisitor)
276     {
277         m_weakSet.visit(heapRootVisitor);
278     }
279
280     inline void MarkedBlock::reapWeakSet()
281     {
282         m_weakSet.reap();
283     }
284
285     inline void MarkedBlock::didConsumeFreeList()
286     {
287         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
288
289         ASSERT(m_state == FreeListed);
290         m_state = Allocated;
291     }
292
293     inline void MarkedBlock::clearMarks()
294     {
295         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
296
297         ASSERT(m_state != New && m_state != FreeListed);
298         m_marks.clearAll();
299
300         // This will become true at the end of the mark phase. We set it now to
301         // avoid an extra pass to do so later.
302         m_state = Marked;
303     }
304
305     inline size_t MarkedBlock::markCount()
306     {
307         return m_marks.count();
308     }
309
310     inline bool MarkedBlock::isEmpty()
311     {
312         return m_marks.isEmpty() && m_weakSet.isEmpty();
313     }
314
315     inline size_t MarkedBlock::cellSize()
316     {
317         return m_atomsPerCell * atomSize;
318     }
319
320     inline bool MarkedBlock::cellsNeedDestruction()
321     {
322         return m_cellsNeedDestruction; 
323     }
324
325     inline bool MarkedBlock::onlyContainsStructures()
326     {
327         return m_onlyContainsStructures;
328     }
329
330     inline size_t MarkedBlock::size()
331     {
332         return markCount() * cellSize();
333     }
334
335     inline size_t MarkedBlock::capacity()
336     {
337         return allocation().size();
338     }
339
340     inline size_t MarkedBlock::atomNumber(const void* p)
341     {
342         return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
343     }
344
345     inline bool MarkedBlock::isMarked(const void* p)
346     {
347         return m_marks.get(atomNumber(p));
348     }
349
350     inline bool MarkedBlock::testAndSetMarked(const void* p)
351     {
352         return m_marks.concurrentTestAndSet(atomNumber(p));
353     }
354
355     inline void MarkedBlock::setMarked(const void* p)
356     {
357         m_marks.set(atomNumber(p));
358     }
359
360     inline bool MarkedBlock::isLive(const JSCell* cell)
361     {
362         switch (m_state) {
363         case Allocated:
364             return true;
365         case Zapped:
366             if (isZapped(cell)) {
367                 // Object dead in previous collection, not allocated since previous collection: mark bit should not be set.
368                 ASSERT(!m_marks.get(atomNumber(cell)));
369                 return false;
370             }
371             
372             // Newly allocated objects: mark bit not set.
373             // Objects that survived prior collection: mark bit set.
374             return true;
375         case Marked:
376             return m_marks.get(atomNumber(cell));
377
378         case New:
379         case FreeListed:
380             ASSERT_NOT_REACHED();
381             return false;
382         }
383
384         ASSERT_NOT_REACHED();
385         return false;
386     }
387
388     inline bool MarkedBlock::isLiveCell(const void* p)
389     {
390         ASSERT(MarkedBlock::isAtomAligned(p));
391         size_t atomNumber = this->atomNumber(p);
392         size_t firstAtom = this->firstAtom();
393         if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
394             return false;
395         if ((atomNumber - firstAtom) % m_atomsPerCell) // Filters pointers into cell middles.
396             return false;
397         if (atomNumber >= m_endAtom) // Filters pointers into invalid cells out of the range.
398             return false;
399
400         return isLive(static_cast<const JSCell*>(p));
401     }
402
403     template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
404     {
405         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
406             JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
407             if (!isLive(cell))
408                 continue;
409
410             functor(cell);
411         }
412     }
413
414     inline bool MarkedBlock::needsSweeping()
415     {
416         return m_state == Marked || m_state == Zapped;
417     }
418
419 #if ENABLE(GGC)
420 template <int _cellSize> void MarkedBlock::gatherDirtyCellsWithSize(DirtyCellVector& dirtyCells)
421 {
422     if (m_cards.testAndClear(0)) {
423         char* ptr = reinterpret_cast<char*>(&atoms()[firstAtom()]);
424         const char* end = reinterpret_cast<char*>(this) + bytesPerCard;
425         while (ptr < end) {
426             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
427             if (isMarked(cell))
428                 dirtyCells.append(cell);
429             ptr += _cellSize;
430         }
431     }
432     
433     const size_t cellOffset = firstAtom() * atomSize % _cellSize;
434     for (size_t i = 1; i < m_cards.cardCount; i++) {
435         if (!m_cards.testAndClear(i))
436             continue;
437         char* ptr = reinterpret_cast<char*>(this) + i * bytesPerCard + cellOffset;
438         char* end = reinterpret_cast<char*>(this) + (i + 1) * bytesPerCard;
439         
440         while (ptr < end) {
441             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
442             if (isMarked(cell))
443                 dirtyCells.append(cell);
444             ptr += _cellSize;
445         }
446     }
447 }
448
449 void MarkedBlock::gatherDirtyCells(DirtyCellVector& dirtyCells)
450 {
451     COMPILE_ASSERT((int)m_cards.cardCount == (int)cardCount, MarkedBlockCardCountsMatch);
452
453     ASSERT(m_state != New && m_state != FreeListed);
454     
455     // This is an optimisation to avoid having to walk the set of marked
456     // blocks twice during GC.
457     m_state = Marked;
458     
459     if (isEmpty())
460         return;
461     
462     size_t cellSize = this->cellSize();
463     if (cellSize == 32) {
464         gatherDirtyCellsWithSize<32>(dirtyCells);
465         return;
466     }
467     if (cellSize == 64) {
468         gatherDirtyCellsWithSize<64>(dirtyCells);
469         return;
470     }
471
472     const size_t firstCellOffset = firstAtom() * atomSize % cellSize;
473     
474     if (m_cards.testAndClear(0)) {
475         char* ptr = reinterpret_cast<char*>(this) + firstAtom() * atomSize;
476         char* end = reinterpret_cast<char*>(this) + bytesPerCard;
477         while (ptr < end) {
478             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
479             if (isMarked(cell))
480                 dirtyCells.append(cell);
481             ptr += cellSize;
482         }
483     }
484     for (size_t i = 1; i < m_cards.cardCount; i++) {
485         if (!m_cards.testAndClear(i))
486             continue;
487         char* ptr = reinterpret_cast<char*>(this) + firstCellOffset + cellSize * ((i * bytesPerCard + cellSize - 1 - firstCellOffset) / cellSize);
488         char* end = reinterpret_cast<char*>(this) + std::min((i + 1) * bytesPerCard, m_endAtom * atomSize);
489         
490         while (ptr < end) {
491             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
492             if (isMarked(cell))
493                 dirtyCells.append(cell);
494             ptr += cellSize;
495         }
496     }
497 }
498 #endif
499
500 } // namespace JSC
501
502 namespace WTF {
503
504     struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
505         static unsigned hash(JSC::MarkedBlock* const& key)
506         {
507             // Aligned VM regions tend to be monotonically increasing integers,
508             // which is a great hash function, but we have to remove the low bits,
509             // since they're always zero, which is a terrible hash function!
510             return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
511         }
512     };
513
514     template<> struct DefaultHash<JSC::MarkedBlock*> {
515         typedef MarkedBlockHash Hash;
516     };
517
518 } // namespace WTF
519
520 #endif // MarkedBlock_h