Reviewed by Maciej and Darin.
[WebKit-https.git] / JavaScriptCore / kjs / collector.cpp
1 // -*- c-basic-offset: 2 -*-
2 /*
3  *  This file is part of the KDE libraries
4  *  Copyright (C) 2003 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 Steet, Fifth Floor, Boston, MA  02110-1301  USA
19  *
20  */
21
22 #include "config.h"
23 #include "collector.h"
24
25 #include <kxmlcore/FastMalloc.h>
26 #include <kxmlcore/FastMallocInternal.h>
27 #include <kxmlcore/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 __APPLE__
36
37 #include <CoreFoundation/CoreFoundation.h>
38 #include <pthread.h>
39 #include <mach/mach_port.h>
40 #include <mach/task.h>
41 #include <mach/thread_act.h>
42
43 #elif WIN32
44
45 #undef ERROR
46 #include <windows.h>
47
48 #else
49
50 #include <pthread.h>
51
52 #ifdef HAVE_PTHREAD_NP_H
53
54 #include <pthread_np.h>
55
56 #endif
57
58 #endif
59
60 using std::max;
61
62 namespace KJS {
63
64 // tunable parameters
65 const size_t MINIMUM_CELL_SIZE = 56;
66 const size_t BLOCK_SIZE = (8 * 4096);
67 const size_t SPARE_EMPTY_BLOCKS = 2;
68 const size_t MIN_ARRAY_SIZE = 14;
69 const size_t GROWTH_FACTOR = 2;
70 const size_t LOW_WATER_FACTOR = 4;
71 const size_t ALLOCATIONS_PER_COLLECTION = 1000;
72
73 // derived constants
74 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
75 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
76 const size_t CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
77
78
79
80 struct CollectorCell {
81   union {
82     double memory[CELL_ARRAY_LENGTH];
83     struct {
84       void *zeroIfFree;
85       ptrdiff_t next;
86     } freeCell;
87   } u;
88 };
89
90
91 struct CollectorBlock {
92   CollectorCell cells[CELLS_PER_BLOCK];
93   uint32_t usedCells;
94   CollectorCell *freeList;
95 };
96
97 struct CollectorHeap {
98   CollectorBlock **blocks;
99   size_t numBlocks;
100   size_t usedBlocks;
101   size_t firstBlockWithPossibleSpace;
102   
103   CollectorCell **oversizeCells;
104   size_t numOversizeCells;
105   size_t usedOversizeCells;
106
107   size_t numLiveObjects;
108   size_t numLiveObjectsAtLastCollect;
109 };
110
111 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
112
113 bool Collector::memoryFull = false;
114
115 void* Collector::allocate(size_t s)
116 {
117   assert(JSLock::lockCount() > 0);
118
119   // collect if needed
120   size_t numLiveObjects = heap.numLiveObjects;
121   if (numLiveObjects - heap.numLiveObjectsAtLastCollect >= ALLOCATIONS_PER_COLLECTION) {
122     collect();
123     numLiveObjects = heap.numLiveObjects;
124   }
125   
126   if (s > CELL_SIZE) {
127     // oversize allocator
128
129     size_t usedOversizeCells = heap.usedOversizeCells;
130     size_t numOversizeCells = heap.numOversizeCells;
131
132     if (usedOversizeCells == numOversizeCells) {
133       numOversizeCells = max(MIN_ARRAY_SIZE, numOversizeCells * GROWTH_FACTOR);
134       heap.numOversizeCells = numOversizeCells;
135       heap.oversizeCells = static_cast<CollectorCell **>(fastRealloc(heap.oversizeCells, numOversizeCells * sizeof(CollectorCell *)));
136     }
137     
138     void *newCell = fastMalloc(s);
139     heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
140     heap.usedOversizeCells = usedOversizeCells + 1;
141     heap.numLiveObjects = numLiveObjects + 1;
142
143     return newCell;
144   }
145   
146   // slab allocator
147   
148   size_t usedBlocks = heap.usedBlocks;
149
150   size_t i = heap.firstBlockWithPossibleSpace;
151   CollectorBlock *targetBlock;
152   size_t targetBlockUsedCells;
153   if (i != usedBlocks) {
154     targetBlock = heap.blocks[i];
155     targetBlockUsedCells = targetBlock->usedCells;
156     assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
157     while (targetBlockUsedCells == CELLS_PER_BLOCK) {
158       if (++i == usedBlocks)
159         goto allocateNewBlock;
160       targetBlock = heap.blocks[i];
161       targetBlockUsedCells = targetBlock->usedCells;
162       assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
163     }
164     heap.firstBlockWithPossibleSpace = i;
165   } else {
166 allocateNewBlock:
167     // didn't find one, need to allocate a new block
168     size_t numBlocks = heap.numBlocks;
169     if (usedBlocks == numBlocks) {
170       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
171       heap.numBlocks = numBlocks;
172       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
173     }
174
175     targetBlock = static_cast<CollectorBlock *>(fastCalloc(1, sizeof(CollectorBlock)));
176     targetBlock->freeList = targetBlock->cells;
177     targetBlockUsedCells = 0;
178     heap.blocks[usedBlocks] = targetBlock;
179     heap.usedBlocks = usedBlocks + 1;
180     heap.firstBlockWithPossibleSpace = usedBlocks;
181   }
182   
183   // find a free spot in the block and detach it from the free list
184   CollectorCell *newCell = targetBlock->freeList;
185   
186   // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized
187   // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
188   targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);
189
190   targetBlock->usedCells = targetBlockUsedCells + 1;
191   heap.numLiveObjects = numLiveObjects + 1;
192
193   return newCell;
194 }
195
196 #if KJS_MULTIPLE_THREADS
197
198 struct Collector::Thread {
199   Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
200   Thread *next;
201   pthread_t posixThread;
202   mach_port_t machThread;
203 };
204
205 pthread_key_t registeredThreadKey;
206 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
207 Collector::Thread *registeredThreads;
208   
209 static void destroyRegisteredThread(void *data) 
210 {
211   Collector::Thread *thread = (Collector::Thread *)data;
212
213   if (registeredThreads == thread) {
214     registeredThreads = registeredThreads->next;
215   } else {
216     Collector::Thread *last = registeredThreads;
217     for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
218       if (t == thread) {
219         last->next = t->next;
220           break;
221       }
222       last = t;
223     }
224   }
225
226   delete thread;
227 }
228
229 static void initializeRegisteredThreadKey()
230 {
231   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
232 }
233
234 void Collector::registerThread()
235 {
236   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
237
238   if (!pthread_getspecific(registeredThreadKey)) {
239     pthread_t pthread = pthread_self();
240     KXMLCore::fastMallocRegisterThread(pthread);
241     Collector::Thread *thread = new Collector::Thread(pthread, pthread_mach_thread_np(pthread));
242     thread->next = registeredThreads;
243     registeredThreads = thread;
244     pthread_setspecific(registeredThreadKey, thread);
245   }
246 }
247
248 #endif
249
250 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
251
252 // cells are 8-byte aligned
253 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
254
255 void Collector::markStackObjectsConservatively(void *start, void *end)
256 {
257   if (start > end) {
258     void *tmp = start;
259     start = end;
260     end = tmp;
261   }
262
263   assert(((char *)end - (char *)start) < 0x1000000);
264   assert(IS_POINTER_ALIGNED(start));
265   assert(IS_POINTER_ALIGNED(end));
266   
267   char **p = (char **)start;
268   char **e = (char **)end;
269   
270   size_t usedBlocks = heap.usedBlocks;
271   CollectorBlock **blocks = heap.blocks;
272   size_t usedOversizeCells = heap.usedOversizeCells;
273   CollectorCell **oversizeCells = heap.oversizeCells;
274
275   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
276
277   while (p != e) {
278     char *x = *p++;
279     if (IS_CELL_ALIGNED(x) && x) {
280       for (size_t block = 0; block < usedBlocks; block++) {
281         size_t offset = x - reinterpret_cast<char *>(blocks[block]);
282         if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0)
283           goto gotGoodPointer;
284       }
285       for (size_t i = 0; i != usedOversizeCells; i++)
286         if (x == reinterpret_cast<char *>(oversizeCells[i]))
287           goto gotGoodPointer;
288       continue;
289
290 gotGoodPointer:
291       if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
292         JSCell *imp = reinterpret_cast<JSCell *>(x);
293         if (!imp->marked())
294           imp->mark();
295       }
296     }
297   }
298 }
299
300 void Collector::markCurrentThreadConservatively()
301 {
302     jmp_buf registers;
303     setjmp(registers);
304
305 #if __APPLE__
306     pthread_t thread = pthread_self();
307     void *stackBase = pthread_get_stackaddr_np(thread);
308 #elif WIN32
309     NT_TIB *pTib;
310     __asm {
311         MOV EAX, FS:[18h]
312         MOV pTib, EAX
313     }
314     void *stackBase = (void *)pTib->StackBase;
315 #else
316     static void *stackBase = 0;
317     static pthread_t stackThread;
318     pthread_t thread = pthread_self();
319     if (stackBase == 0 || thread != stackThread) {
320         pthread_attr_t sattr;
321 #ifdef HAVE_PTHREAD_NP_H
322         // e.g. on FreeBSD 5.4, neundorf@kde.org
323         pthread_attr_get_np(thread, &sattr);
324 #else
325         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
326         pthread_getattr_np(thread, &sattr);
327 #endif
328         // Should work but fails on Linux (?)
329         //  pthread_attr_getstack(&sattr, &stackBase, &stackSize);
330         pthread_attr_getstackaddr(&sattr, &stackBase);
331         assert(stackBase);
332         stackThread = thread;
333     }
334 #endif
335
336     int dummy;
337     void *stackPointer = &dummy;
338
339     markStackObjectsConservatively(stackPointer, stackBase);
340 }
341
342 #if KJS_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 KJS_CPU_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 KJS_CPU_PPC
355   ppc_thread_state_t  regs;
356   unsigned user_count = PPC_THREAD_STATE_COUNT;
357   thread_state_flavor_t flavor = PPC_THREAD_STATE;
358 #elif KJS_CPU_PPC64
359   ppc_thread_state64_t  regs;
360   unsigned user_count = PPC_THREAD_STATE64_COUNT;
361   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
362 #else
363 #error Unknown Architecture
364 #endif
365   // get the thread register state
366   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
367   
368   // scan the registers
369   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
370   
371   // scan the stack
372 #if KJS_CPU_X86
373   markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
374 #elif KJS_CPU_PPC || KJS_CPU_PPC64
375   markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
376 #else
377 #error Unknown Architecture
378 #endif
379
380   thread_resume(thread->machThread);
381 }
382
383 #endif
384
385 void Collector::markStackObjectsConservatively()
386 {
387   markCurrentThreadConservatively();
388
389 #if KJS_MULTIPLE_THREADS
390   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
391     if (thread->posixThread != pthread_self()) {
392       markOtherThreadConservatively(thread);
393     }
394   }
395 #endif
396 }
397
398 typedef HashCountedSet<JSCell *, PointerHash<JSCell *> > ProtectCounts;
399
400 static ProtectCounts& protectedValues()
401 {
402     static ProtectCounts pv;
403     return pv;
404 }
405
406 void Collector::protect(JSValue *k)
407 {
408     assert(k);
409     assert(JSLock::lockCount() > 0);
410
411     if (SimpleNumber::is(k))
412       return;
413
414     protectedValues().insert(k->downcast());
415 }
416
417 void Collector::unprotect(JSValue *k)
418 {
419     assert(k);
420     assert(JSLock::lockCount() > 0);
421
422     if (SimpleNumber::is(k))
423       return;
424
425     protectedValues().remove(k->downcast());
426 }
427
428 void Collector::markProtectedObjects()
429 {
430   ProtectCounts& pv = protectedValues();
431   ProtectCounts::iterator end = pv.end();
432   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
433     JSCell *val = it->first;
434     if (!val->marked())
435       val->mark();
436   }
437 }
438
439 bool Collector::collect()
440 {
441   assert(JSLock::lockCount() > 0);
442
443   if (InterpreterImp::s_hook) {
444     InterpreterImp *scr = InterpreterImp::s_hook;
445     do {
446       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
447       scr->mark();
448       scr = scr->next;
449     } while (scr != InterpreterImp::s_hook);
450   }
451   ConstantValues::mark();
452
453   // MARK: first mark all referenced objects recursively starting out from the set of root objects
454
455   markStackObjectsConservatively();
456   markProtectedObjects();
457   List::markProtectedLists();
458
459   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
460   
461   size_t emptyBlocks = 0;
462   size_t numLiveObjects = heap.numLiveObjects;
463
464   for (size_t block = 0; block < heap.usedBlocks; block++) {
465     CollectorBlock *curBlock = heap.blocks[block];
466
467     size_t usedCells = curBlock->usedCells;
468     CollectorCell *freeList = curBlock->freeList;
469
470     if (usedCells == CELLS_PER_BLOCK) {
471       // special case with a block where all cells are used -- testing indicates this happens often
472       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
473         CollectorCell *cell = curBlock->cells + i;
474         JSCell *imp = reinterpret_cast<JSCell *>(cell);
475         if (imp->m_marked) {
476           imp->m_marked = false;
477         } else {
478           imp->~JSCell();
479           --usedCells;
480           --numLiveObjects;
481
482           // put cell on the free list
483           cell->u.freeCell.zeroIfFree = 0;
484           cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
485           freeList = cell;
486         }
487       }
488     } else {
489       size_t minimumCellsToProcess = usedCells;
490       for (size_t i = 0; i < minimumCellsToProcess; i++) {
491         CollectorCell *cell = curBlock->cells + i;
492         if (cell->u.freeCell.zeroIfFree == 0) {
493           ++minimumCellsToProcess;
494         } else {
495           JSCell *imp = reinterpret_cast<JSCell *>(cell);
496           if (imp->m_marked) {
497             imp->m_marked = false;
498           } else {
499             imp->~JSCell();
500             --usedCells;
501             --numLiveObjects;
502
503             // put cell on the free list
504             cell->u.freeCell.zeroIfFree = 0;
505             cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
506             freeList = cell;
507           }
508         }
509       }
510     }
511     
512     curBlock->usedCells = usedCells;
513     curBlock->freeList = freeList;
514
515     if (usedCells == 0) {
516       emptyBlocks++;
517       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
518 #if !DEBUG_COLLECTOR
519         fastFree(curBlock);
520 #endif
521         // swap with the last block so we compact as we go
522         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
523         heap.usedBlocks--;
524         block--; // Don't move forward a step in this case
525
526         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
527           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
528           heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
529         }
530       }
531     }
532   }
533
534   if (heap.numLiveObjects != numLiveObjects)
535     heap.firstBlockWithPossibleSpace = 0;
536   
537   size_t cell = 0;
538   while (cell < heap.usedOversizeCells) {
539     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
540     
541     if (!imp->m_marked) {
542       imp->~JSCell();
543 #if DEBUG_COLLECTOR
544       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
545 #else
546       fastFree(imp);
547 #endif
548
549       // swap with the last oversize cell so we compact as we go
550       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
551
552       heap.usedOversizeCells--;
553       numLiveObjects--;
554
555       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
556         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
557         heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
558       }
559     } else {
560       imp->m_marked = false;
561       cell++;
562     }
563   }
564   
565   bool deleted = heap.numLiveObjects != numLiveObjects;
566
567   heap.numLiveObjects = numLiveObjects;
568   heap.numLiveObjectsAtLastCollect = numLiveObjects;
569   
570   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
571
572   return deleted;
573 }
574
575 size_t Collector::size() 
576 {
577   return heap.numLiveObjects; 
578 }
579
580 #ifdef KJS_DEBUG_MEM
581 void Collector::finalCheck()
582 {
583 }
584 #endif
585
586 size_t Collector::numInterpreters()
587 {
588   size_t count = 0;
589   if (InterpreterImp::s_hook) {
590     InterpreterImp *scr = InterpreterImp::s_hook;
591     do {
592       ++count;
593       scr = scr->next;
594     } while (scr != InterpreterImp::s_hook);
595   }
596   return count;
597 }
598
599 size_t Collector::numGCNotAllowedObjects()
600 {
601   return 0;
602 }
603
604 size_t Collector::numReferencedObjects()
605 {
606   return protectedValues().size();
607 }
608
609 #if __APPLE__
610
611 static const char *className(JSCell *val)
612 {
613   const char *name = "???";
614   switch (val->type()) {
615     case UnspecifiedType:
616       break;
617     case UndefinedType:
618       name = "undefined";
619       break;
620     case NullType:
621       name = "null";
622       break;
623     case BooleanType:
624       name = "boolean";
625       break;
626     case StringType:
627       name = "string";
628       break;
629     case NumberType:
630       name = "number";
631       break;
632     case ObjectType: {
633       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
634       name = info ? info->className : "Object";
635       break;
636     }
637     case GetterSetterType:
638       name = "gettersetter";
639       break;
640   }
641   return name;
642 }
643
644 const void *Collector::rootObjectClasses()
645 {
646   // FIXME: this should be a HashSet (or maybe even CountedHashSet)
647   CFMutableSetRef classes = CFSetCreateMutable(NULL, 0, &kCFTypeSetCallBacks);
648
649   ProtectCounts& pv = protectedValues();
650   ProtectCounts::iterator end = pv.end();
651   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
652     JSCell *val = it->first;
653     CFStringRef name = CFStringCreateWithCString(NULL, className(val), kCFStringEncodingASCII);
654     CFSetAddValue(classes, name);
655     CFRelease(name);
656   }
657
658   return classes;
659 }
660
661 #endif
662
663 } // namespace KJS