ref: 5f7a6b7ea3c4ae1b51beffe3309e9b6b0491e71f
dir: /sys/src/cmd/venti/srv/lumpcache.c/
#include "stdinc.h"
#include "dat.h"
#include "fns.h"
/* #define CHECK(x) x */
#define CHECK(x)
typedef struct LumpCache LumpCache;
enum
{
HashLog = 9,
HashSize = 1<<HashLog,
HashMask = HashSize - 1,
};
struct LumpCache
{
QLock lock;
Rendez full;
Lump *free; /* list of available lumps */
u32int allowed; /* total allowable space for packets */
u32int avail; /* remaining space for packets */
u32int now; /* ticks for usage timestamps */
Lump **heads; /* hash table for finding address */
int nheap; /* number of available victims */
Lump **heap; /* heap for locating victims */
int nblocks; /* number of blocks allocated */
Lump *blocks; /* array of block descriptors */
};
static LumpCache lumpcache;
static void delheap(Lump *db);
static int downheap(int i, Lump *b);
static void fixheap(int i, Lump *b);
static int upheap(int i, Lump *b);
static Lump *bumplump(void);
void
initlumpcache(u32int size, u32int nblocks)
{
Lump *last, *b;
int i;
lumpcache.full.l = &lumpcache.lock;
lumpcache.nblocks = nblocks;
lumpcache.allowed = size;
lumpcache.avail = size;
lumpcache.heads = MKNZ(Lump*, HashSize);
lumpcache.heap = MKNZ(Lump*, nblocks);
lumpcache.blocks = MKNZ(Lump, nblocks);
setstat(StatLcacheSize, lumpcache.nblocks);
last = nil;
for(i = 0; i < nblocks; i++){
b = &lumpcache.blocks[i];
b->type = TWID8;
b->heap = TWID32;
b->next = last;
last = b;
}
lumpcache.free = last;
lumpcache.nheap = 0;
}
Lump*
lookuplump(u8int *score, int type)
{
uint ms;
Lump *b;
u32int h;
ms = 0;
trace(TraceLump, "lookuplump enter");
h = hashbits(score, HashLog);
/*
* look for the block in the cache
*/
qlock(&lumpcache.lock);
CHECK(checklumpcache());
again:
for(b = lumpcache.heads[h]; b != nil; b = b->next){
if(scorecmp(score, b->score)==0 && type == b->type){
addstat(StatLcacheHit, 1);
trace(TraceLump, "lookuplump hit");
goto found;
}
}
trace(TraceLump, "lookuplump miss");
/*
* missed: locate the block with the oldest second to last use.
* remove it from the heap, and fix up the heap.
*/
while(lumpcache.free == nil){
trace(TraceLump, "lookuplump bump");
CHECK(checklumpcache());
if(bumplump() == nil){
CHECK(checklumpcache());
logerr(EAdmin, "all lump cache blocks in use");
addstat(StatLcacheStall, 1);
CHECK(checklumpcache());
rsleep(&lumpcache.full);
CHECK(checklumpcache());
addstat(StatLcacheStall, -1);
goto again;
}
CHECK(checklumpcache());
}
/* start timer on cache miss to avoid system call on cache hit */
ms = msec();
addstat(StatLcacheMiss, 1);
b = lumpcache.free;
lumpcache.free = b->next;
/*
* the new block has no last use, so assume it happens sometime in the middle
ZZZ this is not reasonable
*/
b->used = (b->used2 + lumpcache.now) / 2;
/*
* rechain the block on the correct hash chain
*/
b->next = lumpcache.heads[h];
lumpcache.heads[h] = b;
if(b->next != nil)
b->next->prev = b;
b->prev = nil;
scorecp(b->score, score);
b->type = type;
b->size = 0;
b->data = nil;
found:
b->ref++;
b->used2 = b->used;
b->used = lumpcache.now++;
if(b->heap != TWID32)
fixheap(b->heap, b);
CHECK(checklumpcache());
qunlock(&lumpcache.lock);
addstat(StatLumpStall, 1);
qlock(&b->lock);
addstat(StatLumpStall, -1);
trace(TraceLump, "lookuplump exit");
addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0);
return b;
}
void
insertlump(Lump *b, Packet *p)
{
u32int size;
/*
* look for the block in the cache
*/
trace(TraceLump, "insertlump enter");
qlock(&lumpcache.lock);
CHECK(checklumpcache());
again:
addstat(StatLcacheWrite, 1);
/*
* missed: locate the block with the oldest second to last use.
* remove it from the heap, and fix up the heap.
*/
size = packetasize(p);
while(lumpcache.avail < size){
trace(TraceLump, "insertlump bump");
CHECK(checklumpcache());
if(bumplump() == nil){
logerr(EAdmin, "all lump cache blocks in use");
addstat(StatLcacheStall, 1);
CHECK(checklumpcache());
rsleep(&lumpcache.full);
CHECK(checklumpcache());
addstat(StatLcacheStall, -1);
goto again;
}
CHECK(checklumpcache());
}
b->data = p;
b->size = size;
lumpcache.avail -= size;
CHECK(checklumpcache());
qunlock(&lumpcache.lock);
trace(TraceLump, "insertlump exit");
}
void
putlump(Lump *b)
{
if(b == nil)
return;
trace(TraceLump, "putlump");
qunlock(&b->lock);
qlock(&lumpcache.lock);
CHECK(checklumpcache());
if(--b->ref == 0){
if(b->heap == TWID32)
upheap(lumpcache.nheap++, b);
trace(TraceLump, "putlump wakeup");
rwakeupall(&lumpcache.full);
}
CHECK(checklumpcache());
qunlock(&lumpcache.lock);
}
/*
* remove some lump from use and update the free list and counters
*/
static Lump*
bumplump(void)
{
Lump *b;
u32int h;
/*
* remove blocks until we find one that is unused
* referenced blocks are left in the heap even though
* they can't be scavenged; this is simple a speed optimization
*/
CHECK(checklumpcache());
for(;;){
if(lumpcache.nheap == 0){
trace(TraceLump, "bumplump emptyheap");
return nil;
}
b = lumpcache.heap[0];
delheap(b);
if(!b->ref){
trace(TraceLump, "bumplump wakeup");
rwakeupall(&lumpcache.full);
break;
}
}
/*
* unchain the block
*/
trace(TraceLump, "bumplump unchain");
if(b->prev == nil){
h = hashbits(b->score, HashLog);
if(lumpcache.heads[h] != b)
sysfatal("bad hash chains in lump cache");
lumpcache.heads[h] = b->next;
}else
b->prev->next = b->next;
if(b->next != nil)
b->next->prev = b->prev;
if(b->data != nil){
packetfree(b->data);
b->data = nil;
lumpcache.avail += b->size;
b->size = 0;
}
b->type = TWID8;
b->next = lumpcache.free;
lumpcache.free = b;
CHECK(checklumpcache());
trace(TraceLump, "bumplump exit");
return b;
}
void
emptylumpcache(void)
{
qlock(&lumpcache.lock);
while(bumplump())
;
qunlock(&lumpcache.lock);
}
/*
* delete an arbitrary block from the heap
*/
static void
delheap(Lump *db)
{
fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
db->heap = TWID32;
}
/*
* push an element up or down to it's correct new location
*/
static void
fixheap(int i, Lump *b)
{
if(upheap(i, b) == i)
downheap(i, b);
}
static int
upheap(int i, Lump *b)
{
Lump *bb;
u32int now;
int p;
now = lumpcache.now;
for(; i != 0; i = p){
p = (i - 1) >> 1;
bb = lumpcache.heap[p];
if(b->used2 - now >= bb->used2 - now)
break;
lumpcache.heap[i] = bb;
bb->heap = i;
}
lumpcache.heap[i] = b;
b->heap = i;
return i;
}
static int
downheap(int i, Lump *b)
{
Lump *bb;
u32int now;
int k;
now = lumpcache.now;
for(; ; i = k){
k = (i << 1) + 1;
if(k >= lumpcache.nheap)
break;
if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
k++;
bb = lumpcache.heap[k];
if(b->used2 - now <= bb->used2 - now)
break;
lumpcache.heap[i] = bb;
bb->heap = i;
}
lumpcache.heap[i] = b;
b->heap = i;
return i;
}
static void
findblock(Lump *bb)
{
Lump *b, *last;
int h;
last = nil;
h = hashbits(bb->score, HashLog);
for(b = lumpcache.heads[h]; b != nil; b = b->next){
if(last != b->prev)
sysfatal("bad prev link");
if(b == bb)
return;
last = b;
}
sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
}
void
checklumpcache(void)
{
Lump *b;
u32int size, now, nfree;
int i, k, refed;
now = lumpcache.now;
for(i = 0; i < lumpcache.nheap; i++){
if(lumpcache.heap[i]->heap != i)
sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
sysfatal("lc: bad heap ordering");
k = (i << 1) + 1;
if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
sysfatal("lc: bad heap ordering");
k++;
if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
sysfatal("lc: bad heap ordering");
}
refed = 0;
size = 0;
for(i = 0; i < lumpcache.nblocks; i++){
b = &lumpcache.blocks[i];
if(b->data == nil && b->size != 0)
sysfatal("bad size: %d data=%p", b->size, b->data);
if(b->ref && b->heap == TWID32)
refed++;
if(b->type != TWID8){
findblock(b);
size += b->size;
}
if(b->heap != TWID32
&& lumpcache.heap[b->heap] != b)
sysfatal("lc: spurious heap value");
}
if(lumpcache.avail != lumpcache.allowed - size){
fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
*(int*)0=0;
}
nfree = 0;
for(b = lumpcache.free; b != nil; b = b->next){
if(b->type != TWID8 || b->heap != TWID32)
sysfatal("lc: bad free list");
nfree++;
}
if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
}