Back to index

radiance  4R0+20100331
holofile.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: holofile.c,v 3.58 2008/12/04 23:34:00 greg Exp $";
00003 #endif
00004 /*
00005  * Routines for managing holodeck files
00006  *
00007  *     9/30/97       GWLarson
00008  */
00009 
00010 #include "copyright.h"
00011 
00012 #include <string.h>
00013 
00014 #include "platform.h"
00015 #include "rtprocess.h"
00016 
00017 #include "holo.h"
00018 
00019 #ifndef CACHESIZE
00020 #ifdef SMLMEM
00021 #define CACHESIZE    10
00022 #else
00023 #define CACHESIZE    100    /* default cache size (Mbytes, 0==inf) */
00024 #endif
00025 #endif
00026 #ifndef FREEBEAMS
00027 #define FREEBEAMS    1500   /* maximum beams to free at a time */
00028 #endif
00029 #ifndef PCTFREE
00030 #define PCTFREE             15     /* maximum fraction to free (%) */
00031 #endif
00032 #ifndef MAXFRAGB
00033 #define MAXFRAGB     64     /* fragment blocks/file to track (0==inf) */
00034 #endif
00035 #ifndef FF_DEFAULT
00036                             /* when to free a beam fragment */
00037 #define FF_DEFAULT   (FF_WRITE|FF_KILL)
00038 #endif
00039 #ifndef MINDIRSEL
00040                             /* minimum directory seek length */
00041 #define MINDIRSEL    (4*BUFSIZ/sizeof(BEAMI))
00042 #endif
00043 
00044 #ifndef BSD
00045 #define write writebuf      /* safe i/o routines */
00046 #define read  readbuf
00047 #endif
00048 
00049 #define FRAGBLK             512    /* number of fragments to allocate at a time */
00050 
00051 int    hdfragflags = FF_DEFAULT;   /* tells when to free fragments */
00052 unsigned      hdcachesize = CACHESIZE*1024*1024; /* target cache size */
00053 unsigned long hdclock;             /* clock value */
00054 
00055 HOLO   *hdlist[HDMAX+1];    /* holodeck pointers (NULL term.) */
00056 
00057 static struct fraglist {
00058        short  nlinks;              /* number of holodeck sections using us */
00059        short  writable;     /* 0 read-only, <0 write error encountered */
00060        int    nfrags;              /* number of known fragments */
00061        BEAMI  *fi;          /* fragments, descending file position */
00062        off_t  flen;         /* last known file length */
00063 } *hdfragl;          /* fragment lists, indexed by file descriptor */
00064 
00065 static int    nhdfragls;    /* size of hdfragl array */
00066 
00067 static HOLO *hdalloc(HDGRID *hproto);
00068 static char *hdrealloc(char *ptr, unsigned siz, char *rout);
00069 static void hdattach(int fd, int wr);
00070 static void hdrelease(int fd);
00071 static void hdmarkdirty(HOLO *hp, int i);
00072 static unsigned int hdmemuse(int all);
00073 static int hdfilord(const void *hb1, const void *hb2);
00074 static off_t hdallocfrag(int fd, uint32 nrays);
00075 static int hdsyncbeam(HOLO *hp, int i);
00076 static int hdlrulist(HDBEAMI *hb, int nents, int n, HOLO *hp);
00077 static int hdfreecache(int pct, HOLO *honly);
00078 
00079 
00080 
00081 HOLO *
00082 hdalloc(             /* allocate and set holodeck section based on grid */
00083        HDGRID *hproto
00084 )
00085 {
00086        HOLO   hdhead;
00087        register HOLO *hp;
00088        int    n;
00089                             /* copy grid to temporary header */
00090        memcpy((void *)&hdhead, (void *)hproto, sizeof(HDGRID));
00091                             /* compute grid vectors and sizes */
00092        hdcompgrid(&hdhead);
00093                             /* allocate header with directory */
00094        n = sizeof(HOLO)+nbeams(&hdhead)*sizeof(BEAMI);
00095        if ((hp = (HOLO *)malloc(n)) == NULL)
00096               return(NULL);
00097                             /* copy header information */
00098        *hp = hdhead;
00099                             /* allocate and clear beam list */
00100        hp->bl = (BEAM **)malloc((nbeams(hp)+1)*sizeof(BEAM *)+sizeof(BEAM));
00101        if (hp->bl == NULL) {
00102               free((void *)hp);
00103               return(NULL);
00104        }
00105        memset((void *)hp->bl, '\0', (nbeams(hp)+1)*sizeof(BEAM *)+sizeof(BEAM));
00106        hp->bl[0] = (BEAM *)(hp->bl+nbeams(hp)+1);       /* set blglob(hp) */
00107        hp->fd = -1;
00108        hp->dirty = 0;
00109        hp->priv = NULL;
00110                             /* clear beam directory */
00111        memset((void *)hp->bi, '\0', (nbeams(hp)+1)*sizeof(BEAMI));
00112        return(hp);          /* all is well */
00113 }
00114 
00115 
00116 char *
00117 hdrealloc(    /* (re)allocate memory, retry then error */
00118        char   *ptr,
00119        unsigned      siz,
00120        char   *rout
00121 )
00122 {
00123        register char *newp;
00124                                    /* call malloc/realloc */
00125        if (ptr == NULL) newp = (char *)malloc(siz);
00126        else newp = (char *)realloc((void *)ptr, siz);
00127                                    /* check success */
00128        if (newp == NULL && rout != NULL) {
00129               hdfreecache(25, NULL);      /* free some memory */
00130               errno = 0;           /* retry */
00131               newp = hdrealloc(ptr, siz, NULL);
00132               if (newp == NULL) {  /* give up and report error */
00133                      sprintf(errmsg, "out of memory in %s", rout);
00134                      error(SYSTEM, errmsg);
00135               }
00136        }
00137        return(newp);
00138 }
00139 
00140 
00141 void
00142 hdattach(     /* start tracking file fragments for some section */
00143        register int  fd,
00144        int    wr
00145 )
00146 {
00147        if (fd >= nhdfragls) {
00148               hdfragl = (struct fraglist *)hdrealloc((char *)hdfragl,
00149                             (fd+1)*sizeof(struct fraglist), "hdattach");
00150               memset((void *)(hdfragl+nhdfragls),
00151                             '\0', (fd+1-nhdfragls)*sizeof(struct fraglist));
00152               nhdfragls = fd+1;
00153        }
00154        hdfragl[fd].nlinks++;
00155        hdfragl[fd].writable = wr;         /* set writable flag */
00156                                           /* get file length */
00157        hdfragl[fd].flen = lseek(fd, (off_t)0, SEEK_END);
00158 }
00159 
00160 
00161 /* Do we need a routine to locate file fragments given known occupants? */
00162 
00163 
00164 void
00165 hdrelease(           /* stop tracking file fragments for some section */
00166        register int  fd
00167 )
00168 {
00169        if ((fd < 0) | (fd >= nhdfragls) || !hdfragl[fd].nlinks)
00170               return;
00171        if (!--hdfragl[fd].nlinks && hdfragl[fd].nfrags) {
00172               free((void *)hdfragl[fd].fi);
00173               hdfragl[fd].fi = NULL;
00174               hdfragl[fd].nfrags = 0;
00175        }
00176 }
00177 
00178 
00179 extern HOLO *
00180 hdinit(       /* initialize a holodeck section in a file */
00181        int    fd,                  /* corresponding file descriptor */
00182        HDGRID *hproto              /* holodeck section grid */
00183 )
00184 {
00185        off_t  rtrunc;
00186        off_t  fpos;
00187        int    writable;
00188        register HOLO *hp;
00189        register int  n;
00190                                    /* prepare for system errors */
00191        errno = 0;
00192        if ((fpos = lseek(fd, (off_t)0, SEEK_CUR)) < 0)
00193               error(SYSTEM, "cannot determine holodeck file position");
00194        if (hproto == NULL) {              /* assume we're loading it */
00195               HDGRID hpr;
00196                                           /* load header */
00197               if (read(fd, (char *)&hpr, sizeof(HDGRID)) != sizeof(HDGRID))
00198                      error(SYSTEM, "cannot load holodeck header");
00199                                           /* allocate grid */
00200               if ((hp = hdalloc(&hpr)) == NULL)
00201                      goto memerr;
00202                                           /* load beam directory */
00203               n = nbeams(hp)*sizeof(BEAMI);
00204               if (read(fd, (char *)(hp->bi+1), n) != n)
00205                      error(SYSTEM, "failure loading holodeck directory");
00206                                           /* check that it's clean */
00207               for (n = nbeams(hp); n > 0; n--)
00208                      if (hp->bi[n].fo < 0) {
00209                             hp->bi[n].fo = 0;
00210                             error(WARNING, "dirty holodeck section");
00211                             break;
00212                      }
00213                                           /* check writability */
00214               if (fd < nhdfragls && hdfragl[fd].nlinks)
00215                      writable = hdfragl[fd].writable;
00216               else
00217                      writable = lseek(fd, fpos, SEEK_SET) == fpos &&
00218                             write(fd, (char *)hp, sizeof(HDGRID)) ==
00219                                                  sizeof(HDGRID);
00220        } else {                    /* else assume we're creating it */
00221               if ((hp = hdalloc(hproto)) == NULL)
00222                      goto memerr;
00223                                           /* write header and skeleton */
00224               n = nbeams(hp)*sizeof(BEAMI);
00225               if (write(fd, (char *)hproto, sizeof(HDGRID)) !=
00226                                    sizeof(HDGRID) ||
00227                             write(fd, (char *)(hp->bi+1), n) != n)
00228                      error(SYSTEM, "cannot write header to holodeck file");
00229               writable = 1;
00230        }
00231        hp->fd = fd;  
00232        hp->dirty = 0;
00233        biglob(hp)->fo = fpos + sizeof(HDGRID);
00234                                    /* start tracking fragments */
00235        hdattach(fd, writable);
00236                                    /* check rays on disk */
00237        fpos = hdfilen(fd);
00238        biglob(hp)->nrd = rtrunc = 0;
00239        for (n = hproto == NULL ? nbeams(hp) : 0; n > 0; n--)
00240               if (hp->bi[n].nrd) {
00241                      if (hp->bi[n].fo+hp->bi[n].nrd*sizeof(RAYVAL) > fpos) {
00242                             rtrunc += hp->bi[n].nrd;
00243                             hp->bi[n].nrd = 0;
00244                      } else
00245                             biglob(hp)->nrd += hp->bi[n].nrd;
00246               }
00247        if (rtrunc) {
00248               sprintf(errmsg, "truncated section, %ld rays lost (%.1f%%)",
00249                             rtrunc, 100.*rtrunc/(rtrunc+biglob(hp)->nrd));
00250               error(WARNING, errmsg);
00251        }
00252                                    /* add to holodeck list */
00253        for (n = 0; n < HDMAX; n++)
00254               if (hdlist[n] == NULL) {
00255                      hdlist[n] = hp;
00256                      break;
00257               }
00258                                    /* all done */
00259        return(hp);
00260 memerr:
00261        error(SYSTEM, "cannot allocate holodeck grid");
00262        return NULL; /* pro forma return */
00263 }
00264 
00265 
00266 void
00267 hdmarkdirty(         /* mark holodeck directory position dirty */
00268        register HOLO *hp,
00269        int    i
00270 )
00271 {
00272        static BEAMI  smudge = {0, -1};
00273        int    mindist, minpos;
00274        register int  j;
00275 
00276        if (!hp->dirty++) {                /* write smudge first time */
00277               if (lseek(hp->fd, biglob(hp)->fo+(i-1)*sizeof(BEAMI),
00278                                    SEEK_SET) < 0 ||
00279                             write(hp->fd, (char *)&smudge,
00280                                    sizeof(BEAMI)) != sizeof(BEAMI))
00281                      error(SYSTEM, "seek/write error in hdmarkdirty");
00282               hp->dirseg[0].s = i;
00283               hp->dirseg[0].n = 1;
00284               return;
00285        }
00286                                           /* insert into segment list */
00287        for (j = hp->dirty; j--; ) {
00288               if (!j || hp->dirseg[j-1].s < i) {
00289                      hp->dirseg[j].s = i;
00290                      hp->dirseg[j].n = 1;
00291                      break;
00292               }
00293               *(hp->dirseg+j) = *(hp->dirseg+(j-1));
00294        }
00295        do {                        /* check neighbors */
00296               mindist = nbeams(hp);              /* find closest */
00297               for (j = hp->dirty; --j; )
00298                      if (hp->dirseg[j].s -
00299                                    (hp->dirseg[j-1].s + hp->dirseg[j-1].n)
00300                                    < mindist) {
00301                             minpos = j;
00302                             mindist = hp->dirseg[j].s -
00303                                    (hp->dirseg[j-1].s + hp->dirseg[j-1].n);
00304                      }
00305                                           /* good enough? */
00306               if (hp->dirty <= MAXDIRSE && mindist > MINDIRSEL)
00307                      break;
00308               j = minpos - 1;                    /* coalesce neighbors */
00309               if (hp->dirseg[j].s + hp->dirseg[j].n <
00310                             hp->dirseg[minpos].s + hp->dirseg[minpos].n)
00311                      hp->dirseg[j].n = hp->dirseg[minpos].s +
00312                                    hp->dirseg[minpos].n - hp->dirseg[j].s;
00313               hp->dirty--;
00314               while (++j < hp->dirty)            /* close the gap */
00315                      *(hp->dirseg+j) = *(hp->dirseg+(j+1));
00316        } while (mindist <= MINDIRSEL);
00317 }
00318 
00319 
00320 extern int
00321 hdsync(                     /* update beams and directory on disk */
00322        register HOLO *hp,
00323        int    all
00324 )
00325 {
00326        register int  j, n;
00327 
00328        if (hp == NULL) {           /* do all holodecks */
00329               n = 0;
00330               for (j = 0; hdlist[j] != NULL; j++)
00331                      n += hdsync(hdlist[j], all);
00332               return(n);
00333        }
00334                                    /* sync the beams */
00335        for (j = (all ? nbeams(hp) : 0); j > 0; j--)
00336               if (hp->bl[j] != NULL)
00337                      hdsyncbeam(hp, j);
00338        if (!hp->dirty)                    /* directory clean? */
00339               return(0);
00340        errno = 0;                  /* write dirty segments */
00341        for (j = 0; j < hp->dirty; j++) {
00342               if (lseek(hp->fd, biglob(hp)->fo +
00343                          (hp->dirseg[j].s-1)*sizeof(BEAMI), SEEK_SET) < 0)
00344                      error(SYSTEM, "cannot seek on holodeck file");
00345               n = hp->dirseg[j].n * sizeof(BEAMI);
00346               if (write(hp->fd, (char *)(hp->bi+hp->dirseg[j].s), n) != n)
00347                      error(SYSTEM, "cannot update section directory");
00348        }
00349        hp->dirty = 0;                     /* all clean */
00350        return(1);
00351 }
00352 
00353 
00354 unsigned int
00355 hdmemuse(            /* return memory usage (in bytes) */
00356        int    all                  /* include overhead (painful) */
00357 )
00358 {
00359        long   total = 0;
00360        register int  i, j;
00361 
00362        for (j = 0; hdlist[j] != NULL; j++) {
00363               total += blglob(hdlist[j])->nrm * sizeof(RAYVAL);
00364               if (all) {
00365                      total += sizeof(HOLO) + sizeof(BEAM *) +
00366                                    nbeams(hdlist[j]) *
00367                                           (sizeof(BEAM *)+sizeof(BEAMI));
00368                      for (i = nbeams(hdlist[j]); i > 0; i--)
00369                             if (hdlist[j]->bl[i] != NULL)
00370                                    total += sizeof(BEAM);
00371               }
00372        }
00373        if (all)
00374               for (j = 0; j < nhdfragls; j++) {
00375                      total += sizeof(struct fraglist);
00376                      if (hdfragl[j].nfrags)
00377                             total += FRAGBLK*sizeof(BEAMI) *
00378                                    ((hdfragl[j].nfrags-1)/FRAGBLK + 1) ;
00379               }
00380        return(total);
00381 }
00382 
00383 
00384 extern off_t
00385 hdfilen(             /* return file length for fd */
00386        int    fd
00387 )
00388 {
00389        off_t  fpos, flen;
00390 
00391        if (fd < 0)
00392               return(-1);
00393        if (fd >= nhdfragls || !hdfragl[fd].nlinks) {
00394               if ((fpos = lseek(fd, (off_t)0, SEEK_CUR)) < 0)
00395                      return(-1);
00396               flen = lseek(fd, (off_t)0, SEEK_END);
00397               lseek(fd, fpos, SEEK_SET);
00398               return(flen);
00399        }
00400        return(hdfragl[fd].flen);
00401 }
00402 
00403 
00404 extern off_t
00405 hdfiluse(     /* compute file usage (in bytes) */
00406        int    fd                   /* open file descriptor to check */
00407 )
00408 {
00409        off_t  total = 0;
00410        register int  j;
00411 
00412        for (j = 0; hdlist[j] != NULL; j++) {
00413               if (hdlist[j]->fd != fd)
00414                      continue;
00415               total += biglob(hdlist[j])->nrd * sizeof(RAYVAL);
00416               total += nbeams(hdlist[j])*sizeof(BEAMI) + sizeof(HDGRID);
00417 #if 0
00418               for (i = nbeams(hdlist[j]); i > 0; i--)
00419                      if (hdlist[j]->bl[i] != NULL)
00420                             total += sizeof(RAYVAL) *
00421                                           (hdlist[j]->bl[i]->nrm -
00422                                           hdlist[j]->bi[i].nrd);
00423 #endif
00424        }
00425        return(total);              /* doesn't include fragments, unflushed rays */
00426 }
00427 
00428 
00429 extern RAYVAL *
00430 hdnewrays(    /* allocate space for add'l rays and return pointer */
00431        register HOLO *hp,
00432        register int  i,
00433        int    nr                   /* number of new rays desired */
00434 )
00435 {
00436        RAYVAL *p;
00437        int    n;
00438 
00439        if (nr <= 0) return(NULL);
00440        CHECK((i < 1) | (i > nbeams(hp)),
00441                      CONSISTENCY, "bad beam index given to hdnewrays");
00442        if (hp->bl[i] != NULL)
00443               hp->bl[i]->tick = hdclock;  /* preempt swap */
00444        if (hdcachesize > 0 && hdmemuse(0) >= hdcachesize)
00445               hdfreecache(PCTFREE, NULL); /* free some space */
00446        if (hp->bl[i] == NULL) {           /* allocate (and load) */
00447               n = hp->bi[i].nrd + nr;
00448               hp->bl[i] = (BEAM *)hdrealloc(NULL, hdbsiz(n), "hdnewrays");
00449               blglob(hp)->nrm += n;
00450               if ((n = hp->bl[i]->nrm = hp->bi[i].nrd)) {
00451                      errno = 0;
00452                      if (lseek(hp->fd, hp->bi[i].fo, SEEK_SET) < 0)
00453                             error(SYSTEM, "seek error on holodeck file");
00454                      n *= sizeof(RAYVAL);
00455                      if (read(hp->fd, (char *)hdbray(hp->bl[i]), n) != n)
00456                             error(SYSTEM,
00457                             "error reading beam from holodeck file");
00458               }
00459        } else {                           /* just grow in memory */
00460               hp->bl[i] = (BEAM *)hdrealloc((char *)hp->bl[i],
00461                             hdbsiz(hp->bl[i]->nrm + nr), "hdnewrays");
00462               blglob(hp)->nrm += nr;
00463        }
00464        if (hdfragflags&FF_ALLOC && hp->bi[i].nrd)
00465               hdfreefrag(hp, i);          /* relinquish old fragment */
00466        p = hdbray(hp->bl[i]) + hp->bl[i]->nrm;
00467        hp->bl[i]->nrm += nr;                     /* update in-core structure */
00468        memset((void *)p, '\0', nr*sizeof(RAYVAL));
00469        blglob(hp)->tick = hp->bl[i]->tick = hdclock++;  /* update LRU clock */
00470        return(p);                         /* point to new rays */
00471 }
00472 
00473 
00474 extern BEAM *
00475 hdgetbeam(    /* get beam (from file if necessary) */
00476        register HOLO *hp,
00477        register int  i
00478 )
00479 {
00480        register int  n;
00481 
00482        CHECK((i < 1) | (i > nbeams(hp)),
00483                      CONSISTENCY, "bad beam index given to hdgetbeam");
00484        if (hp->bl[i] == NULL) {           /* load from disk */
00485               if (!(n = hp->bi[i].nrd))
00486                      return(NULL);
00487               if (hdcachesize > 0 && hdmemuse(0) >= hdcachesize)
00488                      hdfreecache(PCTFREE, NULL); /* get free space */
00489               hp->bl[i] = (BEAM *)hdrealloc(NULL, hdbsiz(n), "hdgetbeam");
00490               blglob(hp)->nrm += hp->bl[i]->nrm = n;
00491               errno = 0;
00492               if (lseek(hp->fd, hp->bi[i].fo, SEEK_SET) < 0)
00493                      error(SYSTEM, "seek error on holodeck file");
00494               n *= sizeof(RAYVAL);
00495               if (read(hp->fd, (char *)hdbray(hp->bl[i]), n) != n)
00496                      error(SYSTEM, "error reading beam from holodeck file");
00497               if (hdfragflags&FF_READ)
00498                      hdfreefrag(hp, i);   /* relinquish old frag. */
00499        }
00500        blglob(hp)->tick = hp->bl[i]->tick = hdclock++;  /* update LRU clock */
00501        return(hp->bl[i]);
00502 }
00503 
00504 
00505 int
00506 hdfilord(     /* order beams for quick loading */
00507        register const void  *hb1,
00508        register const void  *hb2
00509 )
00510 {
00511        register off_t       c;
00512                             /* residents go first */
00513        if (((HDBEAMI*)hb2)->h->bl[((HDBEAMI*)hb2)->b] != NULL)
00514               return(((HDBEAMI*)hb1)->h->bl[((HDBEAMI*)hb1)->b] == NULL);
00515        if (((HDBEAMI*)hb1)->h->bl[((HDBEAMI*)hb1)->b] != NULL)
00516               return(-1);
00517                             /* otherwise sort by file descriptor */
00518        if (((HDBEAMI*)hb1)->h->fd != ((HDBEAMI*)hb2)->h->fd)
00519               return(((HDBEAMI*)hb1)->h->fd - ((HDBEAMI*)hb2)->h->fd);
00520                             /* then by position in file */
00521        c = ((HDBEAMI*)hb1)->h->bi[((HDBEAMI*)hb1)->b].fo
00522               - ((HDBEAMI*)hb2)->h->bi[((HDBEAMI*)hb2)->b].fo;
00523        return(c > 0 ? 1 : c < 0 ? -1 : 0);
00524 }
00525 
00526 
00527 extern void
00528 hdloadbeams(  /* load a list of beams in optimal order */
00529        register HDBEAMI     *hb,   /* list gets sorted by hdfilord() */
00530        int    n,                   /* list length */
00531        void   (*bf)(BEAM *bp, HDBEAMI *hb)       /* callback function (optional) */
00532 )
00533 {
00534        unsigned      origcachesize, memuse;
00535        int    bytesloaded, needbytes, bytes2free;
00536        register BEAM *bp;
00537        register int  i;
00538                                    /* precheck consistency */
00539        if (n <= 0) return;
00540        for (i = n; i--; )
00541               if (hb[i].h==NULL || (hb[i].b<1) | (hb[i].b>nbeams(hb[i].h)))
00542                      error(CONSISTENCY, "bad beam in hdloadbeams");
00543                                    /* sort list for optimal access */
00544        qsort((void *)hb, n, sizeof(HDBEAMI), hdfilord);
00545        bytesloaded = 0;            /* run through loaded beams */
00546        for ( ; n && (bp = hb->h->bl[hb->b]) != NULL; n--, hb++) {
00547               bp->tick = hdclock;  /* preempt swap */
00548               bytesloaded += bp->nrm;
00549               if (bf != NULL)
00550                      (*bf)(bp, hb);
00551        }
00552        bytesloaded *= sizeof(RAYVAL);
00553        if ((origcachesize = hdcachesize) > 0) {
00554               needbytes = 0;              /* figure out memory needs */
00555               for (i = n; i--; )
00556                      needbytes += hb[i].h->bi[hb[i].b].nrd;
00557               needbytes *= sizeof(RAYVAL);
00558               do {                        /* free enough memory */
00559                      memuse = hdmemuse(0);
00560                      bytes2free = needbytes - (int)(hdcachesize-memuse);
00561                      if (bytes2free > (int)(memuse - bytesloaded))
00562                             bytes2free = memuse - bytesloaded;
00563               } while (bytes2free > 0 &&
00564                             hdfreecache(100*bytes2free/memuse, NULL) < 0);
00565               hdcachesize = 0;            /* load beams w/o swap */
00566        }
00567        for (i = 0; i < n; i++)
00568               if ((bp = hdgetbeam(hb[i].h, hb[i].b)) != NULL && bf != NULL)
00569                      (*bf)(bp, hb+i);
00570        hdcachesize = origcachesize;       /* resume dynamic swapping */
00571 }
00572 
00573 
00574 extern int
00575 hdfreefrag(                 /* free a file fragment */
00576        HOLO   *hp,
00577        int    i
00578 )
00579 {
00580        register BEAMI       *bi = &hp->bi[i];
00581        register struct fraglist    *f;
00582        register int  j, k;
00583 
00584        if (bi->nrd <= 0)
00585               return(0);
00586        DCHECK(hp->fd < 0 | hp->fd >= nhdfragls || !hdfragl[hp->fd].nlinks,
00587                      CONSISTENCY, "bad file descriptor in hdfreefrag");
00588        f = &hdfragl[hp->fd];
00589        if (!f->writable)
00590               return(0);
00591        if (f->nfrags % FRAGBLK == 0) {    /* delete empty remnants */
00592               for (j = k = 0; k < f->nfrags; j++, k++) {
00593                      while (f->fi[k].nrd == 0)
00594                             if (++k >= f->nfrags)
00595                                    goto endloop;
00596                      if (k > j)
00597                             *(f->fi+j) = *(f->fi+k);
00598               }
00599        endloop:
00600               f->nfrags = j;
00601        }
00602        j = f->nfrags++;            /* allocate a slot in free list */
00603 #if MAXFRAGB
00604        if (j >= MAXFRAGB*FRAGBLK) {
00605               f->nfrags = j--;     /* stop list growth */
00606               if (bi->nrd <= f->fi[j].nrd)
00607                      return(0);    /* new one no better than discard */
00608        }
00609 #endif
00610        if (j % FRAGBLK == 0) {            /* more (or less) free list space */
00611               register BEAMI       *newp;
00612               if (f->fi == NULL)
00613                      newp = (BEAMI *)malloc((j+FRAGBLK)*sizeof(BEAMI));
00614               else
00615                      newp = (BEAMI *)realloc((void *)f->fi,
00616                                    (j+FRAGBLK)*sizeof(BEAMI));
00617               if (newp == NULL) {
00618                      f->nfrags--;  /* graceful failure */
00619                      return(0);
00620               }
00621               f->fi = newp;
00622        }
00623        for ( ; ; j--) {            /* insert in descending list */
00624               if (!j || bi->fo < f->fi[j-1].fo) {
00625                      f->fi[j].fo = bi->fo;
00626                      f->fi[j].nrd = bi->nrd;
00627                      break;
00628               }
00629               *(f->fi+j) = *(f->fi+(j-1));
00630        }
00631                                    /* coalesce adjacent fragments */
00632                                           /* successors never empty */
00633        if (j && f->fi[j-1].fo == f->fi[j].fo + f->fi[j].nrd*sizeof(RAYVAL)) {
00634               f->fi[j].nrd += f->fi[j-1].nrd;
00635               f->fi[j-1].nrd = 0;
00636        }
00637        for (k = j+1; k < f->nfrags; k++)  /* get non-empty predecessor */
00638               if (f->fi[k].nrd) {
00639                      if (f->fi[j].fo == f->fi[k].fo +
00640                                    f->fi[k].nrd*sizeof(RAYVAL)) {
00641                             f->fi[k].nrd += f->fi[j].nrd;
00642                             f->fi[j].nrd = 0;
00643                      }
00644                      break;
00645               }
00646        biglob(hp)->nrd -= bi->nrd;        /* tell fragment it's free */
00647        bi->nrd = 0;
00648        bi->fo = 0;
00649        hdmarkdirty(hp, i);                /* assume we'll reallocate */
00650        return(1);
00651 }
00652 
00653 
00654 extern int
00655 hdfragOK(     /* get fragment list status for file */
00656        int    fd,
00657        int    *listlen,
00658        register int32       *listsiz
00659 )
00660 {
00661        register struct fraglist    *f;
00662        register int  i;
00663 
00664        if ((fd < 0) | (fd >= nhdfragls) || !(f = &hdfragl[fd])->nlinks)
00665               return(0);           /* listless */
00666        if (listlen != NULL)
00667               *listlen = f->nfrags;
00668        if (listsiz != NULL)
00669               for (i = f->nfrags, *listsiz = 0; i--; )
00670                      *listsiz += f->fi[i].nrd;
00671 #if MAXFRAGB
00672        return(f->nfrags < MAXFRAGB*FRAGBLK);
00673 #else
00674        return(1);                  /* list never fills up */
00675 #endif
00676 }
00677 
00678 
00679 off_t
00680 hdallocfrag(         /* allocate a file fragment */
00681        int    fd,
00682        uint32 nrays
00683 )
00684 {
00685        register struct fraglist    *f;
00686        register int  j;
00687        off_t  nfo;
00688 
00689        if (nrays == 0)
00690               return(-1L);
00691        DCHECK(fd < 0 | fd >= nhdfragls || !hdfragl[fd].nlinks,
00692                      CONSISTENCY, "bad file descriptor in hdallocfrag");
00693        f = &hdfragl[fd];
00694        for (j = f->nfrags; j-- > 0; )     /* first fit algorithm */
00695               if (f->fi[j].nrd >= nrays)
00696                      break;
00697        if (j < 0) {                /* no fragment -- extend file */
00698               nfo = f->flen;
00699               f->flen += nrays*sizeof(RAYVAL);
00700        } else {                    /* else use fragment */
00701               nfo = f->fi[j].fo;
00702               f->fi[j].fo += nrays*sizeof(RAYVAL);
00703               f->fi[j].nrd -= nrays;
00704        }
00705        return(nfo);
00706 }
00707 
00708 
00709 int
00710 hdsyncbeam(          /* sync beam in memory with beam on disk */
00711        register HOLO *hp,
00712        register int  i
00713 )
00714 {
00715        int    fragfreed;
00716        uint32 nrays;
00717        unsigned int  n;
00718        off_t  nfo;
00719                                    /* check file status */
00720        if (hdfragl[hp->fd].writable <= 0)
00721               return(hdfragl[hp->fd].writable);
00722        DCHECK(i < 1 | i > nbeams(hp),
00723                      CONSISTENCY, "bad beam index in hdsyncbeam");
00724                                    /* is current fragment OK? */
00725        if (hp->bl[i] == NULL || (nrays = hp->bl[i]->nrm) == hp->bi[i].nrd)
00726               return(0);
00727                                    /* relinquish old fragment? */
00728        fragfreed = hdfragflags&FF_WRITE && hp->bi[i].nrd && hdfreefrag(hp,i);
00729        if (nrays) {                /* get and write new fragment */
00730               nfo = hdallocfrag(hp->fd, nrays);
00731               errno = 0;
00732               if (lseek(hp->fd, nfo, SEEK_SET) < 0)
00733                      error(SYSTEM, "cannot seek on holodeck file");
00734               n = hp->bl[i]->nrm * sizeof(RAYVAL);
00735               if (write(hp->fd, (char *)hdbray(hp->bl[i]), n) != n) {
00736                      hdfragl[hp->fd].writable = -1;
00737                      hdsync(NULL, 0);     /* sync directories */
00738                      error(SYSTEM, "write error in hdsyncbeam");
00739               }
00740               hp->bi[i].fo = nfo;
00741        } else
00742               hp->bi[i].fo = 0;
00743        biglob(hp)->nrd += nrays - hp->bi[i].nrd;
00744        hp->bi[i].nrd = nrays;
00745        if (!fragfreed)
00746               hdmarkdirty(hp, i);         /* need to flag dir. ent. */
00747        return(1);
00748 }
00749 
00750 
00751 extern int
00752 hdfreebeam(          /* free beam, writing if dirty */
00753        register HOLO *hp,
00754        register int  i
00755 )
00756 {
00757        int    nchanged;
00758 
00759        if (hp == NULL) {           /* clear all holodecks */
00760               nchanged = 0;
00761               for (i = 0; hdlist[i] != NULL; i++)
00762                      nchanged += hdfreebeam(hdlist[i], 0);
00763               return(nchanged);
00764        }
00765        if (hdfragl[hp->fd].writable < 0)  /* check for file error */
00766               return(0);
00767        if (i == 0) {               /* clear entire holodeck */
00768               if (blglob(hp)->nrm == 0)
00769                      return(0);           /* already clear */
00770               nchanged = 0;
00771               for (i = nbeams(hp); i > 0; i--)
00772                      if (hp->bl[i] != NULL)
00773                             nchanged += hdfreebeam(hp, i);
00774               DCHECK(blglob(hp)->nrm != 0,
00775                             CONSISTENCY, "bad beam count in hdfreebeam");
00776               return(nchanged);
00777        }
00778        DCHECK(i < 1 | i > nbeams(hp),
00779                      CONSISTENCY, "bad beam index to hdfreebeam");
00780        if (hp->bl[i] == NULL)
00781               return(0);
00782                                    /* check for additions */
00783        nchanged = hp->bl[i]->nrm - hp->bi[i].nrd;
00784        if (nchanged)
00785               hdsyncbeam(hp, i);          /* write new fragment */
00786        blglob(hp)->nrm -= hp->bl[i]->nrm;
00787        free((void *)hp->bl[i]);           /* free memory */
00788        hp->bl[i] = NULL;
00789        return(nchanged);
00790 }
00791 
00792 
00793 extern int
00794 hdkillbeam(          /* delete beam from holodeck */
00795        register HOLO *hp,
00796        register int  i
00797 )
00798 {
00799        int    nchanged;
00800 
00801        if (hp == NULL) {           /* clobber all holodecks */
00802               nchanged = 0;
00803               for (i = 0; hdlist[i] != NULL; i++)
00804                      nchanged += hdkillbeam(hdlist[i], 0);
00805               return(nchanged);
00806        }
00807        if (i == 0) {               /* clobber entire holodeck */
00808               if ((biglob(hp)->nrd == 0) & (blglob(hp)->nrm == 0))
00809                      return(0);           /* already empty */
00810               nchanged = 0;
00811               nchanged = 0;
00812               for (i = nbeams(hp); i > 0; i--)
00813                      if (hp->bi[i].nrd > 0 || hp->bl[i] != NULL)
00814                             nchanged += hdkillbeam(hp, i);
00815               DCHECK(biglob(hp)->nrd != 0 | blglob(hp)->nrm != 0,
00816                             CONSISTENCY, "bad beam count in hdkillbeam");
00817               return(nchanged);
00818        }
00819        DCHECK(i < 1 | i > nbeams(hp), CONSISTENCY,
00820                      "bad beam index to hdkillbeam");
00821        DCHECK(!hdfragl[hp->fd].writable, CONSISTENCY,
00822                      "hdkillbeam called on read-only holodeck");
00823        if (hp->bl[i] != NULL) {    /* free memory */
00824               blglob(hp)->nrm -= nchanged = hp->bl[i]->nrm;
00825               free((void *)hp->bl[i]);
00826               hp->bl[i] = NULL;
00827        } else
00828               nchanged = hp->bi[i].nrd;
00829        if (hp->bi[i].nrd && !(hdfragflags&FF_KILL && hdfreefrag(hp,i))) {
00830               biglob(hp)->nrd -= hp->bi[i].nrd;  /* free failed */
00831               hp->bi[i].nrd = 0;
00832               hp->bi[i].fo = 0;
00833               hdmarkdirty(hp, i);
00834        }
00835        return(nchanged);
00836 }
00837 
00838 
00839 int
00840 hdlrulist(    /* add beams from holodeck to LRU list */
00841        register HDBEAMI     *hb,          /* beam list */
00842        int    nents,                      /* current list length */
00843        int    n,                          /* maximum list length */
00844        register HOLO *hp                  /* section we're adding from */
00845 )
00846 {
00847        register int  i, j;
00848                                    /* insert each beam from hp */
00849        for (i = 1; i <= nbeams(hp); i++) {
00850               if (hp->bl[i] == NULL)             /* check if loaded */
00851                      continue;
00852 #if 0
00853               if (hp->bl[i]->tick == hdclock)    /* preempt swap? */
00854                      continue;
00855 #endif
00856               if ((j = ++nents) >= n)            /* grow list if we can */
00857                      nents--;
00858               for ( ; ; ) {               /* bubble into place */
00859                      if (!--j || hp->bl[i]->tick >=
00860                                    hb[j-1].h->bl[hb[j-1].b]->tick) {
00861                             hb[j].h = hp;
00862                             hb[j].b = i;
00863                             break;
00864                      }
00865                      *(hb+j) = *(hb+(j-1));
00866               }
00867        }
00868        return(nents);                     /* return new list length */
00869 }
00870 
00871 
00872 int
00873 hdfreecache(         /* free up cache space, writing changes */
00874        int    pct,                        /* maximum percentage to free */
00875        register HOLO *honly               /* NULL means check all */
00876 )
00877 {
00878        HDBEAMI       hb[FREEBEAMS];
00879        int    freetarget;
00880        int    n;
00881        register int  i;
00882 #ifdef DEBUG
00883        unsigned      membefore;
00884 
00885        membefore = hdmemuse(0);
00886 #endif
00887                                           /* compute free target */
00888        freetarget = (honly != NULL) ? blglob(honly)->nrm :
00889                      hdmemuse(0)/sizeof(RAYVAL) ;
00890        freetarget = freetarget*pct/100;
00891        if (freetarget <= 0)
00892               return(0);
00893                                           /* find least recently used */
00894        n = 0;
00895        if (honly != NULL)
00896               n = hdlrulist(hb, n, FREEBEAMS, honly);
00897        else
00898               for (i = 0; hdlist[i] != NULL; i++)
00899                      n = hdlrulist(hb, n, FREEBEAMS, hdlist[i]);
00900                                           /* free LRU beams */
00901        for (i = 0; i < n; i++) {
00902               hdfreebeam(hb[i].h, hb[i].b);
00903               if ((freetarget -= hb[i].h->bi[hb[i].b].nrd) <= 0)
00904                      break;
00905        }
00906        hdsync(honly, 0);    /* synchronize directories as necessary */
00907 #ifdef DEBUG
00908        sprintf(errmsg,
00909        "%dK before, %dK after hdfreecache (%dK total), %d rays short\n",
00910               membefore>>10, hdmemuse(0)>>10, hdmemuse(1)>>10, freetarget);
00911        wputs(errmsg);
00912 #endif
00913        return(-freetarget); /* return how far past goal we went */
00914 }
00915 
00916 
00917 extern void
00918 hddone(              /* clean up holodeck section and free */
00919        register HOLO *hp           /* NULL means clean up all */
00920 )
00921 {
00922        register int  i;
00923 
00924        if (hp == NULL) {           /* NULL means clean up everything */
00925               while (hdlist[0] != NULL)
00926                      hddone(hdlist[0]);
00927               free((void *)hdfragl);
00928               hdfragl = NULL; nhdfragls = 0;
00929               return;
00930        }
00931                                    /* flush all data and free memory */
00932        hdflush(hp);
00933                                    /* release fragment resources */
00934        hdrelease(hp->fd);
00935                                    /* remove hp from active list */
00936        for (i = 0; hdlist[i] != NULL; i++)
00937               if (hdlist[i] == hp) {
00938                      while ((hdlist[i] = hdlist[i+1]) != NULL)
00939                             i++;
00940                      break;
00941               }
00942        free((void *)hp->bl);              /* free beam list */
00943        free((void *)hp);           /* free holodeck struct */
00944 }