Skip to contentSkip to conversation

Promela/spin model for NO_HZ_FULL_SYSIDLE code

DISCUSSION Paul E. McKenney 3 participants 19 messages Mar 30, 2014 – Apr 7, 2014

lore
Share & tools
lore
#0 lore raw

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
#1 lore raw

----- Original Message -----

Quoted 10 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

If we can show that the model can detect a few failure modes, both for safety and progress, then my confidence level in the model will start to improve. ;-)

Thanks,

Mathieu

Quoted 225 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#2 lore raw

----- Original Message -----

Quoted 30 lines

From: "Mathieu Desnoyers" <[email protected]>
To: [email protected]
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:29:25 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

----- Original Message -----

Quoted 11 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

Quoted 3 lines

If we can show that the model can detect a few failure modes, both for safety and progress, then my confidence level in the model will start to improve. ;-)

Digging through the spin documentation, "-l" is indeed another way besides the _np LTL negation to find non-progress cycles.

Still, injecting known failures would let us learn a lot about the model error detection abilities.

Thanks!

Mathieu

Quoted 237 lines

Thanks,

Mathieu

Quoted 211 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
Quoted 15 lines
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#3 lore raw
In reply to Mathieu Desnoyers
Quoted 14 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 10 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 8 lines

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle, as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert() triggers, as expected.

Quoted 2 lines

If we can show that the model can detect a few failure modes, both for safety and progress, then my confidence level in the model will start to improve. ;-)

Well, there probably is a bug in there somewhere, Murphy being who he is. ;-)

Thanx, Paul

Quoted 235 lines

Thanks,

Mathieu

Quoted 225 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#4 lore raw

----- Original Message -----

Quoted 44 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:54:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 15 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 11 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 9 lines

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject
known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle, as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert() triggers, as expected.

Quoted 7 lines
Quoted 4 lines

If we can show that the model can detect a few failure modes, both for safety
and progress, then my confidence level in the model will start to improve. ;-)

Well, there probably is a bug in there somewhere, Murphy being who he is. ;-)

One failure mode your model seems to miss is when I comment the wakeup:

                /* If needed, wake up the timekeeper. */
                if
#ifndef INJECT_NO_WAKEUP
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                        wakeup_timekeeper = 1;
#endif /* #ifndef INJECT_NO_WAKEUP */
                :: else -> skip;
                fi;

Somehow, I feel I am doing something very nasty to the algorithm, but the model checker fails to find any kind of progress or safety issue. Any idea why ?

Thanks,

Mathieu

Quoted 241 lines

Thanx, Paul

Quoted 236 lines

Thanks,

Mathieu

Quoted 211 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
Quoted 15 lines
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#5 lore raw
Quoted 64 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 44 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:54:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 15 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 11 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 9 lines

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject
known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle, as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert() triggers, as expected.

Quoted 7 lines
Quoted 4 lines

If we can show that the model can detect a few failure modes, both for safety
and progress, then my confidence level in the model will start to improve. ;-)

Well, there probably is a bug in there somewhere, Murphy being who he is. ;-)

One failure mode your model seems to miss is when I comment the wakeup:

                /* If needed, wake up the timekeeper. */
                if
#ifndef INJECT_NO_WAKEUP
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                        wakeup_timekeeper = 1;
#endif /* #ifndef INJECT_NO_WAKEUP */
                :: else -> skip;
                fi;
Quoted 3 lines

Somehow, I feel I am doing something very nasty to the algorithm, but the model checker fails to find any kind of progress or safety issue. Any idea why ?

Hmmm... One reason is because I am not modeling the timekeeper thread as waiting for the wakeup. Let me see what I can do about that...

Thanx, Paul

Quoted 252 lines

Thanks,

Mathieu

Quoted 241 lines

Thanx, Paul

Quoted 236 lines

Thanks,

Mathieu

Quoted 211 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
Quoted 15 lines
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#6 lore raw
Quoted 65 lines · Paul E. McKenney
Quoted 64 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 44 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:54:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 15 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 11 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 9 lines

Please keep in mind that it's been a while since I've looked at Promela proofs, but a couple of questions come to mind. First, how is the execution script below checking for progress in any way ? I remember that we used the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject
known failures, and let them be triggered by error-triggering runs in the scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle, as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert() triggers, as expected.

Quoted 7 lines
Quoted 4 lines

If we can show that the model can detect a few failure modes, both for safety
and progress, then my confidence level in the model will start to improve. ;-)

Well, there probably is a bug in there somewhere, Murphy being who he is. ;-)

One failure mode your model seems to miss is when I comment the wakeup:

                /* If needed, wake up the timekeeper. */
                if
#ifndef INJECT_NO_WAKEUP
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                        wakeup_timekeeper = 1;
#endif /* #ifndef INJECT_NO_WAKEUP */
                :: else -> skip;
                fi;
Quoted 6 lines
Quoted 3 lines

Somehow, I feel I am doing something very nasty to the algorithm, but the model checker fails to find any kind of progress or safety issue. Any idea why ?

Hmmm... One reason is because I am not modeling the timekeeper thread as waiting for the wakeup. Let me see what I can do about that...

And here is an updated model. I now make it loop waiting for the wakeup_timekeeper variable to transition to 1. And I learned that Promela ignores "progress" labels within atomic statements...

The previous error injections still trigger asserts.

Thanx, Paul

------------------------------------------------------------------------

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 2

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
			wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			do
			:: full_sysidle_state == RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				/*
				 * We are asleep, so all workers better
				 * be idle.
				 */
progress_full_system_idle_2:
				atomic {
					i = 0;
					idle = 1;
					do
					:: i < NUM_WORKERS ->
						if
						:: am_setup[i] -> idle = 0;
						:: else -> skip;
						fi;
						i++;
					:: i >= NUM_WORKERS -> break;
					od;
					assert(idle == 1 ||
					       full_sysidle_state <
					       RCU_SYSIDLE_FULL);
				}
			:: full_sysidle_state != RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				skip; /* No progress, should be awakened. */
			:: wakeup_timekeeper != 0 ->
				break;
			od;
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
#7 lore raw

----- Original Message -----

Quoted 89 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Monday, March 31, 2014 1:23:19 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 82 lines · Paul E. McKenney
Quoted 80 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 61 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:54:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 16 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 5 lines

For whatever it is worth, the following model claims safety and progress
for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 14 lines

Please keep in mind that it's been a while since I've looked at Promela
proofs, but a couple of questions come to mind. First, how is the execution
script below checking for progress in any way ? I remember that we used
the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject
known failures, and let them be triggered by error-triggering runs in the
scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually
catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle,
as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert()
triggers, as expected.

Quoted 6 lines

If we can show that the model can detect a few failure modes, both for
safety
and progress, then my confidence level in the model will start to improve.
;-)

Quoted 3 lines

Well, there probably is a bug in there somewhere, Murphy being who he is.
;-)

One failure mode your model seems to miss is when I comment the wakeup:

                /* If needed, wake up the timekeeper. */
                if
