Rev 2 | Blame | Compare with Previous | Last modification | View Log | RSS feed
#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];
}