We work at that fuzzy interface between hardware and software, which creates additional problems due to the interactions of our code and the device. Some cause erratic and quite impossible-to-diagnose crashes that infuriate our customers.
The worst bugs of all are those that appear infrequently, that can't be reproduced. Yet a reliable system just cannot tolerate any sort of defect, especially the random one that passes our tests, perhaps dismissed with the "ah, it's just a glitch" behavior.
Potential evil lurks whenever hardware and software interact asynchronously. That is, when some physical device runs at its own rate, sampled by firmware running at some different speed.
I was poking through some open-source code and came across a typical example of asynchronous interactions. The RTEMS real time operating system provided by OAR Corporation is a nicely written, well organized product with a lot of neat features.
But the timer handling routines, at least for the 68302 distribution, are flawed in a way that will fail infrequently but possibly catastrophically. This is just one very public example of the problem I constantly see buried in proprietary firmware.
The code is simple and straightforward, and looks much like any other timer handler.
int
timer_hi;
interrupt timer(){
++timer_hi;}
long read_timer(void){
unsigned int low,
high;
low
=inword(hardware_register);
high=timer_hi;
return
(high<<16 + low);}
There's an interrupt service routine invoked when the 16 bit hardware timer overflows. The ISR services the hardware, increments a global variable named timer_hi, and returns.
Therefore, timer_hi maintains the number of times the hardware counted to 65536. Function read_timer returns the current "time" (the elapsed time in microseconds as tracked by the ISR and the hardware timer). It, too, is delightfully free of complications.
Like most of these sorts of routines it reads the current contents of the hardware's timer register, shifts Timer_hi left 16 bits, and adds in the value read from the timer. That is, the current time is the concatenation the timer's current value and the number of overflows.
Suppose the hardware rolled over 5 times, creating five interrupts. timer_hi equals 5. Perhaps the internal register is, when we call read_timer, 0x1000. The routine returns a value of 0x51000. Simple enough and seemingly devoid of problems.
Race Conditions
But let's think about this more carefully. There are really two things
going on at the same time. Not concurrently, which means "apparently at
the same time," as in a multitasking environment where the RTOS doles
out CPU resources so all tasks appear to be running simultaneously.
No, in this case the code in read_timer executes whenever called, and the clock-counting timer runs at its own rate. The two are asynchronous.
A fundamental rule of hardware design is to panic whenever asynchronous events suddenly synchronize. For instance, when two different processors share a memory array there's quite a bit of convoluted logic required to ensure that only one gets access at any time. If the CPUs use different clocks the problem is much trickier, since the designer may find the two requesting exclusive memory access within fractions of a nanosecond of each other.
This is called a "race" condition and is the source of many gray hairs and dramatic failures.One of read_timer's race conditions might be:
It reads the hardware and gets, let's say, a value of 0xffff.
Before having a chance to retrieve the high part of the time from variable timer_hi, the hardware increments again to 0x0000.
The overflow triggers an interrupt. The ISR runs timer_hi is now 0x0001, not 0 as it was just nanoseconds before.
The ISR returns, our fearless read_timer routine, with no idea an interrupt occurred, blithely concatenates the new 0x0001 with the previously read timer value of 0xffff, and returns 0x1ffff—a hugely incorrect value.
Alternatively, suppose read_timer is called during a time when interrupts are disabled—say, if some other ISR needs the time. One of the few perils of writing encapsulated code and drivers is that you're never quite sure what state the system is in when the routine gets called. In this case:
read_timer starts. The timer is 0xffff with no overflows.
Before much else happens it counts to 0x0000. With interrupts off the pending interrupt gets deferred.
read_timer returns a value of 0x0000 instead of the correct 0x10000, or the reasonable 0xffff.
So the algorithm that seemed so simple has quite subtle problems, necessitating a more sophisticated approach. The RTEMS RTOS, at least in its 68 k distribution, will likely create infrequent but serious errors.
Sure, the odds of getting a misread are small. In fact, the chance of getting an error plummets as the frequency we call read_timer decreases. How often will the race condition surface? Once a week? Monthly?
Many embedded systems run for years without rebooting. Reliable products must never contain fragile code. Our challenge as designers of robust systems is to identify these sorts of issues and create alternative solutions that work correctly, every time.
The problem will be much worse if an interrupt causes a context switch after disabling the counting. Turning interrupts off during this period will eliminate unwanted tasking, but increases both system latency and complexity.
I just hate disabling interrupts, system latency goes up, and sometimes the debugging tools get a bit funky. When reading code a red flag goes up if I see a lot of disable interrupt instructions sprinkled about. Though not necessarily bad, it's often a sign that either the code was beaten into submission (made to work by heroic debugging instead of careful design), or there's something quite difficult and odd about the environment.
Another solution is to read the timer_hi variable, then the hardware timer, and then reread timer_hi. An interrupt occurred if both variable values aren't identical. Iterate until the two variable reads are equal. The upside: correct data, interrupts stay on, and the system doesn't lose counts.
The downside: in a heavily loaded, multitasking environment, it's possible that the routine could loop for rather a long time before getting two identical reads. The function's execution time is nondeterministic. We've gone from a very simple timer reader to somewhat more complex code that could run for milliseconds instead of microseconds.
Another alternative might be to simply disable interrupts around the reads. This will prevent the ISR from gaining control and changing timer_hi after we've already read it, but creates another issue.
We enter read_timer and immediately shut down interrupts. Suppose the hardware timer is at our notoriously-problematic 0xffff, and timer_hi is zero. Now, before the code has a chance to do anything else, the overflow occurs. With context switching shut down we miss the rollover.
The code reads a zero from both the timer register and from timer_hi, returning zero instead of the correct 0x10000, or even a reasonable 0x0ffff. Yet disabling interrupts is probably indeed a good thing to do, despite my rant against this practice.
With them on there's always the chance our reading routine will be suspended by higher priority tasks and other ISRs for perhaps a very long time. Maybe long enough for the timer to roll over several times. So let's try to fix the code. Consider the following:
long
Read_timer(void){
unsigned int low,
high;
push_interrupt_state;
disable_interrupts;
low=inword(Timer_register);
high=timer_hi;
if(inword(timer_overflow))
{++high;
low=inword(timer_register);}
pop_interrupt_state;
return
(((ulong)high)<<16 +
(ulong)low);
}
We've made three changes to the RTEMS code. First, interrupts are off, as described. Second, you'll note that there's no explicit interrupt re-enable. Two new pseudo-C statements have appeared, which push and pop the interrupt state. Trust me for a moment—this is just a more sophisticated way to manage the state of system interrupts.
The third change is a new test that looks at something called "timer_overflow," an input port that is part of the hardware. Most timers have a testable bit that signals an overflow took place. We check this to see if an overflow occurred between turning interrupts off and reading the low part of the time from the device. With an inactive ISR variable timer_hi won't properly reflect such an overflow.
We test the status bit and reread the hardware count if an overflow had happened. Manually incrementing the high part corrects for the suspended ISR. The code then concatenates the two fixed values and returns the correct result—every time. With interrupts off we have increased latency. However, there are no loops; the code's execution time is entirely deterministic.
Other RTOSes
Unhappily, race conditions occur anytime we're need more than one read
to access data that's changing asynchronously to the software. If
you're reading X and Y coordinates, even with just 8 bits of
resolution, from a moving machine there's some peril they could be
seriously out of sync if two reads are required. A ten-bit encoder
managed through byte-wide ports potentially could create a similar
risk.
Having dealt with this problem in a number of embedded systems over the years, I wasn't too shocked to see it in the RTEMS RTOS. It's a pretty obscure issue, after all, though terribly real and potentially deadly.
For fun I looked through the source of uC/OS, another very popular operating system whose source is on the net (see www.ucos-ii.com). uC/OS never reads the timer's hardware. It only counts overflows as detected by the ISR, as there's no need for higher resolution. There's no chance of an incorrect value.
Some of you, particularly those with hardware backgrounds, may be clucking over an obvious solution I've yet to mention. Add an input capture register between the timer and the system; the code sets a "lock the value into the latch" bit, then reads this safely unchanging data. The register is nothing more than a parallel latch, as wide as the input data.
A single clock line drives each flip-flop in the latch, when strobed it locks the data into the register. The output is fed to a pair of processor input ports.
When it's time to read a safe, unchanging value the code issues a "hold the data now" command, which strobes encoder values into the latch. So all bits are stored and can be read by the software at any time, with no fear of things changing between reads. Some designers tie the register's clock input to one of the port control lines.
The I/O read instruction then automatically strobes data into the latch, assuming one is wise enough to ensure the register latches data on the leading edge of the clock.
The input capture register is a very simple way to suspend moving data during the duration of a couple of reads. At first glance it seems perfectly safe. However, a bit of analysis shows that for asynchronous inputs it is not reliable. We're using hardware to fix a software problem, so we must be aware of the limitations of physical logic devices.
To simplify things for a minute, let's zoom in on that input capture register and examine just one of its bits. Each gets stored in a flip-flop, a bit of logic that might have only three connections: data in, data out, and clock. When the input is a one, strobing clock puts a one at the output.
However, suppose the input changes at about the same time clock cycles. What happens?
The short answer is that no one knows.
Jakob
Engblom (jakob@virtutech.com)
is technical marketing manager at
at Virtutech.
He has a MSc in computer science and a PhD in Computer Systems from
Uppsala University, and has
worked with programming tools and simulation tools for embedded and
real-time systems since 1997.
He was a contributor of
material to "The Firmware Handbook," edited
by Jack Ganssle, upon which this series of articles was based and
printed
with permission from Newnes, a division of Elsevier.
Copyright 2008. For
other publications by Jakob Engblom, see www.engbloms.se/jakob.html.