OSDN Git Service

c8ee10e8c8898c1ea58c573872bd6dd6bedfdc7f
[pf3gnuchains/gcc-fork.git] / libgo / runtime / chan.c
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 #include "runtime.h"
6 #include "go-type.h"
7
8 #define NOSELGEN        1
9
10 static  int32   debug   = 0;
11
12 typedef struct  WaitQ   WaitQ;
13 typedef struct  SudoG   SudoG;
14 typedef struct  Select  Select;
15 typedef struct  Scase   Scase;
16
17 typedef struct  __go_type_descriptor    Type;
18 typedef struct  __go_channel_type       ChanType;
19
20 struct  SudoG
21 {
22         G*      g;              // g and selgen constitute
23         uint32  selgen;         // a weak pointer to g
24         SudoG*  link;
25         byte*   elem;           // data element
26 };
27
28 struct  WaitQ
29 {
30         SudoG*  first;
31         SudoG*  last;
32 };
33
34 struct  Hchan
35 {
36         uint32  qcount;                 // total data in the q
37         uint32  dataqsiz;               // size of the circular q
38         uint16  elemsize;
39         bool    closed;
40         uint8   elemalign;
41         uint32  sendx;                  // send index
42         uint32  recvx;                  // receive index
43         WaitQ   recvq;                  // list of recv waiters
44         WaitQ   sendq;                  // list of send waiters
45         Lock;
46 };
47
48 // Buffer follows Hchan immediately in memory.
49 // chanbuf(c, i) is pointer to the i'th slot in the buffer.
50 #define chanbuf(c, i) ((byte*)((c)+1)+(uintptr)(c)->elemsize*(i))
51
52 enum
53 {
54         // Scase.kind
55         CaseRecv,
56         CaseSend,
57         CaseDefault,
58 };
59
60 struct  Scase
61 {
62         SudoG   sg;                     // must be first member (cast to Scase)
63         Hchan*  chan;                   // chan
64         uint16  kind;
65         uint16  index;                  // index to return
66         bool*   receivedp;              // pointer to received bool (recv2)
67 };
68
69 struct  Select
70 {
71         uint16  tcase;                  // total count of scase[]
72         uint16  ncase;                  // currently filled scase[]
73         uint16* pollorder;              // case poll order
74         Hchan** lockorder;              // channel lock order
75         Scase   scase[1];               // one per case (in order of appearance)
76 };
77
78 static  void    dequeueg(WaitQ*);
79 static  SudoG*  dequeue(WaitQ*);
80 static  void    enqueue(WaitQ*, SudoG*);
81
82 Hchan*
83 runtime_makechan_c(ChanType *t, int64 hint)
84 {
85         Hchan *c;
86         int32 n;
87         const Type *elem;
88         
89         elem = t->__element_type;
90
91         if(hint < 0 || (int32)hint != hint || (elem->__size > 0 && (uintptr)hint > ((uintptr)-1) / elem->__size))
92                 runtime_panicstring("makechan: size out of range");
93
94         n = sizeof(*c);
95
96         // allocate memory in one call
97         c = (Hchan*)runtime_mal(n + hint*elem->__size);
98         c->elemsize = elem->__size;
99         c->elemalign = elem->__align;
100         c->dataqsiz = hint;
101
102         if(debug)
103                 runtime_printf("makechan: chan=%p; elemsize=%D; elemalign=%d; dataqsiz=%d\n",
104                         c, (int64)elem->__size, elem->__align, c->dataqsiz);
105
106         return c;
107 }
108
109 // For reflect
110 //      func makechan(typ *ChanType, size uint32) (chan)
111 uintptr reflect_makechan(ChanType *, uint32)
112   asm ("reflect.makechan");
113
114 uintptr
115 reflect_makechan(ChanType *t, uint32 size)
116 {
117         void *ret;
118         Hchan *c;
119
120         c = runtime_makechan_c(t, size);
121         ret = runtime_mal(sizeof(void*));
122         __builtin_memcpy(ret, &c, sizeof(void*));
123         return (uintptr)ret;
124 }
125
126 // makechan(t *ChanType, hint int64) (hchan *chan any);
127 Hchan*
128 __go_new_channel(ChanType *t, uintptr hint)
129 {
130         return runtime_makechan_c(t, hint);
131 }
132
133 Hchan*
134 __go_new_channel_big(ChanType *t, uint64 hint)
135 {
136         return runtime_makechan_c(t, hint);
137 }
138
139 /*
140  * generic single channel send/recv
141  * if the bool pointer is nil,
142  * then the full exchange will
143  * occur. if pres is not nil,
144  * then the protocol will not
145  * sleep but return if it could
146  * not complete.
147  *
148  * sleep can wake up with g->param == nil
149  * when a channel involved in the sleep has
150  * been closed.  it is easiest to loop and re-run
151  * the operation; we'll see that it's now closed.
152  */
153 void
154 runtime_chansend(ChanType *t, Hchan *c, byte *ep, bool *pres)
155 {
156         SudoG *sg;
157         SudoG mysg;
158         G* gp;
159         G* g;
160
161         g = runtime_g();
162
163         if(c == nil) {
164                 USED(t);
165                 if(pres != nil) {
166                         *pres = false;
167                         return;
168                 }
169                 g->status = Gwaiting;
170                 g->waitreason = "chan send (nil chan)";
171                 runtime_gosched();
172                 return;  // not reached
173         }
174
175         if(runtime_gcwaiting)
176                 runtime_gosched();
177
178         if(debug) {
179                 runtime_printf("chansend: chan=%p\n", c);
180         }
181
182         runtime_lock(c);
183         if(c->closed)
184                 goto closed;
185
186         if(c->dataqsiz > 0)
187                 goto asynch;
188
189         sg = dequeue(&c->recvq);
190         if(sg != nil) {
191                 runtime_unlock(c);
192                 
193                 gp = sg->g;
194                 gp->param = sg;
195                 if(sg->elem != nil)
196                         runtime_memmove(sg->elem, ep, c->elemsize);
197                 runtime_ready(gp);
198
199                 if(pres != nil)
200                         *pres = true;
201                 return;
202         }
203
204         if(pres != nil) {
205                 runtime_unlock(c);
206                 *pres = false;
207                 return;
208         }
209
210         mysg.elem = ep;
211         mysg.g = g;
212         mysg.selgen = NOSELGEN;
213         g->param = nil;
214         g->status = Gwaiting;
215         g->waitreason = "chan send";
216         enqueue(&c->sendq, &mysg);
217         runtime_unlock(c);
218         runtime_gosched();
219
220         if(g->param == nil) {
221                 runtime_lock(c);
222                 if(!c->closed)
223                         runtime_throw("chansend: spurious wakeup");
224                 goto closed;
225         }
226
227         return;
228
229 asynch:
230         if(c->closed)
231                 goto closed;
232
233         if(c->qcount >= c->dataqsiz) {
234                 if(pres != nil) {
235                         runtime_unlock(c);
236                         *pres = false;
237                         return;
238                 }
239                 mysg.g = g;
240                 mysg.elem = nil;
241                 mysg.selgen = NOSELGEN;
242                 g->status = Gwaiting;
243                 g->waitreason = "chan send";
244                 enqueue(&c->sendq, &mysg);
245                 runtime_unlock(c);
246                 runtime_gosched();
247
248                 runtime_lock(c);
249                 goto asynch;
250         }
251         runtime_memmove(chanbuf(c, c->sendx), ep, c->elemsize);
252         if(++c->sendx == c->dataqsiz)
253                 c->sendx = 0;
254         c->qcount++;
255
256         sg = dequeue(&c->recvq);
257         if(sg != nil) {
258                 gp = sg->g;
259                 runtime_unlock(c);
260                 runtime_ready(gp);
261         } else
262                 runtime_unlock(c);
263         if(pres != nil)
264                 *pres = true;
265         return;
266
267 closed:
268         runtime_unlock(c);
269         runtime_panicstring("send on closed channel");
270 }
271
272
273 void
274 runtime_chanrecv(ChanType *t, Hchan* c, byte *ep, bool *selected, bool *received)
275 {
276         SudoG *sg;
277         SudoG mysg;
278         G *gp;
279         G *g;
280
281         if(runtime_gcwaiting)
282                 runtime_gosched();
283
284         if(debug)
285                 runtime_printf("chanrecv: chan=%p\n", c);
286
287         g = runtime_g();
288
289         if(c == nil) {
290                 USED(t);
291                 if(selected != nil) {
292                         *selected = false;
293                         return;
294                 }
295                 g->status = Gwaiting;
296                 g->waitreason = "chan receive (nil chan)";
297                 runtime_gosched();
298                 return;  // not reached
299         }
300
301         runtime_lock(c);
302         if(c->dataqsiz > 0)
303                 goto asynch;
304
305         if(c->closed)
306                 goto closed;
307
308         sg = dequeue(&c->sendq);
309         if(sg != nil) {
310                 runtime_unlock(c);
311
312                 if(ep != nil)
313                         runtime_memmove(ep, sg->elem, c->elemsize);
314                 gp = sg->g;
315                 gp->param = sg;
316                 runtime_ready(gp);
317
318                 if(selected != nil)
319                         *selected = true;
320                 if(received != nil)
321                         *received = true;
322                 return;
323         }
324
325         if(selected != nil) {
326                 runtime_unlock(c);
327                 *selected = false;
328                 return;
329         }
330
331         mysg.elem = ep;
332         mysg.g = g;
333         mysg.selgen = NOSELGEN;
334         g->param = nil;
335         g->status = Gwaiting;
336         g->waitreason = "chan receive";
337         enqueue(&c->recvq, &mysg);
338         runtime_unlock(c);
339         runtime_gosched();
340
341         if(g->param == nil) {
342                 runtime_lock(c);
343                 if(!c->closed)
344                         runtime_throw("chanrecv: spurious wakeup");
345                 goto closed;
346         }
347
348         if(received != nil)
349                 *received = true;
350         return;
351
352 asynch:
353         if(c->qcount <= 0) {
354                 if(c->closed)
355                         goto closed;
356
357                 if(selected != nil) {
358                         runtime_unlock(c);
359                         *selected = false;
360                         if(received != nil)
361                                 *received = false;
362                         return;
363                 }
364                 mysg.g = g;
365                 mysg.elem = nil;
366                 mysg.selgen = NOSELGEN;
367                 g->status = Gwaiting;
368                 g->waitreason = "chan receive";
369                 enqueue(&c->recvq, &mysg);
370                 runtime_unlock(c);
371                 runtime_gosched();
372
373                 runtime_lock(c);
374                 goto asynch;
375         }
376         if(ep != nil)
377                 runtime_memmove(ep, chanbuf(c, c->recvx), c->elemsize);
378         runtime_memclr(chanbuf(c, c->recvx), c->elemsize);
379         if(++c->recvx == c->dataqsiz)
380                 c->recvx = 0;
381         c->qcount--;
382
383         sg = dequeue(&c->sendq);
384         if(sg != nil) {
385                 gp = sg->g;
386                 runtime_unlock(c);
387                 runtime_ready(gp);
388         } else
389                 runtime_unlock(c);
390
391         if(selected != nil)
392                 *selected = true;
393         if(received != nil)
394                 *received = true;
395         return;
396
397 closed:
398         if(ep != nil)
399                 runtime_memclr(ep, c->elemsize);
400         if(selected != nil)
401                 *selected = true;
402         if(received != nil)
403                 *received = false;
404         runtime_unlock(c);
405 }
406
407 // The compiler generates a call to __go_send_small to send a value 8
408 // bytes or smaller.
409 void
410 __go_send_small(ChanType *t, Hchan* c, uint64 val)
411 {
412         union
413         {
414                 byte b[sizeof(uint64)];
415                 uint64 v;
416         } u;
417         byte *p;
418
419         u.v = val;
420 #ifndef WORDS_BIGENDIAN
421         p = u.b;
422 #else
423         p = u.b + sizeof(uint64) - t->__element_type->__size;
424 #endif
425         runtime_chansend(t, c, p, nil);
426 }
427
428 // The compiler generates a call to __go_send_big to send a value
429 // larger than 8 bytes or smaller.
430 void
431 __go_send_big(ChanType *t, Hchan* c, byte* p)
432 {
433         runtime_chansend(t, c, p, nil);
434 }
435
436 // The compiler generates a call to __go_receive_small to receive a
437 // value 8 bytes or smaller.
438 uint64
439 __go_receive_small(ChanType *t, Hchan* c)
440 {
441         union {
442                 byte b[sizeof(uint64)];
443                 uint64 v;
444         } u;
445         byte *p;
446
447         u.v = 0;
448 #ifndef WORDS_BIGENDIAN
449         p = u.b;
450 #else
451         p = u.b + sizeof(uint64) - t->__element_type->__size;
452 #endif
453         runtime_chanrecv(t, c, p, nil, nil);
454         return u.v;
455 }
456
457 // The compiler generates a call to __go_receive_big to receive a
458 // value larger than 8 bytes.
459 void
460 __go_receive_big(ChanType *t, Hchan* c, byte* p)
461 {
462         runtime_chanrecv(t, c, p, nil, nil);
463 }
464
465 _Bool runtime_chanrecv2(ChanType *t, Hchan* c, byte* p)
466   __asm__("runtime.chanrecv2");
467
468 _Bool
469 runtime_chanrecv2(ChanType *t, Hchan* c, byte* p)
470 {
471         bool received;
472
473         runtime_chanrecv(t, c, p, nil, &received);
474         return received;
475 }
476
477 // func selectnbsend(c chan any, elem any) bool
478 //
479 // compiler implements
480 //
481 //      select {
482 //      case c <- v:
483 //              ... foo
484 //      default:
485 //              ... bar
486 //      }
487 //
488 // as
489 //
490 //      if selectnbsend(c, v) {
491 //              ... foo
492 //      } else {
493 //              ... bar
494 //      }
495 //
496 _Bool
497 runtime_selectnbsend(ChanType *t, Hchan *c, byte *p)
498 {
499         bool res;
500
501         runtime_chansend(t, c, p, &res);
502         return res;
503 }
504
505 // func selectnbrecv(elem *any, c chan any) bool
506 //
507 // compiler implements
508 //
509 //      select {
510 //      case v = <-c:
511 //              ... foo
512 //      default:
513 //              ... bar
514 //      }
515 //
516 // as
517 //
518 //      if selectnbrecv(&v, c) {
519 //              ... foo
520 //      } else {
521 //              ... bar
522 //      }
523 //
524 _Bool
525 runtime_selectnbrecv(ChanType *t, byte *v, Hchan *c)
526 {
527         bool selected;
528
529         runtime_chanrecv(t, c, v, &selected, nil);
530         return selected;
531 }       
532
533 // func selectnbrecv2(elem *any, ok *bool, c chan any) bool
534 //
535 // compiler implements
536 //
537 //      select {
538 //      case v, ok = <-c:
539 //              ... foo
540 //      default:
541 //              ... bar
542 //      }
543 //
544 // as
545 //
546 //      if c != nil && selectnbrecv2(&v, &ok, c) {
547 //              ... foo
548 //      } else {
549 //              ... bar
550 //      }
551 //
552 _Bool
553 runtime_selectnbrecv2(ChanType *t, byte *v, _Bool *received, Hchan *c)
554 {
555         bool selected;
556         bool r;
557
558         r = false;
559         runtime_chanrecv(t, c, v, &selected, received == nil ? nil : &r);
560         if(received != nil)
561                 *received = r;
562         return selected;
563 }       
564
565 // For reflect:
566 //      func chansend(c chan, val iword, nb bool) (selected bool)
567 // where an iword is the same word an interface value would use:
568 // the actual data if it fits, or else a pointer to the data.
569
570 _Bool reflect_chansend(ChanType *, Hchan *, uintptr, _Bool)
571   __asm__("reflect.chansend");
572
573 _Bool
574 reflect_chansend(ChanType *t, Hchan *c, uintptr val, _Bool nb)
575 {
576         bool selected;
577         bool *sp;
578         byte *vp;
579         
580         if(nb) {
581                 selected = false;
582                 sp = (bool*)&selected;
583         } else {
584                 selected = true;
585                 sp = nil;
586         }
587         if(__go_is_pointer_type(t->__element_type))
588                 vp = (byte*)&val;
589         else
590                 vp = (byte*)val;
591         runtime_chansend(t, c, vp, sp);
592         return selected;
593 }
594
595 // For reflect:
596 //      func chanrecv(c chan, nb bool) (val iword, selected, received bool)
597 // where an iword is the same word an interface value would use:
598 // the actual data if it fits, or else a pointer to the data.
599
600 struct chanrecv_ret
601 {
602         uintptr val;
603         _Bool selected;
604         _Bool received;
605 };
606
607 struct chanrecv_ret reflect_chanrecv(ChanType *, Hchan *, _Bool)
608   __asm__("reflect.chanrecv");
609
610 struct chanrecv_ret
611 reflect_chanrecv(ChanType *t, Hchan *c, _Bool nb)
612 {
613         struct chanrecv_ret ret;
614         byte *vp;
615         bool *sp;
616         bool selected;
617         bool received;
618
619         if(nb) {
620                 selected = false;
621                 sp = &selected;
622         } else {
623                 ret.selected = true;
624                 sp = nil;
625         }
626         received = false;
627         if(__go_is_pointer_type(t->__element_type)) {
628                 vp = (byte*)&ret.val;
629         } else {
630                 vp = runtime_mal(t->__element_type->__size);
631                 ret.val = (uintptr)vp;
632         }
633         runtime_chanrecv(t, c, vp, sp, &received);
634         if(nb)
635                 ret.selected = selected;
636         ret.received = received;
637         return ret;
638 }
639
640 static void newselect(int32, Select**);
641
642 // newselect(size uint32) (sel *byte);
643
644 void* runtime_newselect(int) __asm__("runtime.newselect");
645
646 void*
647 runtime_newselect(int size)
648 {
649         Select *sel;
650
651         newselect(size, &sel);
652         return (void*)sel;
653 }
654
655 static void
656 newselect(int32 size, Select **selp)
657 {
658         int32 n;
659         Select *sel;
660
661         n = 0;
662         if(size > 1)
663                 n = size-1;
664
665         // allocate all the memory we need in a single allocation
666         // start with Select with size cases
667         // then lockorder with size entries
668         // then pollorder with size entries
669         sel = runtime_mal(sizeof(*sel) +
670                 n*sizeof(sel->scase[0]) +
671                 size*sizeof(sel->lockorder[0]) +
672                 size*sizeof(sel->pollorder[0]));
673
674         sel->tcase = size;
675         sel->ncase = 0;
676         sel->lockorder = (void*)(sel->scase + size);
677         sel->pollorder = (void*)(sel->lockorder + size);
678         *selp = sel;
679
680         if(debug)
681                 runtime_printf("newselect s=%p size=%d\n", sel, size);
682 }
683
684 // cut in half to give stack a chance to split
685 static void selectsend(Select *sel, Hchan *c, int index, void *elem);
686
687 // selectsend(sel *byte, hchan *chan any, elem *any) (selected bool);
688
689 void runtime_selectsend(Select *, Hchan *, void *, int)
690   __asm__("runtime.selectsend");
691
692 void
693 runtime_selectsend(Select *sel, Hchan *c, void *elem, int index)
694 {
695         // nil cases do not compete
696         if(c == nil)
697                 return;
698         
699         selectsend(sel, c, index, elem);
700 }
701
702 static void
703 selectsend(Select *sel, Hchan *c, int index, void *elem)
704 {
705         int32 i;
706         Scase *cas;
707         
708         i = sel->ncase;
709         if(i >= sel->tcase)
710                 runtime_throw("selectsend: too many cases");
711         sel->ncase = i+1;
712         cas = &sel->scase[i];
713
714         cas->index = index;
715         cas->chan = c;
716         cas->kind = CaseSend;
717         cas->sg.elem = elem;
718
719         if(debug)
720                 runtime_printf("selectsend s=%p index=%d chan=%p\n",
721                         sel, cas->index, cas->chan);
722 }
723
724 // cut in half to give stack a chance to split
725 static void selectrecv(Select *sel, Hchan *c, int index, void *elem, bool*);
726
727 // selectrecv(sel *byte, hchan *chan any, elem *any) (selected bool);
728
729 void runtime_selectrecv(Select *, Hchan *, void *, int)
730   __asm__("runtime.selectrecv");
731
732 void
733 runtime_selectrecv(Select *sel, Hchan *c, void *elem, int index)
734 {
735         // nil cases do not compete
736         if(c == nil)
737                 return;
738
739         selectrecv(sel, c, index, elem, nil);
740 }
741
742 // selectrecv2(sel *byte, hchan *chan any, elem *any, received *bool) (selected bool);
743
744 void runtime_selectrecv2(Select *, Hchan *, void *, bool *, int)
745   __asm__("runtime.selectrecv2");
746
747 void
748 runtime_selectrecv2(Select *sel, Hchan *c, void *elem, bool *received, int index)
749 {
750         // nil cases do not compete
751         if(c == nil)
752                 return;
753
754         selectrecv(sel, c, index, elem, received);
755 }
756
757 static void
758 selectrecv(Select *sel, Hchan *c, int index, void *elem, bool *received)
759 {
760         int32 i;
761         Scase *cas;
762
763         i = sel->ncase;
764         if(i >= sel->tcase)
765                 runtime_throw("selectrecv: too many cases");
766         sel->ncase = i+1;
767         cas = &sel->scase[i];
768         cas->index = index;
769         cas->chan = c;
770
771         cas->kind = CaseRecv;
772         cas->sg.elem = elem;
773         cas->receivedp = received;
774
775         if(debug)
776                 runtime_printf("selectrecv s=%p index=%d chan=%p\n",
777                         sel, cas->index, cas->chan);
778 }
779
780 // cut in half to give stack a chance to split
781 static void selectdefault(Select*, int);
782
783 // selectdefault(sel *byte) (selected bool);
784
785 void runtime_selectdefault(Select *, int) __asm__("runtime.selectdefault");
786
787 void
788 runtime_selectdefault(Select *sel, int index)
789 {
790         selectdefault(sel, index);
791 }
792
793 static void
794 selectdefault(Select *sel, int index)
795 {
796         int32 i;
797         Scase *cas;
798
799         i = sel->ncase;
800         if(i >= sel->tcase)
801                 runtime_throw("selectdefault: too many cases");
802         sel->ncase = i+1;
803         cas = &sel->scase[i];
804         cas->index = index;
805         cas->chan = nil;
806
807         cas->kind = CaseDefault;
808
809         if(debug)
810                 runtime_printf("selectdefault s=%p index=%d\n",
811                         sel, cas->index);
812 }
813
814 static void
815 sellock(Select *sel)
816 {
817         uint32 i;
818         Hchan *c, *c0;
819
820         c = nil;
821         for(i=0; i<sel->ncase; i++) {
822                 c0 = sel->lockorder[i];
823                 if(c0 && c0 != c) {
824                         c = sel->lockorder[i];
825                         runtime_lock(c);
826                 }
827         }
828 }
829
830 static void
831 selunlock(Select *sel)
832 {
833         uint32 i;
834         Hchan *c, *c0;
835
836         c = nil;
837         for(i=sel->ncase; i-->0;) {
838                 c0 = sel->lockorder[i];
839                 if(c0 && c0 != c) {
840                         c = c0;
841                         runtime_unlock(c);
842                 }
843         }
844 }
845
846 void
847 runtime_block(void)
848 {
849         G *g;
850
851         g = runtime_g();
852         g->status = Gwaiting;   // forever
853         g->waitreason = "select (no cases)";
854         runtime_gosched();
855 }
856
857 static int selectgo(Select**);
858
859 // selectgo(sel *byte);
860
861 int runtime_selectgo(Select *) __asm__("runtime.selectgo");
862
863 int
864 runtime_selectgo(Select *sel)
865 {
866         return selectgo(&sel);
867 }
868
869 static int
870 selectgo(Select **selp)
871 {
872         Select *sel;
873         uint32 o, i, j;
874         Scase *cas, *dfl;
875         Hchan *c;
876         SudoG *sg;
877         G *gp;
878         int index;
879         G *g;
880
881         sel = *selp;
882         if(runtime_gcwaiting)
883                 runtime_gosched();
884
885         if(debug)
886                 runtime_printf("select: sel=%p\n", sel);
887
888         g = runtime_g();
889
890         // The compiler rewrites selects that statically have
891         // only 0 or 1 cases plus default into simpler constructs.
892         // The only way we can end up with such small sel->ncase
893         // values here is for a larger select in which most channels
894         // have been nilled out.  The general code handles those
895         // cases correctly, and they are rare enough not to bother
896         // optimizing (and needing to test).
897
898         // generate permuted order
899         for(i=0; i<sel->ncase; i++)
900                 sel->pollorder[i] = i;
901         for(i=1; i<sel->ncase; i++) {
902                 o = sel->pollorder[i];
903                 j = runtime_fastrand1()%(i+1);
904                 sel->pollorder[i] = sel->pollorder[j];
905                 sel->pollorder[j] = o;
906         }
907
908         // sort the cases by Hchan address to get the locking order.
909         for(i=0; i<sel->ncase; i++) {
910                 c = sel->scase[i].chan;
911                 for(j=i; j>0 && sel->lockorder[j-1] >= c; j--)
912                         sel->lockorder[j] = sel->lockorder[j-1];
913                 sel->lockorder[j] = c;
914         }
915         sellock(sel);
916
917 loop:
918         // pass 1 - look for something already waiting
919         dfl = nil;
920         for(i=0; i<sel->ncase; i++) {
921                 o = sel->pollorder[i];
922                 cas = &sel->scase[o];
923                 c = cas->chan;
924
925                 switch(cas->kind) {
926                 case CaseRecv:
927                         if(c->dataqsiz > 0) {
928                                 if(c->qcount > 0)
929                                         goto asyncrecv;
930                         } else {
931                                 sg = dequeue(&c->sendq);
932                                 if(sg != nil)
933                                         goto syncrecv;
934                         }
935                         if(c->closed)
936                                 goto rclose;
937                         break;
938
939                 case CaseSend:
940                         if(c->closed)
941                                 goto sclose;
942                         if(c->dataqsiz > 0) {
943                                 if(c->qcount < c->dataqsiz)
944                                         goto asyncsend;
945                         } else {
946                                 sg = dequeue(&c->recvq);
947                                 if(sg != nil)
948                                         goto syncsend;
949                         }
950                         break;
951
952                 case CaseDefault:
953                         dfl = cas;
954                         break;
955                 }
956         }
957
958         if(dfl != nil) {
959                 selunlock(sel);
960                 cas = dfl;
961                 goto retc;
962         }
963
964
965         // pass 2 - enqueue on all chans
966         for(i=0; i<sel->ncase; i++) {
967                 o = sel->pollorder[i];
968                 cas = &sel->scase[o];
969                 c = cas->chan;
970                 sg = &cas->sg;
971                 sg->g = g;
972                 sg->selgen = g->selgen;
973
974                 switch(cas->kind) {
975                 case CaseRecv:
976                         enqueue(&c->recvq, sg);
977                         break;
978                 
979                 case CaseSend:
980                         enqueue(&c->sendq, sg);
981                         break;
982                 }
983         }
984
985         g->param = nil;
986         g->status = Gwaiting;
987         g->waitreason = "select";
988         selunlock(sel);
989         runtime_gosched();
990
991         sellock(sel);
992         sg = g->param;
993
994         // pass 3 - dequeue from unsuccessful chans
995         // otherwise they stack up on quiet channels
996         for(i=0; i<sel->ncase; i++) {
997                 cas = &sel->scase[i];
998                 if(cas != (Scase*)sg) {
999                         c = cas->chan;
1000                         if(cas->kind == CaseSend)
1001                                 dequeueg(&c->sendq);
1002                         else
1003                                 dequeueg(&c->recvq);
1004                 }
1005         }
1006
1007         if(sg == nil)
1008                 goto loop;
1009
1010         cas = (Scase*)sg;
1011         c = cas->chan;
1012
1013         if(c->dataqsiz > 0)
1014                 runtime_throw("selectgo: shouldnt happen");
1015
1016         if(debug)
1017                 runtime_printf("wait-return: sel=%p c=%p cas=%p kind=%d\n",
1018                         sel, c, cas, cas->kind);
1019
1020         if(cas->kind == CaseRecv) {
1021                 if(cas->receivedp != nil)
1022                         *cas->receivedp = true;
1023         }
1024
1025         selunlock(sel);
1026         goto retc;
1027
1028 asyncrecv:
1029         // can receive from buffer
1030         if(cas->receivedp != nil)
1031                 *cas->receivedp = true;
1032         if(cas->sg.elem != nil)
1033                 runtime_memmove(cas->sg.elem, chanbuf(c, c->recvx), c->elemsize);
1034         runtime_memclr(chanbuf(c, c->recvx), c->elemsize);
1035         if(++c->recvx == c->dataqsiz)
1036                 c->recvx = 0;
1037         c->qcount--;
1038         sg = dequeue(&c->sendq);
1039         if(sg != nil) {
1040                 gp = sg->g;
1041                 selunlock(sel);
1042                 runtime_ready(gp);
1043         } else {
1044                 selunlock(sel);
1045         }
1046         goto retc;
1047
1048 asyncsend:
1049         // can send to buffer
1050         runtime_memmove(chanbuf(c, c->sendx), cas->sg.elem, c->elemsize);
1051         if(++c->sendx == c->dataqsiz)
1052                 c->sendx = 0;
1053         c->qcount++;
1054         sg = dequeue(&c->recvq);
1055         if(sg != nil) {
1056                 gp = sg->g;
1057                 selunlock(sel);
1058                 runtime_ready(gp);
1059         } else {
1060                 selunlock(sel);
1061         }
1062         goto retc;
1063
1064 syncrecv:
1065         // can receive from sleeping sender (sg)
1066         selunlock(sel);
1067         if(debug)
1068                 runtime_printf("syncrecv: sel=%p c=%p o=%d\n", sel, c, o);
1069         if(cas->receivedp != nil)
1070                 *cas->receivedp = true;
1071         if(cas->sg.elem != nil)
1072                 runtime_memmove(cas->sg.elem, sg->elem, c->elemsize);
1073         gp = sg->g;
1074         gp->param = sg;
1075         runtime_ready(gp);
1076         goto retc;
1077
1078 rclose:
1079         // read at end of closed channel
1080         selunlock(sel);
1081         if(cas->receivedp != nil)
1082                 *cas->receivedp = false;
1083         if(cas->sg.elem != nil)
1084                 runtime_memclr(cas->sg.elem, c->elemsize);
1085         goto retc;
1086
1087 syncsend:
1088         // can send to sleeping receiver (sg)
1089         selunlock(sel);
1090         if(debug)
1091                 runtime_printf("syncsend: sel=%p c=%p o=%d\n", sel, c, o);
1092         if(sg->elem != nil)
1093                 runtime_memmove(sg->elem, cas->sg.elem, c->elemsize);
1094         gp = sg->g;
1095         gp->param = sg;
1096         runtime_ready(gp);
1097
1098 retc:
1099         // return index corresponding to chosen case
1100         index = cas->index;
1101         runtime_free(sel);
1102         return index;
1103
1104 sclose:
1105         // send on closed channel
1106         selunlock(sel);
1107         runtime_panicstring("send on closed channel");
1108         return 0;  // not reached
1109 }
1110
1111 // closechan(sel *byte);
1112 void
1113 runtime_closechan(Hchan *c)
1114 {
1115         SudoG *sg;
1116         G* gp;
1117
1118         if(c == nil)
1119                 runtime_panicstring("close of nil channel");
1120
1121         if(runtime_gcwaiting)
1122                 runtime_gosched();
1123
1124         runtime_lock(c);
1125         if(c->closed) {
1126                 runtime_unlock(c);
1127                 runtime_panicstring("close of closed channel");
1128         }
1129
1130         c->closed = true;
1131
1132         // release all readers
1133         for(;;) {
1134                 sg = dequeue(&c->recvq);
1135                 if(sg == nil)
1136                         break;
1137                 gp = sg->g;
1138                 gp->param = nil;
1139                 runtime_ready(gp);
1140         }
1141
1142         // release all writers
1143         for(;;) {
1144                 sg = dequeue(&c->sendq);
1145                 if(sg == nil)
1146                         break;
1147                 gp = sg->g;
1148                 gp->param = nil;
1149                 runtime_ready(gp);
1150         }
1151
1152         runtime_unlock(c);
1153 }
1154
1155 void
1156 __go_builtin_close(Hchan *c)
1157 {
1158         runtime_closechan(c);
1159 }
1160
1161 // For reflect
1162 //      func chanclose(c chan)
1163
1164 void reflect_chanclose(uintptr) __asm__("reflect.chanclose");
1165
1166 void
1167 reflect_chanclose(uintptr c)
1168 {
1169         runtime_closechan((Hchan*)c);
1170 }
1171
1172 // For reflect
1173 //      func chanlen(c chan) (len int32)
1174
1175 int32 reflect_chanlen(uintptr) __asm__("reflect.chanlen");
1176
1177 int32
1178 reflect_chanlen(uintptr ca)
1179 {
1180         Hchan *c;
1181         int32 len;
1182
1183         c = (Hchan*)ca;
1184         if(c == nil)
1185                 len = 0;
1186         else
1187                 len = c->qcount;
1188         return len;
1189 }
1190
1191 int
1192 __go_chan_len(Hchan *c)
1193 {
1194         return reflect_chanlen((uintptr)c);
1195 }
1196
1197 // For reflect
1198 //      func chancap(c chan) (cap int32)
1199
1200 int32 reflect_chancap(uintptr) __asm__("reflect.chancap");
1201
1202 int32
1203 reflect_chancap(uintptr ca)
1204 {
1205         Hchan *c;
1206         int32 cap;
1207
1208         c = (Hchan*)ca;
1209         if(c == nil)
1210                 cap = 0;
1211         else
1212                 cap = c->dataqsiz;
1213         return cap;
1214 }
1215
1216 int
1217 __go_chan_cap(Hchan *c)
1218 {
1219         return reflect_chancap((uintptr)c);
1220 }
1221
1222 static SudoG*
1223 dequeue(WaitQ *q)
1224 {
1225         SudoG *sgp;
1226
1227 loop:
1228         sgp = q->first;
1229         if(sgp == nil)
1230                 return nil;
1231         q->first = sgp->link;
1232
1233         // if sgp is stale, ignore it
1234         if(sgp->selgen != NOSELGEN &&
1235                 (sgp->selgen != sgp->g->selgen ||
1236                 !runtime_cas(&sgp->g->selgen, sgp->selgen, sgp->selgen + 2))) {
1237                 //prints("INVALID PSEUDOG POINTER\n");
1238                 goto loop;
1239         }
1240
1241         return sgp;
1242 }
1243
1244 static void
1245 dequeueg(WaitQ *q)
1246 {
1247         SudoG **l, *sgp, *prevsgp;
1248         G *g;
1249
1250         g = runtime_g();
1251         prevsgp = nil;
1252         for(l=&q->first; (sgp=*l) != nil; l=&sgp->link, prevsgp=sgp) {
1253                 if(sgp->g == g) {
1254                         *l = sgp->link;
1255                         if(q->last == sgp)
1256                                 q->last = prevsgp;
1257                         break;
1258                 }
1259         }
1260 }
1261
1262 static void
1263 enqueue(WaitQ *q, SudoG *sgp)
1264 {
1265         sgp->link = nil;
1266         if(q->first == nil) {
1267                 q->first = sgp;
1268                 q->last = sgp;
1269                 return;
1270         }
1271         q->last->link = sgp;
1272         q->last = sgp;
1273 }