harvey/sys/src/cmd/venti/srv/icache.c

/*
 * This file is part of the UCB release of Plan 9. It is subject to the license
 * terms in the LICENSE file found in the top-level directory of this
 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
 * part of the UCB release of Plan 9, including this file, may be copied,
 * modified, propagated, or distributed except according to the terms contained
 * in the LICENSE file.
 */

#include "stdinc.h"
#include "dat.h"
#include "fns.h"

int icacheprefetch = 1;

typedef struct ICache ICache;
typedef struct IHash IHash;
typedef struct ISum ISum;

struct ICache
{
	QLock	lock;
	Rendez	full;
	IHash	*hash;
	IEntry	*entries;
	int		nentries;
	IEntry	free;
	IEntry	clean;
	IEntry	dirty;
	uint32_t	maxdirty;
	uint32_t	ndirty;
	AState	as;

	ISum	**sum;
	int		nsum;
	IHash	*shash;
	IEntry	*sentries;
	int		nsentries;
};

static ICache icache;

/*
 * Hash table of IEntries
 */

struct IHash
{
	int bits;
	uint32_t size;
	IEntry **table;
};

static IHash*
mkihash(int size1)
{
	uint32_t size;
	int bits;
	IHash *ih;

	bits = 0;
	size = 1;
	while(size < size1){
		bits++;
		size <<= 1;
	}

	ih = vtmallocz(sizeof(IHash)+size*sizeof(ih->table[0]));
	ih->table = (IEntry**)(ih+1);
	ih->bits = bits;
	ih->size = size;
	return ih;
}

static IEntry*
ihashlookup(IHash *ih, uint8_t score[VtScoreSize], int type)
{
	uint32_t h;
	IEntry *ie;

	h = hashbits(score, ih->bits);
	for(ie=ih->table[h]; ie; ie=ie->nexthash)
		if((type == -1 || type == ie->ia.type) && scorecmp(score, ie->score) == 0)
			return ie;
	return nil;
}

static void
ihashdelete(IHash *ih, IEntry *ie, char *what)
{
	uint32_t h;
	IEntry **l;

	h = hashbits(ie->score, ih->bits);
	for(l=&ih->table[h]; *l; l=&(*l)->nexthash)
		if(*l == ie){
			*l = ie->nexthash;
			return;
		}
	fprint(2, "warning: %s %V not found in ihashdelete\n", what, ie->score);
}

static void
ihashinsert(IHash *ih, IEntry *ie)
{
	uint32_t h;

	h = hashbits(ie->score, ih->bits);
	ie->nexthash = ih->table[h];
	ih->table[h] = ie;
}


/*
 * IEntry lists.
 */

static IEntry*
popout(IEntry *ie)
{
	if(ie->prev == nil && ie->next == nil)
		return ie;
	ie->prev->next = ie->next;
	ie->next->prev = ie->prev;
	ie->next = nil;
	ie->prev = nil;
	return ie;
}

static IEntry*
poplast(IEntry *list)
{
	if(list->prev == list)
		return nil;
	return popout(list->prev);
}

static IEntry*
pushfirst(IEntry *list, IEntry *ie)
{
	popout(ie);
	ie->prev = list;
	ie->next = list->next;
	ie->prev->next = ie;
	ie->next->prev = ie;
	return ie;
}

/*
 * Arena summary cache.
 */
struct ISum
{
	QLock	lock;
	IEntry	*entries;
	int	nentries;
	int	loaded;
	uint64_t addr;
	uint64_t limit;
	Arena *arena;
	int g;
};

static ISum*
scachelookup(uint64_t addr)
{
	int i;
	ISum *s;

	for(i=0; i<icache.nsum; i++){
		s = icache.sum[i];
		if(s->addr <= addr && addr < s->limit){
			if(i > 0){
				memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
				icache.sum[0] = s;
			}
			return s;
		}
	}
	return nil;
}

static void
sumclear(ISum *s)
{
	int i;

	for(i=0; i<s->nentries; i++)
		ihashdelete(icache.shash, &s->entries[i], "scache");
	s->nentries = 0;
	s->loaded = 0;
	s->addr = 0;
	s->limit = 0;
	s->arena = nil;
	s->g = 0;
}

static ISum*
scacheevict(void)
{
	ISum *s;
	int i;

	for(i=icache.nsum-1; i>=0; i--){
		s = icache.sum[i];
		if(canqlock(&s->lock)){
			if(i > 0){
				memmove(icache.sum+1, icache.sum, i*sizeof icache.sum[0]);
				icache.sum[0] = s;
			}
			sumclear(s);
			return s;
		}
	}
	return nil;
}

static void
scachehit(uint64_t addr)
{
	scachelookup(addr);	/* for move-to-front */
}

static void
scachesetup(ISum *s, uint64_t addr)
{
	uint64_t addr0, limit;
	int g;

	s->arena = amapitoag(mainindex, addr, &addr0, &limit, &g);
	s->addr = addr0;
	s->limit = limit;
	s->g = g;
}

