xref: /plan9/sys/src/cmd/fossil/bwatch.c (revision 5e96a66c77eb9140492ca53f857cbbf108e128ed)
1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 #include "error.h"
5 
6 /*
7  * Lock watcher.  Check that locking of blocks is always down.
8  *
9  * This is REALLY slow, and it won't work when the blocks aren't
10  * arranged in a tree (e.g., after the first snapshot).  But it's great
11  * for debugging.
12  */
13 enum
14 {
15 	MaxLock = 16,
16 	HashSize = 1009,
17 };
18 
19 /*
20  * Thread-specific watch state.
21  */
22 typedef struct WThread WThread;
23 struct WThread
24 {
25 	Block *b[MaxLock];	/* blocks currently held */
26 	uint nb;
27 	uint pid;
28 };
29 
30 typedef struct WMap WMap;
31 typedef struct WEntry WEntry;
32 
33 struct WEntry
34 {
35 	uchar c[VtScoreSize];
36 	uchar p[VtScoreSize];
37 	int off;
38 
39 	WEntry *cprev;
40 	WEntry *cnext;
41 	WEntry *pprev;
42 	WEntry *pnext;
43 };
44 
45 struct WMap
46 {
47 	VtLock *lk;
48 
49 	WEntry *hchild[HashSize];
50 	WEntry *hparent[HashSize];
51 };
52 
53 static WMap map;
54 static void **wp;
55 static uint blockSize;
56 static WEntry *pool;
57 uint bwatchDisabled;
58 
59 static uint
hash(uchar score[VtScoreSize])60 hash(uchar score[VtScoreSize])
61 {
62 	uint i, h;
63 
64 	h = 0;
65 	for(i=0; i<VtScoreSize; i++)
66 		h = h*37 + score[i];
67 	return h%HashSize;
68 }
69 
70 #include <pool.h>
71 static void
freeWEntry(WEntry * e)72 freeWEntry(WEntry *e)
73 {
74 	memset(e, 0, sizeof(WEntry));
75 	e->pnext = pool;
76 	pool = e;
77 }
78 
79 static WEntry*
allocWEntry(void)80 allocWEntry(void)
81 {
82 	int i;
83 	WEntry *w;
84 
85 	w = pool;
86 	if(w == nil){
87 		w = vtMemAllocZ(1024*sizeof(WEntry));
88 		for(i=0; i<1024; i++)
89 			freeWEntry(&w[i]);
90 		w = pool;
91 	}
92 	pool = w->pnext;
93 	memset(w, 0, sizeof(WEntry));
94 	return w;
95 }
96 
97 /*
98  * remove all dependencies with score as a parent
99  */
100 static void
_bwatchResetParent(uchar * score)101 _bwatchResetParent(uchar *score)
102 {
103 	WEntry *w, *next;
104 	uint h;
105 
106 	h = hash(score);
107 	for(w=map.hparent[h]; w; w=next){
108 		next = w->pnext;
109 		if(memcmp(w->p, score, VtScoreSize) == 0){
110 			if(w->pnext)
111 				w->pnext->pprev = w->pprev;
112 			if(w->pprev)
113 				w->pprev->pnext = w->pnext;
114 			else
115 				map.hparent[h] = w->pnext;
116 			if(w->cnext)
117 				w->cnext->cprev = w->cprev;
118 			if(w->cprev)
119 				w->cprev->cnext = w->cnext;
120 			else
121 				map.hchild[hash(w->c)] = w->cnext;
122 			freeWEntry(w);
123 		}
124 	}
125 }
126 /*
127  * and child
128  */
129 static void
_bwatchResetChild(uchar * score)130 _bwatchResetChild(uchar *score)
131 {
132 	WEntry *w, *next;
133 	uint h;
134 
135 	h = hash(score);
136 	for(w=map.hchild[h]; w; w=next){
137 		next = w->cnext;
138 		if(memcmp(w->c, score, VtScoreSize) == 0){
139 			if(w->pnext)
140 				w->pnext->pprev = w->pprev;
141 			if(w->pprev)
142 				w->pprev->pnext = w->pnext;
143 			else
144 				map.hparent[hash(w->p)] = w->pnext;
145 			if(w->cnext)
146 				w->cnext->cprev = w->cprev;
147 			if(w->cprev)
148 				w->cprev->cnext = w->cnext;
149 			else
150 				map.hchild[h] = w->cnext;
151 			freeWEntry(w);
152 		}
153 	}
154 }
155 
156 static uchar*
parent(uchar c[VtScoreSize],int * off)157 parent(uchar c[VtScoreSize], int *off)
158 {
159 	WEntry *w;
160 	uint h;
161 
162 	h = hash(c);
163 	for(w=map.hchild[h]; w; w=w->cnext)
164 		if(memcmp(w->c, c, VtScoreSize) == 0){
165 			*off = w->off;
166 			return w->p;
167 		}
168 	return nil;
169 }
170 
171 static void
addChild(uchar p[VtEntrySize],uchar c[VtEntrySize],int off)172 addChild(uchar p[VtEntrySize], uchar c[VtEntrySize], int off)
173 {
174 	uint h;
175 	WEntry *w;
176 
177 	w = allocWEntry();
178 	memmove(w->p, p, VtScoreSize);
179 	memmove(w->c, c, VtScoreSize);
180 	w->off = off;
181 
182 	h = hash(p);
183 	w->pnext = map.hparent[h];
184 	if(w->pnext)
185 		w->pnext->pprev = w;
186 	map.hparent[h] = w;
187 
188 	h = hash(c);
189 	w->cnext = map.hchild[h];
190 	if(w->cnext)
191 		w->cnext->cprev = w;
192 	map.hchild[h] = w;
193 }
194 
195 void
bwatchReset(uchar score[VtScoreSize])196 bwatchReset(uchar score[VtScoreSize])
197 {
198 	vtLock(map.lk);
199 	_bwatchResetParent(score);
200 	_bwatchResetChild(score);
201 	vtUnlock(map.lk);
202 }
203 
204 void
bwatchInit(void)205 bwatchInit(void)
206 {
207 	map.lk = vtLockAlloc();
208 	wp = privalloc();
209 	*wp = nil;
210 }
211 
212 void
bwatchSetBlockSize(uint bs)213 bwatchSetBlockSize(uint bs)
214 {
215 	blockSize = bs;
216 }
217 
218 static WThread*
getWThread(void)219 getWThread(void)
220 {
221 	WThread *w;
222 
223 	w = *wp;
224 	if(w == nil || w->pid != getpid()){
225 		w = vtMemAllocZ(sizeof(WThread));
226 		*wp = w;
227 		w->pid = getpid();
228 	}
229 	return w;
230 }
231 
232 /*
233  * Derive dependencies from the contents of b.
234  */
235 void
bwatchDependency(Block * b)236 bwatchDependency(Block *b)
237 {
238 	int i, epb, ppb;
239 	Entry e;
240 
241 	if(bwatchDisabled)
242 		return;
243 
244 	vtLock(map.lk);
245 	_bwatchResetParent(b->score);
246 
247 	switch(b->l.type){
248 	case BtData:
249 		break;
250 
251 	case BtDir:
252 		epb = blockSize / VtEntrySize;
253 		for(i=0; i<epb; i++){
254 			entryUnpack(&e, b->data, i);
255 			if(!(e.flags & VtEntryActive))
256 				continue;
257 			addChild(b->score, e.score, i);
258 		}
259 		break;
260 
261 	default:
262 		ppb = blockSize / VtScoreSize;
263 		for(i=0; i<ppb; i++)
264 			addChild(b->score, b->data+i*VtScoreSize, i);
265 		break;
266 	}
267 	vtUnlock(map.lk);
268 }
269 
270 static int
depth(uchar * s)271 depth(uchar *s)
272 {
273 	int d, x;
274 
275 	d = -1;
276 	while(s){
277 		d++;
278 		s = parent(s, &x);
279 	}
280 	return d;
281 }
282 
283 static int
lockConflicts(uchar xhave[VtScoreSize],uchar xwant[VtScoreSize])284 lockConflicts(uchar xhave[VtScoreSize], uchar xwant[VtScoreSize])
285 {
286 	uchar *have, *want;
287 	int havedepth, wantdepth, havepos, wantpos;
288 
289 	have = xhave;
290 	want = xwant;
291 
292 	havedepth = depth(have);
293 	wantdepth = depth(want);
294 
295 	/*
296 	 * walk one or the other up until they're both
297  	 * at the same level.
298 	 */
299 	havepos = -1;
300 	wantpos = -1;
301 	have = xhave;
302 	want = xwant;
303 	while(wantdepth > havedepth){
304 		wantdepth--;
305 		want = parent(want, &wantpos);
306 	}
307 	while(havedepth > wantdepth){
308 		havedepth--;
309 		have = parent(have, &havepos);
310 	}
311 
312 	/*
313 	 * walk them up simultaneously until we reach
314 	 * a common ancestor.
315 	 */
316 	while(have && want && memcmp(have, want, VtScoreSize) != 0){
317 		have = parent(have, &havepos);
318 		want = parent(want, &wantpos);
319 	}
320 
321 	/*
322 	 * not part of same tree.  happens mainly with
323 	 * newly allocated blocks.
324 	 */
325 	if(!have || !want)
326 		return 0;
327 
328 	/*
329 	 * never walked want: means we want to lock
330 	 * an ancestor of have.  no no.
331 	 */
332 	if(wantpos == -1)
333 		return 1;
334 
335 	/*
336 	 * never walked have: means we want to lock a
337 	 * child of have.  that's okay.
338 	 */
339 	if(havepos == -1)
340 		return 0;
341 
342 	/*
343 	 * walked both: they're from different places in the tree.
344 	 * require that the left one be locked before the right one.
345 	 * (this is questionable, but it puts a total order on the block tree).
346 	 */
347 	return havepos < wantpos;
348 }
349 
350 static void
stop(void)351 stop(void)
352 {
353 	int fd;
354 	char buf[32];
355 
356 	snprint(buf, sizeof buf, "#p/%d/ctl", getpid());
357 	fd = open(buf, OWRITE);
358 	write(fd, "stop", 4);
359 	close(fd);
360 }
361 
362 /*
363  * Check whether the calling thread can validly lock b.
364  * That is, check that the calling thread doesn't hold
365  * locks for any of b's children.
366  */
367 void
bwatchLock(Block * b)368 bwatchLock(Block *b)
369 {
370 	int i;
371 	WThread *w;
372 
373 	if(bwatchDisabled)
374 		return;
375 
376 	if(b->part != PartData)
377 		return;
378 
379 	vtLock(map.lk);
380 	w = getWThread();
381 	for(i=0; i<w->nb; i++){
382 		if(lockConflicts(w->b[i]->score, b->score)){
383 			fprint(2, "%d: have block %V; shouldn't lock %V\n",
384 				w->pid, w->b[i]->score, b->score);
385 			stop();
386 		}
387 	}
388 	vtUnlock(map.lk);
389 	if(w->nb >= MaxLock){
390 		fprint(2, "%d: too many blocks held\n", w->pid);
391 		stop();
392 	}else
393 		w->b[w->nb++] = b;
394 }
395 
396 /*
397  * Note that the calling thread is about to unlock b.
398  */
399 void
bwatchUnlock(Block * b)400 bwatchUnlock(Block *b)
401 {
402 	int i;
403 	WThread *w;
404 
405 	if(bwatchDisabled)
406 		return;
407 
408 	if(b->part != PartData)
409 		return;
410 
411 	w = getWThread();
412 	for(i=0; i<w->nb; i++)
413 		if(w->b[i] == b)
414 			break;
415 	if(i>=w->nb){
416 		fprint(2, "%d: unlock of unlocked block %V\n", w->pid, b->score);
417 		stop();
418 	}else
419 		w->b[i] = w->b[--w->nb];
420 }
421 
422