#ifndef INJECT_NO_WAKEUP
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                        wakeup_timekeeper = 1;
#endif /* #ifndef INJECT_NO_WAKEUP */
                :: else -> skip;
                fi;

Somehow, I feel I am doing something very nasty to the algorithm, but the model checker fails to find any kind of progress or safety issue. Any idea why ?

Quoted 8 lines
Quoted 2 lines

Hmmm... One reason is because I am not modeling the timekeeper thread as waiting for the wakeup. Let me see what I can do about that...

And here is an updated model. I now make it loop waiting for the wakeup_timekeeper variable to transition to 1. And I learned that Promela ignores "progress" labels within atomic statements...

The previous error injections still trigger asserts.

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

Thoughts ?

Thanks,

Mathieu

Quoted 228 lines

Thanx, Paul

------------------------------------------------------------------------

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 2

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
			wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			do
			:: full_sysidle_state == RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				/*
				 * We are asleep, so all workers better
				 * be idle.
				 */
progress_full_system_idle_2:
				atomic {
					i = 0;
					idle = 1;
					do
					:: i < NUM_WORKERS ->
						if
						:: am_setup[i] -> idle = 0;
						:: else -> skip;
						fi;
						i++;
					:: i >= NUM_WORKERS -> break;
					od;
					assert(idle == 1 ||
					       full_sysidle_state <
					       RCU_SYSIDLE_FULL);
				}
			:: full_sysidle_state != RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				skip; /* No progress, should be awakened. */
			:: wakeup_timekeeper != 0 ->
				break;
			od;
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#8 lore raw
Quoted 111 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 89 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Monday, March 31, 2014 1:23:19 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 82 lines · Paul E. McKenney
Quoted 80 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 61 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Sunday, March 30, 2014 11:54:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 16 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: [email protected], "mathieu desnoyers" <[email protected]>, [email protected]
Cc: [email protected]
Sent: Sunday, March 30, 2014 7:08:56 PM
Subject: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 5 lines

For whatever it is worth, the following model claims safety and progress
for the sysidle state machine.

Thoughts?

Hi Paul,

Quoted 14 lines

Please keep in mind that it's been a while since I've looked at Promela
proofs, but a couple of questions come to mind. First, how is the execution
script below checking for progress in any way ? I remember that we used
the negation of a "_np" LTL claim to check for progress in the past. Moreover, I'd be much more comfortable seeing ifdefs in the code that inject
known failures, and let them be triggered by error-triggering runs in the
scripts (with e.g. -DINJECT_ERROR_XYZ), to confirm that this model actually
catches known issues.

Well, if I comment out the four "progress_" labels, it complains about a non-progress cycle. So at least spin does pay attention to these. ;-)

If I put the "progress_" labels back in, but change the check so as to prevent the state machine from ever entering RCU_SYSIDLE_FULL_NOTED, it cranks through 14M states before complaining about a non-progress cycle,
as expected.

If I revert back to pristine state, and then comment out the statements that reverts state back to RCU_SYSIDLE_NOT when exiting idle, an assert()
triggers, as expected.

Quoted 6 lines

If we can show that the model can detect a few failure modes, both for
safety
and progress, then my confidence level in the model will start to improve.
;-)

Quoted 3 lines

Well, there probably is a bug in there somewhere, Murphy being who he is.
;-)

One failure mode your model seems to miss is when I comment the wakeup:

                /* If needed, wake up the timekeeper. */
                if
#ifndef INJECT_NO_WAKEUP
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                        wakeup_timekeeper = 1;
#endif /* #ifndef INJECT_NO_WAKEUP */
                :: else -> skip;
                fi;

Somehow, I feel I am doing something very nasty to the algorithm, but the model checker fails to find any kind of progress or safety issue. Any idea why ?

Quoted 8 lines
Quoted 2 lines

Hmmm... One reason is because I am not modeling the timekeeper thread as waiting for the wakeup. Let me see what I can do about that...

And here is an updated model. I now make it loop waiting for the wakeup_timekeeper variable to transition to 1. And I learned that Promela ignores "progress" labels within atomic statements...

The previous error injections still trigger asserts.

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 7 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper must start running, for example, the wakeup_timekeeper value must revert to zero.

The problem I had is that the "never" claims seem set up to catch some finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite prefix.

Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Thanx, Paul

Quoted 238 lines

Thanks,

Mathieu

Quoted 228 lines

Thanx, Paul

------------------------------------------------------------------------

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 2

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
progress_idle:
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
			wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			do
			:: full_sysidle_state == RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				/*
				 * We are asleep, so all workers better
				 * be idle.
				 */
progress_full_system_idle_2:
				atomic {
					i = 0;
					idle = 1;
					do
					:: i < NUM_WORKERS ->
						if
						:: am_setup[i] -> idle = 0;
						:: else -> skip;
						fi;
						i++;
					:: i >= NUM_WORKERS -> break;
					od;
					assert(idle == 1 ||
					       full_sysidle_state <
					       RCU_SYSIDLE_FULL);
				}
			:: full_sysidle_state != RCU_SYSIDLE_FULL_NOTED &&
			   wakeup_timekeeper == 0 ->
				skip; /* No progress, should be awakened. */
			:: wakeup_timekeeper != 0 ->
				break;
			od;
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#9 lore raw

----- Original Message -----

Quoted 6 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 41 lines
Quoted 12 lines

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 7 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper must start running, for example, the wakeup_timekeeper value must revert to zero.

The problem I had is that the "never" claims seem set up to catch some finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite prefix.

Quoted 5 lines
Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Here is my attempt at simplifying the model. I use LTL formulas as checks for the two things I think really matter here: having timekeeping eventually active when threads are running, and having timekeeping eventually inactive when threads are idle. Hopefully my Promela is not too rusty:

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG        2       /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL        3       /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED  4       /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle state. */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#10 lore raw
Quoted 51 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 6 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 43 lines
Quoted 12 lines

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 7 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper must start running, for example, the wakeup_timekeeper value must revert to zero.

The problem I had is that the "never" claims seem set up to catch some finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite prefix.

Quoted 1 line

Thoughts ?

Quoted 8 lines
Quoted 3 lines

Me, I eventually switched over to using progress detection. Which might be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Here is my attempt at simplifying the model. I use LTL formulas as checks for the two things I think really matter here: having timekeeping eventually active when threads are running, and having timekeeping eventually inactive when threads are idle. Hopefully my Promela is not too rusty:

Well, this was the first time I had ever tried using LTL or never claims, so you are ahead of me either way. ;-)

Quoted 6 lines

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

OK, am_setup_0 implies that the timekeeper will eventually be running. For two threads, this presumably becomes:

[] ((am_setup_0 || am_setup_1) -> (<> timekeeper_is_running))

Quoted 7 lines

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

And here the two-thread version should be something like this:

[] (!(am_setup_0 || am_setup_1) -> (<> (!timekeeper_is_running || am_setup_0 || am_setup_1)))

It would be nice if never claims allowed local variables, as that would allow looping over the am_setup array. Or maybe I just haven't figured out how to tell spin that a given variable should not be considered to be part of the global state.

Quoted 7 lines

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin

