Making a function safe for use in an ISR

On Jan 25, 12:23 am, "joshc" <josh.cu...@gmail.com> wrote:

> Are you confusing iterative and recursive when you talk of stack
> blowout? I don't see how entry conditions would affect the stack usage
> of this _iterative_ function.

Right. I plead exhaustion. I was actually fixing an issue with an
exploding recursive function at the time I wrote that posting, so it
was uppermost in my mind.

"joshc" <josh.curtz@gmail.com> wrote in message 
news:1169696689.897046.166960@l53g2000cwa.googlegroups.com...
> So during an interview for an embedded software position, I was asked
> to write any function I wanted in C. I chose an iterative factorial
> function like this:
>
> int iterative_factorial(int i) {
>  int f;
>  f = 1;
>
>  while (i != 0) {
>    f = i * f;
>    i--;
>  }
>  return(f);
> }
>
> I was then asked what I would have to worry about or fix to make the
> function safe to use in an ISR. I really could not think of anything
> wrong with this function as it seems reentrant and I don't see any
> concurrency issues. Can anyone think of anything that might make this
> function unsafe to use in an ISR?

As long as all variables are of storage class automatic and there are no 
references to global variables or hardware, this function is already 
ISR-safe.

Basic assumptions:  1)the compiler you're using maintains stack frames and 
keeps everything on the stack, 2)your development tool chain doesn't have 
any other requirements ... such as special keywords that change which 
registers are saved/restored, etc.

-- 
David T. Ashley              (dta@e3ft.com)
http://www.e3ft.com          (Consulting Home Page)
http://www.dtashley.com      (Personal Home Page)
http://gpl.e3ft.com          (GPL Publications and Projects) 

"joshc" <josh.curtz@gmail.com> wrote in message 
news:1169696689.897046.166960@l53g2000cwa.googlegroups.com...
> So during an interview for an embedded software position, I was asked
> to write any function I wanted in C. I chose an iterative factorial
> function like this:
>
> int iterative_factorial(int i) {
>  int f;
>  f = 1;
>
>  while (i != 0) {
>    f = i * f;
>    i--;
>  }
>  return(f);
> }
>
> I was then asked what I would have to worry about or fix to make the
> function safe to use in an ISR. I really could not think of anything
> wrong with this function as it seems reentrant and I don't see any
> concurrency issues. Can anyone think of anything that might make this
> function unsafe to use in an ISR?
>
> Thanks,
>
> Josh
>
As written the function is "unsafe" in many contexts within an embedded app 
(particularly so in an ISR where "get in and out quickly" is often important 
to maintain system timing) :
- i is signed, int may be 8,16,32 (maybe 64?) bits in size
- So, called with i=-1, the function goes completely wrong and executes for 
potentially many loops
- It may be safe, for example, if it is static and the whole module is 
reviewed to make sure this doesn't happen
- If not, I'd generally recommend checking for acceptable parameters
- I often code such things as __tError Function(int nPara, int *pnResult), 
returning an error code (e.g. PARAMETER_OUT_OF_RANGE) and "returning" the 
result by a pointer

On Thu, 25 Jan 2007 23:07:25 -0600, "Gary Pace" <xxx@yyy> wrote:

>
>"joshc" <josh.curtz@gmail.com> wrote in message 
>news:1169696689.897046.166960@l53g2000cwa.googlegroups.com...

>> int iterative_factorial(int i) {
>>  int f;
>>  f = 1;
>>
>>  while (i != 0) {
>>    f = i * f;
>>    i--;
>>  }
>>  return(f);
>> }
>>

This function can not be a stand-alone ISR (with register save
preamble), since ISRs do not in general have input parameters or
return any function results, so apparently this example function is
called from some higher level interrupt service code.
 
>As written the function is "unsafe" in many contexts within an embedded app 
>(particularly so in an ISR where "get in and out quickly" is often important 
>to maintain system timing) :
>- i is signed, int may be 8,16,32 (maybe 64?) bits in size

