1 6f4d00ee 2013-09-23 0intro #include "stdinc.h"
2 6f4d00ee 2013-09-23 0intro #include "dat.h"
3 6f4d00ee 2013-09-23 0intro #include "fns.h"
4 6f4d00ee 2013-09-23 0intro #include "error.h"
7 6f4d00ee 2013-09-23 0intro * Lock watcher. Check that locking of blocks is always down.
9 6f4d00ee 2013-09-23 0intro * This is REALLY slow, and it won't work when the blocks aren't
10 6f4d00ee 2013-09-23 0intro * arranged in a tree (e.g., after the first snapshot). But it's great
11 6f4d00ee 2013-09-23 0intro * for debugging.
15 6f4d00ee 2013-09-23 0intro MaxLock = 16,
16 6f4d00ee 2013-09-23 0intro HashSize = 1009,
20 6f4d00ee 2013-09-23 0intro * Thread-specific watch state.
22 6f4d00ee 2013-09-23 0intro typedef struct WThread WThread;
23 6f4d00ee 2013-09-23 0intro struct WThread
25 6f4d00ee 2013-09-23 0intro Block *b[MaxLock]; /* blocks currently held */
30 6f4d00ee 2013-09-23 0intro typedef struct WMap WMap;
31 6f4d00ee 2013-09-23 0intro typedef struct WEntry WEntry;
33 6f4d00ee 2013-09-23 0intro struct WEntry
35 6f4d00ee 2013-09-23 0intro uchar c[VtScoreSize];
36 6f4d00ee 2013-09-23 0intro uchar p[VtScoreSize];
39 6f4d00ee 2013-09-23 0intro WEntry *cprev;
40 6f4d00ee 2013-09-23 0intro WEntry *cnext;
41 6f4d00ee 2013-09-23 0intro WEntry *pprev;
42 6f4d00ee 2013-09-23 0intro WEntry *pnext;
45 6f4d00ee 2013-09-23 0intro struct WMap
49 6f4d00ee 2013-09-23 0intro WEntry *hchild[HashSize];
50 6f4d00ee 2013-09-23 0intro WEntry *hparent[HashSize];
53 6f4d00ee 2013-09-23 0intro static WMap map;
54 6f4d00ee 2013-09-23 0intro static void **wp;
55 6f4d00ee 2013-09-23 0intro static uint blockSize;
56 6f4d00ee 2013-09-23 0intro static WEntry *pool;
57 6f4d00ee 2013-09-23 0intro uint bwatchDisabled;
59 6f4d00ee 2013-09-23 0intro static uint
60 6f4d00ee 2013-09-23 0intro hash(uchar score[VtScoreSize])
62 6f4d00ee 2013-09-23 0intro uint i, h;
65 6f4d00ee 2013-09-23 0intro for(i=0; i<VtScoreSize; i++)
66 6f4d00ee 2013-09-23 0intro h = h*37 + score[i];
67 6f4d00ee 2013-09-23 0intro return h%HashSize;
70 6f4d00ee 2013-09-23 0intro #include <pool.h>
71 6f4d00ee 2013-09-23 0intro static void
72 6f4d00ee 2013-09-23 0intro freeWEntry(WEntry *e)
74 6f4d00ee 2013-09-23 0intro memset(e, 0, sizeof(WEntry));
75 6f4d00ee 2013-09-23 0intro e->pnext = pool;
79 6f4d00ee 2013-09-23 0intro static WEntry*
80 6f4d00ee 2013-09-23 0intro allocWEntry(void)
83 6f4d00ee 2013-09-23 0intro WEntry *w;
86 6f4d00ee 2013-09-23 0intro if(w == nil){
87 4b576658 2013-09-23 0intro w = vtmallocz(1024*sizeof(WEntry));
88 6f4d00ee 2013-09-23 0intro for(i=0; i<1024; i++)
89 6f4d00ee 2013-09-23 0intro freeWEntry(&w[i]);
92 6f4d00ee 2013-09-23 0intro pool = w->pnext;
93 6f4d00ee 2013-09-23 0intro memset(w, 0, sizeof(WEntry));
98 6f4d00ee 2013-09-23 0intro * remove all dependencies with score as a parent
100 6f4d00ee 2013-09-23 0intro static void
101 6f4d00ee 2013-09-23 0intro _bwatchResetParent(uchar *score)
103 6f4d00ee 2013-09-23 0intro WEntry *w, *next;
106 6f4d00ee 2013-09-23 0intro h = hash(score);
107 6f4d00ee 2013-09-23 0intro for(w=map.hparent[h]; w; w=next){
108 6f4d00ee 2013-09-23 0intro next = w->pnext;
109 6f4d00ee 2013-09-23 0intro if(memcmp(w->p, score, VtScoreSize) == 0){
110 6f4d00ee 2013-09-23 0intro if(w->pnext)
111 6f4d00ee 2013-09-23 0intro w->pnext->pprev = w->pprev;
112 6f4d00ee 2013-09-23 0intro if(w->pprev)
113 6f4d00ee 2013-09-23 0intro w->pprev->pnext = w->pnext;
115 6f4d00ee 2013-09-23 0intro map.hparent[h] = w->pnext;
116 6f4d00ee 2013-09-23 0intro if(w->cnext)
117 6f4d00ee 2013-09-23 0intro w->cnext->cprev = w->cprev;
118 6f4d00ee 2013-09-23 0intro if(w->cprev)
119 6f4d00ee 2013-09-23 0intro w->cprev->cnext = w->cnext;
121 6f4d00ee 2013-09-23 0intro map.hchild[hash(w->c)] = w->cnext;
122 6f4d00ee 2013-09-23 0intro freeWEntry(w);
127 fa325e9b 2020-01-10 cross * and child
129 6f4d00ee 2013-09-23 0intro static void
130 6f4d00ee 2013-09-23 0intro _bwatchResetChild(uchar *score)
132 6f4d00ee 2013-09-23 0intro WEntry *w, *next;
135 6f4d00ee 2013-09-23 0intro h = hash(score);
136 6f4d00ee 2013-09-23 0intro for(w=map.hchild[h]; w; w=next){
137 6f4d00ee 2013-09-23 0intro next = w->cnext;
138 6f4d00ee 2013-09-23 0intro if(memcmp(w->c, score, VtScoreSize) == 0){
139 6f4d00ee 2013-09-23 0intro if(w->pnext)
140 6f4d00ee 2013-09-23 0intro w->pnext->pprev = w->pprev;
141 6f4d00ee 2013-09-23 0intro if(w->pprev)
142 6f4d00ee 2013-09-23 0intro w->pprev->pnext = w->pnext;
144 6f4d00ee 2013-09-23 0intro map.hparent[hash(w->p)] = w->pnext;
145 6f4d00ee 2013-09-23 0intro if(w->cnext)
146 6f4d00ee 2013-09-23 0intro w->cnext->cprev = w->cprev;
147 6f4d00ee 2013-09-23 0intro if(w->cprev)
148 6f4d00ee 2013-09-23 0intro w->cprev->cnext = w->cnext;
150 6f4d00ee 2013-09-23 0intro map.hchild[h] = w->cnext;
151 6f4d00ee 2013-09-23 0intro freeWEntry(w);
156 6f4d00ee 2013-09-23 0intro static uchar*
157 6f4d00ee 2013-09-23 0intro parent(uchar c[VtScoreSize], int *off)
159 6f4d00ee 2013-09-23 0intro WEntry *w;
162 6f4d00ee 2013-09-23 0intro h = hash(c);
163 6f4d00ee 2013-09-23 0intro for(w=map.hchild[h]; w; w=w->cnext)
164 6f4d00ee 2013-09-23 0intro if(memcmp(w->c, c, VtScoreSize) == 0){
165 6f4d00ee 2013-09-23 0intro *off = w->off;
166 6f4d00ee 2013-09-23 0intro return w->p;
168 6f4d00ee 2013-09-23 0intro return nil;
171 6f4d00ee 2013-09-23 0intro static void
172 6f4d00ee 2013-09-23 0intro addChild(uchar p[VtEntrySize], uchar c[VtEntrySize], int off)
175 6f4d00ee 2013-09-23 0intro WEntry *w;
177 6f4d00ee 2013-09-23 0intro w = allocWEntry();
178 6f4d00ee 2013-09-23 0intro memmove(w->p, p, VtScoreSize);
179 6f4d00ee 2013-09-23 0intro memmove(w->c, c, VtScoreSize);
180 6f4d00ee 2013-09-23 0intro w->off = off;
182 6f4d00ee 2013-09-23 0intro h = hash(p);
183 6f4d00ee 2013-09-23 0intro w->pnext = map.hparent[h];
184 6f4d00ee 2013-09-23 0intro if(w->pnext)
185 6f4d00ee 2013-09-23 0intro w->pnext->pprev = w;
186 6f4d00ee 2013-09-23 0intro map.hparent[h] = w;
188 6f4d00ee 2013-09-23 0intro h = hash(c);
189 6f4d00ee 2013-09-23 0intro w->cnext = map.hchild[h];
190 6f4d00ee 2013-09-23 0intro if(w->cnext)
191 6f4d00ee 2013-09-23 0intro w->cnext->cprev = w;
192 6f4d00ee 2013-09-23 0intro map.hchild[h] = w;
196 6f4d00ee 2013-09-23 0intro bwatchReset(uchar score[VtScoreSize])
198 4b576658 2013-09-23 0intro qlock(&map.lk);
199 6f4d00ee 2013-09-23 0intro _bwatchResetParent(score);
200 6f4d00ee 2013-09-23 0intro _bwatchResetChild(score);
201 4b576658 2013-09-23 0intro qunlock(&map.lk);
205 6f4d00ee 2013-09-23 0intro bwatchInit(void)
207 6f4d00ee 2013-09-23 0intro wp = privalloc();
208 6f4d00ee 2013-09-23 0intro *wp = nil;
212 6f4d00ee 2013-09-23 0intro bwatchSetBlockSize(uint bs)
214 6f4d00ee 2013-09-23 0intro blockSize = bs;
217 6f4d00ee 2013-09-23 0intro static WThread*
218 6f4d00ee 2013-09-23 0intro getWThread(void)
220 6f4d00ee 2013-09-23 0intro WThread *w;
223 6f4d00ee 2013-09-23 0intro if(w == nil || w->pid != getpid()){
224 4b576658 2013-09-23 0intro w = vtmallocz(sizeof(WThread));
226 6f4d00ee 2013-09-23 0intro w->pid = getpid();
228 6f4d00ee 2013-09-23 0intro return w;
232 6f4d00ee 2013-09-23 0intro * Derive dependencies from the contents of b.
235 6f4d00ee 2013-09-23 0intro bwatchDependency(Block *b)
237 6f4d00ee 2013-09-23 0intro int i, epb, ppb;
240 6f4d00ee 2013-09-23 0intro if(bwatchDisabled)
243 4b576658 2013-09-23 0intro qlock(&map.lk);
244 6f4d00ee 2013-09-23 0intro _bwatchResetParent(b->score);
246 6f4d00ee 2013-09-23 0intro switch(b->l.type){
247 6f4d00ee 2013-09-23 0intro case BtData:
250 6f4d00ee 2013-09-23 0intro case BtDir:
251 6f4d00ee 2013-09-23 0intro epb = blockSize / VtEntrySize;
252 6f4d00ee 2013-09-23 0intro for(i=0; i<epb; i++){
253 6f4d00ee 2013-09-23 0intro entryUnpack(&e, b->data, i);
254 6f4d00ee 2013-09-23 0intro if(!(e.flags & VtEntryActive))
255 6f4d00ee 2013-09-23 0intro continue;
256 6f4d00ee 2013-09-23 0intro addChild(b->score, e.score, i);
261 6f4d00ee 2013-09-23 0intro ppb = blockSize / VtScoreSize;
262 6f4d00ee 2013-09-23 0intro for(i=0; i<ppb; i++)
263 6f4d00ee 2013-09-23 0intro addChild(b->score, b->data+i*VtScoreSize, i);
266 4b576658 2013-09-23 0intro qunlock(&map.lk);
269 6f4d00ee 2013-09-23 0intro static int
270 6f4d00ee 2013-09-23 0intro depth(uchar *s)
272 6f4d00ee 2013-09-23 0intro int d, x;
275 6f4d00ee 2013-09-23 0intro while(s){
277 6f4d00ee 2013-09-23 0intro s = parent(s, &x);
279 6f4d00ee 2013-09-23 0intro return d;
282 6f4d00ee 2013-09-23 0intro static int
283 6f4d00ee 2013-09-23 0intro lockConflicts(uchar xhave[VtScoreSize], uchar xwant[VtScoreSize])
285 6f4d00ee 2013-09-23 0intro uchar *have, *want;
286 6f4d00ee 2013-09-23 0intro int havedepth, wantdepth, havepos, wantpos;
288 6f4d00ee 2013-09-23 0intro have = xhave;
289 6f4d00ee 2013-09-23 0intro want = xwant;
291 6f4d00ee 2013-09-23 0intro havedepth = depth(have);
292 6f4d00ee 2013-09-23 0intro wantdepth = depth(want);
295 6f4d00ee 2013-09-23 0intro * walk one or the other up until they're both
296 6f4d00ee 2013-09-23 0intro * at the same level.
298 6f4d00ee 2013-09-23 0intro havepos = -1;
299 6f4d00ee 2013-09-23 0intro wantpos = -1;
300 6f4d00ee 2013-09-23 0intro have = xhave;
301 6f4d00ee 2013-09-23 0intro want = xwant;
302 6f4d00ee 2013-09-23 0intro while(wantdepth > havedepth){
303 6f4d00ee 2013-09-23 0intro wantdepth--;
304 6f4d00ee 2013-09-23 0intro want = parent(want, &wantpos);
306 6f4d00ee 2013-09-23 0intro while(havedepth > wantdepth){
307 6f4d00ee 2013-09-23 0intro havedepth--;
308 6f4d00ee 2013-09-23 0intro have = parent(have, &havepos);
312 6f4d00ee 2013-09-23 0intro * walk them up simultaneously until we reach
313 6f4d00ee 2013-09-23 0intro * a common ancestor.
315 6f4d00ee 2013-09-23 0intro while(have && want && memcmp(have, want, VtScoreSize) != 0){
316 6f4d00ee 2013-09-23 0intro have = parent(have, &havepos);
317 6f4d00ee 2013-09-23 0intro want = parent(want, &wantpos);
321 6f4d00ee 2013-09-23 0intro * not part of same tree. happens mainly with
322 6f4d00ee 2013-09-23 0intro * newly allocated blocks.
324 6f4d00ee 2013-09-23 0intro if(!have || !want)
325 6f4d00ee 2013-09-23 0intro return 0;
328 6f4d00ee 2013-09-23 0intro * never walked want: means we want to lock
329 6f4d00ee 2013-09-23 0intro * an ancestor of have. no no.
331 6f4d00ee 2013-09-23 0intro if(wantpos == -1)
332 6f4d00ee 2013-09-23 0intro return 1;
335 6f4d00ee 2013-09-23 0intro * never walked have: means we want to lock a
336 6f4d00ee 2013-09-23 0intro * child of have. that's okay.
338 6f4d00ee 2013-09-23 0intro if(havepos == -1)
339 6f4d00ee 2013-09-23 0intro return 0;
342 6f4d00ee 2013-09-23 0intro * walked both: they're from different places in the tree.
343 6f4d00ee 2013-09-23 0intro * require that the left one be locked before the right one.
344 6f4d00ee 2013-09-23 0intro * (this is questionable, but it puts a total order on the block tree).
346 6f4d00ee 2013-09-23 0intro return havepos < wantpos;
349 6f4d00ee 2013-09-23 0intro static void
350 6f4d00ee 2013-09-23 0intro stop(void)
353 6f4d00ee 2013-09-23 0intro char buf[32];
355 6f4d00ee 2013-09-23 0intro snprint(buf, sizeof buf, "#p/%d/ctl", getpid());
356 6f4d00ee 2013-09-23 0intro fd = open(buf, OWRITE);
357 6f4d00ee 2013-09-23 0intro write(fd, "stop", 4);
358 6f4d00ee 2013-09-23 0intro close(fd);
362 6f4d00ee 2013-09-23 0intro * Check whether the calling thread can validly lock b.
363 6f4d00ee 2013-09-23 0intro * That is, check that the calling thread doesn't hold
364 6f4d00ee 2013-09-23 0intro * locks for any of b's children.
367 6f4d00ee 2013-09-23 0intro bwatchLock(Block *b)
370 6f4d00ee 2013-09-23 0intro WThread *w;
372 6f4d00ee 2013-09-23 0intro if(bwatchDisabled)
375 6f4d00ee 2013-09-23 0intro if(b->part != PartData)
378 4b576658 2013-09-23 0intro qlock(&map.lk);
379 6f4d00ee 2013-09-23 0intro w = getWThread();
380 6f4d00ee 2013-09-23 0intro for(i=0; i<w->nb; i++){
381 6f4d00ee 2013-09-23 0intro if(lockConflicts(w->b[i]->score, b->score)){
382 6f4d00ee 2013-09-23 0intro fprint(2, "%d: have block %V; shouldn't lock %V\n",
383 6f4d00ee 2013-09-23 0intro w->pid, w->b[i]->score, b->score);
387 4b576658 2013-09-23 0intro qunlock(&map.lk);
388 6f4d00ee 2013-09-23 0intro if(w->nb >= MaxLock){
389 6f4d00ee 2013-09-23 0intro fprint(2, "%d: too many blocks held\n", w->pid);
392 6f4d00ee 2013-09-23 0intro w->b[w->nb++] = b;
396 6f4d00ee 2013-09-23 0intro * Note that the calling thread is about to unlock b.
399 6f4d00ee 2013-09-23 0intro bwatchUnlock(Block *b)
402 6f4d00ee 2013-09-23 0intro WThread *w;
404 6f4d00ee 2013-09-23 0intro if(bwatchDisabled)
407 6f4d00ee 2013-09-23 0intro if(b->part != PartData)
410 6f4d00ee 2013-09-23 0intro w = getWThread();
411 6f4d00ee 2013-09-23 0intro for(i=0; i<w->nb; i++)
412 6f4d00ee 2013-09-23 0intro if(w->b[i] == b)
414 6f4d00ee 2013-09-23 0intro if(i>=w->nb){
415 6f4d00ee 2013-09-23 0intro fprint(2, "%d: unlock of unlocked block %V\n", w->pid, b->score);
418 6f4d00ee 2013-09-23 0intro w->b[i] = w->b[--w->nb];