shithub: gefs

ref: e3f72faa42528a76d3c77081bb0bf11a6ea4efa5
dir: /snap.c/

View raw version
#include <u.h>
#include <libc.h>
#include <fcall.h>
#include <avl.h>

#include "dat.h"
#include "fns.h"
#include "atomic.h"

static char*
dlsync(Dlist *dl)
{
	char kvbuf[512];
	Msg m;

	if(dl->ins == nil)
		return nil;
	if(checkflag(dl->ins, Bdirty))
		enqueue(dl->ins);

	dl->hd = dl->ins->bp;
	if(dl->hd.addr == dl->tl.addr)
		dl->tl = dl->hd;
	m.op = Oinsert;
	dlist2kv(dl, &m, kvbuf, sizeof(kvbuf));
	return btupsert(&fs->snap, &m, 1);
}

static void
dlcachedel(Dlist *dl, int hdel)
{
	uint h;
	Dlist *d, **p;

	h = ihash(dl->gen) ^ ihash(dl->bgen);
	if(hdel){
		p = &fs->dlcache[h % fs->dlcmax];
		for(d = *p; d != nil; d = d->chain){
			if(d->gen == dl->gen && d->bgen == dl->bgen)
				break;
			p = &d->chain;
		}
		if(d != nil)
			*p  = d->chain;
	}
	if(dl == fs->dlhead)
		fs->dlhead = dl->cnext;
	if(dl == fs->dltail)
		fs->dltail = dl->cprev;
	if(dl->cnext != nil)
		dl->cnext->cprev = dl->cprev;
	if(dl->cprev != nil)
		dl->cprev->cnext = dl->cnext;
	dl->cnext = nil;
	dl->cprev = nil;
}

static Dlist*
dlcacheget(vlong gen, vlong bgen)
{
	Dlist *dl;
	uint h;

	h = ihash(gen) ^ ihash(bgen);
	for(dl = fs->dlcache[h % fs->dlcmax]; dl != nil; dl = dl->chain)
		if(dl->gen == gen && dl->bgen == bgen)
			break;
	if(dl != nil)
		dlcachedel(dl, 0);
	return dl;
}

static Dlist*
getdl(vlong gen, vlong bgen)
{
	char kbuf[Dlksz], kvbuf[Dlkvpsz];
	Dlist *dl, **p;
	uint h;
	Msg m;
	Kvp kv;
	Key k;

	if((dl = dlcacheget(gen, bgen)) != nil)
		return dl;
	if((dl = mallocz(sizeof(Dlist), 1)) == nil)
		return nil;
	kbuf[0] = Kdlist;
	PACK64(kbuf+1, gen);
	PACK64(kbuf+9, bgen);
	k.k = kbuf;
	k.nk = sizeof(kbuf);

	/* load up existing dlist */
	if(btlookup(&fs->snap, &k, &kv, kvbuf, sizeof(kvbuf)) == nil){
		kv2dlist(&kv, dl);
		if(dl->hd.addr != -1 && (dl->ins = getblk(dl->hd, 0)) == nil){
			free(dl);
			return nil;
		}
		goto Found;
	}

	/* create a new one if it didn't exist */
	dl->gen = gen;
	dl->bgen = bgen;
	dl->hd.addr = -1;
	dl->tl.addr = -1;
	dl->ins = nil;

	m.op = Oinsert;
	dlist2kv(dl, &m, kvbuf, sizeof(kvbuf));
	if(btupsert(&fs->snap, &m, 1) != nil){
		free(dl);
		return nil;
	}
Found:
	h = ihash(gen) ^ ihash(bgen);
	p = &fs->dlcache[h % fs->dlcmax];
	dl->chain = *p;
	*p = dl;
	return dl;
}

void
putdl(Dlist *dl)
{
	Dlist *dt;

	dlcachedel(dl, 0);

	while(fs->dltail != nil && fs->dlcount >= fs->dlcmax){
		dt = fs->dltail;
		dlsync(dt);
		dlcachedel(dt, 1);
		dropblk(dt->ins);
		free(dt);
	}

	dl->cprev = nil;
	dl->cnext = fs->dlhead;
	if(fs->dltail == nil)
		fs->dltail = dl;
	if(fs->dlhead != nil)
		fs->dlhead->cprev = dl;
	fs->dlhead = dl;
}

