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