Heptane and Trampoline

Heptane is a static analysis tool. The goal of the Heptane toolchain is to compute an estimation of the Worst-Case Execution Time (WCET) of a given code snippet. It is composed of 2 parts: a Control Flow Graph (CFG) extractor and a WCET analyser.

Loading the environment:

$ source /share/m1info/ITR/env_setup

HeptaneExtract

  • Input: a XML configuration file
  • Output: a XML file with all CFGs
  • Optional output: files created by objdump, readelf

This first part will extract the program’s Control Flow Graphs (CFGs) from a binary file, each CFG correspondong to a function in the binary. The extractor will look into the binary, with the help of objdump and readelf to extract : the binary sections, the symbol table, intructions listing, etc … and every piece of information needed to identify basic blocks, loops and functions. Then it creates a XML file to store all these information, this file is named “PROGRAMNAME.xml”, with PROGRAMNAME the program’s name found in the configuration file.

Usage

$ HeptaneExtract [-v] myextractconfigfile.xml
-v : will increase verbosity

Config file

<?xml version="1.0"?>
<CONFIGURATION>
<TARGET NAME="ARM" ENDIANNESS="LITTLE"/>
<!-- Objdump (called with options -t -d -z ) -->
<OBJDUMP NAME="arm-elf-objdump" OPT=""/>
<!-- Readelf (called with option -S) -->
<READELF NAME="arm-elf-readelf" OPT=""/>
<!-- Directories of inputs, temporaries and outputs (default values . /tmp and .) -->
<INPUTDIR NAME="."/>
<TMPDIR NAME="/tmp"/>
<RESULTDIR NAME="."/>

<!-- 
Program parameters 
NAME: program name, used as a file name prefix when generating outputs in RESULTDIR 
ENTRYPOINT: the first function to be called in user space, usually the "main" function
SOURCEFILE NAME: should point to the exe file. (merged with INPUTDIR to load file) 
SOURCEFILE TYPE: BINARY -- only binary is available for students
ANNOTATIONFILE: input file defining flow information. (merged with INPUTDIR to load file) 
-->

<PROGRAM NAME = "SomeThing" ENTRYPOINT = "main" >
<SOURCEFILE NAME="SomeThingExecutable" TYPE="BINARY" ANNOTATIONFILE="SomeThing-annot.xml" />
</PROGRAM>
</CONFIGURATION>

Annotation file

To statically estimate the WCET, every analyser will require some flow information such as loop bounds. Because this information is not generated by the analyzer, it must be given by the user to Heptane. The simplest is to use the annotation file. Following is an example of how you can use it, if we consider that the function named “patatra” has 2 loops in its body (sequentially found), and the function named “shiboum” has 2 nested loops. When parsing the file, Heptane will link the loop bound information in the order it finds the loops in the binary.

<?xml version="1.0" ?>
<ANNOT>
<CFG name="patatra">
<LOOP maxiter="42 " />
<LOOP maxiter="24 " />
</CFG>
<CFG name="shiboum">
<LOOP maxiter="21 ">
<LOOP maxiter="12 " />
</LOOP>
</CFG>
</ANNOT>

NXT & Trampoline specificities

Statically analyzing a NXT & Trampoline application is very tricky and requires to use some hacks and specific configurations. Here is what you need to know for the extraction:

  • The binary sent to the brick is the “*_exe.rxe” file, however this file is not an ELF file anymore, it has been modifed by the NXT & Trampoline compilation toolchain. Then to statically analyse your program, you will have to use the original EFL file “*_exe” instead.
  • Be careful about the compilation flags you use, WCET tools do not like compiler optimisations that are too aggressive. For example, you should use “-O0” and only necessary compilation flags. Also, debug flag such as “-g” add some information into the assembly code that will mess up with the Heptane toolchain. Example of a WCET-friendly goil file:
    CFLAGS = "-c -ffreestanding -fsigned-char -mcpu=arm7tdmi -O0 -Wall -Werror-implicit-function-declaration -ffunction-sections -fdata-sections -std=gnu99";
    ASFLAGS = "-mcpu=arm7tdmi --fatal-warnings";
    LDFLAGS = "-O0 --allow-multiple-definition --gc-sections";
  • You will have some missing information such as loop bounds and some other stuff, we strongly advise you to use our annotation file available at /share/m1info/ITR/trampoline-annot.xml ; it contains the required loop bounds, some WCET for library functions that you can not find by yourself and function aliases that the Osek/VDX & Trampoline use.
  • Be careful in the naming of the CFG name in the annotation file when giving control flow information. From your C source file, you might have a task named “blahblah”. In the binary file,  this task is renamed “blahblah_function”. So will it be in CFGs Heptane will extract from the binary.

HeptaneAnalysis

  • Input: a XML configuration file
  • Output: a XML file with all CFGs completed with WCET

This second part will perform the static WCET analysis. HeptaneAnalysis will perform a series of analyses according to the architecture and the ones specified into the configuration file. The further presented configuration file only exhibits the last analysis that finally compute the WCET, an Implicit Path Enumeration Technique (IPET). For other analyses please refer to the paper from 2017 WCET workshop paper. Each analysis will augment the information known about the program and can be written into a XML file, for the IPET analysis shown in the configuration file, the “output_file” attribute will point to a file containing all the extracted CFGs from HeptaneExtract with some specifics informations such as the WCET in number of cycles for each CFG .

Usage

$ HeptaneAnalysis [-t] myanalysisconfigfile.xml
-t : will write traces on stdout

Config file

<?xml version="1.0"?>
<CONFIGURATION>
<!-- directory in which all files will be read/written -->
<INPUTOUTPUTDIR name="./"/>
<!-- Architecture description -->
<ARCHITECTURE>
<!-- Target type -->
<TARGET NAME="ARM" ENDIANNESS="LITTLE"/>
<MEMORY load_latency="100" store_latency="100"/>
</ARCHITECTURE>
<ANALYSIS>
<!-- 
input_file name: name of the xml file containing the program to be analyzed, created by HeptaneExtract 
entrypointname: name of the entry-point function, usually "main"
-->
<ENTRYPOINT input_file ="SomeThing.xml" entrypointname="main"/>
<!-- 
Final WCET computation.
keepresults, output_file, attach_WCET_info : will enable the analyser to create a file with the WCET information
fun_detailed: will enable each function to have its own WCET (not just the entrypoint)
generate_note_req, solver, pipeline: are meant to set-up the solving phase
-->
<IPET keepresults="on" output_file="SomeThing-res.xml" solver="cplex" pipeline="off" attach_WCET_info="on" generate_node_freq="on" fun_detailed="off" />
</ANALYSIS>
</CONFIGURATION>

Result file example

<?xml version="1.0"?>
<PROGRAM id ="1" name="TP4_1_exe" entry="0" >
<CFG id="0" name="main" startnode="2" endnodes="3, " >
<NODE id="2" .... 
</NODE>
<EDGE id="18" .... />
<ATTRS_LIST>
<ATTR type="integer" name="CodeSize" value="416" />
<ATTR type="integer" name="StackSize" value="0" />
<ATTR type="integer" name="WCET" value="109590" />
</ATTRS_LIST>
</CFG>
</PROGRAM>

NXT & Trampoline specificities

Statically analyzing a NXT & Trampoline application is very tricky and require to use some hacks and specific configurations. Here are what you need to know for the analysis:

  • We will not be using any specificities of the ARM architecture such as caches to ease the WCET analysis. This will create a pessimistic WCET, but that will still be safe.
  • Remember that you need the WCET for all tasks of your system
  • Be careful in the naming of the CFG name in the result. From your C source file, you might have a task named “blahblah”, that will be renamed “blahblah_function” in the binary. So will it be in the Heptane result file.

Comments are closed.