git: 9front

Download patch

ref: 0abcb4c245b8b6428bc9ac944f6713226b0b7bb8
parent: f539ef10843fc020f45cf41aa853903f0cfdbdd8
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Tue Dec 16 00:41:20 EST 2014 

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.


--- 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,11 +21,14 @@
 	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;
@@ -40,69 +35,16 @@
 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 @@
 	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 @@
 	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,6 +205,26 @@
 	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)
 {
@@ -283,11 +231,10 @@
 	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);
@@ -294,33 +241,26 @@
 	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)
-			break;
-		t = &e->next;
-	}
+	if(offset+len > MAXCACHE)
+		len = MAXCACHE - offset;
+	pn = offset / BY2PG;
+	offset &= (BY2PG-1);
 
-	if(e == nil) {
-		qunlock(m);
-		return 0;
-	}
-
-	total = 0;
-	while(len > 0) {
-		p = cpage(e);
-		if(p == nil) {
-			*t = e->next;
-			extentfree(e);
+	while(len > 0){
+		p = cpage(m, pn, &po, &pe);
+		if(p == nil)
 			break;
+		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 @@
 			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;
+	ulong offset, pn, po, pe;
 
-	start = nil;
-	*tail = nil;
-	t = &start;
-	while(len > 0) {
-		e = extentalloc();
-		if(e == nil)
-			break;
+	if(off >= MAXCACHE || len <= 0){
+		qunlock(m);
+		return;
+	}
 
-		p = auxpage();
-		if(p == nil) {
-			extentfree(e);
-			break;
-		}
-		l = len;
-		if(l > BY2PG)
-			l = BY2PG;
+	offset = off;
+	if(offset+len > MAXCACHE)
+		len = MAXCACHE - offset;
+	pn = offset / BY2PG;
+	offset &= (BY2PG-1);
 
-		e->cache = p;
-		e->start = offset;
-		e->len = l;
+	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;
+	qunlock(m);
 }
 
-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;
-}
-
 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);
 }
-- 
⑨