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