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