I definitely didn't use "-X". The "spin --help" says "-[XYZ] reserved for use by xspin interface", so maybe it doesn't matter. ;-)

Quoted 5 lines

gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

Interesting. I have put this into a separate branch. May I use your Signed-off-by?

I need to play around a bit more with LTL and progress labels!

Thanx, Paul

Quoted 199 lines

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG        2       /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL        3       /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED  4       /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle state. */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#11 lore raw

----- Original Message -----

Quoted 76 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:21:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 56 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 41 lines
Quoted 12 lines

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 7 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper must start running, for example, the wakeup_timekeeper value must revert to zero.

The problem I had is that the "never" claims seem set up to catch some finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite prefix.

Quoted 5 lines
Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Quoted 5 lines

Here is my attempt at simplifying the model. I use LTL formulas as checks for the two things I think really matter here: having timekeeping eventually
active when threads are running, and having timekeeping eventually inactive when threads are idle. Hopefully my Promela is not too rusty:

Well, this was the first time I had ever tried using LTL or never claims, so you are ahead of me either way. ;-)

Quoted 4 lines

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

Quoted 7 lines
Quoted 2 lines

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

OK, am_setup_0 implies that the timekeeper will eventually be running. For two threads, this presumably becomes:

[] ((am_setup_0 || am_setup_1) -> (<> timekeeper_is_running))

Yes.

Quoted 6 lines
Quoted 6 lines

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

Quoted 7 lines
Quoted 2 lines

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

And here the two-thread version should be something like this:

[] (!(am_setup_0 || am_setup_1) -> (<> (!timekeeper_is_running || am_setup_0 || am_setup_1)))

Yes, I think. Should be double-checked and tested though.

Quoted 5 lines

It would be nice if never claims allowed local variables, as that would allow looping over the am_setup array. Or maybe I just haven't figured out how to tell spin that a given variable should not be considered to be part of the global state.

AFAIU, we're very limited in what we can put in LTL. You could generate a never claim by hand (see the generated pan.ltl as an example), and maybe have more luck.

Quoted 11 lines
Quoted 8 lines

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin

I definitely didn't use "-X". The "spin --help" says "-[XYZ] reserved for use by xspin interface", so maybe it doesn't matter. ;-)

Hopefully. I grabbed the "-X" option from the urcu models. I don't remember why we have it there.

Quoted 9 lines
Quoted 6 lines

gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

Interesting. I have put this into a separate branch. May I use your Signed-off-by?

Yes, of course.

Quoted 2 lines

I need to play around a bit more with LTL and progress labels!

For progress, you'll want to add progress labels within the model, and do a LTL formula checking the _np special variable.

Thanks,

Mathieu

Quoted 211 lines

Thanx, Paul

Quoted 206 lines

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief period.

*/
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough.
*/
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for
sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state.
*/

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle state.
                */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base
                        state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#12 lore raw
Quoted 96 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 76 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:21:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 56 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 41 lines
Quoted 12 lines

Here is the experiment I did on this latest version: I just enabled the safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 7 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately, nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper must start running, for example, the wakeup_timekeeper value must revert to zero.

The problem I had is that the "never" claims seem set up to catch some finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite prefix.

Quoted 5 lines
Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Quoted 5 lines

Here is my attempt at simplifying the model. I use LTL formulas as checks for the two things I think really matter here: having timekeeping eventually
active when threads are running, and having timekeeping eventually inactive when threads are idle. Hopefully my Promela is not too rusty:

Well, this was the first time I had ever tried using LTL or never claims, so you are ahead of me either way. ;-)

Quoted 4 lines

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

Quoted 7 lines
Quoted 2 lines

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

OK, am_setup_0 implies that the timekeeper will eventually be running. For two threads, this presumably becomes:

[] ((am_setup_0 || am_setup_1) -> (<> timekeeper_is_running))

Yes.

Quoted 9 lines
Quoted 8 lines

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

Quoted 6 lines
Quoted 4 lines

And here the two-thread version should be something like this:

[] (!(am_setup_0 || am_setup_1) -> (<> (!timekeeper_is_running || am_setup_0 || am_setup_1)))

Yes, I think. Should be double-checked and tested though.

I did test all four options in the sysidle.sh file with both the original and two-thread LTL claims, and got the expected results. Need something to force failures in the other LTL formula, of course.

Quoted 8 lines
Quoted 4 lines

It would be nice if never claims allowed local variables, as that would allow looping over the am_setup array. Or maybe I just haven't figured out how to tell spin that a given variable should not be considered to be part of the global state.

AFAIU, we're very limited in what we can put in LTL. You could generate a never claim by hand (see the generated pan.ltl as an example), and maybe have more luck.

Any time I tried to assign to anything from within a "never" claim, it yelled at me. ;-)

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin

Quoted 5 lines
Quoted 2 lines

I definitely didn't use "-X". The "spin --help" says "-[XYZ] reserved for use by xspin interface", so maybe it doesn't matter. ;-)

Hopefully. I grabbed the "-X" option from the urcu models. I don't remember why we have it there.

Ah! ;-)

Quoted 10 lines
Quoted 8 lines
Quoted 5 lines

gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

Interesting. I have put this into a separate branch. May I use your Signed-off-by?

Yes, of course.

Very good, thank you!

Quoted 4 lines
Quoted 1 line

I need to play around a bit more with LTL and progress labels!

For progress, you'll want to add progress labels within the model, and do a LTL formula checking the _np special variable.

I did use the progress labels, but used -DNP rather than the LTL _np special variable.

Thanx, Paul

Quoted 222 lines

Thanks,

Mathieu

Quoted 211 lines

Thanx, Paul

Quoted 206 lines

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief period.

*/
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough.
*/
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for
sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state.
*/

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle state.
                */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base
                        state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#13 lore raw

----- Original Message -----

Quoted 168 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:41:03 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 108 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 88 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:21:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 65 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 49 lines
Quoted 14 lines

Here is the experiment I did on this latest version: I just enabled the
safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 8 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately,
nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make
something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper
must start running, for example, the wakeup_timekeeper value must revert
to zero.

The problem I had is that the "never" claims seem set up to catch some
finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite
prefix.

Quoted 6 lines
Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might
be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Quoted 7 lines

Here is my attempt at simplifying the model. I use LTL formulas as checks
for the two things I think really matter here: having timekeeping eventually
active when threads are running, and having timekeeping eventually inactive
when threads are idle. Hopefully my Promela is not too rusty:

Well, this was the first time I had ever tried using LTL or never claims, so you are ahead of me either way. ;-)

Quoted 4 lines

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

Quoted 7 lines
Quoted 2 lines

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

OK, am_setup_0 implies that the timekeeper will eventually be running. For two threads, this presumably becomes:

[] ((am_setup_0 || am_setup_1) -> (<> timekeeper_is_running))

Yes.

Quoted 9 lines
Quoted 8 lines

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

Quoted 7 lines
Quoted 5 lines

And here the two-thread version should be something like this:

[] (!(am_setup_0 || am_setup_1) -> (<> (!timekeeper_is_running || am_setup_0
|| am_setup_1)))

