libgo/runtime/chan.c

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