kernel: new pagecache, remove Lock from page, use cmpswap for Ref instead of Lock

make the Page stucture less than half its original size by getting rid of
the Lock and the lru.

The Lock was required to coordinate the unchaining of pages that where
both cached and on the lru freelist.

now pages have a single next pointer that is used for palloc.head
freelist xor for page cache hash chains in Image.pghash[].

cached pages are not on the freelist anymore, but will be reclaimed
from images by the pager when the freelist runs out of pages.

each Image has its own 512 hash chains for cached page lookup. That is
2MB worth of pages and there should be no collisions for most text images.

page reclaiming can be done without holding palloc.lock as the Image is
the owner of the page hash chains protected by the Image's lock.

reclaiming Image structures can be done quickly by only reclaiming pages from
inactive images, that is images which are not currently in use by segments.

the Ref structure has no Lock anymore. Only a single long that is atomically
incremented or decremnted using cmpswap().

there are various other changes as a consequence code. and lots of pikeshedding,
sorry.

1 files changed, 165 insertions, 218 deletions

diff --git a/sys/src/9/port/page.c b/sys/src/9/port/page.c
index 48e393d2b..f3397c4fa 100644
--- a/sys/src/9/port/page.c
+++ b/sys/src/9/port/page.c
@@ -5,9 +5,7 @@
 #include	"fns.h"
 #include	"../port/error.h"
 
-#define	pghash(daddr)	palloc.hash[(daddr>>PGSHIFT)&(PGHSIZE-1)]
-
-struct	Palloc palloc;
+Palloc palloc;
 
 void
 pageinit(void)
@@ -31,24 +29,19 @@ pageinit(void)
 	}
 
 	color = 0;
-	palloc.head = palloc.pages;
-	p = palloc.head;
+	palloc.head = nil;
+	p = palloc.pages;
 	for(i=0; i<nelem(palloc.mem); i++){
 		pm = &palloc.mem[i];
 		for(j=0; j<pm->npage; j++){
 			memset(p, 0, sizeof *p);
-			p->prev = p-1;
-			p->next = p+1;
 			p->pa = pm->base+j*BY2PG;
 			p->color = color;
-			palloc.freecount++;
 			color = (color+1)%NCOLOR;
+			pagechainhead(p);
 			p++;
 		}
 	}
-	palloc.tail = p - 1;
-	palloc.head->prev = 0;
-	palloc.tail->next = 0;
 
 	palloc.user = p - palloc.pages;
 	u = palloc.user*BY2PG;
@@ -71,78 +64,100 @@ pageinit(void)
 }
 
 void
-pageunchain(Page *p)
+pagechainhead(Page *p)
 {
-	if(canlock(&palloc))
-		panic("pageunchain (palloc %p)", &palloc);
-	if(p->prev)
-		p->prev->next = p->next;
-	else
-		palloc.head = p->next;
-	if(p->next)
-		p->next->prev = p->prev;
-	else
-		palloc.tail = p->prev;
-	p->prev = p->next = nil;
-	palloc.freecount--;
+	p->next = palloc.head;
+	palloc.head = p;
+	palloc.freecount++;
 }
 
-void
-pagechaintail(Page *p)
+static void
+freepages(Page *head, Page *tail, int n)
 {
-	if(canlock(&palloc))
-		panic("pagechaintail");
-	if(palloc.tail) {
-		p->prev = palloc.tail;
-		palloc.tail->next = p;
-	}
-	else {
-		palloc.head = p;
-		p->prev = 0;
-	}
-	palloc.tail = p;
-	p->next = 0;
-	palloc.freecount++;
+	lock(&palloc);
+	tail->next = palloc.head;
+	palloc.head = head;
+	palloc.freecount += n;
+	if(palloc.r.p != nil)
+		wakeup(&palloc.r);
+	unlock(&palloc);
 }
 
