E.7.2.1 Basic Model
Keywords: perfbook_html

###
E.7.2.1 Basic Model

This section translates the process-level dynticks entry/exit code and the grace-period processing into Promela [Hol03]. We start with rcu_exit_nohz() and rcu_enter_nohz() from the 2.6.25-rc4 kernel, placing these in a single Promela process that models exiting and entering dynticks-idle mode in a loop as follows:

      1 proctype dyntick_nohz()
      2 {
      3   byte tmp;
      4   byte i = 0;
      5
      6   do
      7   :: i >= MAX_DYNTICK_LOOP_NOHZ -> break;
      8   :: i < MAX_DYNTICK_LOOP_NOHZ ->
      9     tmp = dynticks_progress_counter;
     10     atomic {
     11       dynticks_progress_counter = tmp + 1;
     12       assert((dynticks_progress_counter & 1) == 1);
     13     }
     14     tmp = dynticks_progress_counter;
     15     atomic {
     16       dynticks_progress_counter = tmp + 1;
     17       assert((dynticks_progress_counter & 1) == 0);
     18     }
     19     i++;
     20   od;
     21 }

Lines 6 and 20 define a loop. Line 7 exits the loop once the loop counter i has exceeded the limit MAX_DYNTICK_LOOP_NOHZ. Line 8 tells the loop construct to execute lines 9-19 for each pass through the loop. Because the conditionals on lines 7 and 8 are exclusive of each other, the normal Promela random selection of true conditions is disabled. Lines 9 and 11 model rcu_exit_nohz()'s non-atomic increment of dynticks_progress_counter, while line 12 models the WARN_ON(). The atomic construct simply reduces the Promela state space, given that the WARN_ON() is not strictly speaking part of the algorithm. Lines 14-18 similarly models the increment and WARN_ON() for rcu_enter_nohz(). Finally, line 19 increments the loop counter.

Each pass through the loop therefore models a CPU exiting dynticks-idle mode (for example, starting to execute a task), then re-entering dynticks-idle mode (for example, that same task blocking).

Quick Quiz E.10: Why isn't the memory barrier in rcu_exit_nohz() and rcu_enter_nohz() modeled in Promela? End Quick Quiz

Quick Quiz E.11: Isn't it a bit strange to model rcu_exit_nohz() followed by rcu_enter_nohz()? Wouldn't it be more natural to instead model entry before exit? End Quick Quiz

The next step is to model the interface to RCU's grace-period processing. For this, we need to model dyntick_save_progress_counter(), rcu_try_flip_waitack_needed(), rcu_try_flip_waitmb_needed(), as well as portions of rcu_try_flip_waitack() and rcu_try_flip_waitmb(), all from the 2.6.25-rc4 kernel. The following grace_period() Promela process models these functions as they would be invoked during a single pass through preemptible RCU's grace-period processing.

      1 proctype grace_period()
      2 {
      3   byte curr;
      4   byte snap;
      5
      6   atomic {
      7     printf("MDLN = %d\n", MAX_DYNTICK_LOOP_NOHZ);
      8     snap = dynticks_progress_counter;
      9   }
     10   do
     11   :: 1 ->
     12     atomic {
     13       curr = dynticks_progress_counter;
     14       if
     15       :: (curr == snap) && ((curr & 1) == 0) ->
     16         break;
     17       :: (curr - snap) > 2 || (snap & 1) == 0 ->
     18         break;
     19       :: 1 -> skip;
     20       fi;
     21     }
     22   od;
     23   snap = dynticks_progress_counter;
     24   do
     25   :: 1 ->
     26     atomic {
     27       curr = dynticks_progress_counter;
     28       if
     29       :: (curr == snap) && ((curr & 1) == 0) ->
     30         break;
     31       :: (curr != snap) ->
     32         break;
     33       :: 1 -> skip;
     34       fi;
     35     }
     36   od;
     37 }

Lines 6-9 print out the loop limit (but only into the .trail file in case of error) and models a line of code from rcu_try_flip_idle() and its call to dyntick_save_progress_counter(), which takes a snapshot of the current CPU's dynticks_progress_counter variable. These two lines are executed atomically to reduce state space.

Lines 10-22 model the relevant code in rcu_try_flip_waitack() and its call to rcu_try_flip_waitack_needed(). This loop is modeling the grace-period state machine waiting for a counter-flip acknowledgement from each CPU, but only that part that interacts with dynticks-idle CPUs.

Line 23 models a line from rcu_try_flip_waitzero() and its call to dyntick_save_progress_counter(), again taking a snapshot of the CPU's dynticks_progress_counter variable.

Finally, lines 24-36 model the relevant code in rcu_try_flip_waitack() and its call to rcu_try_flip_waitack_needed(). This loop is modeling the grace-period state-machine waiting for each CPU to execute a memory barrier, but again only that part that interacts with dynticks-idle CPUs.

Quick Quiz E.12: Wait a minute! In the Linux kernel, both dynticks_progress_counter and rcu_dyntick_snapshot are per-CPU variables. So why are they instead being modeled as single global variables? End Quick Quiz

The resulting model (`dyntickRCU-base.spin`), when run with the `runspin.sh` script, generates 691 states and passes without errors, which is not at all surprising given that it completely lacks the assertions that could find failures. The next section therefore adds safety assertions.