reentrant

From SEGGER Wiki
Jump to: navigation, search

A subroutine is called reentrant if it can safely be called again ("re-entered") before the previous invocation has completed execution. This can happen in different ways:

Typically, this means that the routine does not use any static variables. Routines which use only parameters and local variables are reentrant. Note that re-entrancy is not the same as recursive calling. If a function is recursive, it calls itself, either directly (FuncA calls FuncA) or indirectly (FuncA calls FuncB calls FuncA).

Calling conventions of most modern processors store parameters in registers and on the stack, which is basically required for a routine to be reentrant. Some compilers for older architectures (especially for 8-bit architectures such as 8051 and 6502) do not produce reentrant code and use a static overlay scheme instead.

Bad example

The example below is a bad example, as it uses static variable data. If the code executes multiple times, both instances use the same table. Unfortunately, if the Polynomial parameter for the 2 instances is different, they require different tables. One or both invocations will produce an incorrect result.

unsigned CalcCRC(unsigned crc, const unsigned char* pData, unsigned NumBytes, unsigned Polynomial) {
  int i;
  static unsigned _Poly;
  static unsigned _aCRC[256];

  //
  // Build CRC table if it has not already been built for this polynomial
  //
  if (Polynomial != _Poly) {
    _Poly = Polynomial;
    for (i = 0; i < 256; i++) {
      // ... More code to compute the static table. Left out for clarity
    }
  }
  //
  // Use table to compute the actual crc
  //
  while (NumBytes--) {
    _aCRC[i] = ...
  }
  return crc;  
}

Better example

The code below is a modified version of the "bad example". The static variables are eliminated, or rather one is eliminated as it is no longer required, the array is placed in local memory, so typically the stack. In this case, all it really took is elimination of the static keyword, which places the array in a fixed address in RAM rather than variable, SP- relative address. All re-entrancy problems are solved that way. Unfortunately, the routine now needs to compute the table each time it is call, which is not very efficient, especially if it is frequently called for smaller amounts of data. Possible fixes to this performance problem can now be to use a smaller table (16 entries?) or pre-computed table with 256 constant values. In this case, the routine would be specialized for a single Polynomial, and that Polynomial should probably become part of the name. But anyhow, this is leading to far, below the re-entrant version of the code:

unsigned CalcCRC(unsigned crc, const unsigned char* pData, unsigned NumBytes, unsigned Polynomial) {
  int i;
  unsigned aCRC[256];

  //
  // Build CRC table for this polynomial
  //
    for (i = 0; i < 256; i++) {
      // ... More code to compute the table.
    }
  //
  // Use table to compute the actual crc. Left out for clarity
  //
  while (NumBytes--) {
    aCRC[i] = ...
  }
  return crc;  
}