Subversion Repositories planix.SVN

#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];

}