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