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