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