15. Appendix: RTEMS Formal Model Guide¶
This appendix covers the various formal models of RTEMS that are currently in existence. It serves two purposes: one is to provide detailed documentation of each model, while the other is provide a guide into how to go about developing and deploying such models.
The general approach followed here is to start by looking at the API documentation and identifying the key data-structures and function prototypes. These are then modelled appropriately in Promela. Then, general behavior patterns of interest are identified, and the Promela model is extended to provide those patterns. A key aspect here is exploiting the fact that Promela allows non-deterministic choices to be specified, which gives the effect of producing arbitrary orderings of model behavior. All of this leads to a situation were the SPIN model-checker can effectively generate scenarios for all possible interleavings. The final stage is mapping those scenarios to RTEMS C test code, which has two parts: generating machine-readable output from SPIN, and developing the refinement mapping from that output to C test code.
Some familiarity is assumed here with the Software Test Framework section in this document.
The following models are included in the directory formal/promela/models/
at the top-level in rtems-central
:
- Chains API (
chains/
) Models the unprotected chain append and get API calls in the Classic Chains API Guide. This was an early model to develop the basic methodology.
- Events Manager (
events/
) Models the behaviour of all the API calls in the Classic Events Manager API Guide. This had to tackle real concurrency and deal with multiple CPUs and priority issues.
- Barrier Manager (
barriers/
) Models the behaviour of all the API calls in then Classic Barrier Manager API.
- Message Manager (
messages/
) Models the create, send and receive API calls in the Classic Message Manager API.
At the end of this guide is a section that discusses various issues that should be tackled in future work.
15.1. Testing Chains¶
Documentation: Chains section in the RTEMS Classic API Guide.
Model Directory: formal/promela/models/chains
.
Model Name: chains-api-model
.
The Chains API provides a doubly-linked list data-structure, optimised for fast
operations in an SMP setting. It was used as proof of concept exercise,
and focussed on just two API calls: rtems-chain-append-unprotected
and rtems-chain-get-unprotected
(hereinafter just append
and get
).
15.1.1. API Model¶
File: chains-api-model.pml
While smart code optimization techniques are very important for RTEMS code, the focus when constructing formal models is on functional correctness, not performance. What is required is the simplest, most obviously correct model.
The append
operation adds new nodes on the end of the list,
while get
removes and returns the node at the start of the list.
The Chains API has many other operations that can add/remove nodes at either end, or somewhere in the middle, but these are considered out of scope.
15.1.1.1. Data Structures¶
There are no pointers in Promela, so we have to use arrays,
with array indices modelling pointers.
With just append
and get
, an array can be used to implement a collection
of nodes in memory.
A Node
type is defined that has next and previous indices,
plus an item payload.
Access to the node list is via a special control node with head and tail pointers.
In the model, an explicit size value is added to this control node,
to allow the writing of properties about chain length,
and to prevent array out-of-bound errors in the model itself.
We assume a single chain
,
with list node storage statically allocated in memory
.
#define PTR_SIZE 3
#define MEM_SIZE 8
typedef Node {
unsigned nxt : PTR_SIZE
; unsigned prv : PTR_SIZE
; byte itm
}
Node memory[MEM_SIZE] ;
typedef Control {
unsigned head : PTR_SIZE;
unsigned tail : PTR_SIZE;
unsigned size : PTR_SIZE
}
Control chain ;
While there are 8 memory elements, element 0 is inaccessible,
as the index 0 is treated like a NULL
pointer.
15.1.1.2. Function Calls¶
The RTEMS prototype for append
is:
void rtems_chain_append_unprotected(
rtems_chain_control *the_chain,
rtems_chain_node *the_node
);
Its implementation starts by checking that the node to be appended is “off chain”, before performing the append. The model is designed to satisfy this property so the check is not modelled. Also, the Chains documentation is not clear about certain error cases. As this is a proof of concept exercise, these details are not modelled.
A Promela inline definition append
models the desired behavior,
simulating C pointers with array addresses. Here ch
is the chain argument,
while np
is a node index.
The model starts by checking that the node pointer is not NULL
,
and that there is room in memory
for another node.
These are to ensure that the model does not have any runtime errors.
Doing a standard model-check of this model finds no errors,
which indicates that those assertions are never false.
inline append(ch,np) {
assert(np!=0); assert(ch.size < (MEM_SIZE-1));
if
:: (ch.head == 0) -> ch.head = np; ch.tail = np; ch.size = 1;
memory[np].nxt = 0; memory[np].prv = 0;
:: (ch.head != 0) -> memory[ch.tail].nxt = np; memory[np].prv = ch.tail;
ch.tail = np; ch.size = ch.size + 1;
fi
}
The RTEMS prototype for get
is:
rtems_chain_node *rtems_chain_get_unprotected(
rtems_chain_control *the_chain
);
It returns a pointer to the node, with NULL
returned if the chain is empty.
Promela inlines involve textual substitution,
so the concept of returning a value makes no sense.
For get
, the model is that of a statement that assigns the return value to
a variable. Both the function argument and return variable name are passed as parameters:
/* np = get(ch); */
inline get(ch,np) {
np = ch.head ;
if
:: (np != 0) ->
ch.head = memory[np].nxt;
ch.size = ch.size - 1;
// memory[np].nxt = 0
:: (np == 0) -> skip
fi
if
:: (ch.head == 0) -> ch.tail = 0
:: (ch.head != 0) -> skip
fi
}
15.1.2. Behavior patterns¶
File: chains-api-model.pml
A key feature of using a modelling language like Promela is that it has both explicit and implicit non-determinism. This can be exploited so that SPIN will find all possible interleavings of behavior.
The Chains API model consists of six processes, three which perform append
,
and three that perform get
, waiting if the chain is empty. This model relies
on implicit non-determinism, in that the SPIN scheduler can choose and switch
between any unblocked process at any point. There is no explicit non-determinism
in this model.
Promela process doAppend
takes node index addr
and a value val
as
parameters. It puts val
into the node indexed by addr
,
then calls append
, and terminates.
It is all made atomic to avoid unnecessary internal interleaving of operations because unprotected versions of API calls should only be used when interrupts
are disabled.
proctype doAppend(int addr; int val) {
atomic{ memory[addr].itm = val;
append(chain,addr); } ;
}
The doNonNullGet
process waits for the chain to be non-empty before attempting to get
an element. The first statement inside the atomic
construct is an expression, as a statements, that blocks while it evaluates to
zero. That only happens if head
is in fact zero. The model also has an
assertion that checks that a non-null node is returned.
proctype doNonNullGet() {
atomic{
chain.head != 0;
get(chain,nptr);
assert(nptr != 0);
} ;
}
All processes terminate after they have performed their (sole) action.
The top-level of a Promela model is an initial process declared by the init
construct. This initializes the chain as empty and then runs all six processes concurrently. It then uses the special _nr_pr
variable to wait for all six
processes to terminate. A final assertion checks that the chain is empty.
init {
pid nr;
chain.head = 0; chain.tail = 0; chain.size = 0 ;
nr = _nr_pr; // assignment, sets `nr` to current number of procs
run doAppend(6,21);
run doAppend(3,22);
run doAppend(4,23);
run doNonNullGet();
run doNonNullGet();
run doNonNullGet();
nr == _nr_pr; // expression, waits until number of procs equals `nr`
assert (chain.size == 0);
}
Simulation of this model will show some execution sequence in which the appends happen in a random order, and the gets also occur in a random order, whenever the chain is not empty. All assertions are always satisfied, including the last one above. Model checking this model explores all possible interleavings and reports no errors of any kind. In particular, when the model reaches the last assert statement, the chain size is always zero.
SPIN uses the C pre-processor, and generates the model as a C program. This
model has a simple flow of control: basically execute each process once in an
almost arbitrary order, assert that the chain is empty, and terminate. Test
generation here just requires the negation of the final assertion to get all
possible interleavings. The special C pre-processor definition TEST_GEN
is
used to switch between the two uses of the model. The last line above is
replaced by:
#ifdef TEST_GEN
assert (chain.size != 0);
#else
assert (chain.size == 0);
#endif
A test generation run can then be invoked by passing in -DTEST_GEN
as a
command-line argument.
15.1.3. Annotations¶
File: chains-api-model.pml
The model needs to have printf
statements added to generation the
annotations used to perform the test generation.
This model wraps each of six API calls in its own process, so that model
checking can generate all feasible interleavings. However, the plan for the test code is that it will be just one RTEMS Task, that executes all the API
calls in the order determined by the scenario under consideration. All the
annotations in this model specify 0
as the Promela process identifier.
15.1.3.1. Data Structures¶
Annotations have to be provided for any variable or datastructure declarations
that will need to have corresponding code in the test program.
These have to be printed out as the model starts to run.
For this model, the MAX_SIZE
parameter is important,
as are the variables memory
, nptr
, and chain
:
printf("@@@ 0 NAME Chain_AutoGen\n")
printf("@@@ 0 DEF MAX_SIZE 8\n");
printf("@@@ 0 DCLARRAY Node memory MAX_SIZE\n");
printf("@@@ 0 DECL unsigned nptr NULL\n")
printf("@@@ 0 DECL Control chain\n");
At this point, a parameter-free initialization annotation is issued. This should be refined to C code that initializes the above variables.
printf("@@@INIT\n");
15.1.3.2. Function Calls¶
For append
, two forms of annotation are produced. One uses the CALL
format to report the function being called along with its arguments. The other
form reports the resulting contents of the chain.
proctype doAppend(int addr; int val) {
atomic{ memory[addr].itm = val; append(chain,addr);
printf("@@@ 0 CALL append %d %d\n",val,addr);
show_chain();
} ;
}
The statement show_chain()
is an inline function that prints the
contents of the chain after append returns.
The resulting output is multi-line,
starting with @@@ 0 SEQ chain
,
ending with @@@ 0 END chain
,
and with entries in between of the form @@@ 0 SCALAR _ val
displaying chain elements, line by line.
Something similar is done for get
, with the addition of a third annotation
show_node()
that shows the node that was got:
proctype doNonNullGet() {
atomic{
chain.head != 0;
get(chain,nptr);
printf("@@@ 0 CALL getNonNull %d\n",nptr);
show_chain();
assert(nptr != 0);
show_node();
} ;
}
The statement show_node()
is defined as follows:
inline show_node (){
atomic{
printf("@@@ 0 PTR nptr %d\n",nptr);
if
:: nptr -> printf("@@@ 0 STRUCT nptr\n");
printf("@@@ 0 SCALAR itm %d\n", memory[nptr].itm);
printf("@@@ 0 END nptr\n")
:: else -> skip
fi
}
}
It prints out the value of nptr
, which is an array index. If it is not zero,
it prints out some details of the indexed node structure.
Annotations are also added to the init
process to show the chain and node.
chain.head = 0; chain.tail = 0; chain.size = 0;
show_chain();
show_node();
15.1.4. Refinement¶
Files:
chains-api-model-rfn.yml
chains-api-model-pre.h
tr-chains-api-model.c
Model annotations are converted to C test code using a YAML file that maps
single names to test code snippets into which parameters can be substituted.
Parameters are numbered from zero, and the n
th parameter will be substituted
wherever {n}
occurs in the snippet.
Refinement is more than just the above mapping from annotations to code. Some of
this code will refer to C variables, structures, and functions that are needed
to support the test. Some of these are declared chains-api-model-pre.h
and implemented in tr-chains-api-model.c
.
15.1.4.1. Data Structures¶
The initialization generates one each of NAME
, DEF
, DCLARRAY
, and
INIT
annotations, and two DECL
annotations.
The DEF
entry is currently not looked up as it is automatically converted to a #define
.
The NAME
annotation is used to declare the test case name, which is
stored in the global variable rtems_test_name
. The current
refinement entry is:
NAME: |
const char rtems_test_name[] = "Model_Chain_API";
In this case, the name is fixed and ignores what is declared in the model.
The DCLARRAY Node memory MAX_SIZE
annotation looks up memory_DCL
in the
refinement file, passing in memory
and MAX_SIZE
as arguments. The entry in the refinement file is:
memory_DCL: item {0}[{1}];
Here item
is the type of the chains nodes used in the test code. It is
declared in chains-api-model.pre.h
as:
typedef struct item
{
rtems_chain_node node;
int val;
} item;
Substituting the arguments gives:
item memory[MAX_SIZE];
The two DECL
annotations have two or three parameters. The first is the
type, the second is the variable name, and the optional third is an initial
value. The lookup key is the variable name with _DCL
added on.
In the refinement file, the entry only provides the C type, and the other parts of the declaration are added in.
The entries are:
nptr_DCL: item *
chain_DCL: rtems_chain_control
Annotation DECL unsigned nptr NULL
results in:
item * nptr = NULL ;
Annotation DECL Control chain
results in:
rtems_chain_control chain ;
The INIT
annotation is looked up as INIT
itself. It should be mapped to
code that does all necessary initialization. The refinement entry for chains is:
INIT: rtems_chain_initialize_empty( &chain );
In addition to all the above dealing with declarations and initialization, there are the annotations, already described above, that are used to display composite values, such as structure contents, and chain contents.
In the model, all accesses to individual chain nodes are via index nptr
,
which occurs in two types of annotations, PTR
and STRUCT
. The PTR
annotation is refined by looking up nptr_PTR
with the value of nptr
as the sole argument. The refinement entry is:
nptr_PTR: |
T_eq_ptr( nptr, NULL );
T_eq_ptr( nptr, &memory[{0}] );
The first line is used if the value of nptr
is zero, otherwise the second
line is used.
The use of STRUCT
requires three annotation lines in a row, e.g.:
@@@ 0 STRUCT nptr
@@@ 0 SCALAR itm 21
@@@ 0 END nptr
The STRUCT
and END
annotations do not generate any code, but open and
close a scope in which nptr
is noted as the “name” of the struct. The
SCALAR
annotation is used to observe simple values such as numbers or booleans. However, within a STRUCT
it belongs to a C struct
, so the
relevant field needs to be used to access the value.
Within this scope, the scalar variable itm
is looked up as a field name,
by searching for itm_FSCALAR
with arguments``nptr`` and 21
, which returns the entry:
itm_FSCALAR: T_eq_int( {0}->val, {1} );
This gets turned into the following test:
T_eq_int( nptr->val, 21 );
A similar idea is used to test the contents of a chain. The annotations produced
start with a SEQ
annotation, followed by a SCALAR
annotation for each
item in the chain, and then ending with an END
annotation. Again, there is
a scope defined where the SEQ
argument is the “name” of the sequence.
The SCALAR
entries have no name here (indicated by _
), and their values
are accumulated in a string, separated by spaces. Test code generation is
triggered this time by the END
annotation, that looks up the “name” with _SEQ
appended, and the accumulated string as an argument. The corresponding entry for chain sequences is:
chain_SEQ: |
show_chain( &chain, ctx->buffer );
T_eq_str( ctx->buffer, "{0} 0" );
So, the following chain annotation sequence:
@@@ 0 SEQ chain
@@@ 0 SCALAR _ 21
@@@ 0 SCALAR _ 22
@@@ 0 END chain
becomes the following C code:
show_chain( &chain, ctx->buffer );
T_eq_str( ctx->buffer, " 21 22 0" );
C function show_chain()
is defined in tr-chains-api-model.c
and
generates a string with exactly the same format as that produced above. These
are then compared for equality.
Note
The Promela/SPIN model checker’s prime focus is modelling and verifying
concurrency related properties. It is not intended for verifying sequential
code or data transformations. This is why some of the STRUCT
/SEQ
material here is so clumsy. It plays virtually no role in the other models.
15.1.4.2. Function Calls¶
For @@@ 0 CALL append 22 3
lookup append
to get
memory[{1}].val = {0};
rtems_chain_append_unprotected( &chain, (rtems_chain_node*)&memory[{1}] );
Substitute 22
and 3
in to produce
memory[3].val = 22;
rtems_chain_append_unprotected( &chain, (rtems_chain_node*)&memory[3] );
For @@@ 0 CALL getNonNull 3
lookup getNonNull
to obtain
nptr = get_item( &chain );
T_eq_ptr( nptr, &memory[{0}] );
Function get_item()
is defined in tc-chains-api-model.c
and calls rtems_chain_get_unprotected()
. Substitute 3
to produce:
nptr = get_item( &chain );
T_eq_ptr( nptr, &memory[3] );
15.2. Testing Concurrent Managers¶
All the other models are of Managers that provide some form of communication between multiple RTEMS Tasks. This introduces a number of issues regarding the timing and control of tasks, particularly when developing reproducible tests, where the sequencing of behavior is the same every time the test runs. The tests are generated by following the schemes already in use for regular RTEMS handwritten tests. In particular the pre-existing tests for Send and Receive in the Event Manager where used as a guide.
15.2.1. Testing Strategy¶
The tests are organized as follows:
A designated Task, the Runner, is responsible for initializing, coordinating and tearing down a test run. Coordination involves starting other Worker Tasks that perform tests, and waiting for them to complete. It may also run some tests itself.
One or more Worker Tasks are used to perform test actions.
Each RTEMS Task (Runner/Worker) is modelled by one Promela process.
Simple Binary Semaphores are used to coordinate all the tasks to ensure that the interleaving is always the same (See Semaphore Manager section in Classic API Manual).
Two other Promela processes are required: One, called
Clock()
is used to model timing and timeouts; The other, calledSystem()
models relevant behavior of the RTEMS scheduler.
15.2.2. Model Structure¶
All the models developed so far are based on this framework. The structure of these models takes the following form:
- Constant Declarations
Mainly
#define
s that define important constants.- Datastructure Definitions
Promela
typedef
s that describe key forms of data. In particular there is a typeTask
that models RTEMS Tasks. The Simple Binary Semaphores are modelled as boolean variables.- Global Variable Declarations
Typically these are arrays of data-structures, representing objects such as tasks or semaphores.
- Supporting Models
These are
inline
definitions that capture common behavior. In all models this includesObtain()
andRelease()
to model semaphores, andwaitUntilReady()
that models a blocked task waiting to be unblocked. Included here are other definitions specific to the particular Manager being modelled.- API Models
These are
inline
definitions that model the behavior of each API call. All behavior must be modelled, including bad calls that (should) result in an error code being returned. The parameter lists used in the Promela models will differ from those of the actual API calls. Consider a hypothetical RTEMS API call:rc = rtems_some_api(arg1,arg2,...,argN);One reason, common to all calls, is that the
inline
construct has no concept of returning a value, so a variable parameter has to be added to represent it, and it has to be ensured the appropriate return code is assigned to it.inline some_api(arg1,arg2,...,argN,rc) { ... rc = RC_some_code }Another reason is that some RTEMS types encode a number of different concepts in a single machine word. The most notable of these is the
rtems_options
type, that specifies various options, usually for calls that may block. In some models, some options are modelled individually, for clarity. So the API model may have two or more parameters where the RTEMS call has one.inline some_api(arg1,arg2feat1,arg2feat2,...,argN,rc) { ... rc = RC_some_code }The refinement of this will pass the multiple feature arguments to a C function that will assemble the single RTEMS argument.
A third reason is that sometimes it is important to also provide the process id of the calling task. This can be important where priority and preemption are involved.
- Scenario Generation
A Testsuite that exercises all the API code is highly desirable. This requires running tests that explore a wide range of scenarios, normally devised by hand when writing a testsuite. With Promela/SPIN, the model-checker can generate all of these simplify as a result of its exhaustive search of the model. In practice, scenarios fall into a number of high-level categories, so the first step is make a random choice of such a category. Within a category there may be further choices to be done. A collection of global scenario variables are used to records the choices made. This is all managed by inline
chooseScenario()
.- RTEMS Test Task Modelling
This is a series of Promela
proctype
s, one for the Runner Task, and one for each of the Worker Tasks. Their behavior is controlled by the global scenario variables.- System Modelling
These are Promela processes that model relevant underlying RTEMS behavior, such as the scheduler (
System()
) and timers (Clock()
).- Model Main Process
Called
init
, this initialises variables, invokeschooseScenario()
, runs all the processes, waits for them to terminate, and then terminates itself.
The Promela models developed so far for these Managers always terminate. The last few lines of each are of the form:
#ifdef TEST_GEN
assert(false);
#endif
If these models are run in the usual way (simulation or verification),
then a correct verified model is observed.
If -DTEST_GEN
is provided as the first command-line argument,
in verification mode configured to find all counterexamples,
then all the possible (correct) behaviours of the system will be generated.
15.2.3. Transforming Model Behavior to C Code¶
As described earlier, printf
statements are used
to produce easy to parse output that makes
model events and outcomes easy to identify and process.
The YAML file used to define the refinement from model to code
provides a way of looking up an observation with arguments,
and then obtaining a C template that can be populated with those arguments.
This refinement is a bridge between two distinct worlds:
- Model World:
where the key focus is on correctness and clarity.
- Code World:
where clarity is often sacrificed for efficiency.
This means that the model-to-code relationship need not be a simple one-to-one mapping. This has already been alluded to above when the need for extra parameters in API call models was discussed. It can also be helpful when the model is better treating various attributes separately, while the code handles those attributes packed into machine words.
It is always reasonable to add test support code to the C test sources, and this can include C functions that map distinct attribute values down into some compact merged representation.
15.3. Testing the Event Manager¶
Documentation: Event Manager section in the RTEMS Classic API Guide.
Model Directory: formal/promela/models/events
.
Model Name: event-mgr-model
.
The Event Manager allows tasks to send events to, and receive events from, other tasks. From the perspective of the Event Manager, events are just uninterpreted numbers in the range 0..31, encoded as a 32-bit bitset.
rtems_event_send(id,event_in)
allows a task to send a bitset to a designated task
rtems_event_receive(event_in,option_set,ticks,event_out)
allows a task to specify a desired bitset with options on what to do if it is not present.
Most of the requirements are pretty straightforward, but two were a little more complex, and drove the more complex parts of the modelling.
If a task was blocked waiting to receive events, and a lower priority task then sent the events that would wake that blocked task, then the sending task would be immediately preempted by the receiver task.
There was a requirement that explicitly discussed the situation where the two tasks involved were running on different processors.
A preliminary incomplete model of the Event Manager was originally developed
by the consortium early in the project. The model was then completed during
the rest of the activity by a Masters student: [Jen21].
They also developed the first iteration of the testbuilder
program.
15.3.1. API Model¶
File: event-mgr-model.pml
The RTEMS Event set contains 32 values, but in the model limits this to
just four, which is enough for test purposes.
Some inline definitions are provided to encode (events
), display
(printevents
), and subtract (setminus
) events.
The rtems_option_set
is simplifiedto just two relevant bits: the timeout
setting (Wait
, NoWait
), and how much of the desired event set will
satisfy the receiver (All
, Any
).
These are passed in as two separate arguments to the model of the receive call.
15.3.1.1. Event Send¶
An RTEMS call rc = rtems_event_send(tid,evts)
is modelled by an inline of
the form:
event_send(self,tid,evts,rc)
- The four arguments are:
self
: id of process modelling the task/IDR making call.tid
: id of process modelling the target task of the call.evts
: event set being sent.rc
: updated with the return code when the send completes.
The main complication in the otherwise straightforward model is the requirement to preempt under certain circumstances.
inline event_send(self,tid,evts,rc) {
atomic{
if
:: tid >= BAD_ID -> rc = RC_InvId
:: tid < BAD_ID ->
tasks[tid].pending = tasks[tid].pending | evts
// at this point, have we woken the target task?
unsigned got : NO_OF_EVENTS;
bool sat;
satisfied(tasks[tid],got,sat);
if
:: sat ->
tasks[tid].state = Ready;
printf("@@@ %d STATE %d Ready\n",_pid,tid)
preemptIfRequired(self,tid) ;
// tasks[self].state may now be OtherWait !
waitUntilReady(self);
:: else -> skip
fi
rc = RC_OK;
fi
}
}
Three inline abstractions are used:
satisfied(task,out,sat)
updates
out
with the wanted events received so far, and then checks if a receive has been satisfied. It updates itssat
argument to reflect the check outcome.preemptIfRequired(self,tid)
forces the sending process to enter the
OtherWait
, if circumstances require it.waitUntilReady(self)
basically waits for the process state to become
Ready
.
15.3.1.2. Event Receive¶
An RTEMS call rc = rtems_event_receive(evts,opts,interval,out)
is modelled
by an inline of
the form:
event_receive(self,evts,wait,wantall,interval,out,rc)
- The seven arguments are:
self
: id of process modelling the task making callevts
: input event setwait
: true if receive should waitwhat
: all, or some?interval
: wait interval (0 waits forever)out
: pointer to location for satisfying events when the receive completes.rc
: updated with the return code when the receive completes.
There is a small complication, in that there are distinct variables in the model for receiver options that are combined into a single RTEMS option set. The actual calling sequence in C test code will be:
opts = mergeopts(wait,wantall);
rc = rtems_event_receive(evts,opts,interval,out);
Here mergeopts
is a C function defined in the C Preamble.
inline event_receive(self,evts,wait,wantall,interval,out,rc){
atomic{
printf("@@@ %d LOG pending[%d] = ",_pid,self);
printevents(tasks[self].pending); nl();
tasks[self].wanted = evts;
tasks[self].all = wantall
if
:: out == 0 ->
printf("@@@ %d LOG Receive NULL out.\n",_pid);
rc = RC_InvAddr ;
:: evts == EVTS_PENDING ->
printf("@@@ %d LOG Receive Pending.\n",_pid);
recout[out] = tasks[self].pending;
rc = RC_OK
:: else ->
bool sat;
retry: satisfied(tasks[self],recout[out],sat);
if
:: sat ->
printf("@@@ %d LOG Receive Satisfied!\n",_pid);
setminus(tasks[self].pending,tasks[self].pending,recout[out]);
printf("@@@ %d LOG pending'[%d] = ",_pid,self);
printevents(tasks[self].pending); nl();
rc = RC_OK;
:: !sat && !wait ->
printf("@@@ %d LOG Receive Not Satisfied (no wait)\n",_pid);
rc = RC_Unsat;
:: !sat && wait && interval > 0 ->
printf("@@@ %d LOG Receive Not Satisfied (timeout %d)\n",_pid,interval);
tasks[self].ticks = interval;
tasks[self].tout = false;
tasks[self].state = TimeWait;
printf("@@@ %d STATE %d TimeWait %d\n",_pid,self,interval)
waitUntilReady(self);
if
:: tasks[self].tout -> rc = RC_Timeout
:: else -> goto retry
fi
:: else -> // !sat && wait && interval <= 0
printf("@@@ %d LOG Receive Not Satisfied (wait).\n",_pid);
tasks[self].state = EventWait;
printf("@@@ %d STATE %d EventWait\n",_pid,self)
if
:: sendTwice && !sentFirst -> Released(sendSema);
:: else
fi
waitUntilReady(self);
goto retry
fi
fi
printf("@@@ %d LOG pending'[%d] = ",_pid,self);
printevents(tasks[self].pending); nl();
}
}
Here satisfied()
and waitUntilReady()
are also used.
15.3.2. Behaviour Patterns¶
File: event-mgr-model.pml
The Event Manager model consists of five Promela processes:
init
The first top-level Promela process that performs initialisation, starts the other processes, waits for them to terminate, and finishes.
System
A Promela process that models the behaviour of the operating system, in particular that of the scheduler.
Clock
A Promela process used to facilitate modelling timeouts.
Receiver
The Promela process modelling the test Runner, that also invokes the receive API call.
Sender
A Promela process modelling a singe test Worker that invokes the send API call.
Two simple binary semaphores are used to synchronise the tasks.
The Task model only looks at an abstracted version of RTEMS Task states:
Zombie
used to model a task that has just terminated. It can only be deleted.
Ready
same as the RTEMS notion of
Ready
.EventWait
is
Blocked
inside a call ofevent_receive()
with no timeout.TimeWait
is
Blocked
inside a call ofevent_receive()
with a timeout.OtherWait
is
Blocked
for some other reason, which arises in this model when a sender gets pre-empted by a higher priority receiver it has just satisfied.
Tasks are represented using a datastructure array. As array indices are proxies here for C pointers, the zeroth array entry is always unused, as index value 0 is used to model a NULL C pointer.
typedef Task {
byte nodeid; // So we can spot remote calls
byte pmlid; // Promela process id
mtype state ; // {Ready,EventWait,TickWait,OtherWait}
bool preemptable ;
byte prio ; // lower number is higher priority
int ticks; //
bool tout; // true if woken by a timeout
unsigned wanted : NO_OF_EVENTS ; // EvtSet, those expected by receiver
unsigned pending : NO_OF_EVENTS ; // EvtSet, those already received
bool all; // Do we want All?
};
Task tasks[TASK_MAX]; // tasks[0] models a NULL dereference
byte sendrc; // Sender global variable
byte recrc; // Receiver global variable
byte recout[TASK_MAX] ; // models receive 'out' location.
15.3.2.1. Task Scheduling¶
In order to produce a model that captures real RTEMS Task behaviour, there need to be mechanisms that mimic the behaviour of the scheduler and other activities that can modify the execution state of these Tasks. Given a scenario generated by such a model, synchronisation needs to be added to the generated C code to ensure test has the same execution patterns.
Relevant scheduling behavior is modelled by two inlines that have already
been mentioned: waitUntilReady()
and preemptIfRequired()
.
For synchronisation, simple boolean semaphores are used, where True means available, and False means the semaphore has been acquired.
bool semaphore[SEMA_MAX]; // Semaphore
The synchronisation mechanisms are:
Obtain(sem_id)
call that waits to obtain semaphore
sem_id
.Release(sem_id)
call that releases semaphore
sem_id
Released(sem_id)
simulates ecosystem behaviour that releases
sem_id
.
The difference between Release
and Released
is that the first issues
a SIGNAL
annotation, while the second does not.
15.3.2.2. Scenarios¶
A number of different scenario schemes were defined that cover various aspects of Event Manager behaviour. Some schemes involve only one task, and are usually used to test error-handling or abnormal situations. Other schemes involve two tasks, with some mixture of event sending and receiving, with varying task priorities.
For example, an event send operation can involve a target identifier that
is invalid (BAD_ID
), correctly identifies a receiver task (RCV_ID
), or
is sending events to itself (SEND_ID
).
typedef SendInputs {
byte target_id ;
unsigned send_evts : NO_OF_EVENTS ;
} ;
SendInputs send_in[MAX_STEPS];
An event receive operation will be determined by values for desired events, and the relevant to bits of the option-set parameter.
typedef ReceiveInputs {
unsigned receive_evts : NO_OF_EVENTS ;
bool will_wait;
bool everything;
byte wait_length;
};
ReceiveInputs receive_in[MAX_STEPS];
There is a range of global variables that define scenarios for both send and
receive. This defines a two-step process for choosing a scenario.
The first step is to select a scenario scheme. The possible schemes are
defined by the following mtype
:
mtype = {Send,Receive,SndRcv,RcvSnd,SndRcvSnd,SndPre,MultiCore};
mtype scenario;
One of these is chosen by using a conditional where all alternatives are executable, so behaving as a non-deterministic choice of one of them.
if
:: scenario = Send;
:: scenario = Receive;
:: scenario = SndRcv;
:: scenario = SndPre;
:: scenario = SndRcvSnd;
:: scenario = MultiCore;
fi
Once the value of scenario
is chosen, it is used in another conditional
to select a non-deterministic choice of the finer details of that scenario.
if
:: scenario == Send ->
doReceive = false;
sendTarget = BAD_ID;
:: scenario == Receive ->
doSend = false
if
:: rcvWait = false
:: rcvWait = true; rcvInterval = 4
:: rcvOut = 0;
fi
printf( "@@@ %d LOG sub-senario wait:%d interval:%d, out:%d\n",
_pid, rcvWait, rcvInterval, rcvOut )
:: scenario == SndRcv ->
if
:: sendEvents = 14; // {1,1,1,0}
:: sendEvents = 11; // {1,0,1,1}
fi
printf( "@@@ %d LOG sub-senario send-receive events:%d\n",
_pid, sendEvents )
:: scenario == SndPre ->
sendPrio = 3;
sendPreempt = true;
startSema = rcvSema;
printf( "@@@ %d LOG sub-senario send-preemptable events:%d\n",
_pid, sendEvents )
:: scenario == SndRcvSnd ->
sendEvents1 = 2; // {0,0,1,0}
sendEvents2 = 8; // {1,0,0,0}
sendEvents = sendEvents1;
sendTwice = true;
printf( "@@@ %d LOG sub-senario send-receive-send events:%d\n",
_pid, sendEvents )
:: scenario == MultiCore ->
multicore = true;
sendCore = 1;
printf( "@@@ %d LOG sub-senario multicore send-receive events:%d\n",
_pid, sendEvents )
:: else // go with defaults
fi
Ddefault values are defined for all the global scenario variables so that the above code focusses on what differs. The default scenario is a receiver waiting for a sender of the same priority which sends exactly what was requested.
15.3.2.3. Sender Process (Worker Task)¶
The sender process then uses the scenario configuration to determine its behaviour. A key feature is the way it acquires its semaphore before doing a send, and releases the receiver semaphore when it has just finished sending. Both these semaphores are initialised in the unavailable state.
proctype Sender (byte nid, taskid) {
tasks[taskid].nodeid = nid;
tasks[taskid].pmlid = _pid;
tasks[taskid].prio = sendPrio;
tasks[taskid].preemptable = sendPreempt;
tasks[taskid].state = Ready;
printf("@@@ %d TASK Worker\n",_pid);
if
:: multicore ->
// printf("@@@ %d CALL OtherScheduler %d\n", _pid, sendCore);
printf("@@@ %d CALL SetProcessor %d\n", _pid, sendCore);
:: else
fi
if
:: sendPrio > rcvPrio -> printf("@@@ %d CALL LowerPriority\n", _pid);
:: sendPrio == rcvPrio -> printf("@@@ %d CALL EqualPriority\n", _pid);
:: sendPrio < rcvPrio -> printf("@@@ %d CALL HigherPriority\n", _pid);
:: else
fi
repeat:
Obtain(sendSema);
if
:: doSend ->
if
:: !sentFirst -> printf("@@@ %d CALL StartLog\n",_pid);
:: else
fi
printf("@@@ %d CALL event_send %d %d %d sendrc\n",_pid,taskid,sendTarget,sendEvents);
if
:: sendPreempt && !sentFirst -> printf("@@@ %d CALL CheckPreemption\n",_pid);
:: !sendPreempt && !sentFirst -> printf("@@@ %d CALL CheckNoPreemption\n",_pid);
:: else
fi
event_send(taskid,sendTarget,sendEvents,sendrc);
printf("@@@ %d SCALAR sendrc %d\n",_pid,sendrc);
:: else
fi
Release(rcvSema);
if
:: sendTwice && !sentFirst ->
sentFirst = true;
sendEvents = sendEvents2;
goto repeat;
:: else
fi
printf("@@@ %d LOG Sender %d finished\n",_pid,taskid);
tasks[taskid].state = Zombie;
printf("@@@ %d STATE %d Zombie\n",_pid,taskid)
}
15.3.2.4. Receiver Process (Runner Task)¶
The receiver process uses the scenario configuration to determine its behaviour. It has the responsibility to trigger the start semaphore to allow either itself or the sender to start. The start semaphore corresponds to either the send or receive semaphore, depending on the scenario. The receiver acquires the receive semaphore before proceeding, and releases the send sempahore when done.
proctype Receiver (byte nid, taskid) {
tasks[taskid].nodeid = nid;
tasks[taskid].pmlid = _pid;
tasks[taskid].prio = rcvPrio;
tasks[taskid].preemptable = false;
tasks[taskid].state = Ready;
printf("@@@ %d TASK Runner\n",_pid,taskid);
if
:: multicore ->
printf("@@@ %d CALL SetProcessor %d\n", _pid, rcvCore);
:: else
fi
Release(startSema); // make sure stuff starts */
/* printf("@@@ %d LOG Receiver Task %d running on Node %d\n",_pid,taskid,nid); */
Obtain(rcvSema);
// If the receiver is higher priority then it will be running
// The sender is either blocked waiting for its semaphore
// or because it is lower priority.
// A high priority receiver needs to release the sender now, before it
// gets blocked on its own event receive.
if
:: rcvPrio < sendPrio -> Release(sendSema); // Release send semaphore for preemption
:: else
fi
if
:: doReceive ->
printf("@@@ %d SCALAR pending %d %d\n",_pid,taskid,tasks[taskid].pending);
if
:: sendTwice && !sentFirst -> Release(sendSema)
:: else
fi
printf("@@@ %d CALL event_receive %d %d %d %d %d recrc\n",
_pid,rcvEvents,rcvWait,rcvAll,rcvInterval,rcvOut);
/* (self, evts, when, what, ticks, out, rc) */
event_receive(taskid,rcvEvents,rcvWait,rcvAll,rcvInterval,rcvOut,recrc);
printf("@@@ %d SCALAR recrc %d\n",_pid,recrc);
if
:: rcvOut > 0 ->
printf("@@@ %d SCALAR recout %d %d\n",_pid,rcvOut,recout[rcvOut]);
:: else
fi
printf("@@@ %d SCALAR pending %d %d\n",_pid,taskid,tasks[taskid].pending);
:: else
fi
Release(sendSema);
printf("@@@ %d LOG Receiver %d finished\n",_pid,taskid);
tasks[taskid].state = Zombie;
printf("@@@ %d STATE %d Zombie\n",_pid,taskid)
}
15.3.2.5. System Process¶
A process is needed that periodically wakes up blocked processes. This is modelling background behaviour of the system, such as ISRs and scheduling. All tasks are visited in round-robin order (to prevent starvation) and are made ready if waiting on other things. Tasks waiting for events or timeouts are not touched. This terminates when all tasks are zombies.
proctype System () {
byte taskid ;
bool liveSeen;
printf("@@@ %d LOG System running...\n",_pid);
loop:
taskid = 1;
liveSeen = false;
printf("@@@ %d LOG Loop through tasks...\n",_pid);
atomic {
printf("@@@ %d LOG Scenario is ",_pid);
printm(scenario); nl();
}
do // while taskid < TASK_MAX ....
:: taskid == TASK_MAX -> break;
:: else ->
atomic {
printf("@@@ %d LOG Task %d state is ",_pid,taskid);
printm(tasks[taskid].state); nl()
}
if
:: tasks[taskid].state == Zombie -> taskid++
:: else ->
if
:: tasks[taskid].state == OtherWait
-> tasks[taskid].state = Ready
printf("@@@ %d STATE %d Ready\n",_pid,taskid)
:: else -> skip
fi
liveSeen = true;
taskid++
fi
od
printf("@@@ %d LOG ...all visited, live:%d\n",_pid,liveSeen);
if
:: liveSeen -> goto loop
:: else
fi
printf("@@@ %d LOG All are Zombies, game over.\n",_pid);
stopclock = true;
}
15.3.2.6. Clock Process¶
A process is needed that handles a clock tick,
by decrementing the tick count for tasks waiting on a timeout.
Such a task whose ticks become zero is then made Ready
,
and its timer status is flagged as a timeout. This terminates when all
tasks are zombies (as signalled by System()
via stopclock
).
proctype Clock () {
int tid, tix;
printf("@@@ %d LOG Clock Started\n",_pid)
do
:: stopclock -> goto stopped
:: !stopclock ->
printf(" (tick) \n");
tid = 1;
do
:: tid == TASK_MAX -> break
:: else ->
atomic{
printf("Clock: tid=%d, state=",tid);
printm(tasks[tid].state); nl()
};
if
:: tasks[tid].state == TimeWait ->
tix = tasks[tid].ticks - 1;
if
:: tix == 0
tasks[tid].tout = true
tasks[tid].state = Ready
printf("@@@ %d STATE %d Ready\n",_pid,tid)
:: else
tasks[tid].ticks = tix
fi
:: else // state != TimeWait
fi
tid = tid + 1
od
od
stopped:
printf("@@@ %d LOG Clock Stopped\n",_pid);
}
15.3.2.7. init Process¶
The initial process outputs annotations for defines and declarations,
generates a scenario non-deterministically and then starts the system, clock
and send and receive processes running. It then waits for those to complete,
and them, if test generation is underway, asserts false
to trigger a
seach for counterexamples:
init {
pid nr;
printf("@@@ %d NAME Event_Manager_TestGen\n",_pid)
outputDefines();
outputDeclarations();
printf("@@@ %d INIT\n",_pid);
chooseScenario();
run System();
run Clock();
run Sender(THIS_NODE,SEND_ID);
run Receiver(THIS_NODE,RCV_ID);
_nr_pr == 1;
#ifdef TEST_GEN
assert(false);
#endif
}
The information regarding when tasks should wait and/or restart
can be obtained by tracking the process identifiers,
and noting when they change.
The spin2test
program does this,
and also produces separate test code segments for each Promela process.
15.3.3. Annotations¶
File: event-mgr-model.pml
Nothing more to say here.
15.3.4. Refinement¶
File: event-mgr-model-rfn.yml
The test-code generated here is based on the test-code generated from the specification items used to describe the Event Manager in the main (non-formal) part of the new qualification material.
The relevant specification item is spec/rtems/event/req/send-receive.yml
found in rtems-central
. The corresponding C test code is
tr-event-send-receive.c
found in rtems
at testsuites/validation
.
That automatically generated C code is a single file that uses a set of deeply
nested loops to iterate through the scenarios it generates.
The approach here is to generate a stand-alone C code file for each scenario
(tr-event-mgr-model-N.c
for N
in range 0..8.)
The TASK
annotations issued by the Sender
and Receiver
processes
lookup the following refinement entries, to get code that tests that the C
code Task does correspond to what is being defined in the model.
Runner: |
checkTaskIs( ctx->runner_id );
Worker: |
checkTaskIs( ctx->worker_id );
The WAIT
and SIGNAL
annotations produced by Obtain()
and
Release()
respectively, are mapped to the corresponding operations on
RTEMS semaphores in the test code.
code content
SIGNAL: |
Wakeup( semaphore[{}] );
WAIT: |
Wait( semaphore[{}] );
Some of the CALL
annotations are used to do more complex test setup
involving priorities, or other processors and schedulers. For example:
HigherPriority: |
SetSelfPriority( PRIO_HIGH );
rtems_task_priority prio;
rtems_status_code sc;
sc = rtems_task_set_priority( RTEMS_SELF, RTEMS_CURRENT_PRIORITY, &prio );
T_rsc_success( sc );
T_eq_u32( prio, PRIO_HIGH );
SetProcessor: |
T_ge_u32( rtems_scheduler_get_processor_maximum(), 2 );
uint32_t processor = {};
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(processor, &cpuset);
Some handle more complicated test outcomes, such as observing context-switches:
CheckPreemption: |
log = &ctx->thread_switch_log;
T_eq_sz( log->header.recorded, 2 );
T_eq_u32( log->events[ 0 ].heir, ctx->runner_id );
T_eq_u32( log->events[ 1 ].heir, ctx->worker_id );
Most of the other refinement entries are similar to those described above for the Chains API.
15.4. Testing the Barrier Mananger¶
Documentation: Barrier Manager section in the RTEMS Classic API Guide.
Model Directory: formal/promela/models/barriers
.
Model Name: barrier-mgr-model
.
The Barrier Manager is used to arrange for a number of tasks to wait on a designated barrier object, until either another task releases them, or a given number of tasks are waiting, at which point they are all released.
All five directives were modelled:
rtems_barrier_create()
rtems_barrier_ident()
rtems_barrier_delete()
rtems_barrier_wait()
rtems_barrier_release()
Barriers can be manual (released only by a call to ..release()
),
or automatic (released by the call to ..wait()
that results in a wait count limit being reached.)
There is no notion of queuing in this manager,
only waiting for a barrier to be released.
This model was developed by a Masters student [Jaskuc22], using the Event Manager as a model. It was added into the QDP produced by the follow-on IV&V activity.
15.4.1. API Model¶
File: barrier-mgr-model.pml
Modelling waiting is much easier than modelling queueing.
All that is required is an array of booleans (waiters
), indexed by process id:
typedef Barrier {
byte b_name; // barrier name
bool isAutomatic; // true for automatic, false for manual barrier
int maxWaiters; // maximum count of waiters for automatic barrier
int waiterCount; // current amount of tasks waiting on the barrier
bool waiters[TASK_MAX]; // waiters on the barrier
bool isInitialised; // indicated whenever this barrier was created
}
The name satisfied
is currently used here for an inline that checks when
a barrier can be released.
Other helper inlines include waitAtBarrier()
and barrierRelease()
.
15.4.2. Behaviour Patterns¶
File: barrier-mgr-model.pml
The overall architecture in terms of Promela processes has processes init
, System
, Clock
, Runner
,
and two workers: Worker1
and Worker2
.
The runner and workers each may perform one or more API calls,
in the following order: create, ident, wait, release, delete.
Scenarios mix and match which task does what.
There are three top-level scenarios:
mtype = {ManAcqRel,AutoAcq,AutoToutDel};
In scenario ManAcqRel
, the runner will do create, release and delete,
with sub-scenarios to check error cases as well as good behaviour,
for manual barriers.
Good behaviour involves one or more workers doing a wait.
The AutoAcq
and AutoToutDel
scenarios look at good and bad uses of automatic barriers.
15.4.3. Annotations¶
File: barrier-mgr-model.pml
Similiar to those used in the Event Manager.
15.4.4. Refinement¶
File: barrier-mgr-model-rfn.yml
Similiar to those used in the Event Manager.
15.5. Testing the Message Manager¶
Documentation: Message Manager section in the RTEMS Classic API Guide.
Model Directory: formal/promela/models/messages
.
Model Name: msg-mgr-model
.
The Message Manager provides objects that act as message queues. Tasks can interact with these by enqueuing and/or dequeuing message objects.
There are 11 directives in total, but only the following were modelled:
rtems_message_queue_create()
rtems_message_queue_send()
rtems_message_queue_receive()
The manager supports two queuing protocols, FIFO and priority-based. Only the FIFO queueing was modelled.
This model was developed by a Masters student [Lyn22], using the Event Manager as a model. It was added into the QDP produced by the follow-on IV&V activity.
Below we focus on aspects of this model that differ from the Event Manager.
15.5.1. API Model¶
File: msg-mgr-model.pml
A key feature of this manager is that not only are messages in a queue, but so are the tasks waiting for those messages. Both task and message queues are modelled as circular buffers, with inline definitions of enqueuing and dequeuing operations.
While the Message Manager allows many queues to be created, the model only uses one.
15.5.2. Behaviour Patterns¶
File: msg-mgr-model.pml
The overall architecture in terms of Promela processes has processes init
, System
, Clock
, Sender
, and two receivers:
Receiver1
and Receiver2
.
The Sender
is the test runner, which performs the queue creation,
releases the start semaphore and then performs a send operation if needed.
The receivers are worker processes.
There are four top level scenarios:
mtype = {Send,Receive,SndRcv, RcvSnd};
Scenarios Send
and Receive
are used for testing erroneous calls.
The SndRcv
scenario fills up queues before the receivers run,
while the RcvSnd
has the receivers waiting before messages are sent.
15.5.3. Annotations¶
File: msg-mgr-model.pml
Similiar to those used in the Event Manager.
15.5.4. Refinement¶
File: msg-mgr-model-rfn.yml
Similiar to those used in the Event Manager.
15.6. Current State of Play¶
The models developed here are the result of an ad-hoc incremental development process and have a lot of overlapping material.
15.6.1. Model State¶
The models were developed by first focusing on simple behavior such as error handling, and then adding in simpler behaviors, until sufficient coverage was acheived. The basic philosophy at the time was not to fix anything not broken.
This has led to the models being somewhat over-engineered,
particularly when it comes to scenario generation.
There is some conditional looping behaviour,
implemented using labels and goto
,
that should really be linearised, using conditionals to skip parts.
It is harder than it should be to understand what each scenario does.
Also the API call models have perhaps a bit too much code devoted to system behaviour.
15.6.2. Model Refactoring¶
There is a case to be made to perform some model refactoring. Some of this would address the model state issues above. Other refactoring would extract the common model material out, to be put into files that could be included. This includes the binary semaphore models, and the parts modelling preemption and waiting while blocked.
15.6.3. Test Code Refactoring¶
During the qualification activity,
a new file tx-support.c
was added to the RTEMS validation testsuite codebase.
This gathers C test support functions used by most of the tests.
The contents of the tr-<modelname>.h
and tr-<modelname>.c
files in particular should be brought in line with tx-support.c
.
Suitable Promela models should also be produced
of relevant functions in tx-support.c
.