OSDN Git Service

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