( transcript for https://www.imagix.com/apps/Tasking_Analysis.mp4 )

Analyzing Concurrency Control in C and C++ Source Code

[0:00]  This demo will introduce Imagix 4D's analysis of multi-tasking, or multi-threaded, software.  We'll use Imagix 4D to understand how variables are shared between tasks in multi-tasking systems, and to identify potential problems involving concurrency and variable protection.  To make the demo easy to follow, I'll use an extremely small and extremely simple project.  This way, in the graphs and the source code, you'll be able to follow tasking activities that normally you could only understand through deep task analysis.

[0:35]  Let's look at the code...  There are two root functions here, having to do with engine activities...  And here are two interrupt handlers.  These four functions could be called from the operating system.  For example, the first two functions would be called to start a task.  Or an interrupt could occur which would result in one of the handlers being run.

In setting up this project for task analysis, we specified four tasks, each based on one of these as a root function.  The corresponding task then consists of that root function, and all the functions and variables that it directly or transitively calls, sets or reads.

These four could run concurrently, so they are like tasks in an operating system.  The whole purpose of Imagix 4D's task flow reports and the related advanced analysis is to determine what is going on that could potentially cause race conditions or deadlock conditions between the tasks.

[1:45]  A race condition occurs when a global variable is used by multiple tasks, and the tasks overwrite each others' values.  A deadlock condition occurs when some task waits for another task, and that second task is also waiting in return -- the whole system locks up because the tasks keep waiting for each other. 

In an embedded world, these concurrency problems can occur between tasks in real-time, multi-tasking operating systems.  But these conditions can also occur between threads. Any modern operating system today, whether it's Windows or Android or whatever, has the ability to run several threads within the same program.  Different threads can access the same global variables, which could potentially cause concurrency problems if they're not protected.  So in this way, multi-threaded software faces the same issues as multi-tasking systems.

And it's to address these issues that Imagix 4D's tasking analysis has been created, the Task Flow Check reports in particular. In this demo, we'll examine some of the main reports and discuss their purpose.

[2:50]  Let's look at the graph to get some perspective on the code...  We'll select one of the variables, which are green trapezoids, as opposed to blue rectangles representing functions.  We can see that 'motorLink' is used both by one of the engine tasks, as well as by one of the interrupt handlers.  So there could be a conflict if that's not well coordinated.

To study this, we'll run the Variables Set in Multiple Tasks report, which provides insight on the uses of global variables across different tasks.  Report options allow selection of a usage type, meaning a pattern of how a variable is shared between tasks.  We'll start off with Usage Type set to "Show Set or Read in mMltiple Tasks".  With this setting, any variable that is set or read in at least two tasks will be listed.

We already know from the graph that 'motorLink' is used by two tasks.  And so it shows up in the report.  The report indicates the two tasks where 'motorLink' is used.  And for each task, the report has a detailed entry about each use of that variable within the task.

The letter at the beginning of the entry indicates whether the variable is set or read.  In this case, we can quickly see that the task 'task_direct_motor' is only setting 'motorLink', while the handler task is both setting it and reading it.  We can also see the particular functions within each task that are accessing the variable.  And we can see the line number and file where that occurs.

[4:25]  Some of this information is clear from the code, which we can easily access by double clicking on the entry.  Here we can see that 'motorLink' is being set at line 24 of 'sci_default_handler'.

But determining the task context of 'motorLink' at this point could require quite a bit of study.  And even more difficult to determine would be the protection status of 'motorLink' as it's being read at this line.  

Let's talk about this for a second.  The way to avoid multiple tasks writing to a variable at the same time and then overwriting each other's value, is to employ protection mechanisms.  These protection schemes can either be interrupt protection or might be semaphores, mutex's, whatever is offered by the operating system where the code runs.

In Imagix 4D, we call these protection mechanisms "critical regions".  For this project, we have defined two critical regions, so that the task flow analysis knows about the two pairs of interrupts used in the code.  The one, which we've named 'Int1', uses 'DisableInterrupt1' and 'EnableInterrupt1'.  And the second, 'Int2', employs 'DisableInterrupt2' and 'EnableInterrupt2'.

So now, taking a further look at the report, you'll notice that there are multiple entries for the same line of code.  For example, here is 'motorLink' being set at line 24 in the 'sci_default_rxhandler'.  One entry indicates that the variable access is protected by the interrupt pair we've labeled 'Int2'.  But protection by the 'Int1' interrupt pair is labeled P/U, meaning it's ambiguous.  We can understand what this represents by again looking at the source code.

[6:05]  Here's the line 24 that's being referenced in the report.  Let's look at its context.  We have two different pairs of interrupts.  A 'DisableInterrupt1' call will turn off 'Int1', and then 'EnableInterupt1' will allow it again.  So from here to here, it looks like 'motorLink' is protected against interrupts.

However, looking a little closer, we also see there's an if-then-else in here, and the else branch enables 'Int1' earlier.  So when line 24 is reached, there is an ambiguous situation.  If the first branch of the if-then-else is taken, 'motorLink' is still protected, but if execution goes through the second branch, protection against interrupts is no longer in effect.

We can see that the second critical region is invoked at line 12 and released at line 27, so the variable read at line 24 is always fully protected.  Therefore, the protection status is different with respect to 'Int1' and 'Int2', and that's why the report had two separate entries.

Let's look at a different example, 'rtosL1' being set at line 17.  Because this only occurs in the branch where 'EnableInterrupt1' is not called, it is always protected for both 'Int1' and 'Int2'...  Because protection of this by both critical regions is therefore the same, the entries in the report are combined, showing that this variable read in this task is protected by both critical regions.

[7:30]  So the Variables Set in Multiple Tasks report provides a lot of detail about concurrency and how variables are shared between tasks.  To get more of a summary overview, we can look at the Variable Flow Between Tasks report.

In this report, you get a row for each variable, and a column for each task.  You can see how the variables are used in general.  Each cell entry can represent multiple lines in the source code. 

Let's look at how the task activity for 'motorLink' is summarized.  Here we can see 'motorLink' being used in 'sci_default_handler'.  The leading SR indicates that 'motorLink' is first set and then read within the task.  The P indicates that this variable usage is fully protected by at least one of the critical regions that have been defined.  You may recall that while the protection via 'Int1' was ambiguous, 'motorLink' was protected by 'Int2' in all paths through the code.  The P reflects that.

In the entry for 'rtosL1', you can see a P/U entry for 'uart_rtos_handler'.  This indicates more complete ambiguity, that while there are come paths through the code where the variable is protected, there are others where the variable is not protected by any of the interrupt protection pairs.

There is one piece of information here that is unique to the Variable Flow Between Tasks report.  That's these F1 entries.  When potential feedback loops exist in the code, an F followed by a number is used to indicate which task and variable usage corresponds to a given feedback loop.  

[9:07]  Another tool for obtaining a high level perspective on multi-tasking, concurrency and data sharing is the UML Task Collaboration diagram.

The diagram gives you a way to visually explore how variables are shared between tasks.  The blue is again used to represent tasks and functions, and the green to show the variables being used.  Variables are combined into these shared data boxes based on which tasks are using them.  So 'motorLink', which is used by the first two tasks, is by itself, while the other three globals, used by three of the tasks, are combined.  As throughout Imagix 4D, the orange-ish lines represent variables being read, while the aqua-colored lines show variables being set.  And these fainter lines represent Protected variable use.  From the bold lines, you see that most of the variables can be accessed outside of interrupt protection.

What's particularly useful in this diagram is the filter for focusing in on particular usage...  For example, we might start by visualizing the variable usage with respect to the critical region 'Int2'...  From the reduction in bold lines, we immediately see that the protection provided by 'Int2' is pretty complete.   We can then further reduce the displayed relationships to show just the unprotected variable usage.

[10:34]  This diagram has a complementary report for examining the variable usage that remains after our filtering.  The result is presented in the same format as the original Variables Set in Multiple Tasks report.  But this report is restricted to just the data sharing currently displayed in the diagram.  In displaying details about this ambiguous set at line 89, we have quickly identified the one potential hole in the protection under critical region 'Int2'.

In actual use, you might typically use these tools in the opposite order.  You'd start with the Variable Flow Between Tasks report and/or the Task Collaboration Diagram to get an overview.  Then, you'd dive down into the Variables Set in Multiple Tasks to explore in more detail specifics about intricacies of the protection coverage, feedback loops, etc.

[11:27]  Imagix 4D has several reports covering other aspects of multi-tasking and concurrency.  Let's look at...  the Mismatched Critical Regions.  This shows issues of imbalance in the opening and closing of critical region protection, and of ambiguity about whether specific lines are covered.

The report contains a section for each of the critical regions that you have defined.  These two subsections, Missing End of Critical Region and Missing Start of Critical Region, point to particular imbalances in the entry and exit of the lock/unlock operations.

Let's look at this first item.  There's an enable interrupt at line 25, without a matching disable interrupt.  The report suggests that maybe the disable interrupt belongs at line 22.  We'll jump into the code by double-clicking.

You might notice that this is the same issue we explored earlier, where interrupt protection became unbalanced within the if-then-else logic.  The unmatched end of the critical region is reported as occurring at line 25.  This indicates that line 25 can be reached through at least some path where the interrupt protection in not currently disabled.  The report's entry that the missing start should be at line 22 is merely a suggestion or a guess.  But it steers us to where the issue is, the enable interrupt at line 21.

At this point, we understand how and where this mismatch occurs.  We can decide whether or not this is a design or programming error, and we can make whatever change is appropriate to the code.

[13:03]  Imagix 4D has additional reports dealing with other aspects of multitasking and concurrency.  Out of Step Variables identifies global and static variables whose calculation order is read-then-set. In task-based software, this can cause stale values for a variable being used in calculations.  Reentrant Functions examines functions called from multiple tasks.  To the extent that they use global, static or static-local variables, calling them can result in unanticipated interactions with other tasks.  These two Event reports help identify possible deadlock conditions that can occur while using wait, post and clear event functions to start and halt the execution of specific tasks.

Overall, Imagix 4D's capabilities for exploring issues of multi-tasking and multi-threading are quite extensive.  You can learn more about them in our on-line user guide, and evaluate them on your own code by downloading a copy of Imagix 4D from our website.