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