123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608 |
- /*
- * This file is part of the UCB release of Plan 9. It is subject to the license
- * terms in the LICENSE file found in the top-level directory of this
- * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
- * part of the UCB release of Plan 9, including this file, may be copied,
- * modified, propagated, or distributed except according to the terms contained
- * in the LICENSE file.
- */
- #include "u.h"
- #include "../port/lib.h"
- #include "mem.h"
- #include "dat.h"
- #include "fns.h"
- enum {
- NHASH = 128,
- MAXCACHE = 1024 * 1024,
- NFILE = 4096,
- NEXTENT = 200, /* extent allocation size */
- };
- typedef struct Extent Extent;
- struct Extent {
- int bid;
- u32 start;
- int len;
- Page *cache;
- Extent *next;
- };
- typedef struct Mntcache Mntcache;
- struct Mntcache {
- Qid qid;
- u32 devno;
- Dev *dev;
- QLock QLock;
- Extent *list;
- Mntcache *hash;
- Mntcache *prev;
- Mntcache *next;
- };
- typedef struct Cache Cache;
- struct Cache {
- Lock Lock;
- int pgno;
- Mntcache *head;
- Mntcache *tail;
- Mntcache *hash[NHASH];
- };
- typedef struct Ecache Ecache;
- struct Ecache {
- Lock 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.Lock);
- e->next = ecache.head;
- ecache.head = e;
- ecache.free++;
- unlock(&ecache.Lock);
- }
- static Extent *
- extentalloc(void)
- {
- Extent *e;
- int i;
- lock(&ecache.Lock);
- if(ecache.head == nil){
- e = malloc(NEXTENT * sizeof(Extent));
- if(e == nil){
- unlock(&ecache.Lock);
- 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.Lock);
- return e;
- }
- void
- cinit(void)
- {
- int i;
- Mntcache *mc;
- if((cache.head = malloc(sizeof(Mntcache) * NFILE)) == nil)
- panic("cinit: no memory");
- mc = cache.head;
- /* a better algorithm would be nice */
- // if(conf.npage*PGSZ > 200*MB)
- // maxcache = 10*MAXCACHE;
- // if(conf.npage*PGSZ > 400*MB)
- // maxcache = 50*MAXCACHE;
- for(i = 0; i < NFILE - 1; i++){
- mc->next = mc + 1;
- mc->prev = mc - 1;
- mc++;
- }
- cache.tail = mc;
- cache.tail->next = 0;
- cache.head->prev = 0;
- fscache.notext = 1;
- }
- Page *
- cpage(Extent *e)
- {
- /* Easy consistency check */
- if(e->cache->daddr != e->bid)
- return 0;
- return lookpage(&fscache, e->bid);
- }
- void
- cnodata(Mntcache *mc)
- {
- Extent *e, *n;
- /*
- * Invalidate all extent data
- * Image lru will waste the pages
- */
- for(e = mc->list; e; e = n){
- n = e->next;
- extentfree(e);
- }
- mc->list = 0;
- }
- void
- ctail(Mntcache *mc)
- {
- /* Unlink and send to the tail */
- if(mc->prev)
- mc->prev->next = mc->next;
- else
- cache.head = mc->next;
- if(mc->next)
- mc->next->prev = mc->prev;
- else
- cache.tail = mc->prev;
- if(cache.tail){
- mc->prev = cache.tail;
- cache.tail->next = mc;
- mc->next = 0;
- cache.tail = mc;
- } else {
- cache.head = mc;
- cache.tail = mc;
- mc->prev = 0;
- mc->next = 0;
- }
- }
- void
- copen(Chan *c)
- {
- int h;
- Extent *e, *next;
- Mntcache *mc, *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.Lock);
- for(mc = cache.hash[h]; mc != nil; mc = mc->hash){
- if(mc->qid.path == c->qid.path)
- if(mc->qid.type == c->qid.type)
- if(mc->devno == c->devno && mc->dev == c->dev){
- c->mc = mc;
- ctail(mc);
- unlock(&cache.Lock);
- /* File was updated, invalidate cache */
- if(mc->qid.vers != c->qid.vers){
- mc->qid.vers = c->qid.vers;
- qlock(&mc->QLock);
- cnodata(mc);
- qunlock(&mc->QLock);
- }
- return;
- }
- }
- /* LRU the cache headers */
- mc = cache.head;
- l = &cache.hash[mc->qid.path % NHASH];
- for(f = *l; f; f = f->hash){
- if(f == mc){
- *l = mc->hash;
- break;
- }
- l = &f->hash;
- }
- mc->qid = c->qid;
- mc->devno = c->devno;
- mc->dev = c->dev;
- l = &cache.hash[h];
- mc->hash = *l;
- *l = mc;
- ctail(mc);
- qlock(&mc->QLock);
- c->mc = mc;
- e = mc->list;
- mc->list = 0;
- unlock(&cache.Lock);
- while(e){
- next = e->next;
- extentfree(e);
- e = next;
- }
- qunlock(&mc->QLock);
- }
- static int
- cdev(Mntcache *mc, Chan *c)
- {
- if(mc->qid.path != c->qid.path)
- return 0;
- if(mc->qid.type != c->qid.type)
- return 0;
- if(mc->devno != c->devno)
- return 0;
- if(mc->dev != c->dev)
- return 0;
- if(mc->qid.vers != c->qid.vers)
- return 0;
- return 1;
- }
- int
- cread(Chan *c, u8 *buf, int len, i64 off)
- {
- Proc *up = externup();
- KMap *k;
- Page *p;
- Mntcache *mc;
- Extent *e, **t;
- int o, l, total;
- u32 offset;
- if(off + len > maxcache)
- return 0;
- mc = c->mc;
- if(mc == nil)
- return 0;
- qlock(&mc->QLock);
- if(cdev(mc, c) == 0){
- qunlock(&mc->QLock);
- return 0;
- }
- offset = off;
- t = &mc->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(&mc->QLock);
- return 0;
- }
- total = 0;
- while(len){
- p = cpage(e);
- if(p == 0){
- *t = e->next;
- extentfree(e);
- qunlock(&mc->QLock);
- 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(&mc->QLock);
- nexterror();
- }
- memmove(buf, (u8 *)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(&mc->QLock);
- return total;
- }
- Extent *
- cchain(u8 *buf, u32 offset, int len, Extent **tail)
- {
- Proc *up = externup();
- 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(BIGPGSZ);
- if(p == 0){
- extentfree(e);
- break;
- }
- l = len;
- if(l > BIGPGSZ)
- l = BIGPGSZ;
- e->cache = p;
- e->start = offset;
- e->len = l;
- lock(&cache.Lock);
- e->bid = cache.pgno;
- cache.pgno += BIGPGSZ;
- /* wrap the counter; low bits are unused by pghash but checked by lookpage */
- if((cache.pgno & ~(BIGPGSZ - 1)) == 0){
- if(cache.pgno == BIGPGSZ - 1){
- print("cache wrapped\n");
- cache.pgno = 0;
- } else
- cache.pgno++;
- }
- unlock(&cache.Lock);
- 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, u8 *buf, int boff, int len)
- {
- Proc *up = externup();
- 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((u8 *)VA(k) + boff, buf, len);
- poperror();
- kunmap(k);
- putpage(p);
- return 1;
- }
- void
- cupdate(Chan *c, u8 *buf, int len, i64 off)
- {
- Mntcache *mc;
- Extent *tail;
- Extent *e, *f, *p;
- int o, ee, eblock;
- u32 offset;
- if(off > maxcache || len == 0)
- return;
- mc = c->mc;
- if(mc == nil)
- return;
- qlock(&mc->QLock);
- if(cdev(mc, c) == 0){
- qunlock(&mc->QLock);
- return;
- }
- /*
- * Find the insertion point
- */
- offset = off;
- p = 0;
- for(f = mc->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(&mc->QLock);
- return;
- }
- }
- if(p == 0) { /* at the head */
- e = cchain(buf, offset, len, &tail);
- if(e != 0){
- mc->list = e;
- tail->next = f;
- }
- qunlock(&mc->QLock);
- return;
- }
- /* trim to the predecessor */
- ee = p->start + p->len;
- if(offset < ee){
- o = ee - offset;
- len -= o;
- if(len <= 0){
- qunlock(&mc->QLock);
- return;
- }
- buf += o;
- offset += o;
- }
- /* try and pack data into the predecessor */
- if(offset == ee && p->len < BIGPGSZ){
- o = len;
- if(o > BIGPGSZ - p->len)
- o = BIGPGSZ - 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=%lu p->len=%d f->start=%lu\n", p->start, p->len, f->start);
- qunlock(&mc->QLock);
- return;
- }
- }
- }
- e = cchain(buf, offset, len, &tail);
- if(e != 0){
- p->next = e;
- tail->next = f;
- }
- qunlock(&mc->QLock);
- }
- void
- cwrite(Chan *c, u8 *buf, int len, i64 off)
- {
- int o, eo;
- Mntcache *mc;
- u32 eblock, ee;
- Extent *p, *f, *e, *tail;
- u32 offset;
- if(off > maxcache || len == 0)
- return;
- mc = c->mc;
- if(mc == nil)
- return;
- qlock(&mc->QLock);
- if(cdev(mc, c) == 0){
- qunlock(&mc->QLock);
- return;
- }
- offset = off;
- mc->qid.vers++;
- c->qid.vers++;
- p = 0;
- for(f = mc->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 < BIGPGSZ){
- o = len;
- if(o > BIGPGSZ - eo)
- o = BIGPGSZ - 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)
- mc->list = f;
- else
- p->next = f;
- qunlock(&mc->QLock);
- }
|