[RFC] MISRA-C/C++ Compliant Runtime #3159

liangfu · 2019-05-09T07:12:42Z

For a long time, the development of TVM has been focused on optimizing deep learning inference for almost any processing systems, and it has been used widely in many applications fields. However, when users of TVM were trying to use theirs pretrained & quanitzed model in critical systems (e.g. aircraft control and autonomous driving), the running source code is expected to be extremely reliable and compact. This RFC intends to bring and discuss the possibility to port an essential part of the runtime code base to MISRA-C compliant form, so that the pretrained & quantized model can be potentially used in safety critical systems.

Features Proposed to be MISRA-C/C++ Compliant

load_json and load_params related functions, ndarray class, graph_runtime class
Interface with Zephyr RTOS (e.g. memory allocation, storage device, network related)

apps/bundle_deploy/bundle.cc have concluded the essential source code files:

#include "src/runtime/c_runtime_api.cc"      
#include "src/runtime/cpu_device_api.cc"     
#include "src/runtime/workspace_pool.cc"     
#include "src/runtime/module_util.cc"        
#include "src/runtime/module.cc"             
#include "src/runtime/registry.cc"           
#include "src/runtime/file_util.cc"          
#include "src/runtime/threading_backend.cc"  
#include "src/runtime/thread_pool.cc"        
#include "src/runtime/ndarray.cc"            
#include "src/runtime/system_lib_module.cc"  
#include "src/runtime/graph/graph_runtime.cc"

Proposed Changes

MISRA-C/C++ compliant code should be available at src/crt directory
Test cases should be created to check consistency between c++ implement and MISRA-C/C++ compliant versions.

Notable Coding Rules in MISRA-C

Control flow

14.1 (req) There shall be no unreachable code.
14.5 (req) The continue statement shall not be used.
14.7 (req) A function shall have a single point of exit at the end of the function.
14.10 (req) All if ... else if constructs shall be terminated with an else clause.

Pointer type conversions

11.1 (req) Conversions shall not be performed between a pointer to a function and any type
other than an integral type.
11.2 (req) Conversions shall not be performed between a pointer to object and any type
other than an integral type, another pointer to object type or a pointer to void.

Functions

16.1 (req) Functions shall not be defined with a variable number of arguments.

Standard libraries

20.4 (req) Dynamic heap memory allocation shall not be used.

Integration Tests

Coverity can be used freely in open source projects to scan potential violation of MISRA rules.

Discussion Topics

Shall we preserve Registry based function construction framework in MISRA-C/C++ compliant runtime?
Which MISRA-C/C++ standard shall we comply with in evaluation of the runtime?
(choices: MISRA-C 2004, MISRA-C++-2008, MISRA-C-2012)

Reference

[1] MISRA-C & MISRA C++
[2] Guidelines for the use of the C++14 language in critical and safety-related systems
[3] MISRA-C related issues in Zephyr RTOS
[4] An Analysis of ISO 26262: Using Machine Learning Safely in Automotive Software

The text was updated successfully, but these errors were encountered:

ajtulloch · 2019-05-15T22:41:57Z

@liangfu this looks quite interesting. Does MISRA compliance affect the compiler or the generated code as well (i.e. how do we certify that the output of e.g. LLVM is correct, doesn't segfault, etc?).

WRT to the minimal runtime I put together that bundle_deploy.cc list quite quickly, I think with a bit of pruning (e.g. if we enforce single threaded use from MISRA, we can get rid of threading_backend/thread_pool, etc). IIRC @nhynes and co were potentially interested in a minimal Rust runtime which might be useful as well here?

nhynes · 2019-05-16T01:41:55Z

minimal Rust runtime which might be useful as well here?

For sure. The Rust runtime has all of the features required for running syslib modules, but it makes use of alloc and some tasteful unsafety, which are disallowed by MISRA. If we really wanted to have an ultra-safe runtime, we could do a bit better there. Rust is probably closer to complete safety than rewriting the C++ runtime, though.

Of course, as @Ravenwater has oft mentioned, adopting Rust for existing projects is something of a nonstarter. Perhaps if we could enumerate which platforms (and users) would want a Safe runtime, we could determine whether C++ is truly necessary or just the first thing that comes to mind.

liangfu · 2019-05-16T02:51:22Z

Does MISRA compliance affect the compiler or the generated code as well?

In my observation, the compliance does affect the compiler and the code generator. However, as a first step towards making TVM available for the critical and safety related systems, I think it's important to consider the runtime design first.

Perhaps if we could enumerate which platforms (and users) would want a Safe runtime

It's difficult to enumerate all the platforms and users who want such runtime. However, it would be a good start to consider how could a developer use TVM to perform the perception task in a fully automated driving vehicle. There are a number of platforms that are already certified by ISO 26262 (e.g. QNX ), and for the open source world, I think it's good to start with Zephyr RTOS.

On the other hand, in order to reduce the effort in rewriting another minimal runtime, I think we should try to eliminate the usage of malloc, or at least conclude required memory allocation to input, intermediate and output buffers only.

tqchen · 2019-05-16T03:50:37Z

Memory allocation is fine, as long as we have a pre-allocated heap that provide a sufficient amount of meory

liangfu · 2019-05-16T07:41:35Z

A software implemented with malloc would only reach functional safety level of QM. It would be far from to be graded as ASIL-D. (See ISO 26262 Table 8 Topic 2 in Meeting ISO 26262 Guidelines with the Synopsys Software Integrity Portfolio )

Since neural networks are compiled and optimized in TVM, it is also possible to determine the size of variables in the runtime. This way, the generated config header can be used to eliminate the usage of malloc in the runtime implement.

nhynes · 2019-05-16T22:55:12Z

It's definitely possible to fixup the TVM runtime so that the buffers are included as part of the static library and to inline the pointers at compile time. If the graph is also constructed at compile time (something I've been wanting to do in the rust runtime anyway) then there's not much outside of (Workspace|Thread)Pool that needs allocation.

