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 s = scachelookup(addr); 254 if(s == nil){ 255 /* first time: make an entry in the cache but don't populate it yet */ 256 s = scacheevict(); 257 if(s == nil) 258 return nil; 259 scachesetup(s, addr); 260 qunlock(&s->lock); 261 return nil; 262 } 263 264 /* second time: load from disk */ 265 qlock(&s->lock); 266 if(s->loaded || !icacheprefetch){ 267 qunlock(&s->lock); 268 return nil; 269 } 270 271 return s; /* locked */ 272 } 273 274 /* 275 * Index cache. 276 */ 277 278 void 279 initicache(u32int mem0) 280 { 281 u32int mem; 282 int i, entries, scache; 283 284 icache.full.l = &icache.lock; 285 286 mem = mem0; 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 %,d bytes = %,d entries; %d scache\n", mem0, 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 = vtmallocz(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 %lux\n", getcallerpc(&score)); 415 else{ 416 if(icache.as.aa > as->aa) 417 fprint(2, "%T insertscore: aa moving backward: %#llux -> %#llux\n", icache.as.aa, as->aa); 418 icache.as = *as; 419 } 420 } 421 qunlock(&icache.lock); 422 if(toload){ 423 scacheload(toload); 424 qunlock(&toload->lock); 425 } 426 427 if(icache.ndirty >= icache.maxdirty) 428 kickicache(); 429 430 /* 431 * It's okay not to do this under icache.lock. 432 * Calling insertscore only happens when we hold 433 * the lump, meaning any searches for this block 434 * will hit in the lump cache until after we return. 435 */ 436 if(state == IEDirty) 437 markbloomfilter(mainindex->bloom, score); 438 439 return 0; 440 } 441 442 static int 443 lookupscore_untimed(u8int score[VtScoreSize], int type, IAddr *ia) 444 { 445 IEntry d; 446 447 if(icachelookup(score, type, ia) >= 0) 448 return 0; 449 450 addstat(StatIcacheFill, 1); 451 if(loadientry(mainindex, score, type, &d) < 0) 452 return -1; 453 454 insertscore(score, &d.ia, IEClean, nil); 455 *ia = d.ia; 456 return 0; 457 } 458 459 int 460 lookupscore(u8int score[VtScoreSize], int type, IAddr *ia) 461 { 462 int ms, ret; 463 464 ms = msec(); 465 ret = lookupscore_untimed(score, type, ia); 466 ms = msec() - ms; 467 addstat2(StatIcacheRead, 1, StatIcacheReadTime, ms); 468 return ret; 469 } 470 471 u32int 472 hashbits(u8int *sc, int bits) 473 { 474 u32int v; 475 476 v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3]; 477 if(bits < 32) 478 v >>= (32 - bits); 479 return v; 480 } 481 482 ulong 483 icachedirtyfrac(void) 484 { 485 return (vlong)icache.ndirty*IcacheFrac / icache.nentries; 486 } 487 488 /* 489 * Return a singly-linked list of dirty index entries. 490 * with 32-bit hash numbers between lo and hi 491 * and address < limit. 492 */ 493 IEntry* 494 icachedirty(u32int lo, u32int hi, u64int limit) 495 { 496 u32int h; 497 IEntry *ie, *dirty; 498 499 dirty = nil; 500 trace(TraceProc, "icachedirty enter"); 501 qlock(&icache.lock); 502 for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){ 503 if(ie->state == IEDirty && ie->ia.addr < limit){ 504 h = hashbits(ie->score, 32); 505 if(lo <= h && h <= hi){ 506 ie->nextdirty = dirty; 507 dirty = ie; 508 } 509 } 510 } 511 qunlock(&icache.lock); 512 trace(TraceProc, "icachedirty exit"); 513 if(dirty == nil) 514 flushdcache(); 515 return dirty; 516 } 517 518 AState 519 icachestate(void) 520 { 521 AState as; 522 523 qlock(&icache.lock); 524 as = icache.as; 525 qunlock(&icache.lock); 526 return as; 527 } 528 529 /* 530 * The singly-linked non-circular list of index entries ie 531 * has been written to disk. Move them to the clean list. 532 */ 533 void 534 icacheclean(IEntry *ie) 535 { 536 IEntry *next; 537 538 trace(TraceProc, "icacheclean enter"); 539 qlock(&icache.lock); 540 for(; ie; ie=next){ 541 assert(ie->state == IEDirty); 542 next = ie->nextdirty; 543 ie->nextdirty = nil; 544 popout(ie); /* from icache.dirty */ 545 icache.ndirty--; 546 ie->state = IEClean; 547 pushfirst(&icache.clean, ie); 548 } 549 setstat(StatIcacheDirty, icache.ndirty); 550 rwakeupall(&icache.full); 551 qunlock(&icache.lock); 552 trace(TraceProc, "icacheclean exit"); 553 } 554 555 void 556 emptyicache(void) 557 { 558 int i; 559 IEntry *ie; 560 ISum *s; 561 562 qlock(&icache.lock); 563 while((ie = evictlru()) != nil) 564 pushfirst(&icache.free, ie); 565 for(i=0; i<icache.nsum; i++){ 566 s = icache.sum[i]; 567 qlock(&s->lock); 568 sumclear(s); 569 qunlock(&s->lock); 570 } 571 qunlock(&icache.lock); 572 } 573 574