sys/src/cmd/upas/fs/cache.c

   1 #include "common.h"
   2 #include <libsec.h>
   3 #include "dat.h"
   4
   5 int
   6 findcache(Mcache *c, Message *m)
   7 {
   8         int i;
   9
  10         for(i = 0; i < c->ntab; i++)
  11                 if(c->ctab[i] == m)
  12                         return i;
  13         return -1;
  14 }
  15
  16 static void
  17 prcache(Mcache *c, char *prefix)
  18 {
  19         int j;
  20         Message *m;
  21
  22         if(!debug)
  23                 return;
  24         for(j = 0; j < c->ntab; j++){
  25                 m = c->ctab[j];
  26                 dprint("%s%d/%s\t%p\t%d\t%ld\n", prefix, j, m->name, m, m->refs, m->csize);
  27         }
  28 }
  29
  30 /* debugging only */
  31 static void
  32 dupchk(Mcache *c)
  33 {
  34         int i, j;
  35
  36         if(!debug)
  37                 return;
  38         for(i = 0; i < c->ntab; i++)
  39                 for(j = i + 1; j < c->ntab; j++)
  40                         if(c->ctab[i] == c->ctab[j])
  41                                 goto lose;
  42         return;
  43 lose:
  44         for(j = 0; j < c->ntab; j++)
  45                 dprint("%d\t%p  %d\t%ld\n", j, c->ctab[j], c->ctab[j]->refs, c->ctab[j]->size);
  46         abort();
  47 }
  48
  49 int
  50 addcache(Mcache *c, Message *m)
  51 {
  52         int i;
  53
  54         if((i = findcache(c, m)) < 0){
  55                 if(c->ntab + 1 == nelem(c->ctab))
  56                         abort();
  57                 i = c->ntab++;
  58         }else{
  59                 /* rotate */
  60                 if(i == c->ntab - 1)
  61                         return i;               /* silly shortcut to prevent excessive printage. */
  62                 dprint("addcache rotate %d %d\n", i, c->ntab);
  63                 prcache(c, "");
  64                 memmove(c->ctab + i, c->ctab + i + 1, (c->ntab - i - 1)*sizeof c->ctab[0]);
  65                 i = c->ntab - 1;
  66 c->ctab[i] = m;
  67 dupchk(c);
  68         }
  69         dprint("addcache %d %d  %p\n", i, c->ntab, m);
  70         c->ctab[i] = m;
  71         return i;
  72 }
  73
  74 static void
  75 notecache(Mailbox *mb, Message *m, long sz)
  76 {
  77         assert(Topmsg(mb, m));
  78         assert(sz >= 0 && sz <= Maxmsg);
  79         m->csize += sz;
  80         mb->cached += sz;
  81         addcache(mb, m);
  82 }
  83
  84 static long
  85 cachefree0(Mailbox *mb, Message *m, int force)
  86 {
  87         long sz, i;
  88         Message *s;
  89
  90         if(!force && !mb->fetch)
  91                 return 0;
  92         for(s = m->part; s; s = s->next)
  93                 cachefree(mb, s, force);
  94         dprint("cachefree: %D   %p,     %p\n", m->fileid, m, m->start);
  95         if(m->mallocd){
  96                 free(m->start);
  97                 m->mallocd = 0;
  98         }
  99         if(m->ballocd){
 100                 free(m->body);
 101                 m->ballocd = 0;
 102         }
 103         if(m->hallocd){
 104                 free(m->header);
 105                 m->hallocd = 0;
 106         }
 107         for(i = 0; i < nelem(m->references); i++){
 108                 free(m->references[i]);
 109                 m->references[i] = 0;
 110         }
 111         sz = m->csize;
 112         m->csize = 0;
 113         m->start = 0;
 114         m->end = 0;
 115         m->header = 0;
 116         m->hend = 0;
 117         m->hlen = -1;
 118         m->body = 0;
 119         m->bend = 0;
 120         m->mheader = 0;
 121         m->mhend = 0;
 122         if(mb->decache)
 123                 mb->decache(mb, m);
 124         m->decoded = 0;
 125         m->converted = 0;
 126         m->badchars = 0;
 127         m->cstate &= ~(Cheader|Cbody);
 128         if(Topmsg(mb, m))
 129                 mb->cached -= sz;
 130         return sz;
 131 }
 132
 133 long
 134 cachefree(Mailbox *mb, Message *m, int force)
 135 {
 136         long sz, i;
 137
 138         sz = cachefree0(mb, m, force);
 139         for(i = 0; i < mb->ntab; i++)
 140                 if(m == mb->ctab[i]){
 141                         mb->ntab--;
 142                         memmove(mb->ctab + i, mb->ctab + i + 1, sizeof m*mb->ntab - i);
 143                         dupchk(mb);
 144                         break;
 145                 }
 146         return sz;
 147 }
 148
 149 enum{
 150         Maxntab = nelem(mbl->ctab) - 10,
 151 };
 152
 153 vlong
 154 sumcache(Mcache *c)
 155 {
 156         int i;
 157         vlong sz;
 158
 159         sz = 0;
 160         for(i = 0; i < c->ntab; i++)
 161                 sz += c->ctab[i]->csize;
 162         return sz;
 163 }
 164
 165 int
 166 scancache(Mcache *c)
 167 {
 168         int i;
 169
 170         for(i = 0; i < c->ntab; i++)
 171                 if(c->ctab[i]->csize > Maxmsg)
 172                         return -1;
 173         return 0;
 174 }
 175
 176 /* debugging only */
 177 static void
 178 chkcsize(Mailbox *mb, vlong sz, vlong sz0)
 179 {
 180         int j;
 181         Mcache *c;
 182         Message *m;
 183
 184         if(sumcache(mb) == mb->cached)
 185         if(scancache(mb) == 0)
 186                 return;
 187         eprint("sz0 %lld sz %lld sum %lld sumca %lld\n", sz0, sz, sumcache(mb), mb->cached);
 188         eprint("%lld\n", sumcache(mb));
 189         c = mb;
 190         for(j = 0; j < c->ntab; j++){
 191                 m = c->ctab[j];
 192                 eprint("%d      %p      %d      %ld     %ld\n", j, m, m->refs, m->csize, m->size);
 193         }
 194         abort();
 195 }
 196
 197 /*
 198  * strategy: start with i = 0. while cache exceeds limits,
 199  * find j so that all the [i:j] elements have refs == 0.
 200  * uncache all the [i:j], reduce ntab by i-j.  the tail
 201  * [j+1:ntab] is shifted to [i:ntab], and finally i = i+1.
 202  * we may safely skip the new i, since the condition
 203  * that stopped our scan there still holds.
 204  */
 205 void
 206 putcache(Mailbox *mb, Message *m)
 207 {
 208         int i, j, k;
 209         vlong sz, sz0;
 210         Message **p;
 211
 212         p = mb->ctab;
 213         sz0 = mb->cached;
 214         dupchk(mb);
 215         for(i = 0;; i++){
 216                 sz = mb->cached;
 217                 for(j = i;; j++){
 218                         if(j >= mb->ntab ||
 219                         sz < cachetarg && mb->ntab - (j - i) < Maxntab){
 220                                 if(j != i)
 221                                         break;
 222 chkcsize(mb, sz, sz0);
 223                                 return;
 224                         }
 225                         if(p[j]->refs > 0)
 226                                 break;
 227                         sz -= p[j]->csize;
 228                 }
 229                 if(sz == mb->cached){
 230                         if(i >= mb->ntab)
 231                                 break;
 232                         continue;
 233                 }
 234                 for(k = i; k < j; k++)
 235                         cachefree0(mb, p[k], 0);
 236                 mb->ntab -= j - i;
 237                 memmove(p + i, p + j, (mb->ntab - i)*sizeof *p);
 238         }
 239 chkcsize(mb, sz, sz0);
 240         k = 0;
 241         for(i = 0; i < mb->ntab; i++)
 242                 k += p[i]->refs > 0;
 243         if((mb->ntab > 1 || k != mb->ntab) && Topmsg(mb, m))
 244                 eprint("cache overflow: %D %llud bytes; %d entries\n",
 245                         m? m->fileid: 1ll, mb->cached, mb->ntab);
 246         if(k == mb->ntab)
 247                 return;
 248         debug = 1; prcache(mb, "");
 249         abort();
 250 }
 251
 252 static int
 253 squeeze(Message *m, uvlong o, long l, int c)
 254 {
 255         char *p, *q, *e;
 256         int n;
 257
 258         q = memchr(m->start + o, c, l);
 259         if(q == nil)
 260                 return 0;
 261         n = 0;
 262         e = m->start + o + l;
 263         for(p = q; q < e; q++){
 264                 if(*q == c){
 265                         n++;
 266                         continue;
 267                 }
 268                 *p++ = *q;
 269         }
 270         return n;
 271 }
 272
 273 void
 274 msgrealloc(Message *m, ulong l)
 275 {
 276         long l0, h0, m0, me, b0;
 277
 278         l0 = m->end - m->start;
 279         m->mallocd = 1;
 280         h0 = m->hend - m->start;
 281         m0 = m->mheader - m->start;
 282         me = m->mhend - m->start;
 283         b0 = m->body - m->start;
 284         assert(h0 >= 0 && m0 >= 0 && me >= 0 && b0 >= 0);
 285         m->start = erealloc(m->start, l + 1);
 286         m->rbody = m->start + b0;
 287         m->rbend = m->end = m->start + l0;
 288         if(!m->hallocd){
 289                 m->header = m->start;
 290                 m->hend = m->start + h0;
 291         }
 292         if(!m->ballocd){
 293                 m->body = m->start + b0;
 294                 m->bend = m->start + l0;
 295         }
 296         m->mheader = m->start + m0;
 297         m->mhend = m->start + me;
 298 }
 299
 300 /*
 301  * the way we squeeze out bad characters is exceptionally sneaky.
 302  */
 303 static int
 304 fetch(Mailbox *mb, Message *m, uvlong o, ulong l)
 305 {
 306         int expand;
 307         long l0, n, sz0;
 308
 309 top:
 310         l0 = m->end - m->start;
 311         assert(l0 >= 0);
 312         dprint("fetch %lud sz %lud o %llud l %lud badchars %d\n", l0, m->size, o, l, m->badchars);
 313         if(l0 == m->size || o > m->size)
 314                 return 0;
 315         expand = 0;
 316         if(o + l > m->size)
 317                 l = m->size - o;
 318         if(o + l == m->size)
 319                 l += m->ibadchars - m->badchars;
 320         if(o + l > l0){
 321                 expand = 1;
 322                 msgrealloc(m, o + m->badchars + l);
 323         }
 324         assert(l0 <= o);
 325         sz0 = m->size;
 326         if(mb->fetch(mb, m, o + m->badchars, l) == -1){
 327                 logmsg(m, "can't fetch %D %llud %lud", m->fileid, o, l);
 328                 m->deleted = Dead;
 329                 return -1;
 330         }
 331         if(m->size - sz0)
 332                 l += m->size - sz0;     /* awful botch for gmail */
 333         if(expand){
 334                 /* grumble.  poor planning. */
 335                 if(m->badchars > 0)
 336                         memmove(m->start + o, m->start + o + m->badchars, l);
 337                 n = squeeze(m, o, l, 0);
 338                 n += squeeze(m, o, l - n, '\r');
 339                 if(n > 0){
 340                         if(m->ibadchars == 0)
 341                                 dprint("   %ld more badchars\n", n);
 342                         l -= n;
 343                         m->badchars += n;
 344                         msgrealloc(m, o + l);
 345                 }
 346                 notecache(mb, m, l);
 347                 m->bend = m->rbend = m->end = m->start + o + l;
 348                 if(n)
 349                 if(o + l + n == m->size && m->cstate&Cidx){
 350                         dprint("   redux %llud %ld\n", o + l, n);
 351                         o += l;
 352                         l = n;
 353                         goto top;
 354                 }
 355         }else
 356                 eprint("unhandled case in fetch\n");
 357         *m->end = 0;
 358         return 0;
 359 }
 360
 361 void
 362 cachehash(Mailbox *mb, Message *m)
 363 {
 364         if(m->whole == m->whole->whole)
 365                 henter(PATH(mb->id, Qmbox), m->name,
 366                         (Qid){PATH(m->id, Qdir), 0, QTDIR}, m, mb);
 367         else
 368                 henter(PATH(m->whole->id, Qdir), m->name,
 369                         (Qid){PATH(m->id, Qdir), 0, QTDIR}, m, mb);
 370         henter(PATH(m->id, Qdir), "xxx",
 371                 (Qid){PATH(m->id, Qmax), 0, QTFILE}, m, mb);    /* sleezy speedup */
 372 }
 373
 374 void
 375 newcachehash(Mailbox *mb, Message *m, int doplumb)
 376 {
 377         if(doplumb)
 378                 mailplumb(mb, m, 0);
 379         else
 380                 if(insurecache(mb, m) == 0)
 381                         msgdecref(mb, m);
 382         /* avoid cachehash on error? */
 383         cachehash(mb, m);
 384 }
 385
 386 static char *itab[] = {
 387         "idx",
 388         "stale",
 389         "header",
 390         "body"
 391 };
 392
 393 char*
 394 cstate(Message *m)
 395 {
 396         char *p, *e;
 397         int i, s;
 398         static char buf[64];
 399
 400         s = m->cstate;
 401         p = e = buf;
 402         e += sizeof buf;
 403         for(i = 0; i < 8; i++)
 404                 if(s & 1<<i)
 405                 if(i < nelem(itab))
 406                         p = seprint(p, e, "%s ", itab[i]);
 407         if(p > buf)
 408                 p--;
 409         p[0] = 0;
 410         return buf;
 411 }
 412
 413
 414 static int
 415 middlecache(Mailbox *mb, Message *m)
 416 {
 417         int y;
 418
 419         y = 0;
 420         while(!Topmsg(mb, m)){
 421                 m = m->whole;
 422                 if((m->cstate & Cbody) == 0)
 423                         y = 1;
 424         }
 425         if(y == 0)
 426                 return 0;
 427         dprint("middlecache %d [%D] %lud %lud\n", m->id, m->fileid, m->end - m->start, m->size);
 428         return cachebody(mb, m);
 429 }
 430
 431 int
 432 cacheheaders(Mailbox *mb, Message *m)
 433 {
 434         char *p, *e;
 435         int r;
 436         ulong o;
 437
 438         if(!mb->fetch || m->cstate&Cheader)
 439                 return 0;
 440         if(!Topmsg(mb, m))
 441                 return middlecache(mb, m);
 442         dprint("cacheheaders %d %D\n", m->id, m->fileid);
 443         if(m->size < 10000)
 444                 r = fetch(mb, m, 0, m->size);
 445         else for(r = 0; (o = m->end - m->start) < m->size; ){
 446                 if((r = fetch(mb, m, o, 4096)) < 0)
 447                         break;
 448                 p = m->start + o;
 449                 if(o)
 450                         p--;
 451                 for(e = m->end - 2; p < e; p++){
 452                         p = memchr(p, '\n', e - p);
 453                         if(p == nil)
 454                                 break;
 455                         if(p[1] == '\n' || (p[1] == '\r' && p[2] == '\n'))
 456                                 goto found;
 457                 }
 458         }
 459         if(r < 0)
 460                 return -1;
 461 found:
 462         parseheaders(mb, m, mb->addfrom, 0);
 463         return 0;
 464 }
 465
 466 void
 467 digestmessage(Mailbox *mb, Message *m)
 468 {
 469         assert(m->digest == 0);
 470         m->digest = emalloc(SHA1dlen);
 471         sha1((uchar*)m->start, m->end - m->start, m->digest, nil);
 472         if(mtreeisdup(mb, m)){
 473                 logmsg(m, "dup detected");
 474                 m->deleted = Dup;       /* no dups allowed */
 475         }else
 476                 mtreeadd(mb, m);
 477         dprint("%d %#A\n", m->id, m->digest);
 478 }
 479
 480 int
 481 cachebody(Mailbox *mb, Message *m)
 482 {
 483         ulong o;
 484
 485         while(!Topmsg(mb, m))
 486                 m = m->whole;
 487         if(!mb->fetch || m->cstate&Cbody)
 488                 return 0;
 489         o = m->end - m->start;
 490         dprint("cachebody %d [%D] %lud %lud %s\n", m->id, m->fileid, o, m->size, cstate(m));
 491         if(o < m->size)
 492         if(fetch(mb, m, o, m->size - o) < 0)
 493                 return -1;
 494         if((m->cstate&Cidx) == 0){
 495                 assert(m->ibadchars == 0);
 496                 if(m->badchars > 0)
 497                         dprint("reducing size %ld %ld\n", m->size, m->size - m->badchars);
 498                 m->size -= m->badchars;         /* sneaky */
 499                 m->ibadchars = m->badchars;
 500         }
 501         if(m->digest == 0)
 502                 digestmessage(mb, m);
 503         if(m->lines == 0)
 504                 m->lines = countlines(m);
 505         parse(mb, m, mb->addfrom, 0);
 506         dprint("  →%s\n", cstate(m));
 507         return 0;
 508 }
 509
 510 int
 511 cacheidx(Mailbox *mb, Message *m)
 512 {
 513         if(m->cstate & Cidx)
 514                 return 0;
 515         if(cachebody(mb, m) == -1)
 516                 return -1;
 517         m->cstate |= Cidxstale|Cidx;
 518         return 0;
 519 }
 520
 521 static int
 522 countparts(Message *m)
 523 {
 524         Message *p;
 525
 526         if(m->nparts == 0)
 527                 for(p = m->part; p; p = p->next){
 528                         countparts(p);
 529                         m->nparts++;
 530                 }
 531         return m->nparts;
 532 }
 533
 534 int
 535 insurecache(Mailbox *mb, Message *m)
 536 {
 537         if(m->deleted || !m->inmbox)
 538                 return -1;
 539         msgincref(m);
 540         cacheidx(mb, m);
 541         if((m->cstate & Cidx) == 0){
 542                 logmsg(m, "%s: can't cache: %s: %r", mb->path, m->name);
 543                 msgdecref(mb, m);
 544                 return -1;
 545         }
 546         if(m->digest == 0)
 547                 sysfatal("digest?");
 548         countparts(m);
 549         return 0;
 550 }