sys/src/9/port/cache.c

   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
 119         for(i = 0; i < NFILE-1; i++) {
 120                 m->next = m+1;
 121                 m->prev = m-1;
 122                 m++;
 123         }
 124
 125         cache.tail = m;
 126         cache.tail->next = 0;
 127         cache.head->prev = 0;
 128
 129         fscache.notext = 1;
 130 }
 131
 132 void
 133 cprint(Chan *c, Mntcache *m, char *s)
 134 {
 135         ulong o;
 136         int nb, ct;
 137         Extent *e;
 138
 139         nb = 0;
 140         ct = 1;
 141         o = 0;
 142         if(m->list)
 143                 o = m->list->start;
 144         for(e = m->list; e; e = e->next) {
 145                 nb += e->len;
 146                 if(o != e->start)
 147                         ct = 0;
 148                 o = e->start+e->len;
 149         }
 150         pprint("%s: %#llux.%#lux %d %d %s (%d %c)\n",
 151         s, m->qid.path, m->qid.vers, m->type, m->dev, c->path->s, nb, ct ? 'C' : 'N');
 152
 153         for(e = m->list; e; e = e->next) {
 154                 pprint("\t%4d %5lud %4d %#p\n",
 155                         e->bid, e->start, e->len, e->cache);
 156         }
 157 }
 158
 159 Page*
 160 cpage(Extent *e)
 161 {
 162         /* Easy consistency check */
 163         if(e->cache->daddr != e->bid)
 164                 return 0;
 165
 166         return lookpage(&fscache, e->bid);
 167 }
 168
 169 void
 170 cnodata(Mntcache *m)
 171 {
 172         Extent *e;
 173
 174         /*
 175          * Invalidate all extent data
 176          * Image lru will waste the pages
 177          */
 178         while(e = m->list){
 179                 m->list = e->next;
 180                 extentfree(e);
 181         }
 182 }
 183
 184 void
 185 ctail(Mntcache *m)
 186 {
 187         /* Unlink and send to the tail */
 188         if(m->prev)
 189                 m->prev->next = m->next;
 190         else
 191                 cache.head = m->next;
 192         if(m->next)
 193                 m->next->prev = m->prev;
 194         else
 195                 cache.tail = m->prev;
 196
 197         if(cache.tail) {
 198                 m->prev = cache.tail;
 199                 cache.tail->next = m;
 200                 m->next = 0;
 201                 cache.tail = m;
 202         }
 203         else {
 204                 cache.head = m;
 205                 cache.tail = m;
 206                 m->prev = 0;
 207                 m->next = 0;
 208         }
 209 }
 210
 211 void
 212 copen(Chan *c)
 213 {
 214         int h;
 215         Mntcache *m, *f, **l;
 216
 217         /* directories aren't cacheable and append-only files confuse us */
 218         if(c->qid.type&(QTDIR|QTAPPEND))
 219                 return;
 220         h = c->qid.path%NHASH;
 221         lock(&cache);
 222         for(m = cache.hash[h]; m; m = m->hash) {
 223                 if(m->qid.path == c->qid.path)
 224                 if(m->qid.type == c->qid.type)
 225                 if(m->dev == c->dev && m->type == c->type) {
 226                         /* File was updated, invalidate cache */
 227                         if(m->qid.vers != c->qid.vers){
 228                                 if(!canqlock(m))
 229                                         goto Busy;
 230                                 m->qid.vers = c->qid.vers;
 231                                 goto Update;
 232                         }
 233                         ctail(m);
 234                         c->mcp = m;
 235                         unlock(&cache);
 236                         return;
 237                 }
 238         }
 239
 240         /* LRU the cache headers */
 241         m = cache.head;
 242         if(!canqlock(m))
 243                 goto Busy;
 244         l = &cache.hash[m->qid.path%NHASH];
 245         for(f = *l; f; f = f->hash) {
 246                 if(f == m) {
 247                         *l = m->hash;
 248                         break;
 249                 }
 250                 l = &f->hash;
 251         }
 252
 253         m->qid = c->qid;
 254         m->dev = c->dev;
 255         m->type = c->type;
 256
 257         l = &cache.hash[h];
 258         m->hash = *l;
 259         *l = m;
 260 Update:
 261         ctail(m);
 262         c->mcp = m;
 263         unlock(&cache);
 264         cnodata(m);
 265         qunlock(m);
 266         return;
 267 Busy:
 268         unlock(&cache);
 269         c->mcp = 0;
 270 }
 271
 272 static int
 273 cdev(Mntcache *m, Chan *c)
 274 {
 275         if(m->qid.path != c->qid.path)
 276                 return 0;
 277         if(m->qid.type != c->qid.type)
 278                 return 0;
 279         if(m->dev != c->dev)
 280                 return 0;
 281         if(m->type != c->type)
 282                 return 0;
 283         if(m->qid.vers != c->qid.vers)
 284                 return 0;
 285         return 1;
 286 }
 287
 288 int
 289 cread(Chan *c, uchar *buf, int len, vlong off)
 290 {
 291         KMap *k;
 292         Page *p;
 293         Mntcache *m;
 294         Extent *e, **t;
 295         int o, l, total;
 296         ulong offset;
 297
 298         if(off+len > maxcache)
 299                 return 0;
 300
 301         m = c->mcp;
 302         if(m == 0)
 303                 return 0;
 304
 305         qlock(m);
 306         if(cdev(m, c) == 0) {
 307                 qunlock(m);
 308                 c->mcp = 0;
 309                 return 0;
 310         }
 311
 312         offset = off;
 313         t = &m->list;
 314         for(e = *t; e; e = e->next) {
 315                 if(offset >= e->start && offset < e->start+e->len)
 316                         break;
 317                 t = &e->next;
 318         }
 319
 320         if(e == 0) {
 321                 qunlock(m);
 322                 return 0;
 323         }
 324
 325         total = 0;
 326         while(len) {
 327                 p = cpage(e);
 328                 if(p == 0) {
 329                         *t = e->next;
 330                         extentfree(e);
 331                         qunlock(m);
 332                         return total;
 333                 }
 334
 335                 o = offset - e->start;
 336                 l = len;
 337                 if(l > e->len-o)
 338                         l = e->len-o;
 339
 340                 k = kmap(p);
 341                 if(waserror()) {
 342                         kunmap(k);
 343                         putpage(p);
 344                         qunlock(m);
 345                         nexterror();
 346                 }
 347
 348                 memmove(buf, (uchar*)VA(k) + o, l);
 349
 350                 poperror();
 351                 kunmap(k);
 352
 353                 putpage(p);
 354
 355                 buf += l;
 356                 len -= l;
 357                 offset += l;
 358                 total += l;
 359                 t = &e->next;
 360                 e = e->next;
 361                 if(e == 0 || e->start != offset)
 362                         break;
 363         }
 364
 365         qunlock(m);
 366         return total;
 367 }
 368
 369 Extent*
 370 cchain(uchar *buf, ulong offset, int len, Extent **tail)
 371 {
 372         int l;
 373         Page *p;
 374         KMap *k;
 375         Extent *e, *start, **t;
 376
 377         start = 0;
 378         *tail = 0;
 379         t = &start;
 380         while(len) {
 381                 e = extentalloc();
 382                 if(e == 0)
 383                         break;
 384
 385                 p = auxpage();
 386                 if(p == 0) {
 387                         extentfree(e);
 388                         break;
 389                 }
 390                 l = len;
 391                 if(l > BY2PG)
 392                         l = BY2PG;
 393
 394                 e->cache = p;
 395                 e->start = offset;
 396                 e->len = l;
 397
 398                 lock(&cache);
 399                 e->bid = cache.pgno;
 400                 cache.pgno += BY2PG;
 401                 /* wrap the counter; low bits are unused by pghash but checked by lookpage */
 402                 if((cache.pgno & ~(BY2PG-1)) == 0){
 403                         if(cache.pgno == BY2PG-1){
 404                                 print("cache wrapped\n");
 405                                 cache.pgno = 0;
 406                         }else
 407                                 cache.pgno++;
 408                 }
 409                 unlock(&cache);
 410
 411                 p->daddr = e->bid;
 412                 k = kmap(p);
 413                 if(waserror()) {                /* buf may be virtual */
 414                         kunmap(k);
 415                         nexterror();
 416                 }
 417                 memmove((void*)VA(k), buf, l);
 418                 poperror();
 419                 kunmap(k);
 420
 421                 cachepage(p, &fscache);
 422                 putpage(p);
 423
 424                 buf += l;
 425                 offset += l;
 426                 len -= l;
 427
 428                 *t = e;
 429                 *tail = e;
 430                 t = &e->next;
 431         }
 432
 433         return start;
 434 }
 435
 436 int
 437 cpgmove(Extent *e, uchar *buf, int boff, int len)
 438 {
 439         Page *p;
 440         KMap *k;
 441
 442         p = cpage(e);
 443         if(p == 0)
 444                 return 0;
 445
 446         k = kmap(p);
 447         if(waserror()) {                /* Since buf may be virtual */
 448                 kunmap(k);
 449                 nexterror();
 450         }
 451
 452         memmove((uchar*)VA(k)+boff, buf, len);
 453
 454         poperror();
 455         kunmap(k);
 456         putpage(p);
 457
 458         return 1;
 459 }
 460
 461 void
 462 cupdate(Chan *c, uchar *buf, int len, vlong off)
 463 {
 464         Mntcache *m;
 465         Extent *tail;
 466         Extent *e, *f, *p;
 467         int o, ee, eblock;
 468         ulong offset;
 469
 470         if(off > maxcache || len == 0)
 471                 return;
 472
 473         m = c->mcp;
 474         if(m == 0)
 475                 return;
 476         qlock(m);
 477         if(cdev(m, c) == 0) {
 478                 qunlock(m);
 479                 c->mcp = 0;
 480                 return;
 481         }
 482
 483         /*
 484          * Find the insertion point
 485          */
 486         offset = off;
 487         p = 0;
 488         for(f = m->list; f; f = f->next) {
 489                 if(f->start > offset)
 490                         break;
 491                 p = f;
 492         }
 493
 494         /* trim if there is a successor */
 495         eblock = offset+len;
 496         if(f != 0 && eblock > f->start) {
 497                 len -= (eblock - f->start);
 498                 if(len <= 0) {
 499                         qunlock(m);
 500                         return;
 501                 }
 502         }
 503
 504         if(p == 0) {            /* at the head */
 505                 e = cchain(buf, offset, len, &tail);
 506                 if(e != 0) {
 507                         m->list = e;
 508                         tail->next = f;
 509                 }
 510                 qunlock(m);
 511                 return;
 512         }
 513
 514         /* trim to the predecessor */
 515         ee = p->start+p->len;
 516         if(offset < ee) {
 517                 o = ee - offset;
 518                 len -= o;
 519                 if(len <= 0) {
 520                         qunlock(m);
 521                         return;
 522                 }
 523                 buf += o;
 524                 offset += o;
 525         }
 526
 527         /* try and pack data into the predecessor */
 528         if(offset == ee && p->len < BY2PG) {
 529                 o = len;
 530                 if(o > BY2PG - p->len)
 531                         o = BY2PG - p->len;
 532                 if(cpgmove(p, buf, p->len, o)) {
 533                         p->len += o;
 534                         buf += o;
 535                         len -= o;
 536                         offset += o;
 537                         if(len <= 0) {
 538                                 if(f && p->start + p->len > f->start)
 539                                         print("CACHE: p->start=%uld p->len=%d f->start=%uld\n",
 540                                                 p->start, p->len, f->start);
 541                                 qunlock(m);
 542                                 return;
 543                         }
 544                 }
 545         }
 546
 547         e = cchain(buf, offset, len, &tail);
 548         if(e != 0) {
 549                 p->next = e;
 550                 tail->next = f;
 551         }
 552         qunlock(m);
 553 }
 554
 555 void
 556 cwrite(Chan* c, uchar *buf, int len, vlong off)
 557 {
 558         int o, eo;
 559         Mntcache *m;
 560         ulong eblock, ee;
 561         Extent *p, *f, *e, *tail;
 562         ulong offset;
 563
 564         if(off > maxcache || len == 0)
 565                 return;
 566
 567         m = c->mcp;
 568         if(m == 0)
 569                 return;
 570
 571         qlock(m);
 572         if(cdev(m, c) == 0) {
 573                 qunlock(m);
 574                 c->mcp = 0;
 575                 return;
 576         }
 577
 578         offset = off;
 579         m->qid.vers++;
 580         c->qid.vers++;
 581
 582         p = 0;
 583         for(f = m->list; f; f = f->next) {
 584                 if(f->start >= offset)
 585                         break;
 586                 p = f;
 587         }
 588
 589         if(p != 0) {
 590                 ee = p->start+p->len;
 591                 eo = offset - p->start;
 592                 /* pack in predecessor if there is space */
 593                 if(offset <= ee && eo < BY2PG) {
 594                         o = len;
 595                         if(o > BY2PG - eo)
 596                                 o = BY2PG - eo;
 597                         if(cpgmove(p, buf, eo, o)) {
 598                                 if(eo+o > p->len)
 599                                         p->len = eo+o;
 600                                 buf += o;
 601                                 len -= o;
 602                                 offset += o;
 603                         }
 604                 }
 605         }
 606
 607         /* free the overlap -- it's a rare case */
 608         eblock = offset+len;
 609         while(f && f->start < eblock) {
 610                 e = f->next;
 611                 extentfree(f);
 612                 f = e;
 613         }
 614
 615         /* link the block (if any) into the middle */
 616         e = cchain(buf, offset, len, &tail);
 617         if(e != 0) {
 618                 tail->next = f;
 619                 f = e;
 620         }
 621
 622         if(p == 0)
 623                 m->list = f;
 624         else
 625                 p->next = f;
 626         qunlock(m);
 627 }