% file intro-bm.tex, which is \input from bismon-doc.tex
\section{Introduction}
\label{sec:intro}

This D1.3~\textsuperscript{v1} \textsc{Chariot} deliverable is a first
\textbf{draft} -and \emph{preliminary}- version of
D1.3~\textsuperscript{v2} that will be formally submitted as the
complete and final deliverable at M30 on ``Specialized Static Analysis
tools for more secure and safer IoT software development''. This
deliverable targets software engineering (and indirectly also software
architects) experts working on IoT software coded in C or C++.

\subsection{Mapping \textsc{Chariot} output}
\label{subsec:mapchariot}

We refer to \textsc{Chariot} \emph{Grant Agreement} (GA). See table \ref{tab:mapchariot} below.


\begin{table}[!htbp]
  \caption{\label{tab:mapchariot} adherence to CHARIOT's GA deliverable and tasks descriptions}
  \medskip
  \begin{relsize}{-1.3}
    \begin{tabular}{|p{0.19\textwidth}|p{0.36\textwidth}|p{0.11\textwidth}|p{0.22\textwidth}|}
      \hline \textbf{\textsc{Chariot} GA component title} &
      \textbf{\textsc{Chariot} GA component outline} &
      \textbf{respective document chapter[s]} & \textbf{justification}
      \\ \hline \multicolumn{4}{|c|}{{\large \textbf{deliverable}}}
      \\
      \hline
%
      \begin{minipage}[t]{0.18\textwidth}
        \smallskip
        
        \textbf{{\relsize{+1.5}{D1.3}}} \\
        Specialized Static Analysis tools for
          more secure and safer IoT software development.
      \end{minipage}
              &
      % 
      {The source code (top level documentation) of the prototype static
      analysis tools developed in task T1.3, including the definition
      of data formats and protocols, updates and adapation of existing
      libraries and software components, the persistent monitor
      outline and documentation, anf features description and
      documentation of the compiler and linker extensions. An initial
      version set (V1) will be compiled by M12 followed by a revised
      version set (v2) in M30.}
      & {this whole document}      
      & {a single deliverable (with two versions of it, a preliminary
          draft one D1.3\textsuperscript{v1} and a final one
          D1.3\textsuperscript{v2}) describes the
          work. \S\ref{sec:intro} is an overview and introduces the
          main concepts. \S\ref{sec:datapersist} explains
          persistence. \S\ref{sec:staticanalys} relates to static
          analysis. \S\ref{sec:using} will become a user
          manual. \S\ref{sec:miscwork} relates miscellanous work. The
          conclusion is in \S\ref{sec:conclusion}.} \\      
      \hline
      \multicolumn{4}{|c|}{{\large \textbf{tasks}}} \\
      \hline
      \multirow{4}{*}{\begin{minipage}{0.19\textwidth}\smallskip
          \textbf{\relsize{+1.5}{T1.3}}          
       Specialized Static Analysis tools for
       more secure and safer IoT software development.
        \end{minipage}
      }
      & \textbf{ST1.3.1} definition of data formats and protocols
      & \S\ref{sec:datapersist}; \S\ref{subsec:compilinkext}
      & The persistent monitor data and format are described in \S\ref{sec:datapersist}.
      The protocol to interact with \textsc{Chariot}'s blockchain is related to \S\ref{subsec:compilinkext} and chapter 6 of D1.2 \\
      \cline{2-4}
      & \textbf{ST1.3.2} significant patches to existing free software components
      & \S\ref{subsec:contribfree}
      & Section \S\ref{subsec:contribfree} describe past work, and why future contributions to \emph{GCC} could be needed. \\
      \cline{2-4}
      & \textbf{ST1.3.3} design and implementation of the persistent monitor
      & \S\ref{subsec:chariotvision};  \S\ref{subsec:principles-bismon};  \S\ref{subsec:multithreadist};  \S\ref{sec:datapersist};
      &  \S\ref{subsec:chariotvision} gives the \textsc{Chariot} vision of (informal) static analysis;
      \S\ref{subsec:principles-bismon} explains the driving principles of our \emph{Bismon} persistent monitor,
      and (in  \S\ref{subsec:multithreadist}) its multi-threaded and distributed aspects;
      \S\ref{sec:datapersist} explains its persistent data.  \\
      \cline{2-4}
      & \textbf{ST1.3.4} design and implementation of the compiler and linker extension
      & \S\ref{sec:staticanalys}; \S\ref{subsec:compilinkext}
      & static analysis involves \emph{generated} GCC plugins, as (in this D1.3\textsuperscript{v1} preliminary draft)
      partly explained in \S\ref{sec:staticanalys}; compiler and linker extensions
      are (in D1.3\textsuperscript{v1}) drafted in \S\ref{subsec:compilinkext}  \\
      \hline
%-      \multirow{4}{*}{%
%-     \begin{minipage}[t]{0.18\textwidth}
%-       \smallskip
%-       
%-       \textbf{{\relsize{+1.5}{T1.3}}} \\
%-       Specialized Static Analysis tools for
%-       more secure and safer IoT software development.
%-
%-       \smallskip
%-      \end{minipage} &
%-      \emph{ST1.3.1} definition of the data format and protocols & \SXXX & tobewrittenA \\
%-      \hline
%-      \emph{ST1.3.2} significant patches to existing free software components & \SYYYY & tobewrittenB \\
%-      \hline
%-      \emph{ST1.3.3} design and implementation of the persistent monitor & \SZZZZ & hasbeenwritten \\
%-      \hline
%-      \emph{ST1.3.4} design and implementation of the compiler and linker extension & \STTTT & tobewrittenB \\
%-      \hline
       
      
    \end{tabular}
 \end{relsize}
\end{table}

\subsection{Deliverable Overview and Report Structure}
\label{subsec:overview}

This \textsc{Chariot} deliverable D1.3\textsuperscript{v1} is the
\emph{preliminary draft} of a report D1.2\textsuperscript{v2} scheduled at M30 on
\emph{Specialized Static Analysis tools for more secure and safer IoT
  software development} and relates to the work performed in
\textbf{T1.3} \emph{Specialized Static Analysis tools for more secure
  and safer IoT software development}.

The introduction (this \S\ref{sec:intro}) describes the
\textsc{Chariot} vision on static source code\footnote{Our favorite
  definition of \emph{source code} is inspired by the
  \href{https://www.fsf.org/}{FSF}: the source code is the preferred
  form on which software developers should work. In practice, source
  code is what usually (but not always) should be managed by some
  version control system like a
  \href{http://git-scm.com/}{\texttt{git}} code \index{repository}
  \href{https://en.wikipedia.org/wiki/Comparison_of_source-code-hosting\_facilities}{repository},
  or in some \index{forge}
  \href{https://en.wikipedia.org/wiki/Forge\_(software)}{software
    forge}.}  \index{source code} (mostly of C and C++ code for IoT
firmware and application) analysis (see \S\ref{subsec:chariotvision}),
proposing a simple static analysis \emph{framework} leveraging on the
powerful recent \emph{GCC} [cross-]compiler and explaining the
necessity of persistence, then gives the driving principles of our
\emph{Bismon} persistent monitor (in \S\ref{subsec:principles-bismon});
and explains its multi-threaded and distributed aspects (in
\S\ref{subsec:multithreadist}). The data and its persistence is
detailed (in \S\ref{sec:datapersist}, notably \S\ref{subsec:dataproc}
for the processed data, \S\ref{subsec:gcvalobj} for the garbage
collection, \S\ref{subsec:persistence} for persistence).  The
\S\ref{sec:staticanalys} needs still to be mostly written and will
describe (in the D1.3v2) how static analysis works. The
\S\ref{sec:using} will contain the (mostly generated) user
documentation. The \S\ref{sec:miscwork} describes some miscellanous
work.


Related previous \textsc{Chariot} deliverables include: D1.1 (on
\emph{Classification and use guidelines of relevant standards and
  platforms}), which provides a taxonomy of standards and guidelines
(notably on cybersecurity, at a high and abstract level); but does
mention much source code (except as open source projects such as
IoTivity, FiWire, OM2M, etc). and D1.2 (on \emph{Method for coupling
  preprogrammed private keys on IoT devices with a Blockchain system})
which describes the \textsc{Chariot} blockchain and its \emph{Web API}
(which should be adapted into functions or libraries callable from C
code).

\subsection{Expected audience}
\label{subsec:audience}


The numerous footnotes in this report are for a second reading (and
may be used for forward references). \textbf{To understand this report}
describing a circular and reflexive system, you should \textbf{read it
  twice} (skipping footnotes at the first read).

\bigskip

The reader of this document (within \textsc{Chariot}, a software
engineering expert \index{expert!software engineering} working on
IoT\index{IoT} \index{expert!IoT} software or firmware coded in C or
C++) is expected to:

\begin{itemize}

  \item be fluent in C (cf. \cite{Kernighan:1988:CPL,
    gusted:t2019:modern}) and/or C++ (\cite{Stroustrup:2014:CplusPlus,
    Stroustrup:2020:thriving}) programming (notably on Linux -see
    \cite{Mitchell:2001:ALP, Kerrisk:2010:LinuxProgramming} and the
    \href{https://man7.org/}{\texttt{man7.org}} and
    \href{https://kernelnewbies.org/}{\texttt{kernelnewbies.org}} and
    \href{https://www.kernel.org/}{\texttt{kernel.org}} websites-
    and/or for embedded products, perhaps for IoT),

  \item be knowing a bit the \index{C11}{C11} standard
    (cf. \cite{C11:std,Memarian:2016:PLDI}) and/or the
    \index{C++11}{C++11} one (\cite{CplusPlus11:std}) and
    understanding well the essential notion of \index{undefined
      behavior}{\emph{undefined behavior}} \footnote{See
      \bmurl{http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html}
      and \bmurl{https://blog.regehr.org/archives/1520}} in C or C++
    programs,

  \item be a daily advanced user of \index{Linux}{Linux} for software
    development activities \index{software development}
    \index{development!software} using GCC and related developer tools
    (e.g. \textit{binutils}, version control like \texttt{git}, build
    automation like \texttt{make} or \texttt{ninja}, source code
    editor like \texttt{emacs} or \texttt{vim}, the {\LaTeX} text
    formatter~\footnote{See
      \bmurl{https://www.latex-project.org/}. Some knowledge of
            {\LaTeX} is useful to improve or contribute to this
            document.}) on the \emph{command line}.
    
    \item be \emph{easily} able, in principle, to
      \textbf{compile}~\footnote{When compiling IoT software such as
        firmware, it usually is of course some
        \emph{cross}-compilation.}  his/her or other software coded in
      C (or in C++) \textbf{on the command line} (\emph{without} any
      \index{IDE!integrated development environment}IDE
      -\index{integrated development environment}~integrated software
      environment- or \index{SDK!software development kit} SDK
      -\index{software development kit}~software development kit-)
      with a \textbf{\emph{sequence} of \texttt{gcc} (or \texttt{g++})
        commands}~\footnote{In practice, we all use some \emph{build
          automation} tool, such as \texttt{make}, \texttt{ninja} or
        generators for them such as \texttt{cmake}, \emph{autoconf},
        \texttt{meson}, etc... But the reader is expected to be able
        to configure that, e.g. to add more options to \texttt{gcc} or
        to \texttt{g++} (perhaps in his/her \texttt{Makefile}) and is
        able to think in terms of a sequence of elementary
        \texttt{gcc} or \texttt{g++} compilation commands (or, when
        using Clang, \texttt{clang} or \texttt{clang++} commands).}
      \textbf{on Linux}.



\item to be capable of building large free software or open source projects (such as
  the GCC compiler (cf \cite{gcc-internals} \footnote{See
  \bmurl{http://gcc.gnu.org} and notice that many cross-compiler forms
  of \emph{GCC} may need to be compiled from the source code of that
  compiler distributed by the \emph{FSF}, in particular because GCC
  plugin ability is needed within \textsc{Chariot}, or because
  hardware vendors provide only old versions of that compiler.}), the
  Linux kernel, the \href{https://qt.io/}{\textsc{Qt}} or
  \href{https://www.fltk.org/}{\textsc{Fltk}} graphical toolkits and
  other open source projects of perhaps millions of source code lines)
  and smaller ones (e.g. \texttt{libonion} \footnote{see
  \bmurl{https://coralbits.com/libonion/}}) from their \emph{source}
  \index{qt@\textsc{Qt}} \index{fltk@\textsc{Fltk}}
  \index{libonion@\texttt{libonion}} form.

\item have successfully downloaded and built the \emph{Bismon monitor}
  \index{Bismon} from its source code \index{source code!Bismon} available on
  \\ \bmurl{https://github.com/bstarynk/bismon}, on his/her Linux
  workstation.
  
\item have contributed or participated to some
  \href{https://www.gnu.org/philosophy/free-sw.en.html}{free software}
  or \href{https://opensource.org/}{open source} projects and
  understanding their social (cf \cite{Raymond:2001:CathBaz}) and
  economical (cf \cite{Weber:2004:SuccessOpenSource,
    Tirole:2018:eco-bien-commun, Nagle:2018:Contributing,
    DiCosmo:1998:Holdup, Lerner-Tirole:2000:economics-open-source})
  implications, the practical work flow, the importance of developer
  communities and of business~\footnote{See also Daniel Oberhous' blog
  February 2019 post on
  \url{https://motherboard.vice.com/en_us/article/43zak3/the-internet-was-built-on-the-free-labor-of-open-source-developers-is-that-sustainable}:
  \emph{The Internet Was Built on the Free Labor of Open Source
  Developers. Is That Sustainable?}} support.
  
\item be interested in static source code analysis, so have already
  tried some such tools like \emph{Frama-C} \footnote{See
    \bmurl{http://frama-c.com/}} (cf. \cite{Cuoq:2012:Frama-C}),
  \emph{Clang analyzer} \footnote{See
    \bmurl{https://clang-analyzer.llvm.org/}}, ..., and be aware of
  \index{compiler} compiler concepts and technologies (read
  \cite{Aho:2006:DragonBook}).

  \item be interested by knowledge base tools and symbolic artificial
    intelligence approaches (cf \cite{nouira:1996:knowledge,
      Pitrat:1990:Metaconnaissances, Pitrat:1996:FGCS,
      Polito:2014:Bootstrapping-pharo, RAJ-2018-NoSQL,
      Rodriguez:2019:AgileLean, doyle:1985:expert,
      Starynkevitch-1990-EUM, Khalilian:2021:CGenProg} and
    \href{http://refpersys.org}{\textsc{RefPerSys}}) to software
    engineeering problems (see \cite{rich2014readings,
      beckert2007verification, happel2006applications,
      rus2002knowledge, Baudin2002CaveatAT, TWO:2001:WAPATV,
      Starynkevitch2007Multistage, Starynkevitch:2009:grow,
      FITZ:2019:metamodel-cyberphysys, Gabbay:2013:handbook}).

\item be familiar with operating systems principles
  (see \cite{Tanenbaum:92:OS,ArpaciDusseau14-Book}) and well
  versed in Linux programming
  (cf. \cite{Mitchell:2001:ALP,Kerrisk:2010:LinuxProgramming} \footnote{look
    into \texttt{man} pages on
    \bmurl{http://man7.org/linux/man-pages/}}).

  \item be interested in various \index{programming languages}
    \index{language!programming} programming languages
    (cf. \cite{Abelson1996:SICP,Scott:2007:PLP,Queinnec:1996:LSP}) and
    their \index{implementation!of programming languages}
    implementation\footnote{See also
      \bmurl{https://www.tweag.io/blog}, since several posts there are
      relevant to ideas inspiring \emph{Bismon}.}  including
    \index{language!domain specific (DSL)} \index{DSL!domain specific
      language} \index{DSL} domain specific ones.

    \item is aware that \emph{most software projects
    fail}~\footnote{See
    \bmurl{https://www.geneca.com/why-up-to-75-of-software-projects-will-fail/}}
      (for \emph{some} definition of failure; see also
      \cite{Brooks:1995:MM, Khan:2016-GSEPIM,
        Attarzadeh:2008:proj-man}, etc...), and that obviously
      includes research software projects, which fail even more often,
      and any IoT software in general. I believe that such a high
      failure rate is
      \emph{intrinsic}~\footnote{\href{https://en.wiktionary.org/wiki/IMHO}{IMHO},
      allocation of much more time and efforts, including code
      reviews, on software development is necessary - but sadly it is
      not sufficient - to lower that failure rate. Read about the
      \emph{Joel Test} on
      \bmurl{https://www.joelonsoftware.com/2000/08/09/the-joel-test-12-steps-to-better-code/}
      for more.}  to any non-trivial software developed by humans
      (because of \cite{Braun:1956:magical-seven}, of ``leaky
      abstractions''~\footnote{Cf. Spolsky's \emph{Law of leaky
      abstractions} \index{abstraction} on
      \\ \bmurl{https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/}
      etc... for more.}  and of the
      \href{https://en.wikipedia.org/wiki/Halting\_problem}{\emph{Halting
        problem}}, etc...), and that formal methods approaches are
      still vulnerable \index{vulnerability} \index{specificaton} to
      specification~\footnote{A speculative example of a tragic
      specification bug might include something inside the Boeing 737
      MAX - see \bmurl{https://en.wikipedia.org/wiki/Boeing\_737\_MAX}
      - which could have recent crashes related to bugs in
      specifications, and probably developed with the most serious
      formal methods approaches, dictated by DO-178-C -see
      \bmurl{https://en.wikipedia.org/wiki/DO-178C} etc... But in
      mid-2019 this is only a speculation (details are unknown to
      me). See also the controversial but interesting analysis of
      \cite{graeber:2018:bullshit} explaining the plausibility of such
      speculations.}  bugs. Agile and lean approaches could be
      effective for improving IoT software development processes (see
      \cite{Rodriguez:2019:AgileLean}). \index{code review} Code
      review by senior programmers is needed.
      

    \item is understanding the notion of
      \href{https://en.wikipedia.org/wiki/Technology\_readiness\_level}{\emph
        {Technical Readiness Level}} \index{TRL} (TRL) and its
      implication in innovative projects, notably H2020 \index{h2020@\emph{\textsc{h2020}}} ones (see
      \cite{Heder:2017:TRL}).

      \item is familiar with the idea of generating documentation from
        software source code, either thru
        \href{https://en.wikipedia.org/wiki/Literate_programming}{literate
          programming} techniques, such as the
        \index{nuweb@\texttt{nuweb} system} \index{LaTeX@\LaTeX
          formatter} \index{doxygen@\texttt{doxygen} documentation
          generator} \index{ocamldoc@\texttt{ocamldoc} documentation
          generator}\index{lout@\texttt{lout} document formatter}
        \href{http://nuweb.sourceforge.net/}{\texttt{nuweb} system}
        combined with \href{https://www.latex-project.org/}{\LaTeX},
        or with dedicated documentation generating tools such as
        \href{https://www.doxygen.nl/}{\texttt{doxygen} documentation
          generator} or
        \href{https://caml.inria.fr/pub/docs/manual-ocaml/ocamldoc.html}{\texttt{ocamldoc}
          documentation generator}. Documentation framework tools like
        \href{https://pandoc.org/}{\texttt{pandoc} document converter}, small batch document formatters like \href{https://en.wikipedia.org/wiki/Lout_(software)}{\textsc{Lout} software}
        or schemas such as
        \href{https://docbook.org/}{\textsc{DocBook} document schama}
        are also relevant.
      
\end{itemize}


\bigskip



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The \textsc{Chariot} vision on specialized static source code analysis for more secure and safer IoT software development}
\label{subsec:chariotvision}

\subsubsection{About static source code analysis and IoT}

\index{static analysis} \index{analysis!static} There are many
existing documents related to improving safety and security in IoT
software (e.g. \cite{Chen:2011:DAS, Medwed:2016:ISC,
  KUMAR:2019:cloud-security, Chakkaravarthy:2019:malware-analysis}),
and even more on static source code analysis in general
(cf. \cite{Gomes2009AnOO, GosevaPopstojanova2015OnTC,
  Binkley:2007:SCA} and many others). %

Several conferences are dedicated to static analysis\footnote{The
  25\textsuperscript{th} Static Analysis Symposium happened in
  august 2018, see
  \bmurl{http://staticanalysis.org/sas2018/sas2018.html}; most ACM
  SIGPLAN conferences such as POPL, PLDI, ICFP, OOPSLA, LCTES, SPLASH,
  DSL, CGO, SLE... have papers related to static source code
  analysis.}.  All dominant C compilers (notably GCC and Clang, but
also MicroSoft's \emph{Visual C}\texttrademark) are using complex
static source code analysis techniques for optimizations and warnings
purposes (and that is why C compilers are monsters~\footnote{see
  \bmurl{https://softwareengineering.stackexchange.com/a/273711/40065}
  for more.}). It is wisely noticed (in
\cite{GosevaPopstojanova2015OnTC}) that \textbf{state-of-the-art
  static source code analysis tools are \emph{not} very effective in
  detecting \index{vulnerability!security} security
  vulnerabilities}~\footnote{Se we can only hope an \emph{incremental}
  progress in that area. Static source code analysis in
  \textsc{Chariot} won't make miracles.}, so they are not a ``silver
bullet'' \index{silver bullet} (\cite{Brooks:1987:NSB}). Many
taxonomies of software defects \index{defect!software} already exist
(e.g. \cite{Silva:2016:SES, Wagner:2008:DCD, Levine:2009:DDE}
etc....), notably for IoT\index{IoT} (see \cite{Carpent:2018:RRA,
  Ahmad:2018:ModelBasedIoT, Laszlo:2017:Vessedia}); however the
relation between an explicit defect and a source code property is
generally fuzzy, or ill-defined.

Observe that, while Debian and several other Linux distributions are
packaging many thousands of C or C++ programs and libraries and
several free software source code analyzers (notably \textsc{Frama-C}
and \textsc{Clang} tools and \textsc{Coccinnelle}), very few Debian
packages -coded in C or C++ for example- are conditionnally
``build-depending''\footnote{The Debian packaging system is
  sophisticated enough to just \emph{suggest} a tool useful to
  \emph{build} a package from its source code.} on them. This could be
explained by the practical difficulties, for Debian developers or
packagers, to effectively use these source code analyzers. Large C or
C++ Linux-related software - such as the Linux kernel, standard or
widely used C or C++ libraries (including \texttt{libcurl},
\textsc{Qt}, \textsc{GTK}, \textsc{libz}, \textsc{OpenSSL}, etc...),
Firefox, Libreoffice, various interpreters (Python, Guile), runtime
(Ocaml's or SBCL's ones) or compilers (GCC, Clang) etc... are still
not really analyzable automatically today, in a cost-effective and
time-efficient manner. But Debian cares a lot about software quality
and stability, so when automatic tools are available and
\emph{practically} useful, they \emph{are} used! The same observation
holds even for specialized Linux distributions\footnote{The Raspbian
  distribution is a typical example, see \bmurl{https://raspbian.org/}
  for more. But look also into
  \bmurl{https://www.automotivelinux.org/} or
  \bmurl{https://www.genivi.org/} as another examples.} used in many
non-critical embedded and connected IoT systems.


Language specifications and their implementations allow weird
behavior; for example, simply testing in \emph{C++} or \emph{C} code
an unitialized `bool` variable may crash the entire program (as
explained \href{https://stackoverflow.com/a/54125820/841108}{here}),
even if implementations doing so are not common (but definitely could
happen in the IoT world with DSP embedded processors with VLIW
architecture), related to so called \emph{trap representations}
permitted by language standards (see \cite{CplusPlus11:std,
  C11:std}). Also, some implementations of C have
\texttt{sizeof(char)}, \texttt{sizeof(int)}, \texttt{sizeof(long)},
\texttt{sizeof(void*)} and \texttt{alignof(char)},
\texttt{alignof(long)} being one (e.g. on word-addressable but not
byte-addressable Harvard architectures). \index{ia-32@\textsc{ia-32}
  architecture} \index{x86@\textsc{x86} architecture}. The common
Intel x86 \textsc{ia-32} bits processor architecture (still used in
\href{https://en.wikipedia.org/wiki/Vortex86}{\textsc{Vortex86}
  chips}) allow -with some runtime performance penalty- access to
misaligned 64 bits floating point numbers, but the same C code would
crash on e.g. \index{arm@\textsc{arm} architecture}
\href{https://en.wikipedia.org/wiki/ARM_architecture}{\textsc{Arm}}
systems, such as \index{raspberrypi@\textsc{RaspBerryPi} system}
\href{https://raspberrypi.org/}{\textsc{RaspBerryPi}} boards. Of
course \index{endianness}
\href{https://en.wikipedia.org/wiki/Endianness}{endianness} matters a
lot in any IoT devices and is very important in binary communication
protocols
(e.g. \href{https://en.wikipedia.org/wiki/Serial_ATA}{\textsc{Sata}}
\index{sata@\textsc{Sata} protocol},
\href{https://en.wikipedia.org/wiki/Ethernet}{\textsc{Ethernet}}
\index{ethernet@\textsc{Ethernet} protocol} or
\href{https://en.wikipedia.org/wiki/IEEE_802.11}{\textsc{Ieee 802.11}}
\index{ieee802@\textsc{Ieee 802.11} protocol} \index{wifi}
\textsc{Wifi}, \textsc{Li-Fi} (see \cite{Khandal:2014:lifi})
\index{lifi@\textsc{Li-Fi} protocol} or \index{usb@\textsc{Usb}
  protocol} \href{https://en.wikipedia.org/wiki/USB}{USB} or in the
automotive industry the
\href{https://en.wikipedia.org/wiki/CAN_bus}{\textsc{CAN} bus}. It
also matters in network protocol stacks, including
\index{ip@\textsc{Ip} protocol}
\href{https://en.wikipedia.org/wiki/Internet_protocol_suite}{\textsc{Ip}}
(see \cite{Cerf:2005:protocol}) or \index{asn1@\textsc{ASN-1}}
\href{https://en.wikipedia.org/wiki/ASN.1}{\textsc{Asn-1}} (see
\cite{Barry:1992:ASN1}), used in cryptographic certificates (such as
\href{https://en.wikipedia.org/wiki/X.509}{X.509} for
\index{x509@\textsc{X.509} protocol}
\href{https://en.wikipedia.org/wiki/HTTPS}{\textsc{Https}}
\index{https@\textsc{Https} protocol} secure web servers. The recent
\href{https://en.wikipedia.org/wiki/HTTP/2}{\textsc{Http/2}} web
protocol is a binary one and requires to care about endianness also.
\index{Xwin@\textsc{X11} window system}
\href{https://en.wikipedia.org/wiki/X_Window_System_protocols_and_architecture}{X
  Window System protocols}, \index{Wayland@\textsc{Wayland} display
  server}
\href{https://en.wikipedia.org/wiki/Wayland_(display_server_protocol)}{\textsc{Wayland}
  display protocols} \index{ssh@\textsc{Ssh} secure shell}
\href{https://en.wikipedia.org/wiki/Secure_Shell}{SSH},
\index{rfb@\textsc{Rfb} - remote framebuffer protocol}
\href{https://en.wikipedia.org/wiki/RFB_protocol}{\textsc{Rfb}
  protocol} are also binary, with endianness issues, and extremely
popular in non-critical IoT systems based on Linux. For multimedia
connected consumer devices,
\href{https://en.wikipedia.org/wiki/HDMI}{\textsc{Hdmi}} on the
hardware side, and
\href{https://en.wikipedia.org/wiki/MPEG-4}{\textsc{Mpeg-4}} for
audio/video encoding are also binary protocols or encodings. The
\href{https://en.wikipedia.org/wiki/Ogg}{\textsc{Ogg} container
  format} is free of patent and should be prefered for audio
encoding. The many \index{jpeg@\textsc{Jpeg} image encoding}
\href{https://en.wikipedia.org/wiki/JPEG}{\textsc{Jpeg} digital image
  formats}, very common in digital consumer
photography\index{photography!digital}, needs also endian-sensitive
binary processing, and is increasingly used in most IoT connected
cameras (presumably Linux based), some of which are still designed in
Europe.

\medskip

Static source code analysis tools \index{static analysis!tool} can -generally speaking-
be~\footnote{This is a gross simplification! In practice, there is a
  continuous spectrum of source code analyzers, much like there is a
  spectrum between compilers and interpreters (with e.g. bytecode or
  JIT implementations sitting in between compilation and naive
  interpretation).} viewed as being of one of two kinds:

\begin{itemize}
  \item strongly formal methods\index{formal
    methods}\index{methods!formal} based, semantically oriented,
    ``sound'' tools (e.g. built above abstract interpretation -cf.
    \cite{Cousot:2014:AIP,CousotCousot77-1}-, model checking -cf.
    \cite{Schlich:2010:MCS, Siddiqui:2018:adv-soft-model-check} and
    \cite{Jhala:2009:SMC}-, and other formal techniques on the whole
    program... See also \cite{Andreasen:2017:SAI}) which can give
    excellent results but require a lot of expertise to be used, and
    may take a long time to run~\footnote{There are cases where those
      static analyzers need weeks of computer time to give interesting
      results.}. For examples, \emph{Frama-C} (cf
    \cite{Cuoq:2012:Frama-C}), \emph{Astrée} (cf
    \cite{Mine:2015:TIU}), \emph{Mopsa} (cf \cite{Mine:2018:Mopsa})
    etc... The expert \index{expert!software engineering} user needs
    either to explicitly annotate the analyzed source code (e.g. in
    ACSL for \emph{Frama-C}, see \cite{Baudin:2018:ACSL,
      Delahaye:2013:CSL, Amin:2017:LAW}), and/or cleverly tune the
    many configuration knobs of the static analyzer, and often
    both. Often, the static analyzer itself has to be extended to be
    able to give interesting results on one particular analyzed source
    code~\footnote{The \emph{Astrée} project can be seen as the
      development of a powerful analyzer tool \emph{specifically}
      suited for the needs of Airbus control command software; it
      implements many complex abstract interpretation lattices wisely
      chosen to fit the relevant traits of the analyzed code. Neither
      \emph{Astrée} nor \emph{Frama-C} can easily -without any
      additional tuning or annotations- and successfully be used on
      most Linux command line utilities (e.g. \texttt{bash},
      \texttt{\emph{coreutils}}, \texttt{\emph{binutils}},
      \texttt{gcc}, ...)  or servers (e.g. \texttt{systemd},
      \texttt{lighttpd}, \texttt{Wayland} or \texttt{Xorg}, or IoT
      frameworks such as MQTT...). But \emph{Frama-C} can be extended
      by additional plugins so is a \emph{framework} for sound static
      analysis.}, when that analyzed code is complex or quite
    large. Many formal static analyzers
    (e.g. \cite{Greenaway:2014:DSS, Vedala:2012:ADP}) focus on
    checking just \emph{one} aspect or property of security or
    safety. Usually, formal and sound static analyzers can practically
    cope only with small
    sized analyzed programs of at most one or a few hundred thousands
    lines of C code (following some \emph{particular} coding style or
    using some definable \emph{subset} of the C language\footnote{For
      instance, both \emph{Frama-C} and \emph{Astrée} have issues in
      dealing with standard dynamic C memory allocation above
      \texttt{malloc}; since they target above all the safety critical
      real-time embedded software market where such allocations are
      \emph{forbidden}.}). Some formal analysis approaches include a
    definition of a strict subset of \emph{C}, thru perhaps some
    automatically generated code (cf. \cite{Bhargavan:DFHPRR17}) from
    some DSL.  In practice, the formal sound static analyzers are able
    to prove \emph{automatically} some \emph{simple} properties of
    small, highly critical, software components (e.g. avoiding the
    need of \emph{unit testing} at the expense of very \emph{costly
      software development efforts}).

  \item lightweight ``syntax'' oriented ``unsound'' tools, such as
    Coverity Scan~\footnote{See \bmurl{https://scan.coverity.com/}} or
    Clang-Analyzer, or even recent compilers (GCC or Clang) with all
    warnings and link-time optimization~\footnote{Link-time
      optimization (e.g. compiling and \emph{linking} with \texttt{gcc
        -O2 -flto -Wall -Wextra} using GCC) slows down the build time by more than a
      factor of two since the intermediate internal representation (IR) of the
      compiler (e.g. Gimple \index{Gimple} for \emph{GCC}, see \cite{gcc-internals} \S{12}) is kept in object files and
      reload at ``link-time'' which is done by the \emph{compiler}
      working on the whole program's IR, so is rarely used.}  enabled. Of
    course, these simpler approaches give many false positive warnings
    \index{machine learning}
    (cf \cite{Nadeem:2012:HFP}), but \textbf{machine learning} techniques (cf
    \cite{Perl:2015:VFP, flach:2012:machine-learning, shalev:2014:understanding-machine-learning}) using bug databases could help.
    
\end{itemize}

A generalization of strictly static source code analysis enables a
mixed, semi-static and semi-dynamic approach, but leverages on
extending some existing \emph{compilers} (such as \texttt{gcc} or
\texttt{clang}...), linkers (e.g. \texttt{ld} started by
\texttt{g++}), or even run-time loaders (e.g. \texttt{ld-linux.so} or
\emph{crt0}): inserting some runtime checking code into the compiled
executable, during compilation time or at link time\footnote{That
  could even be at dynamic-link time, e.g. in \texttt{ld-linux.so}
  just before running \texttt{main} in some C or C++ program.}. This
is the design idea of widely used tools such as the \texttt{valgrind}
memory checker\footnote{See \bmurl{http://valgrind.org/}, and be aware
  that \texttt{valgrind} is capable of runtime checking many other
  properties, such as \emph{some} race conditions\index{race
    condition} or other \emph{undefined behavior}\index{undefined
    behavior}.} or the address sanitizer (see
\cite{Serebryany:2012:Asan}) originally in {Clang}, and now also in
\emph{GCC}. Today, both \texttt{gcc} and \texttt{clang} have several
\index{sanitizer!compiler} \index{compiler sanitizer} \emph{compiler
  sanitizers} with such an approach. Some of them are very intrusive
because they slow down the debugged program run time by an important
factor of at least 10x, others are almost imperceptible, since they
may increase memory consumption by perhaps 25\% at runtime, but CPU
time by just a few percents. Some specialized semi-static source code
analyzers also adopt a similiar instrumenting approach (for example,
\cite{Biswas:2017:VVV}). Most sanitizers\footnote{Since our
  \emph{Bismon} framework is becoming capable of customizing
  \emph{GCC} by generating ad-hoc plugins, it could be later used in
  such a way too, to easily develop ad-hoc and \emph{project-specific}
  compiler sanitizers.} are whole-program\footnote{That
  ``whole-program'' holistic aspect is shared by most static source
  code analyzers, such as \emph{Clang-analyzer} or \emph{Frama-C} and
  is of course the major selling point of our \emph{Bismon}
  framework.} tools and need some operating system kernel at runtime,
but they provide yet another effective tool to embedded software
developers.

\medskip

Most (fully) static\footnote{Some compiler sanitizers,
  i.e. semi-static analyzers, may also require user interaction, but
  that is generally done thru ad-hoc source code annotations such as
  \texttt{\#pragma}-s.} source code analyzers require some kind of
interaction with their user (cf \cite{Lipford:2014:ICA}), in
particular to present partial analysis results and explanations about
them, or complex information like control flow graphs, derived
properties at each statements.

The \href{http://vessedia.eu/}{\textsc{Vessedia}} \index{Vessedia@\textsc{Vessedia}} project is an H2020 \index{h2020@\emph{\textsc{h2020}}}
IoT-related project~\footnote{The \textsc{Vessedia} project (Verification
  Engineering of Safety and Security Critical Industrial Applications)
  has received funding from the European Union's Horizon 2020 research
  and innovation programme under grant agreement No. 731453, within
  the call H2020-DS-LEIT-2016, started in january 2017, ending in
  december 2019.} which is focusing on a strong formal methods
approach for IoT \emph{software} and insists on a ``single system
formal verification'' approach (so it makes quite weak hypothesis on
the ``systems of systems'' view); it ``aims at enhancing safety and
security of information and communication technology (ICT) and
especially the Internet of Things (IoT). More precisely the aim of
[the VESSEDIA] project consists in making formal methods more
accessible for application domains that want to improve the security
and reliability of their software applications by means of Formal
Methods''~\footnote{Taken from
  \bmurl{https://vessedia.eu/about}}. Most \textsc{Vessedia} partners
(even the industrial ones, cf. \cite{Berkes:2018:Vessedia-approach}) are versed in formal static analysis
techniques (many of them being already trained to use \emph{Frama-C}
several years before, and several of them contributing actively to
that tool.). Some of the major achievements of \textsc{Vessedia}
includes formal (but \emph{fully automatic}) proofs of often
\emph{simple} (and sometimes very complex and very specific)
properties of some basic software components (e.g. lack of undefined
behavior in the memory allocator, or the linked list implementation,
of Contiki). Some automatically proven properties can be very complex,
and the very hard work~\footnote{In terms of human efforts, the
  formalization of the problem, and the annotation of the code and
  guidance of the prover, takes much more time and money (often more
  than a factor of 30x) than the coding of the C code. Within
  \textsc{Chariot} no large effort is explicitly allocated for such
  concrete but difficult tasks.}  is in formalizing these properties
(in terms of C code!)  and then in assisting the formal tool to prove
them.


In contrast, \textsc{Chariot} focuses mainly on a \emph{systems of
  systems} (e.g. networks of systems and systems of networks)
approach, so~\footnote{Taken in october 2018 from \bmurl{https://www.chariotproject.eu/About}, \emph{\S Technical Approach}.}
``aims to address how safety-critical-systems should
be securely and appropriately managed and integrated with a fog
network made up of heterogeneous IoT devices and gateways.''. Within
\textsc{Chariot}, static analysis methods have to be ``simple'' and
support its \emph{Open IoT Cloud Platform} thru its \emph{IoT Privacy,
  Security and Safety Supervision Engine} \index{IPSE}~\footnote{Taken
  from \bmurl{https://www.chariotproject.eu/About/}}, and some
industrial \textsc{Chariot} partners, while being IoT network and
hardware experts, are noticing that their favorite IDE (provided by
their main IoT hardware vendor) is running some GCC under the hoods
during the build of their firmware, but are not used to static source
code analysis tools. The \textsc{Chariot} approach to static source
code analysis does \emph{not} require the same level of expertise as needed for
the \emph{Verified in Europe} label pushed by the \textsc{Vessedia}
project.

Non-critical~\footnote{In this report, a critical industrial software
  is a piece of embedded code whose \emph{direct} failure impacts
  \emph{human life} (e.g. train braking system, but not its preventive
  maintenance), or \emph{costly industrial installations}
  \index{critical software} (e.g. entire oil platforms, large power
  plants) involving large equipement costing many dozens of M€;
  anything else is non-critical \index{non-critical system}: air
  conditioning of a office building, measurement of brake wear on a
  train for preventive maintenance optimization, door opening
  automation in an airport which can be quickly disabled in emergency
  cases, etc...}, but communicating, industrial IoT is programmed in
various languages\footnote{See
  \bmurl{https://www.iotforall.com/2018-top-3-programming-languages-iot-development/}
  for more.}: when a non-critical equipement should be autonomous so
needs to consume very little energy, programming it in C, C++ or Rust
is preferable (think of smart watches and similar wearables increasing
worker productivity). When such a non-critical computing device is
part of some larger equipement requiring constant and significant
electric power (automatic expressway tollgate, some smart sensors in
an oil refinery, high-end digital oscilloscopes, office
air-conditioning facilities, etc...) it could make sense to code it
in a higher-level language, such as C++, Java, Python, Lua, JavaScript \ldots making
the embedded software developer more productive when producing code
for industrial systems built in small series.

\medskip

The \textbf{\textsc{Chariot} approach} to static source analysis
\textbf{leverages on} an \textbf{\emph{existing}} \emph{recent}
\textbf{GCC cross-compiler}~\footnote{The actual version and the
  concrete configuation of \emph{GCC} are important; we want to stick
  -when reasonably possible- to the latest GCC releases, e.g. to
  \href{https://gcc.gnu.org/gcc-10/}{GCC 10} in summer 2020. In the
  usual case, that \emph{GCC} is a cross-compiler. In the rare case
  where the IoT system runs on an x86-64 device under Linux, that
  \emph{GCC} is not a cross-, but a straight compiler.} so focuses on
GCC-compiled languages\footnote{The 2019
  \href{https://gcc.gnu.org/}{Gnu Compiler Collection} is able to
  compile code written in C, C++, Objective-C, Fortran, Ada, Go,
  and/or D.}. Hence, the IoT software developer following the
\textsc{Chariot} methodology would just add some additional flags to
\emph{existing} \texttt{gcc} or \texttt{g++} cross-compilation
commands, and needs simply to change slightly his/her build automation
scripts (e.g. add a few lines to his \texttt{Makefile}). Such a gentle
approach (see figure \ref{fig:chariotcompil}) has the advantage of not
disturbing much the usual developer workflow and habit, and addresses
also the \emph{junior} IoT software developer. Of course the \emph
{details} of compilation commands would change, the commands shown in
the figure \ref{fig:chariotcompil} are grossly simplified! The
compilation and linking processes are communicating -via some
additional \emph{GCC} plugins (cf. \cite{gcc-internals} \S24) doing
inter-process communication- with our \index{persistent monitor}
\index{persistent!monitor} \emph{persistent monitor}, tentatively
called \texttt{bismon} \index{Bismon}. It is preferable (see
\cite{gcc-runtime-library-exception}) to use free software GCC plugins
(or free software generators for them) when compiling proprietary
firmware with the help of these plugins; otherwise, there might
be~\footnote{Of course, I -Basile Starynkevitch- am not a lawyer, and
  you should check any potential licensing issues with your own
  lawyer.}  some licensing issues on the obtained proprietary binary
firmware blob, if it was compiled with the help of some hypothetical
\emph{proprietary} GCC plugin. The insight driving the \texttt{bismon}
tool is the hope to provide small IoT software development teams with
a semi-automatic assistant working in parallel with the developers and
improving communication between team members, later enabling some
limited software features extraction (see
\cite{Asanovic:2006:landscape, Brooks:1987:NSB, Brooks:1995:MM,
  zuboff:2015:big-other, Perez:2020:query-reformul}).

\begin{figure}[h]
  \begin{center}
    \bmincludewidthgraphics{0.85\textwidth}{chariot-compil-fig}{eps}{svg}
  \end{center}
  \caption{the \textsc{Chariot} compilation of some IoT firmware or
    application {\textbf{(simplified)}}}
  \label{fig:chariotcompil}
\end{figure}

%No \textsc{Chariot} industrial
%partner have any prior extensive experience of static formal-methods
%based source code analysis techniques and tools such as
%\emph{Frama-C}. Most of them don't even build their firmware on a
%Linux workstation (but depend on some proprietary IDE containing an
%obsolete version of \emph{GCC} and have to run that on Windows.).

\subsubsection{The power of an existing compiler: GCC}

\textsc{Chariot} static analysis tools will leverage on the mainstream
\textsc{Gcc}~\footnote{``Gnu Compiler Collection''. See
  \bmurl{http://gcc.gnu.org/} for more. In practice, it is useful to
  build a recent \textsc{Gcc} cross-compiler, fitted for your IoT
  system, from its published source code - see
  \bmurl{https://gcc.gnu.org/mirrors.html} for a list of mirrors.}
compiler (generally used as a
\emph{\index{compiler}\index{cross-compiler}cross-compiler} for IoT
firmware development) Current versions of \emph{GCC} (that is, GCC 8.2
as of September 2018) are capable of quite surprising optimizations
(internally based upon some sophisticated static analysis techniques
and advanced heuristics). But to provide such clever optimizations,
the \textbf{\emph{GCC} compiler has to be quite a large software, of
  more than 5.28 millions lines}~\footnote{Measured by
  \href{https://dwheeler.com/sloccount/}{David Wheeler's
    \texttt{sloccount}} utility} of source code (in
\texttt{gcc-8.2.0}, measured by \texttt{sloccount}). This figure is an
under-estimation~\footnote{The Unix \texttt{wc} utility gives 14.6
  millions lines, including empty ones but excluding generated C++
  code, in 498 megabytes.}, since \emph{GCC} contains a \emph{dozen of
  domain specific languages} and their transpilers to generated C++
code, which are not well recognized or measured by \texttt{sloccount}.


\medskip

We show below several examples of optimizations done by recent
\emph{GCC} compilers. Usually, these optimizations happen in the
middle-end and work on internal intermediate representations which are
mostly not~\footnote{Most of the internal \emph{GCC} representations
  -e.g. \emph{Gimple} or \emph{SSA}- are common to all target systems;
  however, some constants, like the size and alignment of primitive
  data types such as \texttt{long} or pointers, are known at
  preprocessing phase or at early \emph{Gimplification} phase.} target
specific.

\bigskip

\bigskip

{{\raisebox{3pt}{\textcolor{brown}{\rule{0.2\textwidth}{2.0pt}}}} ~ \large{recursive inlining with constant folding}}



\begin{table}[!htbp]
\caption{\label{tab:factinlinecsrc} recursive inlining with constant folding in \emph{GCC} (C source)}
   \medskip
  \begin{center}
    \begin{relsize}{-1.2}
     \begin{tabular}{c}
      \lstinputlisting[language=C]{examples/factinline12.c} \\ 
       \textbf{\emph{C source code}} \\ 
       \hline
     \end{tabular}
    \end{relsize}
  \end{center}
\end{table}

The table \ref{tab:factinlinecsrc} shows a simple example of C code
(file \texttt{factinline12.c}). After preprocessing and parsing, it
becomes quickly expanded in some \emph{Gimple}\index{gimple}
representation (cf. \S{12} of \cite{gcc-internals}), whose elementary
instructions are arithmetic with two operands, or simple tests with
jumps, or simple calls (in so called \emph{A-normal form}
\index{A-normal form}, where nested calls like \verb+a=f(g(x),y);+ get
transformed into a sequence introducing a temporary $\tau$ such as
$\tau$\verb+=g(x)+ then \verb+a=f(+$\tau$\verb+,y)+, etc...), shown in
table \ref{tab:factinlinegimple}.

\input{generated/002-gimple-factinline.tex}

This is a textual (and quite
\emph{incomplete} since a partial view of some) dump of some in-memory
\emph{internal intermediate representation} during compilation. What
really matters to the \textsc{Chariot} static source code analyzer
framework is the data inside the compilation process \texttt{cc1}, not
its partial textual dump~\footnote{It is possible to pass the
  \texttt{-fdump-tree-all} flag to \texttt{gcc}; then hundreds of
  intermediate textual dump files are emitted, including
  \texttt{factinline12.c.004t.gimple} and
  \texttt{factinline12.c.020t.ssa} and many others for the compilation
  of \texttt{factinline12.c} source file.}. The \emph{Gimple} internal
in-memory representation is declared inside several source files of
\emph{GCC}, including its \texttt{gcc-8*/gcc/gimple.def},
\texttt{gcc-8*/gcc/gimple.h},
\texttt{gcc-8*/gcc/gimple-iterator.h}, etc...


After gimplification, many other optimizations happen. \textbf{The
  \emph{GCC} compiler runs more than two hundred optimization passes
  !}\index{optimization}\index{pass!optimization}. The table
\ref{tab:factinlinessa} shows the ``static single assignment'' form
(SSA, see \cite{pop:ssa} and \cite{gcc-internals} \S{13}), where variables are duplicated so that each SSA
variable gets assigned only \emph{once}. The control flow is reduced
to \index{basic block} \emph{basic blocks} (with a single entry point
at start, and perhaps several conditional exit edges). Then special
$\phi$ nodes introduce places where such a variable may come from two
other ones (after branches).

\input{generated/003-ssaopt-factinline.tex}


At last, many other optimizations happen. And the optimized form in
table \ref{tab:factinlineoptim} shows that \texttt{fact12} just
returns the constant 479001600 (which happens to be the result of
\texttt{fact(12)} computed \emph{at compile-time}).

\newpage

Finally, the generated assembler code has no trace of \texttt{fact}
function, and contains just what is shown in table
\ref{tab:factinlineasm} (where many useless comment lines, giving the
detailed configuration of the cross compiler, have been removed).



\pagebreak



{{\raisebox{3pt}{\textcolor{brown}{\rule{0.2\textwidth}{2.0pt}}}} ~ \large{heap allocation optimization}}

\bigskip

Our second example shows that \emph{GCC} is capable of clever
optimizations around dynamic heap allocation and de-allocation. Its
source code in file \texttt{mallfree.c} is shown in table
\ref{tab:mallfreecsrc}.

\begin{table}[!htbp]
\caption{\label{tab:mallfreecsrc} optimization around heap allocation by \emph{GCC} (C source)}
   \medskip
  \begin{center}
    \begin{relsize}{-1.2}
     \begin{tabular}{c}
      \lstinputlisting[language=C]{examples/mallfree.c} \\ 
       \textbf{\emph{C source code}} \\ 
       \hline
     \end{tabular}
    \end{relsize}
  \end{center}
\end{table}

 The straight \emph{GCC} compiler~\footnote{Similar optimizations also
   happen with a GCC MIPS targetted cross-compiler.} (on Linux/x86-64)
 is optimizing and able to remove the calls to \texttt{malloc} and to
 \texttt{free}, following the \index{as-if rule} \href{https://en.wikipedia.org/wiki/As-if\_rule}{\emph{as-if rule}}.

 %\smallskip

The \emph{Gimple} form shown in table
\ref{tab:mallfreegimple}. Pointer arithmetic has been expanded to
target-specific \emph{address} arithmetic in byte units, knowing that
\texttt{sizeof(int)} is 4.

\include{generated/004-gimplessa-mallfree}

 \smallskip

\begin{table}[H]
\caption{\label{tab:mallfreegimple} optimization around heap
  allocation by \emph{GCC} (generated Gimple)}
   \medskip
  \begin{center}
    \begin{relsize}{-1.5}
     \begin{tabular}{c}
      \lstinputlisting[language=C]{generated/mallfree-gimple.c} \\ 
       \textbf{\emph{Gimple code}} \\ 
       \hline
     \end{tabular}
    \end{relsize}
  \end{center}
\end{table}

\medskip

The \emph{SSA/optimized} form appears in table
\ref{tab:mallfreeoptim}. It shows that the call to \texttt{malloc} and
to \texttt{free} have been optimized away, so the \texttt{weirdsum}
function don't use heap allocation anymore.

\begin{table}[H]
\caption{\label{tab:mallfreeoptim} optimization around heap allocation
  by \emph{GCC} (generated SSA/optimized)}
   \medskip
  \begin{center}
    \begin{relsize}{-1.5}
     \begin{tabular}{c}
      \lstinputlisting[language=C]{generated/mallfree-optimized.c} \\ 
       \textbf{\emph{SSA/optimized code}} \\ 
       \hline
     \end{tabular}
    \end{relsize}
  \end{center}
\end{table}

So the generated x86-64 assembler code in table \ref{tab:mallfreeasm}
contain no calls to \texttt{malloc} or \texttt{free}, hence contains the same code that would be generated from just \texttt{int weirdsum(int x, int y) \{return x+y;\}}.


\smallskip

\begin{table}[t]
\caption{\label{tab:mallfreeasm} optimization around heap allocation
  by \emph{GCC} (generated x86-64 assembly)}
   \medskip
  \begin{center}
    \begin{relsize}{-1.5}
     \begin{tabular}{c}
       %\lstinputlisting{language=[x64]Assembler}{generated/mallfree-tail.s} \\
       \begin{minipage}{0.8\textwidth}
         %\listinginput[4]{1}{generated/mallfree-tail.s}
         \VerbatimInput{generated/mallfree-tail.s}
       \end{minipage} \\
       \textbf{\emph{x86-64 assembly}} \\ 
       \hline
     \end{tabular}
    \end{relsize}
  \end{center}
\end{table}

\medskip

This \texttt{mallfree.c} example could look artificial (because human
developers won't \emph{directly} code this way). However, a similar
example might happen in real life after preprocessor expansion and
inlining in large header-mostly libraries. Also, equivalent code
happens (perhaps after some inline expansion done by any optimizing
compiler) with machine generated C code (e.g. by tools like
\href{https://antlr.org/}{\textsc{Antlr}} or
\href{https://www.gnu.org/software/bison/}{\textsc{Bison}} parser
generators, in some \href{http://json.org/}{\textsc{Json}} libraries
or \href{https://www.jsonrpc.org/}{\textsc{JsonRpc} services}) In
addition, most genuine C++11 \index{C++11} code (e.g. using standard
container \index{container!C++} templates from \texttt{<map>} or
\texttt{<vector>} standard headers) would produce conceptually similar
code (since many standard constructors and destructors would call
internally the standard \texttt{::operator new} and \texttt{::operator
  delete} operations, which get inlined into calling the system
\texttt{malloc} and \texttt{free} functions).

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsubsection{Leveraging simple static source analysis on \emph{GCC}}
\label{subsubsec:leveraging-static-analysis}

By hooking through \textsc{Chariot} specific GCC
\emph{plugins}~\footnote{Notice that GCC plugins work mostly on Linux
  -but not really on Windows-, so this explains the \textsc{Chariot}
  requirement of [cross-]compiling IoT firmware on a Linux
  workstation.}  into usual [cross-] \emph{compilation} processes
(some \texttt{gcc} or \texttt{g++}, etc... such as a
\texttt{mips-linux-gnu-gcc-8} or a \texttt{arm-linux-gnueabi-g++-8},
etc...), IoT software developers will be able to take advantage of all
the numerous optimizations and processing done by \emph{GCC}. However,
a typical firmware build would take many dozens of such compilation
processes, since every translation unit (practically \texttt{*.c} C
source files and \texttt{*.cc} C++ source files of the IoT firmware)
requires its compilation process~\footnote{Technically, a C
  compilation process would be running some \texttt{cc1} internal
  executable started by some \texttt{*gcc*} [cross-] compilation
  command.}. In practice, IoT software developers would use some
\emph{existing} \textbf{build automation} tool (such as \texttt{make},
\texttt{ninja}, \texttt{meson}, \texttt{cmake} etc...)  \index{build
  automation} which is running suitable compilation commands. They
would need to adapt~\footnote{How to adapt cleverly their
  \texttt{Makefile} to take advantage of \textsc{Chariot} provided
  static analysis is of course the responsability of the IoT
  developer. Surely several extra lines are needed, and the
  \texttt{CFLAGS=} line of their \texttt{Makefile} should be
  changed. For other builders such as \texttt{ninja}, etc..., some
  similar configuration changes would be needed.}  and configure their
build process (e.g. by editing their \texttt{Makefile}-s, etc...),
notably to fetch their \emph{GCC} plugin C++ code and compile it into
some \texttt{*.so} shared object to be later \texttt{dlopen}-ed by
some cross-compiler \texttt{cc1} process, and to use these plugins in
their cross-compilation of their IoT firmware. By working in
cooperation with existing \emph{GCC} compilation tools, the IoT
developer don't have to change much his/her current development
practices. However, these various compilation processes are producing
partial new (or updated) internal representations, and need to know
about other translation units. So some \textbf{persistence is needed}
to keep some data (such as the control flow graph, etc...) related to
past~\footnote{Notice that recent \emph{GCC} provide a link-time
  optimization (LTO) ability, if the developer compiles \emph{and
    links} with e.g. \texttt{gcc -O2 -flto}. But LTO is not widely
  used since it slows down a lot the building time, and the plugin
  infrastructure of GCC is not very LTO friendly and would be brittle
  to use. At last, there won't be any practical user interface with
  such an approach. So persistence is practically needed, both without
  LTO and if using LTO.}  compilation processes during perhaps the
entire project development work.

IoT developers need to interact with their static source code analysis
(\emph{GCC} based) tool. In particular, they might need to understand
more the optimizations done by their (\textsc{Chariot} augmented, thru
\emph{GCC} plugins) compiler, and they also need to be able to query
some of the numerous intermediate data related to that static analysis
and compilation. Practically, a small team of IoT developers working
on the same IoT firmware project would interact with the static
analysis infrastructure, that is with a single \emph{persistent
  monitor} process. That \textbf{persistent monitor} (\emph{Bismon})
would be some ``server-like'' program, started probably every working
day in the morning and loading its previous state, and gently stopped
every evening and dumping its current state on disk. It needs to keep
its persistent state in some files. For convenience, a textual format
is preferable~\footnote{This is conceptually similar the the SQL dump
  files of current RDBMS. But of course \emph{Bismon} don't use an SQL
  format, but its own textual format.}. These persistent store files
could (and actually should) be regularly backed up and kept in some
version control system.

Since a single \emph{Bismon} process is used by a small team of IoT
developers, it provides some web interface\index{web interface}: each
IoT developer will interact with the persistent monitor through his/her
web \index{browser} browser~\footnote{We don't aim compatibility with
  all web browsers -including old ones- but just with the latest
  \emph{Chrome} (v.70 or newer) and \emph{Firefox} (v.63 or newer)
  browsers, using HTML5, JavaScript, WebSockets, AJAX
  technologies.}. In addition, a static analysis expert (which could
perhaps be the very senior IoT developer of the team) will configure
the static analysis (also through a web interface).

The figure \ref{fig:bismonit} gives an overall picture: on the top,
both Alice and Bill are working on the same IoT project source code
(and each have a slightly different version of that code, since Alice
might work on routine \texttt{foo\_start} in file \texttt{foo.cc},
while Bill is coding the routine \texttt{bar\_event\_loop} in file
\texttt{bar.c}). Both Alice and Bill (IoT developers in the same team,
working on the same IoT firmware) are compiling with the same
\emph{GCC} cross-compiler (the GCC egg) enhanced by a plugin (the
small green puzzle piece, at right of GCC eggs). They use their
favorite editor or IDE to work on the IoT source code, and run from
time to time a builder (e.g. \texttt{make}). They use a browser (with
a rainbow in the figure) to interact with the monitor and query static
analysis data. The purple dashed arrows represent HTTP exchanges
between their browser and the monitor. The compilation processes,
extended by the GCC plugin, communicate with the monitor (thru the
gray dashed arrows). A static analysis expert (the ``geek'', at left
of the Bismon monitor) is configuring the monitor thru his own web
interface. The monitor is \emph{generating} (orange arrow) the C++
code for GCC plugins (small blue hexagon at right), and the IoT
developer needs to change his/her build procedures to compile and use
that generated GCC plugin. \emph{Bismon} also uses meta-programming
techniques to emit (curved blue arrow to left) internal code (bubble)
- notably C code dynamically loaded by the monitor and JavaScript/HTML
used in browsers. The several ``Tux'' penguins remind that all
this (cross-compilers, builders, the persistent monitor, etc...)
should run on Linux systems. The monitor persists its entire state on
disk, so can restart in the state that it has dumped in its previous
run.

\begin{figure}
  \begin{center}
    \bmincludewidthgraphics{0.85\textwidth}{bismon-monitor-fig}{eps}{svg}
  \end{center}
  \caption{The \emph{Bismon} monitor used by some IoT developer team following the \textsc{Chariot} approach.}
  \label{fig:bismonit}
\end{figure}

\newpage 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{Lessons learned from \textit{GCC MELT}}
\label{subsec:lessonsgccmelt}

Our previous \emph{GCC MELT} project (see \cite{Starynkevitch-DSL2011,
  Starynkevitch-GCCMELTweb, Starynkevitch2007Multistage}) provided a
bootstrapped Lisp-like dialect (called \emph{MELT}) to easily extend
\emph{GCC}. That Lisp-like dialect was translated to
\emph{GCC}-specific C++ code (in a transpiler itself coded in
\emph{MELT}). Then \emph{GCC MELT} gave us the following insights:

\begin{itemize}
  \item the \emph{GCC} software is a huge free software project (with
    several hundreds of contributors, many of them working on GCC at
    least half of their time), which is \emph{continuously}
    evolving. Following that evolution requires a significant effort
    by itself (see for example the mail traffic -of several hundreds
    messages monthly- on
    \href{https://gcc.gnu.org/ml/gcc/}{\texttt{gcc@gcc.gnu.org}} and
    \href{https://gcc.gnu.org/ml/gcc-patches/}{\texttt{gcc-patches@gcc.gnu.org}},
    and the amount of work shown at GCC summits or GNU Tools Cauldron,
    etc...). Switching to \emph{Clang} would also require a lot of
    efforts.


  \item pushing a patch or contribution inside \emph{GCC} is very
    demanding, since the community is quite strict (but that explains
    the quality of GCC).

  \item the \emph{GCC} plugin API~\footnote{including of course the
    API related to internal GCC representations, such as \emph{Gimple}
    or \emph{SSA}.} is not ``carved in stone'', and can evolve
    incompatibly from one release of \emph{GCC} to the
    next. Therefore, the C++ code of a plugin for \texttt{gcc-7} may
    require some (perhaps non-trivial) modifications to be usable on
    \texttt{gcc-8}, etc...

  \item a lot of C++ code (nearly two millions lines) was generated
    within our \emph{GCC MELT} project, and the compilation by
    \texttt{g++} into a shared object of that emitted C++ code was a
    significant bottleneck.

  \item Implementing a generational copying garbage collector above
    \emph{Ggc}~\footnote{This is the internal GCC garbage collector, a
      mark-and-sweep one which can run only \emph{between} GCC
      passes.} was challenging (debugging GC code takes a lot of time).

    \item Describing, in MELT, the interface to the
      many~\footnote{Current \emph{GCC-8} have several thousands
        \emph{GTY}-ed classes.} C++ classes internal to \emph{GCC}
      takes a lot of effort. Some automation would be helpful.

   \item In practice, whole-program static analysis requires a
     persistent system, since the ``link-time optimization'' ability
     of \emph{GCC} is not plugin-friendly and is very rarely used.
\end{itemize}

The final D1.3\textsuperscript{v2} document may add further relevant
items to the above list.

\medskip

\subsection{Driving principles for the  \textit{Bismon} persistent monitor}
\label{subsec:principles-bismon}

To enable whole program static source code analysis (for IoT software
developers coding in C or C++ on a Linux developer workstation), we
are developing \emph{Bismon}~\footnote{Notice \texttt{bismon} is a
  \textbf{temporary name} and could be changed, once we find a better
  name for it. Suggestions for better names are welcome.}, a
persistent monitor (free software, for Linux). It leverages above
existing recent \emph{GCC} [cross-] compilers.

%%%%%%%%%%%%%%%%

\subsubsection{About \emph{Bismon}}
\label{subsubsec:about-bismon}

\textit{Bismon} (a \emph{temporary
  name})\index{Bismon} is a free software (GPLv3+ licensed)\footnote{The
  source code is unreleased but available, and continuously evolving,
  on \bmurl{https://github.com/bstarynk/bismon}} static source code
whole-program analysis framework whose initial domain will be
\emph{Internet of Things} (or \index{IoT}{IoT})\footnote{IoT is viewed
  as the first application domain of \textit{Bismon}, but it is hoped
  that most of \textit{Bismon} could be reused and later extended for
  other domains}. It is designed to work with the \textit{Gcc}
compiler (see \bmurl{gcc.gnu.org}) on a Linux
workstation\footnote{Linux specific features are needed by
  \textit{Bismon}, which is unlikely to be buildable or run under
  other operating systems. My Linux distribution is
  \emph{Debian/Unstable}}. \textit{Bismon} is conceptually the
successor of \textit{GCC MELT} \footnote{The \textit{GCC MELT} web
  pages used to be on \texttt{gcc-melt.org} -a DNS domain relinquished
  in april 2018- and are archived on
  \bmurl{https://starynkevitch.net/Basile/gcc-melt}} (see
\cite{Starynkevitch2007Multistage, Starynkevitch-DSL2011}), but don't
share any code with it while retaining several principles and
approaches of \emph{GCC MELT}.

\textit{Bismon} is \textbf{work in progress}, and many things
described here (this preliminary draft D1.3~\textsuperscript{v1} of a
future report D1.3~\textsuperscript{v2} scheduled for M30 - in 2020)
are not completely implemented in 2018 or could drastically change
later.

\bigskip

\textit{Bismon} is (like \textit{GCC MELT} was) a \textbf{domain
  specific language}\footnote{See the
  \href{https://en.wikipedia.org/wiki/Domain-specific\_language}{\emph{Domain-specific
      language}} wikipage.} \index{DSL} \index{Domain-Specific Language!DSL} implementation, targetted to ease static
source code analysis (above the \textit{GCC} compiler), with the
following features:

\begin{itemize}

  \item \index{persistence}{\textbf{persistence}}\footnote{See the
    \href{https://en.wikipedia.org/wiki/Persistence\_(computer\_science)}{\emph{persistence}}
    wikipage.}, somehow \textit{orthogonal persistence}. It is needed
    in particular because compiling some software project (analyzed by
    \textit{Bismon}) is a long-lasting procedure involving
    \textit{several} compiling and linking processes and commands. So
    most of the data handled by \textit{Bismon} can be persisted on
    disk, and reloaded at the next run
    (cf. \cite{Dearle-2010-orthopersist,
      Dearle:2009:OrthogonalPR}). However, some data is temporary by
    nature~\footnote{E.g. data related to a web session, or to a web
      HTTP exchange, or to an ongoing \texttt{gcc} compilation
      process, etc... needs not to be persisted, and would be useless
      when restarting the \textit{Bismon monitor}.} and should not be
    persisted. Such data is called temporary or
    \index{transient}{\textbf{transient}}. But the usual approach is
    to run the \textit{Bismon} program from some initial loaded state
    and have it \index{dump}{\textbf{dump}} its memory state on
    disk~\footnote{Look also into Liam Proven FOSDEM 2018 talk about
      \emph{The circuit less traveled} on
      \bmurl{https://archive.fosdem.org/2018/schedule/event/alternative\_histories/}
      for an interesting point of view regarding persistent systems.}.
    before exiting (and reload that augmented state at the next run),
    and probably more often than that (e.g. twice an hour, or even
    every ten minutes).

  \item \textbf{dynamic typing}\footnote{See also the
    \href{https://en.wikipedia.org/wiki/Dynamic\_programming\_language}{\emph{dynamic
        programming language}} and
    \href{https://en.wikipedia.org/wiki/Dynamic\_typing}{\emph{dynamic
        typing}} wikipages.}, like many scripting
    languages\footnote{See the
      \href{https://en.wikipedia.org/wiki/Scripting_language}{\emph{scripting
          language}} wikipage.} (such as Guile, Python, Lua, etc). Of
    course the dynamically typed data inside the \textit{Bismon
      monitor} is \index{garbage collection}{\textbf{garbage
        collected}} (cf. \cite{Jones:2016:GC-handbook}). The initial
    GC of the monitor is a crude, mark and sweep, precise garbage
    collector, but multi-thread compatible (cf. \S\ref{subsec:gcvalobj}
    below); it uses a naive stop-the-world mark\&sweep algorithm. That
    GC should be replaced by a better one, such as
    \href{https://www.ravenbrook.com/project/mps/}{Ravenbrook MPS}
    \footnote{\label{fn:initial-gc} Improving that GC is a difficult
      work, and past experience on \emph{GCC MELT} taught us that
      developing and debugging a GC is hard, and is a good
      illustration of
      \href{https://en.wikipedia.org/wiki/Hofstadter's_law}{Hofstadter's
        law} (See \cite{Hofstadter:1979:GEB}). We should consider
      later using MPS from
      \bmurl{https://www.ravenbrook.com/project/mps/} -or maybe some
      other state of the art garbage collector, since MPS might become
      an orphaned free software project- but doing that could require
      recoding or regenerating \emph{a lot} of code, since MPS -like
      any other GC- has specific calling conventions and invariants,
      including
      \href{https://en.wikipedia.org/wiki/A-normal_form}{A-normal
        form}. So, switching to MPS or to any other good enough
      garbage collector in \emph{Bismon} would require at least
      several months of work. And, as an open-source project, MPS
      looks barely maintained in mid-2019.}  something better, if good
    performance and scalability is wanted in \emph{Bismon}. The hard
    point is the multi-threaded aspect of \emph{mutator
      threads}\footnote{In garbage collection parlance, a mutator
      thread is an applicative thread needing GC support, e.g. for
      allocation or updates of GC-ed memory zones.}\index{mutator
      thread}\index{thread!mutator} in that \texttt{bismon}
    program. For more details about the difficulty of clever
    trade-offs in such multi-threaded and user interaction-friendly
    garbage collectors, read carefully chapters 14 to 18 of
    \cite{Jones:2016:GC-handbook}.

  \item \textbf{homoiconicity}\footnote{See the
    \href{https://en.wikipedia.org/wiki/Homoiconicity}{\emph{homoiconicity}}
    wikipage.} and \textbf{reflection}\footnote{See the
    \href{https://en.wikipedia.org/wiki/Reflection\_(computer\_programming)}{\emph{reflection}}
    wikipage.} with \textbf{introspection}\footnote{See the
    \href{https://en.wikipedia.org/wiki/Self-awareness}{\emph{self-awareness}},
    \href{https://en.wikipedia.org/wiki/Type\_introspection}{\emph{type
        introspection}} and
    \href{https://en.wikipedia.org/wiki/Virtual\_machine\_introspection}{\emph{virtual
        machine introspection}} wikipages.} (cf
    \cite{Pitrat:1996:FGCS, Pitrat:1990:Metaconnaissances,
      Pitrat:2009:AST, Pitrat:2009:ArtifBeings,
      Doucet:2003:introspection, carle-1992-meringIV}): all the DSL
    code is explicitly represented as data which can be processed by
    \textit{Bismon}, and the current state (including even its
    continuation represented as a reified call stack, cf
    \cite{fouet-starynkevitch:describing-control:1987,
      fouet-1987:gosseyn, Starynkevitch-1990-EUM,
      Reynolds:1993:continuations} and \S\ref{subsubsec:bismon-dsl}) is
    accessible by the DSL.

    \item \textbf{translated}\footnote{See also the
      \href{https://en.wikipedia.org/wiki/Source-to-source_compiler}{\emph{source-to-source
          compiler}} (or \emph{transpiler}) wikipage.} to \emph{C}
      code; and \textbf{generated} \emph{JavaScript} + \emph{HTML} in
      the \index{browser}{browser}, and generated \emph{C++} code of
      \emph{GCC} plugins \index{plugin}

    \item \textbf{bootstrapped\footnote{Read the \href{https://en.wikipedia.org/wiki/Bootstrapping_(compilers)}{\emph{bootstrapping (compilers)}} and \href{https://en.wikipedia.org/wiki/Chicken\_or\_the\_egg}{\emph{Chicken or the egg}} wikipages.} implementation}: \index{bootstrap} (cf. \cite{Pitrat:1996:FGCS, Polito:2014:Bootstrapping-pharo})
      ideally, all of \textit{Bismon} code (including C code dealing
      with data representations, persistent store, etc...) should be
      generated (but that won't happen entirely with the
      \textsc{Chariot} timeframe). However, this ideal has not yet be
      attained, and there is still a significant amount of
      hand-written C code. It is hoped that most of the hand-written C
      code will eventually become replaced by generated C code.
      
    \item ability to \textbf{generate GCC plugins}: the C++ code of
      GCC plugins \index{plugin} performing static analysis of a single translation
      unit should be generated (this was also done in GCC MELT, see \cite{Starynkevitch-DSL2011}).

    \item with \textbf{collaborative web interface}\footnote{See also the \href{https://en.wikipedia.org/wiki/Web\_application}{\emph{web application}} wikipage, but \texttt{bismon} has highly specific pecularities, detailed more in \S\ref{subsec:webinterf} below.}, \index{web interface} used
      by a \emph{small} team of \emph{trusted and well-behaving}
      developers~\footnote{The initial \texttt{bismon} implementation
        had a hand-coded crude GTK interface, nearly unusable. That
        interface is temporarily used to fill the persistent store
        till the web interface (generated by \emph{Bismon}) is
        usable. The GTK interface is already obsolete and should
        disappear at end of 2018. The Web interface (work in
        progress!) is mostly generated - all the HTML and JavaScript
        code is generated (or taken from outside existing projects
        e.g. \href{http://jquery.com/}{\emph{JQuery}} or
        \href{http://codemirror.net/}{\emph{CodeMirror}}), and their
        HTML and JavaScript generators are made of generated C
        code.}. The users of \emph{bismon} are expected to trust each
      other, and to use the \texttt{bismon} tool
      responsibly\footnote{For example, each \emph{bismon} user has
        the technical ability to erase most of the data inside
        \textit{Bismon monitor}, but is expected to not do so. There
        is no mechanism to forbid or warn him doing such bad things.}
      (likewise, developers accessing a \texttt{git} version control
      repository are supposed to act responsibly even if they are
      technically capable of removing most of the source code and its
      history stored in that repository). So protection against
      malicious behavior of \texttt{bismon} users is out of scope.

      Since \textit{Bismon} should be usable by a small team of
      developers (perhaps two or a dozen of them)\footnote{So
        \textit{Bismon}, considered as a Web application, would have
        at most a dozen of \index{browser}{browsers} -and associated
        users- accessing it. Hence, scalability to many HTTP
        connections is not at all a concern (in contrast with most
        usual web applications).}, it is handling some \index{personal
        data}{personal data} (relevant to \index{GDPR}{GDPR}), such as
      the first and last names (or pseudos) of users and their email
      and maintain a password file (used in the Web
      \index{login}{login} form). Compliance to
      \index{regulation!compliance to} regulations (e.g. European GDPR
      \cite{voigt:2017:eu-gdpr, zuboff:2015:big-other}) is out of
      scope and should be in charge of the entities and/or persons
      using and/or deploying \textit{Bismon}. The login \index{login
        template} form template \footnote{on
        \bmurl{https://github.com/bstarynk/bismon/blob/master/login\_ONIONBM.thtml}}
      could and probably should be adapted on each deployment site (by
      giving there site-specific contacts, such as the GDPR data
      controller, and perhaps add corporate logos and social rules,
      etc...). We are sadly aware\footnote{Rabelais wrote in his
        \href{https://en.wikipedia.org/wiki/Gargantua\_and\_Pantagruel#Pantagruel}{\emph{Pantagruel}}
        :
        ``\href{https://www.linguee.com/french-english/translation/sciences+sans+conscience+n\%27est+que+ruine+de+l\%27\%C3\%A2me.html}{Science
          sans conscience n'est que ruine de l'âme}.''  and that very
        polysemic (so quite difficult to translate) sentence was
        written in 1532!} that a mature \textit{Bismon} system might
      -exactly like even \href{http://git-scm.com}{\texttt{git}}
      \index{git@\texttt{git}} could be, and for quite similar
      reasons- in the future be unethically \index{ethics} [ab-]used
      (as most current other
      \href{https://en.wikipedia.org/wiki/Distributed\_computing}{distributed}
      or \href{https://en.wikipedia.org/wiki/Cloud\_computing}{Cloud}
      digital technologies, \cite{thain:2005:distributed-computing,
        dikaiakos:2009:cloud, attiya:2004:distributed,
        peleg:2000:distributed}) in abusive ways (e.g. excessive
      \index{surveillance} surveillance
      \cite{helbing:2019:big-data-democracy, zuboff:2015:big-other,
        oneil:2016:weapons, huws:2015:icapitalism} of developers using
      it), especially when combined with other intrusive automated
      personel \index{personel} monitoring techniques, such as face
      recognition \index{face recognition} (cf
      \cite{jain:2011:face-recognition}), \index{email classification}
      email classification (e.g. \cite{klimt:2004:enron}) or systems
      like Chinese \index{social credit system}
      \href{https://en.wikipedia.org/wiki/Social\_Credit\_System}{Social
        Credit System}.

      \item \textbf{multi-threaded} - as many ``server'' like
        programs, \emph{Bismon} should practically be
        \href{https://en.wikipedia.org/wiki/Thread_(computing)}{multi-threaded}
        \index{multi-threading} \index{threading!multi-} to take
        advantage of current
        \href{https://en.wikipedia.org/wiki/Multi-core\_processor}{multi-core
          processors} \index{processor!multi-core} with
        \href{https://en.wikipedia.org/wiki/Shared\_memory}{shared}
        \href{https://en.wikipedia.org/wiki/Virtual\_memory}{virtual
          memory}\index{memory!virtual} \index{memory!shared}
        \index{shared memory} \index{virtual memory}. Therefore
        \index{synchronization}
        \href{https://en.wikipedia.org/wiki/Synchronization}{synchronization}
        issues (using
        \href{https://computing.llnl.gov/tutorials/pthreads/#ConVarSignal}{condition
          variables} \index{condition variable} and
        \href{https://computing.llnl.gov/tutorials/pthreads/#MutexLocking}{mutexes}
        \index{mutex} and/or
        \href{https://en.wikipedia.org/wiki/Atomic\_semantics}{atomic}
        variables) \index{atomic variable} between threads become
        important to avoid \index{race condition}
        \href{https://en.wikipedia.org/wiki/Race\_condition}{race
          conditions}.

      \item with a \textbf{syntax-oriented editor} or syntactical
        \emph{editor} \index{editor!syntactical}
        \index{syntax-oriented!editor} (for our DSLs), inspired by the
        ideas of \textsc{Mentor} \index{mentor@\textsc{Mentor} system}
        in \cite{donzeaugouge:inria-mentor} (so see also
        \cite{Jacobs:1992:Centaur}, a tutorial on the related, even
        older, \textsc{Centaur} \index{centaur@\textsc{Centaur}
          system} system. We should also follow
        \cite{amershi:2019:guidelines-human-AI-interact}). So the
        static analysis expert \index{expert!static analysis}
        \index{static analysis} is not typing some raw text (in some
        concrete syntax of our \index{DSL} DSL) later handled by
        traditional parsing techniques (as in
        \cite{Aho:2006:DragonBook}) but should interact using a web
        interface to \emph{modify} and \emph{enhance} the persistent
        store (like old Lisp machines or Smalltalk machines did in the
        1980s), partially shown in a web browser (see also
        \S\ref{subsec:webinterf} below). That web interface is
        facilitating \emph{refactoring} of DSL code.
\end{itemize}

\bigskip

It should be noticed that \textbf{\emph{Bismon} is} actually \textbf{a
  somehow generic framework}, \index{framework} designed and usable to
ease static analysis of C or C++ programs using generated \emph{GCC}
plugins and other runtime emitted code. As an orthogonally persistent,
meta-programmable, reflexive, and multi-threaded framework, and with a
few years of additional work and funding, \emph{outside} of the
\textsc{Chariot} project, \textbf{it could be even used for many other
  purposes}, including \emph{artificial intelligence} and \emph{data
  mining} applications on small volumes\footnote{The entire analyzed
  data should fit in \emph{Bismon} persistent store, so dozens of
  gigabytes, not terabytes.}  of data, web-based \emph{collaborative
  software} tools (see also \cite{echeverria:2019:collab-translucence,
  kou:2019:practice, gulay:2019:integ-workf, dragicevic:2019:ITR}),
various multi-user \emph{web applications}, \emph{declarative
  programming} approaches, etc... \index{artificial intelligence}
\index{data mining} \index{persistent store} \index{collaborative
  sofware} \index{application} \index{web application}
\index{application!web} \index{declarative programming}
\index{programming!declarative}

\medskip

\subsubsection{About \emph{Bismon} as a domain-specific language}
\label{subsubsec:bismon-dsl}

Notice that \textit{Bismon} is not even thought as a \emph{textual}
domain specific language~\footnote{In contrast, \emph{GCC MELT} was
  textual and had \texttt{*.melt} source \emph{files} edited with
  \texttt{emacs} using its Lisp mode. This made refactoring difficult,
  since automatic move of textual fragments was not realistically
  possible.} (and this is possible because it is persistent). There is
not (and there won't be) any canonical \emph{textual} syntax for
``source code'' of the domain specific language in \textit{Bismon}
~\footnote{This idea is not new: neither Smalltalk
  (cf. \cite{Goldberg:1983:Smalltalk}), nor Common Lisp
  (cf. \cite{Steele:1990:CommonLisp}), are defined as having a textual
  syntax with an associated operational semantics based on it. Even
  the syntax of C is defined \emph{after} preprocessing. What is
  -perhaps informally- defined for Smalltalk and Common Lisp is some
  abstract internal representation of ``source code'' in ``memory''
  and its ``behavior''. In contrast, Scheme has both its textual
  syntax and its semantics well defined in R5RS, see
  \cite{Adams:1998:R5RS}.}. \index{source code}{\emph{Source code}} is
defined (socially) as the preferred form on which developers are
working on programs. For C or C++ or Scheme programs, source code
indeed sits in textual files in practice (even if the C standard don't
speak of files, only of ``translation units'', see \cite{C11:std}),
and the developer can use any source code editor (perhaps an editor
unaware of the syntax of C, of C++, of Scheme) to change these source
files. In contrast, a developer contributing to \textit{Bismon} is
browsing and changing some internal representations thru the
\textit{Bismon} user interface (a Web interface~\footnote{in mid-2018,
  that Web interface was incomplete, and I still had to temporarily
  use some obsolete GTK-based interface that even I find so disgusting
  that I won't explain it, and sometimes even to edit manually some
  \texttt{store2.bmon} data file, cf \S~\ref{subsubsec:filestate}.};
see also \cite{Myers:2000:PPF} for a survey) and interacts with
\textit{Bismon} to do that. There is no really any \index{abstract
  syntax tree}{abstract syntax \emph{tree}} (or AST) \index{AST} in
\textit{Bismon}: what the developer is working on is some \emph{graph}
(with circularities), and the entire persistent state of \emph{Bismon}
could be viewed as some large graph in memory.

Conceptually the initial \emph{Bismon} DSL \index{DSL} is at first a
\index{language!dynamic}
\href{https://en.wikipedia.org/wiki/Dynamic\_programming\_language}{dynamic
  programming language}, semantically similar to Scheme, Python (or to
a lesser degree, to JavaScript: however, it has classes, not
prototypes, with single-inheritance), and is somehow \emph{compiled}
or
\href{https://en.wikipedia.org/wiki/Source-to-source\_compiler}{\emph{transpiled}}\index{transpiler}\index{transcompiler}
to C. It is \emph{essentially} (unlike most Scheme or Python or
JavaScript implementations) a \emph{multi-threaded} language, since
the emitted routines can run in parallel in our agenda machinery
(cf. \S\ref{subsec:multithreadist} below). Meta-programming techniques
(inspired by Lisp macro systems, see \cite{Queinnec:1996:LSP}, and
largely experimented in \emph{GCC MELT}) will ease the extension of
that language.

The base \emph{Bismon} DSL is currently implemented~\footnote{See
  notably our hand-written files \texttt{gencode\_BM.c} and
  \texttt{emitcode\_BM.c} in october 2018. Our bootstrap philosophy
  might require replacing later these hand-written files by better,
  \emph{bismon} generated, modules.} as a naive transpiler to C code
(respecting the coding rules of our implementation, in particular of
our garbage collector, see \S\ref{subsec:gcvalobj}).

Our initial DSL is designed in terms of code representations as
objects (see \S\ref{subsubsec:objects} below) and immutable values (see
\S\ref{subsubsec:immutvalues} below). It is not defined by some EBNF
textual syntax. For example, an assign statement $\alpha$ \texttt{=} $\beta$
is represented by an object of class \texttt{basiclo\_assign}
    \index{basiclo assign@\texttt{basiclo\_assign}} with its
first component representing the left hand-side $\alpha$ and the
second component representing the right hand-side $\beta$. Expressions
in our DSL are either objects, or nodes, or scalars (integers,
strings, etc...).


What is transpiled to C are Bismon ``modules'' (for example our
\texttt{webjs\_module} contains code related to emission of
JavaScript), each with a sequence of routines. A module can be
dumpable (into the persistent state, which then contains also the
generated C code) or temporary (then the generated C code is not kept
in that state). A routine or function~\footnote{Technically the
  routine would be in the module's shared object binary; the function
  is a \emph{Bismon} object reifying the code of that routine.}  is an
object of class \texttt{basiclo\_function}
\index{basiclo function@\texttt{basiclo\_function}}
\index{basiclo minifunction@\texttt{basiclo\_minifunction}}
or its subclass
\texttt{basiclo\_minifunction}, etc... A function knows its arguments,
local variables, local numbers, body by various attributes
(e.g. \texttt{arguments}, \texttt{locals}, \texttt{numbers},
\texttt{body} etc...). Its body is a block made of statements.

Statements of our DSL include:

\begin{itemize}
\item assignments, of class \texttt{basiclo\_assign}, as explained above.
  
  \item run statements, of class \texttt{basiclo\_run}, \index{basiclo
    run@\texttt{basiclo\_run}} which ``evaluates'' its single operand
    for side effects (similar to expression statements in C or Go). As
    a special (and rather common) case, that operand can be a ``code
    chunk'' \index{code chunk} (conceptually similar to GCC MELT's
    code chunks, see \cite{Starynkevitch-DSL2011} \S3.4.1), that is a
    node of connective \texttt{chunk} providing a ``template'' for
    expansion as C code.

  \item conditional statements, of class \texttt{basiclo\_cond},
    \index{basiclo cond@\texttt{basiclo\_cond}} 
    \index{basiclo when@\texttt{basiclo\_when}} 
    \index{nb conds@\texttt{nb\_conds}} 
      inspired by Lisp's \texttt{cond}. Its components are a sequence
      of when clauses (which are objects of class
      \texttt{basiclo\_when}) followed the ``else'' statements or
      blocks. The \texttt{nb\_conds} attribute in the statement gives
      the number of when clauses.

    \item for loops, we have a \texttt{basiclo\_while} class of
      statements (for ``while'' loops) and a \texttt{basiclo\_loop}
    \index{basiclo while@\texttt{basiclo\_while}} 
    \index{basiclo loop@\texttt{basiclo\_loop}} 
    \index{basiclo exit@\texttt{basiclo\_exit}}
    \index{basiclo return@\texttt{basiclo\_return}} 
      class (for infinite loops). Exiting of loops and blocks are
      using the \texttt{basiclo\_exit} class. Return statements use
      the \texttt{basiclo\_return} class.

      \item failure (inspired by Go's \texttt{panic}) statements are
    \index{basiclo fail@\texttt{basiclo\_fail}} 
        of class \texttt{basiclo\_fail}. Failures are not exceptions,
        but prematurely terminate the tasklet (of the agenda, see
        \S\ref{subsec:multithreadist} below) running the function
        containing that statement.

      \item locking of objects use a \texttt{basiclo\_lockobj} class
    \index{basiclo lockobj@\texttt{basiclo\_lockobj}} 
        (mentioning both an object to lock and a sequence of
        sub-statements or blocks). A locked object is unlocked when
        the end of its locking statement is reached, or when the
        currently active routine terminates (on failure or on return).

      \item execution of primitive side-effecting operations with no
    \index{basiclo cexpansion@\texttt{basiclo\_cexpansion}} 
        result happens in C-expansion statements (of class
          \texttt{basiclo\_cexpansion}), inspired by GCC MELT's
          primitives (see \cite{Starynkevitch-DSL2011}) returning
          \texttt{:void}.

      \item etc...
\end{itemize}

Expressions in our DSL are typed (with types like \texttt{value},
\texttt{object}, \texttt{int}, \texttt{string}, etc...)  and include:

\begin{itemize}
\item scalar (integers, constant strings)
  
\item local variables, or arguments, or numerical variables (of the current function).

\item constant objects (mentioned with \texttt{constants} in the function)

\item closure application (represented by a node of connective \texttt{apply}). Often, the closure's connective would be a
  function object.

  \item quotations (like in Lisp, represented by an unary node of
    connective \texttt{exclam})

\item message sending (represented by a node of connective \texttt{send})

\item primitives (inspired by GCC MELT's ones, see
  \cite{Starynkevitch-DSL2011}; the connective of the node is of class
  \texttt{basiclo\_primitive})

  \item builtin objects like \texttt{current\_closure},
    \texttt{current\_closure\_size}, \texttt{current\_module},
    \texttt{current\_routine}, \texttt{null\_value},
    \texttt{null\_object} are expanded in some ad-hoc \index{current
      closure@\texttt{current\_closure}} \index{current closure
      size@\texttt{current\_closure\_size}} \index{current
      module@\texttt{current\_module}} \index{current
      routine@\texttt{current\_routine}}
    \index{null value@\texttt{null\_value}}
    \index{null object@\texttt{null\_object}}
    fashion~\footnote{That is:
      \texttt{current\_closure} $\rightarrow$ the current closure;
      \texttt{current\_closure\_size} $\rightarrow$ its size;
      \texttt{current\_module} $\rightarrow$ the current module;
      \texttt{current\_routine} $\rightarrow$ the current routine;
      \texttt{null\_value} $\rightarrow$ the null value;
      \texttt{null\_object} $\rightarrow$ the null object;
      respectively.}.

\item etc...
  
\end{itemize}
  

\subsubsection{About \emph{Bismon} as a evolving software system}
\label{subsubsec:bismon-evolving}

So \emph{Bismon} is better thought of as an evolving software
system. We recommend to try it. Notice that \textit{Bismon} is
\textbf{provided as free software} (available
on \bmurl{https://github.com/bstarynk/bismon/} but unreleased in 2018) in \emph{source form only}
and should be \textbf{usable} \emph{only} \textbf{on a Linux/x86-64
  workstation}... (typically, at least 32 gigabytes of RAM and
preferably more, at least 8 cores, several hundreds gigabytes of disk
or SSD).

The \textit{Bismon} system contains \textbf{persistent data} (which is
part of the system itself and should not be considered as ``external''
data; each team using \textit{Bismon} would run its own customized
version of their \textit{Bismon monitor}.), and should be
\textbf{regularily backed up}, and preferably version controlled at
the user site. It is strongly recommended to use
\index{git}{\texttt{git}} \footnote{See \bmurl{http://git-scm.com/}}
or perhaps some other distributed \index{version control}{version
  control} system, to \texttt{git commit} its files several times a
day (probably hourly or even more frequently, as often as a developer
is committing his C++ code), and to backup the files on some external
media or server at least daily. How that is done is outside of the
scope of this document. The \emph{dump facilities} inside
\textit{Bismon} are expected to be used quite often (as often as you
would save your report in a word processor, or your source file in a
source code editor), probably several times per hour. So a developer
team using \textit{Bismon} would probably \texttt{git clone} either
\texttt{git@github.com:bstarynk/bismon.git} thru SSH or
\bmurl{https://github.com/bstarynk/bismon.git}, build it (after
downloading and building required dependencies), and work on that
\texttt{git} repository (and of course back-up it quite often).

We are still growing \emph{Bismon} by feeding it with additional
interactions changing its persistent state. At first, we developed (at
begin of bootstrap\index{bootstrap}) a crude GTK\index{GTK} interface,
shown in figure \ref{fig:bismonscreenshot-cbdcf}, which is a
screenshot made on October 22\textsuperscript{nd} 2018 on git commit
\texttt{cbdcf1ec351c3f2a}, when working on the JavaScript generator
inside \emph{Bismon}. It shows several windows: the large top right
window (named \texttt{new-bismon}) has a command textview (ivory
background, top panel) and a command output (azure background, bottom
panel). The small top left window (named \texttt{bismon values} show
the read-eval-print-loop output (as \texttt{\$a} in two panes). The
mid-sized bottom left window (titled \texttt{bismonob\#1}) shows (in
two text-views of the same GTK text buffer) shows (in top text-view) a
large part of the body of the \texttt{emit\_jsstmt} method for the
\texttt{basiclo\_while} class of \emph{Bismon} and (in bottom
text-view) some components of our \texttt{webjs\_module} object. In
the rear, bottom right, a tiny part of our \texttt{emacs} editor (used
to run \texttt{bismon --gui}...) is visible, and shows a
backtrace~\footnote{Ian L. Taylor's
  \href{https://github.com/ianlancetaylor/libbacktrace}{\texttt{libbacktrace}}
  is used in \emph{bismon} to provide symbolic backtraces.}.


\begin{figure}[h]
  \begin{center}
    \bmincludewidthgraphics{0.98\textwidth}{bismon-cbdcf1ec351c3f2a-screenshot-22oct2018-img}{png}{png}
  \end{center}
  \caption{crude {\relsize{-1}{(soon deprecated)}} GTK interface
    {\relsize{-1}{oct. 22, 2018, git commit
        \texttt{cbdcf1ec351c3f2a}}}}
  \label{fig:bismonscreenshot-cbdcf}
\end{figure}

This crude GTK3 interface~\footnote{It is implemented in 12.5KLOC of C
code in \texttt{gui\_GTKBM.c}, \texttt{newgui\_GTKBM.c} and
\texttt{guicode\_BM.c}}. Anonymous objects are displayed also with
their \index{comment!\texttt{comment}} \texttt{comment} predefined
attribute\footnote{See not only the
\href{https://en.wikipedia.org/wiki/Comment\_(computer\_programming)}{comment}
wikipage but think of a \texttt{comment} macro in \textsc{Lisp},
\textsc{Scheme} or \textsc{Gcc Melt} which would ignore all its
arguments and stays macro-expanded to nil.}. We won't debug that GTK
code -which crashes often\footnote{Because of a design bug related to
garbage collection, practically too costly to be fixed.}- but will
remove it once it can be replaced by a web interface. It will and
needs to be replaced by a Web interface. Several lessons have been
gained with this experience:

\begin{itemize}
\item using GTK~\footnote{Since GTK is a free software library, we
  could consider patching its source code, but such a huge effort is
  not reasonable within the timeframe of \textsc{Chariot}, and GTK is
  still evolving a lot, so patching it would require freezing its
  version. \texttt{gtk+-3.24.1} has 1.2 millions lines of source code,
  measured by D.Wheeler \texttt{sloccount} but it depends also on
  other libraries, such as Pango, Glib, etc... so patching GTK source
  for our precise GC is not reasonable at all.}  is in practice
  incompatible with a multi-threaded precise garbage
  collector~\footnote{See also
    \bmurl{https://stackoverflow.com/q/43141659/841108} about GTK and
    Boehm's conservative GC.}, like the one in \emph{Bismon} (cf
  \S\ref{subsec:gcvalobj} below), in particular because GTK may have
  several nested event loops, so many local garbage collector pointers
  in internal call frames (which are not accessible from routines
  above).

    \item the model and the C API provided by GTK text views and text
      buffers is not adequate for structured syntactic editing (like
      pionneered in Mentor, see \cite{donzeaugouge:inria-mentor}). It is still too low-level and oriented for plain textual edition.

      \item GTK is not compatible with several X11 displays, so a
        single \emph{bismon} process cannot handle several users each
        having its own screen.
\end{itemize}

So we decided to stop investing efforts on the GTK interface, and give
more priority to a Web interface, which is required once a small team
of \emph{several} IoT developers need to interact with the
\emph{bismon} persistent monitor. The GTK interface is just
temporarily needed to fill the persistent store (till our web
interface is usable). We hope that it will be entirely scrapped and
should be replaced by a web interface\footnote{Notice that
\index{copy-paste} copy/pasting becomes then a difficult issue, see
\bmurl{https://softwareengineering.stackexchange.com/q/393837/40065}.}
, and the static analysis expert (and other users pof \emph{Bismon})
will interact with \emph{bismon} thru some Web interface.

Work on the future Web interface has significantly progressed
~\footnote{With the hand-written \texttt{web\_ONIONBM.c} using
  \texttt{libonion}, and the \emph{bismon} module
  \texttt{webjs\_module} translated into the
  \texttt{modules/modbm\_1zCsXG4OTPr\_8PwkDAWr16S.c} emitted C file of
  more than 6.5KLOC in october 2018.}. New users -called
\emph{contributors} \index{contributor}- can be voluntarily registered
and unregistered on the command line~\footnote{Use the option
  \texttt{--contributor=} to add them, \texttt{--remove-contributor=}
  to remove them and \texttt{--add-passwords=} to set their encrypted
  \emph{bismon}-specific password.} into \emph{bismon} in a way
similar to \texttt{git}. When they access any dynamic web page, a
login web form appears (with some GDPR \index{GDPR} related notice) if
no web cookie identifies them. But that Web interface is still
incomplete in October 2018. Several design decisions have been made:
we will use the \texttt{codemirror}~\footnote{See
  \bmurl{http://codemirror.net/} for more.} web framework to show the
analyzed source code of IoT software. The web interface for IoT
developers should be a ``single-page application'' one (so AJAX,
HTML5, CSS3 techniques, with generated JavaScript and HTML
code). \emph{WebSockets} should be used for asynchronous communication
between browser and the \emph{bismon} monitor. The
\href{http://jquery.com/}{\texttt{jquery}},
\href{https://angular.io/}{\texttt{angular}},
\href{https://semantic-ui.com/}{\texttt{semantic-ui}}, etc... web
frameworks are considered as building blocks for that Web interface
and should be installed with inside \emph{bismon}~\footnote{For
  example, the \emph{bismon} source tree has a
  \texttt{webroot/jscript/jquery.js} local file to serve HTTP
  \texttt{GET} requests to an URL like
  \texttt{http://localhost:8086/jscript/jquery.js} handled by the
  \emph{bismon} monitor.} to enable using \emph{bismon} without any
external Internet connection.


IoT developers working with the \emph{Bismon monitor} will use some
Web interface to interact with it.

\subsubsection{About \emph{Bismon} as a static source code analyzer framework}

The \emph{Bismon} persistent monitor will generate the C++ code of GCC
plugins, leveraging on the experience of GCC MELT (see
\cite{Starynkevitch-DSL2011,Starynkevitch2007Multistage,Starynkevitch-GCCMELTweb}). The
C++ code generator will have a design similar to (and share some code
and classes with) our internal initial DSL (cf
\S\ref{subsubsec:bismon-dsl}). It is extremely likely that in many
cases, such a generated GCC plugin would just insert its appropriate
passes by using the pass manager (cf \cite{gcc-internals} \S9 and
\S24.3), and these passes will ``serialize'' internal representations
(either in JSON, or using Google protocol buffer, or using a textual
format close to our dump syntax, see figure \ref{fig:dumpvalsyntax}
below, etc...)  such as \emph{Gimple}-s, \emph{Basic Block}-s and
transmit some form of them to the \emph{Bismon} persistent monitor. In
some simple cases, it is not even necessary to transmit most of that
representation. For instance, a whole program static analysis to help
avoiding stack overflow needs just the size of each call
frame~\footnote{Notice that \emph{GCC} compute these call frame sizes
  (see the \texttt{-fstack-usage} option), and can detect excessively
  big call frame with \texttt{-Wstack-usage=} option.} and the control
flow graph (so only the \emph{Gimple} call statements, ignoring
anything else); with that information (and the control flow graph)
the monitor should be able to estimate an approximation~\footnote{Of
  course dynamic calls, e.g. call thru function pointers, make that
  much more complex and will require manual annotation.} of the
consumed call stack, whole program wide.

Several design decisions have been made regarding the style of the
generated C++ code of GCC plugins: it will use existing scalar data
and \texttt{GTY}-ed classes (see \cite{gcc-internals} \S23), to take
advantage of the existing GCC garbage collector
(\emph{Ggc}). Contrarily to GCC MELT, it won't provide a generational
garbage collector (because most of the processing happens in the
monitor, hence performance of the generated GCC plugin\footnote{In
  practice, generated GCC plugins would simply ``digest'' some
  internal GCC representations and transmit their outcome to the
  Bismon monitor.} is less important), so transforming to A-normal
form is not required at translation (to C++) time.

% @@@ to be completed when some static source code analysis of some C or
% C++ code is possible with \emph{Bismon}, using \emph{generated} GCC
% plugins (emitted as C++ code by \emph{Bismon}, and used inside the
% cross-compilation processed started by IoT developers following the
% \textsc{Chariot} approach.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multi-threaded and distributed aspects of \textit{Bismon}}
\label{subsec:multithreadist}

The \textit{Bismon monitor} is by itself a multi-threaded
process~\footnote{In contrast of most scripting languages
  implementations such as Python, Ocaml, Ruby, etc..., we try hard to
  avoid any ``global interpreter lock'' and strive to develop a
  genuinely multi-threaded monitor.}.
It uses a \emph{fixed} {\index{thread pool}{\emph{thread pool}}} of
{\index{worker thread}{\emph{worker threads}}} (often active)
\footnote{The number of worker threads is given by the \texttt{--job}
  program argument to \texttt{bismon}. For an 8-cores workstation, it
  is suggested to set it to 5 or 6. It should be at least 2, and at
  most 15. This number of jobs also limits the set of simultaneously
  running external processes, such as \texttt{gcc} processes started
  by \emph{Bismon}.}, and additional (generally idle) threads for web
support and other facilities. The \textit{Bismon monitor} is
occasionally starting some external processes, in particular for the
compilation of generated \emph{GCC} plugins, and for the compilation
into \index{module}{\emph{module}s} -technically ``plugins''- of
dynamically generated \emph{C} code by \textit{Bismon}; later it will
dynamically load (with \texttt{dlopen}) these modules, and thus
\textit{Bismon} can increase its code (but cannot decrease it, even if
some code becomes unused and unreachable); however such modules are
\emph{never} \index{garbage collection}{garbage collected} (so
\texttt{dlclose} is never called). So in practice, it is recommended
to restart \emph{Bismon} every day (to avoid endless growth of its
code segments).


The worker threads of \emph{Bismon} are implementing its
\index{agenda}{\textbf{agenda}} \footnote{Details about the agenda,
  such as the fixed set of available priorities, are subject to
  change. We describe here the current implementation in mid-2018.}
machinery. Conceptually, the agenda is a 5-tuple of first-in first-out
queues of \index{tasklet}{\textbf{tasklets}}, each such FIFO queue is
corresponding to one of the five \index{priority}{priorities} :
\emph{very high}, \emph{high}, \emph{normal}, \emph{low}, \emph{very
  low}. Each agenda worker thread removes one tasklet (choosing the
queue of highest possible priority which is non empty, and picking the
tasklet in front of that queue) and runs that tasklet quickly. A
tasklet should run during a few milliseconds (e.g. with some implicit
kind of non-preemptive scheduling) at most (so cannot do any blocking
IO; so input and output happens outside of the agenda). It may add one
or more tasklets (including itself) to the agenda (either at the
front, or at the end, of a queue of given priority), and it may remove
existing tasklets from the agenda. Of course tasklets run in parallel
since there are several worker threads to run the agenda. The agenda
itself is not persisted as a whole, but tasklets\footnote{Actually
  tasklets are objects (see \S\ref{subsubsec:objects} page
  \pageref{subsubsec:objects} below), and to run them, the agenda is
  sending them a message with the predefined selector
  \texttt{\emph{run\_tasklet}}.}  themselves may be
\index{persistent}{persistent} or \index{transient}{transient}.
Tasklets can also be created outside of the agenda (e.g. by incoming
HTTP requests, by completion of external processes, by timers, ...)
and added asynchronously into the agenda.

Outside of the agenda, there is an \emph{idle queue} of delayed todo
closures (a queue of closures to be run, as if it was an idle priority
queue) with some arguments to apply to them. But that \index{idle
  queue}{idle queue} don't contain directly any tasklets. That idle
queue can be filled by external events~\footnote{For example, when an
  external compilation process completes, that queue is filled with
  some closure -provided when starting that compilation- and, as
  arguments, an object with a string buffer containing the output of
  that process, and the integer status of that process.}. Of course the idle
queue is not persisted.

\bigskip

In its final version, the \emph{Bismon system} will involve several
cooperating Linux processes:

\begin{itemize}
\item the \emph{Bismon monitor} itself, with several threads (notably for the agenda mechanism described above)
  
  \item the web \index{browser}{browsers} of developers using that
    particular \emph{Bismon monitor}; each developer probably runs
    his/her own browser. That web browser is expected to follow latest
    Web technologies and standards (HTML5, Javascript6 i.e. EcmaScript
    2016 at least, WebSockets, ...). It should probably be a Firefox
    or a Chrome browser from 2017 or after. The HTML and Javascript is
    dynamically generated by the \emph{Bismon monitor} and should
    provide (to the developer using \emph{Bismon}) some ``single-page
    application'' (cf. \cite{Atkinson:2018:webtabs,
      Queinnec:2004:ContinWeb, Graunke:2003:ModelingWeb})
    feeling~\footnote{So using your browser's backward and forward
      navigation arrows won't work well because in single-page
      applications they \emph{cannot} work reliably}.

    \item the IoT developers using \emph{Bismon} will build their IoT
      firmware as usual; however they will add some extra options (to
      their \texttt{gcc} or \texttt{g++} cross-compilation commands)
      to use some \emph{Bismon} generated GCC plugin in their
      cross-compilation processes. So these cross-compilation
      processes (i.e. \texttt{cc1} started from \texttt{gcc}, or
      \texttt{cc1plus} started from some \texttt{g++}, etc...),
      augmented by generated plugins, are involved.

  \item sometimes \emph{Bismon} would generate some
    \texttt{modules/*.c} file during execution, and fork a (direct)
    compilation of it (technically forking a
    \texttt{./build-bismon-persistent-module.sh} -for persistent
    modules- or a \texttt{./build-bismon-temporary-module.sh} -for
    temporary modules- shell script, which invokes \texttt{make} which
    runs some \texttt{gcc} command) into a ``plugin'' module
    \texttt{modubin/*.so}, which would be \texttt{dlopen}-ed.

  \item \emph{Bismon} should also generate the C++ code of \emph{GCC
    plugins}, to be later compiled then used (with \texttt{gcc} or
    \texttt{g++} option \texttt{-fplugin}). Two kinds of \emph{GCC}
    plugins are considered to be generated:

    \begin{enumerate}
      \item usually, the GCC plugin~\footnote{It is tempting to call
        such plugins \emph{cross-}plugins, since they would be
        \texttt{dlopen}-ed by a cross-compiler.} would be generated to
        assist [cross-] compilation (e.g. of IoT software) by
        developers using \emph{Bismon}. So for an IoT developer
        targeting some RaspberryPi, it could be a GCC plugin
        targeting the \texttt{arm-linux-gnueabi-gcc-8} cross-compiler
        (but the C++ code of that plugin needs to be compiled by the
        native \texttt{gcc} on the host system).
        
      \item But the GCC API is so complex (and under-documented) that
        it is worth extracting it automatically by sometimes
        generating a GCC plugin~\footnote{It is tempting to call such
          plugins \emph{straight-}plugins, since they would be
          \texttt{dlopen}-ed by a straight compiler, not a
          cross-compiler.} to inspect the public headers of
        GCC\footnote{In \emph{GCC MELT}, we tried to describe by
          hand-coded \emph{MELT} code a small part of that GCC API and
          its glue for \emph{MELT}. This approach is exhausting, and
          makes following the evolution of GCC very difficult and
          time-consuming, since new \emph{MELT} code should be written
          or manually adapted at each release of \emph{GCC}. Some
          partial automation is needed to ease that effort of adapting
          to successive \emph{GCC} versions and their non-compatible
          plugins API}. Even when the end-user developer is targetting
        a small IoT chip requiring a cross-compiler (like
        \texttt{arm-linux-gnueabi-gcc-8} above), these GCC inspecting
        plugins are for the native \texttt{gcc} (both
        \cite{Schafmeister:2016:CANDO} and
        \cite{Schafmeister:2015:CLASP} are inspirational for such an
        approach).
        
    \end{enumerate}

    We are considering several ways of providing (to the IoT developer
    using them) such generated C++ code for GCC plugins. We might
    generate (at least for the first common case of GCC plugins
    generated for developers using \emph{Bismon}, and large enough to
    need several~\footnote{By past experience in GCC MELT, we did
      generate C++ files totalizing almost a million lines of C++
      code, and compiling such a large generated C++ code base took
      dozens of minutes, and created a bottleneck.} generated C++
    files) \texttt{*.shar} archives (obtained by Web requests, or
    perhaps some \texttt{wget} or \texttt{curl} command in some
    \texttt{Makefile}) for \emph{GNU sharutils}~\footnote{See
      \bmurl{https://www.gnu.org/software/sharutils/} for more.}
    containing the C++ code and also the \texttt{g++} command
    compiling it. That archive could instead be just a
    \texttt{.tar.gz} file (and the IoT developer would extract it, and
    run \texttt{make} or \texttt{ninja} inside the extracted directory
    to build the shared object GCC plugin binary file), etc... For a
    \emph{small} generated GCC plugin fitting in a single generated
    C++ file of less than a dozen thousands lines, we could simply
    serve in \emph{Bismon} an URL like
    \texttt{http://localhost:8086/genplugin23.c} and require the IoT
    developer to fetch then use that. Other approaches could also be
    considered. The rare second case (GCC plugin code generated to
    inspect the GCC API, running on the same machine as the
    \emph{Bismon} server) could be handled thru external processes
    (similar to compilation of \emph{Bismon} modules). Alternatively,
    we might consider delegating such plugin-enhanced
    cross-compilation processes to the \emph{Bismon} monitor itself,
    etc, etc...
    
\end{itemize}

In principle, the various facets of \emph{Bismon} can run on different
machines as \index{distributed computing}{distributed computing}
(obviously the web browser is not required to run on the same machine
as the \emph{Bismon monitor}, but even the various compilations -of
code generated by \emph{Bismon}, and the cross-compilation of IoT
code- could happen on other machines).

Conceptually, we aim for a \index{multi-tier
  programming}{\textbf{multi-tier programming}} approach (inspired by
Ocsigen~\footnote{See \bmurl{https://ocsigen.org/}} with the high-level
DSL inside \emph{Bismon} generating code: in the \emph{Bismon
  monitor}, as modules; in the \emph{web browser}, as generated
Javascript and HTML; in the \emph{GCC} compiler, as generated GCC plugins.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Local Variables: ;;
%% compile-command: "cd ..; ./build-bismon-doc.sh" ;;
%% End: ;;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
