diff options
| -rw-r--r-- | sys/src/9/port/cache.c | 461 |
1 files changed, 136 insertions, 325 deletions
diff --git a/sys/src/9/port/cache.c b/sys/src/9/port/cache.c index 4391a026d..702fa94d5 100644 --- a/sys/src/9/port/cache.c +++ b/sys/src/9/port/cache.c @@ -8,19 +8,11 @@ enum { NHASH = 128, - MAXCACHE = 1024*1024, - NFILE = 4096, - NEXTENT = 200, /* extent allocation size */ -}; + NFILE = 4093, /* should be prime */ + MAXCACHE = 8*1024*1024, -typedef struct Extent Extent; -struct Extent -{ - uintptr bid; - ulong start; - int len; - Page *cache; - Extent *next; + MAPBITS = 8*sizeof(ulong), + NBITMAP = (PGROUND(MAXCACHE)/BY2PG + MAPBITS-1) / MAPBITS, }; typedef struct Mntcache Mntcache; @@ -29,79 +21,29 @@ struct Mntcache Qid qid; int dev; int type; + QLock; - Extent *list; - Mntcache *hash; - Mntcache *prev; - Mntcache *next; + Mntcache *hash; + Mntcache *prev; + Mntcache *next; + + /* page bitmap of valid pages */ + ulong bitmap[NBITMAP]; }; typedef struct Cache Cache; struct Cache { Lock; - uintptr pgno; + Mntcache *alloc; Mntcache *head; Mntcache *tail; Mntcache *hash[NHASH]; }; -typedef struct Ecache Ecache; -struct Ecache -{ - Lock; - int total; - int free; - Extent* head; -}; - Image fscache; static Cache cache; -static Ecache ecache; -static ulong maxcache = MAXCACHE; - -static void -extentfree(Extent* e) -{ - lock(&ecache); - e->next = ecache.head; - ecache.head = e; - ecache.free++; - unlock(&ecache); -} - -static Extent* -extentalloc(void) -{ - Extent *e; - int i; - - lock(&ecache); - if(ecache.head == nil){ - e = xalloc(NEXTENT*sizeof(Extent)); - if(e == nil){ - unlock(&ecache); - return nil; - } - for(i = 0; i < NEXTENT; i++){ - e->next = ecache.head; - ecache.head = e; - e++; - } - ecache.total += NEXTENT; - ecache.free += NEXTENT; - } - - e = ecache.head; - ecache.head = e->next; - ecache.free--; - unlock(&ecache); - - memset(e, 0, sizeof(Extent)); - - return e; -} void cinit(void) @@ -109,14 +51,12 @@ cinit(void) int i; Mntcache *m; - cache.head = xalloc(sizeof(Mntcache)*NFILE); - m = cache.head; + cache.alloc = xalloc(sizeof(Mntcache)*NFILE); + m = cache.alloc; if (m == nil) panic("cinit: no memory"); - /* a better algorithm would be nice */ - if(conf.npage*BY2PG > 200*MB) - maxcache = 10*MAXCACHE; + cache.head = m; for(i = 0; i < NFILE-1; i++) { m->next = m+1; @@ -131,29 +71,17 @@ cinit(void) fscache.notext = 1; } -static Page* -cpage(Extent *e) +static uintptr +cacheaddr(Mntcache *m, ulong pn) { - /* Easy consistency check */ - if(e->cache->daddr != e->bid) - return nil; - - return lookpage(&fscache, e->bid); + uintptr da = pn * NFILE + (m - cache.alloc); + return (da << PGSHIFT) | (da >> (sizeof(da)*8 - PGSHIFT)); } static void cnodata(Mntcache *m) { - Extent *e; - - /* - * Invalidate all extent data - * pagereclaim() will waste the pages - */ - while((e = m->list) != nil){ - m->list = e->next; - extentfree(e); - } + memset(m->bitmap, 0, sizeof(m->bitmap)); } static void @@ -277,50 +205,62 @@ ccache(Chan *c) return nil; } +static Page* +cpage(Mntcache *m, ulong pn, ulong *po, ulong *pe) +{ + ulong b; + Page *p; + + b = 1 << (pn%MAPBITS); + if((m->bitmap[pn/MAPBITS] & b) == 0) + return nil; + p = lookpage(&fscache, cacheaddr(m, pn)); + if(p == nil){ + m->bitmap[pn/MAPBITS] &= ~b; + return nil; + } + /* see cachedata() below */ + *po = (ulong)p->va & (BY2PG-1); + *pe = (ulong)p->va >> PGSHIFT; + return p; +} + int cread(Chan *c, uchar *buf, int len, vlong off) { KMap *k; Page *p; Mntcache *m; - Extent *e, **t; - int o, l, total; - ulong offset; + int l, total; + ulong offset, pn, po, pe; - if(off >= maxcache || len <= 0) + if(off >= MAXCACHE || len <= 0) return 0; m = ccache(c); if(m == nil) return 0; + total = 0; + offset = off; - t = &m->list; - for(e = *t; e != nil; e = e->next) { - if(offset >= e->start && offset < e->start+e->len) + if(offset+len > MAXCACHE) + len = MAXCACHE - offset; + pn = offset / BY2PG; + offset &= (BY2PG-1); + + while(len > 0){ + p = cpage(m, pn, &po, &pe); + if(p == nil) break; - t = &e->next; - } - - if(e == nil) { - qunlock(m); - return 0; - } - - total = 0; - while(len > 0) { - p = cpage(e); - if(p == nil) { - *t = e->next; - extentfree(e); + if(po >= pe || offset < po || offset >= pe){ + putpage(p); break; } - - o = offset - e->start; - l = len; - if(l > e->len-o) - l = e->len-o; - + l = pe - offset; + if(l > len) + l = len; + k = kmap(p); if(waserror()) { kunmap(k); @@ -328,265 +268,136 @@ cread(Chan *c, uchar *buf, int len, vlong off) qunlock(m); nexterror(); } - - memmove(buf, (uchar*)VA(k) + o, l); - + memmove(buf, (uchar*)VA(k) + offset, l); poperror(); kunmap(k); putpage(p); - buf += l; - len -= l; - offset += l; total += l; - t = &e->next; - e = e->next; - if(e == nil || e->start != offset) + + offset += l; + offset &= (BY2PG-1); + if(offset != 0) break; - } + pn++; + buf += l; + len -= l; + } qunlock(m); + return total; } -static Extent* -cchain(uchar *buf, ulong offset, int len, Extent **tail) +/* invalidate pages in page bitmap */ +static void +invalidate(Mntcache *m, ulong offset, int len) +{ + ulong pn; + + for(pn = offset/BY2PG; len > 0; pn++, len -= BY2PG) + m->bitmap[pn/MAPBITS] &= ~(1 << (pn%MAPBITS)); +} + +/* replace buf data from [off, off+len) in the cache or invalidate */ +static void +cachedata(Mntcache *m, uchar *buf, int len, vlong off) { int l; Page *p; KMap *k; - Extent *e, *start, **t; - - start = nil; - *tail = nil; - t = &start; - while(len > 0) { - e = extentalloc(); - if(e == nil) - break; + ulong offset, pn, po, pe; - p = auxpage(); - if(p == nil) { - extentfree(e); - break; - } - l = len; - if(l > BY2PG) - l = BY2PG; + if(off >= MAXCACHE || len <= 0){ + qunlock(m); + return; + } - e->cache = p; - e->start = offset; - e->len = l; + offset = off; + if(offset+len > MAXCACHE) + len = MAXCACHE - offset; + pn = offset / BY2PG; + offset &= (BY2PG-1); + + while(len > 0){ + l = BY2PG - offset; + if(l > len) + l = len; + p = cpage(m, pn, &po, &pe); + if(p != nil){ + if(po >= pe || offset > pe || (offset+l) < po){ + /* cached range empty or not extendable, set new cached range */ + po = offset; + pe = offset+l; + } else { + /* extend cached range */ + if(offset < po) + po = offset; + if((offset+l) > pe) + pe = offset+l; + } + } else { + p = auxpage(); + if(p == nil){ + invalidate(m, offset + pn*BY2PG, len); + break; + } - lock(&cache); - e->bid = cache.pgno; - cache.pgno += BY2PG; - /* wrap the counter; low bits are unused by pghash but checked by lookpage */ - if((cache.pgno & ~(BY2PG-1)) == 0){ - if(cache.pgno == BY2PG-1){ - print("cache wrapped\n"); - cache.pgno = 0; - }else - cache.pgno++; + p->va = 0; + p->daddr = cacheaddr(m, pn); + cachedel(&fscache, p->daddr); + cachepage(p, &fscache); + m->bitmap[pn/MAPBITS] |= 1 << (pn%MAPBITS); + + po = offset; + pe = offset+l; } - unlock(&cache); - p->daddr = e->bid; k = kmap(p); - if(waserror()) { /* buf may be virtual */ + if(waserror()) { kunmap(k); + putpage(p); + invalidate(m, offset + pn*BY2PG, len); + qunlock(m); nexterror(); } - memmove((void*)VA(k), buf, l); + memmove((uchar*)VA(k) + offset, buf, l); poperror(); kunmap(k); - cachepage(p, &fscache); + /* update cached range */ + p->va = po | (pe << PGSHIFT); putpage(p); + offset = 0; + pn++; buf += l; - offset += l; len -= l; - - *t = e; - *tail = e; - t = &e->next; - } - - return start; -} - -static int -cpgmove(Extent *e, uchar *buf, int boff, int len) -{ - Page *p; - KMap *k; - - p = cpage(e); - if(p == nil) - return 0; - - k = kmap(p); - if(waserror()) { /* Since buf may be virtual */ - kunmap(k); - nexterror(); } - - memmove((uchar*)VA(k)+boff, buf, len); - - poperror(); - kunmap(k); - putpage(p); - - return 1; + qunlock(m); } void cupdate(Chan *c, uchar *buf, int len, vlong off) { - int o; Mntcache *m; - Extent *tail; - Extent *e, *f, *p; - ulong offset, eblock, ee; - - if(off >= maxcache || len <= 0) - return; m = ccache(c); if(m == nil) return; - - /* - * Find the insertion point - */ - offset = off; - p = nil; - for(f = m->list; f != nil; f = f->next) { - if(f->start > offset) - break; - p = f; - } - - /* trim if there is a successor */ - eblock = offset+len; - if(f != nil && eblock > f->start) { - len -= (eblock - f->start); - if(len <= 0) - goto out; - } - - if(p == nil) { /* at the head */ - e = cchain(buf, offset, len, &tail); - if(e != nil) { - m->list = e; - tail->next = f; - } - goto out; - } - - /* trim to the predecessor */ - ee = p->start+p->len; - if(offset < ee) { - o = ee - offset; - len -= o; - if(len <= 0) - goto out; - buf += o; - offset += o; - } - - /* try and pack data into the predecessor */ - if(offset == ee && p->len < BY2PG) { - o = len; - if(o > BY2PG - p->len) - o = BY2PG - p->len; - if(cpgmove(p, buf, p->len, o)) { - p->len += o; - buf += o; - len -= o; - offset += o; - if(len <= 0) { - if(f != nil && p->start + p->len > f->start) - print("CACHE: p->start=%uld p->len=%d f->start=%uld\n", - p->start, p->len, f->start); - goto out; - } - } - } - - e = cchain(buf, offset, len, &tail); - if(e != nil) { - p->next = e; - tail->next = f; - } -out: - qunlock(m); + cachedata(m, buf, len, off); } void cwrite(Chan* c, uchar *buf, int len, vlong off) { - int o, eo; Mntcache *m; - Extent *p, *f, *e, *tail; - ulong offset, eblock, ee; - - if(off >= maxcache || len <= 0) - return; m = ccache(c); if(m == nil) return; - - offset = off; m->qid.vers++; c->qid.vers++; - - p = nil; - for(f = m->list; f != nil; f = f->next) { - if(f->start >= offset) - break; - p = f; - } - - if(p != nil) { - ee = p->start+p->len; - eo = offset - p->start; - /* pack in predecessor if there is space */ - if(offset <= ee && eo < BY2PG) { - o = len; - if(o > BY2PG - eo) - o = BY2PG - eo; - if(cpgmove(p, buf, eo, o)) { - if(eo+o > p->len) - p->len = eo+o; - buf += o; - len -= o; - offset += o; - } - } - } - - /* free the overlap -- it's a rare case */ - eblock = offset+len; - while(f != nil && f->start < eblock) { - e = f->next; - extentfree(f); - f = e; - } - - /* link the block (if any) into the middle */ - e = cchain(buf, offset, len, &tail); - if(e != nil) { - tail->next = f; - f = e; - } - - if(p == nil) - m->list = f; - else - p->next = f; - qunlock(m); + cachedata(m, buf, len, off); } |