gdunlap@0: #include <stdlib.h>
gdunlap@0: #include <stdio.h>
gdunlap@0: #include <assert.h>
gdunlap@0: 
gdunlap@0: #define ASSERT assert
gdunlap@0: 
gdunlap@0: #include "stats.h"
gdunlap@0: #include "list.h"
gdunlap@0: #include "sim.h"
gdunlap@0: #include "workload.h"
gdunlap@0: 
gdunlap@0: FILE *warn;
gdunlap@0: 
gdunlap@0: enum event_type {
gdunlap@0:     EVT_BLOCK,
gdunlap@0:     EVT_WAKE,
gdunlap@0:     EVT_TIMER,
gdunlap@0:     EVT_MAX
gdunlap@0: };
gdunlap@0: 
gdunlap@0: char *event_name[EVT_MAX] = {
gdunlap@0:     [EVT_BLOCK]="block",
gdunlap@0:     [EVT_WAKE] ="wake ",
gdunlap@0:     [EVT_TIMER]="timer"
gdunlap@0: };
gdunlap@0: 
gdunlap@0: struct event {
gdunlap@0:     struct list_head event_list;
gdunlap@0:     enum event_type type;
gdunlap@0:     int time;
gdunlap@0:     int param;  /* Usually VM ID */ 
gdunlap@0: };
gdunlap@0: 
gdunlap@0: char * state_name[STATE_MAX] = {
gdunlap@0:     [STATE_RUN]=    "run    ",
gdunlap@0:     [STATE_PREEMPT]="preempt",
gdunlap@0:     [STATE_WAKE]=   "wake   ",
gdunlap@0:     [STATE_BLOCK]=  "block  ",
gdunlap@0: };
gdunlap@0: 
gdunlap@0: struct {
gdunlap@0:     int now;
gdunlap@0:     struct list_head events;
gdunlap@0:     struct list_head *timer;
gdunlap@0:     const struct sched_ops *sched_ops;
gdunlap@0: } sim;
gdunlap@0: 
gdunlap@0: 
gdunlap@0: struct {
gdunlap@0:     int count;
gdunlap@0:     struct vm vms[MAX_VMS];
gdunlap@0: } V;
gdunlap@0: 
gdunlap@0: extern struct scheduler sched_rr;
gdunlap@0: int default_scheduler = 0;
gdunlap@0: struct scheduler *schedulers[] =
gdunlap@0: {
gdunlap@0:     &sched_rr,
gdunlap@0: };
gdunlap@0: 
gdunlap@0: /* Options */
gdunlap@0: struct {
gdunlap@0:     int time_limit;
gdunlap@0:     int pcpu_count;
gdunlap@0:     const struct workload * workload;
gdunlap@0:     const struct scheduler * scheduler;
gdunlap@0: } opt = {
gdunlap@0:     .time_limit = 100000,
gdunlap@0:     .pcpu_count = 1,
gdunlap@0:     .workload = NULL,
gdunlap@0: };
gdunlap@0: 
gdunlap@0: struct global_pcpu_data P;
gdunlap@0: 
gdunlap@0: /* Sim list interface */
gdunlap@0: /* NB: Caller must free if they're not going to use it! */
gdunlap@0: #define list_event(_l) (list_entry((_l), struct event, event_list))
gdunlap@0: 
gdunlap@0: struct event* sim_remove_event(int type, int param)
gdunlap@0: {
gdunlap@0:     struct event* ret = NULL;
gdunlap@0:     struct list_head *pos, *tmp;
gdunlap@0: 
gdunlap@0:     /* Look for an event that matches this one and remove it */
gdunlap@0:     list_for_each_safe(pos, tmp, &sim.events)
gdunlap@0:     {
gdunlap@0:         struct event *tevt = list_event(pos);
gdunlap@0:         if ( tevt->type == type
gdunlap@0:              && tevt->param == param )
gdunlap@0:         {
gdunlap@0:             list_del(pos);
gdunlap@0:             ret = tevt;
gdunlap@0:             break;
gdunlap@0:         }
gdunlap@0:     }
gdunlap@0: 
gdunlap@0:     return ret;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: void sim_insert_event(int time, int type, int param, int reset)
gdunlap@0: {
gdunlap@0:     struct list_head *pos = NULL;
gdunlap@0:     struct event *evt=NULL;
gdunlap@0: 
gdunlap@0:     ASSERT(time >= sim.now);
gdunlap@0: 
gdunlap@0:     if ( reset )
gdunlap@0:         evt=sim_remove_event(type, param);
gdunlap@0: 
gdunlap@0:     if ( !evt )
gdunlap@0:         evt = (struct event *)malloc(sizeof(*evt));
gdunlap@0: 
gdunlap@0:     printf(" [insert t%d %s param%d]\n",
gdunlap@0:            evt->time, event_name[evt->type], evt->param);
gdunlap@0: 
gdunlap@0:     evt->time = time;
gdunlap@0:     evt->type = type;
gdunlap@0:     evt->param = param;
gdunlap@0: 
gdunlap@0:     INIT_LIST_HEAD(&evt->event_list);
gdunlap@0: 
gdunlap@0:     list_for_each(pos, &sim.events)
gdunlap@0:     {
gdunlap@0:         if ( list_event(pos)->time > evt->time )
gdunlap@0:             break;
gdunlap@0:     }
gdunlap@0:     list_add_tail(&evt->event_list, pos);
gdunlap@0: }
gdunlap@0: 
gdunlap@0: struct event sim_next_event(void)
gdunlap@0: {
gdunlap@0:     struct event *evt;
gdunlap@0:     struct list_head *next;
gdunlap@0: 
gdunlap@0:     ASSERT(!list_empty(&sim.events));
gdunlap@0: 
gdunlap@0:     next=sim.events.next;
gdunlap@0: 
gdunlap@0:     list_del(next);
gdunlap@0:     
gdunlap@0:     evt=list_event(next);
gdunlap@0: 
gdunlap@0:     printf("%d: evt %s param%d\n",
gdunlap@0:            evt->time, event_name[evt->type], evt->param);
gdunlap@0: 
gdunlap@0:     free(evt);
gdunlap@0: 
gdunlap@0:     /* XXX */
gdunlap@0:     return *evt;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: /*
gdunlap@0:  * VM simulation
gdunlap@0:  */
gdunlap@0: void vm_next_event(struct vm *v)
gdunlap@0: {
gdunlap@0:     v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
gdunlap@0: 
gdunlap@0:     v->e = v->workload->list + v->phase_index;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: struct vm* vm_from_vid(int vid)
gdunlap@0: {
gdunlap@0:     ASSERT(vid < V.count);
gdunlap@0: 
gdunlap@0:     return V.vms + vid;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: void vm_block(int now, struct vm *v)
gdunlap@0: {
gdunlap@0:     ASSERT(v->e->type == PHASE_RUN);
gdunlap@0:     v->time_this_phase += now - v->state_start_time;
gdunlap@0:     printf("%s: v%d time_this_phase %d\n",
gdunlap@0:            __func__, v->vid, v->time_this_phase);
gdunlap@0: 
gdunlap@0:     ASSERT(v->time_this_phase == v->e->time);
gdunlap@0: 
gdunlap@0:     vm_next_event(v);
gdunlap@0:     
gdunlap@0:     ASSERT(v->e->type == PHASE_BLOCK);
gdunlap@0: 
gdunlap@0:     sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
gdunlap@0:     v->time_this_phase = 0;
gdunlap@0:     v->was_preempted = 0;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: /* Called when wake event happens; increment timer and reset state */
gdunlap@0: void vm_wake(int now, struct vm *v)
gdunlap@0: {
gdunlap@0:     ASSERT(v->e->type == PHASE_BLOCK);
gdunlap@0:     ASSERT(v->time_this_phase == 0);
gdunlap@0: 
gdunlap@0:     v->time_this_phase = now - v->state_start_time;
gdunlap@0: 
gdunlap@0:     if ( now != 0 )
gdunlap@0:         ASSERT(v->time_this_phase == v->e->time);
gdunlap@0: 
gdunlap@0:     vm_next_event(v);
gdunlap@0: 
gdunlap@0:     v->time_this_phase = 0;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: /* Called when actually starting to run; make block event and set state */
gdunlap@0: void vm_run(int now, struct vm *v)
gdunlap@0: {
gdunlap@0:     ASSERT(v->e->type == PHASE_RUN);
gdunlap@0:     ASSERT(v->time_this_phase < v->e->time);
gdunlap@0: 
gdunlap@0:     sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
gdunlap@0:     v->state_start_time = now;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
gdunlap@0:  * generate a new block event) */
gdunlap@0: void vm_preempt(int now, struct vm *v)
gdunlap@0: {
gdunlap@0:     struct event* evt;
gdunlap@0: 
gdunlap@0:     if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
gdunlap@0:         free(evt);
gdunlap@0: 
gdunlap@0:     v->time_this_phase += now - v->state_start_time;
gdunlap@0:     printf("%s: v%d time_this_phase %d\n",
gdunlap@0:            __func__, v->vid, v->time_this_phase);
gdunlap@0: 
gdunlap@0:     ASSERT(v->time_this_phase < v->e->time);
gdunlap@0: 
gdunlap@0:     v->was_preempted = 1;
gdunlap@0: }
gdunlap@0: 
gdunlap@0: 
gdunlap@0: /* Callbacks the scheduler may make */
gdunlap@0: void sim_sched_timer(int time, int pid)
gdunlap@0: {
gdunlap@0:     sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
gdunlap@0: }
gdunlap@0: 
gdunlap@0: void sim_runstate_change(int now, struct vm *v, int new_runstate)
gdunlap@0: {
gdunlap@0:     int ostate, nstate;
gdunlap@0:     int stime = now - v->state_start_time;
gdunlap@0: 
gdunlap@0:     /* Valid transitions:
gdunlap@0:      * + R->A (preemption): remove block event
gdunlap@0:      * + R->B (block)     : Insert wake event
gdunlap@0:      * + A->R (run)       : Insert block event
gdunlap@0:      * + B->A (wake)      : No action necessary
gdunlap@0:      */
gdunlap@0: 
gdunlap@0:     switch ( v->runstate )
gdunlap@0:     {
gdunlap@0:     case RUNSTATE_RUNNING:
gdunlap@0:         ostate = STATE_RUN;
gdunlap@0:         break;
gdunlap@0:     case RUNSTATE_RUNNABLE:
gdunlap@0:         if ( v->was_preempted )
gdunlap@0:             ostate = STATE_PREEMPT;
gdunlap@0:         else
gdunlap@0:             ostate = STATE_WAKE;
gdunlap@0:         break;
gdunlap@0:     case RUNSTATE_BLOCKED:
gdunlap@0:         ostate = STATE_BLOCK;
gdunlap@0:         break;
gdunlap@0:     }
gdunlap@0: 
gdunlap@0:     update_cycles(&v->stats.state[ostate], stime);
gdunlap@0: 
gdunlap@0: 
gdunlap@0:     if ( v->runstate == RUNSTATE_RUNNING
gdunlap@0:          && new_runstate == RUNSTATE_RUNNABLE )
gdunlap@0:     {
gdunlap@0:         nstate = STATE_PREEMPT;
gdunlap@0:         vm_preempt(now, v);
gdunlap@0:     }
gdunlap@0:     else if ( v->runstate == RUNSTATE_RUNNING
gdunlap@0:               && new_runstate == RUNSTATE_BLOCKED )
gdunlap@0:     {
gdunlap@0:         nstate = STATE_BLOCK;
gdunlap@0:         vm_block(now, v);
gdunlap@0:     }
gdunlap@0:     else if ( v->runstate == RUNSTATE_RUNNABLE
gdunlap@0:               && new_runstate == RUNSTATE_RUNNING )
gdunlap@0:     {
gdunlap@0:         nstate = STATE_RUN;
gdunlap@0:         vm_run(now, v);
gdunlap@0:     }
gdunlap@0:     else if ( v->runstate == RUNSTATE_BLOCKED
gdunlap@0:               && new_runstate == RUNSTATE_RUNNABLE )
gdunlap@0:     {
gdunlap@0:         nstate = STATE_WAKE;
gdunlap@0:         vm_wake(now, v);
gdunlap@0:     }
gdunlap@0:     else
gdunlap@0:         goto unexpected_transition;
gdunlap@0: 
gdunlap@0:     printf("%d: v%d %s %d -> %s\n",
gdunlap@0:            now, v->vid, state_name[ostate], stime, state_name[nstate]);
gdunlap@0: 
gdunlap@0:     v->runstate = new_runstate;
gdunlap@0:     v->state_start_time = now;
gdunlap@0: 
gdunlap@0:     return;
gdunlap@0: 
gdunlap@0: unexpected_transition:
gdunlap@0:     fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
gdunlap@0:             v->vid,
gdunlap@0:             v->runstate,
gdunlap@0:             new_runstate);
gdunlap@0:     exit(1);
gdunlap@0: }
gdunlap@0: 
gdunlap@0: /* 
gdunlap@0:  * Main loop
gdunlap@0:  */
gdunlap@0: void simulate(void)
gdunlap@0: {
gdunlap@0:     while ( sim.now < opt.time_limit )
gdunlap@0:     {
gdunlap@0:         /* Take next event off list */
gdunlap@0:         struct event evt;
gdunlap@0: 
gdunlap@0:         evt = sim_next_event();
gdunlap@0: 
gdunlap@0:         sim.now = evt.time;
gdunlap@0: 
gdunlap@0:         switch(evt.type)
gdunlap@0:         {
gdunlap@0:         case EVT_WAKE:
gdunlap@0:         {
gdunlap@0:             struct vm *v = vm_from_vid(evt.param);
gdunlap@0:             ASSERT(v->processor == -1);
gdunlap@0:             sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
gdunlap@0:             sim.sched_ops->wake(sim.now, v);
gdunlap@0:         }
gdunlap@0:         break;
gdunlap@0:         case EVT_BLOCK:
gdunlap@0:         {
gdunlap@0:             struct vm *v = vm_from_vid(evt.param);
gdunlap@0: 
gdunlap@0:             ASSERT(v->processor != -1);
gdunlap@0:             ASSERT(v->processor <= P.count);
gdunlap@0: 
gdunlap@0:             sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
gdunlap@0: 
gdunlap@0:             evt.param = v->processor; /* FIXME */
gdunlap@0:         }
gdunlap@0:         /* FALL-THRU */
gdunlap@0:         case EVT_TIMER:
gdunlap@0:         {
gdunlap@0:             struct vm *prev, *next;
gdunlap@0:             int pid = evt.param;
gdunlap@0: 
gdunlap@0:             ASSERT(pid < P.count);
gdunlap@0: 
gdunlap@0:             prev = P.pcpus[pid].current;
gdunlap@0: 
gdunlap@0:             next = sim.sched_ops->schedule(sim.now, pid);
gdunlap@0: 
gdunlap@0:             if ( prev && prev != next )
gdunlap@0:             {
gdunlap@0:                 prev->processor = -1;
gdunlap@0:                 if( prev->runstate != RUNSTATE_BLOCKED )
gdunlap@0:                     sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
gdunlap@0:             }
gdunlap@0: 
gdunlap@0:             sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
gdunlap@0:             P.pcpus[pid].current = next;
gdunlap@0:             next->processor = pid;
gdunlap@0:         }
gdunlap@0:         break;
gdunlap@0:         default:
gdunlap@0:             fprintf(stderr, "Unexpected event type: %d\n", evt.type);
gdunlap@0:             exit(1);
gdunlap@0:             break;
gdunlap@0:         }
gdunlap@0:     }
gdunlap@0: }
gdunlap@0: 
gdunlap@0: void init(void)
gdunlap@0: {
gdunlap@0:     int vid, i;
gdunlap@0:     const struct workload *w;
gdunlap@0: 
gdunlap@0:     /* Initialize simulation variables */
gdunlap@0:     sim.now=0;
gdunlap@0:     sim.timer=NULL;
gdunlap@0:     INIT_LIST_HEAD(&sim.events);
gdunlap@0:     sim.sched_ops = &opt.scheduler->ops;
gdunlap@0: 
gdunlap@0:     /* Initialize pcpus */
gdunlap@0:     P.count = opt.pcpu_count;
gdunlap@0:     for ( i=0; i<P.count; i++ )
gdunlap@0:     {
gdunlap@0:         P.pcpus[i].pid = i;
gdunlap@0:         P.pcpus[i].current = NULL;
gdunlap@0:     }
gdunlap@0: 
gdunlap@0:     /* Initialize scheduler */
gdunlap@0:     sim.sched_ops->sched_init();
gdunlap@0: 
gdunlap@0:     /* Initialize vms */
gdunlap@0:     w=opt.workload;
gdunlap@0:     for ( vid=0; vid<w->vm_count; vid++)
gdunlap@0:     {
gdunlap@0:         struct vm *v = V.vms+vid;
gdunlap@0: 
gdunlap@0:         v->vid = vid;
gdunlap@0:         v->runstate = RUNSTATE_BLOCKED;
gdunlap@0:         v->processor = -1;
gdunlap@0:         v->private = NULL;
gdunlap@0: 
gdunlap@0:         v->state_start_time = 0;
gdunlap@0:         v->time_this_phase = 0;
gdunlap@0:         
gdunlap@0: 
gdunlap@0:         v->phase_index = -1;
gdunlap@0:         v->e = NULL;
gdunlap@0:         v->workload = w->vm_workloads+vid;
gdunlap@0:         
gdunlap@0:         V.count++;
gdunlap@0: 
gdunlap@0:         sim.sched_ops->vm_init(vid);
gdunlap@0:     }
gdunlap@0: 
gdunlap@0:     /* Set VM starting conditions */
gdunlap@0:     for ( vid=0; vid<V.count; vid++)
gdunlap@0:     {
gdunlap@0:         struct vm *v = V.vms+vid;
gdunlap@0: 
gdunlap@0:         switch(v->workload->list[0].type)
gdunlap@0:         {
gdunlap@0:         case PHASE_RUN:
gdunlap@0:             v->phase_index = v->workload->phase_count - 1;
gdunlap@0:             v->e = v->workload->list + v->phase_index;
gdunlap@0: 
gdunlap@0:             sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
gdunlap@0:             v->state_start_time = sim.now;
gdunlap@0:             v->time_this_phase = 0;
gdunlap@0:             break;
gdunlap@0:         case PHASE_BLOCK:
gdunlap@0:             v->phase_index = 0;
gdunlap@0:             v->e = v->workload->list;
gdunlap@0: 
gdunlap@0:             sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
gdunlap@0:             v->state_start_time = sim.now;
gdunlap@0:             v->time_this_phase = 0;
gdunlap@0:             break;
gdunlap@0:         }
gdunlap@0:     }
gdunlap@0: 
gdunlap@0:     /* Insert initial scheduler timer */
gdunlap@0:     for ( i=0; i<P.count; i++)
gdunlap@0:         sim_insert_event(sim.now, EVT_TIMER, i, 1);
gdunlap@0: }
gdunlap@0: 
gdunlap@0: void report(void)
gdunlap@0: {
gdunlap@0:     int i, j;
gdunlap@0: 
gdunlap@0:     for ( i=0; i<V.count; i++ )
gdunlap@0:     {
gdunlap@0:         struct vm *v = V.vms + i;
gdunlap@0: 
gdunlap@0:         printf("VM %d\n", i);
gdunlap@0:         for ( j = 0; j < STATE_MAX ; j++ )
gdunlap@0:         {
gdunlap@0:             char s[128];
gdunlap@0:             snprintf(s, 128, " %s", state_name[j]);
gdunlap@0:             print_cycle_summary(&v->stats.state[j],   sim.now, s);
gdunlap@0:         }
gdunlap@0:     }
gdunlap@0: }
gdunlap@0: 
gdunlap@0: int main(int argc, char * argv[])
gdunlap@0: {
gdunlap@0:     warn = stdout;
gdunlap@0: 
gdunlap@0:     /* Read opts, config file? */
gdunlap@0:     if ( !opt.workload )
gdunlap@0:         opt.workload = builtin_workloads+default_workload;
gdunlap@0: 
gdunlap@0:     if ( !opt.scheduler )
gdunlap@0:         opt.scheduler = schedulers[default_scheduler];
gdunlap@0:     /* Setup simulation */
gdunlap@0:     init();
gdunlap@0:     
gdunlap@0:     /* Run simulation */
gdunlap@0:     simulate();
gdunlap@0:     /* Report statistics */
gdunlap@0:     report();
gdunlap@0: }