Yes, I think. Should be double-checked and tested though.

I did test all four options in the sysidle.sh file with both the original and two-thread LTL claims, and got the expected results. Need something to force failures in the other LTL formula, of course.

Quoted 8 lines
Quoted 4 lines

It would be nice if never claims allowed local variables, as that would allow looping over the am_setup array. Or maybe I just haven't figured out how to tell spin that a given variable should not be considered to be part of the global state.

AFAIU, we're very limited in what we can put in LTL. You could generate a never claim by hand (see the generated pan.ltl as an example), and maybe have more luck.

Any time I tried to assign to anything from within a "never" claim, it yelled at me. ;-)

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin

Quoted 5 lines
Quoted 2 lines

I definitely didn't use "-X". The "spin --help" says "-[XYZ] reserved for use by xspin interface", so maybe it doesn't matter. ;-)

Hopefully. I grabbed the "-X" option from the urcu models. I don't remember why we have it there.

Ah! ;-)

Quoted 10 lines
Quoted 8 lines
Quoted 5 lines

gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

Interesting. I have put this into a separate branch. May I use your Signed-off-by?

Yes, of course.

Very good, thank you!

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

I need to play around a bit more with LTL and progress labels!

For progress, you'll want to add progress labels within the model, and do a LTL formula checking the _np special variable.

I did use the progress labels, but used -DNP rather than the LTL _np special variable.

My general approach is to split the model from the checked LTL claims as much as possible, so we can use one model for various claims, checking them one by one. It allows shrinking the max search state space by running each check within different runs.

For me, doing the progress check within as a separate LTL claim check fits well in this work flow.

Thanks,

Mathieu

Quoted 239 lines

Thanx, Paul

Quoted 234 lines

Thanks,

Mathieu

Quoted 223 lines

Thanx, Paul

Quoted 218 lines

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief

period.
*/
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long
enough.
*/
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for
sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle
state.
*/

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */
byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle.
*/

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle
                state.
                */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be
                asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG
                ->
                        /* Non-idle and state advanced, revert to base
                        state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened.
                */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#14 lore raw
Quoted 177 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 168 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:41:03 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 108 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 88 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Thursday, April 3, 2014 1:21:58 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

Quoted 65 lines · Mathieu Desnoyers

----- Original Message -----

Quoted 7 lines

From: "Paul E. McKenney" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], [email protected], [email protected]
Sent: Tuesday, April 1, 2014 10:50:44 PM
Subject: Re: Promela/spin model for NO_HZ_FULL_SYSIDLE code

[...]

Quoted 49 lines
Quoted 14 lines

Here is the experiment I did on this latest version: I just enabled the
safety checking (not progress). I commented these lines out (again):

                /* If needed, wake up the timekeeper. */
                if
                //:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
                //      wakeup_timekeeper = 1;
                :: else -> skip;
                fi;

compile and run with:

Quoted 8 lines

spin -a sysidle.spin
gcc -o pan pan.c
./pan -m1280000 -w22

My expectation would be to trigger some kind of assertion that the timekeeper is not active while the worker is running. Unfortunately,
nothing triggers.

That is expected behavior. Failure to wake up the timekeeper is set up as a progress criterion.

Quoted 4 lines

I see 3 possible solutions: we could either add assertions into other branches of the timekeeper, or add assertions into the worker thread. Another way to do it would be to express the assertions as negation of a LTL formula based on state variables.

I did try both a hand-coded "never" clause and LTL formulas without success. You have more experience with them, so perhaps you could make
something work. The need is that if all worker threads go non-idle indefinitely starting from the RCU_SYSIDLE_FULL_NOTED state, the wakeup_timekeeper must eventually be set to 1, and then the timekeeper
must start running, for example, the wakeup_timekeeper value must revert
to zero.

The problem I had is that the "never" claims seem set up to catch some
finite behavior after a possibly-infinite prefix. In this case, we instead need to catch some infinite behavior after a possibly-infinite
prefix.

Quoted 6 lines
Quoted 1 line

Thoughts ?

Me, I eventually switched over to using progress detection. Which might
be a bit unconventional, but it did have the virtue of making the model complain when it should complain. ;-)

Quoted 7 lines

Here is my attempt at simplifying the model. I use LTL formulas as checks
for the two things I think really matter here: having timekeeping eventually
active when threads are running, and having timekeeping eventually inactive
when threads are idle. Hopefully my Promela is not too rusty:

Well, this was the first time I had ever tried using LTL or never claims, so you are ahead of me either way. ;-)

Quoted 4 lines

1) When, at any point in the trail, a worker is setup, then we want to be sure that at some point in the future the timer is necessarily running:

Quoted 7 lines
Quoted 2 lines

timer_active.ltl:
[] (am_setup_0 -> (<> timekeeper_is_running))

OK, am_setup_0 implies that the timekeeper will eventually be running. For two threads, this presumably becomes:

[] ((am_setup_0 || am_setup_1) -> (<> timekeeper_is_running))

Yes.

Quoted 9 lines
Quoted 8 lines

2) When, at any point in the trail, a worker is not setup, then we want to be sure that at some point in the future, either this thread is setup again, or the timekeeper reaches a not running state:

timer_inactive.ltl:
[] (!am_setup_0 -> (<> (!timekeeper_is_running || am_setup_0)))

Quoted 7 lines
Quoted 5 lines

And here the two-thread version should be something like this:

[] (!(am_setup_0 || am_setup_1) -> (<> (!timekeeper_is_running || am_setup_0
|| am_setup_1)))

Yes, I think. Should be double-checked and tested though.

I did test all four options in the sysidle.sh file with both the original and two-thread LTL claims, and got the expected results. Need something to force failures in the other LTL formula, of course.

Quoted 8 lines
Quoted 4 lines

It would be nice if never claims allowed local variables, as that would allow looping over the am_setup array. Or maybe I just haven't figured out how to tell spin that a given variable should not be considered to be part of the global state.

AFAIU, we're very limited in what we can put in LTL. You could generate a never claim by hand (see the generated pan.ltl as an example), and maybe have more luck.

Any time I tried to assign to anything from within a "never" claim, it yelled at me. ;-)

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines

sysidle.sh:
#!/bin/sh

spin -f "!(cat timer_active.ltl)" > pan.ltl #spin -f "!(cat timer_inactive.ltl)" > pan.ltl spin -a -X -N pan.ltl sysidle.spin
#spin -DINJECT_MISSING_WAKEUP -a -X -N pan.ltl sysidle.spin

Quoted 5 lines
Quoted 2 lines

I definitely didn't use "-X". The "spin --help" says "-[XYZ] reserved for use by xspin interface", so maybe it doesn't matter. ;-)

Hopefully. I grabbed the "-X" option from the urcu models. I don't remember why we have it there.

Ah! ;-)

Quoted 10 lines
Quoted 8 lines
Quoted 5 lines

gcc -o pan pan.c
./pan -f -a -m1280000 -w22

#view trail with:

# spin -v -t -N pan.ltl sysidle.spin

