sys/src/cmd/venti/srv/icache.c

   1 #include "stdinc.h"
   2 #include "dat.h"
   3 #include "fns.h"
   4
   5 int icacheprefetch = 1;
   6
   7 typedef struct ICache ICache;
   8 typedef struct IHash IHash;
   9 typedef struct ISum ISum;
  10
  11 struct ICache
  12 {
  13         QLock   lock;
  14         Rendez  full;
  15         IHash   *hash;
  16         IEntry  *entries;
  17         int             nentries;
  18         IEntry  free;
  19         IEntry  clean;
  20         IEntry  dirty;
  21         u32int  maxdirty;
  22         u32int  ndirty;
  23         AState  as;
  24
  25         ISum    **sum;
  26         int             nsum;
  27         IHash   *shash;
  28         IEntry  *sentries;
  29         int             nsentries;
  30 };
  31
  32 static ICache icache;
  33
  34 /*
  35  * Hash table of IEntries
  36  */
  37
  38 struct IHash
  39 {
  40         int bits;
  41         u32int size;
  42         IEntry **table;
  43 };
  44
  45 static IHash*
  46 mkihash(int size1)
  47 {
  48         u32int size;
  49         int bits;
  50         IHash *ih;
  51
  52         bits = 0;
  53         size = 1;
  54         while(size < size1){
  55                 bits++;
  56                 size <<= 1;
  57         }
  58
  59         ih = vtmallocz(sizeof(IHash)+size*sizeof(ih->table[0]));
  60         ih->table = (IEntry**)(ih+1);
  61         ih->bits = bits;
  62         ih->size = size;
  63         return ih;
  64 }
  65
  66 static IEntry*
  67 ihashlookup(IHash *ih, u8int score[VtScoreSize], int type)
  68 {
  69         u32int h;
  70         IEntry *ie;
  71
  72         h = hashbits(score, ih->bits);
  73         for(ie=ih->table[h]; ie; ie=ie->nexthash)
  74                 if((type == -1 || type == ie->ia.type) && scorecmp(score, ie->score) == 0)
  75                         return ie;
  76         return nil;
  77 }
  78
  79 static void
  80 ihashdelete(IHash *ih, IEntry *ie, char *what)
  81 {
  82         u32int h;
  83         IEntry **l;
  84
  85         h = hashbits(ie->score, ih->bits);
  86         for(l=&ih->table[h]; *l; l=&(*l)->nexthash)
  87                 if(*l == ie){
  88                         *l = ie->nexthash;
  89                         return;
  90                 }
  91         fprint(2, "warning: %s %V not found in ihashdelete\n", what, ie->score);
  92 }
  93
  94 static void
  95 ihashinsert(IHash *ih, IEntry *ie)
  96 {
  97         u32int h;
  98
  99         h = hashbits(ie->score, ih->bits);
 100         ie->nexthash = ih->table[h];
 101         ih->table[h] = ie;
 102 }
 103
 104
 105 /*
 106  * IEntry lists.
 107  */
 108
 109 static IEntry*
 110 popout(IEntry *ie)
 111 {
 112         if(ie->prev == nil && ie->next == nil)
 113                 return ie;
 114         ie->prev->next = ie->next;
 115         ie->next->prev = ie->prev;
 116         ie->next = nil;
 117         ie->prev = nil;
 118         return ie;
 119 }
 120
 121 static IEntry*
 122 poplast(IEntry *list)
 123 {
 124         if(list->prev == list)
 125                 return nil;
 126         return popout(list->prev);
 127 }
 128
 129 static IEntry*
 130 pushfirst(IEntry *list, IEntry *ie)
 131 {
 132         popout(ie);
 133         ie->prev = list;
 134         ie->next = list->next;
 135         ie->prev->next = ie;
 136         ie->next->prev = ie;
 137         return ie;
 138 }
 139
 140 /*
 141  * Arena summary cache.
 142  */
 143 struct ISum
 144 {
 145         QLock   lock;
 146         IEntry  *entries;
 147         int     nentries;
 148         int     loaded;
 149         u64int addr;
 150         u64int limit;
 151         Arena *arena;
 152         int g;
 153 };
 154
 155 static ISum*
 156 scachelookup(u64int addr)
 157 {
 158         int i;
 159         ISum *s;
 160
 161         for(i=0; i<icache.nsum; i++){
 162                 s = icache.sum[i];
 163                 if(s->addr <= addr && addr < s->limit){
 164                         if(i > 0){
 165                                 memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
 166                                 icache.sum[0] = s;
 167                         }
 168                         return s;
 169                 }
 170         }
 171         return nil;
 172 }
 173
 174 static void
 175 sumclear(ISum *s)
 176 {
 177         int i;
 178
 179         for(i=0; i<s->nentries; i++)
 180                 ihashdelete(icache.shash, &s->entries[i], "scache");
 181         s->nentries = 0;
 182         s->loaded = 0;
 183         s->addr = 0;
 184         s->limit = 0;
 185         s->arena = nil;
 186         s->g = 0;
 187 }
 188
 189 static ISum*
 190 scacheevict(void)
 191 {
 192         ISum *s;
 193         int i;
 194
 195         for(i=icache.nsum-1; i>=0; i--){
 196                 s = icache.sum[i];
 197                 if(canqlock(&s->lock)){
 198                         if(i > 0){
 199                                 memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
 200                                 icache.sum[0] = s;
 201                         }
 202                         sumclear(s);
 203                         return s;
 204                 }
 205         }
 206         return nil;
 207 }
 208
 209 static void
 210 scachehit(u64int addr)
 211 {
 212         scachelookup(addr);     /* for move-to-front */
 213 }
 214
 215 static void
 216 scachesetup(ISum *s, u64int addr)
 217 {
 218         u64int addr0, limit;
 219         int g;
 220
 221         s->arena = amapitoag(mainindex, addr, &addr0, &limit, &g);
 222         s->addr = addr0;
 223         s->limit = limit;
 224         s->g = g;
 225 }
 226
 227 static void
 228 scacheload(ISum *s)
 229 {
 230         int i, n;
 231
 232         s->loaded = 1;
 233         n = asumload(s->arena, s->g, s->entries, ArenaCIGSize);
 234         /*
 235          * n can be less then ArenaCIGSize, either if the clump group
 236          * is the last in the arena and is only partially filled, or if there
 237          * are corrupt clumps in the group -- those are not returned.
 238          */
 239         for(i=0; i<n; i++){
 240                 s->entries[i].ia.addr += s->addr;
 241                 ihashinsert(icache.shash, &s->entries[i]);
 242         }
 243 //fprint(2, "%T scacheload %s %d - %d entries\n", s->arena->name, s->g, n);
 244         addstat(StatScachePrefetch, n);
 245         s->nentries = n;
 246 }
 247
 248 static ISum*
 249 scachemiss(u64int addr)
 250 {
 251         ISum *s;
 252
 253         if(!icacheprefetch)
 254                 return nil;
 255         s = scachelookup(addr);
 256         if(s == nil){
 257                 /* first time: make an entry in the cache but don't populate it yet */
 258                 s = scacheevict();
 259                 if(s == nil)
 260                         return nil;
 261                 scachesetup(s, addr);
 262                 qunlock(&s->lock);
 263                 return nil;
 264         }
 265
 266         /* second time: load from disk */
 267         qlock(&s->lock);
 268         if(s->loaded || !icacheprefetch){
 269                 qunlock(&s->lock);
 270                 return nil;
 271         }
 272
 273         return s;       /* locked */
 274 }
 275
 276 /*
 277  * Index cache.
 278  */
 279
 280 void
 281 initicache(u32int mem)
 282 {
 283         int i, entries, scache;
 284
 285         icache.full.l = &icache.lock;
 286
 287         entries = mem / (sizeof(IEntry)+sizeof(IEntry*));
 288         scache = (entries/8) / ArenaCIGSize;
 289         entries -= entries/8;
 290         if(scache < 4)
 291                 scache = 4;
 292         if(scache > 16)
 293                 scache = 16;
 294         if(entries < 1000)
 295                 entries = 1000;
 296 fprint(2, "icache %,lud bytes = %,lud entries; %lud scache\n", mem, entries, scache);
 297
 298         icache.clean.prev = icache.clean.next = &icache.clean;
 299         icache.dirty.prev = icache.dirty.next = &icache.dirty;
 300         icache.free.prev = icache.free.next = &icache.free;
 301
 302         icache.hash = mkihash(entries);
 303         icache.nentries = entries;
 304         setstat(StatIcacheSize, entries);
 305         icache.entries = vtbrk(entries*sizeof icache.entries[0]);
 306         icache.maxdirty = entries / 2;
 307         for(i=0; i<entries; i++)
 308                 pushfirst(&icache.free, &icache.entries[i]);
 309
 310         icache.nsum = scache;
 311         icache.sum = vtmallocz(scache*sizeof icache.sum[0]);
 312         icache.sum[0] = vtmallocz(scache*sizeof icache.sum[0][0]);
 313         icache.nsentries = scache * ArenaCIGSize;
 314         icache.sentries = vtmallocz(scache*ArenaCIGSize*sizeof icache.sentries[0]);
 315         icache.shash = mkihash(scache*ArenaCIGSize);
 316         for(i=0; i<scache; i++){
 317                 icache.sum[i] = icache.sum[0] + i;
 318                 icache.sum[i]->entries = icache.sentries + i*ArenaCIGSize;
 319         }
 320 }
 321
 322
 323 static IEntry*
 324 evictlru(void)
 325 {
 326         IEntry *ie;
 327
 328         ie = poplast(&icache.clean);
 329         if(ie == nil)
 330                 return nil;
 331         ihashdelete(icache.hash, ie, "evictlru");
 332         return ie;
 333 }
 334
 335 static void
 336 icacheinsert(u8int score[VtScoreSize], IAddr *ia, int state)
 337 {
 338         IEntry *ie;
 339
 340         if((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
 341                 addstat(StatIcacheStall, 1);
 342                 while((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
 343                         // Could safely return here if state == IEClean.
 344                         // But if state == IEDirty, have to wait to make
 345                         // sure we don't lose an index write.
 346                         // Let's wait all the time.
 347                         flushdcache();
 348                         kickicache();
 349                         rsleep(&icache.full);
 350                 }
 351                 addstat(StatIcacheStall, -1);
 352         }
 353
 354         memmove(ie->score, score, VtScoreSize);
 355         ie->state = state;
 356         ie->ia = *ia;
 357         if(state == IEClean){
 358                 addstat(StatIcachePrefetch, 1);
 359                 pushfirst(&icache.clean, ie);
 360         }else{
 361                 addstat(StatIcacheWrite, 1);
 362                 assert(state == IEDirty);
 363                 icache.ndirty++;
 364                 setstat(StatIcacheDirty, icache.ndirty);
 365                 delaykickicache();
 366                 pushfirst(&icache.dirty, ie);
 367         }
 368         ihashinsert(icache.hash, ie);
 369 }
 370
 371 int
 372 icachelookup(u8int score[VtScoreSize], int type, IAddr *ia)
 373 {
 374         IEntry *ie;
 375
 376         qlock(&icache.lock);
 377         addstat(StatIcacheLookup, 1);
 378         if((ie = ihashlookup(icache.hash, score, type)) != nil){
 379                 *ia = ie->ia;
 380                 if(ie->state == IEClean)
 381                         pushfirst(&icache.clean, ie);
 382                 addstat(StatIcacheHit, 1);
 383                 qunlock(&icache.lock);
 384                 return 0;
 385         }
 386
 387         if((ie = ihashlookup(icache.shash, score, type)) != nil){
 388                 *ia = ie->ia;
 389                 icacheinsert(score, &ie->ia, IEClean);
 390                 scachehit(ie->ia.addr);
 391                 addstat(StatScacheHit, 1);
 392                 qunlock(&icache.lock);
 393                 return 0;
 394         }
 395         addstat(StatIcacheMiss, 1);
 396         qunlock(&icache.lock);
 397
 398         return -1;
 399 }
 400
 401 int
 402 insertscore(u8int score[VtScoreSize], IAddr *ia, int state, AState *as)
 403 {
 404         ISum *toload;
 405
 406         qlock(&icache.lock);
 407         icacheinsert(score, ia, state);
 408         if(state == IEClean)
 409                 toload = scachemiss(ia->addr);
 410         else{
 411                 assert(state == IEDirty);
 412                 toload = nil;
 413                 if(as == nil)
 414                         fprint(2, "%T insertscore IEDirty without as; called from %#p\n",
 415                                 getcallerpc(&score));
 416                 else{
 417                         if(icache.as.aa > as->aa)
 418                                 fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa);
 419                         icache.as = *as;
 420                 }
 421         }
 422         qunlock(&icache.lock);
 423         if(toload){
 424                 scacheload(toload);
 425                 qunlock(&toload->lock);
 426         }
 427
 428         if(icache.ndirty >= icache.maxdirty)
 429                 kickicache();
 430
 431         /*
 432          * It's okay not to do this under icache.lock.
 433          * Calling insertscore only happens when we hold
 434          * the lump, meaning any searches for this block
 435          * will hit in the lump cache until after we return.
 436          */
 437         if(state == IEDirty)
 438                 markbloomfilter(mainindex->bloom, score);
 439
 440         return 0;
 441 }
 442
 443 int
 444 lookupscore(u8int score[VtScoreSize], int type, IAddr *ia)
 445 {
 446         int ms, ret;
 447         IEntry d;
 448
 449         if(icachelookup(score, type, ia) >= 0){
 450                 addstat(StatIcacheRead, 1);
 451                 return 0;
 452         }
 453
 454         ms = msec();
 455         addstat(StatIcacheFill, 1);
 456         if(loadientry(mainindex, score, type, &d) < 0)
 457                 ret = -1;
 458         else{
 459                 ret = 0;
 460                 insertscore(score, &d.ia, IEClean, nil);
 461                 *ia = d.ia;
 462         }
 463         addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms);
 464         return ret;
 465 }
 466
 467 u32int
 468 hashbits(u8int *sc, int bits)
 469 {
 470         u32int v;
 471
 472         v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
 473         if(bits < 32)
 474                  v >>= (32 - bits);
 475         return v;
 476 }
 477
 478 ulong
 479 icachedirtyfrac(void)
 480 {
 481         return (vlong)icache.ndirty*IcacheFrac / icache.nentries;
 482 }
 483
 484 /*
 485  * Return a singly-linked list of dirty index entries.
 486  * with 32-bit hash numbers between lo and hi
 487  * and address < limit.
 488  */
 489 IEntry*
 490 icachedirty(u32int lo, u32int hi, u64int limit)
 491 {
 492         u32int h;
 493         IEntry *ie, *dirty;
 494
 495         dirty = nil;
 496         trace(TraceProc, "icachedirty enter");
 497         qlock(&icache.lock);
 498         for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){
 499                 if(ie->state == IEDirty && ie->ia.addr <= limit){
 500                         h = hashbits(ie->score, 32);
 501                         if(lo <= h && h <= hi){
 502                                 ie->nextdirty = dirty;
 503                                 dirty = ie;
 504                         }
 505                 }
 506         }
 507         qunlock(&icache.lock);
 508         trace(TraceProc, "icachedirty exit");
 509         if(dirty == nil)
 510                 flushdcache();
 511         return dirty;
 512 }
 513
 514 AState
 515 icachestate(void)
 516 {
 517         AState as;
 518
 519         qlock(&icache.lock);
 520         as = icache.as;
 521         qunlock(&icache.lock);
 522         return as;
 523 }
 524
 525 /*
 526  * The singly-linked non-circular list of index entries ie
 527  * has been written to disk.  Move them to the clean list.
 528  */
 529 void
 530 icacheclean(IEntry *ie)
 531 {
 532         IEntry *next;
 533
 534         trace(TraceProc, "icacheclean enter");
 535         qlock(&icache.lock);
 536         for(; ie; ie=next){
 537                 assert(ie->state == IEDirty);
 538                 next = ie->nextdirty;
 539                 ie->nextdirty = nil;
 540                 popout(ie); /* from icache.dirty */
 541                 icache.ndirty--;
 542                 ie->state = IEClean;
 543                 pushfirst(&icache.clean, ie);
 544         }
 545         setstat(StatIcacheDirty, icache.ndirty);
 546         rwakeupall(&icache.full);
 547         qunlock(&icache.lock);
 548         trace(TraceProc, "icacheclean exit");
 549 }
 550
 551 void
 552 emptyicache(void)
 553 {
 554         int i;
 555         IEntry *ie;
 556         ISum *s;
 557
 558         qlock(&icache.lock);
 559         while((ie = evictlru()) != nil)
 560                 pushfirst(&icache.free, ie);
 561         for(i=0; i<icache.nsum; i++){
 562                 s = icache.sum[i];
 563                 qlock(&s->lock);
 564                 sumclear(s);
 565                 qunlock(&s->lock);
 566         }
 567         qunlock(&icache.lock);
 568 }
 569