If this is supposed to be standard C, then int can not be 8 bits.

Someone pointed out that the ISR could execute for a very long time.
However, in this case this would not be a critical thing for legal
values.

 7! = 0x13B0    Legal 16 bit signed int
 8! = 0x9D80    Legal 16 bit only as unsigned
 9! = 0x58980   Does not fit into 16 bit
 
12! = 0x1C8CFC00  Legal 32 bit signed int
13! = 0x17328CC00 Does not fit into 32 bits

So for 16 bit int, at most 7 iterations would have to be performed,
while the result f fits into int and with 32 bit int, 12 iterations
are required and with 64 bit int, 20 iterations would be performed at
most.

However, multiplications and divisions should be avoided in ISRs,
especially if these are implemented in software or implemented as
microcode with execution times several times larger than ordinary
instructions. 

Floating point instructions should be avoided even if the instruction
set implements these instructions, since saving and restoring the
floating point control/status and actual data registers would take a
huge time. 

While the 8087 style floating point processor (used in most x86
processors) contains an internal stack for internal values, this is
practically useless for ISRs, since it contains only 8 slots and could
be used to 7-8 slots already when the ISR occurs, so executing
floating point operations in the ISR without first saving the stack
could easily overflow the stack.

On later Pentium models, the FPU stack is used as MMX data registers
and the processor might be in MMX mode when the interrupt occurs,
switching it to floating point mode in the ISR takes a very long time
as well as restoring the MMX state after the interrupt execution.

Paul
  

Paul Keinanen wrote:
[snip]
> 
> However, multiplications and divisions should be avoided in ISRs,
> especially if these are implemented in software or implemented as
> microcode with execution times several times larger than ordinary
> instructions. 
> 
> Floating point instructions should be avoided even if the instruction
> set implements these instructions, since saving and restoring the
> floating point control/status and actual data registers would take a
> huge time. 
> 
> While the 8087 style floating point processor (used in most x86
> processors) contains an internal stack for internal values, this is
> practically useless for ISRs, since it contains only 8 slots and could
> be used to 7-8 slots already when the ISR occurs, so executing
> floating point operations in the ISR without first saving the stack
> could easily overflow the stack.
> 
> On later Pentium models, the FPU stack is used as MMX data registers
> and the processor might be in MMX mode when the interrupt occurs,
> switching it to floating point mode in the ISR takes a very long time
> as well as restoring the MMX state after the interrupt execution.
> 
These points are valid enough for X86 architectures. However the OP 
specified an "embedded" application, so it is unlikely a Pentium would 
be used (it might be, of course :)
Many other CPUs have multiply and FP instructions that act directly on 
the CPU registers, so there would be no inherent bar to using them in 
interrupts. Of course, one would want to check the specs for just how 
long they take.

On Friday, in article
     <dngjr29j577keg3m5r01n4vv3mn4nap5ak@4ax.com> keinanen@sci.fi
     "Paul Keinanen" wrote:
>On Thu, 25 Jan 2007 23:07:25 -0600, "Gary Pace" <xxx@yyy> wrote:
>
>>
>>"joshc" <josh.curtz@gmail.com> wrote in message 
>>news:1169696689.897046.166960@l53g2000cwa.googlegroups.com...
>
>>> int iterative_factorial(int i) {
>>>  int f;
>>>  f = 1;
>>>
>>>  while (i != 0) {
>>>    f = i * f;
>>>    i--;
>>>  }
>>>  return(f);
>>> }
>>>
>
>This function can not be a stand-alone ISR (with register save
>preamble), since ISRs do not in general have input parameters or
>return any function results, so apparently this example function is
>called from some higher level interrupt service code.
>
>>As written the function is "unsafe" in many contexts within an embedded app 
>>(particularly so in an ISR where "get in and out quickly" is often important 
>>to maintain system timing) :
>>- i is signed, int may be 8,16,32 (maybe 64?) bits in size
>
>If this is supposed to be standard C, then int can not be 8 bits.
>
>Someone pointed out that the ISR could execute for a very long time.
>However, in this case this would not be a critical thing for legal
>values.
>
> 7! = 0x13B0    Legal 16 bit signed int
> 8! = 0x9D80    Legal 16 bit only as unsigned
> 9! = 0x58980   Does not fit into 16 bit
> 
>12! = 0x1C8CFC00  Legal 32 bit signed int
>13! = 0x17328CC00 Does not fit into 32 bits
>
>So for 16 bit int, at most 7 iterations would have to be performed,
>while the result f fits into int and with 32 bit int, 12 iterations
>are required and with 64 bit int, 20 iterations would be performed at
>most.
>
>However, multiplications and divisions should be avoided in ISRs,
>especially if these are implemented in software or implemented as
>microcode with execution times several times larger than ordinary
>instructions. 