Interesting. I have put this into a separate branch. May I use your Signed-off-by?

Yes, of course.

Very good, thank you!

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

I need to play around a bit more with LTL and progress labels!

For progress, you'll want to add progress labels within the model, and do a LTL formula checking the _np special variable.

I did use the progress labels, but used -DNP rather than the LTL _np special variable.

Quoted 7 lines

My general approach is to split the model from the checked LTL claims as much as possible, so we can use one model for various claims, checking them one by one. It allows shrinking the max search state space by running each check within different runs.

For me, doing the progress check within as a separate LTL claim check fits well in this work flow.

Given how different the models are from the original C code, having a couple models that use different approaches is not a bad thing. ;-)

Thanx, Paul

Quoted 249 lines

Thanks,

Mathieu

Quoted 239 lines

Thanx, Paul

Quoted 234 lines

Thanks,

Mathieu

Quoted 223 lines

Thanx, Paul

Quoted 218 lines

sysidle.spin:

/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Models timekeeper "running"
* state with respect to worker thread idle state.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
* Copyright EfficiOS, 2014
*
* Author: Paul E. McKenney <[email protected]>
* Mathieu Desnoyers <[email protected]>
*/

// adapt LTL formulas before changing NUM_WORKERS //#define NUM_WORKERS 2
#define NUM_WORKERS 1
/* Defines used because LTL formula interprets [] */
#define am_setup_0 am_setup[0]
#define am_setup_1 am_setup[1]

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT         0       /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT       1       /* All CPUs idle for brief

period.
*/
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long
enough.
*/
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for
sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle
state.
*/

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */
byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle.
*/

byte timekeeper_is_running = 1; /* Timekeeper initially running */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
        byte oldstate;

        do
        :: 1 ->
                /* Go idle. */
                am_setup[me] = 0;
                am_busy[me] = 0;

                /* Dyntick-idle in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;

                /* Exit idle loop, model getting out of dyntick idle
                state.
                */
                am_busy[me] = 1;

                /* Get state out of full-system idle states. */
                atomic {
                        oldstate = full_sysidle_state;
                        if
                        :: oldstate > RCU_SYSIDLE_SHORT ->
                                full_sysidle_state = RCU_SYSIDLE_NOT;
                        :: else -> skip;
                        fi;
                }

                /* If needed, wake up the timekeeper. */
                if
                :: oldstate == RCU_SYSIDLE_FULL_NOTED ->
#ifndef INJECT_MISSING_WAKEUP
                        wakeup_timekeeper = 1;
#else
                        skip;
#endif
                :: else -> skip;
                fi;

                /* Mark ourselves fully awake and operational. */
                am_setup[me] = 1;

                /* We are fully awake, so timekeeper must not be
                asleep. */
                assert(full_sysidle_state < RCU_SYSIDLE_FULL);

                /* Running in kernel in the following loop. */
                do
                :: 1 -> skip;
                :: 1 -> break;
                od;
        od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
        i = 0; \
        idle = 1; \
        do \
        :: i < NUM_WORKERS -> \
                if \
                :: am_busy[i] == 1 -> idle = 0; \
                :: else -> skip; \
                fi; \
                i++; \
        :: i >= NUM_WORKERS -> break; \
        od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
        byte i;
        byte idle;
        byte curstate;
        byte newstate;

        do
        :: 1 ->
                /* Capture current state. */
                check_idle();
                curstate = full_sysidle_state;
                newstate = curstate;

                /* Manage state... */
                if
                :: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
                        /* Idle, advance to next state. */
                        atomic {
                                if
                                :: full_sysidle_state == curstate ->
                                        newstate = curstate + 1;
                                        full_sysidle_state = newstate;
                                :: else -> skip;
                                fi;
                        }
                :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG
                ->
                        /* Non-idle and state advanced, revert to base
                        state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
                :: else -> skip;
                fi;

                /* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened.
                */
                if
                :: newstate != RCU_SYSIDLE_FULL_NOTED ->
                        skip;
                :: newstate == RCU_SYSIDLE_FULL_NOTED ->
                        timekeeper_is_running = 0;
                        do
                        :: wakeup_timekeeper == 0 ->
                                skip; /* Awaiting wake up */
                        :: else ->
                                timekeeper_is_running = 1;
                                wakeup_timekeeper = 0;
                                break; /* awakened */
                        od;
                fi;
                assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
        od;
}
init {
        byte i = 0;

        do
        :: i < NUM_WORKERS ->
                am_busy[i] = 1;
                am_setup[i] = 1;
                run worker(i);
                i++;
        :: i >= NUM_WORKERS -> break;
        od;
        run timekeeper();
}

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#15 lore raw
In reply to Paul E. McKenney
Quoted 4 lines · Paul E. McKenney

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

I'm going to get fun of myself by risking a review of this. Warning, I don't speak promelian, so I may well write non-sense :)

Quoted 73 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
Quoted 8 lines
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;

On the upstream code, the first read of full_sysidle_state after exiting idle is not performed by an atomic operation. So I wonder if this is right to put this in the atomic section.

I don't know the language enough to tell if it has no effect but I'm just worried that it gets badly intepreted. Like the above read plus the below conditional write in the same atomic section gets packed in a kind of cmpxchg_if_above() ?

Which is what we want to avoid if the value is not above RCU_SYSIDLE_SHORT after a non atomic read.

Quoted 64 lines
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->
Quoted 1 line

progress_idle:

Is this some kind of label? I can't find the target anywhere.

Quoted 11 lines
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
Quoted 8 lines
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}

It looks good but just one thing about the transition from FULL -> FULL_NOTED. At least in the case of CONFIG_NO_HZ_FULL_SYSIDLE_SMALL (which is usually the scenario I refer to, but I'll check further the grace-period driven way as well), we switch from FULL to FULL_NOTED without checking a new round of the dynticks counters.

But this timekeeper() proc doesn't seem to care and does a check_idle() no matter the current state.

There should probably be a special case to handle that otherwise we add a new round of dynticks counters read between FULL and FULL_NOTED transition and this is an entirely different scenario than what we run.

Quoted 3 lines
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;

Looking at the upstream code, I think we reset also when state == RCU_SYSIDLE_SHORT once we detect a non-idle state. If it's not a mistyping, I'm probably missing something.

Thanks.

Quoted 56 lines
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
#16 lore raw
Quoted 8 lines · Frederic Weisbecker
Quoted 4 lines · Paul E. McKenney

For whatever it is worth, the following model claims safety and progress for the sysidle state machine.

Thoughts?

I'm going to get fun of myself by risking a review of this. Warning, I don't speak promelian, so I may well write non-sense :)

Actually, you did find one real mismatch and one arguable one. ;-)

Quoted 85 lines
Quoted 72 lines

Thanx, Paul

------------------------------------------------------------------------
sysidle.sh
------------------------------------------------------------------------
spin -a sysidle.spin
cc -DNP -o pan pan.c
# Fair scheduling to focus progress checks in timekeeper. ./pan -f -l -m1280000 -w22

