\title{Essay: Applying Contemporary C++ in Enviroments Without
Free-Store}
\documentclass[11pt]{article}
\usepackage{graphicx}
%\usepackage{xcolor}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{subfig}
\usepackage{biblatex}
\addbibresource{references.bib}
\renewcommand{\floatpagefraction}{.8}%
%\renewcommand{\thesubfigure}{Figure \arabic{subfigure}}
\captionsetup[subfigure]{labelformat=simple, labelsep=colon}
\pagestyle{fancy}
\author{Bent Bisballe Nyeng <deva@aasimon.org> University of Aarhus}
\begin{document}
\maketitle

\begin{abstract}
%\section*{Abstract}

In this essay I want to examine to which extend it is possible to use
free-store allocating constructs from the standard template library
(STL) and C++ core-language in enviroments without access to a
free-store.
\end{abstract}

\section{Introduction}
C++ contains a lot of helpful constructs that can be widely used,
including in environments without a free-store, such
as \texttt{concepts}, \texttt{module}s, \texttt{template}s in general,
and functions from \texttt{algorithm} in particular but some parts of
the language and the STL is off-limits when building applications in
environments without free-store such as the perhaps obvious, but
useful \texttt{std::vector} or \texttt{std::string}, but also the less
obvious co-routines\cite{belson} or storing lambdas
in \texttt{std::function}s\cite{elbeno}.
This also inherently means that RAII cannot be used for managing memory
allocations (such as smart-pointers), but can still be used for
managing other types of resources, such as locks or hardware
peripheral access.

\subsection{Dynamic Memory Allocation}

There can be many reasons for not allocating on the free-store, either
by convention; ``no allocations allowed after the engines has
started'', or because the hardware or operating system doesn't
have a virtual memory abstraction, ie. doesn't have a memory
management unit (MMU)\cite{tannenbaum}, and therefore, over time, is
at risk at fragmenting the memory available ultimately leading to
memory depletion\cite{weis}.

In the case of memory fragmentation one might argue that it is not the
allocation that is the problem but rather the free'ing since this is
when the fragmentation happens. This problem is shown in
figure \ref{frag}, which might be possible to circumvent in singular
concrete cases, but cannot be solved in general without the page
indirections of the virtual memory\cite{weis}.

\begin{figure}
\makebox[\textwidth][c]{%
\includegraphics[scale=0.8]{fragmentation.pdf}}
\caption{\textit{(a) visualizes the full, free, memory of a system.
Then, in (b), 4 equal-sized chunks of memory has been allocated
filling up the whole memory. In (c) chunk 2 and 4 has been free'd and
finally, in (d), a chunk which can fit in the total amount of
free memory, is being allocated but fails because of memory
fragmentation.}}
\label{frag}
\end{figure}

This can to some degree be prevented by monotonic allocations which
might work for  not very practical in real-world
software and certainly not for the dynamic allocations in the STL or
the core-language.

In particular, a lambda stored in a \texttt{std::function} might
allocate memory on the free-store if the lambda exceeds the size of
the (compiler dependent) small-buffer optimization (SBO) buffer inside
the \texttt{std::functions}\cite{elbeno}. In much the same way as
the \texttt{std::string} has its small string optimization (also
compiler dependent).

\subsection{Free-Standing}

Work is being done to modify the ``free-standing C++'' towards, among
other things, making it run on systems without free-store by isolating
the parts of the STL that can be used entirely without allocating
along with not supporting exceptions and run-time type
information\cite{craig}.

Working with the resulting small sub-set of the available components,
however, is not well suited for making contemporary C++ applications;
too many core components are missing so be able to really call it
contemporary.
The ideal solution would be to find ways to be able to use all (or at
least more) features, but with a potential known set of restictions or
limitations.

\section{Method}
In the following, 3 methods for managing memory allocations will be
investigated, and their suitability for real-life applications be
evaluated:
\begin{itemize}
\item Support from the compiler to fail compilation if an
      unintentional \texttt{new} or \texttt{delete} is being called,
      at least preventing accidental allocations.
