bwatch.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

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