------------------------------------------------------------------------
sysidle.spin
------------------------------------------------------------------------
/*
* Promela model for CONFIG_NO_HZ_FULL_SYSIDLE=y in the Linux kernel.
* This model assumes that the dyntick-idle bit manipulation works based
* on long usage, and substitutes a per-thread boolean "am_busy[]" array
* for the Linux kernel's dyntick-idle masks. The focus of this model
* is therefore on the state machine itself. Checks for both safety and
* forward progress.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you can access it online at
* http://www.gnu.org/licenses/gpl-2.0.html.
*
* Copyright IBM Corporation, 2014
*
* Author: Paul E. McKenney <[email protected]>
*/

#define NUM_WORKERS 3

byte wakeup_timekeeper = 0; /* Models rcu_kick_nohz_cpu(). */

#define RCU_SYSIDLE_NOT 0 /* Some CPU is not idle. */
#define RCU_SYSIDLE_SHORT 1 /* All CPUs idle for brief period. */
#define RCU_SYSIDLE_LONG 2 /* All CPUs idle for long enough. */
#define RCU_SYSIDLE_FULL 3 /* All CPUs idle, ready for sysidle. */
#define RCU_SYSIDLE_FULL_NOTED 4 /* Actually entered sysidle state. */

byte full_sysidle_state = RCU_SYSIDLE_NOT;

byte am_busy[NUM_WORKERS]; /* Busy is similar to "not dyntick-idle". */ byte am_setup[NUM_WORKERS]; /* Setup means timekeeper knows I am not idle. */

/*
* Non-timekeeping CPU going into and out of dyntick-idle state. */
proctype worker(byte me)

