Back to the Basics – Practical Embedded Coding Tips: Part 1

Virtually every embedded system uses interrupts; many supportmultitasking or multithreaded operations. These sorts of applicationscan expect the program's control flow to change contexts at just aboutany time. When that interrupt comes, the current operation is put onhold and another function or task starts running. What happens iffunctions and tasks share variables? Disaster surely looms if oneroutine corrupts the other's data.

By carefully controlling how data is shared, we create reentrant functions, those that allow multiple concurrent invocations that do notinterfere with each other. The word “pure” is sometimes usedinterchangeably with “reentrant.”

Reentrancy was originally invented for mainframes, in the days whenmemory was a valuable commodity. System operators noticed that a dozenor hundreds of identical copies of a few big programs would be in thecomputer's memory array at any time. At the University of Maryland, myold hacking grounds, the monster Univac 1108 had one of the earlyreentrant FORTRAN compilers.

It burned up a breathtaking (for those days) 32 kW of system memory,but being reentrant, it required only 32 k even if 50 users wererunning it. Everyone executed the same code, from the same set ofaddresses. Each person had his or her own data area, yet everyonerunning the compiler quite literally executed identical code. As theoperating system changed contexts from user to user it swapped dataareas so one person's work didn't affect any other. Share the code, butnot the data.

In the embedded world a routine must satisfy the followingconditions to be reentrant:

Rule # 1. It uses all sharedvariables in an atomic way, unless each is allocated to a specificinstance of the function.
Rule # 2. It does not callnonreentrant functions.
Rule 3. It does not use thehardware in a nonatomic way.

Atomic Variables
Both the first and last rules use the word “atomic,” which comes fromthe Greek word meaning “indivisible.” In the computer world “atomic”means an operation that cannot be interrupted. Consider the assemblylanguage instruction:

mov ax,bx

Since nothing short of a reset can stop or interrupt thisinstruction it's atomic. It will start and complete without anyinterference from other tasks or interrupts. The first part of Rule #1 requires the atomic use ofshared variables. Suppose two functions each share the global variable”foobar.” Function A contains:

temp=foobar; temp+=1; foobar=temp;

This code is not reentrant, because foobar is used nonatomically.That is, it takes three statements to change its value, not one. Thefoobar handling is not indivisible; an interrupt can come between thesestatements, switch context to the other function, which then may alsotry and change foobar.

Clearly there's a conflict, foobar will wind up with an incorrectvalue, the autopilot will crash, and hundreds of screaming people willwonder, “Why didn't they teach those developers about reentrancy?”Suppose, instead, function A looks like:

foobar+=1;

Now the operation is atomic, an interrupt will not suspendprocessing with foobar in a partially changed state, so the routine isreentrant.

Except . . . do you really know what your C compiler generates? Onan x86 processor the code might look like:

movax,[foobar]
incax mov[foobar],ax

which is clearly not atomic, and so not reentrant. The atomicversion is:

inc[foobar]

The moral is to be wary of the compiler; assume it generates atomiccode and you may find 60 Minutes knocking at your door.

The second part of the first reentrancy rule reads ” . . . unlesseach is allocated to a specific instance of the function.” This is anexception to the atomic rule that skirts the issue of shared variables.

An instance is a path through the code. There's noreason a single function can't be called from many other places. In amultitasking environment it's quite possible that several copies of thefunction may indeed be executing concurrently. (Suppose the routine isa driver that retrieves data from a queue; many different parts of thecode may want queued data more or less simultaneously.) Each executionpath is an “instance” of the code. Consider:

intfoo;
void some_function(void){ foo++; }

foo is a global variable whose scope exists beyond that of thefunction. Even if no other routine uses foo, some_function can trashthe variable if more than one instance of it runs at any time. C andC++ can save us from this peril. Use automatic variables. That is,declare foo inside of the function. Then, each instance of the routinewill use a new version of foo created from the stack, as follows:

voidsome_function(void){
int foo; foo++; }

Another option is to dynamically assign memory (using malloc), againso each incarnation uses a unique data area. The fundamental reentrancyproblem is thus avoided, as it's impossible for multiple instances tostamp on a common version of the variable.

Two More Rules
The rest of the rules are very simple.

Rule #2 tells us a callingfunction inherits the reentrancy problems of the callee. That makessense, if other code inside the function trashes shared variables; thesystem is going to crash.

Using a compiled language, though, there's an insidious problem. Areyou sure—really sure—that the runtime package is reentrant? Obviouslystring operations and a lot of other complicated things use runtimecalls to do the real work. An awful lot of compilers also generateruntime calls to do, for instance, long math, or even integermultiplications and divisions.

If a function must be reentrant, talk to the compiler vendor toensure that the entire runtime package is pure. If you buy softwarepackages (like a protocol stack) that may be called from severalplaces, take similar precautions to ensure the purchased routines arealso reentrant.

