← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/JavaScriptCore/heap/MarkedBlock.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

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