{
	byte oldstate;

	do
	:: 1 ->
		/* Go idle. */
		am_setup[me] = 0;
		am_busy[me] = 0;

		/* Dyntick-idle in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
Quoted 8 lines
		od;

		/* Exit idle loop, model getting out of dyntick idle state. */
		am_busy[me] = 1;

		/* Get state out of full-system idle states. */
		atomic {
			oldstate = full_sysidle_state;

On the upstream code, the first read of full_sysidle_state after exiting idle is not performed by an atomic operation. So I wonder if this is right to put this in the atomic section.

Quoted 6 lines

I don't know the language enough to tell if it has no effect but I'm just worried that it gets badly intepreted. Like the above read plus the below conditional write in the same atomic section gets packed in a kind of cmpxchg_if_above() ?

Which is what we want to avoid if the value is not above RCU_SYSIDLE_SHORT after a non atomic read.

Given that cmpxchg() is being used to emulate exactly that atomic operation, I feel good about this Promela translation. If the value is different at the time of the cmpxchg(), the cmpxchg() fails. I suppose I could write it as follows instead:

		/* Get state out of full-system idle states. */
		oldstate = full_sysidle_state;
		do
		:: 1 ->
			atomic {
				if
				:: oldstate > RCU_SYSIDLE_SHORT &&
				   oldstate == full_sysidle_state ->
					full_sysidle_state = RCU_SYSIDLE_NOT;
					break;
				:: else ->
					oldstate = full_sysidle_state;
				fi;
			}
		od;

Here the "if" emulates the cmpxchg() instruction and the rest emulates the loop. Both representations get the same result when

Quoted 61 lines
Quoted 61 lines
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;
Quoted 6 lines
Quoted 4 lines
		/* Check for acceptance state. */
		if
		:: idle == 0 ->

progress_idle:

Is this some kind of label? I can't find the target anywhere.

It is a marker. If you specify -DNP and if there is any cycle of states that does not pass through a label beginning with "progress", the verification will fail. So it is useful for finding livelocks.

Mathieu posted another way of getting this same effect.

Quoted 25 lines
Quoted 11 lines
			skip;
		:: curstate == RCU_SYSIDLE_NOT ->
progress_idle_reset:
			skip;
		:: else -> skip;
		fi;

		/* Manage state... */
		if
		:: idle == 1 && curstate < RCU_SYSIDLE_FULL_NOTED ->
			/* Idle, advance to next state. */
Quoted 8 lines
			atomic {
				if
				:: full_sysidle_state == curstate ->
					newstate = curstate + 1;
					full_sysidle_state = newstate;
				:: else -> skip;
				fi;
			}

It looks good but just one thing about the transition from FULL -> FULL_NOTED. At least in the case of CONFIG_NO_HZ_FULL_SYSIDLE_SMALL (which is usually the scenario I refer to, but I'll check further the grace-period driven way as well), we switch from FULL to FULL_NOTED without checking a new round of the dynticks counters.

Quoted 6 lines

But this timekeeper() proc doesn't seem to care and does a check_idle() no matter the current state.

There should probably be a special case to handle that otherwise we add a new round of dynticks counters read between FULL and FULL_NOTED transition and this is an entirely different scenario than what we run.

Good catch! I changed the above RCU_SYSIDLE_FULL_NOTED to RCU_SYSIDLE_FULL and added an atomic block to move to RCU_SYSIDLE_FULL_NOTED. Still verifies (whew!).

Quoted 6 lines
Quoted 3 lines
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;

Looking at the upstream code, I think we reset also when state == RCU_SYSIDLE_SHORT once we detect a non-idle state. If it's not a mistyping, I'm probably missing something.

I don't see this. The resetting happens in rcu_sysidle_force_exit(), which contains the following:

	while (oldstate > RCU_SYSIDLE_SHORT) {
		newoldstate = cmpxchg(&full_sysidle_state,
				      oldstate, RCU_SYSIDLE_NOT);
		if (oldstate == newoldstate &&
		    oldstate == RCU_SYSIDLE_FULL_NOTED) {
			rcu_kick_nohz_cpu(tick_do_timer_cpu);
			return; /* We cleared it, done! */
		}
		oldstate = newoldstate;
	}

If the state is RCU_SYSIDLE_SHORT, we skip the body of the "if" thus declining to reset back to RCU_SYSIDLE_NOT. Or am I confused?

Thanx, Paul

Quoted 59 lines

Thanks.

Quoted 56 lines
		:: else -> skip;
		fi;

		/* If in RCU_SYSIDLE_FULL_NOTED, wait to be awakened. */
		do
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
			assert(0); /* Should never get here. */
		:: newstate != RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 1 ->
progress_full_system_idle_1:
			assert(full_sysidle_state == RCU_SYSIDLE_NOT);
		   	wakeup_timekeeper = 0;
			break;
		:: newstate == RCU_SYSIDLE_FULL_NOTED &&
		   wakeup_timekeeper == 0 ->

progress_full_system_idle_2:

			/* We are asleep, so all workers better be idle. */
			atomic {
				i = 0;
				idle = 1;
				do
				:: i < NUM_WORKERS ->
					if
					:: am_setup[i] -> idle = 0;
					:: else -> skip;
					fi;
					i++;
				:: i >= NUM_WORKERS -> break;
				od;
				assert(idle == 1 ||
				       full_sysidle_state < RCU_SYSIDLE_FULL);
			}
		od;
		assert(full_sysidle_state <= RCU_SYSIDLE_FULL_NOTED);
	od;
}
init {
	byte i = 0;

	do
	:: i < NUM_WORKERS ->
		am_busy[i] = 1;
		am_setup[i] = 1;
		run worker(i);
		i++;
	:: i >= NUM_WORKERS -> break;
	od;
	run timekeeper();
}
#17 lore raw
Quoted 8 lines · Paul E. McKenney
Quoted 8 lines

On the upstream code, the first read of full_sysidle_state after exiting idle is not performed by an atomic operation. So I wonder if this is right to put this in the atomic section.

I don't know the language enough to tell if it has no effect but I'm just worried that it gets badly intepreted. Like the above read plus the below conditional write in the same atomic section gets packed in a kind of cmpxchg_if_above() ?

Quoted 5 lines
Quoted 2 lines

Which is what we want to avoid if the value is not above RCU_SYSIDLE_SHORT after a non atomic read.

Given that cmpxchg() is being used to emulate exactly that atomic operation, I feel good about this Promela translation.

Right but the very first read that checks if full_sysidle_state is > RCU_SYSIDLE_SHORT is done in a non-atomic way. Only when it verifies the condition do we use cmpxchg()

       while (oldstate > RCU_SYSIDLE_SHORT) {
           newoldstate = cmpxchg(&full_sysidle_state,
                                  oldstate, RCU_SYSIDLE_NOT);
           if (oldstate == newoldstate && oldstate == RCU_SYSIDLE_FULL_NOTED) {
                rcu_kick_nohz_cpu(tick_do_timer_cpu);
                return; /* We cleared it, done! */
           }
           oldstate = newoldstate;
       }

Now the way you wrote it PROMELA looked like we use cmpxchg() (or some close relative) right away from the first read. It's hard to translate with real world operations so I'm inventing cmpxchg_if_above() which has the same atomic and full barrier properties than cmpxchg() expect that it only exchanges old value with new value if old is above the last parameter:

        oldstate = cmpxchg_if_above(oldstate, RCU_SYSIDLE_NOT, RCU_SYSIDLE_SHORT);
        if (oldstate == RCU_SYSIDLE_FULL_NOTED)
                rcu_kick_nohz_cpu(tick_do_timer_cpu);
                return; /* We cleared it, done! */
Quoted 1 line

If the value is different at the time of the cmpxchg(), the cmpxchg() fails.

Right but it might not do a cmpxchg() if oldval is <= SHORT.

Quoted 18 lines

I suppose I could write it as follows instead:

		/* Get state out of full-system idle states. */
		oldstate = full_sysidle_state;
		do
		:: 1 ->
			atomic {
				if
				:: oldstate > RCU_SYSIDLE_SHORT &&
				   oldstate == full_sysidle_state ->
					full_sysidle_state = RCU_SYSIDLE_NOT;
					break;
				:: else ->
					oldstate = full_sysidle_state;
				fi;
			}
		od;
Quoted 2 lines

Here the "if" emulates the cmpxchg() instruction and the rest emulates the loop. Both representations get the same result when

Ok if they have the same result and implement the first read in a non atomic way then it's all good. The PROMELA syntax has just been confusing to me in this regard.

Quoted 67 lines
Quoted 67 lines
Quoted 66 lines
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->

progress_idle:

Quoted 7 lines
Quoted 1 line

Is this some kind of label? I can't find the target anywhere.

It is a marker. If you specify -DNP and if there is any cycle of states that does not pass through a label beginning with "progress", the verification will fail. So it is useful for finding livelocks.

Mathieu posted another way of getting this same effect.

Ah ok.

Quoted 22 lines
Quoted 7 lines
Quoted 4 lines
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;

Looking at the upstream code, I think we reset also when state == RCU_SYSIDLE_SHORT once we detect a non-idle state. If it's not a mistyping, I'm probably missing something.

I don't see this. The resetting happens in rcu_sysidle_force_exit(), which contains the following:

	while (oldstate > RCU_SYSIDLE_SHORT) {
		newoldstate = cmpxchg(&full_sysidle_state,
				      oldstate, RCU_SYSIDLE_NOT);
		if (oldstate == newoldstate &&
		    oldstate == RCU_SYSIDLE_FULL_NOTED) {
			rcu_kick_nohz_cpu(tick_do_timer_cpu);
			return; /* We cleared it, done! */
		}
		oldstate = newoldstate;
	}
Quoted 2 lines

If the state is RCU_SYSIDLE_SHORT, we skip the body of the "if" thus declining to reset back to RCU_SYSIDLE_NOT. Or am I confused?

Hmm, the loop above is the code of !timekeeper side. I'm referring to the timekeeper side (which is what this PROMELA chunck represents, unless I'm utterly confused).

And the timekeeper side resets full_sysidle_state when it detects a non-idle CPU:

rcu_sys_is_idle() -> rcu_sysidle_report -> rcu_sysidle_cancel()

So the PROMELA code suggests that when we find a non idle CPU, we only reset full_sysidle_state when is it >= RCU_SYSIDLE_LONG:

                  :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;

...but actually the condition upstream seems to be full_sysidle_state >= RCU_SYSIDLE_SHORT.

For example we loop in rcu_sys_is_idle() (case of NR_CPUS < 8), and we detect a round of full-idle CPUs, so we set full_sysidle_state to RCU_SYSIDLE_SHORT. Then we do another pass in the loop but this time we detect a CPU is not idle, so we reset to RCU_SYSIDLE_NOT instead of advancing to RCU_SYSIDLE_LONG.

Right?

Thanks.

#18 lore raw
Quoted 62 lines · Frederic Weisbecker
Quoted 8 lines · Paul E. McKenney
Quoted 8 lines

On the upstream code, the first read of full_sysidle_state after exiting idle is not performed by an atomic operation. So I wonder if this is right to put this in the atomic section.

I don't know the language enough to tell if it has no effect but I'm just worried that it gets badly intepreted. Like the above read plus the below conditional write in the same atomic section gets packed in a kind of cmpxchg_if_above() ?

Quoted 5 lines
Quoted 2 lines

Which is what we want to avoid if the value is not above RCU_SYSIDLE_SHORT after a non atomic read.

Given that cmpxchg() is being used to emulate exactly that atomic operation, I feel good about this Promela translation.

Right but the very first read that checks if full_sysidle_state is > RCU_SYSIDLE_SHORT is done in a non-atomic way. Only when it verifies the condition do we use cmpxchg()

       while (oldstate > RCU_SYSIDLE_SHORT) {
           newoldstate = cmpxchg(&full_sysidle_state,
                                  oldstate, RCU_SYSIDLE_NOT);
           if (oldstate == newoldstate && oldstate == RCU_SYSIDLE_FULL_NOTED) {
                rcu_kick_nohz_cpu(tick_do_timer_cpu);
                return; /* We cleared it, done! */
           }
           oldstate = newoldstate;
       }

Now the way you wrote it PROMELA looked like we use cmpxchg() (or some close relative) right away from the first read. It's hard to translate with real world operations so I'm inventing cmpxchg_if_above() which has the same atomic and full barrier properties than cmpxchg() expect that it only exchanges old value with new value if old is above the last parameter:

        oldstate = cmpxchg_if_above(oldstate, RCU_SYSIDLE_NOT, RCU_SYSIDLE_SHORT);
        if (oldstate == RCU_SYSIDLE_FULL_NOTED)
                rcu_kick_nohz_cpu(tick_do_timer_cpu);
                return; /* We cleared it, done! */
Quoted 1 line

If the value is different at the time of the cmpxchg(), the cmpxchg() fails.

Right but it might not do a cmpxchg() if oldval is <= SHORT.

Quoted 18 lines

I suppose I could write it as follows instead:

		/* Get state out of full-system idle states. */
		oldstate = full_sysidle_state;
		do
		:: 1 ->
			atomic {
				if
				:: oldstate > RCU_SYSIDLE_SHORT &&
				   oldstate == full_sysidle_state ->
					full_sysidle_state = RCU_SYSIDLE_NOT;
					break;
				:: else ->
					oldstate = full_sysidle_state;
				fi;
			}
		od;
Quoted 6 lines
Quoted 2 lines

Here the "if" emulates the cmpxchg() instruction and the rest emulates the loop. Both representations get the same result when

Ok if they have the same result and implement the first read in a non atomic way then it's all good. The PROMELA syntax has just been confusing to me in this regard.

Actually, my first attempt above wasn't quite right. This one is better. So, yes, Promela can be confusing. ;-)

		/* Get state out of full-system idle states. */
		oldstate = full_sysidle_state;
		do
		:: 1 ->
			atomic {
				if
				:: oldstate > RCU_SYSIDLE_SHORT &&
				   oldstate == full_sysidle_state ->
					full_sysidle_state = RCU_SYSIDLE_NOT;
					break;
				:: oldstate > RCU_SYSIDLE_SHORT &&
				   oldstate != full_sysidle_state ->
					oldstate = full_sysidle_state;
				:: oldstate <= RCU_SYSIDLE_SHORT -> break;
				fi;
			}
		od;

And this passes as well.

Quoted 98 lines
Quoted 66 lines
Quoted 66 lines
Quoted 65 lines
			if
			:: oldstate > RCU_SYSIDLE_SHORT ->
				full_sysidle_state = RCU_SYSIDLE_NOT;
			:: else -> skip;
			fi;
		}

		/* If needed, wake up the timekeeper. */
		if
		:: oldstate == RCU_SYSIDLE_FULL_NOTED ->
			wakeup_timekeeper = 1;
		:: else -> skip;
		fi;

		/* Mark ourselves fully awake and operational. */
		am_setup[me] = 1;

		/* We are fully awake, so timekeeper must not be asleep. */
		assert(full_sysidle_state < RCU_SYSIDLE_FULL);

		/* Running in kernel in the following loop. */
		do
		:: 1 -> skip;
		:: 1 -> break;
		od;
	od
}

