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