123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628 |
- #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
- {
- Lock;
- 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;
- /* a better algorithm would be nice */
- // if(conf.npage*BY2PG > 200*MB)
- // maxcache = 10*MAXCACHE;
- // if(conf.npage*BY2PG > 400*MB)
- // maxcache = 50*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: 0x%lux.0x%lux %d %d %s (%d %c)\n",
- s, m->qid.path, m->qid.vers, m->type, m->dev, c->name, nb, ct ? 'C' : 'N');
- for(e = m->list; e; e = e->next) {
- pprint("\t%4d %5d %4d %lux\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;
- lock(&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);
- unlock(&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;
- unlock(&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;
- 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++;
- }
- unlock(&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);
- }
|