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

   1 #include "stdinc.h"
   2 #include "dat.h"
   3 #include "fns.h"
   4
   5 /* #define CHECK(x)     x */
   6 #define CHECK(x)
   7
   8 typedef struct LumpCache        LumpCache;
   9
  10 enum
  11 {
  12         HashLog         = 9,
  13         HashSize        = 1<<HashLog,
  14         HashMask        = HashSize - 1,
  15 };
  16
  17 struct LumpCache
  18 {
  19         QLock           lock;
  20         Rendez          full;
  21         Lump            *free;                  /* list of available lumps */
  22         u32int          allowed;                /* total allowable space for packets */
  23         u32int          avail;                  /* remaining space for packets */
  24         u32int          now;                    /* ticks for usage timestamps */
  25         Lump            **heads;                /* hash table for finding address */
  26         int             nheap;                  /* number of available victims */
  27         Lump            **heap;                 /* heap for locating victims */
  28         int             nblocks;                /* number of blocks allocated */
  29         Lump            *blocks;                /* array of block descriptors */
  30 };
  31
  32 static LumpCache        lumpcache;
  33
  34 static void     delheap(Lump *db);
  35 static int      downheap(int i, Lump *b);
  36 static void     fixheap(int i, Lump *b);
  37 static int      upheap(int i, Lump *b);
  38 static Lump     *bumplump(void);
  39
  40 void
  41 initlumpcache(u32int size, u32int nblocks)
  42 {
  43         Lump *last, *b;
  44         int i;
  45
  46         lumpcache.full.l = &lumpcache.lock;
  47         lumpcache.nblocks = nblocks;
  48         lumpcache.allowed = size;
  49         lumpcache.avail = size;
  50         lumpcache.heads = MKNZ(Lump*, HashSize);
  51         lumpcache.heap = MKNZ(Lump*, nblocks);
  52         lumpcache.blocks = MKNZ(Lump, nblocks);
  53         setstat(StatLcacheSize, lumpcache.nblocks);
  54
  55         last = nil;
  56         for(i = 0; i < nblocks; i++){
  57                 b = &lumpcache.blocks[i];
  58                 b->type = TWID8;
  59                 b->heap = TWID32;
  60                 b->next = last;
  61                 last = b;
  62         }
  63         lumpcache.free = last;
  64         lumpcache.nheap = 0;
  65 }
  66
  67 Lump*
  68 lookuplump(u8int *score, int type)
  69 {
  70         uint ms;
  71         Lump *b;
  72         u32int h;
  73
  74         ms = 0;
  75         trace(TraceLump, "lookuplump enter");
  76
  77         h = hashbits(score, HashLog);
  78
  79         /*
  80          * look for the block in the cache
  81          */
  82         qlock(&lumpcache.lock);
  83         CHECK(checklumpcache());
  84 again:
  85         for(b = lumpcache.heads[h]; b != nil; b = b->next){
  86                 if(scorecmp(score, b->score)==0 && type == b->type){
  87                         addstat(StatLcacheHit, 1);
  88                         trace(TraceLump, "lookuplump hit");
  89                         goto found;
  90                 }
  91         }
  92
  93         trace(TraceLump, "lookuplump miss");
  94
  95         /*
  96          * missed: locate the block with the oldest second to last use.
  97          * remove it from the heap, and fix up the heap.
  98          */
  99         while(lumpcache.free == nil){
 100                 trace(TraceLump, "lookuplump bump");
 101                 CHECK(checklumpcache());
 102                 if(bumplump() == nil){
 103                         CHECK(checklumpcache());
 104                         logerr(EAdmin, "all lump cache blocks in use");
 105                         addstat(StatLcacheStall, 1);
 106                         CHECK(checklumpcache());
 107                         rsleep(&lumpcache.full);
 108                         CHECK(checklumpcache());
 109                         addstat(StatLcacheStall, -1);
 110                         goto again;
 111                 }
 112                 CHECK(checklumpcache());
 113         }
 114
 115         /* start timer on cache miss to avoid system call on cache hit */
 116         ms = msec();
 117
 118         addstat(StatLcacheMiss, 1);
 119         b = lumpcache.free;
 120         lumpcache.free = b->next;
 121
 122         /*
 123          * the new block has no last use, so assume it happens sometime in the middle
 124 ZZZ this is not reasonable
 125          */
 126         b->used = (b->used2 + lumpcache.now) / 2;
 127
 128         /*
 129          * rechain the block on the correct hash chain
 130          */
 131         b->next = lumpcache.heads[h];
 132         lumpcache.heads[h] = b;
 133         if(b->next != nil)
 134                 b->next->prev = b;
 135         b->prev = nil;
 136
 137         scorecp(b->score, score);
 138         b->type = type;
 139         b->size = 0;
 140         b->data = nil;
 141
 142 found:
 143         b->ref++;
 144         b->used2 = b->used;
 145         b->used = lumpcache.now++;
 146         if(b->heap != TWID32)
 147                 fixheap(b->heap, b);
 148         CHECK(checklumpcache());
 149         qunlock(&lumpcache.lock);
 150
 151
 152         addstat(StatLumpStall, 1);
 153         qlock(&b->lock);
 154         addstat(StatLumpStall, -1);
 155
 156         trace(TraceLump, "lookuplump exit");
 157         addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0);
 158         return b;
 159 }
 160
 161 void
 162 insertlump(Lump *b, Packet *p)
 163 {
 164         u32int size;
 165
 166         /*
 167          * look for the block in the cache
 168          */
 169         trace(TraceLump, "insertlump enter");
 170         qlock(&lumpcache.lock);
 171         CHECK(checklumpcache());
 172 again:
 173
 174         addstat(StatLcacheWrite, 1);
 175
 176         /*
 177          * missed: locate the block with the oldest second to last use.
 178          * remove it from the heap, and fix up the heap.
 179          */
 180         size = packetasize(p);
 181         while(lumpcache.avail < size){
 182                 trace(TraceLump, "insertlump bump");
 183                 CHECK(checklumpcache());
 184                 if(bumplump() == nil){
 185                         logerr(EAdmin, "all lump cache blocks in use");
 186                         addstat(StatLcacheStall, 1);
 187                         CHECK(checklumpcache());
 188                         rsleep(&lumpcache.full);
 189                         CHECK(checklumpcache());
 190                         addstat(StatLcacheStall, -1);
 191                         goto again;
 192                 }
 193                 CHECK(checklumpcache());
 194         }
 195         b->data = p;
 196         b->size = size;
 197         lumpcache.avail -= size;
 198         CHECK(checklumpcache());
 199         qunlock(&lumpcache.lock);
 200         trace(TraceLump, "insertlump exit");
 201 }
 202
 203 void
 204 putlump(Lump *b)
 205 {
 206         if(b == nil)
 207                 return;
 208
 209         trace(TraceLump, "putlump");
 210         qunlock(&b->lock);
 211         qlock(&lumpcache.lock);
 212         CHECK(checklumpcache());
 213         if(--b->ref == 0){
 214                 if(b->heap == TWID32)
 215                         upheap(lumpcache.nheap++, b);
 216                 trace(TraceLump, "putlump wakeup");
 217                 rwakeupall(&lumpcache.full);
 218         }
 219         CHECK(checklumpcache());
 220         qunlock(&lumpcache.lock);
 221 }
 222
 223 /*
 224  * remove some lump from use and update the free list and counters
 225  */
 226 static Lump*
 227 bumplump(void)
 228 {
 229         Lump *b;
 230         u32int h;
 231
 232         /*
 233          * remove blocks until we find one that is unused
 234          * referenced blocks are left in the heap even though
 235          * they can't be scavenged; this is simple a speed optimization
 236          */
 237         CHECK(checklumpcache());
 238         for(;;){
 239                 if(lumpcache.nheap == 0){
 240                         trace(TraceLump, "bumplump emptyheap");
 241                         return nil;
 242                 }
 243                 b = lumpcache.heap[0];
 244                 delheap(b);
 245                 if(!b->ref){
 246                         trace(TraceLump, "bumplump wakeup");
 247                         rwakeupall(&lumpcache.full);
 248                         break;
 249                 }
 250         }
 251
 252         /*
 253          * unchain the block
 254          */
 255         trace(TraceLump, "bumplump unchain");
 256         if(b->prev == nil){
 257                 h = hashbits(b->score, HashLog);
 258                 if(lumpcache.heads[h] != b)
 259                         sysfatal("bad hash chains in lump cache");
 260                 lumpcache.heads[h] = b->next;
 261         }else
 262                 b->prev->next = b->next;
 263         if(b->next != nil)
 264                 b->next->prev = b->prev;
 265
 266         if(b->data != nil){
 267                 packetfree(b->data);
 268                 b->data = nil;
 269                 lumpcache.avail += b->size;
 270                 b->size = 0;
 271         }
 272         b->type = TWID8;
 273
 274         b->next = lumpcache.free;
 275         lumpcache.free = b;
 276
 277         CHECK(checklumpcache());
 278         trace(TraceLump, "bumplump exit");
 279         return b;
 280 }
 281
 282 void
 283 emptylumpcache(void)
 284 {
 285         qlock(&lumpcache.lock);
 286         while(bumplump())
 287                 ;
 288         qunlock(&lumpcache.lock);
 289 }
 290
 291 /*
 292  * delete an arbitrary block from the heap
 293  */
 294 static void
 295 delheap(Lump *db)
 296 {
 297         fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
 298         db->heap = TWID32;
 299 }
 300
 301 /*
 302  * push an element up or down to it's correct new location
 303  */
 304 static void
 305 fixheap(int i, Lump *b)
 306 {
 307         if(upheap(i, b) == i)
 308                 downheap(i, b);
 309 }
 310
 311 static int
 312 upheap(int i, Lump *b)
 313 {
 314         Lump *bb;
 315         u32int now;
 316         int p;
 317
 318         now = lumpcache.now;
 319         for(; i != 0; i = p){
 320                 p = (i - 1) >> 1;
 321                 bb = lumpcache.heap[p];
 322                 if(b->used2 - now >= bb->used2 - now)
 323                         break;
 324                 lumpcache.heap[i] = bb;
 325                 bb->heap = i;
 326         }
 327
 328         lumpcache.heap[i] = b;
 329         b->heap = i;
 330         return i;
 331 }
 332
 333 static int
 334 downheap(int i, Lump *b)
 335 {
 336         Lump *bb;
 337         u32int now;
 338         int k;
 339
 340         now = lumpcache.now;
 341         for(; ; i = k){
 342                 k = (i << 1) + 1;
 343                 if(k >= lumpcache.nheap)
 344                         break;
 345                 if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
 346                         k++;
 347                 bb = lumpcache.heap[k];
 348                 if(b->used2 - now <= bb->used2 - now)
 349                         break;
 350                 lumpcache.heap[i] = bb;
 351                 bb->heap = i;
 352         }
 353
 354         lumpcache.heap[i] = b;
 355         b->heap = i;
 356         return i;
 357 }
 358
 359 static void
 360 findblock(Lump *bb)
 361 {
 362         Lump *b, *last;
 363         int h;
 364
 365         last = nil;
 366         h = hashbits(bb->score, HashLog);
 367         for(b = lumpcache.heads[h]; b != nil; b = b->next){
 368                 if(last != b->prev)
 369                         sysfatal("bad prev link");
 370                 if(b == bb)
 371                         return;
 372                 last = b;
 373         }
 374         sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
 375 }
 376
 377 void
 378 checklumpcache(void)
 379 {
 380         Lump *b;
 381         u32int size, now, nfree;
 382         int i, k, refed;
 383
 384         now = lumpcache.now;
 385         for(i = 0; i < lumpcache.nheap; i++){
 386                 if(lumpcache.heap[i]->heap != i)
 387                         sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
 388                 if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
 389                         sysfatal("lc: bad heap ordering");
 390                 k = (i << 1) + 1;
 391                 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
 392                         sysfatal("lc: bad heap ordering");
 393                 k++;
 394                 if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
 395                         sysfatal("lc: bad heap ordering");
 396         }
 397
 398         refed = 0;
 399         size = 0;
 400         for(i = 0; i < lumpcache.nblocks; i++){
 401                 b = &lumpcache.blocks[i];
 402                 if(b->data == nil && b->size != 0)
 403                         sysfatal("bad size: %d data=%p", b->size, b->data);
 404                 if(b->ref && b->heap == TWID32)
 405                         refed++;
 406                 if(b->type != TWID8){
 407                         findblock(b);
 408                         size += b->size;
 409                 }
 410                 if(b->heap != TWID32
 411                 && lumpcache.heap[b->heap] != b)
 412                         sysfatal("lc: spurious heap value");
 413         }
 414         if(lumpcache.avail != lumpcache.allowed - size){
 415                 fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
 416                 *(int*)0=0;
 417         }
 418
 419         nfree = 0;
 420         for(b = lumpcache.free; b != nil; b = b->next){
 421                 if(b->type != TWID8 || b->heap != TWID32)
 422                         sysfatal("lc: bad free list");
 423                 nfree++;
 424         }
 425
 426         if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
 427                 sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
 428 }
 429