From 6f4d00ee45693290fae042b27536b54f77b96acd Mon Sep 17 00:00:00 2001 From: David du Colombier <0intro@gmail.com> Date: Mon, 23 Sep 2013 23:00:39 +0200 Subject: fossil: import from plan 9 R=rsc https://codereview.appspot.com/7988047 --- src/cmd/fossil/bwatch.c | 421 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 421 insertions(+) create mode 100644 src/cmd/fossil/bwatch.c (limited to 'src/cmd/fossil/bwatch.c') diff --git a/src/cmd/fossil/bwatch.c b/src/cmd/fossil/bwatch.c new file mode 100644 index 00000000..51deb762 --- /dev/null +++ b/src/cmd/fossil/bwatch.c @@ -0,0 +1,421 @@ +#include "stdinc.h" +#include "dat.h" +#include "fns.h" +#include "error.h" + +/* + * Lock watcher. Check that locking of blocks is always down. + * + * This is REALLY slow, and it won't work when the blocks aren't + * arranged in a tree (e.g., after the first snapshot). But it's great + * for debugging. + */ +enum +{ + MaxLock = 16, + HashSize = 1009, +}; + +/* + * Thread-specific watch state. + */ +typedef struct WThread WThread; +struct WThread +{ + Block *b[MaxLock]; /* blocks currently held */ + uint nb; + uint pid; +}; + +typedef struct WMap WMap; +typedef struct WEntry WEntry; + +struct WEntry +{ + uchar c[VtScoreSize]; + uchar p[VtScoreSize]; + int off; + + WEntry *cprev; + WEntry *cnext; + WEntry *pprev; + WEntry *pnext; +}; + +struct WMap +{ + VtLock *lk; + + WEntry *hchild[HashSize]; + WEntry *hparent[HashSize]; +}; + +static WMap map; +static void **wp; +static uint blockSize; +static WEntry *pool; +uint bwatchDisabled; + +static uint +hash(uchar score[VtScoreSize]) +{ + uint i, h; + + h = 0; + for(i=0; i +static void +freeWEntry(WEntry *e) +{ + memset(e, 0, sizeof(WEntry)); + e->pnext = pool; + pool = e; +} + +static WEntry* +allocWEntry(void) +{ + int i; + WEntry *w; + + w = pool; + if(w == nil){ + w = vtMemAllocZ(1024*sizeof(WEntry)); + for(i=0; i<1024; i++) + freeWEntry(&w[i]); + w = pool; + } + pool = w->pnext; + memset(w, 0, sizeof(WEntry)); + return w; +} + +/* + * remove all dependencies with score as a parent + */ +static void +_bwatchResetParent(uchar *score) +{ + WEntry *w, *next; + uint h; + + h = hash(score); + for(w=map.hparent[h]; w; w=next){ + next = w->pnext; + if(memcmp(w->p, score, VtScoreSize) == 0){ + if(w->pnext) + w->pnext->pprev = w->pprev; + if(w->pprev) + w->pprev->pnext = w->pnext; + else + map.hparent[h] = w->pnext; + if(w->cnext) + w->cnext->cprev = w->cprev; + if(w->cprev) + w->cprev->cnext = w->cnext; + else + map.hchild[hash(w->c)] = w->cnext; + freeWEntry(w); + } + } +} +/* + * and child + */ +static void +_bwatchResetChild(uchar *score) +{ + WEntry *w, *next; + uint h; + + h = hash(score); + for(w=map.hchild[h]; w; w=next){ + next = w->cnext; + if(memcmp(w->c, score, VtScoreSize) == 0){ + if(w->pnext) + w->pnext->pprev = w->pprev; + if(w->pprev) + w->pprev->pnext = w->pnext; + else + map.hparent[hash(w->p)] = w->pnext; + if(w->cnext) + w->cnext->cprev = w->cprev; + if(w->cprev) + w->cprev->cnext = w->cnext; + else + map.hchild[h] = w->cnext; + freeWEntry(w); + } + } +} + +static uchar* +parent(uchar c[VtScoreSize], int *off) +{ + WEntry *w; + uint h; + + h = hash(c); + for(w=map.hchild[h]; w; w=w->cnext) + if(memcmp(w->c, c, VtScoreSize) == 0){ + *off = w->off; + return w->p; + } + return nil; +} + +static void +addChild(uchar p[VtEntrySize], uchar c[VtEntrySize], int off) +{ + uint h; + WEntry *w; + + w = allocWEntry(); + memmove(w->p, p, VtScoreSize); + memmove(w->c, c, VtScoreSize); + w->off = off; + + h = hash(p); + w->pnext = map.hparent[h]; + if(w->pnext) + w->pnext->pprev = w; + map.hparent[h] = w; + + h = hash(c); + w->cnext = map.hchild[h]; + if(w->cnext) + w->cnext->cprev = w; + map.hchild[h] = w; +} + +void +bwatchReset(uchar score[VtScoreSize]) +{ + vtLock(map.lk); + _bwatchResetParent(score); + _bwatchResetChild(score); + vtUnlock(map.lk); +} + +void +bwatchInit(void) +{ + map.lk = vtLockAlloc(); + wp = privalloc(); + *wp = nil; +} + +void +bwatchSetBlockSize(uint bs) +{ + blockSize = bs; +} + +static WThread* +getWThread(void) +{ + WThread *w; + + w = *wp; + if(w == nil || w->pid != getpid()){ + w = vtMemAllocZ(sizeof(WThread)); + *wp = w; + w->pid = getpid(); + } + return w; +} + +/* + * Derive dependencies from the contents of b. + */ +void +bwatchDependency(Block *b) +{ + int i, epb, ppb; + Entry e; + + if(bwatchDisabled) + return; + + vtLock(map.lk); + _bwatchResetParent(b->score); + + switch(b->l.type){ + case BtData: + break; + + case BtDir: + epb = blockSize / VtEntrySize; + for(i=0; idata, i); + if(!(e.flags & VtEntryActive)) + continue; + addChild(b->score, e.score, i); + } + break; + + default: + ppb = blockSize / VtScoreSize; + for(i=0; iscore, b->data+i*VtScoreSize, i); + break; + } + vtUnlock(map.lk); +} + +static int +depth(uchar *s) +{ + int d, x; + + d = -1; + while(s){ + d++; + s = parent(s, &x); + } + return d; +} + +static int +lockConflicts(uchar xhave[VtScoreSize], uchar xwant[VtScoreSize]) +{ + uchar *have, *want; + int havedepth, wantdepth, havepos, wantpos; + + have = xhave; + want = xwant; + + havedepth = depth(have); + wantdepth = depth(want); + + /* + * walk one or the other up until they're both + * at the same level. + */ + havepos = -1; + wantpos = -1; + have = xhave; + want = xwant; + while(wantdepth > havedepth){ + wantdepth--; + want = parent(want, &wantpos); + } + while(havedepth > wantdepth){ + havedepth--; + have = parent(have, &havepos); + } + + /* + * walk them up simultaneously until we reach + * a common ancestor. + */ + while(have && want && memcmp(have, want, VtScoreSize) != 0){ + have = parent(have, &havepos); + want = parent(want, &wantpos); + } + + /* + * not part of same tree. happens mainly with + * newly allocated blocks. + */ + if(!have || !want) + return 0; + + /* + * never walked want: means we want to lock + * an ancestor of have. no no. + */ + if(wantpos == -1) + return 1; + + /* + * never walked have: means we want to lock a + * child of have. that's okay. + */ + if(havepos == -1) + return 0; + + /* + * walked both: they're from different places in the tree. + * require that the left one be locked before the right one. + * (this is questionable, but it puts a total order on the block tree). + */ + return havepos < wantpos; +} + +static void +stop(void) +{ + int fd; + char buf[32]; + + snprint(buf, sizeof buf, "#p/%d/ctl", getpid()); + fd = open(buf, OWRITE); + write(fd, "stop", 4); + close(fd); +} + +/* + * Check whether the calling thread can validly lock b. + * That is, check that the calling thread doesn't hold + * locks for any of b's children. + */ +void +bwatchLock(Block *b) +{ + int i; + WThread *w; + + if(bwatchDisabled) + return; + + if(b->part != PartData) + return; + + vtLock(map.lk); + w = getWThread(); + for(i=0; inb; i++){ + if(lockConflicts(w->b[i]->score, b->score)){ + fprint(2, "%d: have block %V; shouldn't lock %V\n", + w->pid, w->b[i]->score, b->score); + stop(); + } + } + vtUnlock(map.lk); + if(w->nb >= MaxLock){ + fprint(2, "%d: too many blocks held\n", w->pid); + stop(); + }else + w->b[w->nb++] = b; +} + +/* + * Note that the calling thread is about to unlock b. + */ +void +bwatchUnlock(Block *b) +{ + int i; + WThread *w; + + if(bwatchDisabled) + return; + + if(b->part != PartData) + return; + + w = getWThread(); + for(i=0; inb; i++) + if(w->b[i] == b) + break; + if(i>=w->nb){ + fprint(2, "%d: unlock of unlocked block %V\n", w->pid, b->score); + stop(); + }else + w->b[i] = w->b[--w->nb]; +} + -- cgit v1.2.3