1 /* 2 * Copyright (C) 2019 - 2020 Intel Corporation 3 * 4 * SPDX-License-Identifier: BSD-3-Clause 5 */ 6 #ifndef _USFSTL_SCHED_H_ 7 #define _USFSTL_SCHED_H_ 8 #include <stdint.h> 9 #include <inttypes.h> 10 #include <stdbool.h> 11 #include "assert.h" 12 #include "list.h" 13 #include "loop.h" 14 15 /* 16 * usfstl's simple scheduler 17 * 18 * usfstl's concept of time is just a free-running counter. You can use 19 * any units you like, but we recommend micro or nanoseconds, even 20 * with nanoseconds you can simulate ~580 years in a uint64_t time. 21 * 22 * The scheduler is just a really basic concept, you enter "jobs" 23 * and then call usfstl_sched_next() to run the next job. Usually, 24 * this job would schedule another job and call usfstl_sched_next() 25 * again, etc. 26 * 27 * The scheduler supports grouping jobs (currently into up to 32 28 * groups) and then blocking certain groups from being executed in 29 * the next iteration. This can be used, for example, to separate 30 * in-SIM and out-of-SIM jobs, or threads from IRQs, etc. Note 31 * that groups and priorities are two entirely separate concepts. 32 * 33 * In many cases, you'll probably be looking for usfstltask.h instead 34 * as that allows you to simulate a cooperative multithreading system. 35 * However, raw jobs may in that case be useful for things like e.g. 36 * interrupts that come into the simulated system (if they're always 37 * run-to-completion i.e. cannot yield to other jobs.) 38 * 39 * Additionally, the scheduler has APIs to integrate with another, 40 * external, scheduler to synchronize multiple components. 41 */ 42 43 /** 44 * struct usfstl_job - usfstl scheduler job 45 * @time: time this job fires 46 * @priority: priority of the job, in case of multiple happening 47 * at the same time; higher value means higher priority 48 * @group: group value, in range 0-31 49 * @name: job name 50 * @data: job data 51 * @callback: called when the job occurs 52 */ 53 struct usfstl_job { 54 uint64_t start; 55 uint32_t priority; 56 uint8_t group; 57 const char *name; 58 59 void *data; 60 void (*callback)(struct usfstl_job *job); 61 62 /* private: */ 63 struct usfstl_list_entry entry; 64 }; 65 66 /** 67 * struct usfstl_scheduler - usfstl scheduler structure 68 * @external_request: If external scheduler integration is required, 69 * set this function pointer appropriately to request the next 70 * run time from the external scheduler. 71 * @external_wait: For external scheduler integration, this must wait 72 * for the previously requested runtime being granted, and you 73 * must call usfstl_sched_set_time() before returning from this 74 * function. 75 * @external_sync_from: For external scheduler integration, return current 76 * time based on external time info. 77 * @time_advanced: Set this to have logging (or similar) when time 78 * advances. Note that the argument is relative to the previous 79 * time, if you need the current absolute time use 80 * usfstl_sched_current_time(), subtract @delta from that to 81 * obtain the time prior to the current advance. 82 * 83 * Use USFSTL_SCHEDULER() to declare (and initialize) a scheduler. 84 */ 85 struct usfstl_scheduler { 86 void (*external_request)(struct usfstl_scheduler *, uint64_t); 87 void (*external_wait)(struct usfstl_scheduler *); 88 uint64_t (*external_sync_from)(struct usfstl_scheduler *sched); 89 void (*time_advanced)(struct usfstl_scheduler *, uint64_t delta); 90 91 /* private: */ 92 void (*next_time_changed)(struct usfstl_scheduler *); 93 uint64_t current_time; 94 uint64_t prev_external_sync, next_external_sync; 95 96 struct usfstl_list joblist; 97 struct usfstl_list pending_jobs; 98 struct usfstl_job *allowed_job; 99 100 uint32_t blocked_groups; 101 uint8_t next_external_sync_set:1, 102 prev_external_sync_set:1, 103 waiting:1; 104 105 struct { 106 struct usfstl_loop_entry entry; 107 uint64_t start; 108 uint32_t nsec_per_tick; 109 uint8_t timer_triggered:1, 110 initialized:1; 111 } wallclock; 112 113 struct { 114 struct usfstl_scheduler *parent; 115 int64_t offset; 116 uint32_t tick_ratio; 117 struct usfstl_job job; 118 bool waiting; 119 } link; 120 121 struct { 122 void *ctrl; 123 } ext; 124 }; 125 126 #define USFSTL_SCHEDULER(name) \ 127 struct usfstl_scheduler name = { \ 128 .joblist = USFSTL_LIST_INIT(name.joblist), \ 129 .pending_jobs = USFSTL_LIST_INIT(name.pending_jobs), \ 130 } 131 132 #define usfstl_time_check(x) \ 133 ({ uint64_t __t; typeof(x) __x; (void)(&__t == &__x); 1; }) 134 135 /** 136 * usfstl_time_cmp - compare time, wrap-around safe 137 * @a: first time 138 * @op: comparison operator (<, >, <=, >=) 139 * @b: second time 140 * 141 * Returns: (a op b), e.g. usfstl_time_cmp(a, >=, b) returns (a >= b) 142 * while accounting for wrap-around 143 */ 144 #define usfstl_time_cmp(a, op, b) \ 145 (usfstl_time_check(a) && usfstl_time_check(b) && \ 146 (0 op (int64_t)((b) - (a)))) 147 148 /** 149 * USFSTL_ASSERT_TIME_CMP - assert that the time comparison holds 150 * @a: first time 151 * @op: comparison operator 152 * @b: second time 153 */ 154 #define USFSTL_ASSERT_TIME_CMP(a, op, b) do { \ 155 uint64_t _a = a; \ 156 uint64_t _b = b; \ 157 if (!usfstl_time_cmp(_a, op, _b)) \ 158 usfstl_abort(__FILE__, __LINE__, \ 159 "usfstl_time_cmp(" #a ", " #op ", " #b ")",\ 160 " " #a " = %" PRIu64 "\n" \ 161 " " #b " = %" PRIu64 "\n", \ 162 _a, _b); \ 163 } while (0) 164 165 /** 166 * usfstl_sched_current_time - return current time 167 * @sched: the scheduler to operate with 168 */ 169 uint64_t usfstl_sched_current_time(struct usfstl_scheduler *sched); 170 171 /** 172 * usfstl_sched_add_job - add job execution 173 * @sched: the scheduler to operate with 174 * @job: job to add 175 * 176 * Add an job to the execution queue, at the time noted 177 * inside the job. 178 */ 179 void usfstl_sched_add_job(struct usfstl_scheduler *sched, 180 struct usfstl_job *job); 181 182 /** 183 * @usfstl_sched_del_job - remove an job 184 * @sched: the scheduler to operate with 185 * @job: job to remove 186 * 187 * Remove an job from the execution queue, if present. 188 */ 189 void usfstl_sched_del_job(struct usfstl_job *job); 190 191 /** 192 * usfstl_sched_start - start the scheduler 193 * @sched: the scheduler to operate with 194 * 195 * Start the scheduler, which initializes the scheduler data 196 * and syncs with the external scheduler if necessary. 197 */ 198 void usfstl_sched_start(struct usfstl_scheduler *sched); 199 200 /** 201 * usfstl_sched_next - call next job 202 * @sched: the scheduler to operate with 203 * 204 * Go into the scheduler, forward time to the next job, 205 * and call its callback. 206 * 207 * Returns the job that was run. 208 */ 209 struct usfstl_job *usfstl_sched_next(struct usfstl_scheduler *sched); 210 211 /** 212 * usfstl_job_scheduled - check if an job is scheduled 213 * @job: the job to check 214 * 215 * Returns: %true if the job is on the schedule list, %false otherwise. 216 */ 217 bool usfstl_job_scheduled(struct usfstl_job *job); 218 219 /** 220 * usfstl_sched_next_pending - get first/next pending job 221 * @sched: the scheduler to operate with 222 * @job: %NULL or previously returned job 223 * 224 * This is used to implement usfstl_sched_for_each_pending() 225 * and usfstl_sched_for_each_pending_safe(). 226 */ 227 struct usfstl_job *usfstl_sched_next_pending(struct usfstl_scheduler *sched, 228 struct usfstl_job *job); 229 230 #define usfstl_sched_for_each_pending(sched, job) \ 231 for (job = usfstl_sched_next_pending(sched, NULL); job; \ 232 job = usfstl_sched_next_pending(sched, job)) 233 234 #define usfstl_sched_for_each_pending_safe(sched, job, tmp) \ 235 for (job = usfstl_sched_next_pending(sched, NULL), \ 236 tmp = usfstl_sched_next_pending(sched, job); \ 237 job; \ 238 job = tmp, tmp = usfstl_sched_next_pending(sched, tmp)) 239 240 struct usfstl_sched_block_data { 241 uint32_t groups; 242 struct usfstl_job *job; 243 }; 244 245 /** 246 * usfstl_sched_block_groups - block groups from executing 247 * @sched: the scheduler to operate with 248 * @groups: groups to block, ORed with the currently blocked groups 249 * @job: single job that's allowed anyway, e.g. if the caller is 250 * part of the blocked group and must be allowed to continue 251 * @save: save data, use with usfstl_sched_restore_groups() 252 */ 253 void usfstl_sched_block_groups(struct usfstl_scheduler *sched, uint32_t groups, 254 struct usfstl_job *job, 255 struct usfstl_sched_block_data *save); 256 257 /** 258 * usfstl_sched_restore_groups - restore blocked groups 259 * @sched: the scheduler to operate with 260 * @restore: data saved during usfstl_sched_block_groups() 261 */ 262 void usfstl_sched_restore_groups(struct usfstl_scheduler *sched, 263 struct usfstl_sched_block_data *restore); 264 265 /** 266 * usfstl_sched_set_time - set time from external source 267 * @sched: the scheduler to operate with 268 * @time: time 269 * 270 * Set the scheduler time from the external source, use this 271 * before returning from the sched_external_wait() method but also when 272 * injecting any other kind of job like an interrupt from an 273 * external source (only applicable when running with external 274 * scheduling and other external interfaces.) 275 */ 276 void usfstl_sched_set_time(struct usfstl_scheduler *sched, uint64_t time); 277 278 /** 279 * usfstl_sched_set_sync_time - set next external sync time 280 * @sched: the scheduler to operate with 281 * @time: time 282 * 283 * When cooperating with an external scheduler, it may be good to 284 * avoid ping-pong all the time, if there's nothing to do. This 285 * function facilitates that. 286 * 287 * Call it before returning from the sched_external_wait() method and 288 * the scheduler will not sync for each internal job again, but 289 * only when the next internal job would be at or later than the 290 * time given as the argument here. 291 * 292 * Note that then you also have to coordinate with the external 293 * scheduler every time there's any interaction with any other 294 * component also driven by the external scheduler. 295 * 296 * To understand this, consider the following timeline, where the 297 * letters indicate scheduler jobs: 298 * - component 1: A C D E F 299 * - component 2: B G 300 * Without calling this function, component 1 will always sync 301 * with the external scheduler in component 2, for every job 302 * it has. However, after the sync for job/time C, component 303 * 2 knows that it will not have any job until G, so if it 304 * tells component 1 (whatever RPC there is calls this function) 305 * then component 1 will sync again only after F. 306 * 307 * However, this also necessitates that whenever the components 308 * interact, this function could be called again. If you imagine 309 * jobs C-F to just be empty ticks that do nothing then this 310 * might not happen. However, if one of them causes interaction 311 * with component 2 (say a network packet in the simulation) the 312 * interaction may cause a new job to be inserted into the 313 * scheduler timeline of component 2. Let's say, for example, 314 * the job D was a transmission from component 1 to 2, and in 315 * component 2 that causes an interrupt and a rescheduling. The 316 * above timeline will thus change to: 317 * - component 1: A C D E F 318 * - component 2: B N G 319 * inserting the job N. Thus, this very interaction needs to 320 * call this function again with the time of N which will be at 321 * or shortly after the time of D, rather than at G. 322 * 323 * This optimises things if jobs C-F don't cause interaction 324 * with other components, and if considered properly in the RPC 325 * protocol will not cause any degradation. 326 * 327 * If not supported, just never call this function and each and 328 * every job will require external synchronisation. 329 */ 330 void usfstl_sched_set_sync_time(struct usfstl_scheduler *sched, uint64_t time); 331 332 /** 333 * g_usfstl_top_scheduler - top level scheduler 334 * 335 * There can be multiple schedulers in an usfstl binary, in particular 336 * when the multi-binary support code is used. In any case, this will 337 * will point to the top-level scheduler to facilitate another level 338 * of integration if needed. 339 */ 340 extern struct usfstl_scheduler *g_usfstl_top_scheduler; 341 342 /** 343 * usfstl_sched_wallclock_init - initialize wall-clock integration 344 * @sched: the scheduler to initialize, it must not have external 345 * integration set up yet 346 * @ns_per_tick: nanoseconds per scheduler tick 347 * 348 * You can use this function to set up a scheduler to run at roughly 349 * wall clock speed (per the @ns_per_tick setting). 350 * 351 * This is compatible with the usfstlloop abstraction, so you can also 352 * add other things to the event loop and they'll be handled while 353 * the scheduler is waiting for time to pass. 354 * 355 * NOTE: This is currently Linux-only. 356 */ 357 void usfstl_sched_wallclock_init(struct usfstl_scheduler *sched, 358 unsigned int ns_per_tick); 359 360 /** 361 * usfstl_sched_wallclock_exit - remove wall-clock integration 362 * @sched: scheduler to remove wall-clock integration from 363 * 364 * This releases any resources used for the wall-clock integration. 365 */ 366 void usfstl_sched_wallclock_exit(struct usfstl_scheduler *sched); 367 368 /** 369 * usfstl_sched_wallclock_wait_and_handle - wait for external events 370 * @sched: scheduler that's integrated with the wallclock 371 * 372 * If no scheduler events are pending, this will wait for external 373 * events using usfstl_wait_and_handle() and synchronize the time it 374 * took for such an event to arrive into the given scheduler. 375 */ 376 void usfstl_sched_wallclock_wait_and_handle(struct usfstl_scheduler *sched); 377 378 /** 379 * usfstl_sched_link - link a scheduler to another one 380 * @sched: the scheduler to link, must not already use the external 381 * request methods, of course. Should also not be running. 382 * @parent: the parent scheduler to link to 383 * @tick_ratio: "tick_ratio" parent ticks == 1 of our ticks; 384 * e.g. 1000 for if @sched should have microseconds, while @parent 385 * uses nanoseconds. 386 * 387 * This links two schedulers together, and requesting any runtime in the 388 * inner scheduler (@sched) depends on the parent scheduler (@parent) 389 * granting it. 390 * 391 * Time in the inner scheduler is adjusted in two ways: 392 * 1) there's a "tick_ratio" as described above 393 * 2) at the time of linking, neither scheduler changes its current 394 * time, instead an offset between the two is maintained, so the 395 * inner scheduler can be at e.g. zero and be linked to a parent 396 * that has already been running for a while. 397 */ 398 void usfstl_sched_link(struct usfstl_scheduler *sched, 399 struct usfstl_scheduler *parent, 400 uint32_t tick_ratio); 401 402 /** 403 * usfstl_sched_unlink - unlink a scheduler again 404 * @sched: the scheduler to unlink, must be linked 405 */ 406 void usfstl_sched_unlink(struct usfstl_scheduler *sched); 407 408 #endif // _USFSTL_SCHED_H_ 409