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