src/simix/RawContext.cpp

   1 /* Copyright (c) 2009-2015. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 /** \file Rawcontext.cpp
   8   * Fast context switching inspired from SystemV ucontexts.
   9   *
  10   * In contrast to System V context, it does not touch the signal mask
  11   * which avoids making a system call (at least on Linux).
  12   */
  13
  14 #include <math.h>
  15
  16 #include <xbt/log.h>
  17 #include <xbt/parmap.h>
  18 #include <xbt/dynar.h>
  19
  20 #include "smx_private.h"
  21 #include "smx_private.hpp"
  22 #include "mc/mc.h"
  23
  24 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(simix_context);
  25
  26 // ***** Class definitions
  27
  28 namespace simgrid {
  29 namespace simix {
  30
  31 class RawContext;
  32 class RawContextFactory;
  33
  34 class RawContext : public Context {
  35 protected:
  36   void* stack_ = nullptr;
  37   /** pointer to top the stack stack */
  38   void* stack_top_ = nullptr;
  39 public:
  40   friend class RawContextFactory;
  41   RawContext(xbt_main_func_t code,
  42           int argc, char **argv,
  43           void_pfn_smxprocess_t cleanup_func,
  44           smx_process_t process);
  45   ~RawContext();
  46 public:
  47   static void wrapper(void* arg);
  48   void stop() override;
  49   void suspend() override;
  50   void resume();
  51 private:
  52   void suspend_serial();
  53   void suspend_parallel();
  54   void resume_serial();
  55   void resume_parallel();
  56 };
  57
  58 class RawContextFactory : public ContextFactory {
  59 public:
  60   RawContextFactory();
  61   ~RawContextFactory();
  62   RawContext* create_context(
  63     xbt_main_func_t, int, char **, void_pfn_smxprocess_t,
  64     smx_process_t process
  65     ) override;
  66   void run_all() override;
  67 private:
  68   void run_all_adaptative();
  69   void run_all_serial();
  70   void run_all_parallel();
  71 };
  72
  73 ContextFactory* raw_factory()
  74 {
  75   XBT_VERB("Using raw contexts. "
  76     "Because the glibc is just not good enough for us.");
  77   return new RawContextFactory();
  78 }
  79
  80 }
  81 }
  82
  83 // ***** Loads of static stuff
  84
  85 #ifdef CONTEXT_THREADS
  86 static xbt_parmap_t raw_parmap;
  87 static simgrid::simix::RawContext** raw_workers_context;    /* space to save the worker context in each thread */
  88 static unsigned long raw_threads_working;     /* number of threads that have started their work */
  89 static xbt_os_thread_key_t raw_worker_id_key; /* thread-specific storage for the thread id */
  90 #endif
  91 #ifdef ADAPTIVE_THRESHOLD
  92 #define SCHED_ROUND_LIMIT 5
  93 static xbt_os_timer_t round_time;
  94 static double par_time,seq_time;
  95 static double par_ratio,seq_ratio;
  96 static int reached_seq_limit, reached_par_limit;
  97 static unsigned int par_proc_that_ran = 0,seq_proc_that_ran = 0;  /* Counters of processes that have run in SCHED_ROUND_LIMIT scheduling rounds */
  98 static unsigned int seq_sched_round=0, par_sched_round=0; /* Amount of SR that ran serial/parallel*/
  99 /*Varables used to calculate running variance and mean*/
 100 static double prev_avg_par_proc=0,prev_avg_seq_proc=0;
 101 static double delta=0;
 102 static double s_par_proc=0,s_seq_proc=0; /*Standard deviation of number of processes computed in par/seq during the current simulation*/
 103 static double avg_par_proc=0,sd_par_proc=0;
 104 static double avg_seq_proc=0,sd_seq_proc=0;
 105 static long long par_window=(long long)HUGE_VAL,seq_window=0;
 106 #endif
 107 static unsigned long raw_process_index = 0;   /* index of the next process to run in the
 108                                                * list of runnable processes */
 109 static simgrid::simix::RawContext* raw_maestro_context;
 110
 111 static bool raw_context_parallel = false;
 112 #ifdef ADAPTIVE_THRESHOLD
 113 static bool raw_context_adaptative = false;
 114 #endif
 115
 116 // ***** Raw context routines
 117
 118 typedef void (*rawctx_entry_point_t)(void *);
 119
 120 typedef void* raw_stack_t;
 121 extern "C" raw_stack_t raw_makecontext(void* malloced_stack, int stack_size,
 122                                    rawctx_entry_point_t entry_point, void* arg);
 123 extern "C" void raw_swapcontext(raw_stack_t* old, raw_stack_t new_context);
 124
 125 #if PROCESSOR_x86_64
 126 __asm__ (
 127 #if defined(APPLE)
 128    ".text\n"
 129    ".globl _raw_makecontext\n"
 130    "_raw_makecontext:\n"
 131 #elif defined(_WIN32)
 132    ".text\n"
 133    ".globl raw_makecontext\n"
 134    "raw_makecontext:\n"
 135 #else
 136    ".text\n"
 137    ".globl raw_makecontext\n"
 138    ".type raw_makecontext,@function\n"
 139    "raw_makecontext:\n"/* Calling convention sets the arguments in rdi, rsi, rdx and rcx, respectively */
 140 #endif
 141    "   mov %rdi,%rax\n"      /* stack */
 142    "   add %rsi,%rax\n"      /* size  */
 143    "   andq $-16, %rax\n"    /* align stack */
 144    "   movq $0,   -8(%rax)\n" /* @return for func */
 145    "   mov %rdx,-16(%rax)\n" /* func */
 146    "   mov %rcx,-24(%rax)\n" /* arg/rdi */
 147    "   movq $0,  -32(%rax)\n" /* rsi */
 148    "   movq $0,  -40(%rax)\n" /* rdx */
 149    "   movq $0,  -48(%rax)\n" /* rcx */
 150    "   movq $0,  -56(%rax)\n" /* r8  */
 151    "   movq $0,  -64(%rax)\n" /* r9  */
 152    "   movq $0,  -72(%rax)\n" /* rbp */
 153    "   movq $0,  -80(%rax)\n" /* rbx */
 154    "   movq $0,  -88(%rax)\n" /* r12 */
 155    "   movq $0,  -96(%rax)\n" /* r13 */
 156    "   movq $0, -104(%rax)\n" /* r14 */
 157    "   movq $0, -112(%rax)\n" /* r15 */
 158    "   sub $112,%rax\n"
 159    "   ret\n"
 160 );
 161
 162 __asm__ (
 163 #if defined(APPLE)
 164    ".text\n"
 165    ".globl _raw_swapcontext\n"
 166    "_raw_swapcontext:\n"
 167 #elif defined(_WIN32)
 168    ".text\n"
 169    ".globl raw_swapcontext\n"
 170    "raw_swapcontext:\n"
 171 #else
 172    ".text\n"
 173    ".globl raw_swapcontext\n"
 174    ".type raw_swapcontext,@function\n"
 175    "raw_swapcontext:\n" /* Calling convention sets the arguments in rdi and rsi, respectively */
 176 #endif
 177    "   push %rdi\n"
 178    "   push %rsi\n"
 179    "   push %rdx\n"
 180    "   push %rcx\n"
 181    "   push %r8\n"
 182    "   push %r9\n"
 183    "   push %rbp\n"
 184    "   push %rbx\n"
 185    "   push %r12\n"
 186    "   push %r13\n"
 187    "   push %r14\n"
 188    "   push %r15\n"
 189    "   mov %rsp,(%rdi)\n" /* old */
 190    "   mov %rsi,%rsp\n" /* new */
 191    "   pop %r15\n"
 192    "   pop %r14\n"
 193    "   pop %r13\n"
 194    "   pop %r12\n"
 195    "   pop %rbx\n"
 196    "   pop %rbp\n"
 197    "   pop %r9\n"
 198    "   pop %r8\n"
 199    "   pop %rcx\n"
 200    "   pop %rdx\n"
 201    "   pop %rsi\n"
 202    "   pop %rdi\n"
 203    "   ret\n"
 204 );
 205 #elif PROCESSOR_i686
 206 __asm__ (
 207 #if defined(APPLE) || defined(_WIN32)
 208    ".text\n"
 209    ".globl _raw_makecontext\n"
 210    "_raw_makecontext:\n"
 211 #else
 212    ".text\n"
 213    ".globl raw_makecontext\n"
 214    ".type raw_makecontext,@function\n"
 215    "raw_makecontext:\n"
 216 #endif
 217    "   movl 4(%esp),%eax\n"   /* stack */
 218    "   addl 8(%esp),%eax\n"   /* size  */
 219    "   andl $-16, %eax\n"     /* align stack */
 220    "   movl 12(%esp),%ecx\n"  /* func  */
 221    "   movl 16(%esp),%edx\n"  /* arg   */
 222    "   movl %edx, -4(%eax)\n"
 223    "   movl $0,   -8(%eax)\n" /* @return for func */
 224    "   movl %ecx,-12(%eax)\n"
 225    "   movl $0,  -16(%eax)\n" /* ebp */
 226    "   movl $0,  -20(%eax)\n" /* ebx */
 227    "   movl $0,  -24(%eax)\n" /* esi */
 228    "   movl $0,  -28(%eax)\n" /* edi */
 229    "   subl $28,%eax\n"
 230    "   retl\n"
 231 );
 232
 233 __asm__ (
 234 #if defined(APPLE) || defined(_WIN32)
 235    ".text\n"
 236    ".globl _raw_swapcontext\n"
 237    "_raw_swapcontext:\n"
 238 #else
 239    ".text\n"
 240    ".globl raw_swapcontext\n"
 241    ".type raw_swapcontext,@function\n"
 242    "raw_swapcontext:\n"
 243 #endif
 244    "   movl 4(%esp),%eax\n" /* old */
 245    "   movl 8(%esp),%edx\n" /* new */
 246    "   pushl %ebp\n"
 247    "   pushl %ebx\n"
 248    "   pushl %esi\n"
 249    "   pushl %edi\n"
 250    "   movl %esp,(%eax)\n"
 251    "   movl %edx,%esp\n"
 252    "   popl %edi\n"
 253    "   popl %esi\n"
 254    "   popl %ebx\n"
 255    "   popl %ebp\n"
 256    "   retl\n"
 257 );
 258 #else
 259
 260
 261 /* If you implement raw contexts for other processors, don't forget to
 262    update the definition of HAVE_RAWCTX in tools/cmake/CompleteInFiles.cmake */
 263
 264 raw_stack_t raw_makecontext(void* malloced_stack, int stack_size,
 265                             rawctx_entry_point_t entry_point, void* arg) {
 266    THROW_UNIMPLEMENTED;
 267 }
 268
 269 void raw_swapcontext(raw_stack_t* old, raw_stack_t new_context) {
 270    THROW_UNIMPLEMENTED;
 271 }
 272
 273 #endif
 274
 275 // ***** Method definitions
 276
 277 namespace simgrid {
 278 namespace simix {
 279
 280 RawContextFactory::RawContextFactory()
 281   : ContextFactory("RawContextFactory")
 282 {
 283 #ifdef ADAPTIVE_THRESHOLD
 284   raw_context_adaptative = (SIMIX_context_get_parallel_threshold() > 1);
 285 #endif
 286   raw_context_parallel = SIMIX_context_is_parallel();
 287   if (raw_context_parallel) {
 288 #ifdef CONTEXT_THREADS
 289     int nthreads = SIMIX_context_get_nthreads();
 290     xbt_os_thread_key_create(&raw_worker_id_key);
 291     // TODO, lazily init
 292     raw_parmap = nullptr;
 293     raw_workers_context = xbt_new(RawContext*, nthreads);
 294     raw_maestro_context = nullptr;
 295 #endif
 296     // TODO, if(SIMIX_context_get_parallel_threshold() > 1) => choose dynamically
 297   }
 298 #ifdef ADAPTIVE_THRESHOLD
 299   round_time = xbt_os_timer_new();
 300   reached_seq_limit = 0;
 301   reached_par_limit = 0;
 302 #endif
 303 }
 304
 305 RawContextFactory::~RawContextFactory()
 306 {
 307 #ifdef CONTEXT_THREADS
 308   if (raw_parmap)
 309     xbt_parmap_destroy(raw_parmap);
 310   xbt_free(raw_workers_context);
 311 #endif
 312 }
 313
 314 RawContext* RawContextFactory::create_context(
 315     xbt_main_func_t code, int argc, char ** argv,
 316     void_pfn_smxprocess_t cleanup,
 317     smx_process_t process)
 318 {
 319   return this->new_context<RawContext>(code, argc, argv,
 320     cleanup, process);
 321 }
 322
 323 void RawContext::wrapper(void* arg)
 324 {
 325   RawContext* context = (RawContext*) arg;
 326   (*context)();
 327   context->stop();
 328 }
 329
 330 RawContext::RawContext(
 331     xbt_main_func_t code, int argc, char ** argv,
 332     void_pfn_smxprocess_t cleanup,
 333     smx_process_t process)
 334   : Context(code, argc, argv, cleanup, process)
 335 {
 336    if (code) {
 337      this->stack_ = SIMIX_context_stack_new();
 338      this->stack_top_ = raw_makecontext(this->stack_,
 339                          smx_context_usable_stack_size,
 340                          RawContext::wrapper,
 341                          this);
 342    } else {
 343      if(process != nullptr && raw_maestro_context == nullptr)
 344        raw_maestro_context = this;
 345      if (MC_is_active())
 346        MC_ignore_heap(
 347          &raw_maestro_context->stack_top_,
 348          sizeof(raw_maestro_context->stack_top_));
 349    }
 350 }
 351
 352 RawContext::~RawContext()
 353 {
 354   SIMIX_context_stack_delete(this->stack_);
 355 }
 356
 357 void RawContext::stop()
 358 {
 359   Context::stop();
 360   this->suspend();
 361 }
 362
 363 void RawContextFactory::run_all()
 364 {
 365 #ifdef ADAPTIVE_THRESHOLD
 366   if (raw_context_adaptative)
 367     run_all_adaptative();
 368   else
 369 #endif
 370   if (raw_context_parallel)
 371     run_all_parallel();
 372   else
 373     run_all_serial();
 374 }
 375
 376 void RawContextFactory::run_all_serial()
 377 {
 378   smx_process_t first_process =
 379       xbt_dynar_get_as(simix_global->process_to_run, 0, smx_process_t);
 380   raw_process_index = 1;
 381   static_cast<RawContext*>(first_process->context)->resume_serial();
 382 }
 383
 384 void RawContextFactory::run_all_parallel()
 385 {
 386 #ifdef CONTEXT_THREADS
 387   raw_threads_working = 0;
 388   if (raw_parmap == nullptr)
 389     raw_parmap = xbt_parmap_new(
 390       SIMIX_context_get_nthreads(), SIMIX_context_get_parallel_mode());
 391   xbt_parmap_apply(raw_parmap,
 392       [](void* arg) {
 393         smx_process_t process = static_cast<smx_process_t>(arg);
 394         RawContext* context = static_cast<RawContext*>(process->context);
 395         context->resume_parallel();
 396       },
 397       simix_global->process_to_run);
 398 #else
 399   xbt_die("You asked for a parallel execution, but you don't have any threads.");
 400 #endif
 401 }
 402
 403 void RawContext::suspend()
 404 {
 405   if (raw_context_parallel)
 406     RawContext::suspend_parallel();
 407   else
 408     RawContext::suspend_serial();
 409 }
 410
 411 void RawContext::suspend_serial()
 412 {
 413   /* determine the next context */
 414   RawContext* next_context = nullptr;
 415   unsigned long int i;
 416   i = raw_process_index++;
 417   if (i < xbt_dynar_length(simix_global->process_to_run)) {
 418     /* execute the next process */
 419     XBT_DEBUG("Run next process");
 420     next_context = (RawContext*) xbt_dynar_get_as(
 421         simix_global->process_to_run, i, smx_process_t)->context;
 422   }
 423   else {
 424     /* all processes were run, return to maestro */
 425     XBT_DEBUG("No more process to run");
 426     next_context = (RawContext*) raw_maestro_context;
 427   }
 428   SIMIX_context_set_current(next_context);
 429   raw_swapcontext(&this->stack_top_, next_context->stack_top_);
 430 }
 431
 432 void RawContext::suspend_parallel()
 433 {
 434 #ifdef CONTEXT_THREADS
 435   /* determine the next context */
 436   smx_process_t next_work = (smx_process_t) xbt_parmap_next(raw_parmap);
 437   RawContext* next_context = nullptr;
 438
 439   if (next_work != NULL) {
 440     /* there is a next process to resume */
 441     XBT_DEBUG("Run next process");
 442     next_context = (RawContext*) next_work->context;
 443   }
 444   else {
 445     /* all processes were run, go to the barrier */
 446     XBT_DEBUG("No more processes to run");
 447     unsigned long worker_id = (unsigned long)(uintptr_t)
 448       xbt_os_thread_get_specific(raw_worker_id_key);
 449     next_context = (RawContext*) raw_workers_context[worker_id];
 450     XBT_DEBUG("Restoring worker stack %lu (working threads = %lu)",
 451         worker_id, raw_threads_working);
 452   }
 453
 454   SIMIX_context_set_current(next_context);
 455   raw_swapcontext(&this->stack_top_, next_context->stack_top_);
 456 #endif
 457 }
 458
 459 void RawContext::resume()
 460 {
 461   if (raw_context_parallel)
 462     resume_parallel();
 463   else
 464     resume_serial();
 465 }
 466
 467 void RawContext::resume_serial()
 468 {
 469   SIMIX_context_set_current(this);
 470   raw_swapcontext(&raw_maestro_context->stack_top_, this->stack_top_);
 471 }
 472
 473 void RawContext::resume_parallel()
 474 {
 475 #ifdef CONTEXT_THREADS
 476   unsigned long worker_id = __sync_fetch_and_add(&raw_threads_working, 1);
 477   xbt_os_thread_set_specific(raw_worker_id_key, (void*)(uintptr_t) worker_id);
 478   RawContext* worker_context = (RawContext*) SIMIX_context_self();
 479   raw_workers_context[worker_id] = worker_context;
 480   XBT_DEBUG("Saving worker stack %lu", worker_id);
 481   SIMIX_context_set_current(this);
 482   raw_swapcontext(&worker_context->stack_top_, this->stack_top_);
 483 #else
 484   xbt_die("Parallel execution disabled");
 485 #endif
 486 }
 487
 488 /**
 489  * \brief Resumes all processes ready to run.
 490  */
 491 #ifdef ADAPTIVE_THRESHOLD
 492 void RawContectFactory::run_all_adaptative()
 493 {
 494   unsigned long nb_processes = xbt_dynar_length(simix_global->process_to_run);
 495   unsigned long threshold = SIMIX_context_get_parallel_threshold();
 496   reached_seq_limit = (seq_sched_round % SCHED_ROUND_LIMIT == 0);
 497   reached_par_limit = (par_sched_round % SCHED_ROUND_LIMIT == 0);
 498
 499   if(reached_seq_limit && reached_par_limit){
 500     par_ratio = (par_proc_that_ran != 0) ? (par_time / (double)par_proc_that_ran) : 0;
 501     seq_ratio = (seq_proc_that_ran != 0) ? (seq_time / (double)seq_proc_that_ran) : 0;
 502     if(seq_ratio > par_ratio){
 503        if(nb_processes < avg_par_proc) {
 504           threshold = (threshold>2) ? threshold - 1 : threshold ;
 505           SIMIX_context_set_parallel_threshold(threshold);
 506         }
 507     } else {
 508         if(nb_processes > avg_seq_proc){
 509           SIMIX_context_set_parallel_threshold(threshold+1);
 510         }
 511     }
 512   }
 513
 514   if (nb_processes >= SIMIX_context_get_parallel_threshold()) {
 515     simix_global->context_factory->suspend = smx_ctx_raw_suspend_parallel;
 516     if (nb_processes < par_window){
 517       par_sched_round++;
 518       xbt_os_walltimer_start(round_time);
 519       smx_ctx_raw_runall_parallel();
 520       xbt_os_walltimer_stop(round_time);
 521       par_time += xbt_os_timer_elapsed(round_time);
 522
 523       prev_avg_par_proc = avg_par_proc;
 524       delta = nb_processes - avg_par_proc;
 525       avg_par_proc = (par_sched_round==1) ? nb_processes : avg_par_proc + delta / (double) par_sched_round;
 526
 527       if(par_sched_round>=2){
 528         s_par_proc = s_par_proc + (nb_processes - prev_avg_par_proc) * delta;
 529         sd_par_proc = sqrt(s_par_proc / (par_sched_round-1));
 530         par_window = (int) (avg_par_proc + sd_par_proc);
 531       }else{
 532         sd_par_proc = 0;
 533       }
 534
 535       par_proc_that_ran += nb_processes;
 536     } else{
 537       smx_ctx_raw_runall_parallel();
 538     }
 539   } else {
 540     simix_global->context_factory->suspend = smx_ctx_raw_suspend_serial;
 541     if(nb_processes > seq_window){
 542       seq_sched_round++;
 543       xbt_os_walltimer_start(round_time);
 544       smx_ctx_raw_runall_serial();
 545       xbt_os_walltimer_stop(round_time);
 546       seq_time += xbt_os_timer_elapsed(round_time);
 547
 548       prev_avg_seq_proc = avg_seq_proc;
 549       delta = (nb_processes-avg_seq_proc);
 550       avg_seq_proc = (seq_sched_round==1) ? nb_processes : avg_seq_proc + delta / (double) seq_sched_round;
 551
 552       if(seq_sched_round>=2){
 553         s_seq_proc = s_seq_proc + (nb_processes - prev_avg_seq_proc)*delta;
 554         sd_seq_proc = sqrt(s_seq_proc / (seq_sched_round-1));
 555         seq_window = (int) (avg_seq_proc - sd_seq_proc);
 556       } else {
 557         sd_seq_proc = 0;
 558       }
 559
 560       seq_proc_that_ran += nb_processes;
 561     } else {
 562       smx_ctx_raw_runall_serial();
 563     }
 564   }
 565 }
 566
 567 #else
 568
 569 // TODO
 570 void RawContextFactory::run_all_adaptative()
 571 {
 572   unsigned long nb_processes = xbt_dynar_length(simix_global->process_to_run);
 573   if (SIMIX_context_is_parallel()
 574     && (unsigned long) SIMIX_context_get_parallel_threshold() < nb_processes) {
 575         raw_context_parallel = true;
 576         XBT_DEBUG("Runall // %lu", nb_processes);
 577         this->run_all_parallel();
 578     } else {
 579         XBT_DEBUG("Runall serial %lu", nb_processes);
 580         raw_context_parallel = false;
 581         this->run_all_serial();
 582     }
 583 }
 584 #endif
 585
 586 }
 587 }