ref: 3971bc6b760a0658b27d0dd0f46693129ff59164
dir: /cache.c/
#include <u.h>
#include <libc.h>
#pragma pack on
typedef struct {
Lock;
// index into raw cache
u32int index[7];
// 24 bits of value index plus 8 bits of fd
u32int value[7];
} bucket_t;
#pragma pack off
typedef char mainentry_t[8192];
static mainentry_t *data;
static bucket_t *buckets, *bucketend;
static u32int *freelist;
static u32int freelen;
static Lock freelock;
void
cacheinit(void)
{
usize displacement;
assert(sizeof(Lock) == 8);
assert(sizeof(bucket_t) == 64);
data = sbrk(8192 * 128*1024);
// 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*32768);
freelist = sbrk(4 * 128*1024);
displacement = ((usize)buckets & 0b111111);
if(displacement != 0){
displacement = 64 - displacement;
buckets = (bucket_t*)((usize)buckets + displacement);
}
// alignment
assert(((usize)buckets&0b111111) == 0);
bucketend = buckets + 32768;
freelen = 128*1024;
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 read has been finished.
// See documentation at top of file for more details.
void
cachewritten(int fd, u32int blockindex)
{
u64int bucketindex;
bucket_t *bucket;
u32int key;
assert(fd < 0xFF);
key = (blockindex << 8) | fd;
// We have 32K buckets, so we want 15 bits
bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
bucket = &buckets[bucketindex];
unlock(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, int fd, u32int blockindex)
{
u64int bucketindex;
u32int cacheindex;
bucket_t *bucket;
u32int key;
assert(fd < 0xFF);
key = (blockindex << 8) | fd;
// We have 32K buckets, so we want 15 bits
bucketindex = ((u64int)key * 11400714819323198485LL) >> 49;
print("GET bucket index: %llx\n", bucketindex);
bucket = &buckets[bucketindex];
while(bucket != bucketend){
lock(bucket);
for(int i = 0; i < 7; i += 1){
if(bucket->index[i] == 0){
// Key does not exist
cacheindex = grabfree();
*buf = (char*)(data + cacheindex);
assert((cacheindex & 0xFF000000) == 0);
bucket->index[i] = blockindex;
bucket->value[i] = (cacheindex << 8) | fd;
// Leaves bucket locked intentionally!
return 0;
}
if(bucket->index[i] == blockindex && (bucket->value[i] & 0xff) == fd){
*buf = (char*)(data + (bucket->value[i] >> 8));
unlock(bucket);
return 1;
}
}
unlock(bucket);
bucket++;
}
sysfatal("unreachable");
return 0;
}