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()
static void * allocate(size_t s)
Register an object with the collector.
static bool collect()
Run the garbage collection.
ValueImp is the base type for all primitives (Undefined, Null, Boolean, String, Number) and objects i...