ref: 24cb0baaaaffe67972734d90765b50b7ef6b45db
dir: /snap.c/
#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; if(t == nil || adec(&t->memref) != 0) return; if((f = malloc(sizeof(Bfree))) == nil) abort(); f->op = DFtree; f->t = t; limbo(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; }