Reviewed by Maciej
[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     void *stackBase = 0;
317     pthread_attr_t sattr;
318 #ifdef 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(pthread_self(), &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 #endif
330
331     int dummy;
332     void *stackPointer = &dummy;
333
334     markStackObjectsConservatively(stackPointer, stackBase);
335 }
336
337 #if KJS_MULTIPLE_THREADS
338
339 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
340
341 void Collector::markOtherThreadConservatively(Thread *thread)
342 {
343   thread_suspend(thread->machThread);
344
345 #if __i386__
346   i386_thread_state_t regs;
347   unsigned user_count = sizeof(regs)/sizeof(int);
348   thread_state_flavor_t flavor = i386_THREAD_STATE;
349 #elif __ppc__
350   ppc_thread_state_t  regs;
351   unsigned user_count = PPC_THREAD_STATE_COUNT;
352   thread_state_flavor_t flavor = PPC_THREAD_STATE;
353 #elif __ppc64__
354   ppc_thread_state64_t  regs;
355   unsigned user_count = PPC_THREAD_STATE64_COUNT;
356   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
357 #else
358 #error Unknown Architecture
359 #endif
360   // get the thread register state
361   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
362   
363   // scan the registers
364   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
365   
366   // scan the stack
367 #if __i386__
368   markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
369 #elif defined(__ppc__) || defined(__ppc64__)
370   markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
371 #else
372 #error Unknown Architecture
373 #endif
374
375   thread_resume(thread->machThread);
376 }
377
378 #endif
379
380 void Collector::markStackObjectsConservatively()
381 {
382   markCurrentThreadConservatively();
383
384 #if KJS_MULTIPLE_THREADS
385   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
386     if (thread->posixThread != pthread_self()) {
387       markOtherThreadConservatively(thread);
388     }
389   }
390 #endif
391 }
392
393 typedef HashCountedSet<JSCell *, PointerHash<JSCell *> > ProtectCounts;
394
395 static ProtectCounts& protectedValues()
396 {
397     static ProtectCounts pv;
398     return pv;
399 }
400
401 void Collector::protect(JSValue *k)
402 {
403     assert(k);
404     assert(JSLock::lockCount() > 0);
405
406     if (SimpleNumber::is(k))
407       return;
408
409     protectedValues().insert(k->downcast());
410 }
411
412 void Collector::unprotect(JSValue *k)
413 {
414     assert(k);
415     assert(JSLock::lockCount() > 0);
416
417     if (SimpleNumber::is(k))
418       return;
419
420     protectedValues().remove(k->downcast());
421 }
422
423 void Collector::markProtectedObjects()
424 {
425   ProtectCounts& pv = protectedValues();
426   ProtectCounts::iterator end = pv.end();
427   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
428     JSCell *val = it->first;
429     if (!val->marked())
430       val->mark();
431   }
432 }
433
434 bool Collector::collect()
435 {
436   assert(JSLock::lockCount() > 0);
437
438   if (InterpreterImp::s_hook) {
439     InterpreterImp *scr = InterpreterImp::s_hook;
440     do {
441       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
442       scr->mark();
443       scr = scr->next;
444     } while (scr != InterpreterImp::s_hook);
445   }
446   ConstantValues::mark();
447
448   // MARK: first mark all referenced objects recursively starting out from the set of root objects
449
450   markStackObjectsConservatively();
451   markProtectedObjects();
452   List::markProtectedLists();
453
454   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
455   
456   size_t emptyBlocks = 0;
457   size_t numLiveObjects = heap.numLiveObjects;
458
459   for (size_t block = 0; block < heap.usedBlocks; block++) {
460     CollectorBlock *curBlock = heap.blocks[block];
461
462     size_t usedCells = curBlock->usedCells;
463     CollectorCell *freeList = curBlock->freeList;
464
465     if (usedCells == CELLS_PER_BLOCK) {
466       // special case with a block where all cells are used -- testing indicates this happens often
467       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
468         CollectorCell *cell = curBlock->cells + i;
469         JSCell *imp = reinterpret_cast<JSCell *>(cell);
470         if (imp->m_marked) {
471           imp->m_marked = false;
472         } else {
473           imp->~JSCell();
474           --usedCells;
475           --numLiveObjects;
476
477           // put cell on the free list
478           cell->u.freeCell.zeroIfFree = 0;
479           cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
480           freeList = cell;
481         }
482       }
483     } else {
484       size_t minimumCellsToProcess = usedCells;
485       for (size_t i = 0; i < minimumCellsToProcess; i++) {
486         CollectorCell *cell = curBlock->cells + i;
487         if (cell->u.freeCell.zeroIfFree == 0) {
488           ++minimumCellsToProcess;
489         } else {
490           JSCell *imp = reinterpret_cast<JSCell *>(cell);
491           if (imp->m_marked) {
492             imp->m_marked = false;
493           } else {
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       }
505     }
506     
507     curBlock->usedCells = usedCells;
508     curBlock->freeList = freeList;
509
510     if (usedCells == 0) {
511       emptyBlocks++;
512       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
513 #if !DEBUG_COLLECTOR
514         fastFree(curBlock);
515 #endif
516         // swap with the last block so we compact as we go
517         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
518         heap.usedBlocks--;
519         block--; // Don't move forward a step in this case
520
521         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
522           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
523           heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
524         }
525       }
526     }
527   }
528
529   if (heap.numLiveObjects != numLiveObjects)
530     heap.firstBlockWithPossibleSpace = 0;
531   
532   size_t cell = 0;
533   while (cell < heap.usedOversizeCells) {
534     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
535     
536     if (!imp->m_marked) {
537       imp->~JSCell();
538 #if DEBUG_COLLECTOR
539       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
540 #else
541       fastFree(imp);
542 #endif
543
544       // swap with the last oversize cell so we compact as we go
545       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
546
547       heap.usedOversizeCells--;
548       numLiveObjects--;
549
550       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
551         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
552         heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
553       }
554     } else {
555       imp->m_marked = false;
556       cell++;
557     }
558   }
559   
560   bool deleted = heap.numLiveObjects != numLiveObjects;
561
562   heap.numLiveObjects = numLiveObjects;
563   heap.numLiveObjectsAtLastCollect = numLiveObjects;
564   
565   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
566
567   return deleted;
568 }
569
570 size_t Collector::size() 
571 {
572   return heap.numLiveObjects; 
573 }
574
575 #ifdef KJS_DEBUG_MEM
576 void Collector::finalCheck()
577 {
578 }
579 #endif
580
581 size_t Collector::numInterpreters()
582 {
583   size_t count = 0;
584   if (InterpreterImp::s_hook) {
585     InterpreterImp *scr = InterpreterImp::s_hook;
586     do {
587       ++count;
588       scr = scr->next;
589     } while (scr != InterpreterImp::s_hook);
590   }
591   return count;
592 }
593
594 size_t Collector::numGCNotAllowedObjects()
595 {
596   return 0;
597 }
598
599 size_t Collector::numReferencedObjects()
600 {
601   return protectedValues().size();
602 }
603
604 #if __APPLE__
605
606 static const char *className(JSCell *val)
607 {
608   const char *name = "???";
609   switch (val->type()) {
610     case UnspecifiedType:
611       break;
612     case UndefinedType:
613       name = "undefined";
614       break;
615     case NullType:
616       name = "null";
617       break;
618     case BooleanType:
619       name = "boolean";
620       break;
621     case StringType:
622       name = "string";
623       break;
624     case NumberType:
625       name = "number";
626       break;
627     case ObjectType: {
628       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
629       name = info ? info->className : "Object";
630       break;
631     }
632     case GetterSetterType:
633       name = "gettersetter";
634       break;
635   }
636   return name;
637 }
638
639 const void *Collector::rootObjectClasses()
640 {
641   // FIXME: this should be a HashSet (or maybe even CountedHashSet)
642   CFMutableSetRef classes = CFSetCreateMutable(NULL, 0, &kCFTypeSetCallBacks);
643
644   ProtectCounts& pv = protectedValues();
645   ProtectCounts::iterator end = pv.end();
646   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
647     JSCell *val = it->first;
648     CFStringRef name = CFStringCreateWithCString(NULL, className(val), kCFStringEncodingASCII);
649     CFSetAddValue(classes, name);
650     CFRelease(name);
651   }
652
653   return classes;
654 }
655
656 #endif
657
658 } // namespace KJS