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 typedef struct Mntcache Mntcache;
  19 struct Mntcache
  20 {
  21         Qid     qid;
  22         int     dev;
  23         int     type;
  24
  25         QLock;
  26         Mntcache        *hash;
  27         Mntcache        *prev;
  28         Mntcache        *next;
  29
  30         /* page bitmap of valid pages */
  31         ulong           bitmap[NBITMAP];
  32 };
  33
  34 typedef struct Cache Cache;
  35 struct Cache
  36 {
  37         Lock;
  38         Mntcache        *alloc;
  39         Mntcache        *head;
  40         Mntcache        *tail;
  41         Mntcache        *hash[NHASH];
  42 };
  43
  44 Image fscache;
  45
  46 static Cache cache;
  47
  48 void
  49 cinit(void)
  50 {
  51         int i;
  52         Mntcache *m;
  53
  54         m = xalloc(sizeof(Mntcache)*NFILE);
  55         if (m == nil)
  56                 panic("cinit: no memory");
  57
  58         cache.alloc = m;
  59         cache.head = m;
  60
  61         for(i = 0; i < NFILE-1; i++) {
  62                 m->next = m+1;
  63                 m->prev = m-1;
  64                 m++;
  65         }
  66
  67         cache.tail = m;
  68         cache.tail->next = nil;
  69         cache.head->prev = nil;
  70
  71         fscache.notext = 1;
  72 }
  73
  74 static uintptr
  75 cacheaddr(Mntcache *m, ulong pn)
  76 {
  77         uintptr da = pn * NFILE + (m - cache.alloc);
  78         return (da << PGSHIFT) | (da >> (sizeof(da)*8 - PGSHIFT));
  79 }
  80
  81 static void
  82 cnodata(Mntcache *m)
  83 {
  84         memset(m->bitmap, 0, sizeof(m->bitmap));
  85 }
  86
  87 static void
  88 ctail(Mntcache *m)
  89 {
  90         /* Unlink and send to the tail */
  91         if(m->prev != nil)
  92                 m->prev->next = m->next;
  93         else
  94                 cache.head = m->next;
  95         if(m->next != nil)
  96                 m->next->prev = m->prev;
  97         else
  98                 cache.tail = m->prev;
  99
 100         if(cache.tail != nil) {
 101                 m->prev = cache.tail;
 102                 cache.tail->next = m;
 103                 m->next = nil;
 104                 cache.tail = m;
 105         }
 106         else {
 107                 cache.head = m;
 108                 cache.tail = m;
 109                 m->prev = nil;
 110                 m->next = nil;
 111         }
 112 }
 113
 114 /* called with cache locked */
 115 static Mntcache*
 116 clookup(Chan *c, int skipvers)
 117 {
 118         Mntcache *m;
 119
 120         for(m = cache.hash[c->qid.path%NHASH]; m != nil; m = m->hash)
 121                 if(eqchantdqid(c, m->type, m->dev, m->qid, skipvers) && c->qid.type == m->qid.type)
 122                         return m;
 123
 124         return nil;
 125 }
 126
 127 void
 128 copen(Chan *c)
 129 {
 130         Mntcache *m, *f, **l;
 131
 132         /* directories aren't cacheable and append-only files confuse us */
 133         if(c->qid.type&(QTDIR|QTAPPEND)){
 134                 c->mcp = nil;
 135                 return;
 136         }
 137
 138         lock(&cache);
 139         m = clookup(c, 1);
 140         if(m == nil)
 141                 m = cache.head;
 142         else if(m->qid.vers == c->qid.vers) {
 143                 ctail(m);
 144                 unlock(&cache);
 145                 c->mcp = m;
 146                 return;
 147         }
 148         ctail(m);
 149
 150         l = &cache.hash[m->qid.path%NHASH];
 151         for(f = *l; f != nil; f = f->hash) {
 152                 if(f == m) {
 153                         *l = m->hash;
 154                         break;
 155                 }
 156                 l = &f->hash;
 157         }
 158
 159         if(!canqlock(m)){
 160                 unlock(&cache);
 161                 qlock(m);
 162                 lock(&cache);
 163                 f = clookup(c, 0);
 164                 if(f != nil) {
 165                         /*
 166                          * someone got there first while cache lock
 167                          * was released and added a updated Mntcache
 168                          * for us. update LRU and use it.
 169                          */
 170                         ctail(f);
 171                         unlock(&cache);
 172                         qunlock(m);
 173                         c->mcp = f;
 174                         return;
 175                 }
 176         }
 177
 178         m->qid = c->qid;
 179         m->dev = c->dev;
 180         m->type = c->type;
 181
 182         l = &cache.hash[c->qid.path%NHASH];
 183         m->hash = *l;
 184         *l = m;
 185         unlock(&cache);
 186         cnodata(m);
 187         qunlock(m);
 188         c->mcp = m;
 189 }
 190
 191 /* return locked Mntcache if still valid else reset mcp */
 192 static Mntcache*
 193 ccache(Chan *c)
 194 {
 195         Mntcache *m;
 196
 197         m = c->mcp;
 198         if(m != nil) {
 199                 qlock(m);
 200                 if(eqchantdqid(c, m->type, m->dev, m->qid, 0) && c->qid.type == m->qid.type)
 201                         return m;
 202                 c->mcp = nil;
 203                 qunlock(m);
 204         }
 205         return nil;
 206 }
 207
 208 enum {
 209         VABITS  = 8*sizeof(uintptr) - 2*PGSHIFT,
 210         VAMASK  = (((uintptr)1 << VABITS)-1) << PGSHIFT,
 211 };
 212
 213 static Page*
 214 cpage(Mntcache *m, ulong pn, ulong *po, ulong *pe)
 215 {
 216         ulong b;
 217         Page *p;
 218
 219         b = 1 << (pn%MAPBITS);
 220         if((m->bitmap[pn/MAPBITS] & b) == 0)
 221                 return nil;
 222         p = lookpage(&fscache, cacheaddr(m, pn));
 223         if(p == nil){
 224                 m->bitmap[pn/MAPBITS] &= ~b;
 225                 return nil;
 226         }
 227         *po = p->va & (BY2PG-1);
 228         *pe = 1 + (p->va >> (PGSHIFT+VABITS));
 229         assert(*po < *pe);
 230         return p;
 231 }
 232
 233 static void
 234 cpageset(Page *p, ulong po, ulong pe)
 235 {
 236         assert(po < pe);
 237         p->va = po | (p->va & VAMASK) | ((uintptr)pe - 1) << (PGSHIFT+VABITS);
 238 }
 239
 240 int
 241 cread(Chan *c, uchar *buf, int len, vlong off)
 242 {
 243         KMap *k;
 244         Page *p;
 245         Mntcache *m;
 246         int l, total;
 247         ulong offset, pn, po, pe;
 248
 249         if(off >= MAXCACHE || len <= 0)
 250                 return 0;
 251
 252         m = ccache(c);
 253         if(m == nil)
 254                 return 0;
 255
 256         total = 0;
 257
 258         offset = off;
 259         if(offset+len > MAXCACHE)
 260                 len = MAXCACHE - offset;
 261         pn = offset / BY2PG;
 262         offset &= (BY2PG-1);
 263
 264         while(len > 0){
 265                 p = cpage(m, pn, &po, &pe);
 266                 if(p == nil)
 267                         break;
 268                 if(offset < po || offset >= pe){
 269                         putpage(p);
 270                         break;
 271                 }
 272                 l = pe - offset;
 273                 if(l > len)
 274                         l = len;
 275
 276                 k = kmap(p);
 277                 if(waserror()) {
 278                         kunmap(k);
 279                         putpage(p);
 280                         qunlock(m);
 281                         nexterror();
 282                 }
 283                 memmove(buf, (uchar*)VA(k) + offset, l);
 284                 poperror();
 285                 kunmap(k);
 286
 287                 putpage(p);
 288
 289                 total += l;
 290
 291                 offset += l;
 292                 offset &= (BY2PG-1);
 293                 if(offset != 0)
 294                         break;
 295
 296                 pn++;
 297                 buf += l;
 298                 len -= l;
 299         }
 300         qunlock(m);
 301
 302         return total;
 303 }
 304
 305 /* invalidate pages in page bitmap */
 306 static void
 307 invalidate(Mntcache *m, ulong offset, int len)
 308 {
 309         ulong pn;
 310
 311         for(pn = offset/BY2PG; len > 0; pn++, len -= BY2PG)
 312                 m->bitmap[pn/MAPBITS] &= ~(1 << (pn%MAPBITS));
 313 }
 314
 315 /* replace buf data from [off, off+len) in the cache or invalidate */
 316 static void
 317 cachedata(Mntcache *m, uchar *buf, int len, vlong off)
 318 {
 319         int l;
 320         Page *p;
 321         KMap *k;
 322         ulong offset, pn, po, pe;
 323
 324         if(off >= MAXCACHE || len <= 0){
 325                 qunlock(m);
 326                 return;
 327         }
 328
 329         offset = off;
 330         if(offset+len > MAXCACHE)
 331                 len = MAXCACHE - offset;
 332         pn = offset / BY2PG;
 333         offset &= (BY2PG-1);
 334
 335         while(len > 0){
 336                 l = BY2PG - offset;
 337                 if(l > len)
 338                         l = len;
 339                 p = cpage(m, pn, &po, &pe);
 340                 if(p != nil){
 341                         if(offset > pe || (offset+l) < po){
 342                                 /* cached range not extendable, set new cached range */
 343                                 po = offset;
 344                                 pe = offset+l;
 345                         } else {
 346                                 /* extend cached range */
 347                                 if(offset < po)
 348                                         po = offset;
 349                                 if((offset+l) > pe)
 350                                         pe = offset+l;
 351                         }
 352                 } else {
 353                         if(needpages(nil)){
 354                                 invalidate(m, offset + pn*BY2PG, len);
 355                                 break;
 356                         }
 357                         p = newpage(0, nil, pn*BY2PG);
 358                         p->daddr = cacheaddr(m, pn);
 359                         cachedel(&fscache, p->daddr);
 360                         cachepage(p, &fscache);
 361                         m->bitmap[pn/MAPBITS] |= 1 << (pn%MAPBITS);
 362
 363                         po = offset;
 364                         pe = offset+l;
 365                 }
 366                 cpageset(p, po, pe);
 367
 368                 k = kmap(p);
 369                 if(waserror()) {
 370                         kunmap(k);
 371                         putpage(p);
 372                         invalidate(m, offset + pn*BY2PG, len);
 373                         qunlock(m);
 374                         nexterror();
 375                 }
 376                 memmove((uchar*)VA(k) + offset, buf, l);
 377                 poperror();
 378                 kunmap(k);
 379                 putpage(p);
 380
 381                 offset = 0;
 382                 pn++;
 383                 buf += l;
 384                 len -= l;
 385         }
 386         qunlock(m);
 387 }
 388
 389 void
 390 cupdate(Chan *c, uchar *buf, int len, vlong off)
 391 {
 392         Mntcache *m;
 393
 394         m = ccache(c);
 395         if(m == nil)
 396                 return;
 397         cachedata(m, buf, len, off);
 398 }
 399
 400 void
 401 cwrite(Chan* c, uchar *buf, int len, vlong off)
 402 {
 403         Mntcache *m;
 404
 405         m = ccache(c);
 406         if(m == nil)
 407                 return;
 408         m->qid.vers++;
 409         c->qid.vers++;
 410         cachedata(m, buf, len, off);
 411 }