1 files changed, 421 insertions, 0 deletions
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<VtScoreSize; i++)
+		h = h*37 + score[i];
+	return h%HashSize;
+}
+
+#include <pool.h>
+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; i<epb; i++){
+			entryUnpack(&e, b->data, i);
+			if(!(e.flags & VtEntryActive))
+				continue;
+			addChild(b->score, e.score, i);
+		}
+		break;
+
+	default:
+		ppb = blockSize / VtScoreSize;
+		for(i=0; i<ppb; i++)
+			addChild(b->score, 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; i<w->nb; 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; i<w->nb; 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];
+}
+