Back to index

radiance  4R0+20100331
ambient.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: ambient.c,v 2.67 2007/11/17 06:21:58 greg Exp $";
00003 #endif
00004 /*
00005  *  ambient.c - routines dealing with ambient (inter-reflected) component.
00006  *
00007  *  Declarations of external symbols in ambient.h
00008  */
00009 
00010 #include "copyright.h"
00011 
00012 #include <string.h>
00013 
00014 #include  "platform.h"
00015 #include  "ray.h"
00016 #include  "otypes.h"
00017 #include  "resolu.h"
00018 #include  "ambient.h"
00019 #include  "random.h"
00020 
00021 #ifndef  OCTSCALE
00022 #define        OCTSCALE     1.0    /* ceil((valid rad.)/(cube size)) */
00023 #endif
00024 
00025 extern char  *shm_boundary; /* memory sharing boundary */
00026 
00027 #ifndef  MAXASET
00028 #define        MAXASET      4095   /* maximum number of elements in ambient set */
00029 #endif
00030 OBJECT ambset[MAXASET+1]={0};      /* ambient include/exclude set */
00031 
00032 double maxarad;             /* maximum ambient radius */
00033 double minarad;             /* minimum ambient radius */
00034 
00035 static AMBTREE       atrunk;              /* our ambient trunk node */
00036 
00037 static FILE  *ambfp = NULL; /* ambient file pointer */
00038 static int  nunflshed = 0;  /* number of unflushed ambient values */
00039 
00040 #ifndef SORT_THRESH
00041 #ifdef SMLMEM
00042 #define SORT_THRESH  ((3L<<20)/sizeof(AMBVAL))
00043 #else
00044 #define SORT_THRESH  ((9L<<20)/sizeof(AMBVAL))
00045 #endif
00046 #endif
00047 #ifndef SORT_INTVL
00048 #define SORT_INTVL   (SORT_THRESH<<1)
00049 #endif
00050 #ifndef MAX_SORT_INTVL
00051 #define MAX_SORT_INTVL      (SORT_INTVL<<6)
00052 #endif
00053 
00054 static double  avsum = 0.;         /* computed ambient value sum (log) */
00055 static unsigned int  navsum = 0;   /* number of values in avsum */
00056 static unsigned int  nambvals = 0; /* total number of indirect values */
00057 static unsigned int  nambshare = 0;       /* number of values from file */
00058 static unsigned long  ambclock = 0;       /* ambient access clock */
00059 static unsigned long  lastsort = 0;       /* time of last value sort */
00060 static long  sortintvl = SORT_INTVL;      /* time until next sort */
00061 static FILE  *ambinp = NULL;              /* auxiliary file for input */
00062 static long  lastpos = -1;         /* last flush position */
00063 
00064 #define MAXACLOCK    (1L<<30)      /* clock turnover value */
00065        /*
00066         * Track access times unless we are sharing ambient values
00067         * through memory on a multiprocessor, when we want to avoid
00068         * claiming our own memory (copy on write).  Go ahead anyway
00069         * if more than two thirds of our values are unshared.
00070         * Compile with -Dtracktime=0 to turn this code off.
00071         */
00072 #ifndef tracktime
00073 #define tracktime    (shm_boundary == NULL || nambvals > 3*nambshare)
00074 #endif
00075 
00076 #define        AMBFLUSH     (BUFSIZ/AMBVALSIZ)
00077 
00078 #define        newambval()  (AMBVAL *)malloc(sizeof(AMBVAL))
00079 #define  freeav(av)  free((void *)av);
00080 
00081 static void initambfile(int creat);
00082 static void avsave(AMBVAL *av);
00083 static AMBVAL *avstore(AMBVAL  *aval);
00084 static AMBTREE *newambtree(void);
00085 static void freeambtree(AMBTREE  *atp);
00086 
00087 typedef void unloadtf_t(void *);
00088 static unloadtf_t avinsert;
00089 static unloadtf_t av2list;
00090 static void unloadatree(AMBTREE  *at, unloadtf_t *f);
00091 
00092 static int aposcmp(const void *avp1, const void *avp2);
00093 static int avlmemi(AMBVAL *avaddr);
00094 static void sortambvals(int always);
00095 
00096 #ifdef  F_SETLKW
00097 static void aflock(int  typ);
00098 #endif
00099 
00100 
00101 extern void
00102 setambres(                         /* set ambient resolution */
00103        int  ar
00104 )
00105 {
00106        ambres = ar < 0 ? 0 : ar;          /* may be done already */
00107                                           /* set min & max radii */
00108        if (ar <= 0) {
00109               minarad = 0;
00110               maxarad = thescene.cusize / 2.0;
00111        } else {
00112               minarad = thescene.cusize / ar;
00113               maxarad = 64 * minarad;                   /* heuristic */
00114               if (maxarad > thescene.cusize / 2.0)
00115                      maxarad = thescene.cusize / 2.0;
00116        }
00117        if (minarad <= FTINY)
00118               minarad = 10*FTINY;
00119        if (maxarad <= minarad)
00120               maxarad = 64 * minarad;
00121 }
00122 
00123 
00124 extern void
00125 setambacc(                         /* set ambient accuracy */
00126        double  newa
00127 )
00128 {
00129        double  ambdiff;
00130 
00131        if (newa < 0.0)
00132               newa = 0.0;
00133        ambdiff = fabs(newa - ambacc);
00134        if (ambdiff >= .01 && (ambacc = newa) > FTINY && nambvals > 0)
00135               sortambvals(1);                    /* rebuild tree */
00136 }
00137 
00138 
00139 extern void
00140 setambient(void)                          /* initialize calculation */
00141 {
00142        int    readonly = 0;
00143        long   flen;
00144        AMBVAL amb;
00145                                           /* make sure we're fresh */
00146        ambdone();
00147                                           /* init ambient limits */
00148        setambres(ambres);
00149        setambacc(ambacc);
00150        if (ambfile == NULL || !ambfile[0])
00151               return;
00152        if (ambacc <= FTINY) {
00153               sprintf(errmsg, "zero ambient accuracy so \"%s\" not opened",
00154                             ambfile);
00155               error(WARNING, errmsg);
00156               return;
00157        }
00158                                           /* open ambient file */
00159        if ((ambfp = fopen(ambfile, "r+")) == NULL)
00160               readonly = (ambfp = fopen(ambfile, "r")) != NULL;
00161        if (ambfp != NULL) {
00162               initambfile(0);                    /* file exists */
00163               lastpos = ftell(ambfp);
00164               while (readambval(&amb, ambfp))
00165                      avinsert(avstore(&amb));
00166               nambshare = nambvals;              /* share loaded values */
00167               if (readonly) {
00168                      sprintf(errmsg,
00169                             "loaded %u values from read-only ambient file",
00170                                    nambvals);
00171                      error(WARNING, errmsg);
00172                      fclose(ambfp);              /* close file so no writes */
00173                      ambfp = NULL;
00174                      return;                     /* avoid ambsync() */
00175               }
00176                                           /* align file pointer */
00177               lastpos += (long)nambvals*AMBVALSIZ;
00178               flen = lseek(fileno(ambfp), (off_t)0, SEEK_END);
00179               if (flen != lastpos) {
00180                      sprintf(errmsg,
00181                      "ignoring last %ld values in ambient file (corrupted)",
00182                                    (flen - lastpos)/AMBVALSIZ);
00183                      error(WARNING, errmsg);
00184                      fseek(ambfp, lastpos, SEEK_SET);
00185 #ifndef _WIN32 /* XXX we need a replacement for that one */
00186                      ftruncate(fileno(ambfp), (off_t)lastpos);
00187 #endif
00188               }
00189        } else if ((ambfp = fopen(ambfile, "w+")) != NULL) {
00190               initambfile(1);                    /* else create new file */
00191               lastpos = ftell(ambfp);
00192        } else {
00193               sprintf(errmsg, "cannot open ambient file \"%s\"", ambfile);
00194               error(SYSTEM, errmsg);
00195        }
00196        ambsync();                  /* load previous values */
00197 }
00198 
00199 
00200 extern void
00201 ambdone(void)               /* close ambient file and free memory */
00202 {
00203        if (ambfp != NULL) {        /* close ambient file */
00204               ambsync();
00205               fclose(ambfp);
00206               ambfp = NULL;
00207               if (ambinp != NULL) {       
00208                      fclose(ambinp);
00209                      ambinp = NULL;
00210               }
00211               lastpos = -1;
00212        }
00213                                    /* free ambient tree */
00214        unloadatree(&atrunk, free);
00215                                    /* reset state variables */
00216        avsum = 0.;
00217        navsum = 0;
00218        nambvals = 0;
00219        nambshare = 0;
00220        ambclock = 0;
00221        lastsort = 0;
00222        sortintvl = SORT_INTVL;
00223 }
00224 
00225 
00226 extern void
00227 ambnotify(                  /* record new modifier */
00228        OBJECT obj
00229 )
00230 {
00231        static int  hitlimit = 0;
00232        register OBJREC       *o;
00233        register char  **amblp;
00234 
00235        if (obj == OVOID) {         /* starting over */
00236               ambset[0] = 0;
00237               hitlimit = 0;
00238               return;
00239        }
00240        o = objptr(obj);
00241        if (hitlimit || !ismodifier(o->otype))
00242               return;
00243        for (amblp = amblist; *amblp != NULL; amblp++)
00244               if (!strcmp(o->oname, *amblp)) {
00245                      if (ambset[0] >= MAXASET) {
00246                             error(WARNING, "too many modifiers in ambient list");
00247                             hitlimit++;
00248                             return;              /* should this be fatal? */
00249                      }
00250                      insertelem(ambset, obj);
00251                      return;
00252               }
00253 }
00254 
00255 
00256 extern void
00257 multambient(         /* compute ambient component & multiply by coef. */
00258        COLOR  aval,
00259        register RAY  *r,
00260        FVECT  nrm
00261 )
00262 {
00263        static int  rdepth = 0;                   /* ambient recursion */
00264        COLOR  acol;
00265        double d, l;
00266 
00267        if (ambdiv <= 0)                   /* no ambient calculation */
00268               goto dumbamb;
00269                                           /* check number of bounces */
00270        if (rdepth >= ambounce)
00271               goto dumbamb;
00272                                           /* check ambient list */
00273        if (ambincl != -1 && r->ro != NULL &&
00274                      ambincl != inset(ambset, r->ro->omod))
00275               goto dumbamb;
00276 
00277        if (ambacc <= FTINY) {                    /* no ambient storage */
00278               copycolor(acol, aval);
00279               rdepth++;
00280               d = doambient(acol, r, r->rweight, NULL, NULL);
00281               rdepth--;
00282               if (d <= FTINY)
00283                      goto dumbamb;
00284               copycolor(aval, acol);
00285               return;
00286        }
00287 
00288        if (tracktime)                            /* sort to minimize thrashing */
00289               sortambvals(0);
00290                                           /* interpolate ambient value */
00291        setcolor(acol, 0.0, 0.0, 0.0);
00292        d = sumambient(acol, r, nrm, rdepth,
00293                      &atrunk, thescene.cuorg, thescene.cusize);
00294        if (d > FTINY) {
00295               d = 1.0/d;
00296               scalecolor(acol, d);
00297               multcolor(aval, acol);
00298               return;
00299        }
00300        rdepth++;                          /* need to cache new value */
00301        d = makeambient(acol, r, nrm, rdepth-1);
00302        rdepth--;
00303        if (d > FTINY) {
00304               multcolor(aval, acol);             /* got new value */
00305               return;
00306        }
00307 dumbamb:                                  /* return global value */
00308        if ((ambvwt <= 0) | (navsum == 0)) {
00309               multcolor(aval, ambval);
00310               return;
00311        }
00312        l = bright(ambval);                /* average in computations */
00313        if (l > FTINY) {
00314               d = (log(l)*(double)ambvwt + avsum) /
00315                             (double)(ambvwt + navsum);
00316               d = exp(d) / l;
00317               scalecolor(aval, d);
00318               multcolor(aval, ambval);    /* apply color of ambval */
00319        } else {
00320               d = exp( avsum / (double)navsum );
00321               scalecolor(aval, d);        /* neutral color */
00322        }
00323 }
00324 
00325 
00326 extern double
00327 sumambient(   /* get interpolated ambient value */
00328        COLOR  acol,
00329        register RAY  *r,
00330        FVECT  rn,
00331        int  al,
00332        AMBTREE        *at,
00333        FVECT  c0,
00334        double s
00335 )
00336 {
00337        double d, e1, e2, wt, wsum;
00338        COLOR  ct;
00339        FVECT  ck0;
00340        int  i;
00341        register int  j;
00342        register AMBVAL       *av;
00343 
00344        wsum = 0.0;
00345                                    /* do this node */
00346        for (av = at->alist; av != NULL; av = av->next) {
00347               double rn_dot = -2.0;
00348               if (tracktime)
00349                      av->latick = ambclock;
00350               /*
00351                *  Ambient level test.
00352                */
00353               if (av->lvl > al)    /* list sorted, so this works */
00354                      break;
00355               if (av->weight < 0.9*r->rweight)
00356                      continue;
00357               /*
00358                *  Ambient radius test.
00359                */
00360               d = av->pos[0] - r->rop[0];
00361               e1 = d * d;
00362               d = av->pos[1] - r->rop[1];
00363               e1 += d * d;
00364               d = av->pos[2] - r->rop[2];
00365               e1 += d * d;
00366               e1 /= av->rad * av->rad;
00367               if (e1 > ambacc*ambacc*1.21)
00368                      continue;
00369               /*
00370                *  Direction test using closest normal.
00371                */
00372               d = DOT(av->dir, r->ron);
00373               if (rn != r->ron) {
00374                      rn_dot = DOT(av->dir, rn);
00375                      if (rn_dot > 1.0-FTINY)
00376                             rn_dot = 1.0-FTINY;
00377                      if (rn_dot >= d-FTINY) {
00378                             d = rn_dot;
00379                             rn_dot = -2.0;
00380                      }
00381               }
00382               e2 = (1.0 - d) * r->rweight;
00383               if (e2 < 0.0) e2 = 0.0;
00384               if (e1 + e2 > ambacc*ambacc*1.21)
00385                      continue;
00386               /*
00387                *  Ray behind test.
00388                */
00389               d = 0.0;
00390               for (j = 0; j < 3; j++)
00391                      d += (r->rop[j] - av->pos[j]) *
00392                                    (av->dir[j] + r->ron[j]);
00393               if (d*0.5 < -minarad*ambacc-.001)
00394                      continue;
00395               /*
00396                *  Jittering final test reduces image artifacts.
00397                */
00398               e1 = sqrt(e1);
00399               e2 = sqrt(e2);
00400               wt = e1 + e2;
00401               if (wt > ambacc*(.9+.2*urand(9015+samplendx)))
00402                      continue;
00403               /*
00404                *  Recompute directional error using perturbed normal
00405                */
00406               if (rn_dot > 0.0) {
00407                      e2 = sqrt((1.0 - rn_dot)*r->rweight);
00408                      wt = e1 + e2;
00409               }
00410               if (wt <= 1e-3)
00411                      wt = 1e3;
00412               else
00413                      wt = 1.0 / wt;
00414               wsum += wt;
00415               extambient(ct, av, r->rop, rn);
00416               scalecolor(ct, wt);
00417               addcolor(acol, ct);
00418        }
00419        if (at->kid == NULL)
00420               return(wsum);
00421                                    /* do children */
00422        s *= 0.5;
00423        for (i = 0; i < 8; i++) {
00424               for (j = 0; j < 3; j++) {
00425                      ck0[j] = c0[j];
00426                      if (1<<j & i)
00427                             ck0[j] += s;
00428                      if (r->rop[j] < ck0[j] - OCTSCALE*s)
00429                             break;
00430                      if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
00431                             break;
00432               }
00433               if (j == 3)
00434                      wsum += sumambient(acol, r, rn, al,
00435                                           at->kid+i, ck0, s);
00436        }
00437        return(wsum);
00438 }
00439 
00440 
00441 extern double
00442 makeambient(         /* make a new ambient value for storage */
00443        COLOR  acol,
00444        RAY  *r,
00445        FVECT  rn,
00446        int  al
00447 )
00448 {
00449        AMBVAL amb;
00450        FVECT  gp, gd;
00451        int    i;
00452 
00453        amb.weight = 1.0;                  /* compute weight */
00454        for (i = al; i-- > 0; )
00455               amb.weight *= AVGREFL;
00456        if (r->rweight < 0.1*amb.weight)   /* heuristic override */
00457               amb.weight = 1.25*r->rweight;
00458        setcolor(acol, AVGREFL, AVGREFL, AVGREFL);
00459                                           /* compute ambient */
00460        amb.rad = doambient(acol, r, amb.weight, gp, gd);
00461        if (amb.rad <= FTINY) {
00462               setcolor(acol, 0.0, 0.0, 0.0);
00463               return(0.0);
00464        }
00465        scalecolor(acol, 1./AVGREFL);             /* undo assumed reflectance */
00466                                           /* store value */
00467        VCOPY(amb.pos, r->rop);
00468        VCOPY(amb.dir, r->ron);
00469        amb.lvl = al;
00470        copycolor(amb.val, acol);
00471        VCOPY(amb.gpos, gp);
00472        VCOPY(amb.gdir, gd);
00473                                           /* insert into tree */
00474        avsave(&amb);                      /* and save to file */
00475        if (rn != r->ron)
00476               extambient(acol, &amb, r->rop, rn);       /* texture */
00477        return(amb.rad);
00478 }
00479 
00480 
00481 extern void
00482 extambient(          /* extrapolate value at pv, nv */
00483        COLOR  cr,
00484        register AMBVAL       *ap,
00485        FVECT  pv,
00486        FVECT  nv
00487 )
00488 {
00489        FVECT  v1;
00490        register int  i;
00491        double d;
00492 
00493        d = 1.0;                    /* zeroeth order */
00494                                    /* gradient due to translation */
00495        for (i = 0; i < 3; i++)
00496               d += ap->gpos[i]*(pv[i]-ap->pos[i]);
00497                                    /* gradient due to rotation */
00498        VCROSS(v1, ap->dir, nv);
00499        d += DOT(ap->gdir, v1);
00500        if (d <= 0.0) {
00501               setcolor(cr, 0.0, 0.0, 0.0);
00502               return;
00503        }
00504        copycolor(cr, ap->val);
00505        scalecolor(cr, d);
00506 }
00507 
00508 
00509 static void
00510 initambfile(         /* initialize ambient file */
00511        int  creat
00512 )
00513 {
00514        extern char  *progname, *octname;
00515        static char  *mybuf = NULL;
00516 
00517 #ifdef F_SETLKW
00518        aflock(creat ? F_WRLCK : F_RDLCK);
00519 #endif
00520        SET_FILE_BINARY(ambfp);
00521        if (mybuf == NULL)
00522               mybuf = (char *)bmalloc(BUFSIZ+8);
00523        setbuf(ambfp, mybuf);
00524        if (creat) {                /* new file */
00525               newheader("RADIANCE", ambfp);
00526               fprintf(ambfp, "%s -av %g %g %g -aw %d -ab %d -aa %g ",
00527                             progname, colval(ambval,RED),
00528                             colval(ambval,GRN), colval(ambval,BLU),
00529                             ambvwt, ambounce, ambacc);
00530               fprintf(ambfp, "-ad %d -as %d -ar %d ",
00531                             ambdiv, ambssamp, ambres);
00532               if (octname != NULL)
00533                      printargs(1, &octname, ambfp);
00534               else
00535                      fputc('\n', ambfp);
00536               fprintf(ambfp, "SOFTWARE= %s\n", VersionID);
00537               fputnow(ambfp);
00538               fputformat(AMBFMT, ambfp);
00539               putc('\n', ambfp);
00540               putambmagic(ambfp);
00541        } else if (checkheader(ambfp, AMBFMT, NULL) < 0 || !hasambmagic(ambfp))
00542               error(USER, "bad ambient file");
00543 }
00544 
00545 
00546 static void
00547 avsave(                            /* insert and save an ambient value */
00548        AMBVAL *av
00549 )
00550 {
00551        avinsert(avstore(av));
00552        if (ambfp == NULL)
00553               return;
00554        if (writambval(av, ambfp) < 0)
00555               goto writerr;
00556        if (++nunflshed >= AMBFLUSH)
00557               if (ambsync() == EOF)
00558                      goto writerr;
00559        return;
00560 writerr:
00561        error(SYSTEM, "error writing to ambient file");
00562 }
00563 
00564 
00565 static AMBVAL *
00566 avstore(                           /* allocate memory and store aval */
00567        register AMBVAL  *aval
00568 )
00569 {
00570        register AMBVAL  *av;
00571        double d;
00572 
00573        if ((av = newambval()) == NULL)
00574               error(SYSTEM, "out of memory in avstore");
00575        *av = *aval;
00576        av->latick = ambclock;
00577        av->next = NULL;
00578        nambvals++;
00579        d = bright(av->val);
00580        if (d > FTINY) {            /* add to log sum for averaging */
00581               avsum += log(d);
00582               navsum++;
00583        }
00584        return(av);
00585 }
00586 
00587 
00588 #define ATALLOCSZ    512           /* #/8 trees to allocate at once */
00589 
00590 static AMBTREE  *atfreelist = NULL;       /* free ambient tree structures */
00591 
00592 
00593 static AMBTREE *
00594 newambtree(void)                          /* allocate 8 ambient tree structs */
00595 {
00596        register AMBTREE  *atp, *upperlim;
00597 
00598        if (atfreelist == NULL) {   /* get more nodes */
00599               atfreelist = (AMBTREE *)malloc(ATALLOCSZ*8*sizeof(AMBTREE));
00600               if (atfreelist == NULL)
00601                      return(NULL);
00602                                    /* link new free list */
00603               upperlim = atfreelist + 8*(ATALLOCSZ-1);
00604               for (atp = atfreelist; atp < upperlim; atp += 8)
00605                      atp->kid = atp + 8;
00606               atp->kid = NULL;
00607        }
00608        atp = atfreelist;
00609        atfreelist = atp->kid;
00610        memset((char *)atp, '\0', 8*sizeof(AMBTREE));
00611        return(atp);
00612 }
00613 
00614 
00615 static void
00616 freeambtree(                /* free 8 ambient tree structs */
00617        AMBTREE  *atp
00618 )
00619 {
00620        atp->kid = atfreelist;
00621        atfreelist = atp;
00622 }
00623 
00624 
00625 static void
00626 avinsert(                          /* insert ambient value in our tree */
00627        void *av
00628 )
00629 {
00630        register AMBTREE  *at;
00631        register AMBVAL  *ap;
00632        AMBVAL  avh;
00633        FVECT  ck0;
00634        double s;
00635        int  branch;
00636        register int  i;
00637 
00638        if (((AMBVAL*)av)->rad <= FTINY)
00639               error(CONSISTENCY, "zero ambient radius in avinsert");
00640        at = &atrunk;
00641        VCOPY(ck0, thescene.cuorg);
00642        s = thescene.cusize;
00643        while (s*(OCTSCALE/2) > ((AMBVAL*)av)->rad*ambacc) {
00644               if (at->kid == NULL)
00645                      if ((at->kid = newambtree()) == NULL)
00646                             error(SYSTEM, "out of memory in avinsert");
00647               s *= 0.5;
00648               branch = 0;
00649               for (i = 0; i < 3; i++)
00650                      if (((AMBVAL*)av)->pos[i] > ck0[i] + s) {
00651                             ck0[i] += s;
00652                             branch |= 1 << i;
00653                      }
00654               at = at->kid + branch;
00655        }
00656        avh.next = at->alist;              /* order by increasing level */
00657        for (ap = &avh; ap->next != NULL; ap = ap->next)
00658               if (ap->next->lvl >= ((AMBVAL*)av)->lvl)
00659                      break;
00660        ((AMBVAL*)av)->next = ap->next;
00661        ap->next = (AMBVAL*)av;
00662        at->alist = avh.next;
00663 }
00664 
00665 
00666 static void
00667 unloadatree(                /* unload an ambient value tree */
00668        register AMBTREE  *at,
00669        unloadtf_t *f
00670 )
00671 {
00672        register AMBVAL  *av;
00673        register int  i;
00674                                    /* transfer values at this node */
00675        for (av = at->alist; av != NULL; av = at->alist) {
00676               at->alist = av->next;
00677               (*f)(av);
00678        }
00679        if (at->kid == NULL)
00680               return;
00681        for (i = 0; i < 8; i++)            /* transfer and free children */
00682               unloadatree(at->kid+i, f);
00683        freeambtree(at->kid);
00684        at->kid = NULL;
00685 }
00686 
00687 
00688 static struct avl {
00689        AMBVAL *p;
00690        unsigned long t;
00691 }      *avlist1;                   /* ambient value list with ticks */
00692 static AMBVAL **avlist2;           /* memory positions for sorting */
00693 static int    i_avlist;            /* index for lists */
00694 
00695 static int alatcmp(const void *av1, const void *av2);
00696 
00697 static void
00698 av2list(
00699        void *av
00700 )
00701 {
00702 #ifdef DEBUG
00703        if (i_avlist >= nambvals)
00704               error(CONSISTENCY, "too many ambient values in av2list1");
00705 #endif
00706        avlist1[i_avlist].p = avlist2[i_avlist] = (AMBVAL*)av;
00707        avlist1[i_avlist++].t = ((AMBVAL*)av)->latick;
00708 }
00709 
00710 
00711 static int
00712 alatcmp(                    /* compare ambient values for MRA */
00713        const void *av1,
00714        const void *av2
00715 )
00716 {
00717        register long  lc = ((struct avl *)av2)->t - ((struct avl *)av1)->t;
00718        return(lc<0 ? -1 : lc>0 ? 1 : 0);
00719 }
00720 
00721 
00722 /* GW NOTE 2002/10/3:
00723  * I used to compare AMBVAL pointers, but found that this was the
00724  * cause of a serious consistency error with gcc, since the optimizer
00725  * uses some dangerous trick in pointer subtraction that
00726  * assumes pointers differ by exact struct size increments.
00727  */
00728 static int
00729 aposcmp(                    /* compare ambient value positions */
00730        const void    *avp1,
00731        const void    *avp2
00732 )
00733 {
00734        register long diff = *(char * const *)avp1 - *(char * const *)avp2;
00735        if (diff < 0)
00736               return(-1);
00737        return(diff > 0);
00738 }
00739 
00740 #if 1
00741 static int
00742 avlmemi(                           /* find list position from address */
00743        AMBVAL *avaddr
00744 )
00745 {
00746        register AMBVAL  **avlpp;
00747 
00748        avlpp = (AMBVAL **)bsearch((char *)&avaddr, (char *)avlist2,
00749                      nambvals, sizeof(AMBVAL *), aposcmp);
00750        if (avlpp == NULL)
00751               error(CONSISTENCY, "address not found in avlmemi");
00752        return(avlpp - avlist2);
00753 }
00754 #else
00755 #define avlmemi(avaddr)     ((AMBVAL **)bsearch((char *)&avaddr,(char *)avlist2, \
00756                             nambvals,sizeof(AMBVAL *),aposcmp) - avlist2)
00757 #endif
00758 
00759 
00760 static void
00761 sortambvals(                /* resort ambient values */
00762        int    always
00763 )
00764 {
00765        AMBTREE  oldatrunk;
00766        AMBVAL tav, *tap, *pnext;
00767        register int  i, j;
00768                                    /* see if it's time yet */
00769        if (!always && (ambclock++ < lastsort+sortintvl ||
00770                      nambvals < SORT_THRESH))
00771               return;
00772        /*
00773         * The idea here is to minimize memory thrashing
00774         * in VM systems by improving reference locality.
00775         * We do this by periodically sorting our stored ambient
00776         * values in memory in order of most recently to least
00777         * recently accessed.  This ordering was chosen so that new
00778         * ambient values (which tend to be less important) go into
00779         * higher memory with the infrequently accessed values.
00780         *     Since we expect our values to need sorting less
00781         * frequently as the process continues, we double our
00782         * waiting interval after each call.
00783         *     This routine is also called by setambacc() with
00784         * the "always" parameter set to 1 so that the ambient
00785         * tree will be rebuilt with the new accuracy parameter.
00786         */
00787        if (tracktime) {            /* allocate pointer arrays to sort */
00788               avlist2 = (AMBVAL **)malloc(nambvals*sizeof(AMBVAL *));
00789               avlist1 = (struct avl *)malloc(nambvals*sizeof(struct avl));
00790        } else {
00791               avlist2 = NULL;
00792               avlist1 = NULL;
00793        }
00794        if (avlist1 == NULL) {             /* no time tracking -- rebuild tree? */
00795               if (avlist2 != NULL)
00796                      free((void *)avlist2);
00797               if (always) {        /* rebuild without sorting */
00798                      oldatrunk = atrunk;
00799                      atrunk.alist = NULL;
00800                      atrunk.kid = NULL;
00801                      unloadatree(&oldatrunk, avinsert);
00802               }
00803        } else {                    /* sort memory by last access time */
00804               /*
00805                * Sorting memory is tricky because it isn't contiguous.
00806                * We have to sort an array of pointers by MRA and also
00807                * by memory position.  We then copy values in "loops"
00808                * to minimize memory hits.  Nevertheless, we will visit
00809                * everyone at least twice, and this is an expensive process
00810                * when we're thrashing, which is when we need to do it.
00811                */
00812 #ifdef DEBUG
00813               sprintf(errmsg, "sorting %u ambient values at ambclock=%lu...",
00814                             nambvals, ambclock);
00815               eputs(errmsg);
00816 #endif
00817               i_avlist = 0;
00818               unloadatree(&atrunk, av2list);     /* empty current tree */
00819 #ifdef DEBUG
00820               if (i_avlist < nambvals)
00821                      error(CONSISTENCY, "missing ambient values in sortambvals");
00822 #endif
00823               qsort((char *)avlist1, nambvals, sizeof(struct avl), alatcmp);
00824               qsort((char *)avlist2, nambvals, sizeof(AMBVAL *), aposcmp);
00825               for (i = 0; i < nambvals; i++) {
00826                      if (avlist1[i].p == NULL)
00827                             continue;
00828                      tap = avlist2[i];
00829                      tav = *tap;
00830                      for (j = i; (pnext = avlist1[j].p) != tap;
00831                                    j = avlmemi(pnext)) {
00832                             *(avlist2[j]) = *pnext;
00833                             avinsert(avlist2[j]);
00834                             avlist1[j].p = NULL;
00835                      }
00836                      *(avlist2[j]) = tav;
00837                      avinsert(avlist2[j]);
00838                      avlist1[j].p = NULL;
00839               }
00840               free((void *)avlist1);
00841               free((void *)avlist2);
00842                                           /* compute new sort interval */
00843               sortintvl = ambclock - lastsort;
00844               if (sortintvl >= MAX_SORT_INTVL/2)
00845                      sortintvl = MAX_SORT_INTVL;
00846               else
00847                      sortintvl <<= 1;     /* wait twice as long next */
00848 #ifdef DEBUG
00849               eputs("done\n");
00850 #endif
00851        }
00852        if (ambclock >= MAXACLOCK)
00853               ambclock = MAXACLOCK/2;
00854        lastsort = ambclock;
00855 }
00856 
00857 
00858 #ifdef F_SETLKW
00859 
00860 static void
00861 aflock(                     /* lock/unlock ambient file */
00862        int  typ
00863 )
00864 {
00865        static struct flock  fls;   /* static so initialized to zeroes */
00866 
00867        if (typ == fls.l_type)             /* already called? */
00868               return;
00869        fls.l_type = typ;
00870        if (fcntl(fileno(ambfp), F_SETLKW, &fls) < 0)
00871               error(SYSTEM, "cannot (un)lock ambient file");
00872 }
00873 
00874 
00875 extern int
00876 ambsync(void)               /* synchronize ambient file */
00877 {
00878        long  flen;
00879        AMBVAL avs;
00880        register int  n;
00881 
00882        if (ambfp == NULL)   /* no ambient file? */
00883               return(0);
00884                             /* gain appropriate access */
00885        aflock(nunflshed ? F_WRLCK : F_RDLCK);
00886                             /* see if file has grown */
00887        if ((flen = lseek(fileno(ambfp), (off_t)0, SEEK_END)) < 0)
00888               goto seekerr;
00889        if ( (n = flen - lastpos) ) {             /* file has grown */
00890               if (ambinp == NULL) {              /* use duplicate filedes */
00891                      ambinp = fdopen(dup(fileno(ambfp)), "r");
00892                      if (ambinp == NULL)
00893                             error(SYSTEM, "fdopen failed in ambsync");
00894               }
00895               if (fseek(ambinp, lastpos, SEEK_SET) < 0)
00896                      goto seekerr;
00897               while (n >= AMBVALSIZ) {    /* load contributed values */
00898                      if (!readambval(&avs, ambinp)) {
00899                             sprintf(errmsg,
00900                      "ambient file \"%s\" corrupted near character %ld",
00901                                           ambfile, flen - n);
00902                             error(WARNING, errmsg);
00903                             break;
00904                      }
00905                      avinsert(avstore(&avs));
00906                      n -= AMBVALSIZ;
00907               }
00908               lastpos = flen - n;
00909               /*** seek always as safety measure
00910               if (n) ***/                 /* alignment */
00911                      if (lseek(fileno(ambfp), (off_t)lastpos, SEEK_SET) < 0)
00912                             goto seekerr;
00913        }
00914 #ifdef  DEBUG
00915        if (ambfp->_ptr - ambfp->_base != nunflshed*AMBVALSIZ) {
00916               sprintf(errmsg, "ambient file buffer at %d rather than %d",
00917                             ambfp->_ptr - ambfp->_base,
00918                             nunflshed*AMBVALSIZ);
00919               error(CONSISTENCY, errmsg);
00920        }
00921 #endif
00922        n = fflush(ambfp);                 /* calls write() at last */
00923        if (n != EOF)
00924               lastpos += (long)nunflshed*AMBVALSIZ;
00925        else if ((lastpos = lseek(fileno(ambfp), (off_t)0, SEEK_CUR)) < 0)
00926               goto seekerr;
00927               
00928        aflock(F_UNLCK);                   /* release file */
00929        nunflshed = 0;
00930        return(n);
00931 seekerr:
00932        error(SYSTEM, "seek failed in ambsync");
00933        return -1; /* pro forma return */
00934 }
00935 
00936 #else
00937 
00938 extern int
00939 ambsync(void)               /* flush ambient file */
00940 {
00941        if (ambfp == NULL)
00942               return(0);
00943        nunflshed = 0;
00944        return(fflush(ambfp));
00945 }
00946 
00947 #endif