32206e9ecc7b90ea43151876f7c2c56858d850b2
[barrelfish] / tools / schedsim / simulator.c
1 /**
2  * \file
3  * \brief Scheduler system simulator
4  */
5
6 /*
7  * Copyright (c) 2007, 2008, 2009, 2010, ETH Zurich.
8  * All rights reserved.
9  *
10  * This file is distributed under the terms in the attached LICENSE file.
11  * If you do not find this file, copies can be found by writing to:
12  * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group.
13  */
14
15 #include <stdlib.h>
16 #include <stdbool.h>
17 #include <assert.h>
18 #include <stdio.h>
19 #include <stdarg.h>
20 #include <stdint.h>
21
22 /***** Prerequisite definitions copied from Barrelfish headers *****/
23
24 #define trace_event(x,y,z)
25
26 #define DISP_NAME_LEN   16
27
28 enum task_type {
29     TASK_TYPE_BEST_EFFORT,
30     TASK_TYPE_SOFT_REALTIME,
31     TASK_TYPE_HARD_REALTIME
32 };
33
34 enum objtype {
35     ObjType_CNode,
36     ObjType_EndPoint
37 };
38
39 struct capability {
40     enum objtype        type;
41 };
42
43 struct cte {
44     struct capability cap;
45 };
46
47 typedef uintptr_t dispatcher_handle_t;
48
49 struct dispatcher_shared_generic {
50     char        name[DISP_NAME_LEN];///< Name of domain, for debugging purposes
51 };
52
53 struct dcb {
54     dispatcher_handle_t disp;
55     struct cte          cspace;
56     struct cte          ep;
57     size_t              vspace;
58     struct dcb          *next;          ///< Next DCB in schedule
59     unsigned long       release_time, etime, last_dispatch;
60     unsigned long       wcet, period, deadline;
61     unsigned short      weight;
62     enum task_type      type;
63
64     // Simulator state
65     int                 id;
66     bool                dispatched;
67     unsigned long       blocktime;
68     struct dispatcher_shared_generic dsg;
69 };
70
71 struct kcb {
72     struct kcb *prev, *next;
73     struct dcb *queue_head, *queue_tail;
74     unsigned int u_hrt, u_srt, w_be, n_be;
75 } curr;
76 struct kcb *kcb_current = &curr;
77
78
79 static void panic(const char *msg, ...)
80 {
81     va_list ap;
82
83     fprintf(stderr, "Scheduler panic: ");
84     va_start(ap, msg);
85     vfprintf(stderr, msg, ap);
86     va_end(ap);
87     fprintf(stderr, "\n");
88
89     exit(EXIT_FAILURE);
90 }
91
92 static __attribute__ ((unused)) struct dispatcher_shared_generic *
93 get_dispatcher_shared_generic(dispatcher_handle_t handle)
94 {
95     return (struct dispatcher_shared_generic *)handle;
96 }
97
98 static size_t kernel_now = 0;
99 static int kernel_timeslice = 80;
100 static struct dcb *dcb_current = NULL;
101
102 /***** Including scheduler C file *****/
103
104 #include "../../kernel/schedule_rbed.c"
105
106 /***** Simulator internal definitions *****/
107
108 #define MAXTASKS        10
109
110 static struct dcb *sched, **allptrs;
111
112 static void init_dcb(struct dcb *dcb, int id)
113 {
114     dcb->disp = (uintptr_t)&dcb->dsg;
115     dcb->cspace.cap.type = ObjType_CNode;
116     dcb->ep.cap.type = ObjType_EndPoint;
117     dcb->vspace = 1;
118     dcb->next = NULL;
119     dcb->release_time = 0;
120     dcb->wcet = 0;
121     dcb->period = 0;
122     dcb->weight = 0;
123     dcb->etime = 0;
124
125     dcb->id = id;
126     snprintf(dcb->dsg.name, DISP_NAME_LEN, "%d", id);
127 }
128
129 static inline char typechar(enum task_type type)
130 {
131     switch(type) {
132     case TASK_TYPE_HARD_REALTIME:
133         return 'h';
134
135     case TASK_TYPE_SOFT_REALTIME:
136         return 's';
137
138     case TASK_TYPE_BEST_EFFORT:
139         return 'b';
140
141     default:
142         printf("unknown task type!\n");
143         abort();
144         break;
145     }
146 }
147
148 int main(int argc, char **argv)
149 {
150     int tasks = 0, alltasks = MAXTASKS, runtime, quantum = 1;
151
152     if(argc < 3) {
153         printf("Usage: %s <config.cfg> <runtime> [quantum]\n", argv[0]);
154         exit(EXIT_FAILURE);
155     }
156
157     runtime = atoi(argv[2]);
158     if(argc >= 4) {
159         quantum = atoi(argv[3]);
160     }
161
162     sched = malloc(sizeof(struct dcb) * runtime * alltasks);
163     allptrs = calloc(alltasks, sizeof(struct dcb *));
164
165     FILE *f = fopen(argv[1], "r");
166     assert(f != NULL);
167     bool readline = true;
168
169     for(kernel_now = 0; kernel_now < runtime; kernel_now++) {
170         unsigned long time, wcet, period, weight, id, blocktime, deadline, rd;
171         char b[512], *r;
172
173         for(;;) {
174             if(readline) {
175                 do {
176                     r = fgets(b, 512, f);
177                 } while(r != NULL && (b[0] == '#' || b[0] == '\n'));
178
179                 if(r == NULL) {
180                     break;
181                 }
182             } else {
183                 readline = true;
184             }
185
186             if((rd = sscanf(b, "%lu H %lu %lu %lu %lu", &time, &wcet, &period, &blocktime, &deadline)) >= 4) {
187                 if(time != kernel_now) { readline = false; break; }
188                 // Create new hard real-time task
189                 struct dcb *dcb = malloc(sizeof(struct dcb));
190                 init_dcb(dcb, tasks);
191                 dcb->type = TASK_TYPE_HARD_REALTIME;
192                 dcb->wcet = wcet;
193                 dcb->period = period;
194                 dcb->blocktime = blocktime;
195                 dcb->release_time = kernel_now;
196                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "h %d", tasks);
197                 if(rd == 5) {
198                     dcb->deadline = deadline;
199                 } else {
200                     dcb->deadline = period;
201                 }
202                 make_runnable(dcb);
203                 assert(tasks < MAXTASKS);
204                 allptrs[tasks++] = dcb;
205             } else if(sscanf(b, "%lu S %lu %lu", &time, &wcet, &period) == 3) {
206                 if(time != kernel_now) { readline = false; break; }
207                 // Create new soft real-time task
208                 struct dcb *dcb = malloc(sizeof(struct dcb));
209                 init_dcb(dcb, tasks);
210                 dcb->type = TASK_TYPE_SOFT_REALTIME;
211                 dcb->wcet = wcet;
212                 dcb->period = period;
213                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "s %d", tasks);
214                 make_runnable(dcb);
215                 assert(tasks < MAXTASKS);
216                 allptrs[tasks++] = dcb;
217             } else if(sscanf(b, "%lu B %lu", &time, &weight) == 2) {
218                 if(time != kernel_now) { readline = false; break; }
219                 // Create new best-effort task
220                 struct dcb *dcb = malloc(sizeof(struct dcb));
221                 init_dcb(dcb, tasks);
222                 dcb->type = TASK_TYPE_BEST_EFFORT;
223                 dcb->weight = weight;
224                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "b %d", tasks);
225                 make_runnable(dcb);
226                 assert(tasks < MAXTASKS);
227                 allptrs[tasks++] = dcb;
228             } else if(sscanf(b, "%lu d %lu", &time, &id) == 2) {
229                 if(time != kernel_now) { readline = false; break; }
230                 // Delete task with given ID
231                 assert(id < MAXTASKS);
232                 scheduler_remove(allptrs[id]);
233             } else if(sscanf(b, "%lu r %lu", &time, &id) == 2) {
234                 if(time != kernel_now) { readline = false; break; }
235                 // Re-release task with given ID
236                 assert(id < MAXTASKS);
237                 if(allptrs[id]->type != TASK_TYPE_BEST_EFFORT) {
238                     allptrs[id]->release_time = kernel_now;
239                 }
240                 make_runnable(allptrs[id]);
241             } else if(sscanf(b, "%lu y %lu", &time, &id) == 2) {
242                 if(time != kernel_now) { readline = false; break; }
243                 // Yield task with given ID
244                 assert(id < MAXTASKS);
245                 scheduler_yield(allptrs[id]);
246             } else if(sscanf(b, "%lu c %lu", &time, &id) == 2) {
247                 if(time != kernel_now) { readline = false; break; }
248                 // Context switch to task with given ID
249                 assert(id < MAXTASKS);
250                 dcb_current = allptrs[id];
251                 continue;
252             } else {
253                 fprintf(stderr, "Invalid line: %s\n", b);
254                 abort();
255             }
256
257             dcb_current = schedule();
258         }
259
260         for(int i = 0; i < alltasks; i++) {
261             struct dcb *cd = allptrs[i];
262             if(cd != NULL) {
263                 cd->dispatched = false;
264
265 #if 0
266                 if(cd->type == TASK_TYPE_HARD_REALTIME) {
267                     if(cd->etime >= cd->blocktime) {
268                         scheduler_remove(cd);
269                     }
270                 }
271 #endif
272             }
273         }
274
275         if(kernel_now % quantum == 0) {
276             dcb_current = schedule();
277         }
278
279         if(dcb_current != NULL) {
280             dcb_current->dispatched = true;
281
282             /* printf("%4d: dispatching %2d, release time: %4lu, deadline: %4lu, period: %3lu, WCET: %3lu/%3lu\n", kernel_now, dcb_current->id, dcb_current->release_time, dcb_current->deadline, dcb_current->period, dcb_current->etime, dcb_current->wcet); */
283         }
284         for(int i = 0; i < alltasks; i++) {
285             if(allptrs[i] != NULL) {
286                 sched[kernel_now * alltasks + i] = *allptrs[i];
287             }
288         }
289     }
290
291     fclose(f);
292
293     // Print schedule
294     printf("     ");
295     for(int t = 0; t < runtime; t++) {
296         if(t % 1000 == 0) {
297             printf("%d", (t / 1000) % 10);
298         } else {
299             printf(" ");
300         }
301     }
302     printf("\n");
303     printf("     ");
304     for(int t = 0; t < runtime; t++) {
305         if(t % 100 == 0) {
306             printf("%d", (t / 100) % 10);
307         } else {
308             printf(" ");
309         }
310     }
311     printf("\n");
312     printf("     ");
313     for(int t = 0; t < runtime; t++) {
314         if(t % 10 == 0) {
315             printf("%d", (t / 10) % 10);
316         } else {
317             printf(" ");
318         }
319     }
320     printf("\n");
321
322     printf("     ");
323     for(int t = 0; t < runtime; t++) {
324         printf("%d", t % 10);
325     }
326     printf("\n");
327
328     for(int i = 0; i < tasks; i++) {
329         struct dcb *ct = allptrs[i];
330         printf("%c%2d: ", typechar(ct->type), i);
331         for(int t = 0; t < runtime; t++) {
332             struct dcb *s = &sched[t * alltasks + i];
333
334             if(s->dispatched) {
335                 printf("#");
336             } else {
337                 printf(" ");
338             }
339         }
340         printf("\n");
341         printf("     ");
342         for(int t = 0; t < runtime; t++) {
343             struct dcb *s = &sched[t * alltasks + i];
344
345             if(s->release_time == t) {
346                 printf("r");
347             } else {
348                 printf(" ");
349             }
350         }
351         printf("\n");
352     }
353
354     free(sched);
355     free(allptrs);
356     return 0;
357 }