22 #include "collector.h"
30 #define MAX(a,b) ((a) > (b) ? (a) : (b))
36 const int MINIMUM_CELL_SIZE = 56;
37 const int BLOCK_SIZE = (8 * 4096);
38 const int SPARE_EMPTY_BLOCKS = 2;
39 const int MIN_ARRAY_SIZE = 14;
40 const int GROWTH_FACTOR = 2;
41 const int LOW_WATER_FACTOR = 4;
42 const int ALLOCATIONS_PER_COLLECTION = 1000;
45 const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE /
sizeof(double)) + (MINIMUM_CELL_SIZE %
sizeof(double) != 0 ?
sizeof(
double) : 0);
46 const int CELL_SIZE = CELL_ARRAY_LENGTH *
sizeof(double);
47 const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 -
sizeof(int) * 8 -
sizeof(
void *) * 8) / (CELL_SIZE * 8));
51 struct CollectorCell {
52 double memory[CELL_ARRAY_LENGTH];
56 struct CollectorBlock {
57 CollectorCell cells[CELLS_PER_BLOCK];
59 CollectorCell *freeList;
62 struct CollectorHeap {
63 CollectorBlock **blocks;
66 int firstBlockWithPossibleSpace;
68 CollectorCell **oversizeCells;
70 int usedOversizeCells;
73 int numAllocationsSinceLastCollect;
76 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
78 bool Collector::memoryFull =
false;
86 if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
90 if (s > (
unsigned)CELL_SIZE) {
92 if (heap.usedOversizeCells == heap.numOversizeCells) {
93 heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
94 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells *
sizeof(CollectorCell *));
97 void *newCell = malloc(s);
98 heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
99 heap.usedOversizeCells++;
100 heap.numLiveObjects++;
102 ((
ValueImp *)(newCell))->_flags = 0;
108 CollectorBlock *targetBlock = NULL;
111 for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
112 if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
113 targetBlock = heap.blocks[i];
118 heap.firstBlockWithPossibleSpace = i;
120 if (targetBlock == NULL) {
123 if (heap.usedBlocks == heap.numBlocks) {
124 static const size_t maxNumBlocks = ULONG_MAX /
sizeof(CollectorBlock*) / GROWTH_FACTOR;
125 if ((
size_t)heap.numBlocks > maxNumBlocks)
127 heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
128 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks *
sizeof(CollectorBlock *));
131 targetBlock = (CollectorBlock *)calloc(1,
sizeof(CollectorBlock));
132 targetBlock->freeList = targetBlock->cells;
133 heap.blocks[heap.usedBlocks] = targetBlock;
138 CollectorCell *newCell = targetBlock->freeList;
141 if (imp->_vd != NULL) {
142 targetBlock->freeList = (CollectorCell*)(imp->_vd);
143 }
else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
145 targetBlock->freeList = NULL;
148 targetBlock->freeList = newCell + 1;
151 targetBlock->usedCells++;
152 heap.numLiveObjects++;
154 ((
ValueImp *)(newCell))->_flags = 0;
155 return (
void *)(newCell);
160 bool deleted =
false;
164 if (InterpreterImp::s_hook) {
165 InterpreterImp *scr = InterpreterImp::s_hook;
170 }
while (scr != InterpreterImp::s_hook);
174 for (
int block = 0; block < heap.usedBlocks; block++) {
176 int minimumCellsToProcess = heap.blocks[block]->usedCells;
177 CollectorBlock *curBlock = heap.blocks[block];
179 for (
int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
180 if (minimumCellsToProcess < cell) {
181 goto skip_block_mark;
186 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
188 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
189 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
193 minimumCellsToProcess++;
199 for (
int cell = 0; cell < heap.usedOversizeCells; cell++) {
201 if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
202 ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
211 for (
int block = 0; block < heap.usedBlocks; block++) {
212 CollectorBlock *curBlock = heap.blocks[block];
214 int minimumCellsToProcess = curBlock->usedCells;
216 for (
int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
217 if (minimumCellsToProcess < cell) {
218 goto skip_block_sweep;
223 if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
224 if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
228 imp->_flags |= ValueImp::VI_DESTRUCTED;
232 curBlock->usedCells--;
233 heap.numLiveObjects--;
237 imp->_vd = (ValueImpPrivate*)curBlock->freeList;
238 curBlock->freeList = (CollectorCell *)imp;
241 imp->_flags &= ~
ValueImp::VI_MARKED;
244 minimumCellsToProcess++;
250 if (heap.blocks[block]->usedCells == 0) {
252 if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
253 #ifndef DEBUG_COLLECTOR
254 free(heap.blocks[block]);
257 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
261 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
262 heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
263 heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks *
sizeof(CollectorBlock *));
270 heap.firstBlockWithPossibleSpace = 0;
274 while (cell < heap.usedOversizeCells) {
277 if (!imp->refcount &&
278 imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
281 #ifndef DEBUG_COLLECTOR
286 heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
288 heap.usedOversizeCells--;
290 heap.numLiveObjects--;
292 if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
293 heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
294 heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells *
sizeof(CollectorCell *));
298 imp->_flags &= ~
ValueImp::VI_MARKED;
303 heap.numAllocationsSinceLastCollect = 0;
305 memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
310 int Collector::size()
312 return heap.numLiveObjects;
316 void Collector::finalCheck()