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 572