State Machine with no function pointer

Question

I have implemented a complex state machine with numerous state transitions for a safety SIL 4 system. The back bone for this implementation was done using function pointers. When all was sailing smoothly, the V&V opposed the use of function pointers in a SIL 4 system. Reference- Rule 9 NASA.Misra C 2004 however doesnt say that function pointers cant be used.

Is there any other way to implement complex state machines without any function pointers?

Answer 1

First of all, that NASA document is not canon. Start by asking which law/directive/standard/requirement/document that enforces you to follow the NASA document. If it isn't enforced anywhere (which seems very likely, even at NASA itself), you are not obliged to follow it and you can dismiss the whole thing.

Failing to dismiss the nonsense as nonsense, you can use the usual procedure when hitting a wall with safety standards: the solution is always to document in detail how the stated rule doesn't make sense, and slap them in the face with their own methodology.

So rather than abandoning function pointers, ensure that they are used in a safe manner, through the methods described below.

---

Since all safety-related design boils down to risk assessment, you'll always have:

Error -> Cause -> Hazard -> Safety measure

With the given (poor) rationale from the NASA document you would justify the safety measure "avoid function pointers" with something like:

1. Wrong code executed -> Corrupt function pointer -> Runaway code/illegal op code

2. Stack overflow -> Function pointer recursion -> Memory corruption

3. Confused programmer -> Function pointer syntax -> Unintended program functionality

That is all rather vague and a questionable risk assessment, but this is what the NASA document boils down to.

Instead of "avoid function pointers" for the above 3 listed hazards, I would suggest using the following safety measures instead:

1. Defensive programming and assertions.
2. Defensive programming and assertions. Educate programmers.
3. Use typedef. Educate programmers.

Defensive programming and assertions

• For the state machine, ensure that the number of states (items in the enum) corresponds to the number of handlers (items in the array of function pointers). Simply static assert the last item in the enum (called STATES_N or some such) against sizeof(func_pointer_array)/sizeof(*func_pointer_array).
• The function pointer array must be allocated in ROM with error detection/CRC. Other safety requirements will point to this need, easiest way to solve is use a microcontroller with "ECC flash". Back in the days before ECC, you would have to calculate a CRC on the whole ROM instead, which is complex and tedious, but can be done too. You can also create an identical ROM mirror image of the table to protect against flash corruption.
• The only function pointer which your state machine code is allowed to call, is one obtained from this safe function pointer array. Given that your state machine call looks like STATE_MACHINE[i](); where STATE_MACHINE is the array of function pointers, then simply add a run-time check of i to ensure that it is always valid.
• For other function pointers in your program, such as callback functions, ensure that they are initialized to point at valid functions in ROM. Use const pointers if possible (the pointer itself is read-only). If you need to re-assign them in runtime, ensure that they are pointing at a valid function before invoking them.

The above kind of state machine is idiomatic and extremely safe, likely much safer than ordinary function calls elsewhere in your code. You'll of course have to ensure that the state transits are done in a safe and reasonable manner, but that's not something that concerns the function pointers.

Avoiding recursion

This is mainly about educating programmers not to use it, function pointers or no function pointers (seems this would have prevented the Toyota bug).

It is neither hard to spot nor avoid recursion, so half-decent code review formalities should be enough to prevent it. No veteran embedded systems programmer, regardless of safety-critical systems experience, will approve of code containing recursion.

You could/should set an in-house design rule stating that all safety-related code must be reviewed and approved by a veteran C programmer with n years of experience of safety-critical program design.

In addition, you should also check for recursion with static analyser tools (even if they aren't able to detect recursion through function pointers). If you have a static analyser that conforms to any version of MISRA-C, this is included.

Regarding unintended recursion, it is avoided with the above mentioned defensive programming methods.

Confusig function pointer syntax

The function pointer syntax in C can admittedly be very confusing, just look at

int (*(*func)[5])(void);

or some other ridiculous example. It can be solved by always enforcing a typedef for function pointer types.

(Reference: Les Hatton, Safer C, p184 "From a safety-related viewpoint, the simple answer is that they should never be allowed outside the typedef mechanism.")

There are two different ways you can typedef them, I prefer this:

typedef int func_t (void);
func_t* fptr;

Because this doesn't hide the pointer behind a typedef, which is generally bad practice. But if you feel more comfortable with the alternative

typedef int (*func_t) (void);
func_t fptr;

then that's ok practice too.