/*  * This file is part of the UCB release of Plan 9. It is subject to the license * terms in the LICENSE file found in the top-level directory of this * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No * part of the UCB release of Plan 9, including this file, may be copied, * modified, propagated, or distributed except according to the terms contained * in the LICENSE file. */ #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 uinthash(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 voidfreeWEntry(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 voidaddChild(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;} voidbwatchReset(uchar score[VtScoreSize]){	vtLock(map.lk);	_bwatchResetParent(score);	_bwatchResetChild(score);	vtUnlock(map.lk);} voidbwatchInit(void){	map.lk = vtLockAlloc();	wp = privalloc();	*wp = nil;} voidbwatchSetBlockSize(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. */voidbwatchDependency(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 intdepth(uchar *s){	int d, x; 	d = -1;	while(s){		d++;		s = parent(s, &x);	}	return d;} static intlockConflicts(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 voidstop(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. */voidbwatchLock(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. */voidbwatchUnlock(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];}