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;
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)
int i;
Mntcache *m;
- cache.head = xalloc(sizeof(Mntcache)*NFILE);
- m = cache.head;
+ m = xalloc(sizeof(Mntcache)*NFILE);
if (m == nil)
panic("cinit: no memory");
- /* a better algorithm would be nice */
- if(conf.npage*BY2PG > 200*MB)
- maxcache = 10*MAXCACHE;
+ cache.alloc = m;
+ cache.head = m;
for(i = 0; i < NFILE-1; i++) {
m->next = m+1;
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
return nil;
}
+enum {
+ VABITS = 8*sizeof(uintptr) - 2*PGSHIFT,
+ VAMASK = (((uintptr)1 << VABITS)-1) << PGSHIFT,
+};
+
+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;
+ }
+ *po = p->va & (BY2PG-1);
+ *pe = 1 + (p->va >> (PGSHIFT+VABITS));
+ assert(*po < *pe);
+ return p;
+}
+
+static void
+cpageset(Page *p, ulong po, ulong pe)
+{
+ assert(po < pe);
+ p->va = po | (p->va & VAMASK) | ((uintptr)pe - 1) << (PGSHIFT+VABITS);
+}
+
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(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);
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;
-
- e->cache = p;
- e->start = offset;
- e->len = l;
+ if(off >= MAXCACHE || len <= 0){
+ qunlock(m);
+ return;
+ }
- 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++;
+ 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(offset > pe || (offset+l) < po){
+ /* cached range 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 {
+ if(needpages(nil)){
+ invalidate(m, offset + pn*BY2PG, len);
+ break;
+ }
+ p = newpage(0, nil, pn*BY2PG);
+ 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);
+ cpageset(p, po, pe);
- 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);
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);
}
projects / plan9front.git / blobdiff