2003/0406/port/cache.c (diff list | history)

port/cache.c on 1993/1011
1993/1011		#include "u.h" #include "../port/lib.h" #include "mem.h" #include "dat.h" #include "fns.h" #include "../port/error.h"
1993/1014		enum { NHASH = 128, MAXCACHE = 1024*1024, NFILE = 4096,
1999/0508		NEXTENT = 200, /* extent allocation size */
1993/1014		}; typedef struct Extent Extent;
1993/1013		struct Extent
1993/1011		{
1993/1013		int bid; ulong start; int len;
1993/1014		Page *cache;
1993/1013		Extent *next; }; typedef struct Mntcache Mntcache; struct Mntcache {
2001/0527		Qid qid;
1993/1013		int dev; int type;
1993/1014		QLock;
1993/1013		Extent *list; Mntcache *hash; Mntcache *prev; Mntcache *next;
1993/1011		};
1993/1013		typedef struct Cache Cache; struct Cache
1993/1011		{
1993/1017		Lock; int pgno;
1993/1013		Mntcache *head; Mntcache *tail; Mntcache *hash[NHASH];
1993/1011		};
1999/0508		typedef struct Ecache Ecache; struct Ecache { Lock; int total; int free; Extent* head; }; static Image fscache; static Cache cache; static Ecache ecache;
1999/0903		static int maxcache = MAXCACHE;
1999/0508		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.free += NEXTENT; ecache.total += NEXTENT; } e = ecache.head; ecache.head = e->next; memset(e, 0, sizeof(Extent)); ecache.free--; unlock(&ecache); return e; }
1993/1014		void cinit(void) { int i; Mntcache *m; cache.head = xalloc(sizeof(Mntcache)*NFILE); m = cache.head;
1998/0512
2000/0609		/* a better algorithm would be nice */
2001/0530		// if(conf.npage*BY2PG > 200*MB) // maxcache = 10*MAXCACHE; // if(conf.npage*BY2PG > 400*MB) // maxcache = 50*MAXCACHE;
1999/0903
1993/1016		for(i = 0; i < NFILE-1; i++) {
1993/1014		m->next = m+1; m->prev = m-1; m++; } cache.tail = m; cache.tail->next = 0; cache.head->prev = 0;
1994/0817		fscache.notext = 1;
1993/1014		}
1993/1013		void
1993/1017		cprint(Chan *c, Mntcache *m, char *s)
1993/1014		{
1993/1018		ulong o; int nb, ct;
1993/1014		Extent *e;
1993/1028
1993/1018		nb = 0; ct = 1;
1993/1103		o = 0;
1993/1018		if(m->list) o = m->list->start; for(e = m->list; e; e = e->next) { nb += e->len; if(o != e->start) ct = 0; o = e->start+e->len; } pprint("%s: 0x%lux.0x%lux %d %d %s (%d %c)\n",
2001/0527		s, m->qid.path, m->qid.vers, m->type, m->dev, c->name, nb, ct ? 'C' : 'N');
1993/1014
1993/1018		for(e = m->list; e; e = e->next) {
1993/1103		pprint("\t%4d %5d %4d %lux\n",
1993/1014		e->bid, e->start, e->len, e->cache);
1993/1018		}
1993/1014		} Page* cpage(Extent *e) { /* Easy consistency check */ if(e->cache->daddr != e->bid) return 0; return lookpage(&fscache, e->bid); } void
1993/1013		cnodata(Mntcache *m) { Extent *e, *n; /* * Invalidate all extent data * Image lru will waste the pages */ for(e = m->list; e; e = n) {
1993/1014		n = e->next;
1999/0508		extentfree(e);
1993/1013		}
1993/1015		m->list = 0;
1993/1013		} void
1993/1016		ctail(Mntcache *m)
1993/1013		{ /* Unlink and send to the tail */
1998/0512		if(m->prev)
1993/1013		m->prev->next = m->next; else cache.head = m->next; if(m->next) m->next->prev = m->prev; else cache.tail = m->prev; if(cache.tail) { m->prev = cache.tail; cache.tail->next = m; m->next = 0; cache.tail = m; } else {
1993/1018		cache.head = m; cache.tail = m; m->prev = 0; m->next = 0;
1993/1013		} } void copen(Chan *c) {
1993/1018		int h; Extent *e, *next;
1993/1013		Mntcache *m, *f, **l;
2001/0527		/* directories aren't cacheable and append-only files confuse us */ if(c->qid.type&(QTDIR|QTAPPEND))
1993/1015		return;
1993/1018		h = c->qid.path%NHASH;
1993/1016		lock(&cache);
1993/1018		for(m = cache.hash[h]; m; m = m->hash) {
2001/0527		if(m->qid.path == c->qid.path) if(m->qid.type == c->qid.type)
1993/1016		if(m->dev == c->dev && m->type == c->type) { c->mcp = m; ctail(m); unlock(&cache);
1993/1015
1993/1016		/* File was updated, invalidate cache */
2001/0527		if(m->qid.vers != c->qid.vers) { m->qid.vers = c->qid.vers;
1993/1016		qlock(m); cnodata(m); qunlock(m); } return;
1993/1015		}
1993/1013		} /* LRU the cache headers */ m = cache.head;
2001/0527		l = &cache.hash[m->qid.path%NHASH];
1993/1016		for(f = *l; f; f = f->hash) {
1993/1013		if(f == m) {
1993/1018		*l = m->hash;
1993/1013		break; }
1993/1016		l = &f->hash;
1993/1013		}
1993/1015
2001/0527		m->qid = c->qid;
1993/1013		m->dev = c->dev; m->type = c->type;
1993/1018		l = &cache.hash[h]; m->hash = *l; *l = m; ctail(m);
1997/0327		qlock(m);
1993/1013		c->mcp = m;
1993/1018		e = m->list; m->list = 0;
1993/1016		unlock(&cache);
1993/1018		while(e) { next = e->next;
1999/0508		extentfree(e);
1993/1018		e = next; }
1997/0327		qunlock(m);
1993/1013		} static int cdev(Mntcache *m, Chan *c) {
2001/0527		if(m->qid.path != c->qid.path)
1993/1013		return 0;
2001/0527		if(m->qid.type != c->qid.type) return 0;
1993/1013		if(m->dev != c->dev) return 0; if(m->type != c->type) return 0;
2001/0527		if(m->qid.vers != c->qid.vers)
1993/1018		return 0;
1993/1013		return 1; } int
1998/0327		cread(Chan *c, uchar *buf, int len, vlong off)
1993/1013		{ KMap *k; Page *p; Mntcache *m;
1993/1014		Extent *e, **t;
1993/1017		int o, l, total;
1998/0327		ulong offset;
1993/1013
1999/0903		if(off+len > maxcache)
1998/0327		return 0;
1993/1013		m = c->mcp; if(m == 0) return 0;
1993/1015
1993/1013		qlock(m); if(cdev(m, c) == 0) { qunlock(m); return 0; }
1998/0327		offset = off;
1993/1014		t = &m->list; for(e = *t; e; e = e->next) {
1993/1018		if(offset >= e->start && offset < e->start+e->len)
1993/1013		break;
1993/1014		t = &e->next;
1993/1013		} if(e == 0) { qunlock(m); return 0; } total = 0; while(len) {
1993/1014		p = cpage(e);
1993/1013		if(p == 0) {
1993/1014		*t = e->next;
1999/0508		extentfree(e);
1993/1013		qunlock(m); return total; }
1994/0728		o = offset - e->start; l = len; if(l > e->len-o) l = e->len-o;
1993/1013		k = kmap(p); if(waserror()) { kunmap(k); putpage(p); qunlock(m); nexterror(); }
1993/1014		memmove(buf, (uchar*)VA(k) + o, l);
1993/1016		poperror();
1993/1013		kunmap(k);
1994/0728
1993/1013		putpage(p); buf += l; len -= l; offset += l; total += l;
1993/1014		t = &e->next;
1993/1013		e = e->next; if(e == 0 || e->start != offset) break; }
1993/1018
1993/1014		qunlock(m);
1993/1013		return total; }
1993/1014		Extent* cchain(uchar *buf, ulong offset, int len, Extent **tail) { int l; Page *p; KMap *k; Extent *e, *start, **t; start = 0;
1993/1016		*tail = 0;
1993/1014		t = &start; while(len) {
1999/0508		e = extentalloc();
1993/1014		if(e == 0) break; p = auxpage(); if(p == 0) {
1999/0508		extentfree(e);
1993/1014		break; } l = len; if(l > BY2PG) l = BY2PG;
1993/1015		e->cache = p; e->start = offset; e->len = l;
1993/1018
1993/1017		lock(&cache); e->bid = cache.pgno; cache.pgno += BY2PG;
1999/1101		/* wrap the counter; low bits are unused by pghash but checked by lookpage */
1999/1022		if((cache.pgno & ~(BY2PG-1)) == 0){ if(cache.pgno == BY2PG-1){ print("cache wrapped\n"); cache.pgno = 0; }else cache.pgno++; }
1993/1017		unlock(&cache);
1993/1018
1993/1014		p->daddr = e->bid; k = kmap(p);
1994/0728		if(waserror()) { /* buf may be virtual */ kunmap(k); nexterror(); }
1993/1014		memmove((void*)VA(k), buf, l);
1994/0728		poperror();
1993/1014		kunmap(k); cachepage(p, &fscache); putpage(p); buf += l; offset += l; len -= l; *t = e; *tail = e; t = &e->next; }
1993/1016
1993/1014		return start; } int cpgmove(Extent *e, uchar *buf, int boff, int len) { Page *p; KMap *k; p = cpage(e); if(p == 0) return 0;
1993/1015
1993/1014		k = kmap(p);
1994/0728		if(waserror()) { /* Since buf may be virtual */ kunmap(k); nexterror(); }
1993/1014		memmove((uchar*)VA(k)+boff, buf, len);
1994/0728		poperror();
1993/1014		kunmap(k); putpage(p); return 1; }
1993/1013		void
1998/0327		cupdate(Chan *c, uchar *buf, int len, vlong off)
1993/1013		{ Mntcache *m;
1993/1014		Extent *tail; Extent *e, *f, *p;
1993/1015		int o, ee, eblock;
1998/0327		ulong offset;
1993/1013
1999/0903		if(off > maxcache || len == 0)
1993/1015		return;
1993/1013		m = c->mcp; if(m == 0) return; qlock(m); if(cdev(m, c) == 0) { qunlock(m); return; }
1993/1014		/* * Find the insertion point */
1998/0327		offset = off;
1993/1014		p = 0; for(f = m->list; f; f = f->next) {
1999/1227		if(f->start > offset)
1993/1014		break; p = f; }
1993/1015
1999/1227		/* trim if there is a successor */ eblock = offset+len; if(f != 0 && eblock > f->start) { len -= (eblock - f->start); if(len <= 0) { qunlock(m); return;
1993/1014		}
1999/1227		} if(p == 0) { /* at the head */
1993/1014		e = cchain(buf, offset, len, &tail);
1993/1016		if(e != 0) { m->list = e;
1999/1227		tail->next = f;
1993/1016		}
1993/1014		qunlock(m); return; } /* trim to the predecessor */ ee = p->start+p->len; if(offset < ee) { o = ee - offset; len -= o; if(len <= 0) { qunlock(m);
1993/1013		return;
1993/1014		} 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;
1993/1015		if(cpgmove(p, buf, p->len, o)) { p->len += o;
1993/1014		buf += o; len -= o; offset += o; if(len <= 0) {
2003/0406		if(f && p->start + p->len > f->start) print("CACHE: p->start=%uld p->len=%d f->start=%uld\n", p->start, p->len, f->start);
1993/1014		qunlock(m); return; } }
1993/1013		}
1993/1014
1999/1227		e = cchain(buf, offset, len, &tail); if(e != 0) { p->next = e;
1993/1014		tail->next = f;
1999/1227		}
1993/1014		qunlock(m);
1993/1015		} void
1998/0327		cwrite(Chan* c, uchar *buf, int len, vlong off)
1993/1015		{
1999/1227		int o, eo;
1993/1015		Mntcache *m; ulong eblock, ee; Extent *p, *f, *e, *tail;
1998/0327		ulong offset;
1993/1015
1999/0903		if(off > maxcache || len == 0)
1993/1015		return; m = c->mcp; if(m == 0) return; qlock(m); if(cdev(m, c) == 0) { qunlock(m); return; }
1998/0327		offset = off;
2001/0527		m->qid.vers++;
1993/1017		c->qid.vers++;
1993/1015		p = 0; for(f = m->list; f; f = f->next) {
1993/1017		if(f->start >= offset)
1993/1015		break;
1998/0512		p = f;
1996/0326		}
1993/1015		if(p != 0) { ee = p->start+p->len;
1999/1227		eo = offset - p->start; /* pack in predecessor if there is space */ if(offset <= ee && eo < BY2PG) {
1993/1017		o = len;
1999/1227		if(o > BY2PG - eo) o = BY2PG - eo; if(cpgmove(p, buf, eo, o)) { if(eo+o > p->len) p->len = eo+o;
1993/1017		buf += o; len -= o; offset += o; } }
1993/1015		}
1999/1227		/* free the overlap -- it's a rare case */
1993/1015		eblock = offset+len; while(f && f->start < eblock) { e = f->next;
1999/0508		extentfree(f);
1993/1015		f = e; }
1999/1227		/* link the block (if any) into the middle */
1993/1015		e = cchain(buf, offset, len, &tail);
1993/1016		if(e != 0) {
1999/1227		tail->next = f; f = e;
1993/1016		}
1999/1227		if(p == 0) m->list = f; else p->next = f;
1993/1015		qunlock(m);
1993/1011		}