Reviewed by Geoff.
[WebKit-https.git] / JavaScriptCore / kjs / collector.cpp
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  *  This file is part of the KDE libraries
4  *  Copyright (C) 2003, 2004, 2005, 2006 Apple Computer, Inc.
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 #include "config.h"
23 #include "collector.h"
24
25 #include <wtf/FastMalloc.h>
26 #include <wtf/FastMallocInternal.h>
27 #include <wtf/HashCountedSet.h>
28 #include "internal.h"
29 #include "list.h"
30 #include "value.h"
31
32 #include <setjmp.h>
33 #include <algorithm>
34
35 #if PLATFORM(DARWIN)
36
37 #include <pthread.h>
38 #include <mach/mach_port.h>
39 #include <mach/task.h>
40 #include <mach/thread_act.h>
41
42 #elif PLATFORM(WIN_OS)
43
44 #include <windows.h>
45
46 #elif PLATFORM(UNIX)
47
48 #include <pthread.h>
49
50 #if HAVE(PTHREAD_NP_H)
51 #include <pthread_np.h>
52 #endif
53
54 #endif
55
56 #define DEBUG_COLLECTOR 0
57
58 using std::max;
59
60 namespace KJS {
61
62 // tunable parameters
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;
70
71 // derived constants
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));
75
76
77
78 struct CollectorCell {
79   union {
80     double memory[CELL_ARRAY_LENGTH];
81     struct {
82       void *zeroIfFree;
83       ptrdiff_t next;
84     } freeCell;
85   } u;
86 };
87
88
89 struct CollectorBlock {
90   CollectorCell cells[CELLS_PER_BLOCK];
91   uint32_t usedCells;
92   CollectorCell *freeList;
93 };
94
95 struct CollectorHeap {
96   CollectorBlock **blocks;
97   size_t numBlocks;
98   size_t usedBlocks;
99   size_t firstBlockWithPossibleSpace;
100   
101   CollectorCell **oversizeCells;
102   size_t numOversizeCells;
103   size_t usedOversizeCells;
104
105   size_t numLiveObjects;
106   size_t numLiveObjectsAtLastCollect;
107 };
108
109 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
110
111 bool Collector::memoryFull = false;
112
113 void* Collector::allocate(size_t s)
114 {
115   assert(JSLock::lockCount() > 0);
116
117   // collect if needed
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) {
122     collect();
123     numLiveObjects = heap.numLiveObjects;
124   }
125   
126   if (s > CELL_SIZE) {
127     // oversize allocator
128     size_t usedOversizeCells = heap.usedOversizeCells;
129     size_t numOversizeCells = heap.numOversizeCells;
130
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 *)));
135     }
136     
137     void *newCell = fastMalloc(s);
138     heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
139     heap.usedOversizeCells = usedOversizeCells + 1;
140     heap.numLiveObjects = numLiveObjects + 1;
141
142     return newCell;
143   }
144   
145   // slab allocator
146   
147   size_t usedBlocks = heap.usedBlocks;
148
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);
162     }
163     heap.firstBlockWithPossibleSpace = i;
164   } else {
165 allocateNewBlock:
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 *)));
172     }
173
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;
180   }
181   
182   // find a free spot in the block and detach it from the free list
183   CollectorCell *newCell = targetBlock->freeList;
184   
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);
188
189   targetBlock->usedCells = targetBlockUsedCells + 1;
190   heap.numLiveObjects = numLiveObjects + 1;
191
192   return newCell;
193 }
194
195 #if USE(MULTIPLE_THREADS)
196
197 struct Collector::Thread {
198   Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
199   Thread *next;
200   pthread_t posixThread;
201   mach_port_t machThread;
202 };
203
204 pthread_key_t registeredThreadKey;
205 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
206 Collector::Thread *registeredThreads;
207   
208 static void destroyRegisteredThread(void *data) 
209 {
210   Collector::Thread *thread = (Collector::Thread *)data;
211
212   if (registeredThreads == thread) {
213     registeredThreads = registeredThreads->next;
214   } else {
215     Collector::Thread *last = registeredThreads;
216     for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
217       if (t == thread) {
218         last->next = t->next;
219           break;
220       }
221       last = t;
222     }
223   }
224
225   delete thread;
226 }
227
228 static void initializeRegisteredThreadKey()
229 {
230   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
231 }
232
233 void Collector::registerThread()
234 {
235   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
236
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);
244   }
245 }
246
247 #endif
248
249 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
250
251 // cells are 8-byte aligned
252 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
253
254 void Collector::markStackObjectsConservatively(void *start, void *end)
255 {
256   if (start > end) {
257     void *tmp = start;
258     start = end;
259     end = tmp;
260   }
261
262   assert(((char *)end - (char *)start) < 0x1000000);
263   assert(IS_POINTER_ALIGNED(start));
264   assert(IS_POINTER_ALIGNED(end));
265   
266   char **p = (char **)start;
267   char **e = (char **)end;
268   
269   size_t usedBlocks = heap.usedBlocks;
270   CollectorBlock **blocks = heap.blocks;
271   size_t usedOversizeCells = heap.usedOversizeCells;
272   CollectorCell **oversizeCells = heap.oversizeCells;
273
274   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
275
276   while (p != e) {
277     char *x = *p++;
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)
282           goto gotGoodPointer;
283       }
284       for (size_t i = 0; i != usedOversizeCells; i++)
285         if (x == reinterpret_cast<char *>(oversizeCells[i]))
286           goto gotGoodPointer;
287       continue;
288
289 gotGoodPointer:
290       if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
291         JSCell *imp = reinterpret_cast<JSCell *>(x);
292         if (!imp->marked())
293           imp->mark();
294       }
295     }
296   }
297 }
298
299 void Collector::markCurrentThreadConservatively()
300 {
301     jmp_buf registers;
302     setjmp(registers);
303
304 #if PLATFORM(DARWIN)
305     pthread_t thread = pthread_self();
306     void *stackBase = pthread_get_stackaddr_np(thread);
307 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
308     NT_TIB *pTib;
309     __asm {
310         MOV EAX, FS:[18h]
311         MOV pTib, EAX
312     }
313     void *stackBase = (void *)pTib->StackBase;
314 #elif PLATFORM(UNIX)
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);
323 #else
324         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
325         pthread_getattr_np(thread, &sattr);
326 #endif
327         // Should work but fails on Linux (?)
328         //  pthread_attr_getstack(&sattr, &stackBase, &stackSize);
329         pthread_attr_getstackaddr(&sattr, &stackBase);
330         assert(stackBase);
331         stackThread = thread;
332     }
333 #else
334 #error Need a way to get the stack base on this platform
335 #endif
336
337     void *dummy;
338     void *stackPointer = &dummy;
339
340     markStackObjectsConservatively(stackPointer, stackBase);
341 }
342
343 #if USE(MULTIPLE_THREADS)
344
345 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
346
347 void Collector::markOtherThreadConservatively(Thread *thread)
348 {
349   thread_suspend(thread->machThread);
350
351 #if PLATFORM(X86)
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;
359 #elif PLATFORM(PPC)
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;
367 #else
368 #error Unknown Architecture
369 #endif
370   // get the thread register state
371   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
372   
373   // scan the registers
374   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
375    
376   // scan the stack
377 #if PLATFORM(X86) && __DARWIN_UNIX03
378   markStackObjectsConservatively((void *)regs.__esp, pthread_get_stackaddr_np(thread->posixThread));
379 #elif PLATFORM(X86)
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));
389 #else
390 #error Unknown Architecture
391 #endif
392
393   thread_resume(thread->machThread);
394 }
395
396 #endif
397
398 void Collector::markStackObjectsConservatively()
399 {
400   markCurrentThreadConservatively();
401
402 #if USE(MULTIPLE_THREADS)
403   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
404     if (thread->posixThread != pthread_self()) {
405       markOtherThreadConservatively(thread);
406     }
407   }
408 #endif
409 }
410
411 typedef HashCountedSet<JSCell *> ProtectCounts;
412
413 static ProtectCounts& protectedValues()
414 {
415     static ProtectCounts pv;
416     return pv;
417 }
418
419 void Collector::protect(JSValue *k)
420 {
421     assert(k);
422     assert(JSLock::lockCount() > 0);
423
424     if (JSImmediate::isImmediate(k))
425       return;
426
427     protectedValues().add(k->downcast());
428 }
429
430 void Collector::unprotect(JSValue *k)
431 {
432     assert(k);
433     assert(JSLock::lockCount() > 0);
434
435     if (JSImmediate::isImmediate(k))
436       return;
437
438     protectedValues().remove(k->downcast());
439 }
440
441 void Collector::markProtectedObjects()
442 {
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;
447     if (!val->marked())
448       val->mark();
449   }
450 }
451
452 bool Collector::collect()
453 {
454   assert(JSLock::lockCount() > 0);
455
456 #if USE(MULTIPLE_THREADS)
457     bool currentThreadIsMainThread = !pthread_is_threaded_np() || pthread_main_np();
458 #else
459     bool currentThreadIsMainThread = true;
460 #endif
461     
462   if (Interpreter::s_hook) {
463     Interpreter* scr = Interpreter::s_hook;
464     do {
465       scr->mark(currentThreadIsMainThread);
466       scr = scr->next;
467     } while (scr != Interpreter::s_hook);
468   }
469
470   // MARK: first mark all referenced objects recursively starting out from the set of root objects
471
472   markStackObjectsConservatively();
473   markProtectedObjects();
474   List::markProtectedLists();
475
476   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
477   
478   size_t emptyBlocks = 0;
479   size_t numLiveObjects = heap.numLiveObjects;
480
481   for (size_t block = 0; block < heap.usedBlocks; block++) {
482     CollectorBlock *curBlock = heap.blocks[block];
483
484     size_t usedCells = curBlock->usedCells;
485     CollectorCell *freeList = curBlock->freeList;
486
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);
492         if (imp->m_marked) {
493           imp->m_marked = false;
494         } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
495           imp->~JSCell();
496           --usedCells;
497           --numLiveObjects;
498
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);
502           freeList = cell;
503         }
504       }
505     } else {
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;
511         } else {
512           JSCell *imp = reinterpret_cast<JSCell *>(cell);
513           if (imp->m_marked) {
514             imp->m_marked = false;
515           } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
516             imp->~JSCell();
517             --usedCells;
518             --numLiveObjects;
519
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);
523             freeList = cell;
524           }
525         }
526       }
527     }
528     
529     curBlock->usedCells = usedCells;
530     curBlock->freeList = freeList;
531
532     if (usedCells == 0) {
533       emptyBlocks++;
534       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
535 #if !DEBUG_COLLECTOR
536         fastFree(curBlock);
537 #endif
538         // swap with the last block so we compact as we go
539         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
540         heap.usedBlocks--;
541         block--; // Don't move forward a step in this case
542
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 *));
546         }
547       }
548     }
549   }
550
551   if (heap.numLiveObjects != numLiveObjects)
552     heap.firstBlockWithPossibleSpace = 0;
553   
554   size_t cell = 0;
555   while (cell < heap.usedOversizeCells) {
556     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
557     
558     if (!imp->m_marked && (currentThreadIsMainThread || imp->m_destructorIsThreadSafe)) {
559       imp->~JSCell();
560 #if DEBUG_COLLECTOR
561       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
562 #else
563       fastFree(imp);
564 #endif
565
566       // swap with the last oversize cell so we compact as we go
567       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
568
569       heap.usedOversizeCells--;
570       numLiveObjects--;
571
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 *));
575       }
576     } else {
577       imp->m_marked = false;
578       cell++;
579     }
580   }
581   
582   bool deleted = heap.numLiveObjects != numLiveObjects;
583
584   heap.numLiveObjects = numLiveObjects;
585   heap.numLiveObjectsAtLastCollect = numLiveObjects;
586   
587   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
588
589   return deleted;
590 }
591
592 size_t Collector::size() 
593 {
594   return heap.numLiveObjects; 
595 }
596
597 #ifdef KJS_DEBUG_MEM
598 void Collector::finalCheck()
599 {
600 }
601 #endif
602
603 size_t Collector::numInterpreters()
604 {
605   size_t count = 0;
606   if (Interpreter::s_hook) {
607     Interpreter* scr = Interpreter::s_hook;
608     do {
609       ++count;
610       scr = scr->next;
611     } while (scr != Interpreter::s_hook);
612   }
613   return count;
614 }
615
616 size_t Collector::numProtectedObjects()
617 {
618   return protectedValues().size();
619 }
620
621 static const char *typeName(JSCell *val)
622 {
623   const char *name = "???";
624   switch (val->type()) {
625     case UnspecifiedType:
626       break;
627     case UndefinedType:
628       name = "undefined";
629       break;
630     case NullType:
631       name = "null";
632       break;
633     case BooleanType:
634       name = "boolean";
635       break;
636     case StringType:
637       name = "string";
638       break;
639     case NumberType:
640       name = "number";
641       break;
642     case ObjectType: {
643       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
644       name = info ? info->className : "Object";
645       break;
646     }
647     case GetterSetterType:
648       name = "gettersetter";
649       break;
650   }
651   return name;
652 }
653
654 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
655 {
656     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
657
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));
662
663     return counts;
664 }
665
666 } // namespace KJS