Well if this is to be a function returning int of 8,16,32 or even 64bits
the SAFEST method is Lookup table as there are not that many values with
-1, or all ones (signed/unsigned) as return value for out of range.

Why bother computing an integer value that has a limited range of results
everytime, for that matter it could easily be a global table in READ ONLY
space on a true embedded system, depending on how many times called and
if the input range is limited and checked ALWAYS elsewhere.

Assuming you are not trying to do factorials of negative numbers... the
function basically becomes -

int iterative_factorial(int i)
 {
 return ( (i<0 &#4294967295;&#4294967295; i>MAX_INDEX) ? 0xFFFF : factorial_table[i]);
 }

Even with 13 or more entries in the lookup table the code size will be
smaller, the footprint of calls will be smaller, the execution time
will be faster and deterministic.

-- 
Paul Carpenter          | paul@pcserviceselectronics.co.uk
<http://www.pcserviceselectronics.co.uk/>    PC Services
<http://www.gnuh8.org.uk/>              GNU H8 & mailing list info
<http://www.badweb.org.uk/>             For those web sites you hate

On Fri, 26 Jan 2007 03:08:30 -0800, David R Brooks
<davebXXX@iinet.net.au> wrote:

>Paul Keinanen wrote:
>[snip]
>> 
>> However, multiplications and divisions should be avoided in ISRs,
>> especially if these are implemented in software or implemented as
>> microcode with execution times several times larger than ordinary
>> instructions. 
>> 
>> Floating point instructions should be avoided even if the instruction
>> set implements these instructions, since saving and restoring the
>> floating point control/status and actual data registers would take a
>> huge time. 
>> 
>> While the 8087 style floating point processor (used in most x86
>> processors) contains an internal stack for internal values, this is
>> practically useless for ISRs, since it contains only 8 slots and could
>> be used to 7-8 slots already when the ISR occurs, so executing
>> floating point operations in the ISR without first saving the stack
>> could easily overflow the stack.
>> 
>> On later Pentium models, the FPU stack is used as MMX data registers
>> and the processor might be in MMX mode when the interrupt occurs,
>> switching it to floating point mode in the ISR takes a very long time
>> as well as restoring the MMX state after the interrupt execution.
>> 
>These points are valid enough for X86 architectures. However the OP 
>specified an "embedded" application, so it is unlikely a Pentium would 
>be used (it might be, of course :)

There is a quite large number of small form factor processor boards
using mobile Pentiums from Intel. There are other processors from
other manufacturers running Pentium code (of course these processors
can not be called Pentium due to trade mark reasons) that fit into the
PC/104 board. These small boards are used frequently in various
embedded applications. 

IMHO, the greatest problem in using x86 processors in embedded
applications is the short production run, typically 1-2 years, while
some products using embedded processors may be produced for years and
may require support for 10-20 years.

>Many other CPUs have multiply and FP instructions that act directly on 
>the CPU registers, so there would be no inherent bar to using them in 
>interrupts. Of course, one would want to check the specs for just how 
>long they take.

Apart from bandwidth issues (e.g. double requires two 32 bit
registers), one should also check the control register issues, for
instance the rounding/truncate bit found in many processors. Are such
bits readable from the hardware registers before modifying them ?

Paul

In article <1169696689.897046.166960@l53g2000cwa.googlegroups.com>, 
joshc <josh.curtz@gmail.com> writes
>So during an interview for an embedded software position, I was asked
>to write any function I wanted in C. I chose an iterative factorial
>function like this:
>
>int iterative_factorial(int i) {
>  int f;
>  f = 1;
>
>  while (i != 0) {
>    f = i * f;
>    i--;
>  }
>  return(f);
>}
>
>I was then asked what I would have to worry about or fix to make the
>function safe to use in an ISR. I really could not think of anything
>wrong with this function as it seems reentrant and I don't see any
>concurrency issues. Can anyone think of anything that might make this
>function unsafe to use in an ISR?

The answers depend largely on the target architecture and the specific 
compiler you are using.

-- 
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
/\/\/ chris@phaedsys.org      www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

In article <dngjr29j577keg3m5r01n4vv3mn4nap5ak@4ax.com>, Paul Keinanen 
<keinanen@sci.fi> writes
>On Thu, 25 Jan 2007 23:07:25 -0600, "Gary Pace" <xxx@yyy> wrote:
>
>>
>>"joshc" <josh.curtz@gmail.com> wrote in message
>>news:1169696689.897046.166960@l53g2000cwa.googlegroups.com...
>
>>> int iterative_factorial(int i) {
>>>  int f;
>>>  f = 1;
>>>
>>>  while (i != 0) {
>>>    f = i * f;
>>>    i--;
>>>  }
>>>  return(f);
>>> }
>>>
>
>This function can not be a stand-alone ISR (with register save
>preamble), since ISRs do not in general have input parameters or
>return any function results, so apparently this example function is
>called from some higher level interrupt service code.
>
>>As written the function is "unsafe" in many contexts within an embedded app
>>(particularly so in an ISR where "get in and out quickly" is often important
>>to maintain system timing) :
>>- i is signed, int may be 8,16,32 (maybe 64?) bits in size
>
>If this is supposed to be standard C, then int can not be 8 bits.

No,  this  is for an embedded MCU so it can be 8 bits.
Incidentally both signed and unsigned char are integer types. However 
the standard says an int is not less than 16 bits so the chars are 
usually used.

>Someone pointed out that the ISR could execute for a very long time.
>However, in this case this would not be a critical thing for legal
>values.

That is legal for that compiler on that target. ISO C has little 
relevance here.

>Floating point instructions should be avoided even if the instruction
>set implements these instructions, since saving and restoring the
>floating point control/status and actual data registers would take a
>huge time.

That's true. However there is no reason to use floats in this function. 
Which instruction set do you mean? The compiler or the hardware?
Some MCU have FPU most compilers have FP libs that either dit it 
internally or use the HW WFU

>While the 8087 style floating point processor (used in most x86

>On later Pentium models, the FPU stack is used as MMX data registers

The only relevant Intel part here is likely to be the 386


-- 
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
/\/\/ chris@phaedsys.org      www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Chris Hills <chris@phaedsys.org> writes:

> Paul Keinanen <keinanen@sci.fi> writes
>> "Gary Pace" <xxx@yyy> wrote:
>>> - i is signed, int may be 8,16,32 (maybe 64?) bits in size
>> If this is supposed to be standard C, then int can not be 8 bits.

> No,  this  is for an embedded MCU so it can be 8 bits.

Not if you want to call the language C.

You can call it "C-like" if you want, but for the last 17 years there
has been an international standard defining the language called C and
one of its most fundamental features is that the type 'int' can hold
all values between 32767 and -32767 inclusive.  A language with a type
'int' that can not hold at least this range can not be called C.

The C standard _does_ allow for various extensions, and makes the
distinction between "freestanding" and "hosted" implementations (most
embedded platforms will be the former, which for instance doesn't need
to provide all or even any of the standard library) but reducing the
range of _the_ basic type in this way is just not on.

mlp