libgo/runtime/chan.goc

   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 package runtime
   6 #include "runtime.h"
   7 #include "arch.h"
   8 #include "go-type.h"
   9 #include "malloc.h"
  10 #include "chan.h"
  11
  12 uint32 runtime_Hchansize = sizeof(Hchan);
  13
  14 static  void    dequeueg(WaitQ*);
  15 static  SudoG*  dequeue(WaitQ*);
  16 static  void    enqueue(WaitQ*, SudoG*);
  17
  18 static Hchan*
  19 makechan(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
  50 func reflect.makechan(t *ChanType, size uint64) (c *Hchan) {
  51         c = makechan(t, size);
  52 }
  53
  54 Hchan*
  55 __go_new_channel(ChanType *t, uintptr hint)
  56 {
  57         return makechan(t, hint);
  58 }
  59
  60 Hchan*
  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  */
  80 static bool
  81 chansend(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
 159 asynch:
 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
 196 closed:
 197         runtime_unlock(c);
 198         runtime_panicstring("send on closed channel");
 199         return false;  // not reached
 200 }
 201
 202
 203 static bool
 204 chanrecv(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
 284 asynch:
 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
 328 closed:
 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.
 341 void
 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.
 362 void
 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.
 370 void
 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
 380 runtime_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 //
 405 func 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 //
 426 func 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 //
 447 func 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
 455 func reflect.chansend(t *ChanType, c *Hchan, elem *byte, nb bool) (selected bool) {
 456         selected = chansend(t, c, elem, !nb, runtime_getcallerpc(&t));
 457 }
 458
 459 func 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
 464 static Select* newselect(int32);
 465
 466 func newselect(size int32) (sel *byte) {
 467         sel = (byte*)newselect(size);
 468 }
 469
 470 static Select*
 471 newselect(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
 500 static void selectsend(Select *sel, Hchan *c, int index, void *elem);
 501
 502 func 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
 508 static void
 509 selectsend(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
 531 static void selectrecv(Select *sel, Hchan *c, int index, void *elem, bool*);
 532
 533 func 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
 539 func 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
 545 static void
 546 selectrecv(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
 569 static void selectdefault(Select*, int);
 570
 571 func selectdefault(sel *Select, index int32) {
 572         selectdefault(sel, index);
 573 }
 574
 575 static void
 576 selectdefault(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
 596 static void
 597 sellock(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
 612 static void
 613 selunlock(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
 639 static bool
 640 selparkcommit(G *gp, void *sel)
 641 {
 642         USED(gp);
 643         selunlock(sel);
 644         return true;
 645 }
 646
 647 func block() {
 648         runtime_park(nil, nil, "select (no cases)");    // forever
 649 }
 650
 651 static int selectgo(Select**);
 652
 653 // selectgo(sel *byte);
 654
 655 func selectgo(sel *Select) (ret int32) {
 656         return selectgo(&sel);
 657 }
 658
 659 static int
 660 selectgo(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
 745 loop:
 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
 854 asyncrecv:
 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
 876 asyncsend:
 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
 894 syncrecv:
 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
 910 rclose:
 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
 919 syncsend:
 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
 932 retc:
 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
 940 sclose:
 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.
 948 typedef struct runtimeSelect runtimeSelect;
 949 struct 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.
 958 enum SelectDir {
 959         SelectSend = 1,
 960         SelectRecv,
 961         SelectDefault,
 962 };
 963
 964 func 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
 997 static void closechan(Hchan *c, void *pc);
 998
 999 func closechan(c *Hchan) {
1000         closechan(c, runtime_getcallerpc(&c));
1001 }
1002
1003 func reflect.chanclose(c *Hchan) {
1004         closechan(c, runtime_getcallerpc(&c));
1005 }
1006
1007 static void
1008 closechan(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
1054 void
1055 __go_builtin_close(Hchan *c)
1056 {
1057         runtime_closechan(c);
1058 }
1059
1060 func reflect.chanlen(c *Hchan) (len int) {
1061         if(c == nil)
1062                 len = 0;
1063         else
1064                 len = c->qcount;
1065 }
1066
1067 intgo
1068 __go_chan_len(Hchan *c)
1069 {
1070         return reflect_chanlen(c);
1071 }
1072
1073 func reflect.chancap(c *Hchan) (cap int) {
1074         if(c == nil)
1075                 cap = 0;
1076         else
1077                 cap = c->dataqsiz;
1078 }
1079
1080 intgo
1081 __go_chan_cap(Hchan *c)
1082 {
1083         return reflect_chancap(c);
1084 }
1085
1086 static SudoG*
1087 dequeue(WaitQ *q)
1088 {
1089         SudoG *sgp;
1090
1091 loop:
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
1107 static void
1108 dequeueg(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
1125 static void
1126 enqueue(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 }