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 /* called with cache locked */
 212 static Mntcache*
 213 clookup(Chan *c, int skipvers)
 214 {
 215         Mntcache *m;
 216
 217         for(m = cache.hash[c->qid.path%NHASH]; m; m = m->hash)
 218                 if(eqchantdqid(c, m->type, m->dev, m->qid, skipvers) && c->qid.type == m->qid.type)
 219                         return m;
 220
 221         return 0;
 222 }
 223
 224 void
 225 copen(Chan *c)
 226 {
 227         Mntcache *m, *f, **l;
 228
 229         /* directories aren't cacheable and append-only files confuse us */
 230         if(c->qid.type&(QTDIR|QTAPPEND)){
 231                 c->mcp = 0;
 232                 return;
 233         }
 234
 235         lock(&cache);
 236         m = clookup(c, 1);
 237         if(m == 0)
 238                 m = cache.head;
 239         else if(m->qid.vers == c->qid.vers) {
 240                 ctail(m);
 241                 unlock(&cache);
 242                 c->mcp = m;
 243                 return;
 244         }
 245         ctail(m);
 246
 247         l = &cache.hash[m->qid.path%NHASH];
 248         for(f = *l; f; f = f->hash) {
 249                 if(f == m) {
 250                         *l = m->hash;
 251                         break;
 252                 }
 253                 l = &f->hash;
 254         }
 255
 256         if(!canqlock(m)){
 257                 unlock(&cache);
 258                 qlock(m);
 259                 lock(&cache);
 260                 f = clookup(c, 0);
 261                 if(f != 0) {
 262                         /*
 263                          * someone got there first while cache lock
 264                          * was released and added a updated Mntcache
 265                          * for us. update LRU and use it.
 266                          */
 267                         ctail(f);
 268                         unlock(&cache);
 269                         qunlock(m);
 270                         c->mcp = f;
 271                         return;
 272                 }
 273         }
 274
 275         m->qid = c->qid;
 276         m->dev = c->dev;
 277         m->type = c->type;
 278
 279         l = &cache.hash[c->qid.path%NHASH];
 280         m->hash = *l;
 281         *l = m;
 282         unlock(&cache);
 283         cnodata(m);
 284         qunlock(m);
 285         c->mcp = m;
 286 }
 287
 288 /* return locked Mntcache if still valid else reset mcp */
 289 static Mntcache*
 290 ccache(Chan *c)
 291 {
 292         Mntcache *m;
 293
 294         m = c->mcp;
 295         if(m) {
 296                 qlock(m);
 297                 if(eqchantdqid(c, m->type, m->dev, m->qid, 0) && c->qid.type == m->qid.type)
 298                         return m;
 299                 c->mcp = 0;
 300                 qunlock(m);
 301         }
 302         return 0;
 303 }
 304
 305 int
 306 cread(Chan *c, uchar *buf, int len, vlong off)
 307 {
 308         KMap *k;
 309         Page *p;
 310         Mntcache *m;
 311         Extent *e, **t;
 312         int o, l, total;
 313         ulong offset;
 314
 315         if(off+len > maxcache)
 316                 return 0;
 317
 318         m = ccache(c);
 319         if(m == 0)
 320                 return 0;
 321
 322         offset = off;
 323         t = &m->list;
 324         for(e = *t; e; e = e->next) {
 325                 if(offset >= e->start && offset < e->start+e->len)
 326                         break;
 327                 t = &e->next;
 328         }
 329
 330         if(e == 0) {
 331                 qunlock(m);
 332                 return 0;
 333         }
 334
 335         total = 0;
 336         while(len) {
 337                 p = cpage(e);
 338                 if(p == 0) {
 339                         *t = e->next;
 340                         extentfree(e);
 341                         qunlock(m);
 342                         return total;
 343                 }
 344
 345                 o = offset - e->start;
 346                 l = len;
 347                 if(l > e->len-o)
 348                         l = e->len-o;
 349
 350                 k = kmap(p);
 351                 if(waserror()) {
 352                         kunmap(k);
 353                         putpage(p);
 354                         qunlock(m);
 355                         nexterror();
 356                 }
 357
 358                 memmove(buf, (uchar*)VA(k) + o, l);
 359
 360                 poperror();
 361                 kunmap(k);
 362
 363                 putpage(p);
 364
 365                 buf += l;
 366                 len -= l;
 367                 offset += l;
 368                 total += l;
 369                 t = &e->next;
 370                 e = e->next;
 371                 if(e == 0 || e->start != offset)
 372                         break;
 373         }
 374
 375         qunlock(m);
 376         return total;
 377 }
 378
 379 Extent*
 380 cchain(uchar *buf, ulong offset, int len, Extent **tail)
 381 {
 382         int l;
 383         Page *p;
 384         KMap *k;
 385         Extent *e, *start, **t;
 386
 387         start = 0;
 388         *tail = 0;
 389         t = &start;
 390         while(len) {
 391                 e = extentalloc();
 392                 if(e == 0)
 393                         break;
 394
 395                 p = auxpage();
 396                 if(p == 0) {
 397                         extentfree(e);
 398                         break;
 399                 }
 400                 l = len;
 401                 if(l > BY2PG)
 402                         l = BY2PG;
 403
 404                 e->cache = p;
 405                 e->start = offset;
 406                 e->len = l;
 407
 408                 lock(&cache);
 409                 e->bid = cache.pgno;
 410                 cache.pgno += BY2PG;
 411                 /* wrap the counter; low bits are unused by pghash but checked by lookpage */
 412                 if((cache.pgno & ~(BY2PG-1)) == 0){
 413                         if(cache.pgno == BY2PG-1){
 414                                 print("cache wrapped\n");
 415                                 cache.pgno = 0;
 416                         }else
 417                                 cache.pgno++;
 418                 }
 419                 unlock(&cache);
 420
 421                 p->daddr = e->bid;
 422                 k = kmap(p);
 423                 if(waserror()) {                /* buf may be virtual */
 424                         kunmap(k);
 425                         nexterror();
 426                 }
 427                 memmove((void*)VA(k), buf, l);
 428                 poperror();
 429                 kunmap(k);
 430
 431                 cachepage(p, &fscache);
 432                 putpage(p);
 433
 434                 buf += l;
 435                 offset += l;
 436                 len -= l;
 437
 438                 *t = e;
 439                 *tail = e;
 440                 t = &e->next;
 441         }
 442
 443         return start;
 444 }
 445
 446 int
 447 cpgmove(Extent *e, uchar *buf, int boff, int len)
 448 {
 449         Page *p;
 450         KMap *k;
 451
 452         p = cpage(e);
 453         if(p == 0)
 454                 return 0;
 455
 456         k = kmap(p);
 457         if(waserror()) {                /* Since buf may be virtual */
 458                 kunmap(k);
 459                 nexterror();
 460         }
 461
 462         memmove((uchar*)VA(k)+boff, buf, len);
 463
 464         poperror();
 465         kunmap(k);
 466         putpage(p);
 467
 468         return 1;
 469 }
 470
 471 void
 472 cupdate(Chan *c, uchar *buf, int len, vlong off)
 473 {
 474         Mntcache *m;
 475         Extent *tail;
 476         Extent *e, *f, *p;
 477         int o, ee, eblock;
 478         ulong offset;
 479
 480         if(off > maxcache || len == 0)
 481                 return;
 482
 483         m = ccache(c);
 484         if(m == 0)
 485                 return;
 486
 487         /*
 488          * Find the insertion point
 489          */
 490         offset = off;
 491         p = 0;
 492         for(f = m->list; f; f = f->next) {
 493                 if(f->start > offset)
 494                         break;
 495                 p = f;
 496         }
 497
 498         /* trim if there is a successor */
 499         eblock = offset+len;
 500         if(f != 0 && eblock > f->start) {
 501                 len -= (eblock - f->start);
 502                 if(len <= 0) {
 503                         qunlock(m);
 504                         return;
 505                 }
 506         }
 507
 508         if(p == 0) {            /* at the head */
 509                 e = cchain(buf, offset, len, &tail);
 510                 if(e != 0) {
 511                         m->list = e;
 512                         tail->next = f;
 513                 }
 514                 qunlock(m);
 515                 return;
 516         }
 517
 518         /* trim to the predecessor */
 519         ee = p->start+p->len;
 520         if(offset < ee) {
 521                 o = ee - offset;
 522                 len -= o;
 523                 if(len <= 0) {
 524                         qunlock(m);
 525                         return;
 526                 }
 527                 buf += o;
 528                 offset += o;
 529         }
 530
 531         /* try and pack data into the predecessor */
 532         if(offset == ee && p->len < BY2PG) {
 533                 o = len;
 534                 if(o > BY2PG - p->len)
 535                         o = BY2PG - p->len;
 536                 if(cpgmove(p, buf, p->len, o)) {
 537                         p->len += o;
 538                         buf += o;
 539                         len -= o;
 540                         offset += o;
 541                         if(len <= 0) {
 542                                 if(f && p->start + p->len > f->start)
 543                                         print("CACHE: p->start=%uld p->len=%d f->start=%uld\n",
 544                                                 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 = ccache(c);
 572         if(m == 0)
 573                 return;
 574
 575         offset = off;
 576         m->qid.vers++;
 577         c->qid.vers++;
 578
 579         p = 0;
 580         for(f = m->list; f; f = f->next) {
 581                 if(f->start >= offset)
 582                         break;
 583                 p = f;
 584         }
 585
 586         if(p != 0) {
 587                 ee = p->start+p->len;
 588                 eo = offset - p->start;
 589                 /* pack in predecessor if there is space */
 590                 if(offset <= ee && eo < BY2PG) {
 591                         o = len;
 592                         if(o > BY2PG - eo)
 593                                 o = BY2PG - eo;
 594                         if(cpgmove(p, buf, eo, o)) {
 595                                 if(eo+o > p->len)
 596                                         p->len = eo+o;
 597                                 buf += o;
 598                                 len -= o;
 599                                 offset += o;
 600                         }
 601                 }
 602         }
 603
 604         /* free the overlap -- it's a rare case */
 605         eblock = offset+len;
 606         while(f && f->start < eblock) {
 607                 e = f->next;
 608                 extentfree(f);
 609                 f = e;
 610         }
 611
 612         /* link the block (if any) into the middle */
 613         e = cchain(buf, offset, len, &tail);
 614         if(e != 0) {
 615                 tail->next = f;
 616                 f = e;
 617         }
 618
 619         if(p == 0)
 620                 m->list = f;
 621         else
 622                 p->next = f;
 623         qunlock(m);
 624 }