db8e3a941b1ac0eaa115414320a68d66ae258d71
[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_L1CNode,
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 = { 0, 0, 0, 0, 0, 0, 0, 0 };
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 typedef uint64_t systime_t;
99 #define systime_now() kernel_now
100 static size_t kernel_now = 0;
101 static int kernel_timeslice = 80;
102 static struct dcb *dcb_current = NULL;
103
104 /***** Including scheduler C file *****/
105
106 #include "../../kernel/schedule_rbed.c"
107
108 /***** Simulator internal definitions *****/
109
110 #define MAXTASKS        10
111
112 static struct dcb *sched, **allptrs;
113
114 static void init_dcb(struct dcb *dcb, int id)
115 {
116     dcb->disp = (uintptr_t)&dcb->dsg;
117     dcb->cspace.cap.type = ObjType_L1CNode;
118     dcb->ep.cap.type = ObjType_EndPoint;
119     dcb->vspace = 1;
120     dcb->next = NULL;
121     dcb->release_time = 0;
122     dcb->wcet = 0;
123     dcb->period = 0;
124     dcb->weight = 0;
125     dcb->etime = 0;
126
127     dcb->id = id;
128     snprintf(dcb->dsg.name, DISP_NAME_LEN, "%d", id);
129 }
130
131 static inline char typechar(enum task_type type)
132 {
133     switch(type) {
134     case TASK_TYPE_HARD_REALTIME:
135         return 'h';
136
137     case TASK_TYPE_SOFT_REALTIME:
138         return 's';
139
140     case TASK_TYPE_BEST_EFFORT:
141         return 'b';
142
143     default:
144         printf("unknown task type!\n");
145         abort();
146         break;
147     }
148 }
149
150 int main(int argc, char **argv)
151 {
152     int tasks = 0, alltasks = MAXTASKS, runtime, quantum = 1;
153
154     if(argc < 3) {
155         printf("Usage: %s <config.cfg> <runtime> [quantum]\n", argv[0]);
156         exit(EXIT_FAILURE);
157     }
158
159     runtime = atoi(argv[2]);
160     if(argc >= 4) {
161         quantum = atoi(argv[3]);
162     }
163
164     sched = malloc(sizeof(struct dcb) * runtime * alltasks);
165     allptrs = calloc(alltasks, sizeof(struct dcb *));
166
167     FILE *f = fopen(argv[1], "r");
168     assert(f != NULL);
169     bool readline = true;
170
171     for(kernel_now = 0; kernel_now < runtime; kernel_now++) {
172         unsigned long time, wcet, period, weight, id, blocktime, deadline, rd;
173         char b[512], *r;
174
175         for(;;) {
176             if(readline) {
177                 do {
178                     r = fgets(b, 512, f);
179                 } while(r != NULL && (b[0] == '#' || b[0] == '\n'));
180
181                 if(r == NULL) {
182                     break;
183                 }
184             } else {
185                 readline = true;
186             }
187
188             if((rd = sscanf(b, "%lu H %lu %lu %lu %lu", &time, &wcet, &period, &blocktime, &deadline)) >= 4) {
189                 if(time != kernel_now) { readline = false; break; }
190                 // Create new hard real-time task
191                 struct dcb *dcb = malloc(sizeof(struct dcb));
192                 init_dcb(dcb, tasks);
193                 dcb->type = TASK_TYPE_HARD_REALTIME;
194                 dcb->wcet = wcet;
195                 dcb->period = period;
196                 dcb->blocktime = blocktime;
197                 dcb->release_time = kernel_now;
198                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "h %d", tasks);
199                 if(rd == 5) {
200                     dcb->deadline = deadline;
201                 } else {
202                     dcb->deadline = period;
203                 }
204                 make_runnable(dcb);
205                 assert(tasks < MAXTASKS);
206                 allptrs[tasks++] = dcb;
207             } else if(sscanf(b, "%lu S %lu %lu", &time, &wcet, &period) == 3) {
208                 if(time != kernel_now) { readline = false; break; }
209                 // Create new soft real-time task
210                 struct dcb *dcb = malloc(sizeof(struct dcb));
211                 init_dcb(dcb, tasks);
212                 dcb->type = TASK_TYPE_SOFT_REALTIME;
213                 dcb->wcet = wcet;
214                 dcb->period = period;
215                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "s %d", tasks);
216                 make_runnable(dcb);
217                 assert(tasks < MAXTASKS);
218                 allptrs[tasks++] = dcb;
219             } else if(sscanf(b, "%lu B %lu", &time, &weight) == 2) {
220                 if(time != kernel_now) { readline = false; break; }
221                 // Create new best-effort task
222                 struct dcb *dcb = malloc(sizeof(struct dcb));
223                 init_dcb(dcb, tasks);
224                 dcb->type = TASK_TYPE_BEST_EFFORT;
225                 dcb->weight = weight;
226                 snprintf(dcb->dsg.name, DISP_NAME_LEN, "b %d", tasks);
227                 make_runnable(dcb);
228                 assert(tasks < MAXTASKS);
229                 allptrs[tasks++] = dcb;
230             } else if(sscanf(b, "%lu d %lu", &time, &id) == 2) {
231                 if(time != kernel_now) { readline = false; break; }
232                 // Delete task with given ID
233                 assert(id < MAXTASKS);
234                 scheduler_remove(allptrs[id]);
235             } else if(sscanf(b, "%lu r %lu", &time, &id) == 2) {
236                 if(time != kernel_now) { readline = false; break; }
237                 // Re-release task with given ID
238                 assert(id < MAXTASKS);
239                 if(allptrs[id]->type != TASK_TYPE_BEST_EFFORT) {
240                     allptrs[id]->release_time = kernel_now;
241                 }
242                 make_runnable(allptrs[id]);
243             } else if(sscanf(b, "%lu y %lu", &time, &id) == 2) {
244                 if(time != kernel_now) { readline = false; break; }
245                 // Yield task with given ID
246                 assert(id < MAXTASKS);
247                 scheduler_yield(allptrs[id]);
248             } else if(sscanf(b, "%lu c %lu", &time, &id) == 2) {
249                 if(time != kernel_now) { readline = false; break; }
250                 // Context switch to task with given ID
251                 assert(id < MAXTASKS);
252                 dcb_current = allptrs[id];
253                 continue;
254             } else {
255                 fprintf(stderr, "Invalid line: %s\n", b);
256                 abort();
257             }
258
259             dcb_current = schedule();
260         }
261
262         for(int i = 0; i < alltasks; i++) {
263             struct dcb *cd = allptrs[i];
264             if(cd != NULL) {
265                 cd->dispatched = false;
266
267 #if 0
268                 if(cd->type == TASK_TYPE_HARD_REALTIME) {
269                     if(cd->etime >= cd->blocktime) {
270                         scheduler_remove(cd);
271                     }
272                 }
273 #endif
274             }
275         }
276
277         if(kernel_now % quantum == 0) {
278             dcb_current = schedule();
279         }
280
281         if(dcb_current != NULL) {
282             dcb_current->dispatched = true;
283
284             /* 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); */
285         }
286         for(int i = 0; i < alltasks; i++) {
287             if(allptrs[i] != NULL) {
288                 sched[kernel_now * alltasks + i] = *allptrs[i];
289             }
290         }
291     }
292
293     fclose(f);
294
295     // Print schedule
296     printf("     ");
297     for(int t = 0; t < runtime; t++) {
298         if(t % 1000 == 0) {
299             printf("%d", (t / 1000) % 10);
300         } else {
301             printf(" ");
302         }
303     }
304     printf("\n");
305     printf("     ");
306     for(int t = 0; t < runtime; t++) {
307         if(t % 100 == 0) {
308             printf("%d", (t / 100) % 10);
309         } else {
310             printf(" ");
311         }
312     }
313     printf("\n");
314     printf("     ");
315     for(int t = 0; t < runtime; t++) {
316         if(t % 10 == 0) {
317             printf("%d", (t / 10) % 10);
318         } else {
319             printf(" ");
320         }
321     }
322     printf("\n");
323
324     printf("     ");
325     for(int t = 0; t < runtime; t++) {
326         printf("%d", t % 10);
327     }
328     printf("\n");
329
330     for(int i = 0; i < tasks; i++) {
331         struct dcb *ct = allptrs[i];
332         printf("%c%2d: ", typechar(ct->type), i);
333         for(int t = 0; t < runtime; t++) {
334             struct dcb *s = &sched[t * alltasks + i];
335
336             if(s->dispatched) {
337                 printf("#");
338             } else {
339                 printf(" ");
340             }
341         }
342         printf("\n");
343         printf("     ");
344         for(int t = 0; t < runtime; t++) {
345             struct dcb *s = &sched[t * alltasks + i];
346
347             if(s->release_time == t) {
348                 printf("r");
349             } else {
350                 printf(" ");
351             }
352         }
353         printf("\n");
354     }
355
356     free(sched);
357     free(allptrs);
358     return 0;
359 }