shithub: gefs

ref: 8585477a0d205a33c9d89a69f73c7ebf4727cd72
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))
		return nil;

	enqueue(dl->ins);
	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)
{
	char *e, buf[Kvmax];
	Bptr bp, fb;
	Msg m;
	Blk *b;
	char *p;

	bp = dl->hd;
	if(dl != &fs->snapdl){
		m.op = Odelete;
		dlist2kv(dl, &m, buf, sizeof(buf));
		if((e = btupsert(&fs->snap, &m, 1)) != nil)
			return e;
	}
	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 merge, vlong gen, vlong bgen)
{
	char *e, buf[2][Kvmax];
	Dlist *d, *m;
	Msg msg[2];
	Blk *b;

	if((d = getdl(merge, bgen)) == nil)
		return Enomem;
	if((m = getdl(gen, bgen)) == nil)
		return Enomem;
	/*
	 * If the dest dlist didn't exist,
	 * just move the merge dlist over
	 * and be done with it, otherwise
	 * chain onto the existing dlist
	 * tail.
	 */
	if(d->hd.addr == -1){
		assert(d->ins == nil);
		d->hd = m->hd;
		d->tl = m->tl;
		d->ins = m->ins;
		if(d->ins != nil)
			holdblk(d->ins);
	}else{
		if(m->ins != nil && checkflag(m->ins, Bdirty))
			enqueue(m->ins);
		if(d->tl.addr == d->ins->bp.addr)
			b = holdblk(d->ins);
		else
			b = getblk(d->tl, 0);
		if(b == nil)
			return Efs;
		b->logp = m->hd;
		setflag(b, Bdirty);
		enqueue(b);
		dropblk(b);
	}
	msg[0].op = Odelete;
	dlist2kv(m, &msg[0], buf[0], sizeof(buf[0]));
	msg[1].op = Oinsert;
	dlist2kv(d, &msg[1], buf[1], sizeof(buf[1]));
	e = btupsert(&fs->snap, msg, 2);
	putdl(m);
	putdl(d);
	return e;
}

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

	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);

		if(succ != -1 && dl.bgen <= prev)
			e = mergedl(succ, dl.gen, dl.bgen);
		else if(dl.bgen <= prev)
			e = mergedl(prev, dl.gen, dl.bgen);
		else
			e = freedl(&dl, 1);
		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[4][Kvmax], *e;
	int nm, deltree;
	Mount *mnt;
	Msg m[4];

	nm = 0;
	deltree = 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 = packlbl(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->nref <= 1){
		deltree = 1;
		m[nm].op = Orelink;
		retag2kv(t->pred, succ, 0, 0, &m[nm], buf[nm], sizeof(buf[nm]));
		nm++;
		if(t->succ != -1){
			m[nm].op = Oreprev;
			retag2kv(t->succ, t->pred, 0, 0, &m[nm], buf[nm], sizeof(buf[nm]));
			nm++;
		}
		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++;
	}
	assert(nm <= nelem(m));
	if((e = flushdlcache(1)) != nil)
		return e;
	if((e = btupsert(&fs->snap, m, nm)) != nil)
		return e;
	if((e = reclaimblocks(t->gen, succ, t->pred)) != nil)
		return e;
	if(deltree){
		for(mnt = fs->mounts; mnt != nil; mnt = mnt->next){
			if(mnt->root->gen == t->succ)
				mnt->root->pred = t->pred;
			if(mnt->root->gen == t->pred)
				mnt->root->succ = t->succ;
		}
	}
	return nil;
}

/*
 * Attaches a label to a tree, incrementing
 * its reference count. This labelled snapshot
 * will show up in the dump.
 */
char*
tagsnap(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->nref = 0;
		n->ht = t->ht;
		n->bp = t->bp;
		n->succ = -1;
		n->pred = t->gen;
		n->base = t->gen;
		n->gen = aincv(&fs->nextgen, 1);
		n->memgen = aincv(&fs->nextgen, 1);

		t->nref++;
		m[i].op = Orelink;
		retag2kv(t->gen, t->succ, 0, 1, &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++;
		m[i].op = Oinsert;
		tree2kv(n, &m[i], buf[i], sizeof(buf[i]));
		i++;
	}else{
		t->nlbl++;
		m[i].op = Orelink;
		retag2kv(t->gen, t->succ, 1, 0, &m[i], buf[i], sizeof(buf[i]));
		i++;

		m[i].op = Oinsert;
		t->pred = t->gen;
		t->nlbl++;
		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;
	int i;

	if(!o->dirty)
		return nil;

	/* update the old kvp */
	o->nlbl--;
	o->nref++;

	/* create the new one */

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

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

	i = 0;
	m[i].op = Orelink;
	if(o->nlbl == 0 && o->nref == 1){
		t->pred = o->pred;
		retag2kv(t->pred, t->gen, 0, 0, &m[i], buf[i], sizeof(buf[i]));
	}else{
		t->pred = o->gen;
		retag2kv(t->pred, t->gen, -1, 1, &m[i], buf[i], sizeof(buf[i]));
	}
	i++;

	m[i].op = Oinsert;
	tree2kv(t, &m[i], buf[i], sizeof(buf[i]));
	i++;
	m[i].op = Oinsert;
	lbl2kv(lbl, t->gen, Lmut, &m[i], buf[i], sizeof(buf[i]));
	i++;
	if((e = btupsert(&fs->snap, m, i)) != 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->nref == 1)
		delsnap(o, t->gen, 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 = packlbl(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);
		if(dl->tl.addr == -1)
			dl->tl = b->bp;
		b->logp = dl->hd;
		dl->hd = b->bp;
		dl->ins = b;
		cacheins(b);
	}
	p = dl->ins->data + dl->ins->logsz;
	dl->ins->logsz += 8;
	setflag(dl->ins, Bdirty);
	PACK64(p, bp.addr);
	if(t != &fs->snap)
		putdl(dl);
	return 0;
}