1 #include <lib9.h>
2 
3 static struct {
4 	QLp	*p;
5 	QLp	x[1024];
6 } ql = {
7 	ql.x
8 };
9 
10 enum
11 {
12 	Queuing,
13 	QueuingR,
14 	QueuingW,
15 	Sleeping,
16 	Waking,
17 };
18 
19 static void (*procsleep)(_Procrend*) = _procsleep;
20 static void (*procwakeup)(_Procrend*) = _procwakeup;
21 #define _procsleep donotcall_procsleep
22 #define _procwakeup donotcall_procwakeup
23 
24 /* this gets called by the thread library ONLY to get us to use its rendezvous */
25 void
26 _qlockinit(void (*sleep)(_Procrend*), void (*wakeup)(_Procrend*))
27 {
28 	procsleep = sleep;
29 	procwakeup = wakeup;
30 }
31 
32 /* find a free shared memory location to queue ourselves in */
33 static QLp*
34 getqlp(void)
35 {
36 	QLp *p, *op;
37 
38 	op = ql.p;
39 	for(p = op+1; ; p++){
40 		if(p == &ql.x[nelem(ql.x)])
41 			p = ql.x;
42 		if(p == op){
43 			fprint(2, "qlock: out of qlp\n");
44 			abort();
45 		}
46 		if(canlock(&p->inuse)){
47 			ql.p = p;
48 			p->next = nil;
49 			break;
50 		}
51 	}
52 	return p;
53 }
54 
55 void
56 qlock(QLock *q)
57 {
58 	QLp *p, *mp;
59 
60 	lock(&q->lock);
61 	if(!q->locked){
62 		q->locked = 1;
63 		unlock(&q->lock);
64 		return;
65 	}
66 
67 
68 	/* chain into waiting list */
69 	mp = getqlp();
70 	p = q->tail;
71 	if(p == nil)
72 		q->head = mp;
73 	else
74 		p->next = mp;
75 	q->tail = mp;
76 	mp->state = Queuing;
77 	mp->rend.l = &q->lock;
78 	procsleep(&mp->rend);
79 	unlock(&q->lock);
80 	assert(mp->state == Waking);
81 	unlock(&mp->inuse);
82 }
83 
84 void
85 qunlock(QLock *q)
86 {
87 	QLp *p;
88 
89 	lock(&q->lock);
90 	p = q->head;
91 	if(p != nil){
92 		/* wakeup head waiting process */
93 		q->head = p->next;
94 		if(q->head == nil)
95 			q->tail = nil;
96 		p->state = Waking;
97 		procwakeup(&p->rend);
98 		unlock(&q->lock);
99 		return;
100 	}
101 	q->locked = 0;
102 	unlock(&q->lock);
103 }
104 
105 int
106 canqlock(QLock *q)
107 {
108 	if(!canlock(&q->lock))
109 		return 0;
110 	if(!q->locked){
111 		q->locked = 1;
112 		unlock(&q->lock);
113 		return 1;
114 	}
115 	unlock(&q->lock);
116 	return 0;
117 }
118 
119 void
120 rlock(RWLock *q)
121 {
122 	QLp *p, *mp;
123 
124 	lock(&q->lock);
125 	if(q->writer == 0 && q->head == nil){
126 		/* no writer, go for it */
127 		q->readers++;
128 		unlock(&q->lock);
129 		return;
130 	}
131 
132 	mp = getqlp();
133 	p = q->tail;
134 	if(p == 0)
135 		q->head = mp;
136 	else
137 		p->next = mp;
138 	q->tail = mp;
139 	mp->next = nil;
140 	mp->state = QueuingR;
141 	mp->rend.l = &q->lock;
142 	procsleep(&mp->rend);
143 	unlock(&q->lock);
144 	assert(mp->state == Waking);
145 	unlock(&mp->inuse);
146 }
147 
148 int
149 canrlock(RWLock *q)
150 {
151 	lock(&q->lock);
152 	if (q->writer == 0 && q->head == nil) {
153 		/* no writer; go for it */
154 		q->readers++;
155 		unlock(&q->lock);
156 		return 1;
157 	}
158 	unlock(&q->lock);
159 	return 0;
160 }
161 
162 void
163 runlock(RWLock *q)
164 {
165 	QLp *p;
166 
167 	lock(&q->lock);
168 	if(q->readers <= 0)
169 		abort();
170 	p = q->head;
171 	if(--(q->readers) > 0 || p == nil){
172 		unlock(&q->lock);
173 		return;
174 	}
175 
176 	/* start waiting writer */
177 	if(p->state != QueuingW)
178 		abort();
179 	q->head = p->next;
180 	if(q->head == 0)
181 		q->tail = 0;
182 	q->writer = 1;
183 
184 	/* wakeup waiter */
185 	p->state = Waking;
186 	procwakeup(&p->rend);
187 	unlock(&q->lock);
188 }
189 
190 void
191 wlock(RWLock *q)
192 {
193 	QLp *p, *mp;
194 
195 	lock(&q->lock);
196 	if(q->readers == 0 && q->writer == 0){
197 		/* noone waiting, go for it */
198 		q->writer = 1;
199 		unlock(&q->lock);
200 		return;
201 	}
202 
203 	/* wait */
204 	p = q->tail;
205 	mp = getqlp();
206 	if(p == nil)
207 		q->head = mp;
208 	else
209 		p->next = mp;
210 	q->tail = mp;
211 	mp->next = nil;
212 	mp->state = QueuingW;
213 
214 	/* wait in kernel */
215 	mp->rend.l = &q->lock;
216 	procsleep(&mp->rend);
217 	unlock(&q->lock);
218 	assert(mp->state == Waking);
219 	unlock(&mp->inuse);
220 }
221 
222 int
223 canwlock(RWLock *q)
224 {
225 	lock(&q->lock);
226 	if (q->readers == 0 && q->writer == 0) {
227 		/* no one waiting; go for it */
228 		q->writer = 1;
229 		unlock(&q->lock);
230 		return 1;
231 	}
232 	unlock(&q->lock);
233 	return 0;
234 }
235 
236 void
237 wunlock(RWLock *q)
238 {
239 	QLp *p;
240 
241 	lock(&q->lock);
242 	if(q->writer == 0){
243 		fprint(2, "wunlock: not holding lock\n");
244 		abort();
245 	}
246 	p = q->head;
247 	if(p == nil){
248 		q->writer = 0;
249 		unlock(&q->lock);
250 		return;
251 	}
252 	if(p->state == QueuingW){
253 		/* start waiting writer */
254 		q->head = p->next;
255 		if(q->head == nil)
256 			q->tail = nil;
257 		p->state = Waking;
258 		procwakeup(&p->rend);
259 		unlock(&q->lock);
260 		return;
261 	}
262 
263 	if(p->state != QueuingR){
264 		fprint(2, "wunlock: bad state\n");
265 		abort();
266 	}
267 
268 	/* wake waiting readers */
269 	while(q->head != nil && q->head->state == QueuingR){
270 		p = q->head;
271 		q->head = p->next;
272 		q->readers++;
273 		p->state = Waking;
274 		procwakeup(&p->rend);
275 	}
276 	if(q->head == nil)
277 		q->tail = nil;
278 	q->writer = 0;
279 	unlock(&q->lock);
280 }
281 
282 void
283 rsleep(Rendez *r)
284 {
285 	QLp *t, *me;
286 
287 	if(!r->l){
288 		fprint(2, "rsleep: no lock\n");
289 		abort();
290 	}
291 	lock(&r->l->lock);
292 	/* we should hold the qlock */
293 	if(!r->l->locked){
294 		fprint(2, "rsleep: not locked\n");
295 		abort();
296 	}
297 
298 	/* add ourselves to the wait list */
299 	me = getqlp();
300 	me->state = Sleeping;
301 	if(r->head == nil)
302 		r->head = me;
303 	else
304 		r->tail->next = me;
305 	me->next = nil;
306 	r->tail = me;
307 
308 	/* pass the qlock to the next guy */
309 	t = r->l->head;
310 	if(t){
311 		r->l->head = t->next;
312 		if(r->l->head == nil)
313 			r->l->tail = nil;
314 		t->state = Waking;
315 		procwakeup(&t->rend);
316 	}else
317 		r->l->locked = 0;
318 
319 	/* wait for a wakeup */
320 	me->rend.l = &r->l->lock;
321 	procsleep(&me->rend);
322 	assert(me->state == Waking);
323 	unlock(&me->inuse);
324 	if(!r->l->locked){
325 		fprint(2, "rsleep: not locked after wakeup\n");
326 		abort();
327 	}
328 	unlock(&r->l->lock);
329 }
330 
331 int
332 rwakeup(Rendez *r)
333 {
334 	QLp *t;
335 
336 	/*
337 	 * take off wait and put on front of queue
338 	 * put on front so guys that have been waiting will not get starved
339 	 */
340 	
341 	if(!r->l){
342 		fprint(2, "rwakeup: no lock\n");
343 		abort();
344 	}
345 	lock(&r->l->lock);
346 	if(!r->l->locked){
347 		fprint(2, "rwakeup: not locked\n");
348 		abort();
349 	}
350 
351 	t = r->head;
352 	if(t == nil){
353 		unlock(&r->l->lock);
354 		return 0;
355 	}
356 
357 	r->head = t->next;
358 	if(r->head == nil)
359 		r->tail = nil;
360 
361 	t->next = r->l->head;
362 	r->l->head = t;
363 	if(r->l->tail == nil)
364 		r->l->tail = t;
365 
366 	t->state = Queuing;
367 	unlock(&r->l->lock);
368 	return 1;
369 }
370 
371 int
372 rwakeupall(Rendez *r)
373 {
374 	int i;
375 
376 	for(i=0; rwakeup(r); i++)
377 		;
378 	return i;
379 }