%% file datapersist-bm.tex, which is \input from bismon-doc.tex
\section{Data and its persistence in \emph{Bismon}}
\label{sec:datapersist}

Notice that \emph{persistent memory} is also a hardware technology
sold by Intel. See \href{https://pmem.io/}{\texttt{pmem.io}} and
\cite{Scargall:2020:programming}. With care and programming efforts,
such hardware could be used by the \emph{Bismon monitor}.

Several checkpoint/restarting mechanisms, such as the
\href{https://github.com/checkpoint-restore/criu}{\textsc{Criu}
  library}, are conceptually similar to the persistence
mechanism\footnote{See
\href{https://stackoverflow.com/a/62927624/841108}{\texttt{stackoverflow.com/a/62927624/841108}}
for more.} existing in \textsc{Bismon}, but have been developed with
different trade-offs, and no concern for portability.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Data processed in \emph{Bismon}}

\label{subsec:dataproc}

The \emph{Bismon monitor} handles various kinds of
\index{data}{data}. A lot of data is \index{immutable}{immutable} (its
content cannot change once the data has been created, for example
strings). But \index{object}{\textbf{objects}} are of course mutable
and can be modified after creation. Since \emph{Bismon} is
multi-threaded and its agenda is running \emph{several} worker threads
in parallel, these mutable objects contain a \index{mutex}{mutex} for
locking purposes.

So the \emph{Bismon monitor} handle
\index{value}{\textbf{values}}~\footnote{To extend \emph{Bismon} to
  handle some new kind of custom data (such as bignums, images, neural
  networks, etc...) processed by external libraries, it is advised to
  define new \emph{payloads} inside objects
  (cf. \S\ref{subsubsec:objects} below), without adding some new kind
  of values.} (represented in a 64 bits machine word, holding some
pointer or some tagged integer) : they can be immutable, or objects
(and such objects are the only kind of mutable data).

All values (immutable ones and mutable objects) are
hashable~\footnote{Their hash is a non-zero 32 bits unsigned
  number. Only the nil pointer has an hash of 0.}  and totally
ordered.

\medskip

Since \emph{Bismon} is able to persist and process efficiently and
concurrently many kinds of symbolic data organized more or less in a
semantic network (including most abstract syntax trees or AST-s
\index{AST} and their symbolic annotations), it should be re-usable
with additional efforts as a foundation for many other
aspects~\footnote{For an example, look into the ongoing \index{h2020@\emph{\textsc{h2020}}}
  \href{https://www.decoder-project.eu/}{\textsc{Decoder}}
  \index{decoder@\textsc{Decoder}} H2020
  project, ICT-16 call, grant agreement number 82423.} of static
source code analysis, even of programming languages which are not tied
to \emph{GCC}. Of course, some significant work related to parsing is
then required.

The \href{http://www.barrelfish.org/}{\textsc{Barrelfish} operating
  system} \index{Barrelfish OS@\textsc{Barelfish} operating system} (see \cite{gerber:2018:authorization,
    giceva:2016:customized, Schupbach:2008:embracing}...) has a
  \emph{System Knowledge Base} ``used to store, query, unify, and
  compute on a variety of data about the current running state of the
  system'' which is ``based on a port of the
  \href{https://eclipseclp.org/}{\textsc{eCLiPse}} constraint logic
  programming system'' \cite{Apt:2006:constraint} (from
  \cite{barrelfish:2013:overview}), and \textsc{Barrelfish} aims be
  used for IoT computer networks.

%%%%%%%%%%%%%%%%
\subsubsection{Immutable values}
\label{subsubsec:immutvalues}

They include

\begin{itemize}

\item \textbf{tagged integer} (of 63 bits, since the least significant
  bit is a tag bit). The \index{integer}{integer} won't change (and
  integer values don't require extra space to keep that integer, since
  they are encoded in the pointer).
  
\item UTF-8 encoded \textbf{string} (the bytes inside such
  \index{string}{strings} don't change).

  \item boxed constant \textbf{double} \index{double} \index{floating point} (IEEE 754) floating
    point~\footnote{The practical motivation for floating point
      numbers is mostly related to JSON, since the \texttt{jansson}
      library handle differently floating JSON and integer JSON
      values, and perhaps to rare storage of timing data (CPU or
      elapsed time) expressed as a floating point number. We don't
      intend \emph{Bismon} to be used for complex numerical
      processing. Should machine learning libraries become useful -
      after the \textsc{Chariot} project - in \emph{bismon}, their
      data would probably become some object payload.}  numbers; but
    \texttt{NaN} is \emph{never} boxed and becomes reified as the
    \texttt{nan\_double} \emph{object}; hence boxed doubles stay
    comparable (with the convention~\footnote{The intuition behind
      such a convention would be that $-0.0$ is a very (or infinitely)
      small negative number, so less that $+0.0$ which could be a very
      small positive number.}  that $-0.0 < +0.0$, even if they
    compare equal in IEEE 754).

  \item \textbf{tuple} of objects, that is an ordered (but immutable)
    sequence of object pointers (the size or content of a tuple don't
    change). A given object could appear in several positions in a
    \index{tuple}{tuple}.

  \item \textbf{set} of objects, represented internally as a sorted
    array of objects' [i.e. pointers]. A given object can occur only once in a
    set, and membership (of an object inside a set) is tested
    dichotomically in logarithmic time. Of course, the size and
    content of a \index{set}{set} never change.

  \item \textbf{node}. A \index{node}{node} has an object connective,
    and a (possibly empty, but fixed) sequence of \index{son}{sons}
    (sons are themselves values, so can themselves be integers,
    strings, tuples, sets, sub-nodes). The connective, size and sons
    of a node don't change with time. Since a node is immutable and
    knows all its sons at creation time, circularity (e.g. a node
    having itself as some grand-son) inside it is impossible, and the
    node has a finite depth. Nodes whose connective is an instance of
    \index{transient connective
      object@\texttt{transient\_connective\_object}}
    \texttt{transient\_connective\_object} are not dumped so are
    transient. \index{transient!node} \index{node!transient}

  \item \textbf{closure}. A \index{closure}{closure} is like a node
    (it has a connective and sons), but its connective is interpreted
    as the object giving the \index{routine}{routine} (see
    \S\ref{subsubsec:objects} below) to be called when that closure is
    applied, and its sons are considered as closed values. Closures
    whose connective is an instance of \index{transient connective
      object@\texttt{transient\_connective\_object}}
    \texttt{transient\_connective\_object} are not dumped so are
    transient.
        
\end{itemize}

The \index{nil}{\textbf{nil}} value is generally not considered as a
value, but as the absence of some value. We might (later) add other
kind of values (perhaps vectors of 64 bits integers, of doubles,
bignums ...), but they should all be immutable. However, it is very
likely that we prefer complex or weird data to sit inside objects, as
payload. There is also a single
\index{unspecified}{\textbf{unspecified}} value (which is non-nil so
cannot be confused with lack of value represented by nil).

Tuples and nodes and closures could contain nil, but sets cannot. A
node or closure connective is a genuine object (so cannot be nil),
even if nodes or closures could have nil sons.

Sets and tuples are sometimes both considered as
\index{sequence}{\textbf{sequences}} and share some common operations.

The immutable values are somehow lightweight. Most of them (strings,
sets, tuples, nodes) internally keep some hash-code (e.g. to
accelerate equality tests on them, or accessing hash tables having
values as keys). The memory overhead for values is therefore small (a
few extra words at most, to keep GC-data type and mark, size hash).

The \index{size}{size} of values (byte length of strings, number of objects in
tuples or sets, number of sons in nodes or closures) can in principle reach
$2^{31} - 1$ but is generally much smaller (often less than a few
dozens) and could be 0.

Mutable values outside of objects (and their payload, see
\S\ref{subsubsec:objects} below) cannot exist.

Values (even references to objects, e.g. inside sequences or nodes)
are represented as a machine pointer and fit in a 64 bits word. When
its least significant bit is 1, it is a tagged integer.

Values, including objects, are comparable so sortable. For strings,
nodes, closures, sets, tuples we use a lexicographical order. Values
also have an hashcode to be easily put in hash tables, etc..

%%%%%%%%%%%%%%%%
\subsubsection{Mutable objects}
\label{subsubsec:objects}

\index{object}{Objects} are the only kind of \index{mutable}{mutable}
values, and are somehow heavy (at least several dozens of machine words
in memory for each object). They can be accessed nearly simultaneously
by several worker threads running different tasklets, so they need a
locking mechanism and contain a (recursive) mutex~\footnote{Each
  object has its mutex initialized with
  \href{http://man7.org/linux/man-pages/man3/pthread\_mutex\_init.3p.html}{\texttt{pthread\_mutex\_init}(3p)}
  with the \texttt{PTHREAD\_MUTEX\_RECURSIVE} attribute, and lockable
  with
  \href{http://man7.org/linux/man-pages/man3/pthread\_mutex\_lock.3p.html}{\texttt{pthread\_mutex\_lock}(3p)}
  etc...} (so in reality only one thread is accessing or modifying
them at a given instant).

\medskip

\emph{Conceptually}, objects contain the following data:

\begin{itemize}
  \item a constant \emph{unique} serial id (of about 128 bits), called
    the \index{objid}{\textbf{objid}}, randomly generated at object
    creation time and never changed after. In many occasions, that
    objid is printed as 24 characters {\small (two glued blocks of 12
      characters each, the first being an underscore \texttt{\_}, the
      second being a digit, the 10 others being alphanumerical with
      significant case)} such as
    \texttt{\_4ggW2XwfXdp\_1XRSvOvZqTC}~\footnote{That objid
      \texttt{\_4ggW2XwfXdp\_1XRSvOvZqTC} is for the predefined object
      \emph{\texttt{the\_system}}, and corresponds to the two 64 bits
      numbers 3577488711679049683 {\relsize{-1}{(encoded in base  $62 = 10 + 2 \times 26$ as
      \texttt{4ggW2XwfXdp})}}, 1649751471969277032 i.e. to 128 bits
      hexadecimal \texttt{0x31a5cb0767997fd316e5183916681468}.}  or
    \texttt{\_0xbmmxnN8E8\_0ZuEqJmqMNH}. It is expected that objid
    \index{collision}{collisions} never occur in practice, e.g. that
    even thousands of \emph{Bismon monitor} processes (running on many
    distant computers) would in fact never generate the same objid. In
    other words, our objids are as unique as \index{UUID}{UUID}s (from
    \href{https://tools.ietf.org/html/rfc4122}{RFC 4122}) are (but are
    displayed differently, without hyphens). In practice, the first 5
    or a few more characters of an objid are enough to uniquely
    identify it, and we use the \index{€ objid abbreviation} € objid
    abbreviation~\footnote{This € objid abbreviation is for
      documentation purposes; it is not acceptable in persistent store
      files.}, e.g. \texttt{€\_4ggW2XwfX} - an abbreviation for
    \texttt{\_4ggW2XwfXdp\_1XRSvOvZqTC} - to uniquely identify it. The
    concrete textual ``syntax'' for objid-s (starting with an
    underscore then a digit, etc...) is carefully chosen to be
    compatible and friendly with identifiers in C, C++, JavaScript,
    Ocaml, etc. The \emph{Bismon} runtime maintains a large array of
    hashtables and mutexes to be able to quickly find the object
    pointer of a given objid (if such an object exists in memory). The
    objid is used to compare (and sort) objects. The (32 bits,
    non-zero) hash code of an object is obtained from its objid (but
    it is cached in the object's memory, for performance reasons).

    \item the recursive \textbf{mutex lock} of that object~\footnote{We
      have considered using a pthread \texttt{rwlock} instead of a
      \texttt{mutex}, but that would probably be more heavy and
      perhaps slower, but could be experimented in the future.}. So
      locking (or unlocking) an object really means using that lock on
      pthread mutex operations~\footnote{So accessing without the
        protection of that lock being hold, any data inside an object,
        other than its constant objid, its class, its routine pointer,
        is forbidden and considered as \emph{undefined behavior}}.

  \item a \index{space}{\textbf{space}} number fitting in a single
    byte. The space 0 is for \index{transient}{\emph{transient}}
    objects that are not persisted to disk. The space 1 is for
    \index{predefined}{\emph{predefined}} objects (there are about 60
    of them in Q3 of 2018), which are conceptually created before the
    start of \emph{Bismon monitor} processes and are permanently
    available, even at initial load time of the persistent
    store. Those predefined objects are dumped in file
    \texttt{store1.bmon}, the objects of space 2 (conventionally
    called the \emph{global} space) are dumped and persisted in file
    \texttt{store2.bmon}, etc...

    \item the \index{mtime}{\textbf{mtime}} of an object holds its
      modification time, with a millisecond granularity, since the
      Unix Epoch. \index{touch}{Touching} an object is updating its
      \emph{mtime} to the current time.

    \item the (mutable!) \index{class}{\textbf{class}} of an object is
      an \index{atomic}{\emph{atomic}}~\footnote{Here, ``atomic'' is
        understood in the C or C++ memory sense; so a pointer declared
        \texttt{\_Atomic} in C or \texttt{std::atomic} in C++,
        supposing that they are the same and interoperable. Hence the
        class of an object can be obtained \emph{without} locking that
        object.} pointer to an object (usually another one) describing
      its class, as understood by \emph{Bismon}. It is allowed to
      change dynamically~\footnote{Changing classes is permitted
        within reasonable bounds: the class of all classes should
        remain the \emph{\texttt{class}} predefined object; all
        objects should be instances of the predefined
        \emph{\texttt{object}} or more often of some indirect
        sub-class of it; of course these invariants cannot be proved.}
      the class of any object. Classes describe the behavior (i.e. the
      dictionary of ``methods''), not the content (i.e. the
      ``attributes'') of objects and enable single-inheritance (every
      class has one super-class).

    \item the \index{attribute}{\emph{attributes}} of an object are
      organized as an hash-table associating attribute or key objects
      to arbitrary non-nil values. An \textbf{attribute} is an
      arbitrary object, and its value is arbitrary (but cannot be
      nil).

    \item the \index{component}{\emph{components}} of an object are
      organized as a vector (whose size can change, grow, or shrink)
      of values. A \textbf{component} inside an object is a value
      (possibly nil).

      \item objects may contain one \textbf{routine} pointer (or nil),
        described by \begin{enumerate}
          
        \item the \index{routine address}{\emph{routine address}}
          inside an object is a function or \index{routine}{routine}
          pointer (in the C sense, possibly and often nil). The
          signature of that function is described by the routine
          signature~\footnote{Perhaps all our routines will keep the
            same signature, and then it would not need to be
            explicitly stored.}

        \item the \index{routine signature}{\emph{routine signature}}
          is (when the routine address is non-nil) describing the
          signature of the routine address above.
      \end{enumerate}

      Notice that routine address and signature can only change when
      a new module~\footnote{The generated C code of modules also
        contains an array of constant objids, ana another array of
        routine objids.} is loaded (or at initial persistent state load
      time), and that can happen only when the agenda is
      inactive. Conceptually they are mostly constant (and do not
      require any locking).
        
      Most (in 2018, all) routines have the same C signature
      \texttt{objrout\_sigBM} corresponding to the predefined object
      \texttt{\emph{function\_sig}}. For an object of objid
      {$\Omega$} of that signature its routine address
      corresponds to the C name \texttt{crout}{$\Omega$}\texttt{\_BM}. For
      instance, to initialize (at load time) the object of oid
      \texttt{\_9CG8SKNs6Ql\_4PiHd8cnydn} the initial loader (or the
      module loader) would \texttt{dlsym} the
      \texttt{crout\_09Hug4WGnPK\_7PpZby8pz84\_BM} C function name.


      \item objects may also have some (nearly arbitrary)
        \index{payload}{\textbf{payload}} - which can contain anything
        that don't fit elsewhere. That payload~\footnote{Some weird
          payloads, in particular for web exchanges and web sessions,
          cannot be created programmatically by public functions or by
          Bismon code. Web exchange and web session payloads (cf
          \S\ref{subsec:webinterf}) are only internally created by the
          HTTP server code in \emph{bismon}, and cannot and should not
          be persisted.} is a pointer (possibly nil) to some client
        data owned by the object; the payload is usually not a value
        but something else. The garbage collector should know all the
        payload types. In 2018 the following payloads are possible
        (with other specialized payloads, e.g. for parsing, loading,
        dumping and web request and web session support,
        contributors):

        \begin{enumerate}
        \item mutable \index{string buffer}{\emph{string buffer}}.
          \item mutable \index{class}{\emph{class} information} (with its super class, and
            the method ``dictionary'' associating objects -selectors-
            to closures). The class objects are required to have such
            a payload.
        \item mutable \index{vector}{\emph{vector}} of values (like
          for components).
        \item mutable  doubly \index{linked list}{\emph{linked list}} of non-nil values.
        \item mutable \index{associative table}{\emph{associative
            table}} associating objects to non-nil values (like for
          attributes)
        \item mutable \index{hash set}{\emph{hash set}} of objects.
        \item mutable \index{hash map}{\emph{hash maps}} to associate arbitrary
            non-nil values used as keys to other arbitrary non-nil
            values.
        \item mutable \index{dictionary}{\emph{string dictionaries}} associating
          non-empty strings to non-nil values.
        \item mutable JSON \index{JSON} data~\footnote{That is, \texttt{json\_t*} from the \emph{Jansson} library. It is practically useful for WebSocket messages.} 
        \item etc...
        \end{enumerate}

        Of course, the payload of an object should be initialized (so
        created), accessed, used, modified, changed to another
        payload, cleared (so deleted) only while that object is
        locked, and each payload belongs to only one object, its
        owner.
       
\end{itemize}

The ability to have \emph{arbitrary} attributes and components in
every \emph{Bismon} object makes them \textbf{very flexible}
(cf. \cite{Lenat:1983:Eurisko, Lenat:1991:ev-cycl}), and is \emph{on purpose}
related to \href{https://en.wikipedia.org/wiki/Frame\_language}{frame
  languages} (cf. \cite{Bobrow-Winograd:1977:KRL}),
\href{https://en.wikipedia.org/wiki/Semantic\_network}{semantic
  network}s (cf \cite{VanDeRiet:1992:Ling-instr-know}) and
\href{https://en.wikipedia.org/wiki/Ontology\_engineering}{ontology
  engineering} (cf \cite{DeNicola:2009:OntologyBuilding}).

\medskip

For convenience, (some) objects can also be (optionally) named, in
some top-level \index{dictionary}{``dictionary''} or ``symbol
table'' (which actually contain weak references to named objects). But
the \index{name}{name} of an object is not part of it.

\bigskip

\subsection{garbage collection of values and objects}
\label{subsec:gcvalobj}

The \emph{Bismon monitor} has in 2018 a precise, but naive,
mark\&sweep stop-the-world \index{garbage collector}{garbage
  collector} for values \footnote{See also previous footnote
  \ref{fn:initial-gc} on page \pageref{fn:initial-gc} for possible
  improvements of the GC.}, of course including objects. When the GC
is running, the agenda has been de-activated, and no tasklets are
running. Our initial GC is known to not scale well and to be
unfriendly to serious interactive usage, so it should be replaced (see
footnote \ref{fn:initial-gc} in \S\ref{subsubsec:about-bismon} above).

In contrast to most GC implementations (but inspired by the habits of
\emph{GCC} itself -in its \emph{Ggc} garbage collector- in that area),
the garbage collector of the \emph{Bismon monitor} is \textbf{not}
\emph{directly} triggered in allocation routines (but is started by
the agenda machinery). When allocation routines detect that a
significant amount of memory has been consumed, they set some atomic
flag for wanting GC, and later that flag would be tested (regularily)
by the agenda machinery which runs the GC.  So when the GC is actually
running, the call stacks are conceptually empty~\footnote{But the
  support threads, e.g. for web service with \texttt{libonion}, add
  complication to this scheme. However, ignoring conceptually the call
  stacks don't require us to use A-normal forms in module code, as was
  needed in \emph{GCC MELT}, and facilitate thus the generation of C
  code inside them.}, and no tasklet is active.

The garbage collection roots include:

\begin{itemize}
\item all the \index{tasklet}{tasklets} queued in the (several queues) of the agenda
\item all the \index{predefined}{predefined} objects
  \item all the constants (objects~\footnote{The object of objid
    \texttt{\_1FEnnpEkGdI\_5DAcVDL5XHG} should be designed as
    \texttt{BMK\_1FEnnpEkGdI\_5DAcVDL5XHG} in hand-written C code if
    it is not predefined, and a special utility collects all such
    names and generates a table of all these constants.}) referred by
    both hand-written and generated C code (including constants
    referred by \index{module}{modules}, and objects reifying
    modules).
\item some very few global variables (containing values), so
  conceptually the idle queue of closures, and the queue related to
  external running processes, the hash-set of active web request
  objects, etc.
\end{itemize}

The naive \emph{Bismon monitor} garbage collection~\footnote{Some
  previous experimentation with Boehm's GC in multithreaded settings
  has been unsatisfactory.}  works as follow: a queue of non-visited
objects to be scanned is maintained, with an hash-set of marked
objects. Initially, we visit the GC roots above. Visiting a value
involves marking it (recursively for sequences, nodes, closures, ...)
and if it is a newly marked object absent from the hash-set, adding
that object to the scan queue and to the hash set of marked objects,
but nodes or closures whose connective is an instance of
\index{transient connective
  object@\texttt{transient\_connective\_object}}
\texttt{transient\_connective\_object} are ignored so transient. We
repeatedly extract objects to be scanned from the queue and visit
their content (including their attributes, their components, their
signature and payload and the values inside that payload). When the
scan queue is empty, GC is finished.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{persistence in \emph{Bismon}}
\label{subsec:persistence}

\index{persistence}{\emph{Persistence}} is an essential feature of the
\emph{Bismon monitor}, and did inspire the ongoing work in
\index{RefPerSys project@\textsc{RefPerSys} project}
\href{http://refpersys.org/}{\textsc{RefPerSys}}.  \index{load} It
always starts by loading some previous persisted \index{state}{state},
and usually dumps \index{dump} its current state before
termination. On the next run, that new state is loaded, etc....  For
convenience and portability, \emph{the persistent state is a set of
  textual files}~\footnote{A gross analogy is the textual dump of some
  SQL database. That dump is the only way to reliably recover the
  database, so it should be done frequently and the backed-up
  \texttt{database.sql} textual dump can be a large file of many
  gigabytes.}.

In the Internet world, persistence is generally handled \emph{outside}
of the application, by using \index{database} databases. These
databases can be relational (see \cite{Date:2005:Database-in-Depth})
or non-relational (so called \emph{NoSQL} databases, see
\cite{RAJ-2018-NoSQL}). Relational databases are often SQL based
(cf. \cite{Date:2011:SQL-relth}), so applications are using a
relational database management system (or server) such as
\textsc{PostGreSQL}~\footnote{See \bmurl{http://postgresql.org/} for
  more.} or \textsc{MySQL}~\footnote{See \bmurl{http://mysql.com/} and
  its close variant \bmurl{http://mariadb.org/} for more. Notice also
  that \bmurl{http://sqlite.org/} is a library often used to embed a
  single, simple, relational database inside a program.}, etc etc...
Databases are routinely capable to deal with a very large amount of
data (e.g. many terabytes or even petabytes), much more than the
available RAM, because the application using some database is
\emph{explicitly} fetching and updating only a tiny part of it. Hence
such persistence is not orthogonal.

\emph{Orthogonal persistence} \index{persistence!orthogonal}
\index{orthogonal persistence} (see \cite{Dearle-2010-orthopersist})
is defined in
\href{https://en.wikipedia.org/wiki/Persistence\_(computer\_science)\#Orthogonal\_or\_transparent\_persistence}{Wikipedia} as~: ``Persistence is said to be "orthogonal" or "transparent" when it is
implemented as an intrinsic property of the execution environment of a
program. An orthogonal persistence environment does not require any
specific actions by programs running in it to retrieve or save their
state.''.

Since the \emph{Bismon} monitor deals only with the source code of
some (perhaps large) IoT firmware and its related internal
representations, the total volume of data should easily fit inside the
RAM of a high-end workstation. For example, several millions lines of
source code makes a large IoT firmware~\footnote{Most of the firmware
we heard of, even from \textsc{Chariot} partners, have less than
several hundreds thousands lines of C or C++, which expands to one or
two millions Gimple statements. This should fit into one or a few
dozens of gigabytes at most, even taking into account that several
variants of internal representations are kept.} but can be kept in
RAM. Hence \emph{Bismon} favors a (nearly) orthogonal persistence. The
only action required to keep its state is a full dump of its entire
persistent heap. An important insight is the similarity between the
depth-first \index{depth-first} \index{exploration!depth-first}
\index{search!depth-first} exploration \index{algorithm} algorithm
\index{decision!algorithm} (see also \cite{Cormen:2009:Intro-algo,
  Christian:2017:algorithms}) used to dump \index{dump} a persistent
\index{persistent state} state, and classical copying or
\href{https://en.wikipedia.org/wiki/Tracing\_garbage\_collection}{tracing
  garbage collection} \index{garbage collection}
\index{tracing!garbage collection} \index{copying!garbage collection}
algorithms (such as \cite{Cheney:1970:CopyingGc}, or more recent
generational copying GCs, see \cite{Jones:2016:GC-handbook}).

The persistent state should be considered as precious and as valuable
as source code of most software, so it should be backed-up and
probably version-controlled~\footnote{How and when the persistent
  state is dumped, backed up and version controlled is out of scope of
  this report. We strongly recommend doing that frequently, at least
  several times every day and probably a few times each hour. If the
  \textit{Bismon monitor} crashes, you have lost everything since the
  latest dumped persistent store. The textual format of the persisted
  state should be friendly to most version control systems and other
  utilities.} at every site using the \emph{Bismon} monitor.

Notice that in \emph{Bismon} only the \emph{heap} is persisted, but
``continuations'' or ``call stacks'' or threads~\footnote{The call
  stack is not formally known to the C11 or C++11 standard (and the
  optimizing C or C++ compiler[s] which optimize[s] \emph{Bismon} code
  is permitted to ``mess it'' during compilation of the \emph{Bismon}
  runtime). Trying to reify and persist it some ``portable'' C or C++
  code is not reasonable, or would require some very implementation-
  and architecture- specific and tricky code. Even generated C as a
  portable assembler don't know about the call stack.}  are \emph{not
  persisted}~\footnote{Some data related to the agenda
  (cf. \S\ref{subsec:multithreadist}) might be persisted. Persisting
  continuations is however an interesting research topic (to be
  worked out outside of \textsc{Chariot}).} by themselves.

%%%%%%%%%%%%%%%%
\subsubsection{file organization of the persistent state}
\label{subsubsec:filestate}

The persistent state contains both data and ``code''. So it is made of the following \index{file}{files}:

\begin{itemize}
\item data files \texttt{store1.bmon}, \texttt{store2.bmon}
  etc... Each such generated data file describes a (potentially large)
  collection of persistent objects, and mentions also the modules
  required for them. There is one data file per space, so
  \texttt{store1.bmon} is for the space\#1 (containing predefined
  objects), \texttt{store2.bmon} is for the space\#2 (conventionally
  containing ``global'' objects useful on every instance of
  \emph{Bismon}), etc...

  \item code files~\footnote{Conceptually, the \texttt{dlopen}-ed
    shared object files, such as our
    \texttt{modubin/modbm\_1zCsXG4OTPr\_8PwkDAWr16S.so} (which
    corresponds to the emitted
    \texttt{modules/modbm\_3BFt4NfJmZC\_7iYi2dwM38B.c} code file) are
    \emph{not} part of the persistent state. In practice, these shared
    object files obviously need to be built before starting
    \emph{bismon}, since it \texttt{dlopen}-s them at initial load
    time.} contain the \emph{generated} C code of persistent modules
    (in the \texttt{modules/} sub-directory). Since each module is
    (also) reified by an object representing (and generating) that
    module, the code file paths contain objids. For example, our
    object \texttt{\_3BFt4NfJmZC\_7iYi2dwM38B} (it is tentatively
    named \texttt{first\_misc\_module}, of class
    \texttt{\emph{basiclo\_dumpable\_module}}) is emitting its C code
    in the generated
    {\small{\texttt{modules/modbm\_3BFt4NfJmZC\_7iYi2dwM38B.c}}} file,
    so that code file is part of the persistent state.
\end{itemize}

Ideally, in the future (after end of \textsc{Chariot}), the
\emph{Bismon monitor} should be entirely bootstapped~\footnote{This
  was not completely the case of \emph{GCC MELT}, but almost: about
  80\% of \emph{GCC MELT} at the end of that project was coded in
  \emph{MELT} itself. However, it was tied to a particular version of
  \emph{GCC}.}, so all its files should be generated (including what
is still in 2018 the hand-coded ``runtime'' part of \emph{Bismon} such
as our \texttt{*\_BM.c} files, notably the load and dump machinery in
\texttt{load\_BM.c} and \texttt{dump\_BM.c}, the agenda mechanism in
\texttt{agenda\_BM.c}, miscellanous routines including the support of
module loading in \texttt{misc\_BM.cc}, etc, etc...). However, we are
still quite far from that ideal. Existing bootstrapped
\index{bootstrap} systems~\footnote{Observe that an entire Linux
  distribution is also, when considered as a single system of ten
  billions lines of source code, fully bootstrapped. You could
  regenerate all of it. See \bmurl{http://www.linuxfromscratch.org/}
  for guidance.} such as \textsc{Caia} \index{CAIA@\textsc{Caia}}
      {\small (see \cite{Pitrat:2000:machine-intelligence, Pitrat:2009:AST, Pitrat:2009:ArtifBeings},  \cite{Pitrat:blog}\footnote{That \href{http://bootstrappingartificialintelligence.fr/WordPress3/}{blog} explains that all the
        \href{http://starynkevitch.net/Basile/caia-su-24feb2016.tar.bz2}{500KLOC of the C code of CAIA and its persistent data} are generated.}, \textsc{Ocaml}
      \index{Ocaml@\textsc{Ocaml}} {\small (cf \cite{Ocaml,
          Leroy-modular-modules} and many other papers by Xavier Leroy
        and the \href{http://gallium.inria.fr/}{Gallium} team at
        INRIA)}, \index{chicken scheme@\textsc{Chicken Scheme}} \index{Scheme@\emph{Scheme}} \textsc{Chicken/Scheme}\footnote{Notice that
        \emph{semantically} \index{semantics} Bismon is quite close to \emph{Scheme} and
        shares many features with that language; see
        \bmurl{http://starynkevitch.net/Basile/guile-tutorial-1.html}
        for more. The \index{bootstrap} bootstrapped \textsc{Chicken}\index{Chicken@\textsc{Chicken}}  system is on
        \bmurl{https://www.call-cc.org/} and is, like Bismon,
        translated to C.}, \textsc{Self} \index{Self@\textsc{Self}}
            {\small (cf \cite{Ungar:1987:Self})},
            \textsc{Sbcl}\footnote{See \bmurl{http://sbcl.org/} for
              more} \index{Sbcl@\textsc{Sbcl}} and \textsc{Clasp}
            \index{Clasp@\textsc{Clasp}} {\small (cf
              \cite{Schafmeister:2015:CLASP})} show that it is
            possible. The major advantage of generating \emph{all} the
            code of \emph{Bismon} would be to deal with internal
            consistency in some automated and systematic way and
            facilitate refactoring~\footnote{In 2018, if we decide
              painfully to change the representation of attribute
              associations in objects, we have to modify a lot of
              hand-written code and objects simultaneously, and that
              is a difficult and brittle effort of refactoring. If all
              our code was generated, it would be still hard, but much
              less.}. An important insight is that the behavior of a
            bootstrapped \index{bootstrap} system can be improved in
            two ways: the ``source'' of the code could be improved (in
            the case of \emph{Bismon}, all the objects describing some
            module) and the ``generator'' of the code could also be
            improved (cf. \index{partial evaluation}{partial
              evaluation} and Futamura \index{projection} projections,
            e.g. \cite{Futamura:1999:PartialEval}; also,
            \cite{Pitrat:2009:ArtifBeings, Pitrat:blog} gives some
            interesting perspectives for artificial intelligence with
            such an approach).

%%%%%%%%%%%%%%%%
\subsubsection{persisting objects}
\label{subsubsec:persistobj}

Obviously, the objects of \emph{Bismon} (\S~\ref{subsubsec:objects})
may have circular references, and circularity can only happen thru
objects (since other composite values such as nodes or sets are
immutable, \S~\ref{subsubsec:immutvalues}). So the initial loader of
the persistent state proceeds in two passes. The first pass is
creating all the persisted objects as empty and loads the modules
needed by them, and the second pass is filling these objects.

\bigskip

\begin{figure}[h]
\fbox{\parbox{\textwidth}{
\begin{scriptsize}
  \verbatiminput{generated/001-extract-firsttestmodule-dump.tex}
\end{scriptsize}
}}
  \caption{generated dump example: \texttt{first\_test\_module} in file
    \texttt{store2.bmon}}
  \label{fig:objdumpfirsttestmodule}
\end{figure}

\bigskip

The figure \ref{fig:objdumpfirsttestmodule} shows an example of the
textual dump for some object (named \texttt{first\_test\_module}) of
objid {\small\texttt{\_9oXtCgAbkqv\_4y1xhhF5Nhz}} extracted from the
data file \texttt{store2.bmon}.

\medskip

\begin{quote}
\begin{small}
%see https://tex.stackexchange.com/a/498475/42406
The lines starting with \index{«@\texttt{«}}\texttt{«} or
\index{"!(@\texttt{"!(}}\texttt{!(} and with
\index{»@\texttt{»}}\texttt{»} or \index{"!)@\texttt{"!)}}\texttt{!)}
are delimiting the object's persistent representation. %
Comments~\footnote{Once the persistence code - loading and
dumping of the state - is mature enough, we will disable generation of
comments in data files.} can start with a bar \texttt{|} till the
      following bar, or with two slashes \texttt{//} till the end of
      line.  {\verb+!~+} with matching {\verb+(~+} ... \verb+~)+ are
      for ``modifications'' (here, we set the
      \index{name}{\texttt{name}} of that object to
      \texttt{first\_test\_module}). Object payloads are also dumped
      in such ``modification'' form. \verb+!@+ puts the
      \index{mtime}{\emph{mtime}}. \verb+!$+ \textit{classobjid} sets
      the \index{class}{class} to the object of objid
      \textit{classobjid}. \verb+!:+ \textit{attrobj} \textit{valattr}
      put the attribute \textit{attrobj} associated with the value
      \textit{valattr}. \verb+!#+ \textit{nbcomp} reserve the spaces
      for \textit{nbcomp}, and \verb/!&/~\textit{valcomp} appends the
      value \textit{valcomp} as a component. The
      \index{"Σ@$\mathtt{\Sigma}$}
      $\mathtt{\Sigma}$ or
      %\index{"!"|@\texttt{!\textbar}}
      \verb+!|+
      is for \index{signature!function} function signatures.

         Within every dumped object, attributes whose class is
         \texttt{temporary\_attribute\_object} are \emph{not}
         \index{temporary attribute
           object@\texttt{temporary\_attribute\_object}} dumped. This
         enables to mix both dumped attributes -as objects these
         attributes are not indirect instances of
         \texttt{temporary\_attribute\_object}\footnote{That
           \texttt{temporary\_attribute\_object} class has objid
           \texttt{€\_23vPTNrGYB}.}- and non-dumped attributes in the
         same object.
\end{small}
\end{quote}


%%%
\begin{figure}[h]
  \begin{center}
  \begin{tabular}{l c l l}
    \emph{value} & $\leftarrow$ & \emph{int} & ; tagged integers \\
                 & $|$ & \emph{float} & ; double precision floats \\
                 & $|$ & \texttt{\textbf{\_\_}} & ; nil \\
                 & $|$ & \texttt{\textbf{"}}\emph{string}\texttt{\textbf{"}} & ; string  {\scriptsize with JSON-like escapes} \\
                 & $|$ & \emph{objid} & ; object  {\scriptsize of given \emph{objid}}\\
                 & $|$ & \texttt{\textbf{\{}} \emph{objid}$_{elem}$ {...} \texttt{\textbf{\}}}  & ; set  {\scriptsize of elements of given \emph{objid}}\\
                 & $|$ & \texttt{\textbf{[}} \emph{objid}$_{comp}$ {...} \texttt{\textbf{]}}  & ; tuple  {\scriptsize of components of given \emph{objid}}\\
                 & $|$ & \texttt{\textbf{*}} \emph{objid}$_{conn}$ \texttt{\textbf{(}} \emph{value}$_{son}$ {...} \texttt{\textbf{)}}  & ; node {\scriptsize of given connective and son[s]}\\
                 & $|$ & \texttt{\textbf{\%}} \emph{objid}$_{conn}$ \texttt{\textbf{(}} \emph{value}$_{son}$ {...} \texttt{\textbf{)}}  & ; closure {\scriptsize of given connective and son[s]}\\
  \end{tabular}
  \end{center}
  \caption{syntax of values in dumped data files.}
  \label{fig:dumpvalsyntax}
\end{figure}

Data files start
first with the \emph{objid} of modules used by routines (in objects
mentioned in that data file). These module-objids are prefixed with
{\bf{\verb+!^+}} or with {\bf{\texttt{µ}}}. Then the collection of
objects (similar to figure \ref{fig:objdumpfirsttestmodule} each)
follows.


%% see also: https://tex.stackexchange.com/a/58811/42406
%%- \begin{quote}
%%-   \begin{relsize}{-1}
%%-   In July 2019, we have changed some lexical tokens
%%-   in data files.  Notice that, inside thes dumped files, \texttt{«} and
%%-   \verb'!(' for object opening, \texttt{»} and \verb'!)' for object
%%-   closing;
%%-   \texttt{µ} and \verb'!^' for modules,
%%-   $\mathtt{\Sigma}$ and \verb'!|'
%%-   for function signatures, \texttt{∈} and \verb'!$' for classes,
%%-   \texttt{±} and \verb'!@' for modtime, \texttt{↦} and \verb'!:' for
%%-   attributes, \texttt{↳} and \verb'!&' for components, are now strictly
%%-   equivalent. The motivation for doing that change is related to
%%-   \bmurl{https://stackoverflow.com/q/46113583/841108} \ldots
%%-   \end{relsize}
%%- \end{quote}

In data files, objects are represented by their \emph{objid}, perhaps
followed by a useless comment like
{\bf{\verb+|+}}\emph{this}{\bf{\verb+|+}}. And immutable values are in
the grammar given in figure \ref{fig:dumpvalsyntax} (where
\textbf{\texttt{\_\_}}, representing \emph{nil}, can also appear
inside tuples, nodes, closures but not within sets). The
\emph{float}-s are dumped~\footnote{ We don't care about some IEEE-754
  double-precision 64 bits floating point numbers not retaining all
  their significant bits between dump and reload.} with best
effort. At dump time, a \index{transient}{transient} object is
replaced as \emph{nil}, so may be dumped as
\textbf{\texttt{\_\_}}. Within a set, it is skipped so ignored. When
the connective of a node or of a closure is a transient object, that
node or closure is not dumped, but entirely replaced by \emph{nil} so
dumped as \textbf{\texttt{\_\_}}.

The dump works, in a similar fashion of our naive GC, in two phases: a
scanning phase to build the hash-set of all dumped objects. A queue of
objects to be scanned is also used. Then an emission phase is dumping
them (one data file per object space). A \emph{dumper} \index{dumper}
transient object -of class \texttt{dumper\_object} \index{dumper
  object@\texttt{dumper\_object}} is made to reify the ``global'' dump
status (notably the queue of objects to scan, and the hash-set of
dumped objects). So dumping happens by sending messages with selectors
-used by the dumping routine sending messages- like
\texttt{dump\_scan}, \texttt{dump\_value}, \texttt{dump\_data}.  The
\texttt{dump\_scan} \index{dump scan@\texttt{dump\_scan}} message is
sent\footnote{The \emph{dumper} object is the additional argument to
\texttt{dump\_scan}.} to a scanned object having some payload during
the scanning phase. The \texttt{dump\_value} \index{dump
  value@\texttt{dump\_value}} message is sent\footnote{Additional
arguments to to \texttt{dump\_value} are a string buffer object, the
\emph{dumper} object, and the depth as a tagged integer. Notice that
dumping of integers is implemented with the \texttt{dump\_value}
method of class \texttt{int}, dumping of tuples is implemented with
the \texttt{dump\_value} method of class \texttt{tuple}, dumping of
object references as objids \index{objid} is implemented with the
\texttt{dump\_value} method of class \texttt{object}, etc....} is to
dumped values during the emission phase.  The \texttt{dump\_data}
\index{dump data@\texttt{dump\_data}} message is sent\footnote{Extra
arguments to \texttt{dump\_value} are: the \emph{dumper} object and
the string buffer object.} when emitting an object content -notably
its payload - \index{payload} if relevant-, after having dumped its
class, attributes and components. But attributes \index{attribute}
which are direct or indirect instances of
\texttt{temporary\_attribute\_object} are not dumped. Coupling
databases with graphical interfaces and \textsc{Gcc} plugins have been
achieved in \cite{Dean:2009:visual}.



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