rgc_mem.c
Go to the documentation of this file.
00001 /* 
00002  * rgc_mem.c
00003  */
00004 
00005 #include <sys/types.h>
00006 #include <sys/times.h>
00007 #include "eus.h"
00008 
00009 #define myctx (euscontexts[thr_self()])
00010 
00011 // defined in "memory.c"
00012 extern long freeheap, totalheap, marked_words;
00013 /* size of heap left and allocated */
00014 
00015 /* timers */
00016 long alloccount[MAXBUDDY];
00017 
00018 /* disposal processing */
00019 //#define MAXDISPOSE 256
00020 //static  pointer dispose[MAXDISPOSE];
00021 //static  int dispose_count;
00022 
00023 /* 
00024  * suppose that we have allocate lock
00025  */
00026 static int rgc_expand_heap_or_complete_gc(int req)
00027 {
00028   int idx = ERR;
00029 
00030 #ifdef __HEAP_EXPANDABLE
00031   /* acquire locks again in the correct order */
00032   mutex_unlock(&alloc_lock);
00033   lock_collector;
00034   mutex_lock(&alloc_lock);
00035 
00036   idx = newchunk(req); 
00037   unlock_collector;
00038 #else
00039   /* this case is under construction */
00040   mutex_unlock(&alloc_lock);
00041   if (gc_phase == PHASE_NOGC) {
00042     DPRINT1("\x1b[0;32mstart GC: free rate = %lf\x1b[0m", (double)freeheap / (double)totalheap);
00043     notify_gc();
00044   }
00045 
00046   lock_collector;
00047   while (gc_phase != PHASE_NOGC) {
00048     do_a_little_gc_work(AM_UNIT, AS_UNIT);
00049   }
00050   unlock_collector;
00051   mutex_lock(&alloc_lock);
00052 #endif
00053 
00054   return idx;
00055 }
00056 
00057 static inline unsigned long net_free(int req) {
00058   unsigned long total = 0;
00059   register int idx;
00060 
00061   for (idx = (req < REALTIME_ALLOC_LIMIT_IDX ? req : REALTIME_ALLOC_LIMIT_IDX);
00062           idx < MAXBUDDY; idx++)
00063       total += buddysize[idx] * buddy[idx].count;
00064 
00065   return total;
00066 }
00067 
00068 static int km[10] = {4096, 4800, 6000, 8192};
00069 static int ks[10] = {256, 256, 384, 512};
00070 
00071 static int recalc_gc_priority(int req) {
00072   /* now, return a value between 0 to 3 
00073    * 0: no gc
00074    * 1: gc thread
00075    * 2: normal thread
00076    * greater: realtime thread
00077    */
00078   long estimation;
00079   int i;
00080 
00081 #if 0
00082   for (i = 0; i < 4; i++) {
00083     if (gc_phase == PHASE_NOGC || gc_phase >= PHASE_MARK) { 
00084       estimation = (totalheap - freeheap - marked_words) / km[i]
00085         + (totalheap >> 4) / ks[i];
00086     } else {
00087       estimation = (totalheap >> 4) / ks[i];
00088     }
00089     estimation *= 1024;
00090     if (net_free(req) > estimation)
00091      break;
00092   }
00093 //  DPRINT1("estimation = %ld", estimation);
00094   return i;
00095 #endif
00096 
00097   {
00098     unsigned long nfree = net_free(req);
00099     for (i = 0; i < 4; i++) {
00100       if (nfree < totalheap * DEFAULT_GC_THRESHOLD)
00101         nfree *= 2;
00102       else
00103         break;
00104     }
00105   }    
00106 
00107 #if 0
00108   i = (net_free(req) < totalheap * DEFAULT_GC_THRESHOLD); 
00109 #endif 
00110 
00111   return i; 
00112 }
00113 
00114 
00115 volatile static int rem_cnt = 0;
00116 volatile static int gc_pri = 0;
00117 #define my_gc_pri ctx->my_gc_pri
00118 
00119 /* suppose we have collector lock */
00120 static int should_start_gc(int req) {
00121   static int gc_cushion = GC_ACTIVATE_CUSHION;
00122   register int idx;
00123 
00124 //  if (net_free(req) < (double)totalheap * DEFAULT_GC_THRESHOLD)
00125   if (recalc_gc_priority(req) > 0)
00126     gc_cushion--;
00127   
00128   return gc_cushion <= 0 
00129     ? (gc_cushion = GC_ACTIVATE_CUSHION, 1) : 0;
00130 }
00131 
00132 
00133 bpointer rgc_root_alloc_big(register context *ctx, register int req)
00134 { /* req: index to buddy: must be greater than 0 */
00135   register int i, k;
00136   register bpointer b, b2;
00137   numunion nu;
00138   pointer gcm;
00139 
00140   mutex_lock(&alloc_lock);
00141   ctx->alloc_big_count++;
00142 
00143  alloc_again:
00144 
00145   for (k = req; buddy[k].bp == 0; )
00146     k++; /* find blocks of adequate size */
00147 
00148   if (k >= MAXBUDDY) { /* no bigger free cell */
00149     if (buddysize[req] < totalheap / 8) { /*relatively small cell is requested;*/
00150       gcm = speval(GCMARGIN);
00151       DPRINT1("\x1b[1;31mstarved(alloc_big:1, free/total=%d/%d)\x1b[0m",
00152               freeheap, totalheap);
00153       rgc_expand_heap_or_complete_gc(req);
00154       for (k = req; buddy[k].bp == 0;) k++;
00155     }
00156     if (k >= MAXBUDDY) {
00157       DPRINT1("\x1b[1;31mstarved(alloc_big:1, free/total=%d/%d)\x1b[0m",
00158               freeheap, totalheap);
00159       rgc_expand_heap_or_complete_gc(req);
00160       for (k = req; buddy[k].bp == 0;) k++;
00161 
00162       if (k == ERR) {
00163         mutex_unlock(&alloc_lock);
00164         error(E_ALLOCATION);
00165       }
00166     }
00167   }
00168   while (req < k) {
00169     splitheap(k--, buddy); 
00170     if (k > req) k--;
00171   }
00172   k = buddysize[req] - 1;
00173   b = buddy[req].bp;
00174   b2 = b->b.nextbcell;
00175   for (i = 0; i < k; i++) b->b.c[i] = 0;
00176 #ifdef RGC
00177   //  take_care(ctx->lastalloc);
00178 #endif
00179   ctx->lastalloc = makepointer(b);
00180   buddy[req].bp = b2;
00181   buddy[req].count--;
00182 #ifdef DEBUG
00183   printf( "root_alloc_big: alloc 1 block (%d), 0x%lx\n", req, b );
00184 #endif
00185   freeheap -= buddysize[req];
00186   alloccount[req]++;
00187 
00188 #if THREADED
00189   mutex_unlock(&alloc_lock); 
00190 #endif
00191 
00192   /* work other than allocation */
00193   rem_cnt--;
00194   if (rem_cnt < 0) {
00195       lock_collector;
00196       switch(gc_phase) {
00197         case PHASE_NOGC:
00198           /* start a new GC cycle or not? */
00199           if (should_start_gc(req)) {
00200             DPRINT2("\x1b[0;32mstart GC: free rate = %lf, frag rate[%d] = %lf\x1b[0m", 
00201               (double)freeheap / (double)totalheap, req, (double)net_free(req) / (double)freeheap);
00202             
00203             notify_gc();
00204             gc_pri = 1;
00205           }
00206           break;
00207         default:
00208 #ifdef __GC_ALLOC_DRIVEN
00209           /* change GC priority */
00210           gc_pri = recalc_gc_priority(req);
00211 #endif
00212       }
00213 
00214       rem_cnt = GC_GRANULARITY;
00215       unlock_collector;
00216   } else {
00217 #ifdef __GC_ALLOC_DRIVEN
00218     /* do a little gc work if needed */
00219     if (gc_phase != PHASE_NOGC) {
00220       lock_collector;
00221       if (gc_phase != PHASE_NOGC) {
00222         if (my_gc_pri <= gc_pri) {
00223 //      DPRINT1("alloc gc[%d]", gc_pri);
00224           do_a_little_gc_work(AM_UNIT, AS_UNIT);
00225         }
00226       }
00227       unlock_collector;
00228     }
00229 #endif
00230   }
00231 
00232   return b;
00233 }
00234 
00235 
00236 void rgc_root_alloc_small(register context *ctx, register int req)
00237 { /* index to buddy: must be greater than 0 */
00238   register int i, j, k, kk;
00239   register bpointer b, b2;
00240   register struct buddyfree *tb = ctx->thr_buddy;
00241   static long buddyfill[MAXTHRBUDDY + 1] = {0, 500, 300, 20, 15, 10, 0};
00242   numunion nu;
00243 
00244   mutex_lock(&alloc_lock); 
00245   ctx->alloc_small_count++;
00246 
00247  alloc_again:
00248   for (i = 1; i < MAXTHRBUDDY; i++) {
00249     k = kk = buddyfill[i] - tb[i].count; /* how many cells are needed? */
00250     while (buddy[i].count < k) { /* do we have enough free in the root? */
00251       /* fprintf(stderr, "free_count = %d; k = %d\n", buddy[i].count, k); */
00252       j = i + 1;
00253       while (buddy[j].bp == 0) j++;
00254 
00255       if (j >= MAXBUDDY) {/* no free cell */
00256         DPRINT1("\x1b[1;31mstarved(alloc_small:1, free/total=%d/%d)\x1b[0m",
00257                 freeheap, totalheap);
00258         j = rgc_expand_heap_or_complete_gc(DEFAULT_EXPAND_SIZE_IDX);
00259         //unlock_collector;
00260         if (j == ERR) { 
00261           mutex_unlock(&alloc_lock); 
00262           error(E_ALLOCATION);
00263         }
00264       }
00265       splitheap(j, buddy);
00266     }
00267 
00268     /* sufficient free cells are collected in the root free list */
00269     if (k > 0) {
00270       b = buddy[i].bp;
00271       while (k > 0) {
00272         b2 = b;
00273         b->h.cix = -1;
00274         b = b->b.nextbcell;
00275         k--;
00276       }
00277       b2->b.nextbcell = tb[i].bp;
00278       tb[i].bp = buddy[i].bp;
00279       buddy[i].bp = b;
00280       buddy[i].count -= kk;
00281       tb[i].count = buddyfill[i];
00282       freeheap -= buddysize[i] * kk;
00283       alloccount[i] += kk;
00284 #ifdef DEBUG
00285       printf("root_alloc_small: alloc %d block(s) (%d)\n", kk, i);
00286 #endif
00287     }
00288   }
00289 
00290 #if THREADED
00291   mutex_unlock(&alloc_lock); 
00292 #endif
00293   /*
00294   {
00295     int j;
00296     bpointer p;
00297     for (i = 1; i < MAXTHRBUDDY; i++) {
00298       //    fprintf(stderr, "tb[i].count = %d\n", tb[i].count);
00299       for (j = 0, p = tb[i].bp; p != 0; p = p->b.nextbcell) j++;
00300       //    fprintf(stderr, "real list length is = %d\n", j);
00301       ASSERT(tb[i].count == j);
00302     }
00303   }
00304   */
00305 
00306   /* work other than allocation */
00307   rem_cnt--;
00308   if (rem_cnt < 0) {
00309       lock_collector;
00310       switch(gc_phase) {
00311         case PHASE_NOGC:
00312           /* start a new GC cycle or not? */
00313           if (should_start_gc(req)) {
00314             DPRINT2("\x1b[0;32mstart GC: free rate = %lf, frag rate[%d] = %lf\x1b[0m", 
00315               (double)freeheap / (double)totalheap, req, (double)net_free(req) / (double)freeheap);
00316             notify_gc();
00317             gc_pri = 1;
00318           }
00319           break;
00320         default:
00321 #ifdef __GC_ALLOC_DRIVEN
00322           /* change GC priority */
00323           gc_pri = recalc_gc_priority(req);
00324 #endif
00325       }
00326 
00327       rem_cnt = GC_GRANULARITY;
00328       unlock_collector;
00329   } else {
00330 #ifdef __GC_ALLOC_DRIVEN
00331     /* do a little gc work if needed */
00332     if (gc_phase != PHASE_NOGC) {
00333       lock_collector;
00334       if (gc_phase != PHASE_NOGC) {
00335         if (my_gc_pri <= gc_pri) {
00336           do_a_little_gc_work(AM_UNIT, AS_UNIT);
00337         }
00338       }
00339       unlock_collector;
00340     }
00341 #endif
00342   }
00343 
00344   /*return(b);*/
00345 }
00346 
00347 pointer rgc_alloc(register int s, int e, int cid, register int nils)
00348 {  /* allocate heap of 's' longwords */
00349  register int req = 1, i, ss;
00350  register pointer p;
00351  register pointer *v;
00352  register bpointer b, b2;
00353  register context *ctx = myctx;
00354  register struct buddyfree *tb = ctx->thr_buddy;
00355 
00356 #if defined(DEBUG) || defined(DEBUG_COUNT)
00357  static int count = 0;
00358 
00359  count++;
00360 
00361  if (nils > s) {
00362    printf("alloc:%d:nils(=%d) > s(=%d)!!\n", count, nils, s);
00363  }
00364 #endif
00365  ss = max(3, s + 1);     /* one more word for the allocation information */
00366  while (buddysize[req] < ss) req++;
00367 #ifdef DEBUG
00368  printf("alloc:%d:s=%d, e=%d, cid=%d, nils=%d\n",
00369          count, s, e, cid, nils);
00370 #endif
00371  if (req >= MAXTHRBUDDY)
00372    b = rgc_root_alloc_big(ctx, req);
00373  else { /* small cell is requested */
00374    if (tb[req].count == 0) { /* find a cell in the local free list */
00375      rgc_root_alloc_small(ctx, req);
00376 #ifdef DEBUG
00377      printf("alloc:");
00378      dump_bcell(req,ctx->thr_buddy);
00379 #endif
00380    }
00381    ASSERT(tb[req].bp != 0);
00382 #if THREADED
00383    rw_rdlock(&gc_lock);
00384 #endif
00385 #ifdef DEBUG
00386    fflush( stdout );
00387    printf("alloc:%d:", count);
00388    dump_bcell( req, tb );
00389 #endif
00390    b = tb[req].bp;
00391 #ifdef RGC
00392    //    take_care(ctx->lastalloc);
00393 #endif
00394    ctx->lastalloc=makepointer(b);
00395    ss = buddysize[req]-1;
00396    tb[req].bp = b->b.nextbcell;
00397 #if defined(DEBUG) || defined(UALLOC_DEBUG)
00398    printf("alloc:%d:allocate for user[%d(buddysize=%d)] = 0x%lx: new list top = 0x%lx\n",
00399            count, req, buddysize[req], b, tb[req].bp);
00400 #endif
00401    for (i = 0; i < ss; i++) 
00402      b->b.c[i] = 0;
00403    tb[req].count--;
00404 #if THREADED
00405    rw_unlock(&gc_lock);
00406 #endif
00407  }
00408 
00409 #ifdef __USE_MARK_BITMAP
00410  /* PHASE_ROOT_REM or PHASE_MARK or PHASE_SWEEP */
00411  if (gc_phase >= PHASE_SWEEP) {
00412    markon(b);
00413  } else {
00414    b->h.cix = cid;
00415  }
00416  //  fprintf(stderr, "tag=%x\n", b->h.bix & 0xff);
00417 #else
00418  /* sweeping_state.chp synchronization needs only memory barriers */
00419  /* sweeping_state.p synchronization needs collector_lock */
00420  if (gc_phase >= PHASE_SWEEP) { 
00421 //   lock_collector;
00422    if (gc_phase >= PHASE_MARK) {
00423      /*** critical section start ***/
00424      markon(b);
00425      b->h.cix = cid;
00426      /*** critical section end ***/
00427      if (gc_phase < PHASE_MARK) {
00428        /* sweeper might hava passed, because gc_phase has changed. */
00429        lock_collector;
00430        /* we have locked collector, so sweeping_state is consistent. */
00431        if (sweeping_state.p > b) {
00432          markoff(b);
00433        }
00434        unlock_collector;
00435      }
00436    } else if (gc_phase == PHASE_SWEEP) {
00437      if (b >= (bpointer)sweeping_state.chp) {
00438      /*** critical section start ***/
00439        markon(b);
00440        b->h.cix = cid;
00441      /*** critical section end ***/
00442        if (b <= (bpointer)sweeping_state.chp->nextchunk) {
00443          if (b < (bpointer)sweeping_state.chp) /* correct memory barriers are needed. */  
00444            markoff(b); /* sweeper have passed. */
00445          else { /* sweeper may have passed or may not. */
00446            lock_collector;
00447            if (b < sweeping_state.p) {
00448              markoff(b);
00449            }
00450            unlock_collector;
00451          }
00452        }
00453      } 
00454 //     unlock_collector;
00455    b->h.cix = cid;
00456    }
00457  } else { 
00458    b->h.cix = cid;
00459  }
00460 #endif
00461 
00462  b->h.elmtype = e;
00463 #ifndef RGC
00464  b->h.extra = 0;
00465 #endif
00466  b->h.nodispose = 0;
00467  p = makepointer(b);
00468  v = p->c.obj.iv;
00469 #ifdef DEBUG
00470  printf( "alloc:%d:fill NIL:nils = %d, s = %d\n",
00471          count, nils, s );
00472 #endif
00473  i = 0;
00474  while (i < nils) v[i++] = NIL; /* fill NILs in user's  slots */
00475  /* while (nils<s) v[nils++]=NIL; */
00476  i = buddysize[req] - 1;
00477  while (s < i) v[s++] = NULL;   /* fill NULLs in buddy-cells extra slots */
00478 #ifdef DEBUG
00479  printf( "alloc:%d:after filling NIL:", count );
00480  dump_bcell( req, tb );
00481 #endif
00482 #ifdef RGC
00483  //  take_care(ctx->lastalloc);
00484 #endif
00485 #ifdef __PROFILE_GC
00486  allocd_words += buddysize[req];
00487 #endif
00488  return(p);
00489 }
00490 


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