shithub: neoventi

ref: a4f141bd3a1af74816c85f8266ee1125437698eb
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 BUCKET_SIZE 8
// Hardcode 2GiB of cache for now
#define CACHE_SIZE 2ULL*1024*1024*1024
// 
#define NENTRIES CACHE_SIZE/0x2000ULL
// Triple needed size so max possible load factor is ⅓
#define NBUCKETS (3ULL*NENTRIES/8)
#define BITS 64-15

void
cacheinit(void)
{
	usize displacement;
	assert(sizeof(Lock) == 8);
	assert(sizeof(bucket_t) == 64);
	data = sbrk((usize)0x2000 * NENTRIES);
	if(data == (void*)-1)
		sysfatal("failed to allocate cache space of %lux", 8192*NENTRIES);
	buckets = sbrk(64 + 64*NBUCKETS);
	freelist = sbrk(4 * NENTRIES);
	displacement = ((usize)buckets & 0b111111);
	if(displacement != 0){
		displacement = 64 - displacement;
		buckets = (bucket_t*)((usize)buckets + displacement);
	}
	// alignment
	assert(((usize)buckets&0b111111) == 0);
	bucketend = buckets + NBUCKETS;
	freelen = NENTRIES;
	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);
	// Should be impossible to run out - we set up
	// enough buffers for each cache entry to get
	// one.
	// Before grabbing a new one, we'll always evict
	// an old one.
	assert(freelen != 0);
	freelen -= 1;
	result = freelist[freelen];
	unlock(&freelock);
	return result;
}

static bucket_t*
getbucket(u32int key)
{
	// Fibonacci hashing!
	return &buckets[key * 11400714819323198485LL >> BITS];
}

static void
put(bucket_t *bucket, int i, u32int key, u32int cacheindex)
{
	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;
}

static void
get(bucket_t *bucket, int i, char **buf)
{
	usize cacheindex = bucket->values[i*3] | (bucket->values[i*3+1]<<8) | (bucket->values[i*3+2]<<16);
	*buf = data + cacheindex * 8192;
}

static int
trybucket(bucket_t *bucket, int *i, u32int key)
{
	for(*i = 0; *i < BUCKET_SIZE; *i += 1){
		if(bucket->index[*i] == key)
			return 1;
		if(bucket->index[*i] == 0)
			return 0;
	}
	return -1;
}

// 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)
{
	u32int cacheindex;
	int i;
	u32int key = (arenaindex << 16) | blockindex;
	bucket_t *bucket = getbucket(key);
	usize tried = 0;
	while(tried < NBUCKETS){
		switch(trybucket(bucket, &i, key)){
		case -1:
			// miss. linear probe.
			tried+=1;
			bucket++;
			if(bucket == bucketend)
				bucket = buckets;
			continue;
		case 0:
			// found an empty slot
			cacheindex = grabfree();
			*buf = data+(usize)cacheindex*8192;
			put(bucket, i, key, cacheindex);
			return 0;
		case 1:
			// already exists
			get(bucket, i, buf);
			return 1;
		}
	}
	sysfatal("TODO: support eviction");
	return 0;
}