memory.mutex.c
Go to the documentation of this file.
00001 /****************************************************************/
00002 /* memory.c:    memory manager for eulisp                       */
00003 /*      Copyright(c) Toshihiro MATSUI
00004 /*                   Electrotechnical Laboratory,1986.
00005 /****************************************************************/
00006 
00007 #if vxworks
00008 #include        <sys/types.h>
00009 #else
00010 #include        <sys/types.h>
00011 #include        <sys/times.h>
00012 #endif
00013 
00014 #include        "eus.h"
00015 #if Solaris2
00016 #include        <synch.h>
00017 #include        <thread.h>
00018 #endif
00019 
00020 #define nextbuddy(p) ((bpointer)((int)p+(buddysize[p->h.bix]*sizeof(pointer))))
00021 #define marked(p)  (p->h.mark)
00022 #define markon(p)  p->h.mark=1
00023 #define markoff(p) p->h.mark=0
00024 #define myctx (euscontexts[thr_self()])
00025 
00026 #if Solaris2 
00027 extern _end();
00028 #else
00029 extern edata();
00030 #endif
00031 
00032 extern pointer QPARAGC;
00033 
00034 char *maxmemory=(char *)0x100000;
00035 long freeheap=0,totalheap=0;    /*size of heap left and allocated*/
00036 struct chunk *chunklist=NULL;
00037 /* timers */
00038 long gccount,marktime,sweeptime;
00039 long alloccount[MAXBUDDY];
00040 
00041 #if Solaris2
00042 mutex_t alloc_lock;
00043 #endif
00044 
00045 newchunk(k)
00046 register int k;
00047 { register int s;
00048   register struct chunk *cp;
00049   if (k<DEFAULTCHUNKINDEX) k=DEFAULTCHUNKINDEX;
00050   if (QDEBUG && debug) fprintf(stderr,";; newchunk: k=%d\n",k);
00051   s=buddysize[k];
00052   cp=(struct chunk *)(malloc((s+2)*sizeof(pointer)+3) & ~3);
00053   maxmemory=(char *)sbrk(0);
00054   if (cp==NULL) return(ERR);    /*can't allocate new memory*/
00055   cp->nextchunk=chunklist;      /*link to chunk list*/
00056   chunklist=cp;
00057   cp->chunkbix=k;
00058   cp->rootcell.h.mark=0;
00059   cp->rootcell.h.b=1;           /*initial buddy marks*/
00060   cp->rootcell.h.m=0;
00061   cp->rootcell.h.bix=k;
00062   cp->rootcell.b.nextbcell=0;
00063   buddy[k].bp= &cp->rootcell;
00064   buddy[k].count++;
00065   totalheap += s; freeheap += s;
00066   return(k);
00067   }
00068 
00069 static void splitheap(k,buddy)  /*heart of the allocator*/
00070 register int k;
00071 register struct buddyfree *buddy;
00072 { register bpointer b1,b2,bnext;
00073   b1= buddy[k].bp;      /*root buddy pointer*/
00074   bnext=b1->b.nextbcell;
00075   buddy[k].bp= bnext;   /*remove first element*/
00076   buddy[k].count--;
00077   b2= (bpointer)((long)b1+buddysize[k-1]*sizeof(pointer));
00078   if (k==2) {   /*b1 and b2 are of the same size*/
00079     b1->b.nextbcell=b2;
00080     b2->b.nextbcell=buddy[k-1].bp;
00081     buddy[k-1].bp=b1;
00082     buddy[k-1].count +=2;
00083     b2->h.bix= 1;}
00084   else {
00085     b1->b.nextbcell= buddy[k-1].bp;
00086     buddy[k-1].bp=b1;
00087     buddy[k-1].count++;
00088     b2->b.nextbcell=buddy[k-2].bp;
00089     buddy[k-2].bp=b2;
00090     buddy[k-2].count++;
00091     b2->h.bix= k-2;}
00092   b2->h.m=b1->h.m;
00093   b1->h.m=b1->h.b;
00094   b1->h.b=0; b1->h.bix= k-1; b2->h.b=1;
00095   b2->h.mark=b2->h.smark=b2->h.pmark=0;}
00096 
00097 bpointer root_alloc_big(ctx, req)
00098 register context *ctx;
00099 register int req;       /*index to buddy: must be greater than 0*/
00100 { register int i, k;
00101   register bpointer b,b2;
00102   numunion nu;
00103 
00104 #if Solaris2
00105   mutex_lock(&alloc_lock); 
00106 #endif
00107 
00108   ctx->alloc_big_count++;
00109 
00110     k=req;
00111     while (buddy[k].bp==0) k++; /*find blocks of adequate size*/
00112     if (k>=MAXBUDDY) {          /*no bigger free cell*/
00113       if (buddysize[req]<totalheap/8) { /*relatively small cell is requested;*/
00114         gc();                   /* then try garbage collection*/
00115         while (freeheap<(totalheap*min(5.0,fltval(spevalof(GCMARGIN)))))
00116           newchunk(req); /*still not enough space*/
00117         for (k=req; buddy[k].bp==0; ) k++;}
00118       if (k>=MAXBUDDY) {
00119         k=newchunk(req);
00120         if (k==ERR) { 
00121 #if Solaris2
00122           mutex_unlock(&alloc_lock);
00123 #endif
00124           error(E_ALLOCATION);}}}
00125 
00126     while (req<k) { splitheap(k--,&buddy); if (k>req) k--;}
00127     k=buddysize[req]-1;
00128     b=buddy[req].bp;
00129     b2=b->b.nextbcell;
00130     for (i=0; i<k; i++) b->b.c[i]=0;
00131     ctx->lastalloc=makepointer(b);
00132     buddy[req].bp=b2;
00133     buddy[req].count--;
00134     freeheap -= buddysize[req];
00135     alloccount[req]++;
00136 #if Solaris2
00137   mutex_unlock(&alloc_lock); 
00138 #endif
00139   return(b);}
00140 
00141 root_alloc_small(ctx, req)
00142 register context *ctx;
00143 register int req;       /*index to buddy: must be greater than 0*/
00144 { register int i, j, k,kk;
00145   register bpointer b, b2;
00146   register struct buddyfree *tb=ctx->thr_buddy;
00147   static long buddyfill[MAXTHRBUDDY+1]={0,500,300,50,25,20,0};
00148   numunion nu;
00149   int collected=0;
00150 
00151 #if Solaris2
00152   mutex_lock(&alloc_lock); 
00153 #endif
00154   
00155   ctx->alloc_small_count++;
00156 
00157   alloc_again:
00158   for (i=1; i<MAXTHRBUDDY; i++) {
00159     k=kk=buddyfill[i] - tb[i].count; /*how many cells are needed*/
00160     while (buddy[i].count < k) {   /*Do we have enough free in the root?*/
00161 /*      fprintf(stderr, "free_count=%d; k=%d\n",buddy[i].count,k);  */
00162         j=i+1;
00163         while (buddy[j].bp==0) j++;
00164         if (j>=MAXBUDDY) {      /*no free cell*/
00165           if (!collected) {
00166             /* fprintf(stderr, "GC: free=%d total=%d, margin=%f\n",
00167                         freeheap, totalheap, fltval(spevalof(GCMARGIN))); */
00168             gc(); collected=1;
00169             goto alloc_again;}
00170           while (freeheap<(totalheap*min(5.0,fltval(spevalof(GCMARGIN))))) {
00171             j=newchunk(DEFAULTCHUNKINDEX); /*still not enough space*/
00172             if (j==ERR) { mutex_unlock(&alloc_lock); error(E_ALLOCATION);}} }
00173         if (j>=MAXBUDDY) {      /*hard fragmentation seen*/
00174           j=newchunk(DEFAULTCHUNKINDEX);
00175           if (j==ERR) { mutex_unlock(&alloc_lock); error(E_ALLOCATION);}} 
00176         splitheap(j, &buddy);}
00177     /*sufficient free cells collected in the root free list*/
00178     if (k>0) {
00179       b=buddy[i].bp;
00180       while (k>0) { b2=b; b=b->b.nextbcell; k--;}
00181       b2->b.nextbcell=tb[i].bp;
00182       tb[i].bp=buddy[i].bp;
00183       buddy[i].bp=b;
00184       buddy[i].count -= kk;
00185       tb[i].count=buddyfill[i];
00186       freeheap -= buddysize[i]*kk;
00187       alloccount[i] += kk;
00188       }}
00189 #if Solaris2
00190   mutex_unlock(&alloc_lock); 
00191 #endif
00192   /*return(b);*/
00193   }
00194 
00195 pointer halloc(req,e,cid)       /*heap alloc*/
00196 register int req;       /*index to buddy: must be greater than 0*/
00197 int e;                  /*element type*/
00198 int cid;                /*class id*/
00199 { register bpointer b;
00200   register pointer p;
00201   context *ctx=myctx;
00202   register struct buddyfree *tb= ctx->thr_buddy;
00203 
00204   if (/*req>=MAXTHRBUDDY*/ 1)  b=root_alloc_big(ctx, req);
00205   else { /*small cell is requested*/
00206     if (tb[req].count==0) /*find a cell in the local free list*/
00207       root_alloc_small(ctx, req);
00208     b=tb[req].bp;
00209     ctx->lastalloc=makepointer(b);
00210     tb[req].bp=b->b.nextbcell;
00211     tb[req].count--;}
00212   b->h.elmtype=e;
00213   b->h.cix=cid;
00214   p=makepointer(b);
00215   return(p);}
00216 
00217 pointer allocx(s,e,cid,nils)    /*allocate heap of 's' longwords*/
00218 register int s,nils;
00219 int e,cid;
00220 { register int bs=1,i,ss;
00221   register cell *c;
00222   register pointer *v;
00223   register bpointer b;
00224   ss=max(3,s+1);         /*one more word for the allocation information*/
00225   while (buddysize[bs]<ss) bs++;
00226   if (bs>=MAXBUDDY) return(NULL);
00227 
00228 /*  c=halloc(bs,e,cid); */
00229 
00230   b=root_alloc_big(myctx, bs);
00231   b->h.elmtype=e;
00232   b->h.cix=cid;
00233   c=makepointer(b);
00234 
00235   i=buddysize[bs]-1;
00236   v=c->c.obj.iv;
00237   while (nils<s) v[nils++]=NIL; /*fill NILs in user's  slots*/
00238   while (s<i) v[s++]=NULL;      /*fill NULLs in buddy-cells extra slots*/
00239   return(c);}
00240 
00241 pointer alloc(s,e,cid,nils)     /*allocate heap of 's' longwords*/
00242 register int s,nils;
00243 int e,cid;
00244 { register int req=1,i,ss,k;
00245   register cell *c;
00246   register pointer *v;
00247   register bpointer b,b2;
00248   register context *ctx=myctx;
00249   numunion nu;
00250 
00251   ss=max(3,s+1);         /*one more word for the allocation information*/
00252   while (buddysize[req]<ss) req++;
00253   if (req>=MAXBUDDY) return(NULL);
00254 
00255   k=req;
00256   mutex_lock(&alloc_lock); 
00257 
00258     while (buddy[k].bp==0) k++; /*find blocks of adequate size*/
00259     if (k>=MAXBUDDY) {          /*no bigger free cell*/
00260       if (buddysize[req]<totalheap/8) { /*relatively small cell is requested;*/
00261         gc();                   /* then try garbage collection*/
00262         while (freeheap<(totalheap*min(5.0,fltval(spevalof(GCMARGIN)))))
00263           newchunk(req); /*still not enough space*/
00264         for (k=req; buddy[k].bp==0; ) k++;}
00265       if (k>=MAXBUDDY) {
00266         k=newchunk(req);
00267         if (k==ERR) {  mutex_unlock(&alloc_lock); error(E_ALLOCATION);}}}
00268     while (req<k) { splitheap(k--,&buddy); if (k>req) k--;}
00269     k=buddysize[req]-1;
00270     b=buddy[req].bp;
00271     b2=b->b.nextbcell;
00272     for (i=0; i<k; i++) b->b.c[i]=0;
00273     b->h.elmtype=e;
00274     b->h.cix=cid;
00275     c=makepointer(b);
00276     ctx->lastalloc=c;
00277     buddy[req].bp=b2;
00278     buddy[req].count--;
00279     freeheap -= buddysize[req];
00280     alloccount[req]++;
00281   mutex_unlock(&alloc_lock); 
00282 
00283   i=buddysize[req]-1;
00284   v=c->c.obj.iv;
00285   while (nils<s) v[nils++]=NIL; /*fill NILs in user's  slots*/
00286   return(c);}
00287 
00288 
00289 
00290 /****************************************************************/
00291 /* gc: garbage collector
00292 /****************************************************************/
00293 
00294 #define DEFAULT_MAX_GCSTACK 65536*2
00295 pointer *gcstack, *gcsplimit, *gcsp;
00296 #define gcpush(v) (*lgcsp++=((pointer)v))
00297 #define gcpop() (*--lgcsp)
00298 
00299 pointer mark_root, marking, marking2;
00300 
00301 mark(p)
00302 register pointer p;
00303 { register int i,s;
00304   register bpointer bp;
00305   register pointer p2;
00306   register pointer *lgcsp=gcstack;
00307   register pointer *lgcsplimit=gcsplimit;
00308 
00309   mark_root=p;
00310   gcpush(p);
00311 markloop:
00312   if (lgcsp<=gcstack) return;
00313   p=gcpop();
00314 markagain:
00315 #if Solaris2
00316   if ((int)p<(int)_end || (pointer)0x20000000<p) goto markloop;
00317 #else
00318   if ((int)p<(int)edata || (pointer)0x20000000<p) goto markloop;
00319 #endif
00320   bp=bpointerof(p);
00321   if (marked(bp)) goto markloop;        /*already marked*/
00322   markon(bp);                   /*mark it first to avoid endless marking*/
00323   if (pisclosure(p)) goto markloop;     /*avoid marking contents of closure*/
00324   marking=p;
00325   if (bp->h.elmtype==ELM_FIXED) {       /*contents are all pointers*/
00326     s=buddysize[bp->h.bix]-1;
00327     while (lgcsp+s>gcsplimit) { newgcstack(lgcsp); lgcsp=gcsp;}
00328     for (i=0; i<s; i++) {
00329         p2=p->c.obj.iv[i];
00330         if (ispointer(p2)) /* && !marked(bpointerof(p2)))*/  gcpush(p2); }
00331     goto markloop;}
00332   else if (bp->h.elmtype==ELM_POINTER) { /*varing number of pointers*/
00333     s=vecsize(p);
00334     while (lgcsp+s>gcsplimit) { newgcstack(lgcsp); lgcsp=gcsp;}
00335     for (i=0; i<s; i++) {
00336         p2=p->c.vec.v[i];
00337         if (ispointer(p2)) /* && !marked(bpointerof(p2)))*/   gcpush(p2); }
00338       goto markloop;}
00339   else goto markloop;
00340   }
00341 
00342 newgcstack(oldsp)
00343 register pointer *oldsp;
00344 { register pointer *oldstack, *stk, *newstack, *newgcsp;
00345   long top, oldsize, newsize;
00346 
00347   oldstack=stk=gcstack;
00348   oldsize=gcsplimit-gcstack;
00349   newsize=oldsize*2;
00350   top=oldsp-gcstack;
00351   newgcsp=newstack=(pointer *)malloc(newsize * sizeof(pointer)+16);
00352   fprintf(stderr, "\n;; extending gcstack 0x%x[%d] --> 0x%x[%d] top=%x\n",
00353                 oldstack, oldsize, newstack, newsize, top);
00354   while (stk<oldsp) *newgcsp++= *stk++;
00355   gcstack=newstack;
00356   gcsplimit= &gcstack[newsize-10];
00357   gcsp= &gcstack[top];
00358   cfree(oldstack);
00359   }
00360 
00361 int mark_state;
00362 
00363 markall()
00364 { register pointer *p,*spsave;
00365   register int i,j;
00366   register context *ctx;
00367   register bpointer q;
00368 
00369   mark_state=1;
00370   mark(sysobj);         /*mark internally reachable objects*/
00371   mark_state=2;
00372   mark(pkglist);        /*mark all packages*/
00373   for (i=0; i<MAXTHREAD; i++) {
00374     /*mark everything reachable from stacks in euscontexts*/
00375     if (ctx=euscontexts[i]) {
00376       mark_state=ctx;
00377       for (p=ctx->stack; p<ctx->vsp; p++) {
00378         mark_state==(int)p;
00379         if ((((int)(*p) & 3)==0) && 
00380             ((ctx->stack>(pointer *)*p) || ((pointer *)*p>ctx->stacklimit)))
00381                 {  mark(*p); } ;}
00382       mark_state++;
00383       mark(ctx->lastalloc);
00384       mark_state=0x10000;
00385       for (j=1; j<MAXTHRBUDDY; j++) {
00386         q=ctx->thr_buddy[j].bp;
00387         while (q) { markon(q); q=q->b.nextbcell; mark_state++;}
00388         }
00389       }}
00390   mark_state=5;
00391   for (i=0; i<MAXCLASS; i++) {
00392     if (ispointer(classtab[i].def)) mark(classtab[i].def); }
00393   mark_state=0;
00394   }
00395 
00396 reclaim(p)
00397 register bpointer p;
00398 { register int rbix,stat;
00399   register pointer s;
00400   s=makepointer(p);
00401   if (pisfilestream(s)) {
00402     if (!isint(s->c.fstream.fname) && s->c.fstream.direction!=NIL) {
00403       if (s->c.fstream.fd==makeint(0) || s->c.fstream.fd==makeint(1)) {
00404         fprintf(stderr,";; gc! bogus stream at %x fd=%d\n",
00405                 (int)s,intval(s->c.fstream.fd));}
00406       else if ((closestream(s)==0) && debug)
00407         fprintf(stderr,";; gc: dangling stream(address=%x fd=%d) is closed\n",
00408                 (int)s,intval(s->c.fstream.fd)); } }
00409   p->h.cix= -1;
00410   rbix=p->h.bix;
00411   p->b.nextbcell=buddy[rbix].bp;
00412   buddy[rbix].bp=p; buddy[rbix].count++;
00413   freeheap+=buddysize[rbix];}
00414 
00415 static bpointer mergecell(p,cbix)
00416 register bpointer p;
00417 int cbix;
00418 /*the cell pointed by 'p' must not be marked*/
00419 /*mergecell kindly returns next uncollectable cell address*/
00420 { register bpointer np,p2;
00421   np=nextbuddy(p);
00422   while (p->h.b==0 && (int)p->h.bix<cbix) {
00423     if (marked(np)) return(np);
00424     p2=mergecell(np,cbix);      /*merge neighbor cell*/
00425     if (np->h.b==1) {           /*can be merged*/
00426       p->h.b=p->h.m;            /*merge them into bigger cell*/
00427       p->h.m=np->h.m;
00428       p->h.bix++;
00429       np=p2;}
00430     else {
00431       reclaim(np);
00432       return(p2);}}
00433   return(np);}
00434   
00435 static void sweep(cp,gcmerge)
00436 register struct chunk *cp;
00437 register int gcmerge;
00438 { register int s;
00439   register bpointer p,np,tail;
00440 
00441   s=buddysize[cp->chunkbix];
00442   p= &cp->rootcell;
00443   tail=(bpointer)((int)p+(s<<2));
00444   while (p<tail) {
00445     if (marked(p)) { markoff(p); p=nextbuddy(p);}       /*don't collect*/
00446     else if (gcmerge>freeheap) { /* no merge */
00447         np=nextbuddy(p);
00448         reclaim(p);
00449         p=np;} 
00450     else {
00451         np=mergecell(p,cp->chunkbix);   /*update free buddy list*/
00452         reclaim(p);
00453         p=np;} }
00454   }  
00455 
00456 void sweepall()
00457 { 
00458   register struct chunk *chp;
00459   register int i, gcmerge;
00460   numunion nu;
00461   gcmerge=totalheap * min(1.0,fltval(spevalof(GCMARGIN)))
00462                     * max(0.1,fltval(spevalof(GCMERGE)));
00463 
00464   for (i=0; i<MAXBUDDY-1; i++) {
00465     buddy[i].bp=0;      /*purge buddies*/
00466     buddy[i].count=0;   /*clear free cell count*/
00467     }
00468   freeheap=0;
00469   for (chp=chunklist; chp!=0; chp=chp->nextchunk) sweep(chp,gcmerge);
00470   }
00471 
00472 #if vxworks
00473 gc()
00474 { if (debug)  fprintf(stderr,"\n;; gc:");
00475   breakck;
00476   gccount++;
00477   markall();
00478   sweepall();
00479   if (debug) {
00480     fprintf(stderr," free/total=%d/%d stack=%d ",
00481                 freeheap,totalheap,markctx->vsp-markctx->stack);
00482     }
00483   breakck;
00484   }
00485 
00486 #else 
00487 
00488 gc()
00489 { struct tms tbuf1,tbuf2,tbuf3;
00490 
00491   if (debug)  fprintf(stderr,"\n;; gc: thread=%d ",thr_self());
00492   breakck;
00493   gccount++;
00494   times(&tbuf1);
00495 
00496 #if Solaris2
00497   mutex_unlock(&mark_lock);
00498 #endif
00499 
00500   markall();
00501 
00502   times(&tbuf2);
00503   marktime+=(tbuf2.tms_utime-tbuf1.tms_utime);
00504   sweepall();
00505   times(&tbuf3);
00506   sweeptime+=(tbuf3.tms_utime-tbuf2.tms_utime);
00507   if (debug) {
00508     fprintf(stderr," free/total=%d/%d stack=%d ",
00509                 freeheap,totalheap,myctx->vsp - myctx->stack);
00510     fprintf(stderr," mark=%d sweep=%d\n", marktime,sweeptime);}
00511 
00512 #if Solaris2
00513   mutex_unlock(&mark_lock);
00514 #endif
00515   breakck;
00516 }
00517 #endif
00518 


euslisp
Author(s): Toshihiro Matsui
autogenerated on Thu Mar 9 2017 04:57:50