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 //      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: %#llux.%#lux %d %d %s (%d %c)\n",
 153         s, m->qid.path, m->qid.vers, m->type, m->dev, c->path->s, nb, ct ? 'C' : 'N');
 154
 155         for(e = m->list; e; e = e->next) {
 156                 pprint("\t%4d %5lud %4d %#p\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 }