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