lib/ruby-1.9.1-rc1/cont.c

   1 /**********************************************************************
   2
   3   cont.c -
   4
   5   $Author: yugui $
   6   created at: Thu May 23 09:03:43 2007
   7
   8   Copyright (C) 2007 Koichi Sasada
   9
  10 **********************************************************************/
  11
  12 #include "ruby/ruby.h"
  13 #include "vm_core.h"
  14 #include "gc.h"
  15 #include "eval_intern.h"
  16
  17 #define CAPTURE_JUST_VALID_VM_STACK 1
  18
  19 enum context_type {
  20     CONTINUATION_CONTEXT = 0,
  21     FIBER_CONTEXT = 1,
  22     ROOT_FIBER_CONTEXT = 2
  23 };
  24
  25 typedef struct rb_context_struct {
  26     enum context_type type;
  27     VALUE self;
  28     int argc;
  29     VALUE value;
  30     VALUE *vm_stack;
  31 #ifdef CAPTURE_JUST_VALID_VM_STACK
  32     int vm_stack_slen;  /* length of stack (head of th->stack) */
  33     int vm_stack_clen;  /* length of control frames (tail of th->stack) */
  34 #endif
  35     VALUE *machine_stack;
  36     VALUE *machine_stack_src;
  37 #ifdef __ia64
  38     VALUE *machine_register_stack;
  39     VALUE *machine_register_stack_src;
  40     int machine_register_stack_size;
  41 #endif
  42     rb_thread_t saved_thread;
  43     rb_jmpbuf_t jmpbuf;
  44     int machine_stack_size;
  45 } rb_context_t;
  46
  47 enum fiber_status {
  48     CREATED,
  49     RUNNING,
  50     TERMINATED
  51 };
  52
  53 typedef struct rb_fiber_struct {
  54     rb_context_t cont;
  55     VALUE prev;
  56     enum fiber_status status;
  57     struct rb_fiber_struct *prev_fiber;
  58     struct rb_fiber_struct *next_fiber;
  59 } rb_fiber_t;
  60
  61 static VALUE rb_cContinuation;
  62 static VALUE rb_cFiber;
  63 static VALUE rb_eFiberError;
  64
  65 #define GetContPtr(obj, ptr)  \
  66   Data_Get_Struct(obj, rb_context_t, ptr)
  67
  68 #define GetFiberPtr(obj, ptr)  do {\
  69   ptr = (rb_fiber_t*)DATA_PTR(obj);\
  70   if (!ptr) rb_raise(rb_eFiberError, "uninitialized fiber");\
  71 } while(0)
  72
  73 NOINLINE(static VALUE cont_capture(volatile int *stat));
  74
  75 void rb_thread_mark(rb_thread_t *th);
  76
  77 static void
  78 cont_mark(void *ptr)
  79 {
  80     RUBY_MARK_ENTER("cont");
  81     if (ptr) {
  82         rb_context_t *cont = ptr;
  83         rb_gc_mark(cont->value);
  84         rb_thread_mark(&cont->saved_thread);
  85
  86         if (cont->vm_stack) {
  87 #ifdef CAPTURE_JUST_VALID_VM_STACK
  88             rb_gc_mark_locations(cont->vm_stack,
  89                                  cont->vm_stack + cont->vm_stack_slen + cont->vm_stack_clen);
  90 #elif
  91             rb_gc_mark_localtion(cont->vm_stack,
  92                                  cont->vm_stack, cont->saved_thread.stack_size);
  93 #endif
  94         }
  95
  96         if (cont->machine_stack) {
  97             rb_gc_mark_locations(cont->machine_stack,
  98                                  cont->machine_stack + cont->machine_stack_size);
  99         }
 100 #ifdef __ia64
 101         if (cont->machine_register_stack) {
 102             rb_gc_mark_locations(cont->machine_register_stack,
 103                                  cont->machine_register_stack + cont->machine_register_stack_size);
 104         }
 105 #endif
 106     }
 107     RUBY_MARK_LEAVE("cont");
 108 }
 109
 110 static void
 111 cont_free(void *ptr)
 112 {
 113     RUBY_FREE_ENTER("cont");
 114     if (ptr) {
 115         rb_context_t *cont = ptr;
 116         RUBY_FREE_UNLESS_NULL(cont->saved_thread.stack); fflush(stdout);
 117         RUBY_FREE_UNLESS_NULL(cont->machine_stack);
 118 #ifdef __ia64
 119         RUBY_FREE_UNLESS_NULL(cont->machine_register_stack);
 120 #endif
 121         RUBY_FREE_UNLESS_NULL(cont->vm_stack);
 122
 123         /* free rb_cont_t or rb_fiber_t */
 124         ruby_xfree(ptr);
 125     }
 126     RUBY_FREE_LEAVE("cont");
 127 }
 128
 129 static void
 130 fiber_mark(void *ptr)
 131 {
 132     RUBY_MARK_ENTER("cont");
 133     if (ptr) {
 134         rb_fiber_t *fib = ptr;
 135         rb_gc_mark(fib->prev);
 136         cont_mark(&fib->cont);
 137     }
 138     RUBY_MARK_LEAVE("cont");
 139 }
 140
 141 static void
 142 fiber_link_join(rb_fiber_t *fib)
 143 {
 144     VALUE current_fibval = rb_fiber_current();
 145     rb_fiber_t *current_fib;
 146     GetFiberPtr(current_fibval, current_fib);
 147
 148     /* join fiber link */
 149     fib->next_fiber = current_fib->next_fiber;
 150     fib->prev_fiber = current_fib;
 151     current_fib->next_fiber->prev_fiber = fib;
 152     current_fib->next_fiber = fib;
 153 }
 154
 155 static void
 156 fiber_link_remove(rb_fiber_t *fib)
 157 {
 158     fib->prev_fiber->next_fiber = fib->next_fiber;
 159     fib->next_fiber->prev_fiber = fib->prev_fiber;
 160 }
 161
 162 static void
 163 fiber_free(void *ptr)
 164 {
 165     RUBY_FREE_ENTER("fiber");
 166     if (ptr) {
 167         rb_fiber_t *fib = ptr;
 168
 169         if (fib->cont.type != ROOT_FIBER_CONTEXT) {
 170             st_free_table(fib->cont.saved_thread.local_storage);
 171         }
 172         fiber_link_remove(fib);
 173
 174         cont_free(&fib->cont);
 175     }
 176     RUBY_FREE_LEAVE("fiber");
 177 }
 178
 179 static void
 180 cont_save_machine_stack(rb_thread_t *th, rb_context_t *cont)
 181 {
 182     int size;
 183     rb_thread_t *sth = &cont->saved_thread;
 184
 185     SET_MACHINE_STACK_END(&th->machine_stack_end);
 186 #ifdef __ia64
 187     th->machine_register_stack_end = rb_ia64_bsp();
 188 #endif
 189
 190     if (th->machine_stack_start > th->machine_stack_end) {
 191         size = cont->machine_stack_size = th->machine_stack_start - th->machine_stack_end;
 192         cont->machine_stack_src = th->machine_stack_end;
 193     }
 194     else {
 195         size = cont->machine_stack_size = th->machine_stack_end - th->machine_stack_start;
 196         cont->machine_stack_src = th->machine_stack_start;
 197     }
 198
 199     if (cont->machine_stack) {
 200         REALLOC_N(cont->machine_stack, VALUE, size);
 201     }
 202     else {
 203         cont->machine_stack = ALLOC_N(VALUE, size);
 204     }
 205
 206     FLUSH_REGISTER_WINDOWS;
 207     MEMCPY(cont->machine_stack, cont->machine_stack_src, VALUE, size);
 208
 209 #ifdef __ia64
 210     rb_ia64_flushrs();
 211     size = cont->machine_register_stack_size = th->machine_register_stack_end - th->machine_register_stack_start;
 212     cont->machine_register_stack_src = th->machine_register_stack_start;
 213     if (cont->machine_register_stack) {
 214         REALLOC_N(cont->machine_register_stack, VALUE, size);
 215     }
 216     else {
 217         cont->machine_register_stack = ALLOC_N(VALUE, size);
 218     }
 219
 220     MEMCPY(cont->machine_register_stack, cont->machine_register_stack_src, VALUE, size);
 221 #endif
 222
 223     sth->machine_stack_start = sth->machine_stack_end = 0;
 224 #ifdef __ia64
 225     sth->machine_register_stack_start = sth->machine_register_stack_end = 0;
 226 #endif
 227 }
 228
 229 static void
 230 cont_init(rb_context_t *cont)
 231 {
 232     rb_thread_t *th = GET_THREAD();
 233
 234     /* save thread context */
 235     cont->saved_thread = *th;
 236 }
 237
 238 static rb_context_t *
 239 cont_new(VALUE klass)
 240 {
 241     rb_context_t *cont;
 242     volatile VALUE contval;
 243
 244     contval = Data_Make_Struct(klass, rb_context_t, cont_mark, cont_free, cont);
 245     cont->self = contval;
 246     cont_init(cont);
 247     return cont;
 248 }
 249
 250 void vm_stack_to_heap(rb_thread_t *th);
 251
 252 static VALUE
 253 cont_capture(volatile int *stat)
 254 {
 255     rb_context_t *cont;
 256     rb_thread_t *th = GET_THREAD(), *sth;
 257     volatile VALUE contval;
 258
 259     vm_stack_to_heap(th);
 260     cont = cont_new(rb_cContinuation);
 261     contval = cont->self;
 262     sth = &cont->saved_thread;
 263
 264 #ifdef CAPTURE_JUST_VALID_VM_STACK
 265     cont->vm_stack_slen = th->cfp->sp + th->mark_stack_len - th->stack;
 266     cont->vm_stack_clen = th->stack + th->stack_size - (VALUE*)th->cfp;
 267     cont->vm_stack = ALLOC_N(VALUE, cont->vm_stack_slen + cont->vm_stack_clen);
 268     MEMCPY(cont->vm_stack, th->stack, VALUE, cont->vm_stack_slen);
 269     MEMCPY(cont->vm_stack + cont->vm_stack_slen, (VALUE*)th->cfp, VALUE, cont->vm_stack_clen);
 270 #elif
 271     cont->vm_stack = ALLOC_N(VALUE, th->stack_size);
 272     MEMCPY(cont->vm_stack, th->stack, VALUE, th->stack_size);
 273 #endif
 274     sth->stack = 0;
 275
 276     cont_save_machine_stack(th, cont);
 277
 278     if (ruby_setjmp(cont->jmpbuf)) {
 279         VALUE value;
 280
 281         value = cont->value;
 282         cont->value = Qnil;
 283         *stat = 1;
 284         return value;
 285     }
 286     else {
 287         *stat = 0;
 288         return cont->self;
 289     }
 290 }
 291
 292 NORETURN(static void cont_restore_1(rb_context_t *));
 293
 294 static void
 295 cont_restore_1(rb_context_t *cont)
 296 {
 297     rb_thread_t *th = GET_THREAD(), *sth = &cont->saved_thread;
 298
 299     /* restore thread context */
 300     if (cont->type == CONTINUATION_CONTEXT) {
 301         /* continuation */
 302         VALUE fib;
 303
 304         th->fiber = sth->fiber;
 305         fib = th->fiber ? th->fiber : th->root_fiber;
 306
 307         if (fib) {
 308             rb_context_t *fcont;
 309             GetContPtr(fib, fcont);
 310             th->stack_size = fcont->saved_thread.stack_size;
 311             th->stack = fcont->saved_thread.stack;
 312         }
 313 #ifdef CAPTURE_JUST_VALID_VM_STACK
 314         MEMCPY(th->stack, cont->vm_stack, VALUE, cont->vm_stack_slen);
 315         MEMCPY(th->stack + sth->stack_size - cont->vm_stack_clen,
 316                cont->vm_stack + cont->vm_stack_slen, VALUE, cont->vm_stack_clen);
 317 #elif
 318         MEMCPY(th->stack, cont->vm_stack, VALUE, sth->stack_size);
 319 #endif
 320     }
 321     else {
 322         /* fiber */
 323         th->stack = sth->stack;
 324         th->stack_size = sth->stack_size;
 325         th->local_storage = sth->local_storage;
 326         th->fiber = cont->self;
 327     }
 328
 329     th->cfp = sth->cfp;
 330     th->safe_level = sth->safe_level;
 331     th->raised_flag = sth->raised_flag;
 332     th->state = sth->state;
 333     th->status = sth->status;
 334     th->tag = sth->tag;
 335     th->trap_tag = sth->trap_tag;
 336     th->errinfo = sth->errinfo;
 337     th->first_proc = sth->first_proc;
 338
 339     /* restore machine stack */
 340 #ifdef _M_AMD64
 341     {
 342         /* workaround for x64 SEH */
 343         jmp_buf buf;
 344         setjmp(buf);
 345         ((_JUMP_BUFFER*)(&cont->jmpbuf))->Frame =
 346             ((_JUMP_BUFFER*)(&buf))->Frame;
 347     }
 348 #endif
 349     if (cont->machine_stack_src) {
 350         FLUSH_REGISTER_WINDOWS;
 351         MEMCPY(cont->machine_stack_src, cont->machine_stack,
 352                VALUE, cont->machine_stack_size);
 353     }
 354
 355 #ifdef __ia64
 356     if (cont->machine_register_stack_src) {
 357         MEMCPY(cont->machine_register_stack_src, cont->machine_register_stack,
 358                VALUE, cont->machine_register_stack_size);
 359     }
 360 #endif
 361
 362     ruby_longjmp(cont->jmpbuf, 1);
 363 }
 364
 365 NORETURN(NOINLINE(static void cont_restore_0(rb_context_t *, VALUE *)));
 366
 367 #ifdef __ia64
 368 #define C(a) rse_##a##0, rse_##a##1, rse_##a##2, rse_##a##3, rse_##a##4
 369 #define E(a) rse_##a##0= rse_##a##1= rse_##a##2= rse_##a##3= rse_##a##4
 370 static volatile int C(a), C(b), C(c), C(d), C(e);
 371 static volatile int C(f), C(g), C(h), C(i), C(j);
 372 static volatile int C(k), C(l), C(m), C(n), C(o);
 373 static volatile int C(p), C(q), C(r), C(s), C(t);
 374 int rb_dummy_false = 0;
 375 NORETURN(NOINLINE(static void register_stack_extend(rb_context_t *, VALUE *)));
 376 static void
 377 register_stack_extend(rb_context_t *cont, VALUE *curr_bsp)
 378 {
 379     if (rb_dummy_false) {
 380         /* use registers as much as possible */
 381         E(a) = E(b) = E(c) = E(d) = E(e) =
 382         E(f) = E(g) = E(h) = E(i) = E(j) =
 383         E(k) = E(l) = E(m) = E(n) = E(o) =
 384         E(p) = E(q) = E(r) = E(s) = E(t) = 0;
 385         E(a) = E(b) = E(c) = E(d) = E(e) =
 386         E(f) = E(g) = E(h) = E(i) = E(j) =
 387         E(k) = E(l) = E(m) = E(n) = E(o) =
 388         E(p) = E(q) = E(r) = E(s) = E(t) = 0;
 389     }
 390     if (curr_bsp < cont->machine_register_stack_src+cont->machine_register_stack_size) {
 391         register_stack_extend(cont, (VALUE*)rb_ia64_bsp());
 392     }
 393     cont_restore_1(cont);
 394 }
 395 #undef C
 396 #undef E
 397 #endif
 398
 399 static void
 400 cont_restore_0(rb_context_t *cont, VALUE *addr_in_prev_frame)
 401 {
 402     if (cont->machine_stack_src) {
 403 #define STACK_PAD_SIZE 1024
 404         VALUE space[STACK_PAD_SIZE];
 405
 406 #if STACK_GROW_DIRECTION < 0 /* downward */
 407         if (addr_in_prev_frame > cont->machine_stack_src) {
 408             cont_restore_0(cont, &space[0]);
 409         }
 410 #elif STACK_GROW_DIRECTION > 0 /* upward */
 411         if (addr_in_prev_frame < cont->machine_stack_src + cont->machine_stack_size) {
 412             cont_restore_0(cont, &space[STACK_PAD_SIZE-1]);
 413         }
 414 #else
 415         if (addr_in_prev_frame > &space[0]) {
 416             /* Stack grows downward */
 417             if (addr_in_prev_frame > cont->machine_stack_src) {
 418                 cont_restore_0(cont, &space[0]);
 419             }
 420         }
 421         else {
 422             /* Stack grows upward */
 423             if (addr_in_prev_frame < cont->machine_stack_src + cont->machine_stack_size) {
 424                 cont_restore_0(cont, &space[STACK_PAD_SIZE-1]);
 425             }
 426         }
 427 #endif
 428     }
 429 #ifdef __ia64
 430     register_stack_extend(cont, (VALUE*)rb_ia64_bsp());
 431 #else
 432     cont_restore_1(cont);
 433 #endif
 434 }
 435
 436 /*
 437  *  Document-class: Continuation
 438  *
 439  *  Continuation objects are generated by
 440  *  <code>Kernel#callcc</code>. They hold a return address and execution
 441  *  context, allowing a nonlocal return to the end of the
 442  *  <code>callcc</code> block from anywhere within a program.
 443  *  Continuations are somewhat analogous to a structured version of C's
 444  *  <code>setjmp/longjmp</code> (although they contain more state, so
 445  *  you might consider them closer to threads).
 446  *
 447  *  For instance:
 448  *
 449  *     arr = [ "Freddie", "Herbie", "Ron", "Max", "Ringo" ]
 450  *     callcc{|$cc|}
 451  *     puts(message = arr.shift)
 452  *     $cc.call unless message =~ /Max/
 453  *
 454  *  <em>produces:</em>
 455  *
 456  *     Freddie
 457  *     Herbie
 458  *     Ron
 459  *     Max
 460  *
 461  *  This (somewhat contrived) example allows the inner loop to abandon
 462  *  processing early:
 463  *
 464  *     callcc {|cont|
 465  *       for i in 0..4
 466  *         print "\n#{i}: "
 467  *         for j in i*5...(i+1)*5
 468  *           cont.call() if j == 17
 469  *           printf "%3d", j
 470  *         end
 471  *       end
 472  *     }
 473  *     print "\n"
 474  *
 475  *  <em>produces:</em>
 476  *
 477  *     0:   0  1  2  3  4
 478  *     1:   5  6  7  8  9
 479  *     2:  10 11 12 13 14
 480  *     3:  15 16
 481  */
 482
 483 /*
 484  *  call-seq:
 485  *     callcc {|cont| block }   =>  obj
 486  *
 487  *  Generates a <code>Continuation</code> object, which it passes to the
 488  *  associated block. Performing a <em>cont</em><code>.call</code> will
 489  *  cause the <code>callcc</code> to return (as will falling through the
 490  *  end of the block). The value returned by the <code>callcc</code> is
 491  *  the value of the block, or the value passed to
 492  *  <em>cont</em><code>.call</code>. See class <code>Continuation</code>
 493  *  for more details. Also see <code>Kernel::throw</code> for
 494  *  an alternative mechanism for unwinding a call stack.
 495  */
 496
 497 static VALUE
 498 rb_callcc(VALUE self)
 499 {
 500     volatile int called;
 501     volatile VALUE val = cont_capture(&called);
 502
 503     if (called) {
 504         return val;
 505     }
 506     else {
 507         return rb_yield(val);
 508     }
 509 }
 510
 511 static VALUE
 512 make_passing_arg(int argc, VALUE *argv)
 513 {
 514     switch(argc) {
 515       case 0:
 516         return Qnil;
 517       case 1:
 518         return argv[0];
 519       default:
 520         return rb_ary_new4(argc, argv);
 521     }
 522 }
 523
 524 /*
 525  *  call-seq:
 526  *     cont.call(args, ...)
 527  *     cont[args, ...]
 528  *
 529  *  Invokes the continuation. The program continues from the end of the
 530  *  <code>callcc</code> block. If no arguments are given, the original
 531  *  <code>callcc</code> returns <code>nil</code>. If one argument is
 532  *  given, <code>callcc</code> returns it. Otherwise, an array
 533  *  containing <i>args</i> is returned.
 534  *
 535  *     callcc {|cont|  cont.call }           #=> nil
 536  *     callcc {|cont|  cont.call 1 }         #=> 1
 537  *     callcc {|cont|  cont.call 1, 2, 3 }   #=> [1, 2, 3]
 538  */
 539
 540 static VALUE
 541 rb_cont_call(int argc, VALUE *argv, VALUE contval)
 542 {
 543     rb_context_t *cont;
 544     rb_thread_t *th = GET_THREAD();
 545     GetContPtr(contval, cont);
 546
 547     if (cont->saved_thread.self != th->self) {
 548         rb_raise(rb_eRuntimeError, "continuation called across threads");
 549     }
 550     if (cont->saved_thread.trap_tag != th->trap_tag) {
 551         rb_raise(rb_eRuntimeError, "continuation called across trap");
 552     }
 553     if (cont->saved_thread.fiber) {
 554         rb_context_t *fcont;
 555         GetContPtr(cont->saved_thread.fiber, fcont);
 556
 557         if (th->fiber != cont->saved_thread.fiber) {
 558             rb_raise(rb_eRuntimeError, "continuation called across fiber");
 559         }
 560     }
 561
 562     cont->argc = argc;
 563     cont->value = make_passing_arg(argc, argv);
 564
 565     cont_restore_0(cont, &contval);
 566     return Qnil; /* unreachable */
 567 }
 568
 569 /*********/
 570 /* fiber */
 571 /*********/
 572
 573 /*
 574  *  Document-class: Fiber
 575  *
 576  *  Fibers are primitives for implementing light weight cooperative
 577  *  concurrency in Ruby. Basically they are a means of creating code blocks
 578  *  that can be paused and resumed, much like threads. The main difference
 579  *  is that they are never preempted and that the scheduling must be done by
 580  *  the programmer and not the VM.
 581  *
 582  *  As opposed to other stackless light weight concurrency models, each fiber
 583  *  comes with a small 4KB stack. This enables the fiber to be paused from deeply
 584  *  nested function calls within the fiber block.
 585  *
 586  *  When a fiber is created it will not run automatically. Rather it must be
 587  *  be explicitly asked to run using the <code>Fiber#resume</code> method.
 588  *  The code running inside the fiber can give up control by calling
 589  *  <code>Fiber.yield</code> in which case it yields control back to caller
 590  *  (the caller of the <code>Fiber#resume</code>).
 591  *
 592  *  Upon yielding or termination the Fiber returns the value of the last
 593  *  executed expression
 594  *
 595  *  For instance:
 596  *
 597  *    fiber = Fiber.new do
 598  *      Fiber.yield 1
 599  *      2
 600  *    end
 601  *
 602  *    puts fiber.resume
 603  *    puts fiber.resume
 604  *    puts fiber.resume
 605  *
 606  *  <em>produces</em>
 607  *
 608  *    1
 609  *    2
 610  *    FiberError: dead fiber called
 611  *
 612  *  The <code>Fiber#resume</code> method accepts an arbitary number of
 613  *  parameters, if it is the first call to <code>resume</code> then they
 614  *  will be passed as block arguments. Otherwise they will be the return
 615  *  value of the call to <code>Fiber.yield</code>
 616  *
 617  *  Example:
 618  *
 619  *    fiber = Fiber.new do |first|
 620  *      second = Fiber.yield first + 2
 621  *    end
 622  *
 623  *    puts fiber.resume 10
 624  *    puts fiber.resume 14
 625  *    puts fiber.resume 18
 626  *
 627  *  <em>produces</em>
 628  *
 629  *    12
 630  *    14
 631  *    FiberError: dead fiber called
 632  *
 633  */
 634
 635 #define FIBER_VM_STACK_SIZE (4 * 1024)
 636
 637 static VALUE
 638 fiber_alloc(VALUE klass)
 639 {
 640     return Data_Wrap_Struct(klass, fiber_mark, fiber_free, 0);
 641 }
 642
 643 static rb_fiber_t*
 644 fiber_t_alloc(VALUE fibval)
 645 {
 646     rb_fiber_t *fib = ALLOC(rb_fiber_t);
 647
 648     memset(fib, 0, sizeof(rb_fiber_t));
 649     fib->cont.self = fibval;
 650     fib->cont.type = FIBER_CONTEXT;
 651     cont_init(&fib->cont);
 652     fib->prev = Qnil;
 653     fib->status = CREATED;
 654
 655     DATA_PTR(fibval) = fib;
 656
 657     return fib;
 658 }
 659
 660 static VALUE
 661 fiber_init(VALUE fibval, VALUE proc)
 662 {
 663     rb_fiber_t *fib = fiber_t_alloc(fibval);
 664     rb_context_t *cont = &fib->cont;
 665     rb_thread_t *th = &cont->saved_thread;
 666
 667     fiber_link_join(fib);
 668
 669     /* initialize cont */
 670     cont->vm_stack = 0;
 671
 672     th->stack = 0;
 673     th->stack_size = FIBER_VM_STACK_SIZE;
 674     th->stack = ALLOC_N(VALUE, th->stack_size);
 675
 676     th->cfp = (void *)(th->stack + th->stack_size);
 677     th->cfp--;
 678     th->cfp->pc = 0;
 679     th->cfp->sp = th->stack + 1;
 680     th->cfp->bp = 0;
 681     th->cfp->lfp = th->stack;
 682     *th->cfp->lfp = 0;
 683     th->cfp->dfp = th->stack;
 684     th->cfp->self = Qnil;
 685     th->cfp->flag = 0;
 686     th->cfp->iseq = 0;
 687     th->cfp->proc = 0;
 688     th->cfp->block_iseq = 0;
 689     th->tag = 0;
 690     th->local_storage = st_init_numtable();
 691
 692     th->first_proc = proc;
 693
 694     MEMCPY(&cont->jmpbuf, &th->root_jmpbuf, rb_jmpbuf_t, 1);
 695
 696     return fibval;
 697 }
 698
 699 static VALUE
 700 rb_fiber_init(VALUE fibval)
 701 {
 702     return fiber_init(fibval, rb_block_proc());
 703 }
 704
 705 VALUE
 706 rb_fiber_new(VALUE (*func)(ANYARGS), VALUE obj)
 707 {
 708     return fiber_init(fiber_alloc(rb_cFiber), rb_proc_new(func, obj));
 709 }
 710
 711 static VALUE
 712 return_fiber(void)
 713 {
 714     rb_fiber_t *fib;
 715     VALUE curr = rb_fiber_current();
 716     GetFiberPtr(curr, fib);
 717
 718     if (fib->prev == Qnil) {
 719         rb_thread_t *th = GET_THREAD();
 720
 721         if (th->root_fiber != curr) {
 722             return th->root_fiber;
 723         }
 724         else {
 725             rb_raise(rb_eFiberError, "can't yield from root fiber");
 726         }
 727     }
 728     else {
 729         VALUE prev = fib->prev;
 730         fib->prev = Qnil;
 731         return prev;
 732     }
 733 }
 734
 735 VALUE rb_fiber_transfer(VALUE fib, int argc, VALUE *argv);
 736
 737 static void
 738 rb_fiber_terminate(rb_fiber_t *fib)
 739 {
 740     VALUE value = fib->cont.value;
 741     fib->status = TERMINATED;
 742     rb_fiber_transfer(return_fiber(), 1, &value);
 743 }
 744
 745 void
 746 rb_fiber_start(void)
 747 {
 748     rb_thread_t *th = GET_THREAD();
 749     rb_fiber_t *fib;
 750     rb_context_t *cont;
 751     rb_proc_t *proc;
 752     int state;
 753
 754     GetFiberPtr(th->fiber, fib);
 755     cont = &fib->cont;
 756
 757     TH_PUSH_TAG(th);
 758     if ((state = EXEC_TAG()) == 0) {
 759         int argc;
 760         VALUE *argv, args;
 761         GetProcPtr(cont->saved_thread.first_proc, proc);
 762         args = cont->value;
 763         argv = (argc = cont->argc) > 1 ? RARRAY_PTR(args) : &args;
 764         cont->value = Qnil;
 765         th->errinfo = Qnil;
 766         th->local_lfp = proc->block.lfp;
 767         th->local_svar = Qnil;
 768
 769         fib->status = RUNNING;
 770         cont->value = vm_invoke_proc(th, proc, proc->block.self, argc, argv, 0);
 771     }
 772     TH_POP_TAG();
 773
 774     if (state) {
 775         if (TAG_RAISE) {
 776             th->thrown_errinfo = th->errinfo;
 777         }
 778         else {
 779             th->thrown_errinfo =
 780               vm_make_jump_tag_but_local_jump(state, th->errinfo);
 781         }
 782         RUBY_VM_SET_INTERRUPT(th);
 783     }
 784
 785     rb_fiber_terminate(fib);
 786     rb_bug("rb_fiber_start: unreachable");
 787 }
 788
 789 static rb_fiber_t *
 790 root_fiber_alloc(rb_thread_t *th)
 791 {
 792     rb_fiber_t *fib;
 793
 794     /* no need to allocate vm stack */
 795     fib = fiber_t_alloc(fiber_alloc(rb_cFiber));
 796     fib->cont.type = ROOT_FIBER_CONTEXT;
 797     fib->prev_fiber = fib->next_fiber = fib;
 798
 799     return fib;
 800 }
 801
 802 VALUE
 803 rb_fiber_current()
 804 {
 805     rb_thread_t *th = GET_THREAD();
 806     if (th->fiber == 0) {
 807         /* save root */
 808         rb_fiber_t *fib = root_fiber_alloc(th);
 809         th->root_fiber = th->fiber = fib->cont.self;
 810     }
 811     return th->fiber;
 812 }
 813
 814 static VALUE
 815 fiber_store(rb_fiber_t *next_fib)
 816 {
 817     rb_thread_t *th = GET_THREAD();
 818     rb_fiber_t *fib;
 819
 820     if (th->fiber) {
 821         GetFiberPtr(th->fiber, fib);
 822         fib->cont.saved_thread = *th;
 823     }
 824     else {
 825         /* create current fiber */
 826         fib = root_fiber_alloc(th);
 827         th->root_fiber = th->fiber = fib->cont.self;
 828     }
 829
 830     cont_save_machine_stack(th, &fib->cont);
 831
 832     if (ruby_setjmp(fib->cont.jmpbuf)) {
 833         /* restored */
 834         GetFiberPtr(th->fiber, fib);
 835         return fib->cont.value;
 836     }
 837     else {
 838         return Qundef;
 839     }
 840 }
 841
 842 static inline VALUE
 843 fiber_switch(VALUE fibval, int argc, VALUE *argv, int is_resume)
 844 {
 845     VALUE value;
 846     rb_fiber_t *fib;
 847     rb_context_t *cont;
 848     rb_thread_t *th = GET_THREAD();
 849
 850     GetFiberPtr(fibval, fib);
 851     cont = &fib->cont;
 852
 853     if (cont->saved_thread.self != th->self) {
 854         rb_raise(rb_eFiberError, "fiber called across threads");
 855     }
 856     else if (cont->saved_thread.trap_tag != th->trap_tag) {
 857         rb_raise(rb_eFiberError, "fiber called across trap");
 858     }
 859     else if (fib->status == TERMINATED) {
 860         rb_raise(rb_eFiberError, "dead fiber called");
 861     }
 862
 863     if (is_resume) {
 864         fib->prev = rb_fiber_current();
 865     }
 866
 867     cont->argc = argc;
 868     cont->value = make_passing_arg(argc, argv);
 869
 870     if ((value = fiber_store(fib)) == Qundef) {
 871         cont_restore_0(&fib->cont, &value);
 872         rb_bug("rb_fiber_resume: unreachable");
 873     }
 874
 875     RUBY_VM_CHECK_INTS();
 876
 877     return value;
 878 }
 879
 880 VALUE
 881 rb_fiber_transfer(VALUE fib, int argc, VALUE *argv)
 882 {
 883     return fiber_switch(fib, argc, argv, 0);
 884 }
 885
 886 VALUE
 887 rb_fiber_resume(VALUE fibval, int argc, VALUE *argv)
 888 {
 889     rb_fiber_t *fib;
 890     GetFiberPtr(fibval, fib);
 891
 892     if (fib->prev != Qnil) {
 893         rb_raise(rb_eFiberError, "double resume");
 894     }
 895
 896     return fiber_switch(fibval, argc, argv, 1);
 897 }
 898
 899 VALUE
 900 rb_fiber_yield(int argc, VALUE *argv)
 901 {
 902     return rb_fiber_transfer(return_fiber(), argc, argv);
 903 }
 904
 905 /*
 906  *  call-seq:
 907  *     fiber.alive? -> true or false
 908  *
 909  *  Returns true if the fiber can still be resumed (or transferred to).
 910  *  After finishing execution of the fiber block this method will always
 911  *  return false.
 912  */
 913 VALUE
 914 rb_fiber_alive_p(VALUE fibval)
 915 {
 916     rb_fiber_t *fib;
 917     GetFiberPtr(fibval, fib);
 918     return fib->status != TERMINATED;
 919 }
 920
 921 /*
 922  *  call-seq:
 923  *     fiber.resume(args, ...) -> obj
 924  *
 925  *  Resumes the fiber from the point at which the last <code>Fiber.yield</code>
 926  *  was called, or starts running it if it is the first call to
 927  *  <code>resume</code>. Arguments passed to resume will be the value of
 928  *  the <code>Fiber.yield</code> expression or will be passed as block
 929  *  parameters to the fiber's block if this is the first <code>resume</code>.
 930  *
 931  *  Alternatively, when resume is called it evaluates to the arguments passed
 932  *  to the next <code>Fiber.yield</code> statement inside the fiber's block
 933  *  or to the block value if it runs to completion without any
 934  *  <code>Fiber.yield</code>
 935  */
 936 static VALUE
 937 rb_fiber_m_resume(int argc, VALUE *argv, VALUE fib)
 938 {
 939     return rb_fiber_resume(fib, argc, argv);
 940 }
 941
 942 /*
 943  *  call-seq:
 944  *     fiber.transfer(args, ...) -> obj
 945  *
 946  *  Transfer control to another fiber, resuming it from where it last
 947  *  stopped or starting it if it was not resumed before. The calling
 948  *  fiber will be suspended much like in a call to <code>Fiber.yield</code>.
 949  *
 950  *  The fiber which recieves the transfer call is treats it much like
 951  *  a resume call. Arguments passed to transfer are treated like those
 952  *  passed to resume.
 953  *
 954  *  You cannot resume a fiber that transferred control to another one.
 955  *  This will cause a double resume error. You need to transfer control
 956  *  back to this fiber before it can yield and resume.
 957  */
 958 static VALUE
 959 rb_fiber_m_transfer(int argc, VALUE *argv, VALUE fib)
 960 {
 961     return rb_fiber_transfer(fib, argc, argv);
 962 }
 963
 964 /*
 965  *  call-seq:
 966  *     Fiber.yield(args, ...) -> obj
 967  *
 968  *  Yields control back to the context that resumed the fiber, passing
 969  *  along any arguments that were passed to it. The fiber will resume
 970  *  processing at this point when <code>resume</code> is called next.
 971  *  Any arguments passed to the next <code>resume</code> will be the
 972  *  value that this <code>Fiber.yield</code> expression evaluates to.
 973  */
 974 static VALUE
 975 rb_fiber_s_yield(int argc, VALUE *argv, VALUE klass)
 976 {
 977     return rb_fiber_yield(argc, argv);
 978 }
 979
 980 /*
 981  *  call-seq:
 982  *     Fiber.current() -> fiber
 983  *
 984  *  Returns the current fiber. You need to <code>require 'fiber'</code>
 985  *  before using this method. If you are not running in the context of
 986  *  a fiber this method will return the root fiber.
 987  */
 988 static VALUE
 989 rb_fiber_s_current(VALUE klass)
 990 {
 991     return rb_fiber_current();
 992 }
 993
 994 void
 995 Init_Cont(void)
 996 {
 997     rb_cFiber = rb_define_class("Fiber", rb_cObject);
 998     rb_define_alloc_func(rb_cFiber, fiber_alloc);
 999     rb_eFiberError = rb_define_class("FiberError", rb_eStandardError);
1000     rb_define_singleton_method(rb_cFiber, "yield", rb_fiber_s_yield, -1);
1001     rb_define_method(rb_cFiber, "initialize", rb_fiber_init, 0);
1002     rb_define_method(rb_cFiber, "resume", rb_fiber_m_resume, -1);
1003 }
1004
1005 void
1006 Init_Continuation_body(void)
1007 {
1008     rb_cContinuation = rb_define_class("Continuation", rb_cObject);
1009     rb_undef_alloc_func(rb_cContinuation);
1010     rb_undef_method(CLASS_OF(rb_cContinuation), "new");
1011     rb_define_method(rb_cContinuation, "call", rb_cont_call, -1);
1012     rb_define_method(rb_cContinuation, "[]", rb_cont_call, -1);
1013     rb_define_global_function("callcc", rb_callcc, 0);
1014 }
1015
1016 void
1017 Init_Fiber_as_Coroutine(void)
1018 {
1019     rb_define_method(rb_cFiber, "transfer", rb_fiber_m_transfer, -1);
1020     rb_define_method(rb_cFiber, "alive?", rb_fiber_alive_p, 0);
1021     rb_define_singleton_method(rb_cFiber, "current", rb_fiber_s_current, 0);
1022 }