char*
freedl(Dlist *dl, int docontents)
{
	Bptr bp, fb;
	Blk *b;
	char *p;

	bp = dl->hd;
	while(bp.addr != -1){
		if((b = getblk(bp, 0)) == nil)
			return Efs;
		if(docontents){
			for(p = b->data; p != b->data+b->logsz; p += 8){
				fb.addr = UNPACK64(p);
				fb.hash = -1;
				fb.gen = -1;
				freeblk(nil, nil, fb);
			}
		}
		bp = b->logp;
		freeblk(&fs->snap, b, b->bp);
		dropblk(b);
	}
	return nil;
}

static char*
mergedl(vlong succ, vlong gen, vlong bgen)
{
	char *err, buf[2][Kvmax];
	Dlist *d, *m;
	Msg msg[2];
	Blk *b;
//	vlong x;

	err = nil;
	d = getdl(gen, bgen);
	m = getdl(succ, bgen);
	if(d == nil || m == nil){
		err = Efs;
		goto Out;
	}
	if(m->ins == nil){
		m->hd = d->hd;
		m->tl = d->tl;
		m->ins = d->ins;
	}else{
		m->hd = d->hd;
		if((b = getblk(d->tl, 0)) == nil)
			goto Out;
		msg[0].op = Odelete;
		dlist2kv(d, &msg[0], buf[0], sizeof(buf[0]));
		msg[1].op = Oinsert;
		dlist2kv(m, &msg[1], buf[1], sizeof(buf[1]));
		if((err = btupsert(&fs->snap, msg, 2)) != nil)
			sysfatal("merge deadlists: %s", err);

		packbp(b->buf+2, Blksz, &m->hd);
		enqueue(b);
		dropblk(b);

// TODO: merge
//		if(m->ins->logsz + d->ins->logsz < Dlspc){
//			p = d->ins->data;
//			q = m->ins->data + m->ins->logsz;
//			for(i = 0; i < d->ins->logsz; i += 8){
//				m->ins->logsz += 8;
//				x = UNPACK64(p);
//				PACK64(q, x);
//				p += 8;
//				q += 8;
//			}
//		}
	}
Out:
	if(d != nil)
		putdl(d);
	if(m != nil)
		putdl(m);
	return err;
}

vlong
successor(vlong gen)
{
	char *e, pfx[9];
	vlong id, succ;
	Scan s;

	pfx[0] = Kslink;
	succ = -1;
	PACK64(pfx+1, gen);
	btnewscan(&s, pfx, sizeof(pfx));
	if((e = btenter(&fs->snap, &s)) != nil)
		goto Err;
	if((e = btnext(&s, &s.kv)) != nil)
		goto Err;
	if(!s.done)
		kv2link(&s.kv, &id, &succ);
	if((e = btnext(&s, &s.kv)) != nil)
		goto Err;
	if(!s.done)
		sysfatal("multiple successors in cleanup");
	btexit(&s);
	return succ;
Err:
	fprint(2, "error getting snap successor: %s", e);
	btexit(&s);
	return -1;
}

static char*
reclaimblocks(vlong gen, vlong succ, vlong prev)
{
	char *e, pfx[9];
	Dlist dl;
	Scan s;
	Msg m;

	pfx[0] = Kdlist;
	PACK64(pfx+1, gen);
	btnewscan(&s, pfx, sizeof(pfx));
	if((e = btenter(&fs->snap, &s)) != nil)
		return e;
	while(1){
		if((e = btnext(&s, &s.kv)) != nil)
			break;
		if(s.done)
			break;
		kv2dlist(&s.kv, &dl);

		/*
		 * delete the dlist before processing it; it's 
		 * better to leak blocks than to double free.
		 */
		m.op = Odelete;
		m.Kvp = s.kv;
		if((e = btupsert(&fs->snap, &m, 1)) != nil)
			break;
		if(succ == -1)
			e = freedl(&dl, 1);
		else if(dl.bgen > prev)
			e = freedl(&dl, 0);
		else
			e = mergedl(succ, dl.gen, dl.bgen);
		if(e != nil)
			break;
	}
	btexit(&s);
	return e;
}

/*
 * Removes a label from a snapshot, allowing
 * it to be reclaimed if it is not a direct
 * predecessor of more than one other snapshot.
 *
 * If it has one successor and no label, then
 * it will be merged with that successor.
 */
