gdunlap/sched-sim.hg

annotate simulator.c @ 1:ec2d50e41437

Handle multiple cpus.
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 13 17:29:50 2009 +0100 (2009-10-13)
parents d27bb3c56e71
children 1d7310217c5a
rev   line source
gdunlap@0 1 #include <stdlib.h>
gdunlap@0 2 #include <stdio.h>
gdunlap@0 3 #include <assert.h>
gdunlap@0 4
gdunlap@0 5 #define ASSERT assert
gdunlap@0 6
gdunlap@0 7 #include "stats.h"
gdunlap@0 8 #include "list.h"
gdunlap@0 9 #include "sim.h"
gdunlap@0 10 #include "workload.h"
gdunlap@0 11
gdunlap@0 12 FILE *warn;
gdunlap@0 13
gdunlap@0 14 enum event_type {
gdunlap@0 15 EVT_BLOCK,
gdunlap@0 16 EVT_WAKE,
gdunlap@0 17 EVT_TIMER,
gdunlap@0 18 EVT_MAX
gdunlap@0 19 };
gdunlap@0 20
gdunlap@0 21 char *event_name[EVT_MAX] = {
gdunlap@0 22 [EVT_BLOCK]="block",
gdunlap@0 23 [EVT_WAKE] ="wake ",
gdunlap@0 24 [EVT_TIMER]="timer"
gdunlap@0 25 };
gdunlap@0 26
gdunlap@0 27 struct event {
gdunlap@0 28 struct list_head event_list;
gdunlap@0 29 enum event_type type;
gdunlap@0 30 int time;
gdunlap@0 31 int param; /* Usually VM ID */
gdunlap@0 32 };
gdunlap@0 33
gdunlap@0 34 char * state_name[STATE_MAX] = {
gdunlap@0 35 [STATE_RUN]= "run ",
gdunlap@0 36 [STATE_PREEMPT]="preempt",
gdunlap@0 37 [STATE_WAKE]= "wake ",
gdunlap@0 38 [STATE_BLOCK]= "block ",
gdunlap@0 39 };
gdunlap@0 40
gdunlap@0 41 struct {
gdunlap@0 42 int now;
gdunlap@0 43 struct list_head events;
gdunlap@0 44 struct list_head *timer;
gdunlap@0 45 const struct sched_ops *sched_ops;
gdunlap@0 46 } sim;
gdunlap@0 47
gdunlap@0 48
gdunlap@1 49 #ifndef VM_DATA_PUBLIC
gdunlap@1 50 struct global_vm_data {
gdunlap@0 51 int count;
gdunlap@0 52 struct vm vms[MAX_VMS];
gdunlap@1 53 };
gdunlap@1 54 #endif
gdunlap@1 55 struct global_vm_data V;
gdunlap@0 56
gdunlap@0 57 extern struct scheduler sched_rr;
gdunlap@0 58 int default_scheduler = 0;
gdunlap@0 59 struct scheduler *schedulers[] =
gdunlap@0 60 {
gdunlap@0 61 &sched_rr,
gdunlap@0 62 };
gdunlap@0 63
gdunlap@0 64 /* Options */
gdunlap@0 65 struct {
gdunlap@0 66 int time_limit;
gdunlap@0 67 int pcpu_count;
gdunlap@0 68 const struct workload * workload;
gdunlap@0 69 const struct scheduler * scheduler;
gdunlap@0 70 } opt = {
gdunlap@0 71 .time_limit = 100000,
gdunlap@1 72 .pcpu_count = 2,
gdunlap@0 73 .workload = NULL,
gdunlap@0 74 };
gdunlap@0 75
gdunlap@0 76 struct global_pcpu_data P;
gdunlap@0 77
gdunlap@0 78 /* Sim list interface */
gdunlap@0 79 /* NB: Caller must free if they're not going to use it! */
gdunlap@0 80 #define list_event(_l) (list_entry((_l), struct event, event_list))
gdunlap@0 81
gdunlap@0 82 struct event* sim_remove_event(int type, int param)
gdunlap@0 83 {
gdunlap@0 84 struct event* ret = NULL;
gdunlap@0 85 struct list_head *pos, *tmp;
gdunlap@0 86
gdunlap@0 87 /* Look for an event that matches this one and remove it */
gdunlap@0 88 list_for_each_safe(pos, tmp, &sim.events)
gdunlap@0 89 {
gdunlap@0 90 struct event *tevt = list_event(pos);
gdunlap@0 91 if ( tevt->type == type
gdunlap@0 92 && tevt->param == param )
gdunlap@0 93 {
gdunlap@0 94 list_del(pos);
gdunlap@0 95 ret = tevt;
gdunlap@0 96 break;
gdunlap@0 97 }
gdunlap@0 98 }
gdunlap@0 99
gdunlap@0 100 return ret;
gdunlap@0 101 }
gdunlap@0 102
gdunlap@0 103 void sim_insert_event(int time, int type, int param, int reset)
gdunlap@0 104 {
gdunlap@0 105 struct list_head *pos = NULL;
gdunlap@0 106 struct event *evt=NULL;
gdunlap@0 107
gdunlap@0 108 ASSERT(time >= sim.now);
gdunlap@0 109
gdunlap@0 110 if ( reset )
gdunlap@0 111 evt=sim_remove_event(type, param);
gdunlap@0 112
gdunlap@0 113 if ( !evt )
gdunlap@0 114 evt = (struct event *)malloc(sizeof(*evt));
gdunlap@0 115
gdunlap@0 116 evt->time = time;
gdunlap@0 117 evt->type = type;
gdunlap@0 118 evt->param = param;
gdunlap@0 119
gdunlap@1 120 printf(" [insert t%d %s param%d]\n",
gdunlap@1 121 evt->time, event_name[evt->type], evt->param);
gdunlap@1 122
gdunlap@0 123 INIT_LIST_HEAD(&evt->event_list);
gdunlap@0 124
gdunlap@0 125 list_for_each(pos, &sim.events)
gdunlap@0 126 {
gdunlap@0 127 if ( list_event(pos)->time > evt->time )
gdunlap@0 128 break;
gdunlap@0 129 }
gdunlap@0 130 list_add_tail(&evt->event_list, pos);
gdunlap@0 131 }
gdunlap@0 132
gdunlap@0 133 struct event sim_next_event(void)
gdunlap@0 134 {
gdunlap@0 135 struct event *evt;
gdunlap@0 136 struct list_head *next;
gdunlap@0 137
gdunlap@0 138 ASSERT(!list_empty(&sim.events));
gdunlap@0 139
gdunlap@0 140 next=sim.events.next;
gdunlap@0 141
gdunlap@0 142 list_del(next);
gdunlap@0 143
gdunlap@0 144 evt=list_event(next);
gdunlap@0 145
gdunlap@0 146 printf("%d: evt %s param%d\n",
gdunlap@0 147 evt->time, event_name[evt->type], evt->param);
gdunlap@0 148
gdunlap@0 149 free(evt);
gdunlap@0 150
gdunlap@0 151 /* XXX */
gdunlap@0 152 return *evt;
gdunlap@0 153 }
gdunlap@0 154
gdunlap@0 155 /*
gdunlap@0 156 * VM simulation
gdunlap@0 157 */
gdunlap@0 158 void vm_next_event(struct vm *v)
gdunlap@0 159 {
gdunlap@0 160 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
gdunlap@0 161
gdunlap@0 162 v->e = v->workload->list + v->phase_index;
gdunlap@0 163 }
gdunlap@0 164
gdunlap@0 165 struct vm* vm_from_vid(int vid)
gdunlap@0 166 {
gdunlap@1 167 if ( vid >= V.count )
gdunlap@1 168 {
gdunlap@1 169 fprintf(stderr, "%s: v%d >= V.count %d!\n",
gdunlap@1 170 __func__, vid, V.count);
gdunlap@1 171 exit(1);
gdunlap@1 172 }
gdunlap@0 173
gdunlap@0 174 return V.vms + vid;
gdunlap@0 175 }
gdunlap@0 176
gdunlap@0 177 void vm_block(int now, struct vm *v)
gdunlap@0 178 {
gdunlap@0 179 ASSERT(v->e->type == PHASE_RUN);
gdunlap@0 180 v->time_this_phase += now - v->state_start_time;
gdunlap@0 181 printf("%s: v%d time_this_phase %d\n",
gdunlap@0 182 __func__, v->vid, v->time_this_phase);
gdunlap@0 183
gdunlap@0 184 ASSERT(v->time_this_phase == v->e->time);
gdunlap@0 185
gdunlap@0 186 vm_next_event(v);
gdunlap@0 187
gdunlap@0 188 ASSERT(v->e->type == PHASE_BLOCK);
gdunlap@0 189
gdunlap@0 190 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
gdunlap@0 191 v->time_this_phase = 0;
gdunlap@0 192 v->was_preempted = 0;
gdunlap@0 193 }
gdunlap@0 194
gdunlap@0 195 /* Called when wake event happens; increment timer and reset state */
gdunlap@0 196 void vm_wake(int now, struct vm *v)
gdunlap@0 197 {
gdunlap@0 198 ASSERT(v->e->type == PHASE_BLOCK);
gdunlap@0 199 ASSERT(v->time_this_phase == 0);
gdunlap@0 200
gdunlap@0 201 v->time_this_phase = now - v->state_start_time;
gdunlap@0 202
gdunlap@0 203 if ( now != 0 )
gdunlap@0 204 ASSERT(v->time_this_phase == v->e->time);
gdunlap@0 205
gdunlap@0 206 vm_next_event(v);
gdunlap@0 207
gdunlap@0 208 v->time_this_phase = 0;
gdunlap@0 209 }
gdunlap@0 210
gdunlap@0 211 /* Called when actually starting to run; make block event and set state */
gdunlap@0 212 void vm_run(int now, struct vm *v)
gdunlap@0 213 {
gdunlap@0 214 ASSERT(v->e->type == PHASE_RUN);
gdunlap@0 215 ASSERT(v->time_this_phase < v->e->time);
gdunlap@0 216
gdunlap@0 217 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
gdunlap@0 218 v->state_start_time = now;
gdunlap@0 219 }
gdunlap@0 220
gdunlap@0 221 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
gdunlap@0 222 * generate a new block event) */
gdunlap@0 223 void vm_preempt(int now, struct vm *v)
gdunlap@0 224 {
gdunlap@0 225 struct event* evt;
gdunlap@0 226
gdunlap@0 227 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
gdunlap@0 228 free(evt);
gdunlap@0 229
gdunlap@0 230 v->time_this_phase += now - v->state_start_time;
gdunlap@0 231 printf("%s: v%d time_this_phase %d\n",
gdunlap@0 232 __func__, v->vid, v->time_this_phase);
gdunlap@0 233
gdunlap@0 234 ASSERT(v->time_this_phase < v->e->time);
gdunlap@0 235
gdunlap@0 236 v->was_preempted = 1;
gdunlap@0 237 }
gdunlap@0 238
gdunlap@0 239
gdunlap@0 240 /* Callbacks the scheduler may make */
gdunlap@0 241 void sim_sched_timer(int time, int pid)
gdunlap@0 242 {
gdunlap@1 243 if ( pid >= P.count )
gdunlap@1 244 {
gdunlap@1 245 fprintf(stderr, "%s: p%d >= P.count %d\n",
gdunlap@1 246 __func__, pid, P.count);
gdunlap@1 247 exit(1);
gdunlap@1 248 }
gdunlap@1 249
gdunlap@1 250 if ( P.pcpus[pid].idle )
gdunlap@1 251 {
gdunlap@1 252 P.pcpus[pid].idle = 0;
gdunlap@1 253 P.idle--;
gdunlap@1 254 }
gdunlap@0 255 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
gdunlap@0 256 }
gdunlap@0 257
gdunlap@0 258 void sim_runstate_change(int now, struct vm *v, int new_runstate)
gdunlap@0 259 {
gdunlap@0 260 int ostate, nstate;
gdunlap@0 261 int stime = now - v->state_start_time;
gdunlap@0 262
gdunlap@0 263 /* Valid transitions:
gdunlap@0 264 * + R->A (preemption): remove block event
gdunlap@0 265 * + R->B (block) : Insert wake event
gdunlap@0 266 * + A->R (run) : Insert block event
gdunlap@0 267 * + B->A (wake) : No action necessary
gdunlap@0 268 */
gdunlap@0 269
gdunlap@0 270 switch ( v->runstate )
gdunlap@0 271 {
gdunlap@0 272 case RUNSTATE_RUNNING:
gdunlap@0 273 ostate = STATE_RUN;
gdunlap@0 274 break;
gdunlap@0 275 case RUNSTATE_RUNNABLE:
gdunlap@0 276 if ( v->was_preempted )
gdunlap@0 277 ostate = STATE_PREEMPT;
gdunlap@0 278 else
gdunlap@0 279 ostate = STATE_WAKE;
gdunlap@0 280 break;
gdunlap@0 281 case RUNSTATE_BLOCKED:
gdunlap@0 282 ostate = STATE_BLOCK;
gdunlap@0 283 break;
gdunlap@0 284 }
gdunlap@0 285
gdunlap@0 286 update_cycles(&v->stats.state[ostate], stime);
gdunlap@0 287
gdunlap@0 288
gdunlap@0 289 if ( v->runstate == RUNSTATE_RUNNING
gdunlap@0 290 && new_runstate == RUNSTATE_RUNNABLE )
gdunlap@0 291 {
gdunlap@0 292 nstate = STATE_PREEMPT;
gdunlap@0 293 vm_preempt(now, v);
gdunlap@0 294 }
gdunlap@0 295 else if ( v->runstate == RUNSTATE_RUNNING
gdunlap@0 296 && new_runstate == RUNSTATE_BLOCKED )
gdunlap@0 297 {
gdunlap@0 298 nstate = STATE_BLOCK;
gdunlap@0 299 vm_block(now, v);
gdunlap@0 300 }
gdunlap@0 301 else if ( v->runstate == RUNSTATE_RUNNABLE
gdunlap@0 302 && new_runstate == RUNSTATE_RUNNING )
gdunlap@0 303 {
gdunlap@0 304 nstate = STATE_RUN;
gdunlap@0 305 vm_run(now, v);
gdunlap@0 306 }
gdunlap@0 307 else if ( v->runstate == RUNSTATE_BLOCKED
gdunlap@0 308 && new_runstate == RUNSTATE_RUNNABLE )
gdunlap@0 309 {
gdunlap@0 310 nstate = STATE_WAKE;
gdunlap@0 311 vm_wake(now, v);
gdunlap@0 312 }
gdunlap@0 313 else
gdunlap@0 314 goto unexpected_transition;
gdunlap@0 315
gdunlap@0 316 printf("%d: v%d %s %d -> %s\n",
gdunlap@0 317 now, v->vid, state_name[ostate], stime, state_name[nstate]);
gdunlap@0 318
gdunlap@0 319 v->runstate = new_runstate;
gdunlap@0 320 v->state_start_time = now;
gdunlap@0 321
gdunlap@0 322 return;
gdunlap@0 323
gdunlap@0 324 unexpected_transition:
gdunlap@0 325 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
gdunlap@0 326 v->vid,
gdunlap@0 327 v->runstate,
gdunlap@0 328 new_runstate);
gdunlap@0 329 exit(1);
gdunlap@0 330 }
gdunlap@0 331
gdunlap@0 332 /*
gdunlap@0 333 * Main loop
gdunlap@0 334 */
gdunlap@0 335 void simulate(void)
gdunlap@0 336 {
gdunlap@0 337 while ( sim.now < opt.time_limit )
gdunlap@0 338 {
gdunlap@0 339 /* Take next event off list */
gdunlap@0 340 struct event evt;
gdunlap@0 341
gdunlap@0 342 evt = sim_next_event();
gdunlap@0 343
gdunlap@0 344 sim.now = evt.time;
gdunlap@0 345
gdunlap@0 346 switch(evt.type)
gdunlap@0 347 {
gdunlap@0 348 case EVT_WAKE:
gdunlap@0 349 {
gdunlap@0 350 struct vm *v = vm_from_vid(evt.param);
gdunlap@0 351 ASSERT(v->processor == -1);
gdunlap@0 352 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
gdunlap@0 353 sim.sched_ops->wake(sim.now, v);
gdunlap@0 354 }
gdunlap@0 355 break;
gdunlap@0 356 case EVT_BLOCK:
gdunlap@0 357 {
gdunlap@0 358 struct vm *v = vm_from_vid(evt.param);
gdunlap@0 359
gdunlap@0 360 ASSERT(v->processor != -1);
gdunlap@0 361 ASSERT(v->processor <= P.count);
gdunlap@0 362
gdunlap@0 363 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
gdunlap@0 364
gdunlap@0 365 evt.param = v->processor; /* FIXME */
gdunlap@0 366 }
gdunlap@0 367 /* FALL-THRU */
gdunlap@0 368 case EVT_TIMER:
gdunlap@0 369 {
gdunlap@0 370 struct vm *prev, *next;
gdunlap@0 371 int pid = evt.param;
gdunlap@0 372
gdunlap@0 373 ASSERT(pid < P.count);
gdunlap@0 374
gdunlap@0 375 prev = P.pcpus[pid].current;
gdunlap@0 376
gdunlap@0 377 next = sim.sched_ops->schedule(sim.now, pid);
gdunlap@0 378
gdunlap@0 379 if ( prev && prev != next )
gdunlap@0 380 {
gdunlap@0 381 prev->processor = -1;
gdunlap@0 382 if( prev->runstate != RUNSTATE_BLOCKED )
gdunlap@0 383 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
gdunlap@0 384 }
gdunlap@0 385
gdunlap@1 386
gdunlap@0 387 P.pcpus[pid].current = next;
gdunlap@1 388 if ( next )
gdunlap@1 389 {
gdunlap@1 390 if ( next != prev )
gdunlap@1 391 {
gdunlap@1 392 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
gdunlap@1 393 next->processor = pid;
gdunlap@1 394 }
gdunlap@1 395 }
gdunlap@1 396 else
gdunlap@1 397 {
gdunlap@1 398 P.pcpus[pid].idle = 1;
gdunlap@1 399 P.idle++;
gdunlap@1 400 }
gdunlap@0 401 }
gdunlap@0 402 break;
gdunlap@0 403 default:
gdunlap@0 404 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
gdunlap@0 405 exit(1);
gdunlap@0 406 break;
gdunlap@0 407 }
gdunlap@0 408 }
gdunlap@0 409 }
gdunlap@0 410
gdunlap@0 411 void init(void)
gdunlap@0 412 {
gdunlap@0 413 int vid, i;
gdunlap@0 414 const struct workload *w;
gdunlap@0 415
gdunlap@0 416 /* Initialize simulation variables */
gdunlap@0 417 sim.now=0;
gdunlap@0 418 sim.timer=NULL;
gdunlap@0 419 INIT_LIST_HEAD(&sim.events);
gdunlap@0 420 sim.sched_ops = &opt.scheduler->ops;
gdunlap@0 421
gdunlap@0 422 /* Initialize pcpus */
gdunlap@0 423 P.count = opt.pcpu_count;
gdunlap@1 424 P.idle = 0;
gdunlap@0 425 for ( i=0; i<P.count; i++ )
gdunlap@0 426 {
gdunlap@0 427 P.pcpus[i].pid = i;
gdunlap@1 428 P.pcpus[i].idle = 1;
gdunlap@1 429 P.idle++;
gdunlap@0 430 P.pcpus[i].current = NULL;
gdunlap@0 431 }
gdunlap@0 432
gdunlap@0 433 /* Initialize scheduler */
gdunlap@0 434 sim.sched_ops->sched_init();
gdunlap@0 435
gdunlap@0 436 /* Initialize vms */
gdunlap@0 437 w=opt.workload;
gdunlap@1 438 V.count = 0;
gdunlap@0 439 for ( vid=0; vid<w->vm_count; vid++)
gdunlap@0 440 {
gdunlap@0 441 struct vm *v = V.vms+vid;
gdunlap@0 442
gdunlap@0 443 v->vid = vid;
gdunlap@0 444 v->runstate = RUNSTATE_BLOCKED;
gdunlap@0 445 v->processor = -1;
gdunlap@0 446 v->private = NULL;
gdunlap@0 447
gdunlap@0 448 v->state_start_time = 0;
gdunlap@0 449 v->time_this_phase = 0;
gdunlap@0 450
gdunlap@0 451
gdunlap@0 452 v->phase_index = -1;
gdunlap@0 453 v->e = NULL;
gdunlap@0 454 v->workload = w->vm_workloads+vid;
gdunlap@0 455
gdunlap@0 456 V.count++;
gdunlap@0 457
gdunlap@0 458 sim.sched_ops->vm_init(vid);
gdunlap@0 459 }
gdunlap@0 460
gdunlap@0 461 /* Set VM starting conditions */
gdunlap@0 462 for ( vid=0; vid<V.count; vid++)
gdunlap@0 463 {
gdunlap@0 464 struct vm *v = V.vms+vid;
gdunlap@0 465
gdunlap@0 466 switch(v->workload->list[0].type)
gdunlap@0 467 {
gdunlap@0 468 case PHASE_RUN:
gdunlap@0 469 v->phase_index = v->workload->phase_count - 1;
gdunlap@0 470 v->e = v->workload->list + v->phase_index;
gdunlap@0 471
gdunlap@0 472 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
gdunlap@0 473 v->state_start_time = sim.now;
gdunlap@0 474 v->time_this_phase = 0;
gdunlap@0 475 break;
gdunlap@0 476 case PHASE_BLOCK:
gdunlap@0 477 v->phase_index = 0;
gdunlap@0 478 v->e = v->workload->list;
gdunlap@0 479
gdunlap@0 480 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
gdunlap@0 481 v->state_start_time = sim.now;
gdunlap@0 482 v->time_this_phase = 0;
gdunlap@0 483 break;
gdunlap@0 484 }
gdunlap@0 485 }
gdunlap@0 486 }
gdunlap@0 487
gdunlap@0 488 void report(void)
gdunlap@0 489 {
gdunlap@0 490 int i, j;
gdunlap@0 491
gdunlap@0 492 for ( i=0; i<V.count; i++ )
gdunlap@0 493 {
gdunlap@0 494 struct vm *v = V.vms + i;
gdunlap@0 495
gdunlap@0 496 printf("VM %d\n", i);
gdunlap@0 497 for ( j = 0; j < STATE_MAX ; j++ )
gdunlap@0 498 {
gdunlap@0 499 char s[128];
gdunlap@0 500 snprintf(s, 128, " %s", state_name[j]);
gdunlap@0 501 print_cycle_summary(&v->stats.state[j], sim.now, s);
gdunlap@0 502 }
gdunlap@0 503 }
gdunlap@0 504 }
gdunlap@0 505
gdunlap@0 506 int main(int argc, char * argv[])
gdunlap@0 507 {
gdunlap@0 508 warn = stdout;
gdunlap@0 509
gdunlap@0 510 /* Read opts, config file? */
gdunlap@0 511 if ( !opt.workload )
gdunlap@0 512 opt.workload = builtin_workloads+default_workload;
gdunlap@0 513
gdunlap@0 514 if ( !opt.scheduler )
gdunlap@0 515 opt.scheduler = schedulers[default_scheduler];
gdunlap@0 516 /* Setup simulation */
gdunlap@0 517 init();
gdunlap@0 518
gdunlap@0 519 /* Run simulation */
gdunlap@0 520 simulate();
gdunlap@0 521 /* Report statistics */
gdunlap@0 522 report();
gdunlap@0 523 }