-void
-pagechainhead(Page *p)
+int
+pagereclaim(Image *i, int min)
 {
-	if(canlock(&palloc))
-		panic("pagechainhead");
-	if(palloc.head) {
-		p->next = palloc.head;
-		palloc.head->prev = p;
+	Page **h, **l, *p;
+	Page *fh, *ft;
+	int n;
+
+	lock(i);
+	if(i->pgref == 0){
+		unlock(i);
+		return 0;
 	}
-	else {
-		palloc.tail = p;
-		p->next = 0;
+	incref(i);
+
+	n = 0;
+	fh = ft = nil;
+	for(h = i->pghash; h < &i->pghash[PGHSIZE]; h++){
+		if((p = *h) == nil)
+			continue;
+		for(l = h; p != nil; p = p->next){
+			if(p->ref == 0)
+				break;
+			l = &p->next;
+		}
+		if(p == nil)
+			continue;
+
+		*l = p->next;
+		p->next = nil;
+		p->image = nil;
+		p->daddr = ~0;
+		i->pgref--;
+		decref(i);
+
+		if(fh == nil)
+			fh = p;
+		else
+			ft->next = p;
+		ft = p;
+		if(++n >= min)
+			break;
 	}
-	palloc.head = p;
-	p->prev = 0;
-	palloc.freecount++;
+	unlock(i);
+	putimage(i);
+
+	if(n > 0)
+		freepages(fh, ft, n);
+
+	return n;
+}
+
+int
+ispages(void*)
+{
+	return palloc.freecount >= swapalloc.highwater;
 }
 
 Page*
 newpage(int clear, Segment **s, uintptr va)
 {
-	Page *p;
+	Page *p, **l;
 	KMap *k;
 	uchar ct;
-	int i, hw, color;
+	int i, color;
 
-	lock(&palloc);
 	color = getpgcolor(va);
-	hw = swapalloc.highwater;
+	lock(&palloc);
 	for(;;) {
-		if(palloc.freecount > hw)
+		if(palloc.freecount > swapalloc.highwater)
 			break;
 		if(up->kp && palloc.freecount > 0)
 			break;
-
 		unlock(&palloc);
-		if(s)
-			qunlock(&((*s)->lk));
+		if(s != nil)
+			qunlock(*s);
 
 		if(!waserror()){
 			eqlock(&palloc.pwait);	/* Hold memory requesters here */
@@ -164,40 +179,40 @@ newpage(int clear, Segment **s, uintptr va)
 		 * a page. Fault will call newpage again when it has
 		 * reacquired the segment locks
 		 */
-		if(s){
-			*s = 0;
-			return 0;
+		if(s != nil){
+			*s = nil;
+			return nil;
 		}
 
 		lock(&palloc);
 	}
 
 	/* First try for our colour */
-	for(p = palloc.head; p; p = p->next)
+	l = &palloc.head;
+	for(p = *l; p != nil; p = p->next){
 		if(p->color == color)
 			break;
+		l = &p->next;
+	}
 
 	ct = PG_NOFLUSH;
-	if(p == 0) {
-		p = palloc.head;
+	if(p == nil) {
+		l = &palloc.head;
+		p = *l;
 		p->color = color;
 		ct = PG_NEWCOL;
 	}
 
-	pageunchain(p);
-
-	lock(p);
-	if(p->ref != 0)
-		panic("newpage: p->ref %d != 0", p->ref);
+	*l = p->next;
+	p->next = nil;
+	palloc.freecount--;
+	unlock(&palloc);
 
-	uncachepage(p);
-	p->ref++;
+	p->ref = 1;
 	p->va = va;
 	p->modref = 0;
 	for(i = 0; i < MAXMACH; i++)
 		p->cachectl[i] = ct;
-	unlock(p);
-	unlock(&palloc);
 
 	if(clear) {
 		k = kmap(p);
@@ -208,12 +223,6 @@ newpage(int clear, Segment **s, uintptr va)
 	return p;
 }
 
-int
-ispages(void*)
-{
-	return palloc.freecount >= swapalloc.highwater;
-}
-
 void
 putpage(Page *p)
 {
@@ -221,29 +230,12 @@ putpage(Page *p)
 		putswap(p);
 		return;
 	}
-
-	lock(&palloc);
-	lock(p);
-
-	if(p->ref == 0)
-		panic("putpage");
-
-	if(--p->ref > 0) {
-		unlock(p);
-		unlock(&palloc);
+	if(p->image != nil) {
+		decref(p);
 		return;
 	}
-
-	if(p->image && p->image != &swapimage)
-		pagechaintail(p);
-	else 
-		pagechainhead(p);
-
-	if(palloc.r.p != 0)
-		wakeup(&palloc.r);
-
-	unlock(p);
-	unlock(&palloc);
+	if(decref(p) == 0)
+		freepages(p, p, 1);
 }
 
 Page*
@@ -253,19 +245,15 @@ auxpage(void)
 
 	lock(&palloc);
 	p = palloc.head;
-	if(palloc.freecount < swapalloc.highwater) {
+	if(p == nil || palloc.freecount < swapalloc.highwater) {
 		unlock(&palloc);
-		return 0;
+		return nil;
 	}
-	pageunchain(p);
-
-	lock(p);
-	if(p->ref != 0)
-		panic("auxpage");
-	p->ref++;
-	uncachepage(p);
-	unlock(p);
+	palloc.head = p->next;
+	p->next = nil;
+	palloc.freecount--;
 	unlock(&palloc);
+	p->ref = 1;
 
 	return p;
 }
@@ -283,115 +271,81 @@ copypage(Page *f, Page *t)
 }
 
 void
-uncachepage(Page *p)			/* Always called with a locked page */
+cachepage(Page *p, Image *i)
 {
-	Page **l, *f;
+	Page **h;
+
+	lock(i);
+	p->image = i;
+	h = &PGHASH(i, p->daddr);
+	p->next = *h;
+	*h = p;
+	incref(i);
+	i->pgref++;
+	unlock(i);
+}
+
+void
+uncachepage(Page *p)
+{
+	Page **l, *x;
 	Image *i;
 
 	i = p->image;
-	if(i == 0)
+	if(i == nil)
 		return;
 
-	lock(&palloc.hashlock);
-	l = &pghash(p->daddr);
-	for(f = *l; f; f = f->hash) {
-		if(f == p) {
-			*l = p->hash;
-			break;
+	lock(i);
+	if(p->image != i){
+		unlock(i);
+		return;
+	}
+	l = &PGHASH(i, p->daddr);
+	for(x = *l; x != nil; x = x->next) {
+		if(x == p){
+			*l = p->next;
+			p->next = nil;
+			p->image = nil;
+			p->daddr = ~0;
+			i->pgref--;
+			unlock(i);
+			putimage(i);
+			return;
 		}
-		l = &f->hash;
+		l = &x->next;
 	}
-	unlock(&palloc.hashlock);
-	p->image = 0;
-	p->daddr = 0;
-
-	lock(i);
-	i->pgref--;
 	unlock(i);
-	putimage(i);
 }
 
-void
-cachepage(Page *p, Image *i)
+Page*
+lookpage(Image *i, uintptr daddr)
 {
-	Page **l;
-
-	/* If this ever happens it should be fixed by calling
-	 * uncachepage instead of panic. I think there is a race
-	 * with pio in which this can happen. Calling uncachepage is
-	 * correct - I just wanted to see if we got here.
-	 */
-	if(p->image)
-		panic("cachepage");
+	Page *p;
 
 	lock(i);
-	i->ref++;
-	i->pgref++;
+	for(p = PGHASH(i, daddr); p != nil; p = p->next) {
+		if(p->daddr == daddr) {
+			incref(p);
+			unlock(i);
+			return p;
+		}
+	}
 	unlock(i);
 
-	lock(&palloc.hashlock);
-	p->image = i;
-	l = &pghash(p->daddr);
-	p->hash = *l;
-	*l = p;
-	unlock(&palloc.hashlock);
+	return nil;
 }
 
 void
 cachedel(Image *i, uintptr daddr)
 {
-	Page *f;
-
-retry:
-	lock(&palloc.hashlock);
-	for(f = pghash(daddr); f; f = f->hash) {
-		if(f->image == i && f->daddr == daddr) {
-			unlock(&palloc.hashlock);
-
-			lock(f);
-			if(f->image != i || f->daddr != daddr) {
-				unlock(f);
-				goto retry;
-			}
-			uncachepage(f);
-			unlock(f);
+	Page *p;
 
-			return;
-		}
+	while((p = lookpage(i, daddr)) != nil){
+		uncachepage(p);
+		putpage(p);
 	}
-	unlock(&palloc.hashlock);
 }
 
-Page *
-lookpage(Image *i, uintptr daddr)
-{
-	Page *f;
-
-retry:
-	lock(&palloc.hashlock);
-	for(f = pghash(daddr); f; f = f->hash) {
-		if(f->image == i && f->daddr == daddr) {
-			unlock(&palloc.hashlock);
-
-			lock(&palloc);
-			lock(f);
-			if(f->image != i || f->daddr != daddr) {
-				unlock(f);
-				unlock(&palloc);
-				goto retry;
-			}
-			if(++f->ref == 1)
-				pageunchain(f);
-			unlock(&palloc);
-			unlock(f);
-
-			return f;
-		}
-	}
-	unlock(&palloc.hashlock);
-
-	return 0;
-}
 
 Pte*
 ptecpy(Pte *old)
@@ -403,14 +357,11 @@ ptecpy(Pte *old)
 	dst = &new->pages[old->first-old->pages];
 	new->first = dst;
 	for(src = old->first; src <= old->last; src++, dst++)
-		if(*src) {
+		if(*src != nil) {
 			if(onswap(*src))
 				dupswap(*src);
-			else {
-				lock(*src);
-				(*src)->ref++;
-				unlock(*src);
-			}
+			else
+				incref(*src);
 			new->last = dst;
 			*dst = *src;
 		}
@@ -432,39 +383,35 @@ ptealloc(void)
 void
 freepte(Segment *s, Pte *p)
 {
-	int ref;
 	void (*fn)(Page*);
-	Page *pt, **pg, **ptop;
+	Page **pg, **ptop;
 
 	switch(s->type&SG_TYPE) {
 	case SG_PHYSICAL:
 		fn = s->pseg->pgfree;
 		ptop = &p->pages[PTEPERTAB];
-		if(fn) {
+		if(fn != nil) {
 			for(pg = p->pages; pg < ptop; pg++) {
-				if(*pg == 0)
+				if(*pg == nil)
 					continue;
 				(*fn)(*pg);
-				*pg = 0;
+				*pg = nil;
 			}
 			break;
 		}
 		for(pg = p->pages; pg < ptop; pg++) {
-			pt = *pg;
-			if(pt == 0)
-				continue;
-			lock(pt);
-			ref = --pt->ref;
-			unlock(pt);
-			if(ref == 0)
-				free(pt);
+			if(*pg != nil) {
+				if(decref(*pg) == 0)
+					free(*pg);
+				*pg = nil;
+			}
 		}
 		break;
 	default:
 		for(pg = p->first; pg <= p->last; pg++)
-			if(*pg) {
+			if(*pg != nil) {
 				putpage(*pg);
-				*pg = 0;
+				*pg = nil;
 			}
 	}
 	free(p);
@@ -503,7 +450,7 @@ checkpagerefs(void)
 	nwrong = 0;
 	for(i=0; i<np; i++){
 		if(palloc.pages[i].ref != ref[i]){
-			iprint("page %#p ref %d actual %lud\n", 
+			iprint("page %#p ref %ld actual %lud\n", 
 				palloc.pages[i].pa, palloc.pages[i].ref, ref[i]);
 			ref[i] = 1;
 			nwrong++;