static void
scacheload(ISum *s)
{
	int i, n;

	s->loaded = 1;
	n = asumload(s->arena, s->g, s->entries, ArenaCIGSize);
	/*
	 * n can be less then ArenaCIGSize, either if the clump group
	 * is the last in the arena and is only partially filled, or if there
	 * are corrupt clumps in the group -- those are not returned.
	 */
	for(i=0; i<n; i++){
		s->entries[i].ia.addr += s->addr;
		ihashinsert(icache.shash, &s->entries[i]);
	}
//fprint(2, "%T scacheload %s %d - %d entries\n", s->arena->name, s->g, n);
	addstat(StatScachePrefetch, n);
	s->nentries = n;
}

static ISum*
scachemiss(uint64_t addr)
{
	ISum *s;

	if(!icacheprefetch)
		return nil;
	s = scachelookup(addr);
	if(s == nil){
		/* first time: make an entry in the cache but don't populate it yet */
		s = scacheevict();
		if(s == nil)
			return nil;
		scachesetup(s, addr);
		qunlock(&s->lock);
		return nil;
	}

	/* second time: load from disk */
	qlock(&s->lock);
	if(s->loaded || !icacheprefetch){
		qunlock(&s->lock);
		return nil;
	}

	return s;	/* locked */
}

/*
 * Index cache.
 */

void
initicache(uint32_t mem0)
{
	uint32_t mem;
	int i, entries, scache;

	icache.full.l = &icache.lock;

	mem = mem0;
	entries = mem / (sizeof(IEntry)+sizeof(IEntry*));
	scache = (entries/8) / ArenaCIGSize;
	entries -= entries/8;
	if(scache < 4)
		scache = 4;
	if(scache > 16)
		scache = 16;
	if(entries < 1000)
		entries = 1000;
fprint(2, "icache %,d bytes = %,d entries; %d scache\n", mem0, entries, scache);

	icache.clean.prev = icache.clean.next = &icache.clean;
	icache.dirty.prev = icache.dirty.next = &icache.dirty;
	icache.free.prev = icache.free.next = &icache.free;

	icache.hash = mkihash(entries);
	icache.nentries = entries;
	setstat(StatIcacheSize, entries);
	icache.entries = vtmallocz(entries*sizeof icache.entries[0]);
	icache.maxdirty = entries / 2;
	for(i=0; i<entries; i++)
		pushfirst(&icache.free, &icache.entries[i]);

	icache.nsum = scache;
	icache.sum = vtmallocz(scache*sizeof icache.sum[0]);
	icache.sum[0] = vtmallocz(scache*sizeof icache.sum[0][0]);
	icache.nsentries = scache * ArenaCIGSize;
	icache.sentries = vtmallocz(scache*ArenaCIGSize*sizeof icache.sentries[0]);
	icache.shash = mkihash(scache*ArenaCIGSize);
	for(i=0; i<scache; i++){
		icache.sum[i] = icache.sum[0] + i;
		icache.sum[i]->entries = icache.sentries + i*ArenaCIGSize;
	}
}


static IEntry*
evictlru(void)
{
	IEntry *ie;

	ie = poplast(&icache.clean);
	if(ie == nil)
		return nil;
	ihashdelete(icache.hash, ie, "evictlru");
	return ie;
}