tqchen · 2019-05-16T23:00:56Z

Yes, what I mean is to pre-calculate the space necessary and mimic device-alloc with the fix size heap

nhynes · 2019-05-16T23:38:36Z

mimic device-alloc with the fix size heap

From what I can tell, writing a user malloc is against the spirit of MISRA. Part of the benefit is knowing exactly what will happen in the memory manager, but I'm not sure whether it's reasonable to ask people to bring their own libc. We actually don't need dynamic memory management at all, though.

tqchen · 2019-05-17T00:21:58Z

I don't mean to bring our own libc, but just to implement the DeviceAPI::Alloc with a fixed pre-allocated heap.

nhynes · 2019-05-17T01:40:57Z

Ah, that makes total sense: a non-trivial implementation of DeviceAPI. Gee, what a nice abstraction! I still kind of want the static graph, though :)

liangfu · 2019-05-22T09:53:12Z

If I understand correctly, using a fixed pre-allocated heap would lead us to convert a fragment of the storage pool (which is a fixed-sized static memory) into the specific data type for computation. This violates another rule that restrict (or avoid) using data type conversion. In this case, I think building static graph is preferred.

… of TVM models This is an alternative implementation of a subset of the TVM runtime API (and graph runtime) that focuses entirely on reducing code size, at the expense of functionality (no tvm.extern(..) calls via PackedFunc, CPU only, etc). It might be worth incrementally expanding the surface area if there's interest. The motivation for this work was seeing what the minimal useful subset of the TVM runtime is. This is relevant for e.g. super code-size constrained applications in e.g. embedded/mobile. The current runtime is more like O(100KiB) or so, so this might be compelling for some users. The smaller surface area for auditing might make this relevant for apache#3159, or the usecases I was thinking about in apache#2523 (comment) re: the Rust runtime. The symbols in the tvm::minimalruntime space (i.e. excluding std:: and picojson::) are about 5KiB, so I think there's a bunch of room here (i.e. we could replace picojson:: with [`jsmn`](https://zserge.com/jsmn.html) or something, and we could replace more of the `std::unordered_map` usage, etc with custom primitives as well (similar to the `DynArray`).

… of TVM models (#3567) This is an alternative implementation of a subset of the TVM runtime API (and graph runtime) that focuses entirely on reducing code size, at the expense of functionality (no tvm.extern(..) calls via PackedFunc, CPU only, etc). It might be worth incrementally expanding the surface area if there's interest. The motivation for this work was seeing what the minimal useful subset of the TVM runtime is. This is relevant for e.g. super code-size constrained applications in e.g. embedded/mobile. The current runtime is more like O(100KiB) or so, so this might be compelling for some users. The smaller surface area for auditing might make this relevant for #3159, or the usecases I was thinking about in #2523 (comment) re: the Rust runtime. The symbols in the tvm::minimalruntime space (i.e. excluding std:: and picojson::) are about 5KiB, so I think there's a bunch of room here (i.e. we could replace picojson:: with [`jsmn`](https://zserge.com/jsmn.html) or something, and we could replace more of the `std::unordered_map` usage, etc with custom primitives as well (similar to the `DynArray`).

… of TVM models (apache#3567) This is an alternative implementation of a subset of the TVM runtime API (and graph runtime) that focuses entirely on reducing code size, at the expense of functionality (no tvm.extern(..) calls via PackedFunc, CPU only, etc). It might be worth incrementally expanding the surface area if there's interest. The motivation for this work was seeing what the minimal useful subset of the TVM runtime is. This is relevant for e.g. super code-size constrained applications in e.g. embedded/mobile. The current runtime is more like O(100KiB) or so, so this might be compelling for some users. The smaller surface area for auditing might make this relevant for apache#3159, or the usecases I was thinking about in apache#2523 (comment) re: the Rust runtime. The symbols in the tvm::minimalruntime space (i.e. excluding std:: and picojson::) are about 5KiB, so I think there's a bunch of room here (i.e. we could replace picojson:: with [`jsmn`](https://zserge.com/jsmn.html) or something, and we could replace more of the `std::unordered_map` usage, etc with custom primitives as well (similar to the `DynArray`).

JammyZhou · 2019-11-09T13:52:13Z

@liangfu Good to know you are using Zephyr RTOS for the development of this RFC. Can you share more details about your effort to integrate TVM with Zephyr? I'm also interested in it.

liangfu · 2019-11-12T02:14:33Z

@JammyZhou The runtime part is actually OS independent. I refer to Zephyr RTOS as an example of OS that provides MISRA-C compliance. As Zephyr RTOS is designed to be architecture independent, I worked on building the runtime with Zephyr RTOS on top of qemu_x86, so that the complete system would be considered to be MISRA-C compliant, and it can be easily ported to other platforms with high reliability.

JammyZhou · 2019-11-13T13:53:37Z

@liangfu Thanks for your reply. I would assume some implementation is required in the runtime to call APIs provided by Zephyr (e.g, memory allocation, etc). Is there some base I can use as a start? I have several Arm boards with Zephyr support on hand, so I can try the TVM support on these real hardware.

tqchen · 2020-03-11T16:25:01Z

#3934

tqchen added the status: RFC label May 9, 2019

liangfu changed the title ~~[RFC] MISRA-C 2012 Compliant C Runtime~~ [RFC] MISRA-C/C++ Compliant C/C++ Runtime May 10, 2019

liangfu changed the title ~~[RFC] MISRA-C/C++ Compliant C/C++ Runtime~~ [RFC] MISRA-C/C++ Compliant Runtime May 10, 2019

ajtulloch mentioned this issue Jul 18, 2019

[RFC] [Contrib] [Runtime] Minimal runtime (~12kb .text on ARMv7/x86) for subset of TVM models #3567

Merged

liangfu mentioned this issue Sep 11, 2019

[Runtime] MISRA-C compliant TVM runtime #3934

Merged

tqchen closed this as completed Mar 11, 2020

liangfu mentioned this issue Mar 13, 2020

[uTVM][Runtime] Deprecate uTVM Standalone Runtime #5060

Closed

9 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[RFC] MISRA-C/C++ Compliant Runtime #3159

[RFC] MISRA-C/C++ Compliant Runtime #3159

liangfu commented May 9, 2019 •

edited

Loading

ajtulloch commented May 15, 2019

nhynes commented May 16, 2019

liangfu commented May 16, 2019

tqchen commented May 16, 2019

liangfu commented May 16, 2019 •

edited

Loading

nhynes commented May 16, 2019

tqchen commented May 16, 2019

nhynes commented May 16, 2019

tqchen commented May 17, 2019

nhynes commented May 17, 2019

liangfu commented May 22, 2019

JammyZhou commented Nov 9, 2019

liangfu commented Nov 12, 2019

JammyZhou commented Nov 13, 2019

tqchen commented Mar 11, 2020

[RFC] MISRA-C/C++ Compliant Runtime #3159

[RFC] MISRA-C/C++ Compliant Runtime #3159

Comments

liangfu commented May 9, 2019 • edited Loading

Features Proposed to be MISRA-C/C++ Compliant

Proposed Changes

Notable Coding Rules in MISRA-C

Integration Tests

Discussion Topics

Reference

ajtulloch commented May 15, 2019

nhynes commented May 16, 2019

liangfu commented May 16, 2019

tqchen commented May 16, 2019

liangfu commented May 16, 2019 • edited Loading

nhynes commented May 16, 2019

tqchen commented May 16, 2019

nhynes commented May 16, 2019

tqchen commented May 17, 2019

nhynes commented May 17, 2019

liangfu commented May 22, 2019

JammyZhou commented Nov 9, 2019

liangfu commented Nov 12, 2019

JammyZhou commented Nov 13, 2019

tqchen commented Mar 11, 2020

liangfu commented May 9, 2019 •

edited

Loading

liangfu commented May 16, 2019 •

edited

Loading