Rule #3 is a uniquelyembedded caveat. Hardware looks a lot like a variable, if it takes morethan a single I/O operation to handle a device, reentrancy problems candevelop.

Consider Zilog's SCC serial controller. Accessing any of thedevice's internal registers requires two steps: first write theregister's address to a port, then read or write the register from thesame port, the same I/O address. If an interrupt comes between settingthe port and accessing the register another function might take overand access the device. When control returns to the first function theregister address you set will be incorrect.

Keeping Code Reentrant
What are our best options for eliminating nonreentrant code? The firstrule of thumb is to avoid shared variables. Globals are the source ofno end of debugging woes and failed code. Use automatic variables ordynamically allocated memory.

Yet globals are also the fastest way to pass data around. It's notentirely possible to eliminate them from real time systems. Therefore,when using a shared resource (variable or hardware) we must take adifferent sort of action.

The most common approach is to disable interrupts duringnonreentrant code. With interrupts off the system suddenly becomes asingle-process environment. There will be no context switches. Disableinterrupts, do the nonreentrant work, and then turn interrupts back on.

Most times this sort of code looks like:

long i;
void do_something(void){    disable_interrupts();
    i+=0x1234;     enable_interrupts(); }

This solution does not work. If do_something() is a generic routine,perhaps called from many places, and is invoked with interruptsdisabled, it returns after turning them back on. The machine's contextis changed, probably in a very dangerous manner.

Don't use the old excuse “yeah, but I wrote the code and I'mcareful. I'll call the routine only when I know that interrupts will beon.” A future programmer probably does not know about this restriction,and may see do_something() as just the ticket needed to solve someother problem . . . perhaps when interrupts are off.

Better code looks like:

long i; void do_so mething(void){     push interruptstate;
   disable_interrupts();
    i+=0x1234;     pop interruptstate;
}

Shutting interrupts down does increase system latency, reducing itsability to respond to external events in a timely manner. A kinder,gentler approach is to use a semaphore to indicate when a resource isbusy. Semaphores are simple on-off state indicators whose processing isinherently atomic, often used as “in-use” flags to have routines idlewhen a shared resource is not available.

Nearly every commercial real time operating system includessemaphores; if this is your way of achieving reentrant code, by allmeans use an RTOS. Don't have an RTOS? Sometimes I see code thatassigns an in-use flag to protect a shared resource, like this:

while (in_use);         //wait tillresource free
in_use=TRUE;        //set resource busy
Donon-reentrant     stuff in_use=FALSE;      //set resource available

If some other routine has access to the resource it sets in_usetrue, causing this routine to idle until in_use gets released. Seemselegant and simple, but it does not work. An interrupt that occursafter the while statement will preempt execution. This routine feels itnow has exclusive access to the resource, yet hasn't had a chance toset in_use true.

Some other routine can now get access to the resource. Someprocessors have a test-and-set instruction, which acts like the in-useflag, but that is interrupt-safe. It'll always work. The instructionlooks something like:

Tset variable  ; if  (variable==0){
                      ;       variable=1;                       ;       returns TRUE;}                       ;  else {returns FALSE;}

If you're not so lucky to have a test-and-set, try the following:

loop:      mov    al,0            ; 0 means “in use”              xchg    al,variable             cmp      al,0             je         loop             ; loop ifin use

If al = 0, we swapped 0 with zero; nothing changed, but the codeloops since someone else is using the resource. If al = 1, we put a 0into the “in use” variable, marking the resource as busy. We fall outof the loop, now having control of the resource. It'll work every time.

Recursion
No discussion of reentrancy is complete without mentioning recursion,if only because there's so much confusion between the two. A functionis recursive if it calls itself. That's a classic way to removeiteration from many sorts of algorithms.

Given enough stack space this is a perfectly valid, though tough todebug, way to write code. Since a recursive function calls itself,clearly it must be reentrant to avoid trashing its variables. So allrecursive functions must be reentrant, but not all reentrant functionsare recursive.

To read Part 2 go to Asynchronous hardware/firmware .
To read Part 3 , go to Dealing with Interrupt Latency
To read Part 5 , go to Using your C-compiler to minimize code size
To read Part 6 go to Writing compiler-friendly C-code

JakobEngblom (jakob@virtutech.com)is technical marketing manager atat Virtutech.He has a MSc in computer science and a PhD in Computer Systems fromUppsala University, and hasworked with programming tools and simulation tools for embedded andreal-time systems since 1997. 
He was a contributor of material to “ The Firmware Handbook,” editedby Jack Ganssle, upon which this series of articles was based andprintedwith permission from Newnes, a division of Elsevier.Copyright 2008.  Forother publications by Jakob Engblom, see www.engbloms.se/jakob.html.

1 thought on “Back to the Basics – Practical Embedded Coding Tips: Part 1

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.