Blame | Last modification | View Log | RSS feed
#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"
#include "../port/error.h"
enum
{
NHASH = 128,
MAXCACHE = 1024*1024,
NFILE = 4096,
NEXTENT = 200, /* extent allocation size */
};
typedef struct Extent Extent;
struct Extent
{
int bid;
ulong start;
int len;
Page *cache;
Extent *next;
};
typedef struct Mntcache Mntcache;
struct Mntcache
{
Qid qid;
int dev;
int type;
QLock;
Extent *list;
Mntcache *hash;
Mntcache *prev;
Mntcache *next;
};
typedef struct Cache Cache;
struct Cache
{
QLock;
int pgno;
Mntcache *head;
Mntcache *tail;
Mntcache *hash[NHASH];
};
typedef struct Ecache Ecache;
struct Ecache
{
Lock;
int total;
int free;
Extent* head;
};
static Image fscache;
static Cache cache;
static Ecache ecache;
static int 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.free += NEXTENT;
ecache.total += NEXTENT;
}
e = ecache.head;
ecache.head = e->next;
memset(e, 0, sizeof(Extent));
ecache.free--;
unlock(&ecache);
return e;
}
void
cinit(void)
{
int i;
Mntcache *m;
cache.head = xalloc(sizeof(Mntcache)*NFILE);
m = cache.head;
if (m == nil)
panic("cinit: no memory");
/* a better algorithm would be nice */
if(conf.npage*BY2PG > 400*MB)
maxcache = 20*MAXCACHE;
else if(conf.npage*BY2PG > 200*MB)
maxcache = 10*MAXCACHE;
for(i = 0; i < NFILE-1; i++) {
m->next = m+1;
m->prev = m-1;
m++;
}
cache.tail = m;
cache.tail->next = 0;
cache.head->prev = 0;
fscache.notext = 1;
}
void
cprint(Chan *c, Mntcache *m, char *s)
{
ulong o;
int nb, ct;
Extent *e;
nb = 0;
ct = 1;
o = 0;
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: %#llux.%#lux %d %d %s (%d %c)\n",
s, m->qid.path, m->qid.vers, m->type, m->dev, c->path->s, nb, ct ? 'C' : 'N');
for(e = m->list; e; e = e->next) {
pprint("\t%4d %5lud %4d %#p\n",
e->bid, e->start, e->len, e->cache);
}
}
Page*
cpage(Extent *e)
{
/* Easy consistency check */
if(e->cache->daddr != e->bid)
return 0;
return lookpage(&fscache, e->bid);
}
void
cnodata(Mntcache *m)
{
Extent *e, *n;
/*
* Invalidate all extent data
* Image lru will waste the pages
*/
for(e = m->list; e; e = n) {
n = e->next;
extentfree(e);
}
m->list = 0;
}
void
ctail(Mntcache *m)
{
/* Unlink and send to the tail */
if(m->prev)
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 {
cache.head = m;
cache.tail = m;
m->prev = 0;
m->next = 0;
}
}
void
copen(Chan *c)
{
int h;
Extent *e, *next;
Mntcache *m, *f, **l;
/* directories aren't cacheable and append-only files confuse us */
if(c->qid.type&(QTDIR|QTAPPEND))
return;
h = c->qid.path%NHASH;
qlock(&cache);
for(m = cache.hash[h]; m; m = m->hash) {
if(m->qid.path == c->qid.path)
if(m->qid.type == c->qid.type)
if(m->dev == c->dev && m->type == c->type) {
c->mcp = m;
ctail(m);
qunlock(&cache);
/* File was updated, invalidate cache */
if(m->qid.vers != c->qid.vers) {
m->qid.vers = c->qid.vers;
qlock(m);
cnodata(m);
qunlock(m);
}
return;
}
}
/* LRU the cache headers */
m = cache.head;
l = &cache.hash[m->qid.path%NHASH];
for(f = *l; f; f = f->hash) {
if(f == m) {
*l = m->hash;
break;
}
l = &f->hash;
}
m->qid = c->qid;
m->dev = c->dev;
m->type = c->type;
l = &cache.hash[h];
m->hash = *l;
*l = m;
ctail(m);
qlock(m);
c->mcp = m;
e = m->list;
m->list = 0;
qunlock(&cache);
while(e) {
next = e->next;
extentfree(e);
e = next;
}
qunlock(m);
}
static int
cdev(Mntcache *m, Chan *c)
{
if(m->qid.path != c->qid.path)
return 0;
if(m->qid.type != c->qid.type)
return 0;
if(m->dev != c->dev)
return 0;
if(m->type != c->type)
return 0;
if(m->qid.vers != c->qid.vers)
return 0;
return 1;
}
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;
if(off+len > maxcache)
return 0;
m = c->mcp;
if(m == 0)
return 0;
qlock(m);
if(cdev(m, c) == 0) {
qunlock(m);
return 0;
}
offset = off;
t = &m->list;
for(e = *t; e; e = e->next) {
if(offset >= e->start && offset < e->start+e->len)
break;
t = &e->next;
}
if(e == 0) {
qunlock(m);
return 0;
}
total = 0;
while(len) {
p = cpage(e);
if(p == 0) {
*t = e->next;
extentfree(e);
qunlock(m);
return total;
}
o = offset - e->start;
l = len;
if(l > e->len-o)
l = e->len-o;
k = kmap(p);
if(waserror()) {
kunmap(k);
putpage(p);
qunlock(m);
nexterror();
}
memmove(buf, (uchar*)VA(k) + o, l);
poperror();
kunmap(k);
putpage(p);
buf += l;
len -= l;
offset += l;
total += l;
t = &e->next;
e = e->next;
if(e == 0 || e->start != offset)
break;
}
qunlock(m);
return total;
}
Extent*
cchain(uchar *buf, ulong offset, int len, Extent **tail)
{
int l;
Page *p;
KMap *k;
Extent *e, *start, **t;
start = 0;
*tail = 0;
t = &start;
while(len) {
e = extentalloc();
if(e == 0)
break;
p = auxpage();
if(p == 0) {
extentfree(e);
break;
}
l = len;
if(l > BY2PG)
l = BY2PG;
e->cache = p;
e->start = offset;
e->len = l;
qlock(&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++;
}
qunlock(&cache);
p->daddr = e->bid;
k = kmap(p);
if(waserror()) { /* buf may be virtual */
kunmap(k);
nexterror();
}
memmove((void*)VA(k), buf, l);
poperror();
kunmap(k);
cachepage(p, &fscache);
putpage(p);
buf += l;
offset += l;
len -= l;
*t = e;
*tail = e;
t = &e->next;
}
return start;
}
int
cpgmove(Extent *e, uchar *buf, int boff, int len)
{
Page *p;
KMap *k;
p = cpage(e);
if(p == 0)
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)
{
Mntcache *m;
Extent *tail;
Extent *e, *f, *p;
int o, ee, eblock;
ulong offset;
if(off > maxcache || len == 0)
return;
m = c->mcp;
if(m == 0)
return;
qlock(m);
if(cdev(m, c) == 0) {
qunlock(m);
return;
}
/*
* Find the insertion point
*/
offset = off;
p = 0;
for(f = m->list; f; f = f->next) {
if(f->start > offset)
break;
p = f;
}
/* 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;
}
}
if(p == 0) { /* at the head */
e = cchain(buf, offset, len, &tail);
if(e != 0) {
m->list = e;
tail->next = f;
}
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);
return;
}
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 && p->start + p->len > f->start) print("CACHE: p->start=%uld p->len=%d f->start=%uld\n", p->start, p->len, f->start);
qunlock(m);
return;
}
}
}
e = cchain(buf, offset, len, &tail);
if(e != 0) {
p->next = e;
tail->next = f;
}
qunlock(m);
}
void
cwrite(Chan* c, uchar *buf, int len, vlong off)
{
int o, eo;
Mntcache *m;
ulong eblock, ee;
Extent *p, *f, *e, *tail;
ulong offset;
if(off > maxcache || len == 0)
return;
m = c->mcp;
if(m == 0)
return;
qlock(m);
if(cdev(m, c) == 0) {
qunlock(m);
return;
}
offset = off;
m->qid.vers++;
c->qid.vers++;
p = 0;
for(f = m->list; f; f = f->next) {
if(f->start >= offset)
break;
p = f;
}
if(p != 0) {
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 && 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 != 0) {
tail->next = f;
f = e;
}
if(p == 0)
m->list = f;
else
p->next = f;
qunlock(m);
}