\item Using Custom Allocators for the STL components that supports it.
\item Overloading \texttt{new}/\texttt{delete} to use stack allocated
      memory instead of the free-store for all allocation.
\end{itemize}

\noindent{}Each of the three will be evaluated with
\texttt{std::string}, \texttt{std::vector}, \texttt{std::function} and
co-routines.\\
The experiments are done on a linux PC using the gcc-11.2 compiler.

\section{Experiments}

This section describes the work done during the three experiments
along with any numerical or analytical results found.

\subsection{Detecting Allocations}\label{detect}

Searches on the Internet{\tm} has identified no ways of instructing
the compiler that ``no allocations allowed, fail if one is made''.
The reworked free-standing specification might make this possible in
the future, similarly to how exceptions and run-time type information
can be disabled with \texttt{-fno-exceptions} and \texttt{-fno-rtti}.
There exists a \texttt{-ffreestanding} argument, but this follows the
old (current) definition of free-standing and as such allows
dynamic allocation so it cannot be used.

Some constructs have built-in optimizations that make them store their
data in local members, instead of on the free-store through a pointer,
until som limit is reached making it possible to use for
example \texttt{std::string}s or \texttt{std::function}s as long as
they don't require more than $N$ bytes, where $N$ is a compiler
dependent.

To detect if a free-store allocation is done a simple overload
of \texttt{new} and \texttt{delete} can be done, which simply throws
an exeption if called.
This will lead to a run-time error and not a compile-time one as would
have been the ideal solution, but at least it can assists in finding
the $N$ for a specific compiler.

This experiment can be found in the \texttt{noalloc.cc} file. The
following table shows the impirically deduced sizes of $N$ wherever
SSO/SBO is available along with comments about the general component
behaviour.\\

\noindent\begin{tabular}{| l | c | l |}
\hline
Component & $N$ & Comments \\
\hline
\texttt{std::string} & $16$ & Exception propagates to caller. \\
\texttt{std::vector} & N/A  & No SBO, exception propagates to caller. \\
\texttt{std::function} & $16$ & Exception doesn't seem to propagate to
caller (possible gcc bug). \\
co-routine & N/A & No SBO, exception propagates to caller. \\
\hline
\end{tabular}

\subsection{Custom Allocator}

\begin{verbatim}
Write allocator that uses stack-buffer and fails when depleted and try
it out (monotonic allocations)
List the components that supports it
\end{verbatim}

Writing a custom allocator is only a solution to a sub-set of the
allocations in an application, for example if all allocations are
guaranteed to always be of the same size, in which can no
fragmentation will occur.

But for most applications (or at least most parts on an application)
this is not the case, and therefore others means need to be taken into
use.

std::string works, using basic_string, but is a bit clumsy

std::vector works beautifully

std::function as of c++17 can no longer be used with allocators

Adding new operator to promise_type:
https://en.cppreference.com/w/cpp/language/coroutines#Dynamic_allocation


\subsection{Use \texttt{new} with Stack Buffer}
The most common way of addressing this, is simply to only use stack
allocation, or store all objects in as static globals.
But in certain areas of the C++ language dynamic allocation might
occur without the developer knowing about it.
\texttt{std::string}s of sizes that doesn't fit in the SSO buffer is
one example, but even more devious is the capture clause of a
lambda, which might allocate extra memory, if more than $N$ members
are captured, where $N$ is compiler dependent.

Expanding on the overloaded \texttt{new} and \texttt{delete} from
section \ref{detect} a mechanism for using a stack-buffer for exactly
one call to \texttt{new} is made, looking something like this:
\begin{lstlisting}[language=C++]
void foo()
\end{lstlisting}

Object owning the buffer and registering itself with the next call to
new.

Scope of the stack object must be the same as the object using
it. Compiler does not help with that so this must be done by
convention.

\section{Summing Up}

Can be done, but is by no means elegant and can in some solution be
downright dangerous.
But if this is the price to pay to be able to use co-routines in
microcontrollers perhaps it is worth it none the less.

\printbibliography

\end{document}