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 mem0)
 282 {
 283         u32int mem;
 284         int i, entries, scache;
 285
 286         icache.full.l = &icache.lock;
 287
 288         mem = mem0;
 289         entries = mem / (sizeof(IEntry)+sizeof(IEntry*));
 290         scache = (entries/8) / ArenaCIGSize;
 291         entries -= entries/8;
 292         if(scache < 4)
 293                 scache = 4;
 294         if(scache > 16)
 295                 scache = 16;
 296         if(entries < 1000)
 297                 entries = 1000;
 298 fprint(2, "icache %,d bytes = %,d entries; %d scache\n", mem0, entries, scache);
 299
 300         icache.clean.prev = icache.clean.next = &icache.clean;
 301         icache.dirty.prev = icache.dirty.next = &icache.dirty;
 302         icache.free.prev = icache.free.next = &icache.free;
 303
 304         icache.hash = mkihash(entries);
 305         icache.nentries = entries;
 306         setstat(StatIcacheSize, entries);
 307         icache.entries = vtmallocz(entries*sizeof icache.entries[0]);
 308         icache.maxdirty = entries / 2;
 309         for(i=0; i<entries; i++)
 310                 pushfirst(&icache.free, &icache.entries[i]);
 311
 312         icache.nsum = scache;
 313         icache.sum = vtmallocz(scache*sizeof icache.sum[0]);
 314         icache.sum[0] = vtmallocz(scache*sizeof icache.sum[0][0]);
 315         icache.nsentries = scache * ArenaCIGSize;
 316         icache.sentries = vtmallocz(scache*ArenaCIGSize*sizeof icache.sentries[0]);
 317         icache.shash = mkihash(scache*ArenaCIGSize);
 318         for(i=0; i<scache; i++){
 319                 icache.sum[i] = icache.sum[0] + i;
 320                 icache.sum[i]->entries = icache.sentries + i*ArenaCIGSize;
 321         }
 322 }
 323
 324
 325 static IEntry*
 326 evictlru(void)
 327 {
 328         IEntry *ie;
 329
 330         ie = poplast(&icache.clean);
 331         if(ie == nil)
 332                 return nil;
 333         ihashdelete(icache.hash, ie, "evictlru");
 334         return ie;
 335 }
 336
 337 static void
 338 icacheinsert(u8int score[VtScoreSize], IAddr *ia, int state)
 339 {
 340         IEntry *ie;
 341
 342         if((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
 343                 addstat(StatIcacheStall, 1);
 344                 while((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
 345                         // Could safely return here if state == IEClean.
 346                         // But if state == IEDirty, have to wait to make
 347                         // sure we don't lose an index write.
 348                         // Let's wait all the time.
 349                         flushdcache();
 350                         kickicache();
 351                         rsleep(&icache.full);
 352                 }
 353                 addstat(StatIcacheStall, -1);
 354         }
 355
 356         memmove(ie->score, score, VtScoreSize);
 357         ie->state = state;
 358         ie->ia = *ia;
 359         if(state == IEClean){
 360                 addstat(StatIcachePrefetch, 1);
 361                 pushfirst(&icache.clean, ie);
 362         }else{
 363                 addstat(StatIcacheWrite, 1);
 364                 assert(state == IEDirty);
 365                 icache.ndirty++;
 366                 setstat(StatIcacheDirty, icache.ndirty);
 367                 delaykickicache();
 368                 pushfirst(&icache.dirty, ie);
 369         }
 370         ihashinsert(icache.hash, ie);
 371 }
 372
 373 int
 374 icachelookup(u8int score[VtScoreSize], int type, IAddr *ia)
 375 {
 376         IEntry *ie;
 377
 378         qlock(&icache.lock);
 379         addstat(StatIcacheLookup, 1);
 380         if((ie = ihashlookup(icache.hash, score, type)) != nil){
 381                 *ia = ie->ia;
 382                 if(ie->state == IEClean)
 383                         pushfirst(&icache.clean, ie);
 384                 addstat(StatIcacheHit, 1);
 385                 qunlock(&icache.lock);
 386                 return 0;
 387         }
 388
 389         if((ie = ihashlookup(icache.shash, score, type)) != nil){
 390                 *ia = ie->ia;
 391                 icacheinsert(score, &ie->ia, IEClean);
 392                 scachehit(ie->ia.addr);
 393                 addstat(StatScacheHit, 1);
 394                 qunlock(&icache.lock);
 395                 return 0;
 396         }
 397         addstat(StatIcacheMiss, 1);
 398         qunlock(&icache.lock);
 399
 400         return -1;
 401 }
 402
 403 int
 404 insertscore(u8int score[VtScoreSize], IAddr *ia, int state, AState *as)
 405 {
 406         ISum *toload;
 407
 408         qlock(&icache.lock);
 409         icacheinsert(score, ia, state);
 410         if(state == IEClean)
 411                 toload = scachemiss(ia->addr);
 412         else{
 413                 assert(state == IEDirty);
 414                 toload = nil;
 415                 if(as == nil)
 416                         fprint(2, "%T insertscore IEDirty without as; called from %#p\n",
 417                                 getcallerpc(&score));
 418                 else{
 419                         if(icache.as.aa > as->aa)
 420                                 fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa);
 421                         icache.as = *as;
 422                 }
 423         }
 424         qunlock(&icache.lock);
 425         if(toload){
 426                 scacheload(toload);
 427                 qunlock(&toload->lock);
 428         }
 429
 430         if(icache.ndirty >= icache.maxdirty)
 431                 kickicache();
 432
 433         /*
 434          * It's okay not to do this under icache.lock.
 435          * Calling insertscore only happens when we hold
 436          * the lump, meaning any searches for this block
 437          * will hit in the lump cache until after we return.
 438          */
 439         if(state == IEDirty)
 440                 markbloomfilter(mainindex->bloom, score);
 441
 442         return 0;
 443 }
 444
 445 int
 446 lookupscore(u8int score[VtScoreSize], int type, IAddr *ia)
 447 {
 448         int ms, ret;
 449         IEntry d;
 450
 451         if(icachelookup(score, type, ia) >= 0){
 452                 addstat(StatIcacheRead, 1);
 453                 return 0;
 454         }
 455
 456         ms = msec();
 457         addstat(StatIcacheFill, 1);
 458         if(loadientry(mainindex, score, type, &d) < 0)
 459                 ret = -1;
 460         else{
 461                 ret = 0;
 462                 insertscore(score, &d.ia, IEClean, nil);
 463                 *ia = d.ia;
 464         }
 465         addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms);
 466         return ret;
 467 }
 468
 469 u32int
 470 hashbits(u8int *sc, int bits)
 471 {
 472         u32int v;
 473
 474         v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
 475         if(bits < 32)
 476                  v >>= (32 - bits);
 477         return v;
 478 }
 479
 480 ulong
 481 icachedirtyfrac(void)
 482 {
 483         return (vlong)icache.ndirty*IcacheFrac / icache.nentries;
 484 }
 485
 486 /*
 487  * Return a singly-linked list of dirty index entries.
 488  * with 32-bit hash numbers between lo and hi
 489  * and address < limit.
 490  */
 491 IEntry*
 492 icachedirty(u32int lo, u32int hi, u64int limit)
 493 {
 494         u32int h;
 495         IEntry *ie, *dirty;
 496
 497         dirty = nil;
 498         trace(TraceProc, "icachedirty enter");
 499         qlock(&icache.lock);
 500         for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){
 501                 if(ie->state == IEDirty && ie->ia.addr <= limit){
 502                         h = hashbits(ie->score, 32);
 503                         if(lo <= h && h <= hi){
 504                                 ie->nextdirty = dirty;
 505                                 dirty = ie;
 506                         }
 507                 }
 508         }
 509         qunlock(&icache.lock);
 510         trace(TraceProc, "icachedirty exit");
 511         if(dirty == nil)
 512                 flushdcache();
 513         return dirty;
 514 }
 515
 516 AState
 517 icachestate(void)
 518 {
 519         AState as;
 520
 521         qlock(&icache.lock);
 522         as = icache.as;
 523         qunlock(&icache.lock);
 524         return as;
 525 }
 526
 527 /*
 528  * The singly-linked non-circular list of index entries ie
 529  * has been written to disk.  Move them to the clean list.
 530  */
 531 void
 532 icacheclean(IEntry *ie)
 533 {
 534         IEntry *next;
 535
 536         trace(TraceProc, "icacheclean enter");
 537         qlock(&icache.lock);
 538         for(; ie; ie=next){
 539                 assert(ie->state == IEDirty);
 540                 next = ie->nextdirty;
 541                 ie->nextdirty = nil;
 542                 popout(ie); /* from icache.dirty */
 543                 icache.ndirty--;
 544                 ie->state = IEClean;
 545                 pushfirst(&icache.clean, ie);
 546         }
 547         setstat(StatIcacheDirty, icache.ndirty);
 548         rwakeupall(&icache.full);
 549         qunlock(&icache.lock);
 550         trace(TraceProc, "icacheclean exit");
 551 }
 552
 553 void
 554 emptyicache(void)
 555 {
 556         int i;
 557         IEntry *ie;
 558         ISum *s;
 559
 560         qlock(&icache.lock);
 561         while((ie = evictlru()) != nil)
 562                 pushfirst(&icache.free, ie);
 563         for(i=0; i<icache.nsum; i++){
 564                 s = icache.sum[i];
 565                 qlock(&s->lock);
 566                 sumclear(s);
 567                 qunlock(&s->lock);
 568         }
 569         qunlock(&icache.lock);
 570 }
 571