char*
delsnap(Tree *t, vlong succ, char *name)
{
	char buf[2][Kvmax], *e;
	Msg m[2];
	int nm;

	nm = 0;
	if(name != nil){
		if(strcmp(name, "dump") == 0
		|| strcmp(name, "empty") == 0
		|| strcmp(name, "adm") == 0)
			return Ename;

		m[nm].op = Odelete;
		m[nm].k = buf[nm];
		if((e = packlabel(buf[nm], sizeof(buf[nm]), name)) == nil)
			return Ename;
		m[nm].nk = e - m[nm].k;
		m[nm].v = nil;
		m[nm].nv = 0;
		t->nlbl--;
		nm++;
	}
 
	if(t->nlbl == 0 && t->nsucc <= 1){
		m[nm].op = Odelete;
		m[nm].k = buf[nm];
		if((e = packsnap(buf[nm], sizeof(buf[nm]), t->gen)) == nil)
			return Ename;
		m[nm].nk = e - m[nm].k;
		m[nm].v = nil;
		m[nm].nv = 0;
		nm++;
	}else{
		m[nm].op = Oinsert;
		tree2kv(t, &m[nm], buf[nm], sizeof(buf[nm]));
		nm++;
	}
	if((e = flushdlcache(1)) != nil)
		return e;
	if((e = btupsert(&fs->snap, m, nm)) != nil)
		return e;
	if((e = reclaimblocks(t->gen, succ, t->prev)) != nil)
		return e;
	return nil;
}

/*
 * Attaches a label to a tree, incrementing
 * its reference count. This labelled snapshot
 * will show up in the dump.
 */
char*
labelsnap(Tree *t, char *name, int mutable)
{
	char buf[3][Kvmax];
	Msg m[3];
	Tree *n;
	int i;

	if(strcmp(name, "dump") == 0
	|| strcmp(name, "empty") == 0
	|| strcmp(name, "adm") == 0)
		return Ename;

	i = 0;
	if(mutable){
		if((n = mallocz(sizeof(Tree), 1)) == nil)
			return Enomem;
		n->memref = 1;
		n->dirty = 0;
		n->nlbl = 1;
		n->nsucc = 0;
		n->ht = t->ht;
		n->bp = t->bp;
		n->prev = t->gen;
		n->base = t->gen;
		n->gen = aincv(&fs->nextgen, 1);
		n->memgen = aincv(&fs->nextgen, 1);

		t->flag |= Tforked;
		t->nsucc++;

		m[i].op = Oinsert;
		tree2kv(t, &m[i], buf[i], sizeof(buf[i]));
		i++;

		m[i].op = Oinsert;
		tree2kv(n, &m[i], buf[i], sizeof(buf[i]));
		i++;

		m[i].op = Oinsert;
		lbl2kv(name, n->gen, 1, &m[i], buf[i], sizeof(buf[i]));
		i++;
	}else{
		t->nlbl++;
		m[i].op = Oinsert;
		tree2kv(t, &m[i], buf[i], sizeof(buf[i]));
		i++;

		m[i].op = Oinsert;
		lbl2kv(name, t->gen, 0, &m[i], buf[i], sizeof(buf[i]));
		i++;
	}
	return btupsert(&fs->snap, m, i);
}

/*
 * Updates a snapshot; keeps the generation the same if possible,
 * otherwise moves to a new generation. A snapshot may only stay
 * at the same generation as long as it is at the tip of a snapshot
 * list; once it's observable by a derived snapshot it must be
 * immutable.
 */
char*
updatesnap(Tree **r, Tree *o, char *lbl)
{
	char buf[4][Kvmax], *e;
	Msg m[4];
	Tree *t;

	if(!o->dirty)
		return nil;

	/* update the old kvp */
	o->nsucc++;
	o->nlbl--;
	m[0].op = Oinsert;
	tree2kv(o, &m[0], buf[0], sizeof(buf[0]));

	/* create the new one */

	if((t = mallocz(sizeof(Tree), 1)) == nil)
		return Enomem;
	t->memref = 1;
	t->dirty = 0;

	t->nlbl = 1;
	t->nsucc = 0;
	t->ht = o->ht;
	t->bp = o->bp;
	t->base = o->base;
	t->prev = o->gen;
	t->gen = o->memgen;
	t->memgen = aincv(&fs->nextgen, 1);

	m[1].op = Oinsert;
	tree2kv(t, &m[1], buf[1], sizeof(buf[1]));
	m[2].op = Oinsert;
	link2kv(t->prev, t->gen, &m[2], buf[2], sizeof(buf[2]));
	m[3].op = Oinsert;
	lbl2kv(lbl, t->gen, Lmut, &m[3], buf[3], sizeof(buf[3]));
	if((e = btupsert(&fs->snap, m, 4)) != nil){
		free(t);
		return e;
	}

	/* only update the dirty status after we sync */
	o->dirty = 0;

	/* this was the last ref to the snap */
	if(o->nlbl == 0 && o->nsucc == 1){
		t->prev = o->prev;
		delsnap(o, -1, nil);
	}
	closesnap(o);
	asetp(r, t);
	return nil;
}

