ref: e09c2b721b7d4f0d0750c3338dd227d4bc3a95c5
parent: 1c8b5de992131cc255b18781b5da528220392c6b
author: cinap_lenrek <cinap_lenrek@felloff.net>
date: Wed Sep 13 19:24:10 EDT 2017
upas/fs: replace fixed cache table with lru linked list the cachetab just keeps track of recent messages that have not been called cachefree() on. under some conditions, the fixed table could overflow (all messages having refs > 0). with a linked list, overflow becomes non fatal and the algorithm is simpler to implement.
--- a/sys/src/cmd/upas/fs/cache.c
+++ b/sys/src/cmd/upas/fs/cache.c
@@ -2,76 +2,26 @@
#include <libsec.h>
#include "dat.h"
-int
-findcache(Mcache *c, Message *m)
-{- int i;
-
- for(i = 0; i < c->ntab; i++)
- if(c->ctab[i] == m)
- return i;
- return -1;
-}
-
static void
-prcache(Mcache *c, char *prefix)
+addlru(Mcache *c, Message *m)
{- int j;
- Message *m;
+ Message *l, **ll;
- if(!debug)
- return;
- for(j = 0; j < c->ntab; j++){- m = c->ctab[j];
- dprint("%s%d/%s\t%p\t%d\t%ld\n", prefix, j, m->name, m, m->refs, m->csize);+ c->nlru++;
+ ll = &c->lru;
+ while((l = *ll) != nil){+ if(l == m){+ c->nlru--;
+ *ll = m->lru;
+ } else {+ ll = &l->lru;
+ }
}
+ m->lru = nil;
+ *ll = m;
}
-/* debugging only */
static void
-dupchk(Mcache *c)
-{- int i, j;
-
- if(!debug)
- return;
- for(i = 0; i < c->ntab; i++)
- for(j = i + 1; j < c->ntab; j++)
- if(c->ctab[i] == c->ctab[j])
- goto lose;
- return;
-lose:
- for(j = 0; j < c->ntab; j++)
- dprint("%d\t%p %d\t%ld\n", j, c->ctab[j], c->ctab[j]->refs, c->ctab[j]->size);- abort();
-}
-
-int
-addcache(Mcache *c, Message *m)
-{- int i;
-
- if((i = findcache(c, m)) < 0){- if(c->ntab + 1 == nelem(c->ctab))
- abort();
- i = c->ntab++;
- }else{- /* rotate */
- if(i == c->ntab - 1)
- return i; /* silly shortcut to prevent excessive printage. */
- dprint("addcache rotate %d %d\n", i, c->ntab);- prcache(c, "");
- memmove(c->ctab + i, c->ctab + i + 1, (c->ntab - i - 1)*sizeof c->ctab[0]);
- i = c->ntab - 1;
-c->ctab[i] = m;
-dupchk(c);
- }
- dprint("addcache %d %d %p\n", i, c->ntab, m);- c->ctab[i] = m;
- return i;
-}
-
-static void
notecache(Mailbox *mb, Message *m, long sz)
{assert(Topmsg(mb, m));
@@ -78,17 +28,17 @@
assert(sz >= 0 && sz <= Maxmsg);
m->csize += sz;
mb->cached += sz;
- addcache(mb, m);
+ addlru(mb, m);
}
-static long
+static void
cachefree0(Mailbox *mb, Message *m, int force)
{long sz, i;
Message *s;
- if(!force && !mb->fetch)
- return 0;
+ if(!force && mb->fetch == nil)
+ return;
for(s = m->part; s; s = s->next)
cachefree(mb, s, force);
dprint("cachefree: %D %p, %p\n", m->fileid, m, m->start);@@ -127,126 +77,39 @@
m->cstate &= ~(Cheader|Cbody);
if(Topmsg(mb, m))
mb->cached -= sz;
- return sz;
}
-long
+void
cachefree(Mailbox *mb, Message *m, int force)
{- long sz, i;
+ Message **ll;
- sz = cachefree0(mb, m, force);
- for(i = 0; i < mb->ntab; i++)
- if(m == mb->ctab[i]){- mb->ntab--;
- memmove(mb->ctab + i, mb->ctab + i + 1, sizeof m*mb->ntab - i);
- dupchk(mb);
+ for(ll = &mb->lru; *ll != nil; ll = &((*ll)->lru)){+ if(*ll == m){+ mb->nlru--;
+ *ll = m->lru;
+ m->lru = nil;
break;
}
- return sz;
-}
-
-enum{- Maxntab = nelem(mbl->ctab) - 10,
-};
-
-vlong
-sumcache(Mcache *c)
-{- int i;
- vlong sz;
-
- sz = 0;
- for(i = 0; i < c->ntab; i++)
- sz += c->ctab[i]->csize;
- return sz;
-}
-
-int
-scancache(Mcache *c)
-{- int i;
-
- for(i = 0; i < c->ntab; i++)
- if(c->ctab[i]->csize > Maxmsg)
- return -1;
- return 0;
-}
-
-/* debugging only */
-static void
-chkcsize(Mailbox *mb, vlong sz, vlong sz0)
-{- int j;
- Mcache *c;
- Message *m;
-
- if(sumcache(mb) == mb->cached)
- if(scancache(mb) == 0)
- return;
- eprint("sz0 %lld sz %lld sum %lld sumca %lld\n", sz0, sz, sumcache(mb), mb->cached);- eprint("%lld\n", sumcache(mb));- c = mb;
- for(j = 0; j < c->ntab; j++){- m = c->ctab[j];
- eprint("%d %p %d %ld %ld\n", j, m, m->refs, m->csize, m->size);}
- abort();
+ cachefree0(mb, m, force);
}
-/*
- * strategy: start with i = 0. while cache exceeds limits,
- * find j so that all the [i:j] elements have refs == 0.
- * uncache all the [i:j], reduce ntab by i-j. the tail
- * [j+1:ntab] is shifted to [i:ntab], and finally i = i+1.
- * we may safely skip the new i, since the condition
- * that stopped our scan there still holds.
- */
void
putcache(Mailbox *mb, Message *m)
{- int i, j, k;
- vlong sz, sz0;
- Message **p;
+ int n;
- p = mb->ctab;
- sz0 = mb->cached;
- dupchk(mb);
- for(i = 0;; i++){- sz = mb->cached;
- for(j = i;; j++){- if(j >= mb->ntab ||
- sz < cachetarg && mb->ntab - (j - i) < Maxntab){- if(j != i)
- break;
-chkcsize(mb, sz, sz0);
+ addlru(mb, m);
+ while(mb->lru != nil && (mb->cached > cachetarg || mb->nlru > 10)){+ n = 0;
+ while(mb->lru->refs > 0){+ if(++n >= mb->nlru)
return;
- }
- if(p[j]->refs > 0)
- break;
- sz -= p[j]->csize;
+ addlru(mb, mb->lru);
}
- if(sz == mb->cached){- if(i >= mb->ntab)
- break;
- continue;
- }
- for(k = i; k < j; k++)
- cachefree0(mb, p[k], 0);
- mb->ntab -= j - i;
- memmove(p + i, p + j, (mb->ntab - i)*sizeof *p);
+ cachefree(mb, mb->lru, 0);
}
-chkcsize(mb, sz, sz0);
- k = 0;
- for(i = 0; i < mb->ntab; i++)
- k += p[i]->refs > 0;
- if((mb->ntab > 1 || k != mb->ntab) && Topmsg(mb, m))
- eprint("cache overflow: %D %llud bytes; %d entries\n", - m? m->fileid: 1ll, mb->cached, mb->ntab);
- if(k == mb->ntab)
- return;
- debug = 1; prcache(mb, "");
- abort();
}
static int
--- a/sys/src/cmd/upas/fs/dat.h
+++ b/sys/src/cmd/upas/fs/dat.h
@@ -127,6 +127,7 @@
Message *next;
Message *part;
Message *whole;
+ Message *lru; /* least recently use chain */
union{char *lim; /* used by plan9; not compatable with cache */
@@ -143,8 +144,8 @@
typedef struct Mcache Mcache;
struct Mcache {uvlong cached;
- int ntab;
- Message *ctab[Nctab];
+ int nlru;
+ Message *lru;
};
typedef struct Mailbox Mailbox;
@@ -206,7 +207,7 @@
/**/
void putcache(Mailbox*, Message*); /* asymmetricial */
-long cachefree(Mailbox*, Message*, int);
+void cachefree(Mailbox*, Message*, int);
Message* gettopmsg(Mailbox*, Message*);
char* syncmbox(Mailbox*, int);
--- a/sys/src/cmd/upas/fs/mbox.c
+++ b/sys/src/cmd/upas/fs/mbox.c
@@ -92,7 +92,8 @@
m->cstate &= ~Cnew;
if(m->cstate & Cnew){ if(insurecache(mb, m) == 0){- mailplumb(mb, m);
+ if(doplumb)
+ mailplumb(mb, m);
msgdecref(mb, m);
}
m->cstate &= ~Cnew;