21 #include "collector.h"
29 #define MAX(a,b) ((a) > (b) ? (a) : (b))
35 const int MINIMUM_CELL_SIZE = 56;
36 const int BLOCK_SIZE = (8 * 4096);
37 const int SPARE_EMPTY_BLOCKS = 2;
38 const int MIN_ARRAY_SIZE = 14;
39 const int GROWTH_FACTOR = 2;
40 const int LOW_WATER_FACTOR = 4;
41 const int ALLOCATIONS_PER_COLLECTION = 1000;
44 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE /
sizeof(double)) + (MINIMUM_CELL_SIZE %
sizeof(double) != 0 ?
sizeof(
double) : 0);
45 const int CELL_SIZE = CELL_ARRAY_LENGTH *
sizeof(double);
46 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 -
sizeof(int) * 8 -
sizeof(
void *) * 8) / (CELL_SIZE * 8));
50 struct CollectorCell {
51 double memory[CELL_ARRAY_LENGTH];
55 struct CollectorBlock {
56 CollectorCell cells[CELLS_PER_BLOCK];
58 CollectorCell *freeList;
61 struct CollectorHeap {
62 CollectorBlock **blocks;
65 int firstBlockWithPossibleSpace;
67 CollectorCell **oversizeCells;
69 int usedOversizeCells;
72 int numAllocationsSinceLastCollect;
75 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
77 bool Collector::memoryFull =
false;
85 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
89 if (s > (
unsigned)CELL_SIZE) {
91 if (heap.usedOversizeCells == heap.numOversizeCells) {
92 heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
93 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells *
sizeof(CollectorCell *));
96 void *newCell = malloc(s);
97 heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
98 heap.usedOversizeCells++;
99 heap.numLiveObjects++;
101 ((
ValueImp *)(newCell))->_flags = 0;
107 CollectorBlock *targetBlock = NULL;
110 for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
111 if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
112 targetBlock = heap.blocks[i];
117 heap.firstBlockWithPossibleSpace = i;
119 if (targetBlock == NULL) {
122 if (heap.usedBlocks == heap.numBlocks) {
123 static const size_t maxNumBlocks = ULONG_MAX /
sizeof(CollectorBlock*) / GROWTH_FACTOR;
124 if ((
size_t)heap.numBlocks > maxNumBlocks)
126 heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
127 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks *
sizeof(CollectorBlock *));
130 targetBlock = (CollectorBlock *)calloc(1,
sizeof(CollectorBlock));
131 targetBlock->freeList = targetBlock->cells;
132 heap.blocks[heap.usedBlocks] = targetBlock;
137 CollectorCell *newCell = targetBlock->freeList;
140 if (imp->_vd != NULL) {
141 targetBlock->freeList = (CollectorCell*)(imp->_vd);
142 }
else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
144 targetBlock->freeList = NULL;
147 targetBlock->freeList = newCell + 1;
150 targetBlock->usedCells++;
151 heap.numLiveObjects++;
153 ((
ValueImp *)(newCell))->_flags = 0;
154 return (
void *)(newCell);
159 bool deleted =
false;
163 if (InterpreterImp::s_hook) {
164 InterpreterImp *scr = InterpreterImp::s_hook;
169 }
while (scr != InterpreterImp::s_hook);
173 for (
int block = 0; block < heap.usedBlocks; block++) {
175 int minimumCellsToProcess = heap.blocks[block]->usedCells;
176 CollectorBlock *curBlock = heap.blocks[block];
178 for (
int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
179 if (minimumCellsToProcess < cell) {
180 goto skip_block_mark;
185 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
187 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
188 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
192 minimumCellsToProcess++;
198 for (
int cell = 0; cell < heap.usedOversizeCells; cell++) {
200 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
201 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
210 for (
int block = 0; block < heap.usedBlocks; block++) {
211 CollectorBlock *curBlock = heap.blocks[block];
213 int minimumCellsToProcess = curBlock->usedCells;
215 for (
int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
216 if (minimumCellsToProcess < cell) {
217 goto skip_block_sweep;
222 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
223 if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
227 imp->_flags |= ValueImp::VI_DESTRUCTED;
231 curBlock->usedCells--;
232 heap.numLiveObjects--;
236 imp->_vd = (ValueImpPrivate*)curBlock->freeList;
237 curBlock->freeList = (CollectorCell *)imp;
240 imp->_flags &= ~
ValueImp::VI_MARKED;
243 minimumCellsToProcess++;
249 if (heap.blocks[block]->usedCells == 0) {
251 if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
252 #ifndef DEBUG_COLLECTOR
253 free(heap.blocks[block]);
256 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
260 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
261 heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
262 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks *
sizeof(CollectorBlock *));
269 heap.firstBlockWithPossibleSpace = 0;
273 while (cell < heap.usedOversizeCells) {
276 if (!imp->refcount &&
277 imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
280 #ifndef DEBUG_COLLECTOR
285 heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
287 heap.usedOversizeCells--;
289 heap.numLiveObjects--;
291 if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
292 heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
293 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells *
sizeof(CollectorCell *));
297 imp->_flags &= ~
ValueImp::VI_MARKED;
302 heap.numAllocationsSinceLastCollect = 0;
304 memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
309 int Collector::size()
311 return heap.numLiveObjects;
315 void Collector::finalCheck()
static bool collect()
Run the garbage collection.
ValueImp is the base type for all primitives (Undefined, Null, Boolean, String, Number) and objects i...
static void * allocate(size_t s)
Register an object with the collector.