1: /**********************************************************************
    2: 
    3:   cont.c - 
    4: 
    5:   $Author: ko1 $
    6:   $Date: 2007-12-25 13:16:06 +0900 (Tue, 25 Dec 2007) $
    7:   created at: Thu May 23 09:03:43 2007
    8: 
    9:   Copyright (C) 2007 Koichi Sasada
   10: 
   11: **********************************************************************/
   12: 
   13: #include "ruby/ruby.h"
   14: #include "vm_core.h"
   15: #include "gc.h"
   16: #include "eval_intern.h"
   17: 
   18: enum context_type {
   19:     CONTINUATION_CONTEXT = 0,
   20:     FIBER_CONTEXT = 1,
   21:     ROOT_FIBER_CONTEXT = 2,
   22: };
   23: 
   24: typedef struct rb_context_struct {
   25:     VALUE self;
   26:     VALUE value;
   27:     VALUE *vm_stack;
   28:     VALUE *machine_stack;
   29:     VALUE *machine_stack_src;
   30: #ifdef __ia64
   31:     VALUE *machine_register_stack;
   32:     VALUE *machine_register_stack_src;
   33:     int machine_register_stack_size;
   34: #endif
   35:     rb_thread_t saved_thread;
   36:     rb_jmpbuf_t jmpbuf;
   37:     int machine_stack_size;
   38:     VALUE prev;
   39:     int alive;
   40:     enum context_type type;
   41: } rb_context_t;
   42: 
   43: static VALUE rb_cContinuation;
   44: static VALUE rb_cFiber;
   45: static VALUE rb_eFiberError;
   46: 
   47: #define GetContPtr(obj, ptr)  \
   48:   Data_Get_Struct(obj, rb_context_t, ptr)
   49: 
   50: NOINLINE(static VALUE cont_capture(volatile int *stat));
   51: 
   52: void rb_thread_mark(rb_thread_t *th);
   53: 
   54: static void
   55: cont_mark(void *ptr)
   56: {
   57:     RUBY_MARK_ENTER("cont");
   58:     if (ptr) {
   59:         rb_context_t *cont = ptr;
   60:         rb_gc_mark(cont->value);
   61:         rb_gc_mark(cont->prev);
   62:         rb_thread_mark(&cont->saved_thread);
   63: 
   64:         if (cont->vm_stack) {
   65:             rb_gc_mark_locations(cont->vm_stack,
   66:                                  cont->vm_stack + cont->saved_thread.stack_size);
   67:         }
   68: 
   69:         if (cont->machine_stack) {
   70:             rb_gc_mark_locations(cont->machine_stack,
   71:                                  cont->machine_stack + cont->machine_stack_size);
   72:         }
   73: #ifdef __ia64
   74:         if (cont->machine_register_stack) {
   75:             rb_gc_mark_locations(cont->machine_register_stack,
   76:                                  cont->machine_register_stack + cont->machine_register_stack_size);
   77:         }
   78: #endif
   79:     }
   80:     RUBY_MARK_LEAVE("cont");
   81: }
   82: 
   83: static void
   84: cont_free(void *ptr)
   85: {
   86:     RUBY_FREE_ENTER("cont");
   87:     if (ptr) {
   88:         rb_context_t *cont = ptr;
   89:         RUBY_FREE_UNLESS_NULL(cont->saved_thread.stack);
   90:         RUBY_FREE_UNLESS_NULL(cont->machine_stack);
   91: #ifdef __ia64
   92:         RUBY_FREE_UNLESS_NULL(cont->machine_register_stack);
   93: #endif
   94:         RUBY_FREE_UNLESS_NULL(cont->vm_stack);
   95: 
   96:         if (cont->type == FIBER_CONTEXT) {
   97:             st_free_table(cont->saved_thread.local_storage);
   98:         }
   99: 
  100:         ruby_xfree(ptr);
  101:     }
  102:     RUBY_FREE_LEAVE("cont");
  103: }
  104: 
  105: static void
  106: cont_save_machine_stack(rb_thread_t *th, rb_context_t *cont)
  107: {
  108:     int size;
  109:     rb_thread_t *sth = &cont->saved_thread;
  110: 
  111:     SET_MACHINE_STACK_END(&th->machine_stack_end);
  112: #ifdef __ia64
  113:     th->machine_register_stack_end = rb_ia64_bsp();
  114: #endif
  115: 
  116:     if (th->machine_stack_start > th->machine_stack_end) {
  117:         size = cont->machine_stack_size = th->machine_stack_start - th->machine_stack_end;
  118:         cont->machine_stack_src = th->machine_stack_end;
  119:     }
  120:     else {
  121:         size = cont->machine_stack_size = th->machine_stack_end - th->machine_stack_start;
  122:         cont->machine_stack_src = th->machine_stack_start;
  123:     }
  124: 
  125:     if (cont->machine_stack) {
  126:         REALLOC_N(cont->machine_stack, VALUE, size);
  127:     }
  128:     else {
  129:         cont->machine_stack = ALLOC_N(VALUE, size);
  130:     }
  131: 
  132:     FLUSH_REGISTER_WINDOWS;
  133:     MEMCPY(cont->machine_stack, cont->machine_stack_src, VALUE, size);
  134: 
  135: #ifdef __ia64
  136:     rb_ia64_flushrs();
  137:     size = cont->machine_register_stack_size = th->machine_register_stack_end - th->machine_register_stack_start;
  138:     cont->machine_register_stack_src = th->machine_register_stack_start;
  139:     if (cont->machine_register_stack) {
  140:         REALLOC_N(cont->machine_register_stack, VALUE, size);
  141:     }
  142:     else {
  143:         cont->machine_register_stack = ALLOC_N(VALUE, size);
  144:     }
  145: 
  146:     MEMCPY(cont->machine_register_stack, cont->machine_register_stack_src, VALUE, size);
  147: #endif
  148: 
  149:     sth->machine_stack_start = sth->machine_stack_end = 0;
  150: #ifdef __ia64
  151:     sth->machine_register_stack_start = sth->machine_register_stack_end = 0;
  152: #endif
  153: }
  154: 
  155: static rb_context_t *
  156: cont_new(VALUE klass)
  157: {
  158:     rb_context_t *cont;
  159:     volatile VALUE contval;
  160:     rb_thread_t *th = GET_THREAD();
  161: 
  162:     contval = Data_Make_Struct(klass, rb_context_t,
  163:                                cont_mark, cont_free, cont);
  164: 
  165:     cont->self = contval;
  166:     cont->alive = Qtrue;
  167: 
  168:     /* save thread context */
  169:     cont->saved_thread = *th;
  170: 
  171:     return cont;
  172: }
  173: 
  174: void vm_stack_to_heap(rb_thread_t *th);
  175: 
  176: static VALUE
  177: cont_capture(volatile int *stat)
  178: {
  179:     rb_context_t *cont;
  180:     rb_thread_t *th = GET_THREAD(), *sth;
  181:     volatile VALUE contval;
  182: 
  183:     vm_stack_to_heap(th);
  184:     cont = cont_new(rb_cContinuation);
  185:     contval = cont->self;
  186:     sth = &cont->saved_thread;
  187: 
  188:     cont->vm_stack = ALLOC_N(VALUE, th->stack_size);
  189:     MEMCPY(cont->vm_stack, th->stack, VALUE, th->stack_size);
  190:     sth->stack = 0;
  191: 
  192:     cont_save_machine_stack(th, cont);
  193: 
  194:     if (ruby_setjmp(cont->jmpbuf)) {
  195:         VALUE value;
  196: 
  197:         value = cont->value;
  198:         cont->value = Qnil;
  199:         *stat = 1;
  200:         return value;
  201:     }
  202:     else {
  203:         *stat = 0;
  204:         return cont->self;
  205:     }
  206: }
  207: 
  208: NORETURN(static void cont_restore_1(rb_context_t *));
  209: 
  210: static void
  211: cont_restore_1(rb_context_t *cont)
  212: {
  213:     rb_thread_t *th = GET_THREAD(), *sth = &cont->saved_thread;
  214: 
  215:     /* restore thread context */
  216:     if (cont->type == CONTINUATION_CONTEXT) {
  217:         /* continuation */
  218:         VALUE fib;
  219: 
  220:         th->fiber = sth->fiber;
  221:         fib = th->fiber ? th->fiber : th->root_fiber;
  222: 
  223:         if (fib) {
  224:             rb_context_t *fcont;
  225:             GetContPtr(fib, fcont);
  226:             th->stack_size = fcont->saved_thread.stack_size;
  227:             th->stack = fcont->saved_thread.stack;
  228:         }
  229:         MEMCPY(th->stack, cont->vm_stack, VALUE, sth->stack_size);
  230:     }
  231:     else {
  232:         /* fiber */
  233:         th->stack = sth->stack;
  234:         th->stack_size = sth->stack_size;
  235:         th->local_storage = sth->local_storage;
  236:         th->fiber = cont->self;
  237:     }
  238: 
  239:     th->cfp = sth->cfp;
  240:     th->safe_level = sth->safe_level;
  241:     th->raised_flag = sth->raised_flag;
  242:     th->state = sth->state;
  243:     th->status = sth->status;
  244:     th->tag = sth->tag;
  245:     th->trap_tag = sth->trap_tag;
  246:     th->errinfo = sth->errinfo;
  247:     th->first_proc = sth->first_proc;
  248: 
  249:     /* restore machine stack */
  250: #ifdef _M_AMD64
  251:     {
  252:         /* workaround for x64 SEH */
  253:         jmp_buf buf;
  254:         setjmp(buf);
  255:         ((_JUMP_BUFFER*)(&cont->jmpbuf))->Frame =
  256:             ((_JUMP_BUFFER*)(&buf))->Frame;
  257:     }
  258: #endif
  259:     if (cont->machine_stack_src) {
  260:         FLUSH_REGISTER_WINDOWS;
  261:         MEMCPY(cont->machine_stack_src, cont->machine_stack,
  262:                VALUE, cont->machine_stack_size);
  263:     }
  264: 
  265: #ifdef __ia64
  266:     if (cont->machine_register_stack_src) {
  267:         MEMCPY(cont->machine_register_stack_src, cont->machine_register_stack,
  268:                VALUE, cont->machine_register_stack_size);
  269:     }
  270: #endif
  271: 
  272:     ruby_longjmp(cont->jmpbuf, 1);
  273: }
  274: 
  275: NORETURN(NOINLINE(static void cont_restore_0(rb_context_t *, VALUE *)));
  276: 
  277: #ifdef __ia64
  278: #define C(a) rse_##a##0, rse_##a##1, rse_##a##2, rse_##a##3, rse_##a##4
  279: #define E(a) rse_##a##0= rse_##a##1= rse_##a##2= rse_##a##3= rse_##a##4
  280: static volatile int C(a), C(b), C(c), C(d), C(e);
  281: static volatile int C(f), C(g), C(h), C(i), C(j);
  282: static volatile int C(k), C(l), C(m), C(n), C(o);
  283: static volatile int C(p), C(q), C(r), C(s), C(t);
  284: int rb_dummy_false = 0;
  285: NORETURN(NOINLINE(static void register_stack_extend(rb_context_t *, VALUE *)));
  286: static void
  287: register_stack_extend(rb_context_t *cont, VALUE *curr_bsp)
  288: {
  289:     if (rb_dummy_false) {
  290:         /* use registers as much as possible */
  291:         E(a) = E(b) = E(c) = E(d) = E(e) =
  292:         E(f) = E(g) = E(h) = E(i) = E(j) =
  293:         E(k) = E(l) = E(m) = E(n) = E(o) =
  294:         E(p) = E(q) = E(r) = E(s) = E(t) = 0;
  295:         E(a) = E(b) = E(c) = E(d) = E(e) =
  296:         E(f) = E(g) = E(h) = E(i) = E(j) =
  297:         E(k) = E(l) = E(m) = E(n) = E(o) =
  298:         E(p) = E(q) = E(r) = E(s) = E(t) = 0;
  299:     }
  300:     if (curr_bsp < cont->machine_register_stack_src+cont->machine_register_stack_size) {
  301:         register_stack_extend(cont, (VALUE*)rb_ia64_bsp());
  302:     }
  303:     cont_restore_1(cont);
  304: }
  305: #undef C
  306: #undef E
  307: #endif
  308: 
  309: static void
  310: cont_restore_0(rb_context_t *cont, VALUE *addr_in_prev_frame)
  311: {
  312:     if (cont->machine_stack_src) {
  313: #define STACK_PAD_SIZE 1024
  314:         VALUE space[STACK_PAD_SIZE];
  315: 
  316: #if STACK_GROW_DIRECTION < 0 /* downward */
  317:         if (addr_in_prev_frame > cont->machine_stack_src) {
  318:             cont_restore_0(cont, &space[0]);
  319:         }
  320: #elif STACK_GROW_DIRECTION > 0 /* upward */
  321:         if (addr_in_prev_frame < cont->machine_stack_src + cont->machine_stack_size) {
  322:             cont_restore_0(cont, &space[STACK_PAD_SIZE-1]);
  323:         }
  324: #else
  325:         if (addr_in_prev_frame > &space[0]) {
  326:             /* Stack grows downward */
  327:             if (addr_in_prev_frame > cont->saved_thread.machine_stack_src) {
  328:                 cont_restore_0(cont, &space[0]);
  329:             }
  330:         }
  331:         else {
  332:             /* Stack grows upward */
  333:             if (addr_in_prev_frame < cont->machine_stack_src + cont->machine_stack_size) {
  334:                 cont_restore_0(cont, &space[STACK_PAD_SIZE-1]);
  335:             }
  336:         }
  337: #endif
  338:     }
  339: #ifdef __ia64
  340:     register_stack_extend(cont, (VALUE*)rb_ia64_bsp());
  341: #else
  342:     cont_restore_1(cont);
  343: #endif
  344: }
  345: 
  346: /*
  347:  *  Document-class: Continuation
  348:  *
  349:  *  Continuation objects are generated by
  350:  *  <code>Kernel#callcc</code>. They hold a return address and execution
  351:  *  context, allowing a nonlocal return to the end of the
  352:  *  <code>callcc</code> block from anywhere within a program.
  353:  *  Continuations are somewhat analogous to a structured version of C's
  354:  *  <code>setjmp/longjmp</code> (although they contain more state, so
  355:  *  you might consider them closer to threads).
  356:  *     
  357:  *  For instance:
  358:  *     
  359:  *     arr = [ "Freddie", "Herbie", "Ron", "Max", "Ringo" ]
  360:  *     callcc{|$cc|}
  361:  *     puts(message = arr.shift)
  362:  *     $cc.call unless message =~ /Max/
  363:  *     
  364:  *  <em>produces:</em>
  365:  *     
  366:  *     Freddie
  367:  *     Herbie
  368:  *     Ron
  369:  *     Max
  370:  *     
  371:  *  This (somewhat contrived) example allows the inner loop to abandon
  372:  *  processing early:
  373:  *     
  374:  *     callcc {|cont|
  375:  *       for i in 0..4
  376:  *         print "\n#{i}: "
  377:  *         for j in i*5...(i+1)*5
  378:  *           cont.call() if j == 17
  379:  *           printf "%3d", j
  380:  *         end
  381:  *       end
  382:  *     }
  383:  *     print "\n"
  384:  *     
  385:  *  <em>produces:</em>
  386:  *     
  387:  *     0:   0  1  2  3  4
  388:  *     1:   5  6  7  8  9
  389:  *     2:  10 11 12 13 14
  390:  *     3:  15 16
  391:  */
  392: 
  393: /*
  394:  *  call-seq:
  395:  *     callcc {|cont| block }   =>  obj
  396:  *  
  397:  *  Generates a <code>Continuation</code> object, which it passes to the
  398:  *  associated block. Performing a <em>cont</em><code>.call</code> will
  399:  *  cause the <code>callcc</code> to return (as will falling through the
  400:  *  end of the block). The value returned by the <code>callcc</code> is
  401:  *  the value of the block, or the value passed to
  402:  *  <em>cont</em><code>.call</code>. See class <code>Continuation</code>
  403:  *  for more details. Also see <code>Kernel::throw</code> for
  404:  *  an alternative mechanism for unwinding a call stack.
  405:  */
  406: 
  407: static VALUE
  408: rb_callcc(VALUE self)
  409: {
  410:     volatile int called;
  411:     volatile VALUE val = cont_capture(&called);
  412: 
  413:     if (called) {
  414:         return val;
  415:     }
  416:     else {
  417:         return rb_yield(val);
  418:     }
  419: }
  420: 
  421: static VALUE
  422: make_passing_arg(int argc, VALUE *argv)
  423: {
  424:     switch(argc) {
  425:       case 0:
  426:         return Qnil;
  427:       case 1:
  428:         return argv[0];
  429:       default:
  430:         return rb_ary_new4(argc, argv);
  431:     }
  432: }
  433: 
  434: /*
  435:  *  call-seq:
  436:  *     cont.call(args, ...)
  437:  *     cont[args, ...]
  438:  *  
  439:  *  Invokes the continuation. The program continues from the end of the
  440:  *  <code>callcc</code> block. If no arguments are given, the original
  441:  *  <code>callcc</code> returns <code>nil</code>. If one argument is
  442:  *  given, <code>callcc</code> returns it. Otherwise, an array
  443:  *  containing <i>args</i> is returned.
  444:  *     
  445:  *     callcc {|cont|  cont.call }           #=> nil
  446:  *     callcc {|cont|  cont.call 1 }         #=> 1
  447:  *     callcc {|cont|  cont.call 1, 2, 3 }   #=> [1, 2, 3]
  448:  */
  449: 
  450: static VALUE
  451: rb_cont_call(int argc, VALUE *argv, VALUE contval)
  452: {
  453:     rb_context_t *cont;
  454:     rb_thread_t *th = GET_THREAD();
  455:     GetContPtr(contval, cont);
  456: 
  457:     if (cont->saved_thread.self != th->self) {
  458:         rb_raise(rb_eRuntimeError, "continuation called across threads");
  459:     }
  460:     if (cont->saved_thread.trap_tag != th->trap_tag) {
  461:         rb_raise(rb_eRuntimeError, "continuation called across trap");
  462:     }
  463:     if (cont->saved_thread.fiber) {
  464:         rb_context_t *fcont;
  465:         GetContPtr(cont->saved_thread.fiber, fcont);
  466: 
  467:         if (th->fiber != cont->saved_thread.fiber) {
  468:             rb_raise(rb_eRuntimeError, "continuation called across fiber");
  469:         }
  470:         
  471:         if (!fcont->alive) {
  472:             rb_raise(rb_eRuntimeError, "continuation called dead fiber");
  473:         }
  474:     }
  475: 
  476:     cont->value = make_passing_arg(argc, argv);
  477: 
  478:     cont_restore_0(cont, &contval);
  479:     return Qnil; /* unreachable */
  480: }
  481: 
  482: /*********/
  483: /* fiber */
  484: /*********/
  485: 
  486: #define FIBER_VM_STACK_SIZE (4 * 1024)
  487: 
  488: static rb_context_t *
  489: fiber_alloc(VALUE klass)
  490: {
  491:     rb_context_t *cont = cont_new(klass);
  492: 
  493:     cont->type = FIBER_CONTEXT;
  494:     cont->prev = Qnil;
  495: 
  496:     return cont;
  497: }
  498: 
  499: static VALUE
  500: fiber_new(VALUE klass, VALUE proc)
  501: {
  502:     rb_context_t *cont = fiber_alloc(klass);
  503:     VALUE contval = cont->self;
  504:     rb_thread_t *th = &cont->saved_thread;
  505: 
  506:     /* initialize */
  507:     cont->vm_stack = 0;
  508: 
  509:     th->stack = 0;
  510:     th->stack_size = FIBER_VM_STACK_SIZE;
  511:     th->stack = ALLOC_N(VALUE, th->stack_size);
  512: 
  513:     th->cfp = (void *)(th->stack + th->stack_size);
  514:     th->cfp--;
  515:     th->cfp->pc = 0;
  516:     th->cfp->sp = th->stack + 1;
  517:     th->cfp->bp = 0;
  518:     th->cfp->lfp = th->stack;
  519:     *th->cfp->lfp = 0;
  520:     th->cfp->dfp = th->stack;
  521:     th->cfp->self = Qnil;
  522:     th->cfp->flag = 0;
  523:     th->cfp->iseq = 0;
  524:     th->cfp->proc = 0;
  525:     th->cfp->block_iseq = 0;
  526:     th->tag = 0;
  527:     th->local_storage = st_init_numtable();
  528: 
  529:     th->first_proc = proc;
  530: 
  531:     MEMCPY(&cont->jmpbuf, &th->root_jmpbuf, rb_jmpbuf_t, 1);
  532: 
  533:     return contval;
  534: }
  535: 
  536: VALUE
  537: rb_fiber_new(VALUE (*func)(ANYARGS), VALUE obj)
  538: {
  539:     return fiber_new(rb_cFiber, rb_proc_new(func, obj));
  540: }
  541: 
  542: static VALUE
  543: rb_fiber_s_new(VALUE self)
  544: {
  545:     return fiber_new(self, rb_block_proc());
  546: }
  547: 
  548: static VALUE
  549: return_fiber(void)
  550: {
  551:     rb_context_t *cont;
  552:     VALUE curr = rb_fiber_current();
  553:     GetContPtr(curr, cont);
  554: 
  555:     if (cont->prev == Qnil) {
  556:         rb_thread_t *th = GET_THREAD();
  557: 
  558:         if (th->root_fiber != curr) {
  559:             return th->root_fiber;
  560:         }
  561:         else {
  562:             rb_raise(rb_eFiberError, "can't yield from root fiber");
  563:         }
  564:     }
  565:     else {
  566:         VALUE prev = cont->prev;
  567:         cont->prev = Qnil;
  568:         return prev;
  569:     }
  570: }
  571: 
  572: VALUE rb_fiber_transfer(VALUE fib, int argc, VALUE *argv);
  573: 
  574: static void
  575: rb_fiber_terminate(rb_context_t *cont)
  576: {
  577:     VALUE value = cont->value;
  578:     cont->alive = Qfalse;
  579:     rb_fiber_transfer(return_fiber(), 1, &value);
  580: }
  581: 
  582: void
  583: rb_fiber_start(void)
  584: {
  585:     rb_thread_t *th = GET_THREAD();
  586:     rb_context_t *cont;
  587:     rb_proc_t *proc;
  588:     VALUE args;
  589:     int state;
  590: 
  591:     GetContPtr(th->fiber, cont);
  592:     TH_PUSH_TAG(th);
  593:     if ((state = EXEC_TAG()) == 0) {
  594:         GetProcPtr(cont->saved_thread.first_proc, proc);
  595:         args = cont->value;
  596:         cont->value = Qnil;
  597:         th->errinfo = Qnil;
  598:         th->local_lfp = proc->block.lfp;
  599:         th->local_svar = Qnil;
  600: 
  601:         cont->value = vm_invoke_proc(th, proc, proc->block.self, 1, &args, 0);
  602:     }
  603: