Thursday, February 3, 2022

[SOLVED] How to get a warning for using recursion?

Issue

Some rule sets and guidelines of embedded software development forbid recursion entirely. I use arm-none-eabi-gcc with an ARM Cortex-M4 based microcontroller.

I'm looking for a static analysis tool which would warn me about the use of recursion in the code. I have little experience with such tools. Is it possible to use clang-tidy or the clang static analyzer for this? If yes, how can I configure them to warn about recursion?

(A quick look at the gcc option summary tells me that gcc alone can't do this.)

NOTE:

  • Please don't tell me "just don't recurse". The code base is big and not mine alone. I'd like to be able to prove that there is no recursion in it.
    (That is like saying "just don't dereference a null pointer". While nobody does on purpose, tools exist for a reason to verify that it doesn't happen.)

Solution

This is solvable using callgraph data generated by Clang.

Step 1. Generate call graph information using clang: 

clang -S -emit-llvm SourceFile.c -o - | opt -analyze -print-callgraph

(From Generate calling graph for C++ code, replacing -dot-callgraph with -print-callgraph.)

For an input like:

void a(){}
void b(){a();}
void c(){a(); b();}
void d(){a(); c();}
void e(){e();}

this will produce:

CallGraph Root is: <<null function: 0x0x7fdef25036c0>>
Call graph node <<null function>><<0x7fdef25036c0>>  #uses=0
  CS<0x0> calls function 'a'
  CS<0x0> calls function 'b'
  CS<0x0> calls function 'c'
  CS<0x0> calls function 'd'

Call graph node for function: 'a'<<0x7fdef2503750>>  #uses=4

Call graph node for function: 'b'<<0x7fdef25037d0>>  #uses=2
  CS<0x7fdef2500a38> calls function 'a'

Call graph node for function: 'c'<<0x7fdef2503870>>  #uses=2
  CS<0x7fdef2500cb8> calls function 'a'
  CS<0x7fdef2500d28> calls function 'b'

Call graph node for function: 'd'<<0x7fdef2503970>>  #uses=1
  CS<0x7fdef2500fe8> calls function 'a'
  CS<0x7fdef2501058> calls function 'c'

Call graph node for function: 'e'<<0x7f8912d03c10>>  #uses=2
  CS<0x7f8912d01318> calls function 'e'

(In C++, mangled function names can be cleaned up with c++filt; templates get ugly but are doable.) With that data, it's possible to sketch out how one detects recursion:

Step 2. Parse callgraph data into favorite scripting language to form representation of callgraph.

class Graph(object):

  _callees = []

  def add_callee(self, f):
    self._callees.append(f)
    # etc

Step 3. For each function, walk graph looking for calls to that function. Something kind of like this:

def walkGraph(node,f,stack):
  for callee in node._callees:
    if f == callee:
      print('Recursion!')
      dumpStack(stack,f)
    else:
      walkGraph(callee,f,stack.append(node))


Answered By - Some Who Call Me Tim
Answer Checked By - Marilyn (WPSolving Volunteer)
at