gdunlap/sched-sim.hg

view simulator.c @ 3:d957708efa86

Fix some simulator bugs, mostly dealing with events happening at the same time
author George Dunlap <gdunlap@xensource.com>
date Mon Oct 19 20:11:33 2009 +0100 (2009-10-19)
parents 1d7310217c5a
children 18f3d6e25ffc
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 int default_scheduler = 0;
61 struct scheduler *schedulers[] =
62 {
63 &sched_rr,
64 NULL
65 };
67 /* Options */
69 struct global_pcpu_data P;
71 /* Sim list interface */
72 /* NB: Caller must free if they're not going to use it! */
73 #define list_event(_l) (list_entry((_l), struct event, event_list))
75 struct event* sim_remove_event(int type, int param)
76 {
77 struct event* ret = NULL;
78 struct list_head *pos, *tmp;
80 /* Look for an event that matches this one and remove it */
81 list_for_each_safe(pos, tmp, &sim.events)
82 {
83 struct event *tevt = list_event(pos);
84 if ( tevt->type == type
85 && tevt->param == param )
86 {
87 list_del(pos);
88 ret = tevt;
89 break;
90 }
91 }
93 return ret;
94 }
96 void sim_insert_event(int time, int type, int param, int reset)
97 {
98 struct list_head *pos = NULL;
99 struct event *evt=NULL;
101 ASSERT(time >= sim.now);
103 if ( reset )
104 evt=sim_remove_event(type, param);
106 if ( !evt )
107 evt = (struct event *)malloc(sizeof(*evt));
109 evt->time = time;
110 evt->type = type;
111 evt->param = param;
113 printf(" [insert t%d %s param%d]\n",
114 evt->time, event_name[evt->type], evt->param);
116 INIT_LIST_HEAD(&evt->event_list);
118 list_for_each(pos, &sim.events)
119 {
120 if ( list_event(pos)->time > evt->time )
121 break;
122 }
123 list_add_tail(&evt->event_list, pos);
124 }
126 struct event sim_next_event(void)
127 {
128 struct event *evt;
129 struct list_head *next;
131 ASSERT(!list_empty(&sim.events));
133 next=sim.events.next;
135 list_del(next);
137 evt=list_event(next);
139 printf("%d: evt %s param%d\n",
140 evt->time, event_name[evt->type], evt->param);
142 free(evt);
144 /* XXX */
145 return *evt;
146 }
148 /*
149 * VM simulation
150 */
151 void vm_next_event(struct vm *v)
152 {
153 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
155 v->e = v->workload->list + v->phase_index;
156 }
158 struct vm* vm_from_vid(int vid)
159 {
160 if ( vid >= V.count )
161 {
162 fprintf(stderr, "%s: v%d >= V.count %d!\n",
163 __func__, vid, V.count);
164 exit(1);
165 }
167 return V.vms + vid;
168 }
170 void vm_block(int now, struct vm *v)
171 {
172 ASSERT(v->e->type == PHASE_RUN);
173 v->time_this_phase += now - v->state_start_time;
174 printf("%s: v%d time_this_phase %d (evt %d)\n",
175 __func__, v->vid, v->time_this_phase, v->e->time);
177 ASSERT(v->time_this_phase == v->e->time);
179 vm_next_event(v);
181 ASSERT(v->e->type == PHASE_BLOCK);
183 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
184 v->time_this_phase = 0;
185 v->was_preempted = 0;
186 }
188 /* Called when wake event happens; increment timer and reset state */
189 void vm_wake(int now, struct vm *v)
190 {
191 ASSERT(v->e->type == PHASE_BLOCK);
192 ASSERT(v->time_this_phase == 0);
194 v->time_this_phase = now - v->state_start_time;
196 if ( now != 0 )
197 ASSERT(v->time_this_phase == v->e->time);
199 vm_next_event(v);
201 v->time_this_phase = 0;
202 }
204 /* Called when actually starting to run; make block event and set state */
205 void vm_run(int now, struct vm *v)
206 {
207 ASSERT(v->e->type == PHASE_RUN);
208 ASSERT(v->time_this_phase <= v->e->time);
210 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
211 v->state_start_time = now;
212 }
214 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
215 * generate a new block event) */
216 void vm_preempt(int now, struct vm *v)
217 {
218 struct event* evt;
220 v->time_this_phase += now - v->state_start_time;
221 printf("%s: v%d time_this_phase %d (evt %d)\n",
222 __func__, v->vid, v->time_this_phase, v->e->time);
224 ASSERT( v->time_this_phase <= v->e->time );
226 /* Only remove block event if we still have more runtime left */
227 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
228 free(evt);
230 v->was_preempted = 1;
231 }
234 /* Callbacks the scheduler may make */
235 void sim_sched_timer(int time, int pid)
236 {
237 if ( time < 0 )
238 {
239 fprintf(stderr, "%s: Time %d < 0!\n",
240 __func__, time);
241 abort();
242 }
244 if ( pid >= P.count )
245 {
246 fprintf(stderr, "%s: p%d >= P.count %d\n",
247 __func__, pid, P.count);
248 exit(1);
249 }
251 if ( P.pcpus[pid].idle )
252 {
253 P.pcpus[pid].idle = 0;
254 P.idle--;
255 }
256 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
257 }
259 void sim_runstate_change(int now, struct vm *v, int new_runstate)
260 {
261 int ostate, nstate;
262 int stime = now - v->state_start_time;
264 /* Valid transitions:
265 * + R->A (preemption): remove block event
266 * + R->B (block) : Insert wake event
267 * + A->R (run) : Insert block event
268 * + B->A (wake) : No action necessary
269 */
271 switch ( v->runstate )
272 {
273 case RUNSTATE_RUNNING:
274 ostate = STATE_RUN;
275 break;
276 case RUNSTATE_RUNNABLE:
277 if ( v->was_preempted )
278 ostate = STATE_PREEMPT;
279 else
280 ostate = STATE_WAKE;
281 break;
282 case RUNSTATE_BLOCKED:
283 ostate = STATE_BLOCK;
284 break;
285 }
287 update_cycles(&v->stats.state[ostate], stime);
290 if ( v->runstate == RUNSTATE_RUNNING
291 && new_runstate == RUNSTATE_RUNNABLE )
292 {
293 nstate = STATE_PREEMPT;
294 vm_preempt(now, v);
295 }
296 else if ( v->runstate == RUNSTATE_RUNNING
297 && new_runstate == RUNSTATE_BLOCKED )
298 {
299 nstate = STATE_BLOCK;
300 vm_block(now, v);
301 }
302 else if ( v->runstate == RUNSTATE_RUNNABLE
303 && new_runstate == RUNSTATE_RUNNING )
304 {
305 nstate = STATE_RUN;
306 vm_run(now, v);
307 }
308 else if ( v->runstate == RUNSTATE_BLOCKED
309 && new_runstate == RUNSTATE_RUNNABLE )
310 {
311 nstate = STATE_WAKE;
312 vm_wake(now, v);
313 }
314 else
315 goto unexpected_transition;
317 printf("%d: v%d %s %d -> %s\n",
318 now, v->vid, state_name[ostate], stime, state_name[nstate]);
320 v->runstate = new_runstate;
321 v->state_start_time = now;
323 return;
325 unexpected_transition:
326 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
327 v->vid,
328 v->runstate,
329 new_runstate);
330 exit(1);
331 }
333 /*
334 * Main loop
335 */
336 void simulate(void)
337 {
338 while ( sim.now < opt.time_limit )
339 {
340 /* Take next event off list */
341 struct event evt;
343 evt = sim_next_event();
345 sim.now = evt.time;
347 switch(evt.type)
348 {
349 case EVT_WAKE:
350 {
351 struct vm *v = vm_from_vid(evt.param);
352 ASSERT(v->processor == -1);
353 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
354 sim.sched_ops->wake(sim.now, v->vid);
355 }
356 break;
357 case EVT_BLOCK:
358 {
359 struct vm *v = vm_from_vid(evt.param);
361 ASSERT(v->processor != -1);
362 ASSERT(v->processor <= P.count);
364 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
366 evt.param = v->processor; /* FIXME */
367 }
368 /* FALL-THRU */
369 case EVT_TIMER:
370 {
371 struct vm *prev, *next;
372 int pid = evt.param;
374 ASSERT(pid < P.count);
376 prev = P.pcpus[pid].current;
378 next = sim.sched_ops->schedule(sim.now, pid);
380 if ( prev && prev != next )
381 {
382 prev->processor = -1;
383 if( prev->runstate != RUNSTATE_BLOCKED )
384 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
385 }
388 P.pcpus[pid].current = next;
389 if ( next )
390 {
391 if ( next != prev )
392 {
393 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
394 next->processor = pid;
395 }
396 }
397 else
398 {
399 if ( P.pcpus[pid].idle )
400 {
401 fprintf(stderr, "Strange, pid %d already idle!\n",
402 pid);
403 abort();
404 }
406 /* If the pcpu is going idle, clear all timers from it */
407 sim_remove_event(EVT_TIMER, pid);
409 P.pcpus[pid].idle = 1;
410 P.idle++;
411 }
412 }
413 break;
414 default:
415 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
416 exit(1);
417 break;
418 }
419 }
420 }
422 void init(void)
423 {
424 int vid, i;
425 const struct workload *w;
427 /* Initialize simulation variables */
428 sim.now=0;
429 sim.timer=NULL;
430 INIT_LIST_HEAD(&sim.events);
431 sim.sched_ops = &opt.scheduler->ops;
433 /* Initialize pcpus */
434 P.count = opt.pcpu_count;
435 P.idle = 0;
436 for ( i=0; i<P.count; i++ )
437 {
438 P.pcpus[i].pid = i;
439 P.pcpus[i].idle = 1;
440 P.idle++;
441 P.pcpus[i].current = NULL;
442 }
444 /* Initialize scheduler */
445 sim.sched_ops->sched_init();
447 /* Initialize vms */
448 w=opt.workload;
449 V.count = 0;
450 for ( vid=0; vid<w->vm_count; vid++)
451 {
452 struct vm *v = V.vms+vid;
454 v->vid = vid;
455 v->runstate = RUNSTATE_BLOCKED;
456 v->processor = -1;
457 v->private = NULL;
459 v->state_start_time = 0;
460 v->time_this_phase = 0;
463 v->phase_index = -1;
464 v->e = NULL;
465 v->workload = w->vm_workloads+vid;
467 V.count++;
469 sim.sched_ops->vm_init(vid);
470 }
472 /* Set VM starting conditions */
473 for ( vid=0; vid<V.count; vid++)
474 {
475 struct vm *v = V.vms+vid;
477 switch(v->workload->list[0].type)
478 {
479 case PHASE_RUN:
480 v->phase_index = v->workload->phase_count - 1;
481 v->e = v->workload->list + v->phase_index;
483 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
484 v->state_start_time = sim.now;
485 v->time_this_phase = 0;
486 break;
487 case PHASE_BLOCK:
488 v->phase_index = 0;
489 v->e = v->workload->list;
491 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
492 v->state_start_time = sim.now;
493 v->time_this_phase = 0;
494 break;
495 }
496 }
497 }
499 void report(void)
500 {
501 int i, j;
503 for ( i=0; i<V.count; i++ )
504 {
505 struct vm *v = V.vms + i;
507 printf("VM %d\n", i);
508 for ( j = 0; j < STATE_MAX ; j++ )
509 {
510 char s[128];
511 snprintf(s, 128, " %s", state_name[j]);
512 print_cycle_summary(&v->stats.state[j], sim.now, s);
513 }
514 }
515 }
517 int main(int argc, char * argv[])
518 {
519 warn = stdout;
521 parse_options(argc, argv);
523 /* Setup simulation */
524 init();
526 /* Run simulation */
527 simulate();
528 /* Report statistics */
529 report();
530 }