9

Let me explain what I mean by data consistency issue. Take following scenario for example

uint16 x,y;
x=0x01FF;
y=x;

Clearly, these variables are 16 bit but if an 8 bit CPU is used with this code, read or write operations would not be atomic. Thereby an interrupt can occur in between and change the value.This is one situation which MIGHT lead to data inconsistency.

Here's another example,

if(x>7) //x is global variable
{
 switch(x)
        {
           case 8://do something
                   break;
           case 10://do something
                   break;
           default: //do default
        }
}

In the above excerpt code, if an interrupt is changing the value of x from 8 to 5 after the if statement but before the switch statement,we end up in default case, instead of case 8.

Please note, I'm looking for ways to detect such scenarios (but not solutions)

Are there any tools that can detect such issues in Embedded C?

EnsieT
  • 91
  • 5
  • 3
    A worse issue with the code you show is that you assign to `y` from `x` before `x` has been initialized. – Some programmer dude Aug 21 '17 at 07:24
  • 1
    I don't think that there are tools available to detect when the interrupt is going to occur just from the source code. – Gaurav Pathak Aug 21 '17 at 07:25
  • You can only use tools wich are made for detecting concurrent access. Then filter the results. However, strictly speaking, the C standard does not guarantee atomic access to anything (if no special mechanisms are used). – Yunnosch Aug 21 '17 at 07:28
  • Thanks, edited the question. @Someprogrammerdude – EnsieT Aug 21 '17 at 07:51
  • Thanks, I understand. But still I'm just looking if someone has done anything about this.. An algorithm, a script or a tool for detection. @GauravPathak – EnsieT Aug 21 '17 at 07:52
  • Thanks, I agree. Can you please let me know the tools for detecting concurrent access..? @Yunnosch – EnsieT Aug 21 '17 at 07:53
  • If your platform doesn't provide atomic operations for 16-bit ints, then **all** operations on 16-bit ints would be a potential cause for concern (on this metric). If interrupts are your concern, then the solution is to minimise the amount of code occurring in the handler. – Oliver Charlesworth Aug 21 '17 at 07:54
  • In my experience atomic memory access are typically tied up with atomic peripheral use, preventing static analyzers from easily reasoning the semantics. I would certainly recommend anotating any accesses requiring atomicity and using libraries to enforce this, such as C11 atomics. I find the best tool is a well-defined synchronization policy, personally I favor defining ownership based upon peripheral interrupt enable and with memory barriers inbetween. Inducing stress-tests to fire off interrupts at abnormal rates is valuable although full coverage is virtually impossible. – doynax Aug 21 '17 at 07:56
  • Thanks. Yes, in this case it is simple. However, there are many scenarios (Global variables, nested conditional statements etc.) which MIGHT lead to data inconsistency. I'm looking for some tool or algorithm that can detect such scenarios. @OliverCharlesworth – EnsieT Aug 21 '17 at 07:57
  • Can you edit your question to include a *concrete* example of the kind of problem you're trying to avoid? (For example, I can't see how nested conditionals are directly related to concurrency problems.) – Oliver Charlesworth Aug 21 '17 at 08:02
  • Thanks for the valuable inputs. I'll keep them in mind. Thing is, the code is already written, reworking would be time taking. I'm looking for a way to detect such scenarios and edit only those parts of code. @doynax – EnsieT Aug 21 '17 at 08:03
  • I think you might use something like a "critical section". You might start implementing the functions `void set16Bit(short int *, char * flag)`, `short int get16Bit(short int *, char * flag)` to be used to set/get the short int value shared with the ISR. In these functions you might use the 8 bits variable (the char * - reading and writing it shall be atomic) as flag to individuate if the variable is in use or not ... such as a simple mutex. https://en.wikipedia.org/wiki/Mutual_exclusion see also: https://en.wikipedia.org/wiki/Test-and-set – Sir Jo Black Aug 21 '17 at 08:18
  • I have edited the question. Thanks for your time @OliverCharlesworth – EnsieT Aug 21 '17 at 08:29
  • 3
    I'm not sure the conditional case is fundamentally different. Essentially **any** variable that is also accessed in your interrupt handler is potentially vulnerable, unless you use dedicated atomic constructs. – Oliver Charlesworth Aug 21 '17 at 08:32
  • Thanks for the suggestion and the links. I'm only looking for ways to detect (not solve). Sorry, I have included that statement in my question now. @SergioFormiggini – EnsieT Aug 21 '17 at 08:35
  • I don't think the C language could, natively, act as you're looking for. I think it's better you indagate if the CPU/MCU you use has similar mechanism. – Sir Jo Black Aug 21 '17 at 08:55
  • I remember that using VxWorks on a DY4 VME CARD I found the Tornado tool that was able to detect the issue you indicate. (An another tool that was able to detect might be Paragadigm debugger, but I'm not sure!) – Sir Jo Black Aug 21 '17 at 09:01
  • 1
    Admittedly this is only repeating @OliverCharlesworth statement, but I try to highlight the core point: The code between and including the "if" and the "switch" will absolutely always be a critical section. No degree of atomicity of access to the variable will help. You would have to use a synchronisation mechanism (semaphore, mutex, or in embedded system often an interrupt lock). Please separate those two aspects of your question. Both aspects will however be detected by a concurrent access detection tool, assuming correct config (which might be harder to do than a thorough code review). – Yunnosch Aug 21 '17 at 09:25
  • 1
    Seems to me like if you're not going to fully rework this delightful code and it's reliance on shared globals then you are leaving yourself open to all sorts of unpredictable behaviour. Grit your teeth, find all variables shared between ISRs and any interruptable code (some ISRs might be interruptable?) and then protect every access to those variables everywhere in the interruptable code. Suggest you make the person who wrote the code do the rework, assuming you can trust them to be rigorous. Or rewrite it properly with only explicitly justified and fully reviewed use of shared globals. – DisappointedByUnaccountableMod Aug 21 '17 at 15:06

2 Answers2

4

It is possible for a static analysis tool that is context (thread/interrupt) aware to determine the use of shared data, and that such a tool could recognise specific mechanisms to protect such data (or lack thereof).

One such tool is Polyspace Code Prover; it is very expensive and very complex, and does a lot more besides that described above. Specifically to quote (elided) from the whitepaper here:

With abstract interpretation the following program elements are interpreted in new ways:

[...]

  • Any global shared data may change at any time in a multitask program, except when protection mechanisms, such as memory locks or critical sections, have been applied

[...]

It may have improved in the long time since I used it, but one issue I had was that it worked on a lock-access-unlock idiom, where you specified to the tool what the lock/unlock calls or macros were. The problem with that is that the C++ project I worked on used a smarter method where a locking object (mutex, scheduler-lock or interrupt disable for example) locked on instantiation (in the constructor) and unlocked in the destructor so that it unlocked automatically when the object went out of scope (a lock by scope idiom). This meant that the unlock was implicit and invisible to Polyspace. It could however at least identify all the shared data.

Another issue with the tool is that you must specify all thread and interrupt entry points for concurrency analysis, and in my case these were private-virtual functions in task and interrupt classes, again making them invisible to Polyspace. This was solved by conditionally making the entry-points public for the abstract analysis only, but meant that the code being tested does not have the exact semantics of the code to be run.

Of course these are non-problems for C code, and in my experience Polyspace is much more successfully applied to C in any case; you are far less likely to be writing code in a style to suit the tool rather than the tool working with your existing code-base.

Clifford
  • 88,407
  • 13
  • 85
  • 165
3

There are no such tools as far as I am aware. And that is probably because you can't detect them.

Pretty much every operation in your C code has the potential to get interrupted before it is finished. Less obvious than the 16 bit scenario, there is also this:

uint8_t a, b;
...
a = b;

There is no guarantees that this is atomic! The above assignment may as well translate to multiple assembler instructions, such as 1) load a into register, 2) store register at memory address. You can't know this unless you disassemble the C code and check.

This can create very subtle bugs. Any assumption of the kind "as long as I use 8 bit variables on my 8 bit CPU, I can't get interrupted" is naive. Even if such code would result in atomic operations on a given CPU, the code is non-portable.

The only reliable, fully-portable solution is to use some manner of semaphore. On embedded systems, this could be as simple as a bool variable. Another solution is to use inline assembler, but that can't be ported cross platform.

To solve this, C11 introduced the qualifier _Atomic to the language. However, C11 support among embedded systems compilers is still mediocre.

Lundin
  • 195,001
  • 40
  • 254
  • 396