gdunlap/sched-sim.hg

view simulator.c @ 11:31f36108fc43

c02: Initial commit (clone of c01)
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 20 18:14:37 2009 +0100 (2009-10-20)
parents 403bd7680df6
children f289f886cbcc
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 extern struct scheduler sched_credit02;
62 int default_scheduler = 0;
63 struct scheduler *schedulers[] =
64 {
65 &sched_rr,
66 &sched_credit01,
67 &sched_credit02,
68 NULL
69 };
71 /* Options */
73 struct global_pcpu_data P;
75 /* Sim list interface */
76 /* NB: Caller must free if they're not going to use it! */
77 #define list_event(_l) (list_entry((_l), struct event, event_list))
79 struct event* sim_remove_event(int type, int param)
80 {
81 struct event* ret = NULL;
82 struct list_head *pos, *tmp;
84 /* Look for an event that matches this one and remove it */
85 list_for_each_safe(pos, tmp, &sim.events)
86 {
87 struct event *tevt = list_event(pos);
88 if ( tevt->type == type
89 && tevt->param == param )
90 {
91 list_del(pos);
92 ret = tevt;
93 break;
94 }
95 }
97 return ret;
98 }
100 void sim_insert_event(int time, int type, int param, int reset)
101 {
102 struct list_head *pos = NULL;
103 struct event *evt=NULL;
105 ASSERT(time >= sim.now);
107 if ( reset )
108 evt=sim_remove_event(type, param);
110 if ( !evt )
111 evt = (struct event *)malloc(sizeof(*evt));
113 evt->time = time;
114 evt->type = type;
115 evt->param = param;
117 printf(" [insert t%d %s param%d]\n",
118 evt->time, event_name[evt->type], evt->param);
120 INIT_LIST_HEAD(&evt->event_list);
122 list_for_each(pos, &sim.events)
123 {
124 if ( list_event(pos)->time > evt->time )
125 break;
126 }
127 list_add_tail(&evt->event_list, pos);
128 }
130 struct event sim_next_event(void)
131 {
132 struct event *evt;
133 struct list_head *next;
135 ASSERT(!list_empty(&sim.events));
137 next=sim.events.next;
139 list_del(next);
141 evt=list_event(next);
143 printf("%d: evt %s param%d\n",
144 evt->time, event_name[evt->type], evt->param);
146 free(evt);
148 /* XXX */
149 return *evt;
150 }
152 /*
153 * VM simulation
154 */
155 void vm_next_event(struct vm *v)
156 {
157 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
159 v->e = v->workload->list + v->phase_index;
160 }
162 struct vm* vm_from_vid(int vid)
163 {
164 if ( vid >= V.count )
165 {
166 fprintf(stderr, "%s: v%d >= V.count %d!\n",
167 __func__, vid, V.count);
168 exit(1);
169 }
171 return V.vms + vid;
172 }
174 void vm_block(int now, struct vm *v)
175 {
176 ASSERT(v->e->type == PHASE_RUN);
177 v->time_this_phase += now - v->state_start_time;
178 printf("%s: v%d time_this_phase %d (evt %d)\n",
179 __func__, v->vid, v->time_this_phase, v->e->time);
181 ASSERT(v->time_this_phase == v->e->time);
183 vm_next_event(v);
185 ASSERT(v->e->type == PHASE_BLOCK);
187 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
188 v->time_this_phase = 0;
189 v->was_preempted = 0;
190 }
192 /* Called when wake event happens; increment timer and reset state */
193 void vm_wake(int now, struct vm *v)
194 {
195 ASSERT(v->e->type == PHASE_BLOCK);
196 ASSERT(v->time_this_phase == 0);
198 v->time_this_phase = now - v->state_start_time;
200 if ( now != 0 )
201 ASSERT(v->time_this_phase == v->e->time);
203 vm_next_event(v);
205 v->time_this_phase = 0;
206 }
208 /* Called when actually starting to run; make block event and set state */
209 void vm_run(int now, struct vm *v)
210 {
211 ASSERT(v->e->type == PHASE_RUN);
212 ASSERT(v->time_this_phase <= v->e->time);
214 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
215 v->state_start_time = now;
216 }
218 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
219 * generate a new block event) */
220 void vm_preempt(int now, struct vm *v)
221 {
222 struct event* evt;
224 v->time_this_phase += now - v->state_start_time;
225 printf("%s: v%d time_this_phase %d (evt %d)\n",
226 __func__, v->vid, v->time_this_phase, v->e->time);
228 ASSERT( v->time_this_phase <= v->e->time );
230 /* Only remove block event if we still have more runtime left */
231 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
232 free(evt);
234 v->was_preempted = 1;
235 }
238 /* Callbacks the scheduler may make */
239 void sim_sched_timer(int time, int pid)
240 {
241 if ( time < 0 )
242 {
243 fprintf(stderr, "%s: Time %d < 0!\n",
244 __func__, time);
245 abort();
246 }
248 if ( pid >= P.count )
249 {
250 fprintf(stderr, "%s: p%d >= P.count %d\n",
251 __func__, pid, P.count);
252 exit(1);
253 }
255 if ( P.pcpus[pid].idle )
256 {
257 P.pcpus[pid].idle = 0;
258 P.idle--;
259 }
260 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
261 }
263 void dump_running(int now, struct vm *v)
264 {
265 printf("runtime v%d %d %llu\n",
266 v->vid,
267 now,
268 v->stats.state[RUNSTATE_RUNNING].cycles);
269 }
271 void sim_runstate_change(int now, struct vm *v, int new_runstate)
272 {
273 int ostate, nstate;
274 int stime = now - v->state_start_time;
276 /* Valid transitions:
277 * + R->A (preemption): remove block event
278 * + R->B (block) : Insert wake event
279 * + A->R (run) : Insert block event
280 * + B->A (wake) : No action necessary
281 */
283 switch ( v->runstate )
284 {
285 case RUNSTATE_RUNNING:
286 ostate = STATE_RUN;
287 break;
288 case RUNSTATE_RUNNABLE:
289 if ( v->was_preempted )
290 ostate = STATE_PREEMPT;
291 else
292 ostate = STATE_WAKE;
293 break;
294 case RUNSTATE_BLOCKED:
295 ostate = STATE_BLOCK;
296 break;
297 }
299 update_cycles(&v->stats.state[ostate], stime);
301 if ( v->runstate == RUNSTATE_RUNNING
302 || new_runstate == RUNSTATE_RUNNING )
303 dump_running(now, v);
306 if ( v->runstate == RUNSTATE_RUNNING
307 && new_runstate == RUNSTATE_RUNNABLE )
308 {
309 nstate = STATE_PREEMPT;
310 vm_preempt(now, v);
311 }
312 else if ( v->runstate == RUNSTATE_RUNNING
313 && new_runstate == RUNSTATE_BLOCKED )
314 {
315 nstate = STATE_BLOCK;
316 vm_block(now, v);
317 }
318 else if ( v->runstate == RUNSTATE_RUNNABLE
319 && new_runstate == RUNSTATE_RUNNING )
320 {
321 nstate = STATE_RUN;
322 vm_run(now, v);
323 }
324 else if ( v->runstate == RUNSTATE_BLOCKED
325 && new_runstate == RUNSTATE_RUNNABLE )
326 {
327 nstate = STATE_WAKE;
328 vm_wake(now, v);
329 }
330 else
331 goto unexpected_transition;
333 printf("%d: v%d %s %d -> %s\n",
334 now, v->vid, state_name[ostate], stime, state_name[nstate]);
336 v->runstate = new_runstate;
337 v->state_start_time = now;
339 return;
341 unexpected_transition:
342 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
343 v->vid,
344 v->runstate,
345 new_runstate);
346 exit(1);
347 }
349 /*
350 * Main loop
351 */
352 void simulate(void)
353 {
354 while ( sim.now < opt.time_limit )
355 {
356 /* Take next event off list */
357 struct event evt;
359 evt = sim_next_event();
361 sim.now = evt.time;
363 switch(evt.type)
364 {
365 case EVT_WAKE:
366 {
367 struct vm *v = vm_from_vid(evt.param);
368 ASSERT(v->processor == -1);
369 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
370 sim.sched_ops->wake(sim.now, v->vid);
371 }
372 break;
373 case EVT_BLOCK:
374 {
375 struct vm *v = vm_from_vid(evt.param);
377 ASSERT(v->processor != -1);
378 ASSERT(v->processor <= P.count);
380 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
382 evt.param = v->processor; /* FIXME */
383 }
384 /* FALL-THRU */
385 case EVT_TIMER:
386 {
387 struct vm *prev, *next;
388 int pid = evt.param;
390 ASSERT(pid < P.count);
392 prev = P.pcpus[pid].current;
394 next = sim.sched_ops->schedule(sim.now, pid);
396 if ( prev && prev != next )
397 {
398 prev->processor = -1;
399 if( prev->runstate != RUNSTATE_BLOCKED )
400 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
401 }
404 P.pcpus[pid].current = next;
405 if ( next )
406 {
407 if ( next != prev )
408 {
409 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
410 next->processor = pid;
411 }
412 }
413 else
414 {
415 if ( P.pcpus[pid].idle )
416 {
417 fprintf(stderr, "Strange, pid %d already idle!\n",
418 pid);
419 abort();
420 }
422 /* If the pcpu is going idle, clear all timers from it */
423 sim_remove_event(EVT_TIMER, pid);
425 P.pcpus[pid].idle = 1;
426 P.idle++;
427 }
428 }
429 break;
430 default:
431 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
432 exit(1);
433 break;
434 }
435 }
436 }
438 void init(void)
439 {
440 int vid, i;
441 const struct workload *w;
443 /* Initialize simulation variables */
444 sim.now=0;
445 sim.timer=NULL;
446 INIT_LIST_HEAD(&sim.events);
447 sim.sched_ops = &opt.scheduler->ops;
449 /* Initialize pcpus */
450 P.count = opt.pcpu_count;
451 P.idle = 0;
452 for ( i=0; i<P.count; i++ )
453 {
454 P.pcpus[i].pid = i;
455 P.pcpus[i].idle = 1;
456 P.idle++;
457 P.pcpus[i].current = NULL;
458 }
460 /* Initialize scheduler */
461 sim.sched_ops->sched_init();
463 /* Initialize vms */
464 w=opt.workload;
465 V.count = 0;
466 for ( vid=0; vid<w->vm_count; vid++)
467 {
468 struct vm *v = V.vms+vid;
470 v->vid = vid;
471 v->runstate = RUNSTATE_BLOCKED;
472 v->processor = -1;
473 v->private = NULL;
475 v->state_start_time = 0;
476 v->time_this_phase = 0;
479 v->phase_index = -1;
480 v->e = NULL;
481 v->workload = w->vm_workloads+vid;
483 V.count++;
485 sim.sched_ops->vm_init(vid);
486 }
488 /* Set VM starting conditions */
489 for ( vid=0; vid<V.count; vid++)
490 {
491 struct vm *v = V.vms+vid;
493 switch(v->workload->list[0].type)
494 {
495 case PHASE_RUN:
496 v->phase_index = v->workload->phase_count - 1;
497 v->e = v->workload->list + v->phase_index;
499 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
500 v->state_start_time = sim.now;
501 v->time_this_phase = 0;
502 break;
503 case PHASE_BLOCK:
504 v->phase_index = 0;
505 v->e = v->workload->list;
507 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
508 v->state_start_time = sim.now;
509 v->time_this_phase = 0;
510 break;
511 }
512 }
513 }
515 void report(void)
516 {
517 int i, j;
519 for ( i=0; i<V.count; i++ )
520 {
521 struct vm *v = V.vms + i;
523 printf("VM %d\n", i);
524 for ( j = 0; j < STATE_MAX ; j++ )
525 {
526 char s[128];
527 snprintf(s, 128, " %s", state_name[j]);
528 print_cycle_summary(&v->stats.state[j], sim.now, s);
529 }
530 }
531 }
533 int main(int argc, char * argv[])
534 {
535 warn = stdout;
537 parse_options(argc, argv);
539 /* Setup simulation */
540 init();
542 /* Run simulation */
543 simulate();
544 /* Report statistics */
545 report();
546 }