1 // -*- mode: c++; c-basic-offset: 4 -*-
3 * This file is part of the KDE libraries
4 * Copyright (C) 2003, 2004, 2005, 2006 Apple Computer, Inc.
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.
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.
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
23 #include "collector.h"
25 #include <wtf/FastMalloc.h>
26 #include <wtf/FastMallocInternal.h>
27 #include <wtf/HashCountedSet.h>
38 #include <mach/mach_port.h>
39 #include <mach/task.h>
40 #include <mach/thread_act.h>
42 #elif PLATFORM(WIN_OS)
50 #if HAVE(PTHREAD_NP_H)
51 #include <pthread_np.h>
56 #define DEBUG_COLLECTOR 0
63 const size_t MINIMUM_CELL_SIZE = 48;
64 const size_t BLOCK_SIZE = (8 * 4096);
65 const size_t SPARE_EMPTY_BLOCKS = 2;
66 const size_t MIN_ARRAY_SIZE = 14;
67 const size_t GROWTH_FACTOR = 2;
68 const size_t LOW_WATER_FACTOR = 4;
69 const size_t ALLOCATIONS_PER_COLLECTION = 1000;
72 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
73 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
74 const size_t CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
78 struct CollectorCell {
80 double memory[CELL_ARRAY_LENGTH];
89 struct CollectorBlock {
90 CollectorCell cells[CELLS_PER_BLOCK];
92 CollectorCell *freeList;
95 struct CollectorHeap {
96 CollectorBlock **blocks;
99 size_t firstBlockWithPossibleSpace;
101 CollectorCell **oversizeCells;
102 size_t numOversizeCells;
103 size_t usedOversizeCells;
105 size_t numLiveObjects;
106 size_t numLiveObjectsAtLastCollect;
109 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
111 bool Collector::memoryFull = false;
113 void* Collector::allocate(size_t s)
115 assert(JSLock::lockCount() > 0);
118 size_t numLiveObjects = heap.numLiveObjects;
119 size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
120 size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
121 if (numNewObjects >= ALLOCATIONS_PER_COLLECTION && numNewObjects >= numLiveObjectsAtLastCollect) {
123 numLiveObjects = heap.numLiveObjects;
127 // oversize allocator
128 size_t usedOversizeCells = heap.usedOversizeCells;
129 size_t numOversizeCells = heap.numOversizeCells;
131 if (usedOversizeCells == numOversizeCells) {
132 numOversizeCells = max(MIN_ARRAY_SIZE, numOversizeCells * GROWTH_FACTOR);
133 heap.numOversizeCells = numOversizeCells;
134 heap.oversizeCells = static_cast<CollectorCell **>(fastRealloc(heap.oversizeCells, numOversizeCells * sizeof(CollectorCell *)));
137 void *newCell = fastMalloc(s);
138 heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
139 heap.usedOversizeCells = usedOversizeCells + 1;
140 heap.numLiveObjects = numLiveObjects + 1;
147 size_t usedBlocks = heap.usedBlocks;
149 size_t i = heap.firstBlockWithPossibleSpace;
150 CollectorBlock *targetBlock;
151 size_t targetBlockUsedCells;
152 if (i != usedBlocks) {
153 targetBlock = heap.blocks[i];
154 targetBlockUsedCells = targetBlock->usedCells;
155 assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
156 while (targetBlockUsedCells == CELLS_PER_BLOCK) {
157 if (++i == usedBlocks)
158 goto allocateNewBlock;
159 targetBlock = heap.blocks[i];
160 targetBlockUsedCells = targetBlock->usedCells;
161 assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
163 heap.firstBlockWithPossibleSpace = i;
166 // didn't find one, need to allocate a new block
167 size_t numBlocks = heap.numBlocks;
168 if (usedBlocks == numBlocks) {
169 numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
170 heap.numBlocks = numBlocks;
171 heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
174 targetBlock = static_cast<CollectorBlock *>(fastCalloc(1, sizeof(CollectorBlock)));
175 targetBlock->freeList = targetBlock->cells;
176 targetBlockUsedCells = 0;
177 heap.blocks[usedBlocks] = targetBlock;
178 heap.usedBlocks = usedBlocks + 1;
179 heap.firstBlockWithPossibleSpace = usedBlocks;
182 // find a free spot in the block and detach it from the free list
183 CollectorCell *newCell = targetBlock->freeList;
185 // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized
186 // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
187 targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);
189 targetBlock->usedCells = targetBlockUsedCells + 1;
190 heap.numLiveObjects = numLiveObjects + 1;
195 #if USE(MULTIPLE_THREADS)
197 struct Collector::Thread {
198 Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
200 pthread_t posixThread;
201 mach_port_t machThread;
204 pthread_key_t registeredThreadKey;
205 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
206 Collector::Thread *registeredThreads;
208 static void destroyRegisteredThread(void *data)
210 Collector::Thread *thread = (Collector::Thread *)data;
212 if (registeredThreads == thread) {
213 registeredThreads = registeredThreads->next;
215 Collector::Thread *last = registeredThreads;
216 for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
218 last->next = t->next;
228 static void initializeRegisteredThreadKey()
230 pthread_key_create(®isteredThreadKey, destroyRegisteredThread);
233 void Collector::registerThread()
235 pthread_once(®isteredThreadKeyOnce, initializeRegisteredThreadKey);
237 if (!pthread_getspecific(registeredThreadKey)) {
238 pthread_t pthread = pthread_self();
239 WTF::fastMallocRegisterThread(pthread);
240 Collector::Thread *thread = new Collector::Thread(pthread, pthread_mach_thread_np(pthread));
241 thread->next = registeredThreads;
242 registeredThreads = thread;
243 pthread_setspecific(registeredThreadKey, thread);
249 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
251 // cells are 8-byte aligned
252 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
254 void Collector::markStackObjectsConservatively(void *start, void *end)
262 assert(((char *)end - (char *)start) < 0x1000000);
263 assert(IS_POINTER_ALIGNED(start));
264 assert(IS_POINTER_ALIGNED(end));
266 char **p = (char **)start;
267 char **e = (char **)end;
269 size_t usedBlocks = heap.usedBlocks;
270 CollectorBlock **blocks = heap.blocks;
271 size_t usedOversizeCells = heap.usedOversizeCells;
272 CollectorCell **oversizeCells = heap.oversizeCells;
274 const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
278 if (IS_CELL_ALIGNED(x) && x) {
279 for (size_t block = 0; block < usedBlocks; block++) {
280 size_t offset = x - reinterpret_cast<char *>(blocks[block]);
281 if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0)
284 for (size_t i = 0; i != usedOversizeCells; i++)
285 if (x == reinterpret_cast<char *>(oversizeCells[i]))
290 if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
291 JSCell *imp = reinterpret_cast<JSCell *>(x);
299 void Collector::markCurrentThreadConservatively()
305 pthread_t thread = pthread_self();
306 void *stackBase = pthread_get_stackaddr_np(thread);
307 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
313 void *stackBase = (void *)pTib->StackBase;
315 static void *stackBase = 0;
316 static pthread_t stackThread;
317 pthread_t thread = pthread_self();
318 if (stackBase == 0 || thread != stackThread) {
319 pthread_attr_t sattr;
320 #if HAVE(PTHREAD_NP_H)
321 // e.g. on FreeBSD 5.4, neundorf@kde.org
322 pthread_attr_get_np(thread, &sattr);
324 // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
325 pthread_getattr_np(thread, &sattr);
327 // Should work but fails on Linux (?)
328 // pthread_attr_getstack(&sattr, &stackBase, &stackSize);
329 pthread_attr_getstackaddr(&sattr, &stackBase);
331 stackThread = thread;
334 #error Need a way to get the stack base on this platform
338 void *stackPointer = &dummy;
340 markStackObjectsConservatively(stackPointer, stackBase);
343 #if USE(MULTIPLE_THREADS)
345 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
347 void Collector::markOtherThreadConservatively(Thread *thread)
349 thread_suspend(thread->machThread);
352 i386_thread_state_t regs;
353 unsigned user_count = sizeof(regs)/sizeof(int);
354 thread_state_flavor_t flavor = i386_THREAD_STATE;
355 #elif PLATFORM(X86_64)
356 x86_thread_state64_t regs;
357 unsigned user_count = x86_THREAD_STATE64_COUNT;
358 thread_state_flavor_t flavor = x86_THREAD_STATE64;
360 ppc_thread_state_t regs;
361 unsigned user_count = PPC_THREAD_STATE_COUNT;
362 thread_state_flavor_t flavor = PPC_THREAD_STATE;
363 #elif PLATFORM(PPC64)
364 ppc_thread_state64_t regs;
365 unsigned user_count = PPC_THREAD_STATE64_COUNT;
366 thread_state_flavor_t flavor = PPC_THREAD_STATE64;
368 #error Unknown Architecture
370 // get the thread register state
371 thread_get_state(thread->machThread, flavor, (thread_state_t)®s, &user_count);
373 // scan the registers
374 markStackObjectsConservatively((void *)®s, (void *)((char *)®s + (user_count * sizeof(usword_t))));
377 #if PLATFORM(X86) && __DARWIN_UNIX03
378 markStackObjectsConservatively((void *)regs.__esp, pthread_get_stackaddr_np(thread->posixThread));
380 markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
381 #elif PLATFORM(X86_64) && __DARWIN_UNIX03
382 markStackObjectsConservatively((void *)regs.__rsp, pthread_get_stackaddr_np(thread->posixThread));
383 #elif PLATFORM(X86_64)
384 markStackObjectsConservatively((void *)regs.rsp, pthread_get_stackaddr_np(thread->posixThread));
385 #elif (PLATFORM(PPC) || PLATFORM(PPC64)) && __DARWIN_UNIX03
386 markStackObjectsConservatively((void *)regs.__r1, pthread_get_stackaddr_np(thread->posixThread));
387 #elif PLATFORM(PPC) || PLATFORM(PPC64)
388 markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
390 #error Unknown Architecture
393 thread_resume(thread->machThread);
398 void Collector::markStackObjectsConservatively()
400 markCurrentThreadConservatively();
402 #if USE(MULTIPLE_THREADS)
403 for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
404 if (thread->posixThread != pthread_self()) {
405 markOtherThreadConservatively(thread);
411 typedef HashCountedSet<JSCell *> ProtectCounts;
413 static ProtectCounts& protectedValues()
415 static ProtectCounts pv;
419 void Collector::protect(JSValue *k)
422 assert(JSLock::lockCount() > 0);
424 if (JSImmediate::isImmediate(k))
427 protectedValues().add(k->downcast());
430 void Collector::unprotect(JSValue *k)
433 assert(JSLock::lockCount() > 0);
435 if (JSImmediate::isImmediate(k))
438 protectedValues().remove(k->downcast());
441 void Collector::markProtectedObjects()
443 ProtectCounts& pv = protectedValues();
444 ProtectCounts::iterator end = pv.end();
445 for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
446 JSCell *val = it->first;
452 bool Collector::collect()
454 assert(JSLock::lockCount() > 0);
456 #if USE(MULTIPLE_THREADS)
457 bool currentThreadIsMainThread = !pthread_is_threaded_np() || pthread_main_np();
459 bool currentThreadIsMainThread = true;
462 if (Interpreter::s_hook) {
463 Interpreter* scr = Interpreter::s_hook;
465 scr->mark(currentThreadIsMainThread);
467 } while (scr != Interpreter::s_hook);
470 // MARK: first mark all referenced objects recursively starting out from the set of root objects
472 markStackObjectsConservatively();
473 markProtectedObjects();
474 List::markProtectedLists();
476 // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
478 size_t emptyBlocks = 0;
479 size_t numLiveObjects = heap.numLiveObjects;
481 for (size_t block = 0; block < heap.usedBlocks; block++) {
482 CollectorBlock *curBlock = heap.blocks[block];
484 size_t usedCells = curBlock->usedCells;
485 CollectorCell *freeList = curBlock->freeList;
487 if (usedCells == CELLS_PER_BLOCK) {
488 // special case with a block where all cells are used -- testing indicates this happens often
489 for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
490 CollectorCell *cell = curBlock->cells + i;
491 JSCell *imp = reinterpret_cast<JSCell *>(cell);
493 imp->m_marked = false;
494 } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
499 // put cell on the free list
500 cell->u.freeCell.zeroIfFree = 0;
501 cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
506 size_t minimumCellsToProcess = usedCells;
507 for (size_t i = 0; i < minimumCellsToProcess; i++) {
508 CollectorCell *cell = curBlock->cells + i;
509 if (cell->u.freeCell.zeroIfFree == 0) {
510 ++minimumCellsToProcess;
512 JSCell *imp = reinterpret_cast<JSCell *>(cell);
514 imp->m_marked = false;
515 } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
520 // put cell on the free list
521 cell->u.freeCell.zeroIfFree = 0;
522 cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
529 curBlock->usedCells = usedCells;
530 curBlock->freeList = freeList;
532 if (usedCells == 0) {
534 if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
538 // swap with the last block so we compact as we go
539 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
541 block--; // Don't move forward a step in this case
543 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
544 heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
545 heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
551 if (heap.numLiveObjects != numLiveObjects)
552 heap.firstBlockWithPossibleSpace = 0;
555 while (cell < heap.usedOversizeCells) {
556 JSCell *imp = (JSCell *)heap.oversizeCells[cell];
558 if (!imp->m_marked && (currentThreadIsMainThread || imp->m_destructorIsThreadSafe)) {
561 heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
566 // swap with the last oversize cell so we compact as we go
567 heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
569 heap.usedOversizeCells--;
572 if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
573 heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
574 heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
577 imp->m_marked = false;
582 bool deleted = heap.numLiveObjects != numLiveObjects;
584 heap.numLiveObjects = numLiveObjects;
585 heap.numLiveObjectsAtLastCollect = numLiveObjects;
587 memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
592 size_t Collector::size()
594 return heap.numLiveObjects;
598 void Collector::finalCheck()
603 size_t Collector::numInterpreters()
606 if (Interpreter::s_hook) {
607 Interpreter* scr = Interpreter::s_hook;
611 } while (scr != Interpreter::s_hook);
616 size_t Collector::numProtectedObjects()
618 return protectedValues().size();
621 static const char *typeName(JSCell *val)
623 const char *name = "???";
624 switch (val->type()) {
625 case UnspecifiedType:
643 const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
644 name = info ? info->className : "Object";
647 case GetterSetterType:
648 name = "gettersetter";
654 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
656 HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
658 ProtectCounts& pv = protectedValues();
659 ProtectCounts::iterator end = pv.end();
660 for (ProtectCounts::iterator it = pv.begin(); it != end; ++it)
661 counts->add(typeName(it->first));