d21cb3152c6ac752d8f713d21c3825a56a5496e8
[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 = 56;
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   if (numLiveObjects - heap.numLiveObjectsAtLastCollect >= ALLOCATIONS_PER_COLLECTION) {
120     collect();
121     numLiveObjects = heap.numLiveObjects;
122   }
123   
124   if (s > CELL_SIZE) {
125     // oversize allocator
126
127     size_t usedOversizeCells = heap.usedOversizeCells;
128     size_t numOversizeCells = heap.numOversizeCells;
129
130     if (usedOversizeCells == numOversizeCells) {
131       numOversizeCells = max(MIN_ARRAY_SIZE, numOversizeCells * GROWTH_FACTOR);
132       heap.numOversizeCells = numOversizeCells;
133       heap.oversizeCells = static_cast<CollectorCell **>(fastRealloc(heap.oversizeCells, numOversizeCells * sizeof(CollectorCell *)));
134     }
135     
136     void *newCell = fastMalloc(s);
137     heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
138     heap.usedOversizeCells = usedOversizeCells + 1;
139     heap.numLiveObjects = numLiveObjects + 1;
140
141     return newCell;
142   }
143   
144   // slab allocator
145   
146   size_t usedBlocks = heap.usedBlocks;
147
148   size_t i = heap.firstBlockWithPossibleSpace;
149   CollectorBlock *targetBlock;
150   size_t targetBlockUsedCells;
151   if (i != usedBlocks) {
152     targetBlock = heap.blocks[i];
153     targetBlockUsedCells = targetBlock->usedCells;
154     assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
155     while (targetBlockUsedCells == CELLS_PER_BLOCK) {
156       if (++i == usedBlocks)
157         goto allocateNewBlock;
158       targetBlock = heap.blocks[i];
159       targetBlockUsedCells = targetBlock->usedCells;
160       assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
161     }
162     heap.firstBlockWithPossibleSpace = i;
163   } else {
164 allocateNewBlock:
165     // didn't find one, need to allocate a new block
166     size_t numBlocks = heap.numBlocks;
167     if (usedBlocks == numBlocks) {
168       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
169       heap.numBlocks = numBlocks;
170       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
171     }
172
173     targetBlock = static_cast<CollectorBlock *>(fastCalloc(1, sizeof(CollectorBlock)));
174     targetBlock->freeList = targetBlock->cells;
175     targetBlockUsedCells = 0;
176     heap.blocks[usedBlocks] = targetBlock;
177     heap.usedBlocks = usedBlocks + 1;
178     heap.firstBlockWithPossibleSpace = usedBlocks;
179   }
180   
181   // find a free spot in the block and detach it from the free list
182   CollectorCell *newCell = targetBlock->freeList;
183   
184   // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized
185   // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
186   targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);
187
188   targetBlock->usedCells = targetBlockUsedCells + 1;
189   heap.numLiveObjects = numLiveObjects + 1;
190
191   return newCell;
192 }
193
194 #if USE(MULTIPLE_THREADS)
195
196 struct Collector::Thread {
197   Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
198   Thread *next;
199   pthread_t posixThread;
200   mach_port_t machThread;
201 };
202
203 pthread_key_t registeredThreadKey;
204 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
205 Collector::Thread *registeredThreads;
206   
207 static void destroyRegisteredThread(void *data) 
208 {
209   Collector::Thread *thread = (Collector::Thread *)data;
210
211   if (registeredThreads == thread) {
212     registeredThreads = registeredThreads->next;
213   } else {
214     Collector::Thread *last = registeredThreads;
215     for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
216       if (t == thread) {
217         last->next = t->next;
218           break;
219       }
220       last = t;
221     }
222   }
223
224   delete thread;
225 }
226
227 static void initializeRegisteredThreadKey()
228 {
229   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
230 }
231
232 void Collector::registerThread()
233 {
234   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
235
236   if (!pthread_getspecific(registeredThreadKey)) {
237     pthread_t pthread = pthread_self();
238     WTF::fastMallocRegisterThread(pthread);
239     Collector::Thread *thread = new Collector::Thread(pthread, pthread_mach_thread_np(pthread));
240     thread->next = registeredThreads;
241     registeredThreads = thread;
242     pthread_setspecific(registeredThreadKey, thread);
243   }
244 }
245
246 #endif
247
248 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
249
250 // cells are 8-byte aligned
251 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
252
253 void Collector::markStackObjectsConservatively(void *start, void *end)
254 {
255   if (start > end) {
256     void *tmp = start;
257     start = end;
258     end = tmp;
259   }
260
261   assert(((char *)end - (char *)start) < 0x1000000);
262   assert(IS_POINTER_ALIGNED(start));
263   assert(IS_POINTER_ALIGNED(end));
264   
265   char **p = (char **)start;
266   char **e = (char **)end;
267   
268   size_t usedBlocks = heap.usedBlocks;
269   CollectorBlock **blocks = heap.blocks;
270   size_t usedOversizeCells = heap.usedOversizeCells;
271   CollectorCell **oversizeCells = heap.oversizeCells;
272
273   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
274
275   while (p != e) {
276     char *x = *p++;
277     if (IS_CELL_ALIGNED(x) && x) {
278       for (size_t block = 0; block < usedBlocks; block++) {
279         size_t offset = x - reinterpret_cast<char *>(blocks[block]);
280         if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0)
281           goto gotGoodPointer;
282       }
283       for (size_t i = 0; i != usedOversizeCells; i++)
284         if (x == reinterpret_cast<char *>(oversizeCells[i]))
285           goto gotGoodPointer;
286       continue;
287
288 gotGoodPointer:
289       if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
290         JSCell *imp = reinterpret_cast<JSCell *>(x);
291         if (!imp->marked())
292           imp->mark();
293       }
294     }
295   }
296 }
297
298 void Collector::markCurrentThreadConservatively()
299 {
300     jmp_buf registers;
301     setjmp(registers);
302
303 #if PLATFORM(DARWIN)
304     pthread_t thread = pthread_self();
305     void *stackBase = pthread_get_stackaddr_np(thread);
306 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
307     NT_TIB *pTib;
308     __asm {
309         MOV EAX, FS:[18h]
310         MOV pTib, EAX
311     }
312     void *stackBase = (void *)pTib->StackBase;
313 #elif PLATFORM(UNIX)
314     static void *stackBase = 0;
315     static pthread_t stackThread;
316     pthread_t thread = pthread_self();
317     if (stackBase == 0 || thread != stackThread) {
318         pthread_attr_t sattr;
319 #if HAVE(PTHREAD_NP_H)
320         // e.g. on FreeBSD 5.4, neundorf@kde.org
321         pthread_attr_get_np(thread, &sattr);
322 #else
323         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
324         pthread_getattr_np(thread, &sattr);
325 #endif
326         // Should work but fails on Linux (?)
327         //  pthread_attr_getstack(&sattr, &stackBase, &stackSize);
328         pthread_attr_getstackaddr(&sattr, &stackBase);
329         assert(stackBase);
330         stackThread = thread;
331     }
332 #else
333 #error Need a way to get the stack base on this platform
334 #endif
335
336     int dummy;
337     void *stackPointer = &dummy;
338
339     markStackObjectsConservatively(stackPointer, stackBase);
340 }
341
342 #if USE(MULTIPLE_THREADS)
343
344 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
345
346 void Collector::markOtherThreadConservatively(Thread *thread)
347 {
348   thread_suspend(thread->machThread);
349
350 #if PLATFORM(X86)
351   i386_thread_state_t regs;
352   unsigned user_count = sizeof(regs)/sizeof(int);
353   thread_state_flavor_t flavor = i386_THREAD_STATE;
354 #elif PLATFORM(X86_64)
355   x86_thread_state64_t  regs;
356   unsigned user_count = x86_THREAD_STATE64_COUNT;
357   thread_state_flavor_t flavor = x86_THREAD_STATE64;
358 #elif PLATFORM(PPC)
359   ppc_thread_state_t  regs;
360   unsigned user_count = PPC_THREAD_STATE_COUNT;
361   thread_state_flavor_t flavor = PPC_THREAD_STATE;
362 #elif PLATFORM(PPC64)
363   ppc_thread_state64_t  regs;
364   unsigned user_count = PPC_THREAD_STATE64_COUNT;
365   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
366 #else
367 #error Unknown Architecture
368 #endif
369   // get the thread register state
370   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
371   
372   // scan the registers
373   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
374    
375   // scan the stack
376 #if PLATFORM(X86) && __DARWIN_UNIX03
377   markStackObjectsConservatively((void *)regs.__esp, pthread_get_stackaddr_np(thread->posixThread));
378 #elif PLATFORM(X86)
379   markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
380 #elif PLATFORM(X86_64) && __DARWIN_UNIX03
381   markStackObjectsConservatively((void *)regs.__rsp, pthread_get_stackaddr_np(thread->posixThread));
382 #elif PLATFORM(X86_64)
383   markStackObjectsConservatively((void *)regs.rsp, pthread_get_stackaddr_np(thread->posixThread));
384 #elif (PLATFORM(PPC) || PLATFORM(PPC64)) && __DARWIN_UNIX03
385   markStackObjectsConservatively((void *)regs.__r1, pthread_get_stackaddr_np(thread->posixThread));
386 #elif PLATFORM(PPC) || PLATFORM(PPC64)
387   markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
388 #else
389 #error Unknown Architecture
390 #endif
391
392   thread_resume(thread->machThread);
393 }
394
395 #endif
396
397 void Collector::markStackObjectsConservatively()
398 {
399   markCurrentThreadConservatively();
400
401 #if USE(MULTIPLE_THREADS)
402   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
403     if (thread->posixThread != pthread_self()) {
404       markOtherThreadConservatively(thread);
405     }
406   }
407 #endif
408 }
409
410 typedef HashCountedSet<JSCell *> ProtectCounts;
411
412 static ProtectCounts& protectedValues()
413 {
414     static ProtectCounts pv;
415     return pv;
416 }
417
418 void Collector::protect(JSValue *k)
419 {
420     assert(k);
421     assert(JSLock::lockCount() > 0);
422
423     if (JSImmediate::isImmediate(k))
424       return;
425
426     protectedValues().add(k->downcast());
427 }
428
429 void Collector::unprotect(JSValue *k)
430 {
431     assert(k);
432     assert(JSLock::lockCount() > 0);
433
434     if (JSImmediate::isImmediate(k))
435       return;
436
437     protectedValues().remove(k->downcast());
438 }
439
440 void Collector::markProtectedObjects()
441 {
442   ProtectCounts& pv = protectedValues();
443   ProtectCounts::iterator end = pv.end();
444   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
445     JSCell *val = it->first;
446     if (!val->marked())
447       val->mark();
448   }
449 }
450
451 bool Collector::collect()
452 {
453   assert(JSLock::lockCount() > 0);
454
455 #if USE(MULTIPLE_THREADS)
456     bool currentThreadIsMainThread = !pthread_is_threaded_np() || pthread_main_np();
457 #else
458     bool currentThreadIsMainThread = true;
459 #endif
460     
461   if (Interpreter::s_hook) {
462     Interpreter* scr = Interpreter::s_hook;
463     do {
464       scr->mark(currentThreadIsMainThread);
465       scr = scr->next;
466     } while (scr != Interpreter::s_hook);
467   }
468
469   // MARK: first mark all referenced objects recursively starting out from the set of root objects
470
471   markStackObjectsConservatively();
472   markProtectedObjects();
473   List::markProtectedLists();
474
475   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
476   
477   size_t emptyBlocks = 0;
478   size_t numLiveObjects = heap.numLiveObjects;
479
480   for (size_t block = 0; block < heap.usedBlocks; block++) {
481     CollectorBlock *curBlock = heap.blocks[block];
482
483     size_t usedCells = curBlock->usedCells;
484     CollectorCell *freeList = curBlock->freeList;
485
486     if (usedCells == CELLS_PER_BLOCK) {
487       // special case with a block where all cells are used -- testing indicates this happens often
488       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
489         CollectorCell *cell = curBlock->cells + i;
490         JSCell *imp = reinterpret_cast<JSCell *>(cell);
491         if (imp->m_marked) {
492           imp->m_marked = false;
493         } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
494           imp->~JSCell();
495           --usedCells;
496           --numLiveObjects;
497
498           // put cell on the free list
499           cell->u.freeCell.zeroIfFree = 0;
500           cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
501           freeList = cell;
502         }
503       }
504     } else {
505       size_t minimumCellsToProcess = usedCells;
506       for (size_t i = 0; i < minimumCellsToProcess; i++) {
507         CollectorCell *cell = curBlock->cells + i;
508         if (cell->u.freeCell.zeroIfFree == 0) {
509           ++minimumCellsToProcess;
510         } else {
511           JSCell *imp = reinterpret_cast<JSCell *>(cell);
512           if (imp->m_marked) {
513             imp->m_marked = false;
514           } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
515             imp->~JSCell();
516             --usedCells;
517             --numLiveObjects;
518
519             // put cell on the free list
520             cell->u.freeCell.zeroIfFree = 0;
521             cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
522             freeList = cell;
523           }
524         }
525       }
526     }
527     
528     curBlock->usedCells = usedCells;
529     curBlock->freeList = freeList;
530
531     if (usedCells == 0) {
532       emptyBlocks++;
533       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
534 #if !DEBUG_COLLECTOR
535         fastFree(curBlock);
536 #endif
537         // swap with the last block so we compact as we go
538         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
539         heap.usedBlocks--;
540         block--; // Don't move forward a step in this case
541
542         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
543           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
544           heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
545         }
546       }
547     }
548   }
549
550   if (heap.numLiveObjects != numLiveObjects)
551     heap.firstBlockWithPossibleSpace = 0;
552   
553   size_t cell = 0;
554   while (cell < heap.usedOversizeCells) {
555     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
556     
557     if (!imp->m_marked && (currentThreadIsMainThread || imp->m_destructorIsThreadSafe)) {
558       imp->~JSCell();
559 #if DEBUG_COLLECTOR
560       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
561 #else
562       fastFree(imp);
563 #endif
564
565       // swap with the last oversize cell so we compact as we go
566       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
567
568       heap.usedOversizeCells--;
569       numLiveObjects--;
570
571       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
572         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
573         heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
574       }
575     } else {
576       imp->m_marked = false;
577       cell++;
578     }
579   }
580   
581   bool deleted = heap.numLiveObjects != numLiveObjects;
582
583   heap.numLiveObjects = numLiveObjects;
584   heap.numLiveObjectsAtLastCollect = numLiveObjects;
585   
586   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
587
588   return deleted;
589 }
590
591 size_t Collector::size() 
592 {
593   return heap.numLiveObjects; 
594 }
595
596 #ifdef KJS_DEBUG_MEM
597 void Collector::finalCheck()
598 {
599 }
600 #endif
601
602 size_t Collector::numInterpreters()
603 {
604   size_t count = 0;
605   if (Interpreter::s_hook) {
606     Interpreter* scr = Interpreter::s_hook;
607     do {
608       ++count;
609       scr = scr->next;
610     } while (scr != Interpreter::s_hook);
611   }
612   return count;
613 }
614
615 size_t Collector::numProtectedObjects()
616 {
617   return protectedValues().size();
618 }
619
620 static const char *typeName(JSCell *val)
621 {
622   const char *name = "???";
623   switch (val->type()) {
624     case UnspecifiedType:
625       break;
626     case UndefinedType:
627       name = "undefined";
628       break;
629     case NullType:
630       name = "null";
631       break;
632     case BooleanType:
633       name = "boolean";
634       break;
635     case StringType:
636       name = "string";
637       break;
638     case NumberType:
639       name = "number";
640       break;
641     case ObjectType: {
642       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
643       name = info ? info->className : "Object";
644       break;
645     }
646     case GetterSetterType:
647       name = "gettersetter";
648       break;
649   }
650   return name;
651 }
652
653 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
654 {
655     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
656
657     ProtectCounts& pv = protectedValues();
658     ProtectCounts::iterator end = pv.end();
659     for (ProtectCounts::iterator it = pv.begin(); it != end; ++it)
660         counts->add(typeName(it->first));
661
662     return counts;
663 }
664
665 } // namespace KJS