ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/ambient.c
Revision: 2.62
Committed: Mon Aug 22 16:07:26 2005 UTC (18 years, 7 months ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R7P2, rad3R8
Changes since 2.61: +2 -2 lines
Log Message:
Fixed bug in ambient calculation causing zero results for some scenes

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: ambient.c,v 2.61 2005/05/31 18:01:09 greg Exp $";
3 #endif
4 /*
5 * ambient.c - routines dealing with ambient (inter-reflected) component.
6 *
7 * Declarations of external symbols in ambient.h
8 */
9
10 #include "copyright.h"
11
12 #include <string.h>
13
14 #include "platform.h"
15 #include "ray.h"
16 #include "otypes.h"
17 #include "resolu.h"
18 #include "ambient.h"
19 #include "random.h"
20
21 #ifndef OCTSCALE
22 #define OCTSCALE 1.0 /* ceil((valid rad.)/(cube size)) */
23 #endif
24
25 extern char *shm_boundary; /* memory sharing boundary */
26
27 #ifndef MAXASET
28 #define MAXASET 2047 /* maximum number of elements in ambient set */
29 #endif
30 OBJECT ambset[MAXASET+1]={0}; /* ambient include/exclude set */
31
32 double maxarad; /* maximum ambient radius */
33 double minarad; /* minimum ambient radius */
34
35 static AMBTREE atrunk; /* our ambient trunk node */
36
37 static FILE *ambfp = NULL; /* ambient file pointer */
38 static int nunflshed = 0; /* number of unflushed ambient values */
39
40 #ifndef SORT_THRESH
41 #ifdef SMLMEM
42 #define SORT_THRESH ((3L<<20)/sizeof(AMBVAL))
43 #else
44 #define SORT_THRESH ((9L<<20)/sizeof(AMBVAL))
45 #endif
46 #endif
47 #ifndef SORT_INTVL
48 #define SORT_INTVL (SORT_THRESH<<1)
49 #endif
50 #ifndef MAX_SORT_INTVL
51 #define MAX_SORT_INTVL (SORT_INTVL<<6)
52 #endif
53
54 static double avsum = 0.; /* computed ambient value sum (log) */
55 static unsigned int navsum = 0; /* number of values in avsum */
56 static unsigned int nambvals = 0; /* total number of indirect values */
57 static unsigned int nambshare = 0; /* number of values from file */
58 static unsigned long ambclock = 0; /* ambient access clock */
59 static unsigned long lastsort = 0; /* time of last value sort */
60 static long sortintvl = SORT_INTVL; /* time until next sort */
61 static FILE *ambinp = NULL; /* auxiliary file for input */
62 static long lastpos = -1; /* last flush position */
63
64 #define MAXACLOCK (1L<<30) /* clock turnover value */
65 /*
66 * Track access times unless we are sharing ambient values
67 * through memory on a multiprocessor, when we want to avoid
68 * claiming our own memory (copy on write). Go ahead anyway
69 * if more than two thirds of our values are unshared.
70 * Compile with -Dtracktime=0 to turn this code off.
71 */
72 #ifndef tracktime
73 #define tracktime (shm_boundary == NULL || nambvals > 3*nambshare)
74 #endif
75
76 #define AMBFLUSH (BUFSIZ/AMBVALSIZ)
77
78 #define newambval() (AMBVAL *)malloc(sizeof(AMBVAL))
79 #define freeav(av) free((void *)av);
80
81 static void initambfile(int creat);
82 static void avsave(AMBVAL *av);
83 static AMBVAL *avstore(AMBVAL *aval);
84 static AMBTREE *newambtree(void);
85 static void freeambtree(AMBTREE *atp);
86
87 typedef void unloadtf_t(void *);
88 static unloadtf_t avinsert;
89 static unloadtf_t av2list;
90 static void unloadatree(AMBTREE *at, unloadtf_t *f);
91
92 static int aposcmp(const void *avp1, const void *avp2);
93 static int avlmemi(AMBVAL *avaddr);
94 static void sortambvals(int always);
95
96 #ifdef F_SETLKW
97 static void aflock(int typ);
98 #endif
99
100
101 extern void
102 setambres( /* set ambient resolution */
103 int ar
104 )
105 {
106 ambres = ar < 0 ? 0 : ar; /* may be done already */
107 /* set min & max radii */
108 if (ar <= 0) {
109 minarad = 0;
110 maxarad = thescene.cusize / 2.0;
111 } else {
112 minarad = thescene.cusize / ar;
113 maxarad = 64 * minarad; /* heuristic */
114 if (maxarad > thescene.cusize / 2.0)
115 maxarad = thescene.cusize / 2.0;
116 }
117 if (minarad <= FTINY)
118 minarad = 10*FTINY;
119 if (maxarad <= minarad)
120 maxarad = 64 * minarad;
121 }
122
123
124 extern void
125 setambacc( /* set ambient accuracy */
126 double newa
127 )
128 {
129 double ambdiff;
130
131 if (newa < 0.0)
132 newa = 0.0;
133 ambdiff = fabs(newa - ambacc);
134 if (ambdiff >= .01 && (ambacc = newa) > FTINY && nambvals > 0)
135 sortambvals(1); /* rebuild tree */
136 }
137
138
139 extern void
140 setambient(void) /* initialize calculation */
141 {
142 int readonly = 0;
143 long pos, flen;
144 AMBVAL amb;
145 /* make sure we're fresh */
146 ambdone();
147 /* init ambient limits */
148 setambres(ambres);
149 setambacc(ambacc);
150 if (ambfile == NULL || !ambfile[0])
151 return;
152 if (ambacc <= FTINY) {
153 sprintf(errmsg, "zero ambient accuracy so \"%s\" not opened",
154 ambfile);
155 error(WARNING, errmsg);
156 return;
157 }
158 /* open ambient file */
159 if ((ambfp = fopen(ambfile, "r+")) == NULL)
160 readonly = (ambfp = fopen(ambfile, "r")) != NULL;
161 if (ambfp != NULL) {
162 initambfile(0); /* file exists */
163 pos = ftell(ambfp);
164 while (readambval(&amb, ambfp))
165 avinsert(avstore(&amb));
166 nambshare = nambvals; /* share loaded values */
167 if (readonly) {
168 sprintf(errmsg,
169 "loaded %u values from read-only ambient file",
170 nambvals);
171 error(WARNING, errmsg);
172 fclose(ambfp); /* close file so no writes */
173 ambfp = NULL;
174 return; /* avoid ambsync() */
175 }
176 /* align file pointer */
177 pos += (long)nambvals*AMBVALSIZ;
178 flen = lseek(fileno(ambfp), (off_t)0, SEEK_END);
179 if (flen != pos) {
180 sprintf(errmsg,
181 "ignoring last %ld values in ambient file (corrupted)",
182 (flen - pos)/AMBVALSIZ);
183 error(WARNING, errmsg);
184 fseek(ambfp, pos, 0);
185 #ifndef _WIN32 /* XXX we need a replacement for that one */
186 ftruncate(fileno(ambfp), (off_t)pos);
187 #endif
188 }
189 } else if ((ambfp = fopen(ambfile, "w+")) != NULL) {
190 initambfile(1); /* else create new file */
191 } else {
192 sprintf(errmsg, "cannot open ambient file \"%s\"", ambfile);
193 error(SYSTEM, errmsg);
194 }
195 nunflshed++; /* lie */
196 ambsync();
197 }
198
199
200 extern void
201 ambdone(void) /* close ambient file and free memory */
202 {
203 if (ambfp != NULL) { /* close ambient file */
204 ambsync();
205 fclose(ambfp);
206 ambfp = NULL;
207 if (ambinp != NULL) {
208 fclose(ambinp);
209 ambinp = NULL;
210 }
211 lastpos = -1;
212 }
213 /* free ambient tree */
214 unloadatree(&atrunk, free);
215 /* reset state variables */
216 avsum = 0.;
217 navsum = 0;
218 nambvals = 0;
219 nambshare = 0;
220 ambclock = 0;
221 lastsort = 0;
222 sortintvl = SORT_INTVL;
223 }
224
225
226 extern void
227 ambnotify( /* record new modifier */
228 OBJECT obj
229 )
230 {
231 static int hitlimit = 0;
232 register OBJREC *o;
233 register char **amblp;
234
235 if (obj == OVOID) { /* starting over */
236 ambset[0] = 0;
237 hitlimit = 0;
238 return;
239 }
240 o = objptr(obj);
241 if (hitlimit || !ismodifier(o->otype))
242 return;
243 for (amblp = amblist; *amblp != NULL; amblp++)
244 if (!strcmp(o->oname, *amblp)) {
245 if (ambset[0] >= MAXASET) {
246 error(WARNING, "too many modifiers in ambient list");
247 hitlimit++;
248 return; /* should this be fatal? */
249 }
250 insertelem(ambset, obj);
251 return;
252 }
253 }
254
255
256 extern void
257 multambient( /* compute ambient component & multiply by coef. */
258 COLOR aval,
259 register RAY *r,
260 FVECT nrm
261 )
262 {
263 static int rdepth = 0; /* ambient recursion */
264 COLOR acol;
265 double d, l;
266
267 if (ambdiv <= 0) /* no ambient calculation */
268 goto dumbamb;
269 /* check number of bounces */
270 if (rdepth >= ambounce)
271 goto dumbamb;
272 /* check ambient list */
273 if (ambincl != -1 && r->ro != NULL &&
274 ambincl != inset(ambset, r->ro->omod))
275 goto dumbamb;
276
277 if (ambacc <= FTINY) { /* no ambient storage */
278 copycolor(acol, aval);
279 rdepth++;
280 d = doambient(acol, r, r->rweight, NULL, NULL);
281 rdepth--;
282 if (d <= FTINY)
283 goto dumbamb;
284 copycolor(aval, acol);
285 return;
286 }
287
288 if (tracktime) /* sort to minimize thrashing */
289 sortambvals(0);
290 /* interpolate ambient value */
291 setcolor(acol, 0.0, 0.0, 0.0);
292 d = sumambient(acol, r, nrm, rdepth,
293 &atrunk, thescene.cuorg, thescene.cusize);
294 if (d > FTINY) {
295 d = 1.0/d;
296 scalecolor(acol, d);
297 multcolor(aval, acol);
298 return;
299 }
300 rdepth++; /* need to cache new value */
301 d = makeambient(acol, r, nrm, rdepth-1);
302 rdepth--;
303 if (d > FTINY) {
304 multcolor(aval, acol); /* got new value */
305 return;
306 }
307 dumbamb: /* return global value */
308 if ((ambvwt <= 0) | (navsum == 0)) {
309 multcolor(aval, ambval);
310 return;
311 }
312 l = bright(ambval); /* average in computations */
313 if (l > FTINY) {
314 d = (log(l)*(double)ambvwt + avsum) /
315 (double)(ambvwt + navsum);
316 d = exp(d) / l;
317 scalecolor(aval, d);
318 multcolor(aval, ambval); /* apply color of ambval */
319 } else {
320 d = exp( avsum / (double)navsum );
321 scalecolor(aval, d); /* neutral color */
322 }
323 }
324
325
326 extern double
327 sumambient( /* get interpolated ambient value */
328 COLOR acol,
329 register RAY *r,
330 FVECT rn,
331 int al,
332 AMBTREE *at,
333 FVECT c0,
334 double s
335 )
336 {
337 double d, e1, e2, wt, wsum;
338 COLOR ct;
339 FVECT ck0;
340 int i;
341 register int j;
342 register AMBVAL *av;
343
344 wsum = 0.0;
345 /* do this node */
346 for (av = at->alist; av != NULL; av = av->next) {
347 double rn_dot = -2.0;
348 if (tracktime)
349 av->latick = ambclock;
350 /*
351 * Ambient level test.
352 */
353 if (av->lvl > al) /* list sorted, so this works */
354 break;
355 if (av->weight < 0.9*r->rweight)
356 continue;
357 /*
358 * Ambient radius test.
359 */
360 d = av->pos[0] - r->rop[0];
361 e1 = d * d;
362 d = av->pos[1] - r->rop[1];
363 e1 += d * d;
364 d = av->pos[2] - r->rop[2];
365 e1 += d * d;
366 e1 /= av->rad * av->rad;
367 if (e1 > ambacc*ambacc*1.21)
368 continue;
369 /*
370 * Direction test using closest normal.
371 */
372 d = DOT(av->dir, r->ron);
373 if (rn != r->ron) {
374 rn_dot = DOT(av->dir, rn);
375 if (rn_dot > 1.0-FTINY)
376 rn_dot = 1.0-FTINY;
377 if (rn_dot >= d-FTINY) {
378 d = rn_dot;
379 rn_dot = -2.0;
380 }
381 }
382 e2 = (1.0 - d) * r->rweight;
383 if (e2 < 0.0) e2 = 0.0;
384 if (e1 + e2 > ambacc*ambacc*1.21)
385 continue;
386 /*
387 * Ray behind test.
388 */
389 d = 0.0;
390 for (j = 0; j < 3; j++)
391 d += (r->rop[j] - av->pos[j]) *
392 (av->dir[j] + r->ron[j]);
393 if (d*0.5 < -minarad*ambacc-.001)
394 continue;
395 /*
396 * Jittering final test reduces image artifacts.
397 */
398 e1 = sqrt(e1);
399 e2 = sqrt(e2);
400 wt = e1 + e2;
401 if (wt > ambacc*(.9+.2*urand(9015+samplendx)))
402 continue;
403 /*
404 * Recompute directional error using perturbed normal
405 */
406 if (rn_dot > 0.0) {
407 e2 = sqrt((1.0 - rn_dot)*r->rweight);
408 wt = e1 + e2;
409 }
410 if (wt <= 1e-3)
411 wt = 1e3;
412 else
413 wt = 1.0 / wt;
414 wsum += wt;
415 extambient(ct, av, r->rop, rn);
416 scalecolor(ct, wt);
417 addcolor(acol, ct);
418 }
419 if (at->kid == NULL)
420 return(wsum);
421 /* do children */
422 s *= 0.5;
423 for (i = 0; i < 8; i++) {
424 for (j = 0; j < 3; j++) {
425 ck0[j] = c0[j];
426 if (1<<j & i)
427 ck0[j] += s;
428 if (r->rop[j] < ck0[j] - OCTSCALE*s)
429 break;
430 if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
431 break;
432 }
433 if (j == 3)
434 wsum += sumambient(acol, r, rn, al,
435 at->kid+i, ck0, s);
436 }
437 return(wsum);
438 }
439
440
441 extern double
442 makeambient( /* make a new ambient value for storage */
443 COLOR acol,
444 RAY *r,
445 FVECT rn,
446 int al
447 )
448 {
449 AMBVAL amb;
450 FVECT gp, gd;
451 int i;
452
453 amb.weight = 1.0; /* compute weight */
454 for (i = al; i-- > 0; )
455 amb.weight *= AVGREFL;
456 if (r->rweight < 0.1*amb.weight) /* heuristic override */
457 amb.weight = 1.25*r->rweight;
458 setcolor(acol, AVGREFL, AVGREFL, AVGREFL);
459 /* compute ambient */
460 amb.rad = doambient(acol, r, amb.weight, gp, gd);
461 if (amb.rad <= FTINY) {
462 setcolor(acol, 0.0, 0.0, 0.0);
463 return(0.0);
464 }
465 scalecolor(acol, 1./AVGREFL); /* undo assumed reflectance */
466 /* store value */
467 VCOPY(amb.pos, r->rop);
468 VCOPY(amb.dir, r->ron);
469 amb.lvl = al;
470 copycolor(amb.val, acol);
471 VCOPY(amb.gpos, gp);
472 VCOPY(amb.gdir, gd);
473 /* insert into tree */
474 avsave(&amb); /* and save to file */
475 if (rn != r->ron)
476 extambient(acol, &amb, r->rop, rn); /* texture */
477 return(amb.rad);
478 }
479
480
481 extern void
482 extambient( /* extrapolate value at pv, nv */
483 COLOR cr,
484 register AMBVAL *ap,
485 FVECT pv,
486 FVECT nv
487 )
488 {
489 FVECT v1;
490 register int i;
491 double d;
492
493 d = 1.0; /* zeroeth order */
494 /* gradient due to translation */
495 for (i = 0; i < 3; i++)
496 d += ap->gpos[i]*(pv[i]-ap->pos[i]);
497 /* gradient due to rotation */
498 VCROSS(v1, ap->dir, nv);
499 d += DOT(ap->gdir, v1);
500 if (d <= 0.0) {
501 setcolor(cr, 0.0, 0.0, 0.0);
502 return;
503 }
504 copycolor(cr, ap->val);
505 scalecolor(cr, d);
506 }
507
508
509 static void
510 initambfile( /* initialize ambient file */
511 int creat
512 )
513 {
514 extern char *progname, *octname;
515 static char *mybuf = NULL;
516
517 #ifdef F_SETLKW
518 aflock(creat ? F_WRLCK : F_RDLCK);
519 #endif
520 SET_FILE_BINARY(ambfp);
521 if (mybuf == NULL)
522 mybuf = (char *)bmalloc(BUFSIZ+8);
523 setbuf(ambfp, mybuf);
524 if (creat) { /* new file */
525 newheader("RADIANCE", ambfp);
526 fprintf(ambfp, "%s -av %g %g %g -aw %d -ab %d -aa %g ",
527 progname, colval(ambval,RED),
528 colval(ambval,GRN), colval(ambval,BLU),
529 ambvwt, ambounce, ambacc);
530 fprintf(ambfp, "-ad %d -as %d -ar %d ",
531 ambdiv, ambssamp, ambres);
532 if (octname != NULL)
533 printargs(1, &octname, ambfp);
534 else
535 fputc('\n', ambfp);
536 fprintf(ambfp, "SOFTWARE= %s\n", VersionID);
537 fputnow(ambfp);
538 fputformat(AMBFMT, ambfp);
539 putc('\n', ambfp);
540 putambmagic(ambfp);
541 } else if (checkheader(ambfp, AMBFMT, NULL) < 0 || !hasambmagic(ambfp))
542 error(USER, "bad ambient file");
543 }
544
545
546 static void
547 avsave( /* insert and save an ambient value */
548 AMBVAL *av
549 )
550 {
551 avinsert(avstore(av));
552 if (ambfp == NULL)
553 return;
554 if (writambval(av, ambfp) < 0)
555 goto writerr;
556 if (++nunflshed >= AMBFLUSH)
557 if (ambsync() == EOF)
558 goto writerr;
559 return;
560 writerr:
561 error(SYSTEM, "error writing to ambient file");
562 }
563
564
565 static AMBVAL *
566 avstore( /* allocate memory and store aval */
567 register AMBVAL *aval
568 )
569 {
570 register AMBVAL *av;
571 double d;
572
573 if ((av = newambval()) == NULL)
574 error(SYSTEM, "out of memory in avstore");
575 *av = *aval;
576 av->latick = ambclock;
577 av->next = NULL;
578 nambvals++;
579 d = bright(av->val);
580 if (d > FTINY) { /* add to log sum for averaging */
581 avsum += log(d);
582 navsum++;
583 }
584 return(av);
585 }
586
587
588 #define ATALLOCSZ 512 /* #/8 trees to allocate at once */
589
590 static AMBTREE *atfreelist = NULL; /* free ambient tree structures */
591
592
593 static AMBTREE *
594 newambtree(void) /* allocate 8 ambient tree structs */
595 {
596 register AMBTREE *atp, *upperlim;
597
598 if (atfreelist == NULL) { /* get more nodes */
599 atfreelist = (AMBTREE *)malloc(ATALLOCSZ*8*sizeof(AMBTREE));
600 if (atfreelist == NULL)
601 return(NULL);
602 /* link new free list */
603 upperlim = atfreelist + 8*(ATALLOCSZ-1);
604 for (atp = atfreelist; atp < upperlim; atp += 8)
605 atp->kid = atp + 8;
606 atp->kid = NULL;
607 }
608 atp = atfreelist;
609 atfreelist = atp->kid;
610 memset((char *)atp, '\0', 8*sizeof(AMBTREE));
611 return(atp);
612 }
613
614
615 static void
616 freeambtree( /* free 8 ambient tree structs */
617 AMBTREE *atp
618 )
619 {
620 atp->kid = atfreelist;
621 atfreelist = atp;
622 }
623
624
625 static void
626 avinsert( /* insert ambient value in our tree */
627 void *av
628 )
629 {
630 register AMBTREE *at;
631 register AMBVAL *ap;
632 AMBVAL avh;
633 FVECT ck0;
634 double s;
635 int branch;
636 register int i;
637
638 if (((AMBVAL*)av)->rad <= FTINY)
639 error(CONSISTENCY, "zero ambient radius in avinsert");
640 at = &atrunk;
641 VCOPY(ck0, thescene.cuorg);
642 s = thescene.cusize;
643 while (s*(OCTSCALE/2) > ((AMBVAL*)av)->rad*ambacc) {
644 if (at->kid == NULL)
645 if ((at->kid = newambtree()) == NULL)
646 error(SYSTEM, "out of memory in avinsert");
647 s *= 0.5;
648 branch = 0;
649 for (i = 0; i < 3; i++)
650 if (((AMBVAL*)av)->pos[i] > ck0[i] + s) {
651 ck0[i] += s;
652 branch |= 1 << i;
653 }
654 at = at->kid + branch;
655 }
656 avh.next = at->alist; /* order by increasing level */
657 for (ap = &avh; ap->next != NULL; ap = ap->next)
658 if (ap->next->lvl >= ((AMBVAL*)av)->lvl)
659 break;
660 ((AMBVAL*)av)->next = ap->next;
661 ap->next = (AMBVAL*)av;
662 at->alist = avh.next;
663 }
664
665
666 static void
667 unloadatree( /* unload an ambient value tree */
668 register AMBTREE *at,
669 unloadtf_t *f
670 )
671 {
672 register AMBVAL *av;
673 register int i;
674 /* transfer values at this node */
675 for (av = at->alist; av != NULL; av = at->alist) {
676 at->alist = av->next;
677 (*f)(av);
678 }
679 if (at->kid == NULL)
680 return;
681 for (i = 0; i < 8; i++) /* transfer and free children */
682 unloadatree(at->kid+i, f);
683 freeambtree(at->kid);
684 at->kid = NULL;
685 }
686
687
688 static struct avl {
689 AMBVAL *p;
690 unsigned long t;
691 } *avlist1; /* ambient value list with ticks */
692 static AMBVAL **avlist2; /* memory positions for sorting */
693 static int i_avlist; /* index for lists */
694
695 static int alatcmp(const void *av1, const void *av2);
696
697 static void
698 av2list(
699 void *av
700 )
701 {
702 #ifdef DEBUG
703 if (i_avlist >= nambvals)
704 error(CONSISTENCY, "too many ambient values in av2list1");
705 #endif
706 avlist1[i_avlist].p = avlist2[i_avlist] = (AMBVAL*)av;
707 avlist1[i_avlist++].t = ((AMBVAL*)av)->latick;
708 }
709
710
711 static int
712 alatcmp( /* compare ambient values for MRA */
713 const void *av1,
714 const void *av2
715 )
716 {
717 register long lc = ((struct avl *)av2)->t - ((struct avl *)av1)->t;
718 return(lc<0 ? -1 : lc>0 ? 1 : 0);
719 }
720
721
722 /* GW NOTE 2002/10/3:
723 * I used to compare AMBVAL pointers, but found that this was the
724 * cause of a serious consistency error with gcc, since the optimizer
725 * uses some dangerous trick in pointer subtraction that
726 * assumes pointers differ by exact struct size increments.
727 */
728 static int
729 aposcmp( /* compare ambient value positions */
730 const void *avp1,
731 const void *avp2
732 )
733 {
734 register long diff = *(char * const *)avp1 - *(char * const *)avp2;
735 if (diff < 0)
736 return(-1);
737 return(diff > 0);
738 }
739
740 #if 1
741 static int
742 avlmemi( /* find list position from address */
743 AMBVAL *avaddr
744 )
745 {
746 register AMBVAL **avlpp;
747
748 avlpp = (AMBVAL **)bsearch((char *)&avaddr, (char *)avlist2,
749 nambvals, sizeof(AMBVAL *), aposcmp);
750 if (avlpp == NULL)
751 error(CONSISTENCY, "address not found in avlmemi");
752 return(avlpp - avlist2);
753 }
754 #else
755 #define avlmemi(avaddr) ((AMBVAL **)bsearch((char *)&avaddr,(char *)avlist2, \
756 nambvals,sizeof(AMBVAL *),aposcmp) - avlist2)
757 #endif
758
759
760 static void
761 sortambvals( /* resort ambient values */
762 int always
763 )
764 {
765 AMBTREE oldatrunk;
766 AMBVAL tav, *tap, *pnext;
767 register int i, j;
768 /* see if it's time yet */
769 if (!always && (ambclock++ < lastsort+sortintvl ||
770 nambvals < SORT_THRESH))
771 return;
772 /*
773 * The idea here is to minimize memory thrashing
774 * in VM systems by improving reference locality.
775 * We do this by periodically sorting our stored ambient
776 * values in memory in order of most recently to least
777 * recently accessed. This ordering was chosen so that new
778 * ambient values (which tend to be less important) go into
779 * higher memory with the infrequently accessed values.
780 * Since we expect our values to need sorting less
781 * frequently as the process continues, we double our
782 * waiting interval after each call.
783 * This routine is also called by setambacc() with
784 * the "always" parameter set to 1 so that the ambient
785 * tree will be rebuilt with the new accuracy parameter.
786 */
787 if (tracktime) { /* allocate pointer arrays to sort */
788 avlist2 = (AMBVAL **)malloc(nambvals*sizeof(AMBVAL *));
789 avlist1 = (struct avl *)malloc(nambvals*sizeof(struct avl));
790 } else {
791 avlist2 = NULL;
792 avlist1 = NULL;
793 }
794 if (avlist1 == NULL) { /* no time tracking -- rebuild tree? */
795 if (avlist2 != NULL)
796 free((void *)avlist2);
797 if (always) { /* rebuild without sorting */
798 oldatrunk = atrunk;
799 atrunk.alist = NULL;
800 atrunk.kid = NULL;
801 unloadatree(&oldatrunk, avinsert);
802 }
803 } else { /* sort memory by last access time */
804 /*
805 * Sorting memory is tricky because it isn't contiguous.
806 * We have to sort an array of pointers by MRA and also
807 * by memory position. We then copy values in "loops"
808 * to minimize memory hits. Nevertheless, we will visit
809 * everyone at least twice, and this is an expensive process
810 * when we're thrashing, which is when we need to do it.
811 */
812 #ifdef DEBUG
813 sprintf(errmsg, "sorting %u ambient values at ambclock=%lu...",
814 nambvals, ambclock);
815 eputs(errmsg);
816 #endif
817 i_avlist = 0;
818 unloadatree(&atrunk, av2list); /* empty current tree */
819 #ifdef DEBUG
820 if (i_avlist < nambvals)
821 error(CONSISTENCY, "missing ambient values in sortambvals");
822 #endif
823 qsort((char *)avlist1, nambvals, sizeof(struct avl), alatcmp);
824 qsort((char *)avlist2, nambvals, sizeof(AMBVAL *), aposcmp);
825 for (i = 0; i < nambvals; i++) {
826 if (avlist1[i].p == NULL)
827 continue;
828 tap = avlist2[i];
829 tav = *tap;
830 for (j = i; (pnext = avlist1[j].p) != tap;
831 j = avlmemi(pnext)) {
832 *(avlist2[j]) = *pnext;
833 avinsert(avlist2[j]);
834 avlist1[j].p = NULL;
835 }
836 *(avlist2[j]) = tav;
837 avinsert(avlist2[j]);
838 avlist1[j].p = NULL;
839 }
840 free((void *)avlist1);
841 free((void *)avlist2);
842 /* compute new sort interval */
843 sortintvl = ambclock - lastsort;
844 if (sortintvl >= MAX_SORT_INTVL/2)
845 sortintvl = MAX_SORT_INTVL;
846 else
847 sortintvl <<= 1; /* wait twice as long next */
848 #ifdef DEBUG
849 eputs("done\n");
850 #endif
851 }
852 if (ambclock >= MAXACLOCK)
853 ambclock = MAXACLOCK/2;
854 lastsort = ambclock;
855 }
856
857
858 #ifdef F_SETLKW
859
860 static void
861 aflock( /* lock/unlock ambient file */
862 int typ
863 )
864 {
865 static struct flock fls; /* static so initialized to zeroes */
866
867 fls.l_type = typ;
868 if (fcntl(fileno(ambfp), F_SETLKW, &fls) < 0)
869 error(SYSTEM, "cannot (un)lock ambient file");
870 }
871
872
873 extern int
874 ambsync(void) /* synchronize ambient file */
875 {
876 long flen;
877 AMBVAL avs;
878 register int n;
879
880 if (nunflshed == 0)
881 return(0);
882 if (lastpos < 0) /* initializing (locked in initambfile) */
883 goto syncend;
884 /* gain exclusive access */
885 aflock(F_WRLCK);
886 /* see if file has grown */
887 if ((flen = lseek(fileno(ambfp), (off_t)0, SEEK_END)) < 0)
888 goto seekerr;
889 if ( (n = flen - lastpos) ) { /* file has grown */
890 if (ambinp == NULL) { /* use duplicate filedes */
891 ambinp = fdopen(dup(fileno(ambfp)), "r");
892 if (ambinp == NULL)
893 error(SYSTEM, "fdopen failed in ambsync");
894 }
895 if (fseek(ambinp, lastpos, 0) < 0)
896 goto seekerr;
897 while (n >= AMBVALSIZ) { /* load contributed values */
898 if (!readambval(&avs, ambinp)) {
899 sprintf(errmsg,
900 "ambient file \"%s\" corrupted near character %ld",
901 ambfile, flen - n);
902 error(WARNING, errmsg);
903 break;
904 }
905 avinsert(avstore(&avs));
906 n -= AMBVALSIZ;
907 }
908 /*** seek always as safety measure
909 if (n) ***/ /* alignment */
910 if (lseek(fileno(ambfp), (off_t)(flen-n), SEEK_SET) < 0)
911 goto seekerr;
912 }
913 #ifdef DEBUG
914 if (ambfp->_ptr - ambfp->_base != nunflshed*AMBVALSIZ) {
915 sprintf(errmsg, "ambient file buffer at %d rather than %d",
916 ambfp->_ptr - ambfp->_base,
917 nunflshed*AMBVALSIZ);
918 error(CONSISTENCY, errmsg);
919 }
920 #endif
921 syncend:
922 n = fflush(ambfp); /* calls write() at last */
923 if ((lastpos = lseek(fileno(ambfp), (off_t)0, SEEK_CUR)) < 0)
924 goto seekerr;
925 aflock(F_UNLCK); /* release file */
926 nunflshed = 0;
927 return(n);
928 seekerr:
929 error(SYSTEM, "seek failed in ambsync");
930 return -1; /* pro forma return */
931 }
932
933 #else
934
935 extern int
936 ambsync(void) /* flush ambient file */
937 {
938 if (nunflshed == 0)
939 return(0);
940 nunflshed = 0;
941 return(fflush(ambfp));
942 }
943
944 #endif