Any systematic way to avoid "reentry" problem? (embedded system)

Question

We are using C to build a system on ARM core (i.e. an embedded system). The question is: how can we avoid reentry problem in a formal way so that we are confident all reentry bugs are removed. This may not be a practical wish but surely important for any system, I guess.

Just for the discussion, I guess drawing UML diagram or have a complete state machine would be a good start (but how to generate it AFTER the whole system is developed?). Any suggestions on how to use state machine / UML diagram to do the analysis?

Answer 1

Quick fix, if you suspect something:

int some_func(int x, int y)
{
    static volatile int do_not_enter_twice = 0;
    assert(!(do_not_enter_twice++));

    /* some_func continued */

    do_not_enter_twice--;
    return whatever;
}

Longer answer:
Use some tool to make a call graph and continue manually from there.

Answer 2

I'm not exactly sure about the problem you want to solve, but let me make an educated guess.

The first point is to identify the functions that could be problematic. A reentry happens either by recursive calls, which may go over several nested calls and even be hidden by callbacks/dependency injection, or by functions that are used within multiple threads.

You could draw a directed call graph. Say function A calls B and C, function B calls D, E and F, function C calls nothing, and so on. Draw this for each thread when multithreading. If there are cycles in the graph, then all functions making this cycle need to be reentry-safe. You can ignore subbranches in this case. Functions that are used in multiple threads need to be safe, too, but now including all subbranches, because you do not exactly know where each thread currently is. Things will get complex and complicated when locks are used, so let us ignore this for now.

This step can surely be automated by code analysis tools.

Now that the functions are identified,

• Functions that only depend on their function-local data are usually safe. This is one of the nice properties of functional programming.
• Functions that depend on external data (not within the function scope) should be closely examined, it is especially important to know when and where the external data is changed.
• Functions that change external data should raise a red flag and activate a loud alarm siren, especially when multithreading.

Answer 3

I'd do 2 things to check your code. Thorough group code-review (with the goal of finding reentrance mistakes only, not style or other errors). Secondly, a practical attack on problems.

For example:

int myfunction(int x, int y) {
    REENTRANCE_CHECK;
    ... body of function
}

Now you can #define REENTRANCE_CHECK to be either be empty (for production) or some code that checks the function is never re-entered. Run your tests (if you don't have tests, then run it on your device with the debugger attached) with these checks enabled, and see if anything drops off.

Similarly, you can add debug logic to detect incorrect updates to global state. Write code that uses locks (which assert if they're acquired when already held.

Something like this:

int my_global;
DEFINE_GLOBAL_LOCK(my_global);

void my_dangerous_function() {
    ...
    LOCK_GLOBAL(my_global);
    .. some critical section of code that uses my_global.
    UNLOCK_GLOBAL(my_global);
    ...
}

Again, DECLARE_GLOBAL_LOCK, LOCK_GLOBAL and UNLOCK_GLOBAL can be either #defined to be real locking code (which of course you'll have to write) for testing, and for production they can be #defined to nothing.

This approach only works if you find and wrap all accesses to your global state, but that's easy with a search.

Answer 4

A tool that can compute huge call graphs is the DMS Software Reengineering Toolkit and its C front end. The C front end is used to parse the C code; DMS has machinery built in to compute control and data flow analysis, points-to analysis and extract call-direct and call-indirect-thru-pointer facts

DMS has been used to build call graphs for C source code systems of 35 million lines of C code (= 250,000 functions), and then to extract information from that call graph. A key issue when building large graphs like this is to compute points-to information as accurately as practical (there are hard theory limitations on doing this perfectly) so that indirect function calls are conservatively targeted to a minimal number of false positive targets.

In your case, the information to extract is, as other authors indicate, "is there a cycle?" in this call graph.

At this scale, you don't want to do this by hand, and you need to re-do it every time you get ready for a production build. So mechanizing the check would make a lot of sense.