/*
 * open snapshot by label, returning a tree.
 */
Tree*
opensnap(char *label, int *mut)
{
	char *p, buf[Kvmax];
	Tree *t;
	uint flg;
	vlong gen;
	Kvp kv;
	Key k;

	/* Klabel{"name"} => Ksnap{id} */
	if((p = packlabel(buf, sizeof(buf), label)) == nil)
		return nil;
	k.k = buf;
	k.nk = p - buf;
	if(btlookup(&fs->snap, &k, &kv, buf, sizeof(buf)) != nil)
		return nil;
	assert(kv.nv == 1+8+4);
	gen = UNPACK64(kv.v + 1);
	flg = UNPACK32(kv.v + 1+8);
	if(mut != nil)
		*mut = !!(flg&Lmut);

	if((t = mallocz(sizeof(Tree), 1)) == nil)
		goto Error;
	if((p = packsnap(buf, sizeof(buf), gen)) == nil)
		goto Error;
	k.k = buf;
	k.nk = p - buf;
	if(btlookup(&fs->snap, &k, &kv, buf, sizeof(buf)) != nil)
		abort();
	if(unpacktree(t, kv.v, kv.nv) == nil)
		abort();
	t->memref = 1;
	t->memgen = aincv(&fs->nextgen, 1);
	return t;
Error:
	free(t);
	return nil;
}

/*
 * close snapshot, flushing and freeing in-memory
 * representation.
 */
void
closesnap(Tree *t)
{
	Bfree *f;
	ulong ge;

	if(t == nil || adec(&t->memref) != 0)
		return;
	if((f = malloc(sizeof(Bfree))) == nil)
		abort();
	f->op = DFtree;
	f->t = t;
	ge = agetl(&fs->epoch);
	f->next = fs->limbo[ge];
	fs->limbo[ge] = f;
}

char*
flushdlcache(int clear)
{
	Dlist *dl, *n;
	char *e;

	for(dl = fs->dlhead; dl != nil; dl = n){
		n = dl->cnext;
		if((e = dlsync(dl)) != nil)
			return e;
		if(clear){
			if(dl->ins != nil)
				dropblk(dl->ins);
			free(dl);
		}
	}
	if(clear){
		fs->dlhead = nil;
		fs->dltail = nil;
		memset(fs->dlcache, 0, fs->dlcmax*sizeof(Dlist*));
	}
	return nil;
}

/*
 * Marks a block as killed by the tree
 * t, which means that it will be free
 * for use after t is reclaimed.
 *
 * t must be an active snapshot with
 * no successors.
 */
int
killblk(Tree *t, Bptr bp)
{
	Dlist *dl;
	Blk *b;
	char *p;

	/* leak it and let the full collection clean it up */
	if(bp.gen <= t->base)
		return 0;
	if(t == &fs->snap)
		dl = &fs->snapdl;
	else if((dl = getdl(t->gen, bp.gen)) == nil)
 		return -1;
	if(dl->ins == nil || Logspc - dl->ins->logsz < Logslop){
		if((b = newblk(&fs->snap, Tdlist)) == nil){
			putdl(dl);
			return -1;
		}
		if(dl->ins != nil){
			enqueue(dl->ins);
			/* enqueuing updates the hashes */
			if(dl->ins->bp.addr == dl->tl.addr)
				dl->tl = dl->ins->bp;
			b->logp = dl->ins->bp;
		}else{
			dl->tl = b->bp;
			b->logp = (Bptr){-1, -1, -1};
		}
		cacheins(b);
		dl->hd = b->bp;
		dl->ins = b;
	}
	p = dl->ins->data + dl->ins->logsz;
	dl->ins->flag |=  Bdirty;
	dl->ins->logsz += 8;
	PACK64(p, bp.addr);
	if(t != &fs->snap)
		putdl(dl);
	return 0;
}