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