shithub: neoventi

ref: a24a074bc3809078435fbcb45250967ec9a5891e
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 0x80000
// Oversizes, but ensures power-of-two for fibonacci hashing
#define BUCKETS (ENTRIES/8)
#define BITS 48

void
cacheinit(void)
{
	usize displacement;
	assert(sizeof(Lock) == 8);
	assert(sizeof(bucket_t) == 64);
	data = sbrk((usize)0x2000 * ENTRIES);
	if(data == (void*)-1)
		sysfatal("failed to allocate cache space of %lux", 8192*ENTRIES/2);
	print("data %llx, end %llx\n", data, data + 8192*ENTRIES);
	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;
}

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;
	if(*buf == (void*)0x7fffdfff){
		print("data %llx, cacheindex %lld, data+cacheindex*0x2000 %llx\n", data, cacheindex, data+cacheindex*0x2000);
	}
}

static int
trybucket(bucket_t *bucket, int *i, u32int key)
{
	for(*i = 0; *i < NENTRIES; *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);
	while(bucket != bucketend){
		switch(trybucket(bucket, &i, key)){
		case -1:
			// miss. linear probe.
			bucket++;
			continue;
		case 0:
			// found an empty slot
			cacheindex = grabfree();
			*buf = data+(usize)cacheindex*8192;
	if(*buf == (void*)0x7fffdfff){
		print("data %llx, cacheindex %lld, data+cacheindex*0x2000 %llx\n", data, cacheindex, data+cacheindex*0x2000);
	}
			put(bucket, i, key, cacheindex);
			return 0;
		case 1:
			// already exists
			get(bucket, i, buf);
			return 1;
		}
	}
//FIXME not unreachable
//if the final bucket is full, we must handle it
	sysfatal("unreachable");
	return 0;
}