gdunlap/sched-sim.hg

view simulator.c @ 6:403bd7680df6

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