| 1 |
Scheduler monitors |
| 2 |
================== |
| 3 |
|
| 4 |
- Name: sched |
| 5 |
- Type: container for multiple monitors |
| 6 |
- Author: Gabriele Monaco <[email protected]>, Daniel Bristot de Oliveira <[email protected]> |
| 7 |
|
| 8 |
Description |
| 9 |
----------- |
| 10 |
|
| 11 |
Monitors describing complex systems, such as the scheduler, can easily grow to |
| 12 |
the point where they are just hard to understand because of the many possible |
| 13 |
state transitions. |
| 14 |
Often it is possible to break such descriptions into smaller monitors, |
| 15 |
sharing some or all events. Enabling those smaller monitors concurrently is, |
| 16 |
in fact, testing the system as if we had one single larger monitor. |
| 17 |
Splitting models into multiple specification is not only easier to |
| 18 |
understand, but gives some more clues when we see errors. |
| 19 |
|
| 20 |
The sched monitor is a set of specifications to describe the scheduler behaviour. |
| 21 |
It includes several per-cpu and per-task monitors that work independently to verify |
| 22 |
different specifications the scheduler should follow. |
| 23 |
|
| 24 |
To make this system as straightforward as possible, sched specifications are *nested* |
| 25 |
monitors, whereas sched itself is a *container*. |
| 26 |
From the interface perspective, sched includes other monitors as sub-directories, |
| 27 |
enabling/disabling or setting reactors to sched, propagates the change to all monitors, |
| 28 |
however single monitors can be used independently as well. |
| 29 |
|
| 30 |
It is important that future modules are built after their container (sched, in |
| 31 |
this case), otherwise the linker would not respect the order and the nesting |
| 32 |
wouldn't work as expected. |
| 33 |
To do so, simply add them after sched in the Makefile. |
| 34 |
|
| 35 |
Specifications |
| 36 |
-------------- |
| 37 |
|
| 38 |
The specifications included in sched are currently a work in progress, adapting the ones |
| 39 |
defined in by Daniel Bristot in [1]. |
| 40 |
|
| 41 |
Currently we included the following: |
| 42 |
|
| 43 |
Monitor sco |
| 44 |
~~~~~~~~~~~ |
| 45 |
|
| 46 |
The scheduling context operations (sco) monitor ensures changes in a task state |
| 47 |
happen only in thread context:: |
| 48 |
|
| 49 |
|
| 50 |
| |
| 51 |
| |
| 52 |
v |
| 53 |
sched_set_state +------------------+ |
| 54 |
+------------------ | | |
| 55 |
| | thread_context | |
| 56 |
+-----------------> | | <+ |
| 57 |
+------------------+ | |
| 58 |
| | |
| 59 |
| schedule_entry | schedule_exit |
| 60 |
v | |
| 61 |
| |
| 62 |
scheduling_context -+ |
| 63 |
|
| 64 |
Monitor snroc |
| 65 |
~~~~~~~~~~~~~ |
| 66 |
|
| 67 |
The set non runnable on its own context (snroc) monitor ensures changes in a |
| 68 |
task state happens only in the respective task's context. This is a per-task |
| 69 |
monitor:: |
| 70 |
|
| 71 |
| |
| 72 |
| |
| 73 |
v |
| 74 |
+------------------+ |
| 75 |
| other_context | <+ |
| 76 |
+------------------+ | |
| 77 |
| | |
| 78 |
| sched_switch_in | sched_switch_out |
| 79 |
v | |
| 80 |
sched_set_state | |
| 81 |
+------------------ | |
| 82 |
| own_context | |
| 83 |
+-----------------> -+ |
| 84 |
|
| 85 |
Monitor scpd |
| 86 |
~~~~~~~~~~~~ |
| 87 |
|
| 88 |
The schedule called with preemption disabled (scpd) monitor ensures schedule is |
| 89 |
called with preemption disabled:: |
| 90 |
|
| 91 |
| |
| 92 |
| |
| 93 |
v |
| 94 |
+------------------+ |
| 95 |
| cant_sched | <+ |
| 96 |
+------------------+ | |
| 97 |
| | |
| 98 |
| preempt_disable | preempt_enable |
| 99 |
v | |
| 100 |
schedule_entry | |
| 101 |
schedule_exit | |
| 102 |
+----------------- can_sched | |
| 103 |
| | |
| 104 |
+----------------> -+ |
| 105 |
|
| 106 |
Monitor snep |
| 107 |
~~~~~~~~~~~~ |
| 108 |
|
| 109 |
The schedule does not enable preempt (snep) monitor ensures a schedule call |
| 110 |
does not enable preemption:: |
| 111 |
|
| 112 |
| |
| 113 |
| |
| 114 |
v |
| 115 |
preempt_disable +------------------------+ |
| 116 |
preempt_enable | | |
| 117 |
+------------------ | non_scheduling_context | |
| 118 |
| | | |
| 119 |
+-----------------> | | <+ |
| 120 |
+------------------------+ | |
| 121 |
| | |
| 122 |
| schedule_entry | schedule_exit |
| 123 |
v | |
| 124 |
| |
| 125 |
scheduling_contex -+ |
| 126 |
|
| 127 |
Monitor sts |
| 128 |
~~~~~~~~~~~ |
| 129 |
|
| 130 |
The schedule implies task switch (sts) monitor ensures a task switch happens |
| 131 |
only in scheduling context and up to once, as well as scheduling occurs with |
| 132 |
interrupts enabled but no task switch can happen before interrupts are |
| 133 |
disabled. When the next task picked for execution is the same as the previously |
| 134 |
running one, no real task switch occurs but interrupts are disabled nonetheless:: |
| 135 |
|
| 136 |
irq_entry | |
| 137 |
+----+ | |
| 138 |
v | v |
| 139 |
+------------+ irq_enable #===================# irq_disable |
| 140 |
| | ------------> H H irq_entry |
| 141 |
| cant_sched | <------------ H H irq_enable |
| 142 |
| | irq_disable H can_sched H --------------+ |
| 143 |
+------------+ H H | |
| 144 |
H H | |
| 145 |
+---------------> H H <-------------+ |
| 146 |
| #===================# |
| 147 |
| | |
| 148 |
schedule_exit | schedule_entry |
| 149 |
| v |
| 150 |
| +-------------------+ irq_enable |
| 151 |
| | scheduling | <---------------+ |
| 152 |
| +-------------------+ | |
| 153 |
| | | |
| 154 |
| | irq_disable +--------+ irq_entry |
| 155 |
| v | | --------+ |
| 156 |
| +-------------------+ irq_entry | in_irq | | |
| 157 |
| | | -----------> | | <-------+ |
| 158 |
| | disable_to_switch | +--------+ |
| 159 |
| | | --+ |
| 160 |
| +-------------------+ | |
| 161 |
| | | |
| 162 |
| | sched_switch | |
| 163 |
| v | |
| 164 |
| +-------------------+ | |
| 165 |
| | switching | | irq_enable |
| 166 |
| +-------------------+ | |
| 167 |
| | | |
| 168 |
| | irq_enable | |
| 169 |
| v | |
| 170 |
| +-------------------+ | |
| 171 |
+-- | enable_to_exit | <-+ |
| 172 |
+-------------------+ |
| 173 |
^ | irq_disable |
| 174 |
| | irq_entry |
| 175 |
+---------------+ irq_enable |
| 176 |
|
| 177 |
Monitor nrp |
| 178 |
----------- |
| 179 |
|
| 180 |
The need resched preempts (nrp) monitor ensures preemption requires |
| 181 |
``need_resched``. Only kernel preemption is considered, since preemption |
| 182 |
while returning to userspace, for this monitor, is indistinguishable from |
| 183 |
``sched_switch_yield`` (described in the sssw monitor). |
| 184 |
A kernel preemption is whenever ``__schedule`` is called with the preemption |
| 185 |
flag set to true (e.g. from preempt_enable or exiting from interrupts). This |
| 186 |
type of preemption occurs after the need for ``rescheduling`` has been set. |
| 187 |
This is not valid for the *lazy* variant of the flag, which causes only |
| 188 |
userspace preemption. |
| 189 |
A ``schedule_entry_preempt`` may involve a task switch or not, in the latter |
| 190 |
case, a task goes through the scheduler from a preemption context but it is |
| 191 |
picked as the next task to run. Since the scheduler runs, this clears the need |
| 192 |
to reschedule. The ``any_thread_running`` state does not imply the monitored |
| 193 |
task is not running as this monitor does not track the outcome of scheduling. |
| 194 |
|
| 195 |
In theory, a preemption can only occur after the ``need_resched`` flag is set. In |
| 196 |
practice, however, it is possible to see a preemption where the flag is not |
| 197 |
set. This can happen in one specific condition:: |
| 198 |
|
| 199 |
need_resched |
| 200 |
preempt_schedule() |
| 201 |
preempt_schedule_irq() |
| 202 |
__schedule() |
| 203 |
!need_resched |
| 204 |
__schedule() |
| 205 |
|
| 206 |
In the situation above, standard preemption starts (e.g. from preempt_enable |
| 207 |
when the flag is set), an interrupt occurs before scheduling and, on its exit |
| 208 |
path, it schedules, which clears the ``need_resched`` flag. |
| 209 |
When the preempted task runs again, the standard preemption started earlier |
| 210 |
resumes, although the flag is no longer set. The monitor considers this a |
| 211 |
``nested_preemption``, this allows another preemption without re-setting the |
| 212 |
flag. This condition relaxes the monitor constraints and may catch false |
| 213 |
negatives (i.e. no real ``nested_preemptions``) but makes the monitor more |
| 214 |
robust and able to validate other scenarios. |
| 215 |
For simplicity, the monitor starts in ``preempt_irq``, although no interrupt |
| 216 |
occurred, as the situation above is hard to pinpoint:: |
| 217 |
|
| 218 |
schedule_entry |
| 219 |
irq_entry #===========================================# |
| 220 |
+-------------------------- H H |
| 221 |
| H H |
| 222 |
+-------------------------> H any_thread_running H |
| 223 |
H H |
| 224 |
+-------------------------> H H |
| 225 |
| #===========================================# |
| 226 |
| schedule_entry | ^ |
| 227 |
| schedule_entry_preempt | sched_need_resched | schedule_entry |
| 228 |
| | schedule_entry_preempt |
| 229 |
| v | |
| 230 |
| +----------------------+ | |
| 231 |
| +--- | | | |
| 232 |
| sched_need_resched | | rescheduling | -+ |
| 233 |
| +--> | | |
| 234 |
| +----------------------+ |
| 235 |
| | irq_entry |
| 236 |
| v |
| 237 |
| +----------------------+ |
| 238 |
| | | ---+ |
| 239 |
| ---> | | | sched_need_resched |
| 240 |
| | preempt_irq | | irq_entry |
| 241 |
| | | <--+ |
| 242 |
| | | <--+ |
| 243 |
| +----------------------+ | |
| 244 |
| | schedule_entry | sched_need_resched |
| 245 |
| | schedule_entry_preempt | |
| 246 |
| v | |
| 247 |
| +-----------------------+ | |
| 248 |
+-------------------------- | nested_preempt | --+ |
| 249 |
+-----------------------+ |
| 250 |
^ irq_entry | |
| 251 |
+-------------------+ |
| 252 |
|
| 253 |
Due to how the ``need_resched`` flag on the preemption count works on arm64, |
| 254 |
this monitor is unstable on that architecture, as it often records preemption |
| 255 |
when the flag is not set, even in presence of the workaround above. |
| 256 |
For the time being, the monitor is disabled by default on arm64. |
| 257 |
|
| 258 |
Monitor sssw |
| 259 |
------------ |
| 260 |
|
| 261 |
The set state sleep and wakeup (sssw) monitor ensures ``set_state`` to |
| 262 |
sleepable leads to sleeping and sleeping tasks require wakeup. It includes the |
| 263 |
following types of switch: |
| 264 |
|
| 265 |
* ``switch_suspend``: |
| 266 |
a task puts itself to sleep, this can happen only after explicitly setting |
| 267 |
the task to ``sleepable``. After a task is suspended, it needs to be woken up |
| 268 |
(``waking`` state) before being switched in again. |
| 269 |
Setting the task's state to ``sleepable`` can be reverted before switching if it |
| 270 |
is woken up or set to ``runnable``. |
| 271 |
* ``switch_blocking``: |
| 272 |
a special case of a ``switch_suspend`` where the task is waiting on a |
| 273 |
sleeping RT lock (``PREEMPT_RT`` only), it is common to see wakeup and set |
| 274 |
state events racing with each other and this leads the model to perceive this |
| 275 |
type of switch when the task is not set to sleepable. This is a limitation of |
| 276 |
the model in SMP system and workarounds may slow down the system. |
| 277 |
* ``switch_preempt``: |
| 278 |
a task switch as a result of kernel preemption (``schedule_entry_preempt`` in |
| 279 |
the nrp model). |
| 280 |
* ``switch_yield``: |
| 281 |
a task explicitly calls the scheduler or is preempted while returning to |
| 282 |
userspace. It can happen after a ``yield`` system call, from the idle task or |
| 283 |
if the ``need_resched`` flag is set. By definition, a task cannot yield while |
| 284 |
``sleepable`` as that would be a suspension. A special case of a yield occurs |
| 285 |
when a task in ``TASK_INTERRUPTIBLE`` calls the scheduler while a signal is |
| 286 |
pending. The task doesn't go through the usual blocking/waking and is set |
| 287 |
back to runnable, the resulting switch (if there) looks like a yield to the |
| 288 |
``signal_wakeup`` state and is followed by the signal delivery. From this |
| 289 |
state, the monitor expects a signal even if it sees a wakeup event, although |
| 290 |
not necessary, to rule out false negatives. |
| 291 |
|
| 292 |
This monitor doesn't include a running state, ``sleepable`` and ``runnable`` |
| 293 |
are only referring to the task's desired state, which could be scheduled out |
| 294 |
(e.g. due to preemption). However, it does include the event |
| 295 |
``sched_switch_in`` to represent when a task is allowed to become running. This |
| 296 |
can be triggered also by preemption, but cannot occur after the task got to |
| 297 |
``sleeping`` before a ``wakeup`` occurs:: |
| 298 |
|
| 299 |
+--------------------------------------------------------------------------+ |
| 300 |
| | |
| 301 |
| | |
| 302 |
| switch_suspend | | |
| 303 |
| switch_blocking | | |
| 304 |
v v | |
| 305 |
+----------+ #==========================# set_state_runnable | |
| 306 |
| | H H wakeup | |
| 307 |
| | H H switch_in | |
| 308 |
| | H H switch_yield | |
| 309 |
| sleeping | H H switch_preempt | |
| 310 |
| | H H signal_deliver | |
| 311 |
| | switch_ H H ------+ | |
| 312 |
| | _blocking H runnable H | | |
| 313 |
| | <----------- H H <-----+ | |
| 314 |
+----------+ H H | |
| 315 |
| wakeup H H | |
| 316 |
+---------------------> H H | |
| 317 |
H H | |
| 318 |
+---------> H H | |
| 319 |
| #==========================# | |
| 320 |
| | ^ | |
| 321 |
| | | set_state_runnable | |
| 322 |
| | | wakeup | |
| 323 |
| set_state_sleepable | +------------------------+ |
| 324 |
| v | | |
| 325 |
| +--------------------------+ set_state_sleepable |
| 326 |
| | | switch_in |
| 327 |
| | | switch_preempt |
| 328 |
signal_deliver | sleepable | signal_deliver |
| 329 |
| | | ------+ |
| 330 |
| | | | |
| 331 |
| | | <-----+ |
| 332 |
| +--------------------------+ |
| 333 |
| | ^ |
| 334 |
| switch_yield | set_state_sleepable |
| 335 |
| v | |
| 336 |
| +---------------+ | |
| 337 |
+---------- | signal_wakeup | -+ |
| 338 |
+---------------+ |
| 339 |
^ | switch_in |
| 340 |
| | switch_preempt |
| 341 |
| | switch_yield |
| 342 |
+-----------+ wakeup |
| 343 |
|
| 344 |
Monitor opid |
| 345 |
------------ |
| 346 |
|
| 347 |
The operations with preemption and irq disabled (opid) monitor ensures |
| 348 |
operations like ``wakeup`` and ``need_resched`` occur with interrupts and |
| 349 |
preemption disabled or during interrupt context, in such case preemption may |
| 350 |
not be disabled explicitly. |
| 351 |
``need_resched`` can be set by some RCU internals functions, in which case it |
| 352 |
doesn't match a task wakeup and might occur with only interrupts disabled:: |
| 353 |
|
| 354 |
| sched_need_resched |
| 355 |
| sched_waking |
| 356 |
| irq_entry |
| 357 |
| +--------------------+ |
| 358 |
v v | |
| 359 |
+------------------------------------------------------+ |
| 360 |
+----------- | disabled | <+ |
| 361 |
| +------------------------------------------------------+ | |
| 362 |
| | ^ | |
| 363 |
| | preempt_disable sched_need_resched | |
| 364 |
| preempt_enable | +--------------------+ | |
| 365 |
| v | v | | |
| 366 |
| +------------------------------------------------------+ | |
| 367 |
| | irq_disabled | | |
| 368 |
| +------------------------------------------------------+ | |
| 369 |
| | | ^ | |
| 370 |
| irq_entry irq_entry | | | |
| 371 |
| sched_need_resched v | irq_disable | |
| 372 |
| sched_waking +--------------+ | | | |
| 373 |
| +----- | | irq_enable | | |
| 374 |
| | | in_irq | | | | |
| 375 |
| +----> | | | | | |
| 376 |
| +--------------+ | | irq_disable |
| 377 |
| | | | | |
| 378 |
| irq_enable | irq_enable | | | |
| 379 |
| v v | | |
| 380 |
| #======================================================# | |
| 381 |
| H enabled H | |
| 382 |
| #======================================================# | |
| 383 |
| | ^ ^ preempt_enable | | |
| 384 |
| preempt_disable preempt_enable +--------------------+ | |
| 385 |
| v | | |
| 386 |
| +------------------+ | | |
| 387 |
+----------> | preempt_disabled | -+ | |
| 388 |
+------------------+ | |
| 389 |
| | |
| 390 |
+-------------------------------------------------------+ |
| 391 |
|
| 392 |
This monitor is designed to work on ``PREEMPT_RT`` kernels, the special case of |
| 393 |
events occurring in interrupt context is a shortcut to identify valid scenarios |
| 394 |
where the preemption tracepoints might not be visible, during interrupts |
| 395 |
preemption is always disabled. On non- ``PREEMPT_RT`` kernels, the interrupts |
| 396 |
might invoke a softirq to set ``need_resched`` and wake up a task. This is |
| 397 |
another special case that is currently not supported by the monitor. |
| 398 |
|
| 399 |
References |
| 400 |
---------- |
| 401 |
|
| 402 |
[1] - https://bristot.me/linux-task-model |