/*
* Are all the workers in dyntick-idle state?
*/

#define check_idle() \
	i = 0; \
	idle = 1; \
	do \
	:: i < NUM_WORKERS -> \
		if \
		:: am_busy[i] == 1 -> idle = 0; \
		:: else -> skip; \
		fi; \
		i++; \
	:: i >= NUM_WORKERS -> break; \
	od

/*
* Timekeeping CPU.
*/
proctype timekeeper()

{
	byte i;
	byte idle;
	byte curstate;
	byte newstate;

	do
	:: 1 ->
		/* Capture current state. */
		check_idle();
		curstate = full_sysidle_state;
		newstate = curstate;

		/* Check for acceptance state. */
		if
		:: idle == 0 ->

progress_idle:

Quoted 7 lines
Quoted 1 line

Is this some kind of label? I can't find the target anywhere.

It is a marker. If you specify -DNP and if there is any cycle of states that does not pass through a label beginning with "progress", the verification will fail. So it is useful for finding livelocks.

Mathieu posted another way of getting this same effect.

Ah ok.

Quoted 22 lines
Quoted 7 lines
Quoted 4 lines
		:: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
			/* Non-idle and state advanced, revert to base state. */
			full_sysidle_state = RCU_SYSIDLE_NOT;

Looking at the upstream code, I think we reset also when state == RCU_SYSIDLE_SHORT once we detect a non-idle state. If it's not a mistyping, I'm probably missing something.

I don't see this. The resetting happens in rcu_sysidle_force_exit(), which contains the following:

	while (oldstate > RCU_SYSIDLE_SHORT) {
		newoldstate = cmpxchg(&full_sysidle_state,
				      oldstate, RCU_SYSIDLE_NOT);
		if (oldstate == newoldstate &&
		    oldstate == RCU_SYSIDLE_FULL_NOTED) {
			rcu_kick_nohz_cpu(tick_do_timer_cpu);
			return; /* We cleared it, done! */
		}
		oldstate = newoldstate;
	}
Quoted 5 lines
Quoted 2 lines

If the state is RCU_SYSIDLE_SHORT, we skip the body of the "if" thus declining to reset back to RCU_SYSIDLE_NOT. Or am I confused?

Hmm, the loop above is the code of !timekeeper side. I'm referring to the timekeeper side (which is what this PROMELA chunck represents, unless I'm utterly confused).

Yep, we are in the timekeeper part of the model.

Quoted 11 lines

And the timekeeper side resets full_sysidle_state when it detects a non-idle CPU:

rcu_sys_is_idle() -> rcu_sysidle_report -> rcu_sysidle_cancel()

So the PROMELA code suggests that when we find a non idle CPU, we only reset full_sysidle_state when is it >= RCU_SYSIDLE_LONG:

                  :: idle == 0 && full_sysidle_state >= RCU_SYSIDLE_LONG ->
                        /* Non-idle and state advanced, revert to base state. */
                        full_sysidle_state = RCU_SYSIDLE_NOT;
Quoted 7 lines

...but actually the condition upstream seems to be full_sysidle_state >= RCU_SYSIDLE_SHORT.

For example we loop in rcu_sys_is_idle() (case of NR_CPUS < 8), and we detect a round of full-idle CPUs, so we set full_sysidle_state to RCU_SYSIDLE_SHORT. Then we do another pass in the loop but this time we detect a CPU is not idle, so we reset to RCU_SYSIDLE_NOT instead of advancing to RCU_SYSIDLE_LONG.

Right?

So rcu_sys_is_idle() invokes rcu_sysidle_report() after each scan. If rcu_sysidle_report() sees that there was a nonidle CPU, it invokes rcu_sysidle_cancel(). Which does indeed set the state back to RCU_SYSIDLE_NOT, as you say. Who wrote this code, anyway? ;-)

IIRC, the rationale was that hitting the state hard and often on small systems should not be a problem. But there will probably soon be some system out there that will not like this sort of treatment.

I am tempted to modify the kernel to make it easier to model by putting a check for full_sysidle_state >= RCU_SYSIDLE_LONG in rcu_sysidle_cancel(), and I might at some point do just that. For the moment, I just made the model check both ways. It does work either way. (Whew!)

Seems like it would be simpler if the state machines for both large and small systems operated the same, though. And the extra check certainly shouldn't hurt small systems. So I will change the kernel!

Thanx, Paul