ref: a1aaaac69337a484bb66c9c5b3ffc581b1319dac
dir: /cache.c/
#include <u.h>
#include <libc.h>
#pragma pack on
typedef struct {
Lock;
// arena-local block index | arena index << 16
u32int index[8];
u8int values[8*3];
} bucket_t;
#pragma pack off
static char *data;
static bucket_t *buckets, *bucketend;
static u32int *freelist;
static u32int freelen;
static Lock freelock;
#define NENTRIES 8
#define ENTRIES 0x10000
// Oversizes, but ensures power-of-two for fibonacci hashing
#define BUCKETS (ENTRIES/4)
#define BITS 56
void
cacheinit(void)
{
usize displacement;
assert(sizeof(Lock) == 8);
assert(sizeof(bucket_t) == 64);
data = sbrk(8192 * ENTRIES);
// 18725 buckets is the minimum for 128K entries; we round up to 32,768. That "wastes" ~1MiB, but spreads entries out further,
// and gives a nice power of two for fibonacci hashing.
buckets = sbrk(64 + 64*BUCKETS);
freelist = sbrk(4 * ENTRIES);
displacement = ((usize)buckets & 0b111111);
if(displacement != 0){
displacement = 64 - displacement;
buckets = (bucket_t*)((usize)buckets + displacement);
}
// alignment
assert(((usize)buckets&0b111111) == 0);
bucketend = buckets + BUCKETS;
freelen = ENTRIES;
for(u32int i = 0; i < freelen; i += 1){
freelist[i] = i;
}
}
// Grabs a free cache entry, evicting if necessary.
u32int
grabfree(void)
{
u32int result;
lock(&freelock);
// For now, block until something is free.
// This is terrible. FIXME
while(freelen == 0){
unlock(&freelock);
sleep(50);
lock(&freelock);
}
freelen -= 1;
result = freelist[freelen];
unlock(&freelock);
return result;
}
// Called to indicate that a request has been finished.
// See documentation at top of file for more details.
void
cachedone(u16int arenaindex, u16int blockindex)
{
u64int bucketindex;
bucket_t *bucket;
u32int key;
key = arenaindex<<16 | blockindex;
// We have 32K buckets, so we want 15 bits
bucketindex = ((u64int)key * 11400714819323198485LL) >> BITS;
bucket = &buckets[bucketindex];
// Need to do linear probing to find the right bucket to unlock
for(;;){
for(int i = 0; i < NENTRIES; i += 1){
if(bucket->index[i] == key){
unlock(bucket);
return;
}
}
bucket++;
}
}
// Looks up a cache entry. If the entry is not present in cache,
// this grabs a free buffer, inserts it into cache, and yields
// its index so that the caller may fill it up.
// Returns whether the data was already in cache.
int
cachelookup(char **buf, u16int arenaindex, u32int blockindex)
{
u64int bucketindex;
u32int cacheindex;
bucket_t *bucket;
u32int key;
assert(blockindex < 0x10000);
key = arenaindex << 16 | (blockindex&0xFFFF);
// We have 32K buckets, so we want 15 bits
bucketindex = ((u64int)key * 11400714819323198485LL) >> BITS;
bucket = &buckets[bucketindex];
while(bucket != bucketend){
lock(bucket);
for(int i = 0; i < NENTRIES; i += 1){
if(bucket->index[i] == 0){
// Key does not exist
cacheindex = grabfree();
*buf = &data[cacheindex*8192];
assert((cacheindex & 0xFF000000) == 0);
bucket->index[i] = key;
bucket->values[i*3] = cacheindex&0xFF;
bucket->values[i*3+1] = (cacheindex>>8)&0xFF;
bucket->values[i*3+2] = cacheindex>>16;
// Leaves bucket locked intentionally!
return 0;
}
if(bucket->index[i] == key){
u32int cacheindex = bucket->values[i*3] | (bucket->values[i*3+1]<<8) | (bucket->values[i*3+2]<<16);
*buf = &data[cacheindex * 8192];
return 1;
}
}
unlock(bucket);
bucket++;
}
//FIXME not unreachable
//if the final bucket is full, we must handle it
sysfatal("unreachable");
return 0;
}