4 #define MIN_BLOCK_SIZE 256
6 // "type" for an object freed by the collector
7 #define T_GCFREED 123 // DEBUG
14 // Decremented every allocation. When it reaches zero, we do a
15 // garbage collection. The value is reset to 1/2 of the total object
16 // count each collection, which is sane: it ensures that no more than
17 // 50% growth can happen between collections, and ensures that garbage
18 // collection work is constant with allocation work (i.e. that O(N)
19 // work is done only every O(1/2N) allocations).
20 static int GlobalAllocCount = 256;
22 static void appendfree(struct naPool*p, struct naObj* o)
25 if(p->freesz <= p->nfree) {
26 int i, n = 1+((3*p->nfree)>>1);
27 void** newf = naAlloc(n * sizeof(void*));
28 for(i=0; i<p->nfree; i++)
35 p->free[p->nfree++] = o;
38 static void naCode_gcclean(struct naCode* o)
40 naFree(o->byteCode); o->byteCode = 0;
41 naFree(o->constants); o->constants = 0;
44 static void naGhost_gcclean(struct naGhost* g)
46 if(g->ptr) g->gtype->destroy(g->ptr);
50 static void freeelem(struct naPool* p, struct naObj* o)
52 // Mark the object as "freed" for debugging purposes
53 o->type = T_GCFREED; // DEBUG
55 // Free any intrinsic (i.e. non-garbage collected) storage the
59 naStr_gcclean((struct naStr*)o);
62 naVec_gcclean((struct naVec*)o);
65 naHash_gcclean((struct naHash*)o);
68 naCode_gcclean((struct naCode*)o);
71 naGhost_gcclean((struct naGhost*)o);
75 // And add it to the free list
79 static void newBlock(struct naPool* p, int need)
83 struct Block* newblocks;
85 if(need < MIN_BLOCK_SIZE)
86 need = MIN_BLOCK_SIZE;
88 newblocks = naAlloc((p->nblocks+1) * sizeof(struct Block));
89 for(i=0; i<p->nblocks; i++) newblocks[i] = p->blocks[i];
91 p->blocks = newblocks;
92 buf = naAlloc(need * p->elemsz);
93 naBZero(buf, need * p->elemsz);
94 p->blocks[p->nblocks].size = need;
95 p->blocks[p->nblocks].block = buf;
98 for(i=0; i<need; i++) {
99 struct naObj* o = (struct naObj*)(buf + i*p->elemsz);
106 void naGC_init(struct naPool* p, int type)
109 p->elemsz = naTypeSize(type);
118 int naGC_size(struct naPool* p)
121 for(i=0; i<p->nblocks; i++)
122 total += ((struct Block*)(p->blocks + i))->size;
126 struct naObj* naGC_get(struct naPool* p)
128 // Collect every GlobalAllocCount allocations.
129 // This gets set to ~50% of the total object count each
130 // collection (it's incremented in naGC_reap()).
131 if(--GlobalAllocCount < 0) {
132 GlobalAllocCount = 0;
136 // If we're out, then allocate an extra 12.5%
138 newBlock(p, naGC_size(p)/8);
139 return p->free[--p->nfree];
142 // Sets the reference bit on the object, and recursively on all
143 // objects reachable from it. Clumsy: uses C stack recursion, which
144 // is slower than it need be and may cause problems on some platforms
145 // due to the very large stack depths that result.
146 void naGC_mark(naRef r)
150 if(IS_NUM(r) || IS_NIL(r))
153 if(r.ref.ptr.obj->mark == 1)
156 // Verify that the object hasn't been freed incorrectly:
157 if(r.ref.ptr.obj->type == T_GCFREED) *(int*)0=0; // DEBUG
159 r.ref.ptr.obj->mark = 1;
160 switch(r.ref.ptr.obj->type) {
162 for(i=0; i<r.ref.ptr.vec->size; i++)
163 naGC_mark(r.ref.ptr.vec->array[i]);
166 if(r.ref.ptr.hash->table == 0)
168 for(i=0; i < (1<<r.ref.ptr.hash->lgalloced); i++) {
169 struct HashNode* hn = r.ref.ptr.hash->table[i];
178 naGC_mark(r.ref.ptr.code->srcFile);
179 for(i=0; i<r.ref.ptr.code->nConstants; i++)
180 naGC_mark(r.ref.ptr.code->constants[i]);
183 naGC_mark(r.ref.ptr.closure->namespace);
184 naGC_mark(r.ref.ptr.closure->next);
187 naGC_mark(r.ref.ptr.func->code);
188 naGC_mark(r.ref.ptr.func->closure);
193 // Collects all the unreachable objects into a free list, and
194 // allocates more space if needed.
195 void naGC_reap(struct naPool* p)
197 int i, elem, total = 0;
199 for(i=0; i<p->nblocks; i++) {
200 struct Block* b = p->blocks + i;
202 for(elem=0; elem < b->size; elem++) {
203 struct naObj* o = (struct naObj*)(b->block + elem * p->elemsz);
210 // Add 50% of our total to the global count
211 GlobalAllocCount += total/2;
213 // Allocate more if necessary (try to keep 25-50% of the objects
215 if(p->nfree < total/4) {
216 int used = total - p->nfree;
217 int avail = total - used;
218 int need = used/2 - avail;