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         NFILE           = 4093,         /* should be prime */
  12         MAXCACHE        = 8*1024*1024,
  13
  14         MAPBITS         = 8*sizeof(ulong),
  15         NBITMAP         = (PGROUND(MAXCACHE)/BY2PG + MAPBITS-1) / MAPBITS,
  16 };
  17
  18 /* devmnt.c: parallel read ahread implementation */
  19 extern void mntrahinit(Mntrah *rah);
  20 extern long mntrahread(Mntrah *rah, Chan *c, uchar *buf, long len, vlong off);
  21
  22 typedef struct Mntcache Mntcache;
  23 struct Mntcache
  24 {
  25         Qid             qid;
  26         int             dev;
  27         int             type;
  28
  29         QLock;
  30         Proc            *locked;
  31         ulong           nlocked;
  32
  33         Mntcache        *hash;
  34         Mntcache        *prev;
  35         Mntcache        *next;
  36
  37         /* page bitmap of valid pages */
  38         ulong           bitmap[NBITMAP];
  39
  40         /* read ahead state */
  41         Mntrah          rah;
  42 };
  43
  44 typedef struct Cache Cache;
  45 struct Cache
  46 {
  47         Lock;
  48         Mntcache        *alloc;
  49         Mntcache        *head;
  50         Mntcache        *tail;
  51         Mntcache        *hash[NHASH];
  52 };
  53
  54 Image fscache;
  55
  56 static Cache cache;
  57
  58 void
  59 cinit(void)
  60 {
  61         int i;
  62         Mntcache *m;
  63
  64         m = xalloc(sizeof(Mntcache)*NFILE);
  65         if (m == nil)
  66                 panic("cinit: no memory");
  67
  68         cache.alloc = m;
  69         cache.head = m;
  70
  71         for(i = 0; i < NFILE-1; i++) {
  72                 m->next = m+1;
  73                 m->prev = m-1;
  74                 m++;
  75         }
  76
  77         cache.tail = m;
  78         cache.tail->next = nil;
  79         cache.head->prev = nil;
  80
  81         fscache.notext = 1;
  82 }
  83
  84 static uintptr
  85 cacheaddr(Mntcache *m, ulong pn)
  86 {
  87         uintptr da = pn * NFILE + (m - cache.alloc);
  88         return (da << PGSHIFT) | (da >> (sizeof(da)*8 - PGSHIFT));
  89 }
  90
  91 static void
  92 cnodata(Mntcache *m)
  93 {
  94         memset(m->bitmap, 0, sizeof(m->bitmap));
  95 }
  96
  97 static void
  98 ctail(Mntcache *m)
  99 {
 100         /* Unlink and send to the tail */
 101         if(m->prev != nil)
 102                 m->prev->next = m->next;
 103         else
 104                 cache.head = m->next;
 105         if(m->next != nil)
 106                 m->next->prev = m->prev;
 107         else
 108                 cache.tail = m->prev;
 109
 110         if(cache.tail != nil) {
 111                 m->prev = cache.tail;
 112                 cache.tail->next = m;
 113                 m->next = nil;
 114                 cache.tail = m;
 115         }
 116         else {
 117                 cache.head = m;
 118                 cache.tail = m;
 119                 m->prev = nil;
 120                 m->next = nil;
 121         }
 122 }
 123
 124 /* called with cache locked */
 125 static Mntcache*
 126 clookup(Chan *c, int skipvers)
 127 {
 128         Mntcache *m;
 129
 130         for(m = cache.hash[c->qid.path%NHASH]; m != nil; m = m->hash)
 131                 if(eqchantdqid(c, m->type, m->dev, m->qid, skipvers) && c->qid.type == m->qid.type)
 132                         return m;
 133
 134         return nil;
 135 }
 136
 137 /*
 138  * resursive Mntcache locking. Mntcache.rah is protected by the
 139  * same lock and we want to call cupdate() from mntrahread()
 140  * while holding the lock.
 141  */
 142 static int
 143 cancachelock(Mntcache *m)
 144 {
 145         if(m->locked == up || canqlock(m)){
 146                 m->locked = up;
 147                 m->nlocked++;
 148                 return 1;
 149         }
 150         return 0;
 151 }
 152 static void
 153 cachelock(Mntcache *m)
 154 {
 155         if(m->locked != up){
 156                 qlock(m);
 157                 assert(m->nlocked == 0);
 158                 m->locked = up;
 159         }
 160         m->nlocked++;
 161
 162 }
 163 static void
 164 cacheunlock(Mntcache *m)
 165 {
 166         assert(m->locked == up);
 167         if(--m->nlocked == 0){
 168                 m->locked = nil;
 169                 qunlock(m);
 170         }
 171 }
 172
 173 /* return locked Mntcache if still valid else reset mcp */
 174 static Mntcache*
 175 ccache(Chan *c)
 176 {
 177         Mntcache *m;
 178
 179         m = c->mcp;
 180         if(m != nil) {
 181                 cachelock(m);
 182                 if(eqchantdqid(c, m->type, m->dev, m->qid, 0) && c->qid.type == m->qid.type)
 183                         return m;
 184                 c->mcp = nil;
 185                 cacheunlock(m);
 186         }
 187         return nil;
 188 }
 189
 190 int
 191 copen(Chan *c)
 192 {
 193         Mntcache *m, *f, **l;
 194
 195         /* directories aren't cacheable */
 196         if(c->qid.type&QTDIR){
 197                 c->mcp = nil;
 198                 return 0;
 199         }
 200
 201         lock(&cache);
 202         m = clookup(c, 0);
 203         if(m != nil){
 204                 ctail(m);
 205                 unlock(&cache);
 206                 c->mcp = m;
 207                 return 1;
 208         }
 209         m = clookup(c, 1);
 210         if(m == nil)
 211                 m = cache.head;
 212         ctail(m);
 213
 214         l = &cache.hash[m->qid.path%NHASH];
 215         for(f = *l; f != nil; f = f->hash) {
 216                 if(f == m) {
 217                         *l = m->hash;
 218                         break;
 219                 }
 220                 l = &f->hash;
 221         }
 222
 223         if(!cancachelock(m)){
 224                 unlock(&cache);
 225                 cachelock(m);
 226                 lock(&cache);
 227                 f = clookup(c, 0);
 228                 if(f != nil) {
 229                         /*
 230                          * someone got there first while cache lock
 231                          * was released and added a updated Mntcache
 232                          * for us. update LRU and use it.
 233                          */
 234                         ctail(f);
 235                         unlock(&cache);
 236                         cacheunlock(m);
 237                         c->mcp = f;
 238                         return 1;
 239                 }
 240         }
 241
 242         m->qid = c->qid;
 243         m->dev = c->dev;
 244         m->type = c->type;
 245
 246         l = &cache.hash[c->qid.path%NHASH];
 247         m->hash = *l;
 248         *l = m;
 249
 250         unlock(&cache);
 251
 252         m->rah.vers = m->qid.vers;
 253         mntrahinit(&m->rah);
 254         cnodata(m);
 255         cacheunlock(m);
 256         c->mcp = m;
 257         return 0;
 258 }
 259
 260 enum {
 261         VABITS  = 8*sizeof(uintptr) - 2*PGSHIFT,
 262         VAMASK  = (((uintptr)1 << VABITS)-1) << PGSHIFT,
 263 };
 264
 265 static Page*
 266 cpage(Mntcache *m, ulong pn, ulong *po, ulong *pe)
 267 {
 268         ulong b;
 269         Page *p;
 270
 271         b = 1 << (pn%MAPBITS);
 272         if((m->bitmap[pn/MAPBITS] & b) == 0)
 273                 return nil;
 274         p = lookpage(&fscache, cacheaddr(m, pn));
 275         if(p == nil){
 276                 m->bitmap[pn/MAPBITS] &= ~b;
 277                 return nil;
 278         }
 279         *po = p->va & (BY2PG-1);
 280         *pe = 1 + (p->va >> (PGSHIFT+VABITS));
 281         assert(*po < *pe);
 282         return p;
 283 }
 284
 285 static void
 286 cpageset(Page *p, ulong po, ulong pe)
 287 {
 288         assert(po < pe);
 289         p->va = po | (p->va & VAMASK) | ((uintptr)pe - 1) << (PGSHIFT+VABITS);
 290 }
 291
 292 int
 293 cread(Chan *c, uchar *buf, int len, vlong off)
 294 {
 295         KMap *k;
 296         Page *p;
 297         Mntcache *m;
 298         int l, tot;
 299         ulong offset, pn, po, pe;
 300
 301         if(len <= 0)
 302                 return 0;
 303
 304         m = ccache(c);
 305         if(m == nil)
 306                 return 0;
 307
 308         if(waserror()){
 309                 cacheunlock(m);
 310                 nexterror();
 311         }
 312
 313         tot = 0;
 314         if(off >= MAXCACHE)
 315                 goto Prefetch;
 316
 317         offset = off;
 318         if(offset+len > MAXCACHE)
 319                 len = MAXCACHE - offset;
 320         pn = offset / BY2PG;
 321         offset &= (BY2PG-1);
 322
 323         while(len > 0){
 324                 p = cpage(m, pn, &po, &pe);
 325                 if(p == nil)
 326                         break;
 327                 if(offset < po || offset >= pe){
 328                         putpage(p);
 329                         break;
 330                 }
 331                 l = pe - offset;
 332                 if(l > len)
 333                         l = len;
 334
 335                 k = kmap(p);
 336                 if(waserror()) {
 337                         kunmap(k);
 338                         putpage(p);
 339                         nexterror();
 340                 }
 341                 memmove(buf, (uchar*)VA(k) + offset, l);
 342                 kunmap(k);
 343                 putpage(p);
 344                 poperror();
 345
 346                 tot += l;
 347                 buf += l;
 348                 len -= l;
 349
 350                 offset += l;
 351                 offset &= (BY2PG-1);
 352                 if(offset != 0)
 353                         break;
 354
 355                 pn++;
 356         }
 357
 358 Prefetch:
 359         if(len > 0){
 360                 if(m->rah.vers != m->qid.vers){
 361                         mntrahinit(&m->rah);
 362                         m->rah.vers = m->qid.vers;
 363                 }
 364                 off += tot;
 365                 tot += mntrahread(&m->rah, c, buf, len, off);
 366         }
 367         cacheunlock(m);
 368         poperror();
 369
 370         return tot;
 371 }
 372
 373 /* invalidate pages in page bitmap */
 374 static void
 375 invalidate(Mntcache *m, ulong offset, int len)
 376 {
 377         ulong pn;
 378
 379         for(pn = offset/BY2PG; len > 0; pn++, len -= BY2PG)
 380                 m->bitmap[pn/MAPBITS] &= ~(1 << (pn%MAPBITS));
 381 }
 382
 383 /* replace buf data from [off, off+len) in the cache or invalidate */
 384 static void
 385 cachedata(Mntcache *m, uchar *buf, int len, vlong off)
 386 {
 387         int l;
 388         Page *p;
 389         KMap *k;
 390         ulong offset, pn, po, pe;
 391
 392         if(off >= MAXCACHE || len <= 0){
 393                 cacheunlock(m);
 394                 return;
 395         }
 396
 397         offset = off;
 398         if(offset+len > MAXCACHE)
 399                 len = MAXCACHE - offset;
 400         pn = offset / BY2PG;
 401         offset &= (BY2PG-1);
 402
 403         while(len > 0){
 404                 l = BY2PG - offset;
 405                 if(l > len)
 406                         l = len;
 407                 p = cpage(m, pn, &po, &pe);
 408                 if(p != nil){
 409                         if(offset > pe || (offset+l) < po){
 410                                 /* cached range not extendable, set new cached range */
 411                                 po = offset;
 412                                 pe = offset+l;
 413                         } else {
 414                                 /* extend cached range */
 415                                 if(offset < po)
 416                                         po = offset;
 417                                 if((offset+l) > pe)
 418                                         pe = offset+l;
 419                         }
 420                 } else {
 421                         if(needpages(nil)){
 422                                 invalidate(m, offset + pn*BY2PG, len);
 423                                 break;
 424                         }
 425                         p = newpage(0, nil, pn*BY2PG);
 426                         p->daddr = cacheaddr(m, pn);
 427                         cachedel(&fscache, p->daddr);
 428                         cachepage(p, &fscache);
 429                         m->bitmap[pn/MAPBITS] |= 1 << (pn%MAPBITS);
 430
 431                         po = offset;
 432                         pe = offset+l;
 433                 }
 434                 cpageset(p, po, pe);
 435
 436                 k = kmap(p);
 437                 if(waserror()) {
 438                         kunmap(k);
 439                         putpage(p);
 440                         invalidate(m, offset + pn*BY2PG, len);
 441                         cacheunlock(m);
 442                         nexterror();
 443                 }
 444                 memmove((uchar*)VA(k) + offset, buf, l);
 445                 poperror();
 446                 kunmap(k);
 447                 putpage(p);
 448
 449                 offset = 0;
 450                 pn++;
 451                 buf += l;
 452                 len -= l;
 453         }
 454         cacheunlock(m);
 455 }
 456
 457 void
 458 cupdate(Chan *c, uchar *buf, int len, vlong off)
 459 {
 460         Mntcache *m;
 461
 462         m = ccache(c);
 463         if(m == nil)
 464                 return;
 465         cachedata(m, buf, len, off);
 466 }
 467
 468 void
 469 cwrite(Chan* c, uchar *buf, int len, vlong off)
 470 {
 471         Mntcache *m;
 472
 473         m = ccache(c);
 474         if(m == nil)
 475                 return;
 476         m->qid.vers++;
 477         c->qid.vers++;
 478         if(c->qid.type&QTAPPEND){
 479                 cacheunlock(m);
 480                 return;
 481         }
 482         cachedata(m, buf, len, off);
 483 }
 484
 485 void
 486 ctrunc(Chan *c)
 487 {
 488         Mntcache *m;
 489
 490         if(c->qid.type&QTDIR)
 491                 return;
 492
 493         if((c->flag&COPEN) == 0){
 494                 lock(&cache);
 495                 c->mcp = clookup(c, 0);
 496                 unlock(&cache);
 497         }
 498
 499         m = ccache(c);
 500         if(m == nil)
 501                 return;
 502         mntrahinit(&m->rah);
 503         cnodata(m);
 504         cacheunlock(m);
 505
 506         if((c->flag&COPEN) == 0)
 507                 c->mcp = nil;
 508 }
 509
 510 void
 511 cclunk(Chan *c)
 512 {
 513         Mntcache *m;
 514
 515         m = ccache(c);
 516         if(m == nil)
 517                 return;
 518         mntrahinit(&m->rah);
 519         cacheunlock(m);
 520         c->mcp = nil;
 521 }