Reviewed by John.
[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     ((ValueImp *)(newCell))->_flags = 0;
114     return newCell;
115   }
116   
117   // slab allocator
118   
119   CollectorBlock *targetBlock = NULL;
120   
121   int i;
122   for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
123     if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
124       targetBlock = heap.blocks[i];
125       break;
126     }
127   }
128
129   heap.firstBlockWithPossibleSpace = i;
130   
131   if (targetBlock == NULL) {
132     // didn't find one, need to allocate a new block
133     
134     if (heap.usedBlocks == heap.numBlocks) {
135       heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
136       heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
137     }
138     
139     targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
140     targetBlock->freeList = targetBlock->cells;
141     heap.blocks[heap.usedBlocks] = targetBlock;
142     heap.usedBlocks++;
143   }
144   
145   // find a free spot in the block and detach it from the free list
146   CollectorCell *newCell = targetBlock->freeList;
147
148   if (newCell->u.freeCell.next != NULL) {
149     targetBlock->freeList = newCell->u.freeCell.next;
150   } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
151     // last cell in this block
152     targetBlock->freeList = NULL;
153   } else {
154     // all next pointers are initially 0, meaning "next cell"
155     targetBlock->freeList = newCell + 1;
156   }
157
158   targetBlock->usedCells++;
159   heap.numLiveObjects++;
160
161   ((ValueImp *)(newCell))->_flags = 0;
162   return (void *)(newCell);
163 }
164
165 bool Collector::collect()
166 {
167   assert(Interpreter::lockCount() > 0);
168
169   bool deleted = false;
170
171   // MARK: first mark all referenced objects recursively
172   // starting out from the set of root objects
173   if (InterpreterImp::s_hook) {
174     InterpreterImp *scr = InterpreterImp::s_hook;
175     do {
176       //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
177       scr->mark();
178       scr = scr->next;
179     } while (scr != InterpreterImp::s_hook);
180   }
181   
182   // mark any other objects that we wouldn't delete anyway
183   for (int block = 0; block < heap.usedBlocks; block++) {
184
185     int minimumCellsToProcess = heap.blocks[block]->usedCells;
186     CollectorBlock *curBlock = heap.blocks[block];
187
188     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
189       if (minimumCellsToProcess < cell) {
190         goto skip_block_mark;
191       }
192         
193       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
194
195       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
196         
197         if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
198             ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
199           imp->mark();
200         }
201       } else {
202         minimumCellsToProcess++;
203       }
204     }
205   skip_block_mark: ;
206   }
207   
208   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
209     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
210     if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
211         ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
212       imp->mark();
213     }
214   }
215
216   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
217   
218   int emptyBlocks = 0;
219
220   for (int block = 0; block < heap.usedBlocks; block++) {
221     CollectorBlock *curBlock = heap.blocks[block];
222
223     int minimumCellsToProcess = curBlock->usedCells;
224
225     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
226       if (minimumCellsToProcess < cell) {
227         goto skip_block_sweep;
228       }
229
230       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
231
232       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0) {
233         if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
234           //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
235           // emulate destructing part of 'operator delete()'
236           imp->~ValueImp();
237           curBlock->usedCells--;
238           heap.numLiveObjects--;
239           deleted = true;
240
241           // put it on the free list
242           ((CollectorCell *)imp)->u.freeCell.zeroIfFree = 0;
243           ((CollectorCell *)imp)->u.freeCell.next = curBlock->freeList;
244           curBlock->freeList = (CollectorCell *)imp;
245
246         } else {
247           imp->_flags &= ~ValueImp::VI_MARKED;
248         }
249       } else {
250         minimumCellsToProcess++;
251       }
252     }
253
254   skip_block_sweep:
255
256     if (heap.blocks[block]->usedCells == 0) {
257       emptyBlocks++;
258       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
259 #if !DEBUG_COLLECTOR
260         free(heap.blocks[block]);
261 #endif
262         // swap with the last block so we compact as we go
263         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
264         heap.usedBlocks--;
265         block--; // Don't move forward a step in this case
266
267         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
268           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
269           heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
270         }
271       } 
272     }
273   }
274
275   if (deleted) {
276     heap.firstBlockWithPossibleSpace = 0;
277   }
278   
279   int cell = 0;
280   while (cell < heap.usedOversizeCells) {
281     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
282     
283     if (!imp->refcount && 
284         imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
285       
286       imp->~ValueImp();
287 #if DEBUG_COLLECTOR
288       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
289 #else
290       free((void *)imp);
291 #endif
292
293       // swap with the last oversize cell so we compact as we go
294       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
295
296       heap.usedOversizeCells--;
297       deleted = true;
298       heap.numLiveObjects--;
299
300       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
301         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR; 
302         heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
303       }
304
305     } else {
306       imp->_flags &= ~ValueImp::VI_MARKED;
307       cell++;
308     }
309   }
310   
311   heap.numAllocationsSinceLastCollect = 0;
312   
313   memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
314
315   return deleted;
316 }
317
318 int Collector::size() 
319 {
320   return heap.numLiveObjects; 
321 }
322
323 #ifdef KJS_DEBUG_MEM
324 void Collector::finalCheck()
325 {
326 }
327 #endif
328
329 #if APPLE_CHANGES
330
331 int Collector::numInterpreters()
332 {
333   int count = 0;
334   if (InterpreterImp::s_hook) {
335     InterpreterImp *scr = InterpreterImp::s_hook;
336     do {
337       ++count;
338       scr = scr->next;
339     } while (scr != InterpreterImp::s_hook);
340   }
341   return count;
342 }
343
344 int Collector::numGCNotAllowedObjects()
345 {
346   int count = 0;
347   for (int block = 0; block < heap.usedBlocks; block++) {
348     CollectorBlock *curBlock = heap.blocks[block];
349
350     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
351       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
352       
353       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
354           (imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
355         ++count;
356       }
357     }
358   }
359   
360   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
361     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
362     if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0) {
363       ++count;
364     }
365   }
366
367   return count;
368 }
369
370 int Collector::numReferencedObjects()
371 {
372   int count = 0;
373   for (int block = 0; block < heap.usedBlocks; block++) {
374     CollectorBlock *curBlock = heap.blocks[block];
375
376     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
377       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
378       
379       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
380           imp->refcount != 0) {
381         ++count;
382       }
383     }
384   }
385   
386   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
387     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
388       if (imp->refcount != 0) {
389         ++count;
390       }
391   }
392
393   return count;
394 }
395
396 const void *Collector::rootObjectClasses()
397 {
398   CFMutableSetRef classes = CFSetCreateMutable(NULL, 0, &kCFTypeSetCallBacks);
399   
400   for (int block = 0; block < heap.usedBlocks; block++) {
401     CollectorBlock *curBlock = heap.blocks[block];
402     for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
403       ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
404       
405       if (((CollectorCell *)imp)->u.freeCell.zeroIfFree != 0 &&
406           ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
407         const char *mangled_name = typeid(*imp).name();
408         int status;
409         char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
410         
411         CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
412         free(demangled_name);
413         CFSetAddValue(classes, className);
414         CFRelease(className);
415       }
416     }
417   }
418   
419   for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
420     ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
421     
422     if ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0) {
423       const char *mangled_name = typeid(*imp).name();
424       int status;
425       char *demangled_name = __cxxabiv1::__cxa_demangle (mangled_name, NULL, NULL, &status);
426       
427       CFStringRef className = CFStringCreateWithCString(NULL, demangled_name, kCFStringEncodingASCII);
428       free(demangled_name);
429       CFSetAddValue(classes, className);
430       CFRelease(className);
431     }
432   }
433   
434   return classes;
435 }
436
437 #endif // APPLE_CHANGES
438
439 } // namespace KJS