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 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 Collector_h
23#define Collector_h
24
25#include <stddef.h>
26#include <string.h>
27#include <wtf/HashCountedSet.h>
28#include <wtf/HashSet.h>
29#include <wtf/Noncopyable.h>
30#include <wtf/OwnPtr.h>
31#include <wtf/StdLibExtras.h>
32#include <wtf/Threading.h>
33
34#if ENABLE(JSC_MULTIPLE_THREADS)
35#include <pthread.h>
36#endif
37
38#define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) <= CELL_SIZE, class_fits_in_cell)
39
40namespace JSC {
41
42    class CollectorBlock;
43    class JSCell;
44    class JSGlobalData;
45    class JSValue;
46    class MarkedArgumentBuffer;
47    class MarkStack;
48
49    enum OperationInProgress { NoOperation, Allocation, Collection };
50
51    class LiveObjectIterator;
52
53    struct CollectorHeap {
54        size_t nextBlock;
55        size_t nextCell;
56        CollectorBlock** blocks;
57
58        void* nextNumber;
59
60        size_t numBlocks;
61        size_t usedBlocks;
62
63        size_t extraCost;
64        bool didShrink;
65
66        OperationInProgress operationInProgress;
67    };
68
69    class Heap : public Noncopyable {
70    public:
71        class Thread;
72
73        void destroy();
74
75        void* allocateNumber(size_t);
76        void* allocate(size_t);
77
78        bool isBusy(); // true if an allocation or collection is in progress
79        void collectAllGarbage();
80
81        static const size_t minExtraCost = 256;
82        static const size_t maxExtraCost = 1024 * 1024;
83
84        void reportExtraMemoryCost(size_t cost);
85
86        size_t objectCount() const;
87        struct Statistics {
88            size_t size;
89            size_t free;
90        };
91        Statistics statistics() const;
92
93        void protect(JSValue);
94        void unprotect(JSValue);
95
96        static Heap* heap(JSValue); // 0 for immediate values
97        static Heap* heap(JSCell*);
98
99        size_t globalObjectCount();
100        size_t protectedObjectCount();
101        size_t protectedGlobalObjectCount();
102        HashCountedSet<const char*>* protectedObjectTypeCounts();
103        HashCountedSet<const char*>* objectTypeCounts();
104
105        void registerThread(); // Only needs to be called by clients that can use the same heap from multiple threads.
106
107        static bool isCellMarked(const JSCell*);
108        static void markCell(JSCell*);
109
110        void markConservatively(MarkStack&, void* start, void* end);
111
112        HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = new HashSet<MarkedArgumentBuffer*>; return *m_markListSet; }
113
114        JSGlobalData* globalData() const { return m_globalData; }
115        static bool isNumber(JSCell*);
116
117        LiveObjectIterator primaryHeapBegin();
118        LiveObjectIterator primaryHeapEnd();
119
120    private:
121        void reset();
122        void sweep();
123        static CollectorBlock* cellBlock(const JSCell*);
124        static size_t cellOffset(const JSCell*);
125
126        friend class JSGlobalData;
127        Heap(JSGlobalData*);
128        ~Heap();
129
130        NEVER_INLINE CollectorBlock* allocateBlock();
131        NEVER_INLINE void freeBlock(size_t);
132        NEVER_INLINE void freeBlockPtr(CollectorBlock*);
133        void freeBlocks();
134        void resizeBlocks();
135        void growBlocks(size_t neededBlocks);
136        void shrinkBlocks(size_t neededBlocks);
137        void clearMarkBits();
138        void clearMarkBits(CollectorBlock*);
139        size_t markedCells(size_t startBlock = 0, size_t startCell = 0) const;
140
141        void recordExtraCost(size_t);
142
143        void addToStatistics(Statistics&) const;
144
145        void markRoots();
146        void markProtectedObjects(MarkStack&);
147        void markCurrentThreadConservatively(MarkStack&);
148        void markCurrentThreadConservativelyInternal(MarkStack&);
149        void markOtherThreadConservatively(MarkStack&, Thread*);
150        void markStackObjectsConservatively(MarkStack&);
151
152        typedef HashCountedSet<JSCell*> ProtectCountSet;
153
154        CollectorHeap m_heap;
155
156        ProtectCountSet m_protectedValues;
157
158        HashSet<MarkedArgumentBuffer*>* m_markListSet;
159
160#if ENABLE(JSC_MULTIPLE_THREADS)
161        void makeUsableFromMultipleThreads();
162
163        static void unregisterThread(void*);
164        void unregisterThread();
165
166        Mutex m_registeredThreadsMutex;
167        Thread* m_registeredThreads;
168        pthread_key_t m_currentThreadRegistrar;
169#endif
170
171        JSGlobalData* m_globalData;
172    };
173
174    // tunable parameters
175    template<size_t bytesPerWord> struct CellSize;
176
177    // cell size needs to be a power of two for certain optimizations in collector.cpp
178#if USE(JSVALUE32)
179    template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 32; };
180#else
181    template<> struct CellSize<sizeof(uint32_t)> { static const size_t m_value = 64; };
182#endif
183    template<> struct CellSize<sizeof(uint64_t)> { static const size_t m_value = 64; };
184
185#if OS(WINCE) || OS(SYMBIAN)
186    const size_t BLOCK_SIZE = 64 * 1024; // 64k
187#else
188    const size_t BLOCK_SIZE = 64 * 4096; // 256k
189#endif
190
191    // derived constants
192    const size_t BLOCK_OFFSET_MASK = BLOCK_SIZE - 1;
193    const size_t BLOCK_MASK = ~BLOCK_OFFSET_MASK;
194    const size_t MINIMUM_CELL_SIZE = CellSize<sizeof(void*)>::m_value;
195    const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
196    const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
197    const size_t SMALL_CELL_SIZE = CELL_SIZE / 2;
198    const size_t CELL_MASK = CELL_SIZE - 1;
199    const size_t CELL_ALIGN_MASK = ~CELL_MASK;
200    const size_t CELLS_PER_BLOCK = (BLOCK_SIZE - sizeof(Heap*)) * 8 * CELL_SIZE / (8 * CELL_SIZE + 1) / CELL_SIZE; // one bitmap byte can represent 8 cells.
201
202    const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
203    const size_t BITMAP_WORDS = (BITMAP_SIZE + 3) / sizeof(uint32_t);
204
205    struct CollectorBitmap {
206        uint32_t bits[BITMAP_WORDS];
207        bool get(size_t n) const { return !!(bits[n >> 5] & (1 << (n & 0x1F))); }
208        void set(size_t n) { bits[n >> 5] |= (1 << (n & 0x1F)); }
209        void clear(size_t n) { bits[n >> 5] &= ~(1 << (n & 0x1F)); }
210        void clearAll() { memset(bits, 0, sizeof(bits)); }
211        size_t count(size_t startCell = 0)
212        {
213            size_t result = 0;
214            for ( ; (startCell & 0x1F) != 0; ++startCell) {
215                if (get(startCell))
216                    ++result;
217            }
218            for (size_t i = startCell >> 5; i < BITMAP_WORDS; ++i)
219                result += WTF::bitCount(bits[i]);
220            return result;
221        }
222        size_t isEmpty() // Much more efficient than testing count() == 0.
223        {
224            for (size_t i = 0; i < BITMAP_WORDS; ++i)
225                if (bits[i] != 0)
226                    return false;
227            return true;
228        }
229    };
230
231    struct CollectorCell {
232        double memory[CELL_ARRAY_LENGTH];
233    };
234
235    class CollectorBlock {
236    public:
237        CollectorCell cells[CELLS_PER_BLOCK];
238        CollectorBitmap marked;
239        Heap* heap;
240    };
241
242    struct HeapConstants {
243        static const size_t cellSize = CELL_SIZE;
244        static const size_t cellsPerBlock = CELLS_PER_BLOCK;
245        typedef CollectorCell Cell;
246        typedef CollectorBlock Block;
247    };
248
249    inline CollectorBlock* Heap::cellBlock(const JSCell* cell)
250    {
251        return reinterpret_cast<CollectorBlock*>(reinterpret_cast<uintptr_t>(cell) & BLOCK_MASK);
252    }
253
254    inline size_t Heap::cellOffset(const JSCell* cell)
255    {
256        return (reinterpret_cast<uintptr_t>(cell) & BLOCK_OFFSET_MASK) / CELL_SIZE;
257    }
258
259    inline bool Heap::isCellMarked(const JSCell* cell)
260    {
261        return cellBlock(cell)->marked.get(cellOffset(cell));
262    }
263
264    inline void Heap::markCell(JSCell* cell)
265    {
266        cellBlock(cell)->marked.set(cellOffset(cell));
267    }
268
269    inline void Heap::reportExtraMemoryCost(size_t cost)
270    {
271        if (cost > minExtraCost)
272            recordExtraCost(cost);
273    }
274
275    inline void* Heap::allocateNumber(size_t s)
276    {
277        if (void* result = m_heap.nextNumber) {
278            m_heap.nextNumber = 0;
279            return result;
280        }
281
282        void* result = allocate(s);
283        m_heap.nextNumber = static_cast<char*>(result) + (CELL_SIZE / 2);
284        return result;
285    }
286
287} // namespace JSC
288
289#endif /* Collector_h */
290