1 /*
2 * Copyright (C) 2019 - 2020 Intel Corporation
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6 #include <stddef.h>
7 #include <stdint.h>
8 #include <usfstl/assert.h>
9 #include <usfstl/sched.h>
10 #include <usfstl/list.h>
11 #include "internal.h"
12
usfstl_sched_current_time(struct usfstl_scheduler * sched)13 uint64_t usfstl_sched_current_time(struct usfstl_scheduler *sched)
14 {
15 uint64_t current_time;
16
17 if (!sched->external_sync_from || !sched->waiting)
18 return sched->current_time;
19
20 current_time = sched->external_sync_from(sched);
21
22 /* update current time after sync */
23 usfstl_sched_set_time(sched, current_time);
24
25 return current_time;
26 }
27
usfstl_sched_external_request(struct usfstl_scheduler * sched,uint64_t time)28 static bool usfstl_sched_external_request(struct usfstl_scheduler *sched,
29 uint64_t time)
30 {
31 if (!sched->external_request)
32 return false;
33
34 /*
35 * If we received a next_external_sync point, we don't need to ask for
36 * runtime for anything earlier than that point, we're allowed to run.
37 * However, note that this only applies if we're not currently waiting,
38 * if we are in fact waiting for permission, then of course we need to
39 * ask for any earlier time, regardless of the next_external_sync, as
40 * we won't schedule until we get called to run, and that usually won't
41 * happen if we don't ask for it.
42 */
43 if (!sched->waiting && sched->next_external_sync_set &&
44 usfstl_time_cmp(time, <, sched->next_external_sync))
45 return false;
46
47 /* If we asked for this time slot already, don't ask again but wait. */
48 if (sched->prev_external_sync_set && time == sched->prev_external_sync)
49 return true;
50
51 sched->prev_external_sync = time;
52 sched->prev_external_sync_set = 1;
53 sched->external_request(sched, time);
54
55 return true;
56 }
57
usfstl_sched_external_wait(struct usfstl_scheduler * sched)58 static void usfstl_sched_external_wait(struct usfstl_scheduler *sched)
59 {
60 /*
61 * Once we wait for the external scheduler, we have to ask again
62 * even if for some reason we end up asking for the same time.
63 */
64 sched->prev_external_sync_set = 0;
65 sched->waiting = 1;
66 sched->external_wait(sched);
67 sched->waiting = 0;
68 }
69
usfstl_sched_add_job(struct usfstl_scheduler * sched,struct usfstl_job * job)70 void usfstl_sched_add_job(struct usfstl_scheduler *sched, struct usfstl_job *job)
71 {
72 struct usfstl_job *tmp;
73
74 USFSTL_ASSERT_TIME_CMP(job->start, >=, sched->current_time);
75 USFSTL_ASSERT(!usfstl_job_scheduled(job),
76 "cannot add a job that's already scheduled");
77 USFSTL_ASSERT_CMP(job->group, <, 32, "%u");
78
79 if ((1 << job->group) & sched->blocked_groups &&
80 job != sched->allowed_job) {
81 job->start = 0;
82 usfstl_list_append(&sched->pending_jobs, &job->entry);
83 return;
84 }
85
86 usfstl_for_each_list_item(tmp, &sched->joblist, entry) {
87 if (usfstl_time_cmp(tmp->start, >, job->start))
88 break;
89 if (tmp->start == job->start &&
90 tmp->priority < job->priority)
91 break;
92 }
93
94 /* insert after previous entry */
95 if (!tmp)
96 usfstl_list_append(&sched->joblist, &job->entry);
97 else
98 usfstl_list_insert_before(&tmp->entry, &job->entry);
99
100 /*
101 * Request the new job's runtime from the external scheduler
102 * (if configured); if this job doesn't request any earlier
103 * runtime than previously requested, this does nothing. It
104 * may, however, request earlier runtime if this is due to
105 * an interrupt we got from outside while waiting for the
106 * external scheduler.
107 */
108 usfstl_sched_external_request(sched, job->start);
109
110 if (sched->next_time_changed)
111 sched->next_time_changed(sched);
112 }
113
usfstl_job_scheduled(struct usfstl_job * job)114 bool usfstl_job_scheduled(struct usfstl_job *job)
115 {
116 return job->entry.next != NULL;
117 }
118
usfstl_sched_del_job(struct usfstl_job * job)119 void usfstl_sched_del_job(struct usfstl_job *job)
120 {
121 if (!usfstl_job_scheduled(job))
122 return;
123
124 usfstl_list_item_remove(&job->entry);
125 }
126
_usfstl_sched_set_time(struct usfstl_scheduler * sched,uint64_t time)127 void _usfstl_sched_set_time(struct usfstl_scheduler *sched, uint64_t time)
128 {
129 uint64_t delta;
130
131 if (sched->current_time == time)
132 return;
133
134 // check that we at least don't move backwards
135 USFSTL_ASSERT_TIME_CMP(time, >=, sched->current_time);
136
137 delta = time - sched->current_time;
138 sched->current_time = time;
139
140 if (sched->time_advanced)
141 sched->time_advanced(sched, delta);
142 }
143
usfstl_sched_set_time(struct usfstl_scheduler * sched,uint64_t time)144 void usfstl_sched_set_time(struct usfstl_scheduler *sched, uint64_t time)
145 {
146 /*
147 * also check that we're not getting set to something later than what
148 * we requested, that'd be a bug since we want to run something at an
149 * earlier time than what we just got set to; unless we have nothing
150 * to do and thus don't care at all.
151 */
152 USFSTL_ASSERT(usfstl_list_empty(&sched->joblist) ||
153 usfstl_time_cmp(time, <=, sched->prev_external_sync),
154 "scheduler time moves further (to %" PRIu64 ") than requested (%" PRIu64 ")",
155 time, sched->prev_external_sync);
156
157 _usfstl_sched_set_time(sched, time);
158 }
159
usfstl_sched_forward(struct usfstl_scheduler * sched,uint64_t until)160 static void usfstl_sched_forward(struct usfstl_scheduler *sched, uint64_t until)
161 {
162 USFSTL_ASSERT_TIME_CMP(until, >=, sched->current_time);
163
164 if (usfstl_sched_external_request(sched, until)) {
165 usfstl_sched_external_wait(sched);
166 /*
167 * The external_wait() method must call
168 * usfstl_sched_set_time() before returning,
169 * so we don't in this case.
170 */
171 return;
172 }
173
174 _usfstl_sched_set_time(sched, until);
175 }
176
usfstl_sched_start(struct usfstl_scheduler * sched)177 void usfstl_sched_start(struct usfstl_scheduler *sched)
178 {
179 if (usfstl_sched_external_request(sched, sched->current_time))
180 usfstl_sched_external_wait(sched);
181 }
182
usfstl_sched_next(struct usfstl_scheduler * sched)183 struct usfstl_job *usfstl_sched_next(struct usfstl_scheduler *sched)
184 {
185 while (true) {
186 struct usfstl_job *job = usfstl_sched_next_pending(sched, NULL);
187
188 if (!job) {
189 /*
190 * If external scheduler is active, we might get here
191 * with nothing to do, so we just need to wait for an
192 * external input/job which will add a job to our
193 * scheduler.
194 *
195 * Due to the fact that we don't have any API for
196 * cancelling external time requests, we might have
197 * requested time from the external scheduler for a
198 * job that subsequently got removed, ending up here
199 * without a job, or one further in the future which
200 * would cause usfstl_sched_forward() to wait again.
201 *
202 * Additionally, we might only remove the job we just
203 * found during the usfstl_sched_forward() below, if
204 * that causes the main loop to run and we detect an
205 * event that causes a job removal (such as a client
206 * disconnecting from a server), so the job pointer we
207 * have might go stale. Hence, all of this needs to be
208 * checked in the overall loop.
209 */
210 if (sched->external_request) {
211 usfstl_sched_external_wait(sched);
212 continue;
213 }
214 break;
215 }
216
217 /*
218 * Forward, but only if job isn't in the past - this
219 * can happen if some job was inserted while we
220 * were in fact waiting for the external scheduler, i.e.
221 * some sort of external job happened while we thought
222 * there was nothing to do.
223 */
224 if (usfstl_time_cmp(job->start, >, sched->current_time))
225 usfstl_sched_forward(sched, job->start);
226
227 /*
228 * Some sort of external job might have come to us (while
229 * we were stuck waiting for the external scheduler), and
230 * might have inserted an earlier job into the timeline.
231 * If it's not this job's turn yet, reinsert it and check
232 * what's up next in the next loop iteration.
233 *
234 * Also, 'job' might now have been removed, see above.
235 */
236 if (usfstl_sched_next_pending(sched, NULL) != job)
237 continue;
238
239 /*
240 * Otherwise we've actually reached this job, so remove
241 * and call it.
242 */
243 usfstl_sched_del_job(job);
244 job->callback(job);
245 return job;
246 }
247
248 /*
249 * We must not get here, if there's no job whatsoever the
250 * simulation has basically ended in an undefined state, even
251 * the main thread can no longer make progress.
252 */
253 USFSTL_ASSERT(0, "scheduling while there's nothing to do");
254 }
255
usfstl_sched_set_sync_time(struct usfstl_scheduler * sched,uint64_t time)256 void usfstl_sched_set_sync_time(struct usfstl_scheduler *sched, uint64_t time)
257 {
258 USFSTL_ASSERT_TIME_CMP(time, >=, sched->current_time);
259 sched->next_external_sync = time;
260 sched->next_external_sync_set = 1;
261 }
262
usfstl_sched_block_job(struct usfstl_scheduler * sched,struct usfstl_job * job)263 static void usfstl_sched_block_job(struct usfstl_scheduler *sched,
264 struct usfstl_job *job)
265 {
266 usfstl_sched_del_job(job);
267 usfstl_list_append(&sched->pending_jobs, &job->entry);
268 }
269
usfstl_sched_next_pending(struct usfstl_scheduler * sched,struct usfstl_job * job)270 struct usfstl_job *usfstl_sched_next_pending(struct usfstl_scheduler *sched,
271 struct usfstl_job *job)
272 {
273 return job ? usfstl_next_item(&sched->joblist, job, struct usfstl_job, entry) :
274 usfstl_list_first_item(&sched->joblist, struct usfstl_job, entry);
275 }
276
usfstl_sched_remove_blocked_jobs(struct usfstl_scheduler * sched)277 static void usfstl_sched_remove_blocked_jobs(struct usfstl_scheduler *sched)
278 {
279 struct usfstl_job *job = NULL, *next;
280
281 usfstl_for_each_list_item_continue_safe(job, next, &sched->joblist,
282 entry) {
283 if (job == sched->allowed_job)
284 continue;
285 if ((1 << job->group) & sched->blocked_groups)
286 usfstl_sched_block_job(sched, job);
287 }
288 }
289
usfstl_sched_restore_job(struct usfstl_scheduler * sched,struct usfstl_job * job)290 static void usfstl_sched_restore_job(struct usfstl_scheduler *sched,
291 struct usfstl_job *job)
292 {
293 usfstl_sched_del_job(job);
294 if (usfstl_time_cmp(job->start, <, sched->current_time))
295 job->start = sched->current_time;
296 usfstl_sched_add_job(sched, job);
297 }
298
usfstl_sched_restore_blocked_jobs(struct usfstl_scheduler * sched)299 static void usfstl_sched_restore_blocked_jobs(struct usfstl_scheduler *sched)
300 {
301 struct usfstl_job *job = NULL, *next;
302
303 usfstl_for_each_list_item_continue_safe(job, next, &sched->pending_jobs,
304 entry) {
305 if (job == sched->allowed_job ||
306 !((1 << job->group) & sched->blocked_groups))
307 usfstl_sched_restore_job(sched, job);
308 }
309 }
310
usfstl_sched_block_groups(struct usfstl_scheduler * sched,uint32_t groups,struct usfstl_job * job,struct usfstl_sched_block_data * save)311 void usfstl_sched_block_groups(struct usfstl_scheduler *sched, uint32_t groups,
312 struct usfstl_job *job,
313 struct usfstl_sched_block_data *save)
314 {
315 save->groups = sched->blocked_groups;
316 save->job = sched->allowed_job;
317
318 // it makes no sense to allow a job unless its group is blocked
319 USFSTL_ASSERT(!job || (1 << job->group) & groups,
320 "allowed job group %d must be part of blocked groups (0x%x\n)",
321 job->group, groups);
322
323 sched->blocked_groups |= groups;
324 sched->allowed_job = job;
325
326 usfstl_sched_remove_blocked_jobs(sched);
327 }
328
usfstl_sched_restore_groups(struct usfstl_scheduler * sched,struct usfstl_sched_block_data * restore)329 void usfstl_sched_restore_groups(struct usfstl_scheduler *sched,
330 struct usfstl_sched_block_data *restore)
331 {
332 sched->blocked_groups = restore->groups;
333 sched->allowed_job = restore->job;
334
335 usfstl_sched_restore_blocked_jobs(sched);
336 usfstl_sched_remove_blocked_jobs(sched);
337 }
338
usfstl_sched_link_job_callback(struct usfstl_job * job)339 static void usfstl_sched_link_job_callback(struct usfstl_job *job)
340 {
341 struct usfstl_scheduler *sched = job->data;
342
343 sched->link.waiting = false;
344 }
345
usfstl_sched_link_external_sync_from(struct usfstl_scheduler * sched)346 static uint64_t usfstl_sched_link_external_sync_from(struct usfstl_scheduler *sched)
347 {
348 uint64_t parent_time;
349
350 parent_time = usfstl_sched_current_time(sched->link.parent);
351
352 return DIV_ROUND_UP(parent_time - sched->link.offset,
353 sched->link.tick_ratio);
354 }
355
usfstl_sched_link_external_wait(struct usfstl_scheduler * sched)356 static void usfstl_sched_link_external_wait(struct usfstl_scheduler *sched)
357 {
358 sched->link.waiting = true;
359
360 while (sched->link.waiting)
361 usfstl_sched_next(sched->link.parent);
362
363 usfstl_sched_set_time(sched, usfstl_sched_current_time(sched));
364 }
365
usfstl_sched_link_external_request(struct usfstl_scheduler * sched,uint64_t time)366 static void usfstl_sched_link_external_request(struct usfstl_scheduler *sched,
367 uint64_t time)
368 {
369 uint64_t parent_time;
370 struct usfstl_job *job = &sched->link.job;
371
372 parent_time = sched->link.tick_ratio * time + sched->link.offset;
373
374 usfstl_sched_del_job(job);
375 job->start = parent_time;
376 usfstl_sched_add_job(sched->link.parent, job);
377 }
378
usfstl_sched_link(struct usfstl_scheduler * sched,struct usfstl_scheduler * parent,uint32_t tick_ratio)379 void usfstl_sched_link(struct usfstl_scheduler *sched,
380 struct usfstl_scheduler *parent,
381 uint32_t tick_ratio)
382 {
383 struct usfstl_job *job;
384
385 USFSTL_ASSERT(tick_ratio, "a ratio must be set");
386 USFSTL_ASSERT(!sched->link.parent, "must not be linked");
387
388 USFSTL_ASSERT_EQ(sched->external_request, NULL, "%p");
389 sched->external_request = usfstl_sched_link_external_request;
390
391 USFSTL_ASSERT_EQ(sched->external_wait, NULL, "%p");
392 sched->external_wait = usfstl_sched_link_external_wait;
393
394 USFSTL_ASSERT_EQ(sched->external_sync_from, NULL, "%p");
395 sched->external_sync_from = usfstl_sched_link_external_sync_from;
396
397 sched->link.tick_ratio = tick_ratio;
398 sched->link.parent = parent;
399
400 sched->link.job.callback = usfstl_sched_link_job_callback;
401 sched->link.job.data = sched;
402
403 /* current_time = (parent_time - offset) / tick_ratio */
404 sched->link.offset = sched->link.parent->current_time -
405 sched->current_time * sched->link.tick_ratio;
406
407 /* if we have a job already, request to run it */
408 job = usfstl_sched_next_pending(sched, NULL);
409 if (job)
410 usfstl_sched_external_request(sched, job->start);
411 }
412
usfstl_sched_unlink(struct usfstl_scheduler * sched)413 void usfstl_sched_unlink(struct usfstl_scheduler *sched)
414 {
415 USFSTL_ASSERT(sched->link.parent, "must be linked");
416
417 sched->external_sync_from = NULL;
418 sched->external_wait = NULL;
419 sched->external_request = NULL;
420
421 usfstl_sched_del_job(&sched->link.job);
422 memset(&sched->link, 0, sizeof(sched->link));
423 }
424