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