kernel: new mount cache

this is a new more simple version of the mount cache
that does not require dynamic allocations for extends.

the Mntcache structure now contains a page bitmap
that is used for quick page invalidation. the size
of the bitmap is proportional to MAXCACHE.

instead of keeping track of cached range in the
Extend data structure, we keep all the information
in the Page itself. the offset from the page where
the cache range starts is in the low PGSHIT bits and
the end in the top bits of Page.va.

we choose Page.daddr to map 1:1 the Mountcache number
and page number (pn) in the Mountcache. to find a page,
we first check the bitmap if the page is there and then
do a pagelookup() with the daddr key.

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);
 }