cache.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 #include        "u.h"
    2 #include        "../port/lib.h"
    3 #include        "mem.h"
    4 #include        "dat.h"
    5 #include        "fns.h"
    6 #include        "../port/error.h"
    7 
    8 enum
    9 {
   10         NHASH           = 128,
   11         MAXCACHE        = 1024*1024,
   12         NFILE           = 4096,
   13         NEXTENT         = 200,          /* extent allocation size */
   14 };
   15 
   16 typedef struct Extent Extent;
   17 struct Extent
   18 {
   19         int     bid;
   20         ulong   start;
   21         int     len;
   22         Page    *cache;
   23         Extent  *next;
   24 };
   25 
   26 typedef struct Mntcache Mntcache;
   27 struct Mntcache
   28 {
   29         Qid     qid;
   30         int     dev;
   31         int     type;
   32         QLock;
   33         Extent   *list;
   34         Mntcache *hash;
   35         Mntcache *prev;
   36         Mntcache *next;
   37 };
   38 
   39 typedef struct Cache Cache;
   40 struct Cache
   41 {
   42         Lock;
   43         int             pgno;
   44         Mntcache        *head;
   45         Mntcache        *tail;
   46         Mntcache        *hash[NHASH];
   47 };
   48 
   49 typedef struct Ecache Ecache;
   50 struct Ecache
   51 {
   52         Lock;
   53         int     total;
   54         int     free;
   55         Extent* head;
   56 };
   57 
   58 static Image fscache;
   59 static Cache cache;
   60 static Ecache ecache;
   61 static int maxcache = MAXCACHE;
   62 
   63 static void
   64 extentfree(Extent* e)
   65 {
   66         lock(&ecache);
   67         e->next = ecache.head;
   68         ecache.head = e;
   69         ecache.free++;
   70         unlock(&ecache);
   71 }
   72 
   73 static Extent*
   74 extentalloc(void)
   75 {
   76         Extent *e;
   77         int i;
   78 
   79         lock(&ecache);
   80         if(ecache.head == nil){
   81                 e = xalloc(NEXTENT*sizeof(Extent));
   82                 if(e == nil){
   83                         unlock(&ecache);
   84                         return nil;
   85                 }
   86                 for(i = 0; i < NEXTENT; i++){
   87                         e->next = ecache.head;
   88                         ecache.head = e;
   89                         e++;
   90                 }
   91                 ecache.free += NEXTENT;
   92                 ecache.total += NEXTENT;
   93         }
   94 
   95         e = ecache.head;
   96         ecache.head = e->next;
   97         memset(e, 0, sizeof(Extent));
   98         ecache.free--;
   99         unlock(&ecache);
  100 
  101         return e;
  102 }
  103 
  104 void
  105 cinit(void)
  106 {
  107         int i;
  108         Mntcache *m;
  109 
  110         cache.head = xalloc(sizeof(Mntcache)*NFILE);
  111         m = cache.head;
  112         if (m == nil)
  113                 panic("cinit: no memory");
  114 
  115         /* a better algorithm would be nice */
  116 //      if(conf.npage*BY2PG > 200*MB)
  117 //              maxcache = 10*MAXCACHE;
  118 //      if(conf.npage*BY2PG > 400*MB)
  119 //              maxcache = 50*MAXCACHE;
  120 
  121         for(i = 0; i < NFILE-1; i++) {
  122                 m->next = m+1;
  123                 m->prev = m-1;
  124                 m++;
  125         }
  126 
  127         cache.tail = m;
  128         cache.tail->next = 0;
  129         cache.head->prev = 0;
  130 
  131         fscache.notext = 1;
  132 }
  133 
  134 void
  135 cprint(Chan *c, Mntcache *m, char *s)
  136 {
  137         ulong o;
  138         int nb, ct;
  139         Extent *e;
  140 
  141         nb = 0;
  142         ct = 1;
  143         o = 0;
  144         if(m->list)
  145                 o = m->list->start;
  146         for(e = m->list; e; e = e->next) {
  147                 nb += e->len;
  148                 if(o != e->start)
  149                         ct = 0;
  150                 o = e->start+e->len;
  151         }
  152         pprint("%s: %#lux.%#lux %d %d %s (%d %c)\n",
  153         s, m->qid.path, m->qid.vers, m->type, m->dev, c->path, nb, ct ? 'C' : 'N');
  154 
  155         for(e = m->list; e; e = e->next) {
  156                 pprint("\t%4d %5d %4d %lux\n",
  157                         e->bid, e->start, e->len, e->cache);
  158         }
  159 }
  160 
  161 Page*
  162 cpage(Extent *e)
  163 {
  164         /* Easy consistency check */
  165         if(e->cache->daddr != e->bid)
  166                 return 0;
  167 
  168         return lookpage(&fscache, e->bid);
  169 }
  170 
  171 void
  172 cnodata(Mntcache *m)
  173 {
  174         Extent *e, *n;
  175 
  176         /*
  177          * Invalidate all extent data
  178          * Image lru will waste the pages
  179          */
  180         for(e = m->list; e; e = n) {
  181                 n = e->next;
  182                 extentfree(e);
  183         }
  184         m->list = 0;
  185 }
  186 
  187 void
  188 ctail(Mntcache *m)
  189 {
  190         /* Unlink and send to the tail */
  191         if(m->prev)
  192                 m->prev->next = m->next;
  193         else
  194                 cache.head = m->next;
  195         if(m->next)
  196                 m->next->prev = m->prev;
  197         else
  198                 cache.tail = m->prev;
  199 
  200         if(cache.tail) {
  201                 m->prev = cache.tail;
  202                 cache.tail->next = m;
  203                 m->next = 0;
  204                 cache.tail = m;
  205         }
  206         else {
  207                 cache.head = m;
  208                 cache.tail = m;
  209                 m->prev = 0;
  210                 m->next = 0;
  211         }
  212 }
  213 
  214 void
  215 copen(Chan *c)
  216 {
  217         int h;
  218         Extent *e, *next;
  219         Mntcache *m, *f, **l;
  220 
  221         /* directories aren't cacheable and append-only files confuse us */
  222         if(c->qid.type&(QTDIR|QTAPPEND))
  223                 return;
  224 
  225         h = c->qid.path%NHASH;
  226         lock(&cache);
  227         for(m = cache.hash[h]; m; m = m->hash) {
  228                 if(m->qid.path == c->qid.path)
  229                 if(m->qid.type == c->qid.type)
  230                 if(m->dev == c->dev && m->type == c->type) {
  231                         c->mcp = m;
  232                         ctail(m);
  233                         unlock(&cache);
  234 
  235                         /* File was updated, invalidate cache */
  236                         if(m->qid.vers != c->qid.vers) {
  237                                 m->qid.vers = c->qid.vers;
  238                                 qlock(m);
  239                                 cnodata(m);
  240                                 qunlock(m);
  241                         }
  242                         return;
  243                 }
  244         }
  245 
  246         /* LRU the cache headers */
  247         m = cache.head;
  248         l = &cache.hash[m->qid.path%NHASH];
  249         for(f = *l; f; f = f->hash) {
  250                 if(f == m) {
  251                         *l = m->hash;
  252                         break;
  253                 }
  254                 l = &f->hash;
  255         }
  256 
  257         m->qid = c->qid;
  258         m->dev = c->dev;
  259         m->type = c->type;
  260 
  261         l = &cache.hash[h];
  262         m->hash = *l;
  263         *l = m;
  264         ctail(m);
  265 
  266         qlock(m);
  267         c->mcp = m;
  268         e = m->list;
  269         m->list = 0;
  270         unlock(&cache);
  271 
  272         while(e) {
  273                 next = e->next;
  274                 extentfree(e);
  275                 e = next;
  276         }
  277         qunlock(m);
  278 }
  279 
  280 static int
  281 cdev(Mntcache *m, Chan *c)
  282 {
  283         if(m->qid.path != c->qid.path)
  284                 return 0;
  285         if(m->qid.type != c->qid.type)
  286                 return 0;
  287         if(m->dev != c->dev)
  288                 return 0;
  289         if(m->type != c->type)
  290                 return 0;
  291         if(m->qid.vers != c->qid.vers)
  292                 return 0;
  293         return 1;
  294 }
  295 
  296 int
  297 cread(Chan *c, uchar *buf, int len, vlong off)
  298 {
  299         KMap *k;
  300         Page *p;
  301         Mntcache *m;
  302         Extent *e, **t;
  303         int o, l, total;
  304         ulong offset;
  305 
  306         if(off+len > maxcache)
  307                 return 0;
  308 
  309         m = c->mcp;
  310         if(m == 0)
  311                 return 0;
  312 
  313         qlock(m);
  314         if(cdev(m, c) == 0) {
  315                 qunlock(m);
  316                 return 0;
  317         }
  318 
  319         offset = off;
  320         t = &m->list;
  321         for(e = *t; e; e = e->next) {
  322                 if(offset >= e->start && offset < e->start+e->len)
  323                         break;
  324                 t = &e->next;
  325         }
  326 
  327         if(e == 0) {
  328                 qunlock(m);
  329                 return 0;
  330         }
  331 
  332         total = 0;
  333         while(len) {
  334                 p = cpage(e);
  335                 if(p == 0) {
  336                         *t = e->next;
  337                         extentfree(e);
  338                         qunlock(m);
  339                         return total;
  340                 }
  341 
  342                 o = offset - e->start;
  343                 l = len;
  344                 if(l > e->len-o)
  345                         l = e->len-o;
  346 
  347                 k = kmap(p);
  348                 if(waserror()) {
  349                         kunmap(k);
  350                         putpage(p);
  351                         qunlock(m);
  352                         nexterror();
  353                 }
  354 
  355                 memmove(buf, (uchar*)VA(k) + o, l);
  356 
  357                 poperror();
  358                 kunmap(k);
  359 
  360                 putpage(p);
  361 
  362                 buf += l;
  363                 len -= l;
  364                 offset += l;
  365                 total += l;
  366                 t = &e->next;
  367                 e = e->next;
  368                 if(e == 0 || e->start != offset)
  369                         break;
  370         }
  371 
  372         qunlock(m);
  373         return total;
  374 }
  375 
  376 Extent*
  377 cchain(uchar *buf, ulong offset, int len, Extent **tail)
  378 {
  379         int l;
  380         Page *p;
  381         KMap *k;
  382         Extent *e, *start, **t;
  383 
  384         start = 0;
  385         *tail = 0;
  386         t = &start;
  387         while(len) {
  388                 e = extentalloc();
  389                 if(e == 0)
  390                         break;
  391 
  392                 p = auxpage();
  393                 if(p == 0) {
  394                         extentfree(e);
  395                         break;
  396                 }
  397                 l = len;
  398                 if(l > BY2PG)
  399                         l = BY2PG;
  400 
  401                 e->cache = p;
  402                 e->start = offset;
  403                 e->len = l;
  404 
  405                 lock(&cache);
  406                 e->bid = cache.pgno;
  407                 cache.pgno += BY2PG;
  408                 /* wrap the counter; low bits are unused by pghash but checked by lookpage */
  409                 if((cache.pgno & ~(BY2PG-1)) == 0){
  410                         if(cache.pgno == BY2PG-1){
  411                                 print("cache wrapped\n");
  412                                 cache.pgno = 0;
  413                         }else
  414                                 cache.pgno++;
  415                 }
  416                 unlock(&cache);
  417 
  418                 p->daddr = e->bid;
  419                 k = kmap(p);
  420                 if(waserror()) {                /* buf may be virtual */
  421                         kunmap(k);
  422                         nexterror();
  423                 }
  424                 memmove((void*)VA(k), buf, l);
  425                 poperror();
  426                 kunmap(k);
  427 
  428                 cachepage(p, &fscache);
  429                 putpage(p);
  430 
  431                 buf += l;
  432                 offset += l;
  433                 len -= l;
  434 
  435                 *t = e;
  436                 *tail = e;
  437                 t = &e->next;
  438         }
  439 
  440         return start;
  441 }
  442 
  443 int
  444 cpgmove(Extent *e, uchar *buf, int boff, int len)
  445 {
  446         Page *p;
  447         KMap *k;
  448 
  449         p = cpage(e);
  450         if(p == 0)
  451                 return 0;
  452 
  453         k = kmap(p);
  454         if(waserror()) {                /* Since buf may be virtual */
  455                 kunmap(k);
  456                 nexterror();
  457         }
  458 
  459         memmove((uchar*)VA(k)+boff, buf, len);
  460 
  461         poperror();
  462         kunmap(k);
  463         putpage(p);
  464 
  465         return 1;
  466 }
  467 
  468 void
  469 cupdate(Chan *c, uchar *buf, int len, vlong off)
  470 {
  471         Mntcache *m;
  472         Extent *tail;
  473         Extent *e, *f, *p;
  474         int o, ee, eblock;
  475         ulong offset;
  476 
  477         if(off > maxcache || len == 0)
  478                 return;
  479 
  480         m = c->mcp;
  481         if(m == 0)
  482                 return;
  483         qlock(m);
  484         if(cdev(m, c) == 0) {
  485                 qunlock(m);
  486                 return;
  487         }
  488 
  489         /*
  490          * Find the insertion point
  491          */
  492         offset = off;
  493         p = 0;
  494         for(f = m->list; f; f = f->next) {
  495                 if(f->start > offset)
  496                         break;
  497                 p = f;
  498         }
  499 
  500         /* trim if there is a successor */
  501         eblock = offset+len;
  502         if(f != 0 && eblock > f->start) {
  503                 len -= (eblock - f->start);
  504                 if(len <= 0) {
  505                         qunlock(m);
  506                         return;
  507                 }
  508         }
  509 
  510         if(p == 0) {            /* at the head */
  511                 e = cchain(buf, offset, len, &tail);
  512                 if(e != 0) {
  513                         m->list = e;
  514                         tail->next = f;
  515                 }
  516                 qunlock(m);
  517                 return;
  518         }
  519 
  520         /* trim to the predecessor */
  521         ee = p->start+p->len;
  522         if(offset < ee) {
  523                 o = ee - offset;
  524                 len -= o;
  525                 if(len <= 0) {
  526                         qunlock(m);
  527                         return;
  528                 }
  529                 buf += o;
  530                 offset += o;
  531         }
  532 
  533         /* try and pack data into the predecessor */
  534         if(offset == ee && p->len < BY2PG) {
  535                 o = len;
  536                 if(o > BY2PG - p->len)
  537                         o = BY2PG - p->len;
  538                 if(cpgmove(p, buf, p->len, o)) {
  539                         p->len += o;
  540                         buf += o;
  541                         len -= o;
  542                         offset += o;
  543                         if(len <= 0) {
  544 if(f && p->start + p->len > f->start) print("CACHE: p->start=%uld p->len=%d f->start=%uld\n", p->start, p->len, f->start);
  545                                 qunlock(m);
  546                                 return;
  547                         }
  548                 }
  549         }
  550 
  551         e = cchain(buf, offset, len, &tail);
  552         if(e != 0) {
  553                 p->next = e;
  554                 tail->next = f;
  555         }
  556         qunlock(m);
  557 }
  558 
  559 void
  560 cwrite(Chan* c, uchar *buf, int len, vlong off)
  561 {
  562         int o, eo;
  563         Mntcache *m;
  564         ulong eblock, ee;
  565         Extent *p, *f, *e, *tail;
  566         ulong offset;
  567 
  568         if(off > maxcache || len == 0)
  569                 return;
  570 
  571         m = c->mcp;
  572         if(m == 0)
  573                 return;
  574 
  575         qlock(m);
  576         if(cdev(m, c) == 0) {
  577                 qunlock(m);
  578                 return;
  579         }
  580 
  581         offset = off;
  582         m->qid.vers++;
  583         c->qid.vers++;
  584 
  585         p = 0;
  586         for(f = m->list; f; f = f->next) {
  587                 if(f->start >= offset)
  588                         break;
  589                 p = f;
  590         }
  591 
  592         if(p != 0) {
  593                 ee = p->start+p->len;
  594                 eo = offset - p->start;
  595                 /* pack in predecessor if there is space */
  596                 if(offset <= ee && eo < BY2PG) {
  597                         o = len;
  598                         if(o > BY2PG - eo)
  599                                 o = BY2PG - eo;
  600                         if(cpgmove(p, buf, eo, o)) {
  601                                 if(eo+o > p->len)
  602                                         p->len = eo+o;
  603                                 buf += o;
  604                                 len -= o;
  605                                 offset += o;
  606                         }
  607                 }
  608         }
  609 
  610         /* free the overlap -- it's a rare case */
  611         eblock = offset+len;
  612         while(f && f->start < eblock) {
  613                 e = f->next;
  614                 extentfree(f);
  615                 f = e;
  616         }
  617 
  618         /* link the block (if any) into the middle */
  619         e = cchain(buf, offset, len, &tail);
  620         if(e != 0) {
  621                 tail->next = f;
  622                 f = e;
  623         }
  624 
  625         if(p == 0)
  626                 m->list = f;
  627         else
  628                 p->next = f;
  629         qunlock(m);
  630 }
Cache object: da61b6bf6e1d23486e0eff2851e20651
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/port/cache.c

FreeBSD/Linux Kernel Cross Reference
sys/port/cache.c
