001 #ifndef GC_HH
002 #define GC_HH 21
003 #define GC_MASK 0x7fff
004 CQue gc_heads[GC_MASK+1];
005 CQue gc_goods[GC_MASK+1];
006 CQue gc_to_check;
007 
008 CTask *gc_mem_task=Fs;
009 F64 gc_next=tS;
010 class CGCPtr:CQue {
011   I32 marked;
012   I32 handled;
013   U0 (*finalize)(U8*);
014   U0 start;
015 };
016 U64 HashPtr(I64 p) {
017   p>>=3;
018   I64 h=21;
019   I64 i;
020   for(i=0;i!=8;i++) {
021     h*=37;
022     h+=(p>>(i*8))&0xff;
023   }
024   return h;
025 }
026 Bool GCMarkPtr0(CGCPtr *ptr) {
027   static I64 depth=0;
028 //MAlloced ptrs are aligned
029   if(!ptr||ptr&0b111)
030         return FALSE;
031   I64 bucket=HashPtr(ptr)&GC_MASK;
032   --ptr;
033   I64 len;
034   U8 **flat;
035   CGCPtr  *head=&gc_heads[bucket],*cur;
036   for(cur=head->next;cur!=head;cur=cur->next) {
037     if(ptr==cur) {
038       if(ptr->marked++ ==0&&!ptr->handled) {
039         if(++depth<=32) {
040           QueRem(ptr);
041           QueIns(ptr,&gc_goods[bucket]);
042           len=MSize(ptr)-sizeof(CGCPtr);
043           ptr->handled=TRUE;
044           flat=ptr+1;
045           while((len-=8)>=0) {
046             GCMarkPtr0(*flat);
047             ++flat;
048           }
049           --depth;
050           return FALSE; //Already handled
051         }
052         QueRem(ptr);
053         QueIns(ptr,gc_to_check.last);
054         --depth;
055         return TRUE;
056       }
057     }
058   }
059   return FALSE;
060 }
061 Bool GCMarkPtr(U8 **flat,I64 l) {
062   Bool r=FALSE;
063   while((l-=8)>=0) {
064     r|=GCMarkPtr0(*flat);
065     flat++;
066   }
067   return r;
068 }
069 U0 ScanAllMem(CTask *for_task,U8 *head2,Bool(*scan)(U8*,I64)) {
070   CHashGlblVar *gv;
071   CExcept *cur_ex;
072   I64 len;
073   U8 **flat,repeat;
074   CGCPtr *dummy,*head,*cur,*next;
075   I64 bucket=for_task->hash_table->mask+1;
076   while(--bucket>=0) {
077     gv=for_task->hash_table->body[bucket];
078     while(gv) {
079       if(gv->type&HTT_FRAME_PTR) {
080         len=sizeof CHashGeneric;
081         flat=gv;
082         scan(flat,len);
083       }
084       if(gv->type&HTT_GLBL_VAR&&gv->data_addr) {
085         len=gv->size;
086         flat=gv->data_addr;
087         if(flat!=&gc_heads&&flat!=&gc_goods&&flat!=&gc_to_check)  {
088           scan(flat,len);
089          }
090       }
091       gv=gv->next;
092     }
093   }
094   flat=for_task;
095   len=sizeof(CTask);
096   scan(flat,len);
097 
098   for(cur_ex=for_task->next_except;cur_ex!=&for_task->next_except;cur_ex=cur_ex->next) {
099     flat=cur_ex;
100     len=MSize(cur_ex);
101     scan(flat,len);
102   }
103   flat=for_task->stk;
104   len=MSize(flat);
105   scan(flat,len);
106 
107   //New to checks are added at the end,so dont worry about new ones being added
108   for(cur=gc_to_check.next;cur!=&gc_to_check;cur=next) {
109     dummy=cur+1;
110     cur->marked=0;
111     cur->handled=0;
112     scan(cur,MSize(cur));
113     QueRem(cur);
114     bucket=HashPtr(cur+1)&GC_MASK;
115     QueIns(cur,&gc_goods[bucket]);
116     next=gc_to_check.next;
117   }
118 }
119 Bool gc_enable=TRUE;
120 I64 gc_lock=0;
121 U0 GCCollect() {
122   if(!gc_enable) return ;
123   while(LBts(&gc_lock,0))
124     Yield;
125   CTask *for_task=gc_mem_task;
126   U8 **flat;
127   I64 len;
128   Bool repeat;
129   I64 bucket,total;
130   static F64 old_tS=tS;
131   CGCPtr *head,*cur,*next;
132 
133   again:;
134   if(gc_next>tS)
135     return;
136   gc_next=tS-old_tS+1.1;
137   old_tS=tS;
138 
139   bucket=GC_MASK+1;
140   while(--bucket>=0) {
141     head=&gc_heads[bucket];
142     for(cur=head->next;cur!=head;cur=cur->next) {
143       cur->marked=0,cur->handled=0;
144     }
145   }
146 
147   ScanAllMem(for_task,&gc_heads,&GCMarkPtr);
148 
149   bucket=GC_MASK+1;
150   while(--bucket>=0) {
151     head=&gc_heads[bucket];
152     for(cur=head->next;cur!=head;cur=cur->next) {
153      if(cur->finalize)
154        (*cur->finalize)(cur+1);
155     }
156     QueDel(head);
157     QueInit(head);
158   }
159   bucket=GC_MASK+1;
160 
161   while(--bucket>=0) {
162     if(QueCnt(&gc_goods[bucket])) {
163       head=&gc_heads[bucket];
164       head->next=gc_goods[bucket].next;
165       head->last=gc_goods[bucket].last;
166       head->next->last=head;
167       head->last->next=head;
168     }
169     QueInit(&gc_goods[bucket]);
170   }
171   LBtr(&gc_lock,0);
172 }
173 
174 U8 *GCCAlloc(I64 sz) {
175   CGCPtr *p=CAlloc(sz+sizeof(CGCPtr),gc_mem_task);
176   while(LBts(&gc_lock,0))
177     Yield;
178   QueIns(p,gc_heads[HashPtr(p+1)&GC_MASK].next);
179   LBtr(&gc_lock,0);
180   return p+1;
181 }
182 U8 *GCStrNew(U8 *s) {
183   if(!s) return NULL;
184   U8 *ret=GCCAlloc(StrLen(s)+1);
185   StrCpy(ret,s);
186   return ret;
187 }
188 U8 *GCMAllocIdent(CGCPtr *s) {
189   if(!s) return NULL;
190   I64 l;
191   U8 *ret=GCCAlloc(l=MSize(s-1)-sizeof(CGCPtr));
192   MemCpy(ret,s,l);
193   return ret;
194 }
195 
196 U0 GCInit() {
197   I64 i=GC_MASK+1;
198   while(--i>=0) {
199     QueInit(&gc_heads[i]);
200     QueInit(&gc_goods[i]);
201   }
202   QueInit(&gc_to_check);
203 }
204 I64 GCMSize(CGCPtr *p) {
205   if(!p) return 0;
206   return MSize(p-1);
207 }
208 U0 GCFree(CGCPtr *p) {
209   if(!p) return;
210   while(LBts(&gc_lock,0))
211     Yield;
212   --p;
213   if(p->finalize)
214     (*p->finalize)(p+1);
215   QueRem(p);
216   Free(p);
217   LBtr(&gc_lock,0);
218 }
219 U0 GCFinalize(CGCPtr *ptr,U0 (*fun_ptr)(U8*)) {
220   if(!ptr) return;
221   --ptr;
222   ptr->finalize=fun_ptr;
223 }
224 GCInit;
225 #endif