static void
icacheinsert(uint8_t score[VtScoreSize], IAddr *ia, int state)
{
	IEntry *ie;

	if((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
		addstat(StatIcacheStall, 1);
		while((ie = poplast(&icache.free)) == nil && (ie = evictlru()) == nil){
			// Could safely return here if state == IEClean.
			// But if state == IEDirty, have to wait to make
			// sure we don't lose an index write.
			// Let's wait all the time.
			flushdcache();
			kickicache();
			rsleep(&icache.full);
		}
		addstat(StatIcacheStall, -1);
	}

	memmove(ie->score, score, VtScoreSize);
	ie->state = state;
	ie->ia = *ia;
	if(state == IEClean){
		addstat(StatIcachePrefetch, 1);
		pushfirst(&icache.clean, ie);
	}else{
		addstat(StatIcacheWrite, 1);
		assert(state == IEDirty);
		icache.ndirty++;
		setstat(StatIcacheDirty, icache.ndirty);
		delaykickicache();
		pushfirst(&icache.dirty, ie);
	}
	ihashinsert(icache.hash, ie);
}

int
icachelookup(uint8_t score[VtScoreSize], int type, IAddr *ia)
{
	IEntry *ie;

	qlock(&icache.lock);
	addstat(StatIcacheLookup, 1);
	if((ie = ihashlookup(icache.hash, score, type)) != nil){
		*ia = ie->ia;
		if(ie->state == IEClean)
			pushfirst(&icache.clean, ie);
		addstat(StatIcacheHit, 1);
		qunlock(&icache.lock);
		return 0;
	}

	if((ie = ihashlookup(icache.shash, score, type)) != nil){
		*ia = ie->ia;
		icacheinsert(score, &ie->ia, IEClean);
		scachehit(ie->ia.addr);
		addstat(StatScacheHit, 1);
		qunlock(&icache.lock);
		return 0;
	}
	addstat(StatIcacheMiss, 1);
	qunlock(&icache.lock);

	return -1;
}

int
insertscore(uint8_t score[VtScoreSize], IAddr *ia, int state, AState *as)
{
	ISum *toload;

	qlock(&icache.lock);
	icacheinsert(score, ia, state);
	if(state == IEClean)
		toload = scachemiss(ia->addr);
	else{
		assert(state == IEDirty);
		toload = nil;
		if(as == nil)
			fprint(2, "%T insertscore IEDirty without as; called from %#p\n",
				getcallerpc());
		else{
			if(icache.as.aa > as->aa)
				fprint(2, "%T insertscore: aa moving backward: %#llx -> %#llx\n", icache.as.aa, as->aa);
			icache.as = *as;
		}
	}
	qunlock(&icache.lock);
	if(toload){
		scacheload(toload);
		qunlock(&toload->lock);
	}

	if(icache.ndirty >= icache.maxdirty)
		kickicache();

	/*
	 * It's okay not to do this under icache.lock.
	 * Calling insertscore only happens when we hold
	 * the lump, meaning any searches for this block
	 * will hit in the lump cache until after we return.
	 */
	if(state == IEDirty)
		markbloomfilter(mainindex->bloom, score);

	return 0;
}

int
lookupscore(uint8_t score[VtScoreSize], int type, IAddr *ia)
{
	int ms, ret;
	IEntry d;

	if(icachelookup(score, type, ia) >= 0){
		addstat(StatIcacheRead, 1);
		return 0;
	}

	ms = msec();
	addstat(StatIcacheFill, 1);
	if(loadientry(mainindex, score, type, &d) < 0)
		ret = -1;
	else{
		ret = 0;
		insertscore(score, &d.ia, IEClean, nil);
		*ia = d.ia;
	}
	addstat2(StatIcacheRead, 1, StatIcacheReadTime, msec() - ms);
	return ret;
}

uint32_t
hashbits(uint8_t *sc, int bits)
{
	uint32_t v;

	v = (sc[0] << 24) | (sc[1] << 16) | (sc[2] << 8) | sc[3];
	if(bits < 32)
		 v >>= (32 - bits);
	return v;
}

uint32_t
icachedirtyfrac(void)
{
	return (int64_t)icache.ndirty*IcacheFrac / icache.nentries;
}

/*
 * Return a singly-linked list of dirty index entries.
 * with 32-bit hash numbers between lo and hi
 * and address < limit.
 */
IEntry*
icachedirty(uint32_t lo, uint32_t hi, uint64_t limit)
{
	uint32_t h;
	IEntry *ie, *dirty;

	dirty = nil;
	trace(TraceProc, "icachedirty enter");
	qlock(&icache.lock);
	for(ie = icache.dirty.next; ie != &icache.dirty; ie=ie->next){
		if(ie->state == IEDirty && ie->ia.addr <= limit){
			h = hashbits(ie->score, 32);
			if(lo <= h && h <= hi){
				ie->nextdirty = dirty;
				dirty = ie;
			}
		}
	}
	qunlock(&icache.lock);
	trace(TraceProc, "icachedirty exit");
	if(dirty == nil)
		flushdcache();
	return dirty;
}

AState
icachestate(void)
{
	AState as;

	qlock(&icache.lock);
	as = icache.as;
	qunlock(&icache.lock);
	return as;
}

/*
 * The singly-linked non-circular list of index entries ie
 * has been written to disk.  Move them to the clean list.
 */
void
icacheclean(IEntry *ie)
{
	IEntry *next;

	trace(TraceProc, "icacheclean enter");
	qlock(&icache.lock);
	for(; ie; ie=next){
		assert(ie->state == IEDirty);
		next = ie->nextdirty;
		ie->nextdirty = nil;
		popout(ie); /* from icache.dirty */
		icache.ndirty--;
		ie->state = IEClean;
		pushfirst(&icache.clean, ie);
	}
	setstat(StatIcacheDirty, icache.ndirty);
	rwakeupall(&icache.full);
	qunlock(&icache.lock);
	trace(TraceProc, "icacheclean exit");
}

void
emptyicache(void)
{
	int i;
	IEntry *ie;
	ISum *s;

	qlock(&icache.lock);
	while((ie = evictlru()) != nil)
		pushfirst(&icache.free, ie);
	for(i=0; i<icache.nsum; i++){
		s = icache.sum[i];
		qlock(&s->lock);
		sumclear(s);
		qunlock(&s->lock);
	}
	qunlock(&icache.lock);
}