048c2aecec8bbb3c798c832e651c3236847120ee
[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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
19  *
20  */
21
22 #include "collector.h"
23
24 #include "value.h"
25 #include "internal.h"
26
27 #if APPLE_CHANGES
28 #include <CoreFoundation/CoreFoundation.h>
29 #include <cxxabi.h>
30 #endif
31
32 #include <collector.h>
33 #include <value.h>
34 #include <internal.h>
35
36 namespace KJS {
37
38 // tunable parameters
39 const int MINIMUM_CELL_SIZE = 56;
40 const int BLOCK_SIZE = (8 * 4096);
41 const int SPARE_EMPTY_BLOCKS = 2;
42 const int MIN_ARRAY_SIZE = 14;
43 const int GROWTH_FACTOR = 2;
44 const int LOW_WATER_FACTOR = 4;
45 const int ALLOCATIONS_PER_COLLECTION = 1000;
46
47 // derived constants
48 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
49 const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
50 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
51
52
53
54 struct CollectorCell {
55   union {
56     double memory[CELL_ARRAY_LENGTH];
57     struct {
58       void *zeroIfFree;
59       CollectorCell *next;
60     } freeCell;
61   } u;
62 };
63
64
65 struct CollectorBlock {
66   CollectorCell cells[CELLS_PER_BLOCK];
67   int32_t usedCells;
68   CollectorCell *freeList;
69 };
70
71 struct CollectorHeap {
72   CollectorBlock **blocks;
73   int numBlocks;
74   int usedBlocks;
75   int firstBlockWithPossibleSpace;
76   
77   CollectorCell **oversizeCells;
78   int numOversizeCells;
79   int usedOversizeCells;
80
81   int numLiveObjects;
82   int numAllocationsSinceLastCollect;
83 };
84
85 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
86
87 bool Collector::memoryFull = false;
88
89 void* Collector::allocate(size_t s)
90 {
91   assert(Interpreter::lockCount() > 0);
92
93   if (s == 0)
94     return 0L;
95   
96   // collect if needed
97   if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
98     collect();
99   }
100   
101   if (s > (unsigned)CELL_SIZE) {
102     // oversize allocator
103     if (heap.usedOversizeCells == heap.numOversizeCells) {
104       heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
105       heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
106     }
107     
108     void *newCell = malloc(s);
109     heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
110     heap.usedOversizeCells++;
111     heap.numLiveObjects++;
112
113 #if !USE_CONSERVATIVE_GC
114     ((ValueImp *)(newCell))->_flags = 0;
115 #endif
116     return newCell;
117   }
118   
119   // slab allocator
120   
121   CollectorBlock *targetBlock = NULL;
122   
123   int i;
124   for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
125     if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
126       targetBlock = heap.blocks[i];
127       break;
128     }
129   }
130
131   heap.firstBlockWithPossibleSpace = i;
132   
133   if (targetBlock == NULL) {
134     // didn't find one, need to allocate a new block
135     
136     if (heap.usedBlocks == heap.numBlocks) {
137       heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
138       heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
139     }
140     
141     targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
142     targetBlock->freeList = targetBlock->cells;
143     heap.blocks[heap.usedBlocks] = targetBlock;
144     heap.usedBlocks++;
145   }
146   
147   // find a free spot in the block and detach it from the free list
148   CollectorCell *newCell = targetBlock->freeList;
149
150   if (newCell->u.freeCell.next != NULL) {
151     targetBlock->freeList = newCell->u.freeCell.next;
152   } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
153     // last cell in this block
154     targetBlock->freeList = NULL;
155   } else {
156     // all next pointers are initially 0, meaning "next cell"
157     targetBlock->freeList = newCell + 1;
158   }
159
160   targetBlock->usedCells++;
161   heap.numLiveObjects++;
162
163 #if !USE_CONSERVATIVE_GC
164   ((ValueImp *)(newCell))->_flags = 0;
165 #endif
166   return (void *)(newCell);
167 }
168
169 #if TEST_CONSERVATIVE_GC || USE_CONSERVATIVE_GC
170
171 // cells are 8-byte aligned 
172 #define IS_POINTER_ALIGNED(p) (((int)(p) & 7) == 0)
173
174 void Collector::markStackObjectsConservatively(void *start, void *end)
175 {
176   assert(((char *)end - (char *)start) < 0x1000000);
177   assert(IS_POINTER_ALIGNED(start));
178   assert(IS_POINTER_ALIGNED(end));
179   
180   char **p = (char **)start;
181   char **e = (char **)end;
182   
183   while (p != e) {
184     char *x = *p++;
185     if (IS_POINTER_ALIGNED(x) && x) {
186       bool good = false;
187       for (int block = 0; block < heap.usedBlocks; block++) {
188         size_t offset = x - (char *)heap.blocks[block];
189         const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
190         if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0) {
191           good = true;
192           break;
193         }
194       }
195       
196       if (!good) {
197         int n = heap.usedOversizeCells;
198         for (int i = 0; i != n; i++) {
199           if (x == (char *)heap.oversizeCells[i]) {
200             good = true;
201             break;
202           }
203         }
204       }
205       
206       if (good && ((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
207         ValueImp *imp = (ValueImp *)x;
208         if (!imp->marked())
209           imp->mark();
210       }
211     }
212   }
213 }
214
215 void Collector::markStackObjectsConservatively()
216 {
217   jmp_buf registers;
218   setjmp(registers);
219
220   pthread_t thread = pthread_self();
221   void *stackBase = pthread_get_stackaddr_np(thread);
222   void *stackPointer;
223   asm("mr %0,r1" : "=r" (stackPointer));
224   markStackObjectsConservatively(stackPointer, stackBase);
225 }
226
227 void Collector::markProtectedObjects()
228 {
229   for (int i = 0; i < ProtectedValues::_tableSize; i++) {
230     ValueImp *val = ProtectedValues::_table[i].key;
231     if (val && !val->marked()) {
232       val->mark();
233     }
234   }
235 }
236
237 #endif
238
239 bool Collector::collect()
240 {
241   assert(Interpreter::lockCount() > 0);
242
243   bool deleted = false;
244
245 #if TEST_CONSERVATIVE_GC
246   // CONSERVATIVE MARK: mark the root set using conservative GC bit (will compare later)
247   ValueImp::useConservativeMark(true);
248 #endif
249
250 #if USE_CONSERVATIVE_GC || TEST_CONSERVATIVE_GC
251   if (InterpreterImp::s_hook) {
252     InterpreterImp *scr = InterpreterImp::s_hook;
253     do {
254       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
255       scr->mark();
256       scr = scr->next;
257     } while (scr != InterpreterImp::s_hook);
258   }
259
260   markStackObjectsConservatively();
261   markProtectedObjects();
262 #endif
263
264 #if TEST_CONSERVATIVE_GC
265   ValueImp::useConservativeMark(false);
266 #endif
267
268 #if !USE_CONSERVATIVE_GC
269   // MARK: first mark all referenced objects recursively
270   // starting out from the set of root objects
271   if (InterpreterImp::s_hook) {
272     InterpreterImp *scr = InterpreterImp::s_hook;
273     do {
274       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
275       scr->mark();
276       scr = scr->next;
277     } while (scr != InterpreterImp::s_hook);
278   }
279   
280   // mark any other objects that we wouldn't delete anyway
281   for (int block = 0; block < heap.usedBlocks; block++) {
282
283     int minimumCellsToProcess = heap.blocks[block]->usedCells;
284     CollectorBlock *curBlock = heap.blocks[block];
285
286     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
287       if (minimumCellsToProcess < cell) {
288         goto skip_block_mark;
289       }
290         
291       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
292
293       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
294         
295         if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
296             ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
297           imp->mark();
298         }
299       } else {
300         minimumCellsToProcess++;
301       }
302     }
303   skip_block_mark: ;
304   }
305   
306   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
307     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
308     if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
309         ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
310       imp->mark();
311     }
312   }
313 #endif
314
315   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
316   
317   int emptyBlocks = 0;
318
319   for (int block = 0; block < heap.usedBlocks; block++) {
320     CollectorBlock *curBlock = heap.blocks[block];
321
322     int minimumCellsToProcess = curBlock->usedCells;
323
324     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
325       if (minimumCellsToProcess < cell) {
326         goto skip_block_sweep;
327       }
328
329       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
330
331       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
332 #if USE_CONSERVATIVE_GC
333         if (!imp->_marked)
334 #else
335         if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED))
336 #endif
337         {
338           //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
339           // emulate destructing part of 'operator delete()'
340           imp->~ValueImp();
341           curBlock->usedCells--;
342           heap.numLiveObjects--;
343           deleted = true;
344
345           // put it on the free list
346           ((CollectorCell *)imp)->u.freeCell.zeroIfFree = 0;
347           ((CollectorCell *)imp)->u.freeCell.next = curBlock->freeList;
348           curBlock->freeList = (CollectorCell *)imp;
349
350         } else {
351 #if USE_CONSERVATIVE_GC
352           imp->_marked = 0;
353 #elif TEST_CONSERVATIVE_GC
354           imp->_flags &= ~(ValueImp::VI_MARKED | ValueImp::VI_CONSERVATIVE_MARKED);
355 #else
356           imp->_flags &= ~ValueImp::VI_MARKED;
357 #endif
358         }
359       } else {
360         minimumCellsToProcess++;
361       }
362     }
363
364   skip_block_sweep:
365
366     if (heap.blocks[block]->usedCells == 0) {
367       emptyBlocks++;
368       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
369 #if !DEBUG_COLLECTOR
370         free(heap.blocks[block]);
371 #endif
372         // swap with the last block so we compact as we go
373         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
374         heap.usedBlocks--;
375         block--; // Don't move forward a step in this case
376
377         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
378           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
379           heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
380         }
381       } 
382     }
383   }
384
385   if (deleted) {
386     heap.firstBlockWithPossibleSpace = 0;
387   }
388   
389   int cell = 0;
390   while (cell < heap.usedOversizeCells) {
391     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
392     
393 #if USE_CONSERVATIVE_GC
394     if (!imp->_marked) {
395 #else
396     if (!imp->refcount && 
397         imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
398 #endif
399
400       imp->~ValueImp();
401 #if DEBUG_COLLECTOR
402       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
403 #else
404       free((void *)imp);
405 #endif
406
407       // swap with the last oversize cell so we compact as we go
408       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
409
410       heap.usedOversizeCells--;
411       deleted = true;
412       heap.numLiveObjects--;
413
414       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
415         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
416         heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
417       }
418
419     } else {
420 #if USE_CONSERVATIVE_GC
421       imp->_marked = 0;
422 #elif TEST_CONSERVATIVE_GC
423       imp->_flags &= ~(ValueImp::VI_MARKED | ValueImp::VI_CONSERVATIVE_MARKED);
424 #else
425       imp->_flags &= ~ValueImp::VI_MARKED;
426 #endif
427       cell++;
428     }
429   }
430   
431   heap.numAllocationsSinceLastCollect = 0;
432   
433   memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
434
435   return deleted;
436 }
437
438 int Collector::size() 
439 {
440   return heap.numLiveObjects; 
441 }
442
443 #ifdef KJS_DEBUG_MEM
444 void Collector::finalCheck()
445 {
446 }
447 #endif
448
449 #if APPLE_CHANGES
450
451 int Collector::numInterpreters()
452 {
453   int count = 0;
454   if (InterpreterImp::s_hook) {
455     InterpreterImp *scr = InterpreterImp::s_hook;
456     do {
457       ++count;
458       scr = scr->next;
459     } while (scr != InterpreterImp::s_hook);
460   }
461   return count;
462 }
463
464 int Collector::numGCNotAllowedObjects()
465 {
466   int count = 0;
467 #if !USE_CONSERVATIVE_GC
468   for (int block = 0; block < heap.usedBlocks; block++) {
469     CollectorBlock *curBlock = heap.blocks[block];
470
471     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
472       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
473       
474       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
475           (imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
476         ++count;
477       }
478     }
479   }
480   
481   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
482     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
483     if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
484       ++count;
485     }
486   }
487 #endif
488
489   return count;
490 }
491
492 int Collector::numReferencedObjects()
493 {
494   int count = 0;
495
496 #if USE_CONSERVATIVE_GC
497   for (int i = 0; i < ProtectedValues::_tableSize; i++) {
498     ValueImp *val = ProtectedValues::_table[i].key;
499     if (val) {
500       ++count;
501     }
502   }
503
504 #else
505
506   for (int block = 0; block < heap.usedBlocks; block++) {
507     CollectorBlock *curBlock = heap.blocks[block];
508
509     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
510       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
511       
512       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
513           imp->refcount != 0) {
514         ++count;
515       }
516     }
517   }
518   
519   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
520     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
521       if (imp->refcount != 0) {
522         ++count;
523       }
524   }
525 #endif
526
527   return count;
528 }
529
530 const void *Collector::rootObjectClasses()
531 {
532   CFMutableSetRef classes = CFSetCreateMutable(NULL, 0, &kCFTypeSetCallBacks);
533
534 #if USE_CONSERVATIVE_GC
535   for (int i = 0; i < ProtectedValues::_tableSize; i++) {
536     ValueImp *val = ProtectedValues::_table[i].key;
537     if (val) {
538       const char *mangled_name = typeid(*val).name();
539       int status;
540       char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
541       
542       CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
543       free(demangled_name);
544       CFSetAddValue(classes, className);
545       CFRelease(className);
546     }
547   }
548 #else
549   for (int block = 0; block < heap.usedBlocks; block++) {
550     CollectorBlock *curBlock = heap.blocks[block];
551     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
552       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
553       
554       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
555           ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
556         const char *mangled_name = typeid(*imp).name();
557         int status;
558         char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
559         
560         CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
561         free(demangled_name);
562         CFSetAddValue(classes, className);
563         CFRelease(className);
564       }
565     }
566   }
567   
568   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
569     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
570     
571     if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0) {
572       const char *mangled_name = typeid(*imp).name();
573       int status;
574       char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
575       
576       CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
577       free(demangled_name);
578       CFSetAddValue(classes, className);
579       CFRelease(className);
580     }
581   }
582 #endif
583   
584   return classes;
585 }
586
587 #endif // APPLE_CHANGES
588
589 } // namespace KJS