A6: final(?) read-through

2 files changed, 192 insertions, 120 deletions

diff --git a/a6/au_BentBisballeNyeng_A6.tex b/a6/au_BentBisballeNyeng_A6.tex
index 6acd180..3304874 100644
--- a/a6/au_BentBisballeNyeng_A6.tex
+++ b/a6/au_BentBisballeNyeng_A6.tex
@@ -1,15 +1,13 @@
-\title{Essay: Applying Contemporary C++ in Enviroments Without
-Free-Store}
+\title{Essay: Applying Contemporary C++ in Systems Without Free-Store}
 \documentclass[11pt]{article}
 \usepackage{graphicx}
-%\usepackage{xcolor}
+\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}
@@ -17,8 +15,6 @@ Free-Store}
 \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
@@ -47,13 +43,13 @@ 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}.
+at risk of fragmenting the memory 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. The problem is shown in
-figure \ref{frag}, which might be possible to circumvent in singular
+when the fragmentation happens. The problem, shown in
+figure \ref{frag}, might be possible to work around in singular
 concrete cases, but cannot be solved in general without the page
 indirections of the virtual memory\cite{weis}.
 
@@ -71,50 +67,57 @@ fragmentation.}}
 
 This can to some degree be prevented by monotonic allocations where
 each allocation always has the same size and therefore can be re-used
-directly after being freed. This might work for some special usecases,
-where objects of similar size are being stored in a pool may not be
+directly after being freed. This might work for some special use-cases,
+where objects of similar size are being stored in a pool but is not
 applicable in software in general and certainly not for the dynamic
-allocations in the STL or the core-language.
+allocations in the STL or the core-language which will have varying
+sizes.
 
 In particular, a lambda stored in a \texttt{std::function} might
 allocate memory on the free-store if the lambda captures 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
-(SSO) which are also compiler dependent in size.
+buffer inside the \texttt{std::functions}\cite{elbeno}. The resulting
+allocation will have the size of the captured
+data. \texttt{std::string}s works in much the same way with its small
+string optimization (SSO) which are also compiler dependent in size.
 
 \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}.
+Work is being done to improve on the ``free-standing C++''
+specification 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
+without the need for run-time type information\cite{craig}.
 
-Working with the resulting small sub-set of the available components,
+Working with the resulting reduce sub-set of the available features,
 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
+Too many of the core components are simply missing to be able to call it
+truly contemporary.
+Instead, the ideal solution would be to find ways to be able to use all (or at
+least more) of the 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
+examined, 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.
+\item Do nothing special, but try to make the compiler fail
+      compilation if an unintentional \texttt{new} or \texttt{delete}
+      is being called, at least preventing accidental allocations.
+\item Use Custom Allocators for the STL components that supports it.
+\item Overloading the \texttt{new} and \texttt{delete} operators 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.\\
+a simple example of a generator
+co-routine\footnote{No \texttt{std::generator} was supplied with my
+tool-chain so I had to use a similar implementation
+from \cite{generator} which can be found in the \texttt{generator.h}
+file.}.\\
 The experiments are done on a linux PC using the gcc-11.2 compiler.
 
 \section{Experiments}
@@ -124,40 +127,46 @@ along with any numerical or analytical results found.
 
 \subsection{Detecting Allocations}\label{detect}
 
-The most common way of addressing the problem of allocation with no
-free-store is to simply only use stack allocations, or store all
-objects 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.
-%
-Searches on The Internet\texttrademark{} has identified no ways of instructing
-the compiler that ``no allocations allowed, fail if one is made''.
+The simplest way of addressing the problem of allocation with no
+free-store is to simply only use stack allocation constructs, or store all
+objects as static globals. this could be by using
+the \texttt{std::array} or by using placement \texttt{new} for
+allocating with existing buffers.
+But as mentioned in certain areas of the C++ language dynamic
+allocation might occur without the developer knowing about it.
+Searches on The Internet\texttrademark{} has identified no ways direct
+ways of instructing the compiler that ``no allocations allowed, fail
+if one is made''. The best option I have been able to find is to use a
+combination of odd arguments to prevent linking with the standard
+libraries (primarily libc and libstdc++), provide some specially
+required functions, and then get a linker error if the \texttt{new}
+or \texttt{delete} operator functions were needed\cite{cs107e} - not
+very practical - \textit{and} one would have to compile the program
+twice to first do the check and then to actually create the binary.
 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.
+can be disabled with \texttt{-fno-exceptions} and \texttt{-fno-rtti},
+but that doesn't seem to be around the corner.
+Note that there is an existing \texttt{-ffreestanding} argument, but
+this follows a different definition of free-standing which allows
+dynamic allocation, so this is not a solution.
 
 As mentiond in section \ref{dyn}, 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
+instead of on the free-store through a pointer, until some 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 or when a free-store allocation is done a simple overload
-of \texttt{new} is made, which simply throws an exeption if called.
-This will lead to a run-time error and not a compile-time one, which
-would otherwise have been the ideal solution, but at least it can
-assists in finding the $N$s for a specific compiler.
+To detect if or when a free-store allocation is done (ie. when the $N$
+is exceeded) a simple overload of \texttt{new} operator can be made,
+simply throwing an exeption if called.
+This will lead to a run-time error and not a compile-time error, but
+at least it can assists in finding the $N$s for a specific compiler.
 
-The code could simply look something like this:
+The complete code for this experiment can be found in the
+\texttt{noalloc.cc} file. For reference the code for the \texttt{new}
+operator is listed here:
 
 \footnotesize\begin{lstlisting}[language=C++]
 void* operator new(std::size_t)
@@ -166,49 +175,61 @@ void* operator new(std::size_t)
 }
 \end{lstlisting}\normalsize
 
-The complete code for this experiment can be found in
-the \texttt{noalloc.cc} file.
-The following table shows the impirically deduced sizes of $N$ wherever
-SSO or SBO is available along with comments about the general component
-behaviour. The sizes were simply increased until the compiled program
-started throwing the \texttt{std::bad\_alloc} exception.\\
+For each of the components, the sizes of $N$ were increased until the
+compiled program started throwing the \texttt{std::bad\_alloc} exceptions.
+The following table shows thise impirically deduced sizes of $N$ for my
+specific compiler for the components supporting SSO or SBO 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::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. \\
+co-routine             & N/A  & No SBO, exception propagates to caller. \\
 \hline
-\end{tabular}
+\end{tabular}\\
 
-\subsection{Custom Allocator}
+16 bytes for storing is not much, but for the \texttt{std::function}
+it might be sufficient for most simple lambda captures. For
+the \texttt{std::string}s it might also be reasonable for many uses,
+but since the strings are more dynamic in nature it is easy to
+accidentally break the barrier after a string has been created.
 
-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.
+\subsection{Custom Allocator}
 
-But for most applications (or at least most parts on an application)
-this is not the case, and therefore other means need to be taken into
-use.
+Custom allocators are classes that can be used as replacements for the
+normal \texttt{new} and \texttt{delete} operators for a single object
+instance.
 
-Write allocator that uses stack-buffer and fails when depleted and try
-it out (monotonic allocations)
+This feature is only supported by some of the components in the STL,
+mainly the containers, and can therefore only be used as a solution to
+a sub-set of the allocations in an application.
+In particular they are good for container types that use monotonic
+allocations where all allocations for the same size. Here a freed
+chunk of memory is guaranteed to always be possible to re-use so no
+fragmentation will occur.
 
-\noindent{}The following code was heavily inspired the answer to this
-article \cite{mapo}, heavily modified to take a stack size as a template
-argument:
+For this experiment a custom allocator is written that uses an
+internal member buffer and always returns that when an allocation is
+requested.
+It throws an exception if the allocation size exceeds the buffer size.
+The code can be found in the \texttt{custom.cc} file.
+A summized version of the custom allocator, \texttt{StackAllaocator},
+can be seen below. It was inspired by the answer to this
+article \cite{mapo}, heavily modified to take a stack size as a
+template argument:
 
 \footnotesize\begin{lstlisting}[language=C++]
 template <typename T, std::size_t S>
 struct StackAllocator
 {
   ...
-  pointer allocate(size_type n) {
+  pointer allocate(size_type n)
+  {
     if(n > S) throw std::bad_alloc();
     return buf;
   }
@@ -220,7 +241,7 @@ private:
 };
 \end{lstlisting}\normalsize
 
-This allocator can now be used in the following ways:
+The allocator can be used in the following ways:
 
 \footnotesize\begin{lstlisting}[language=C++]
 std::basic_string<char, std::char_traits<char>,
@@ -232,11 +253,11 @@ std::vector<int, StackAllocator<int, 10>> vec{42};
 //std::function<std::allocator_arg, StackAllocator<int, 10>, int()> f;
 \end{lstlisting}\normalsize
 
-These experiments can be found in the \texttt{custom.cc} file.
 \texttt{std::string} works but need to use
-the \texttt{std::basic\_string} for the instantiation, which is a bit
-clumsy. This can be made a bit easier to read, using a templated type
-indirection only exposing the buffer size as the template argument:
+the basetype, \texttt{std::basic\_string}, for the instantiation,
+which is a bit clumsy.
+This can be made a bit clearer to read by using a templated type
+indirection only exposing the buffer size template argument:
 
 \footnotesize\begin{lstlisting}[language=C++]
 template<std::size_t S>
@@ -247,16 +268,17 @@ using String = std::basic_string<char, std::char_traits<char>,
 \texttt{std::vector} on the other hand works works beautifully. The
 syntax is clean and easy to understand.
 
-In C++17 the custom allocator support in \texttt{std::function}s were
+In C++17 the custom allocator support in \texttt{std::function} were
 removed - so this is no longer supported\cite{P0302R0}.
 
-Co-routines doesn't support custom allocator directly but they can be
+Co-routines doesn't support custom allocators directly but they can be
 made to use a similar construct by adding a \texttt{operator new}
-implementation inside the \texttt{promise\_type}\cite{coroutines}.
-This was done by modifying the \texttt{Generator} class, adding the
-operator along with a template argument specifying the size.
+implementation inside their \texttt{promise\_type}\cite{coroutines}.
+In the experiment it was done by modifying the \texttt{Generator}
+class, adding the operator along with a template argument specifying
+the buffer size.
 This new implementation resides in \texttt{generator\_stack.h} and the
-main change is these few lines:
+main change is shown here:
 
 \footnotesize\begin{lstlisting}[language=C++]
 template <typename T, std::size_t S>
@@ -279,20 +301,22 @@ struct Generator
 The allocator, and therefore the buffer it carries, is stored within
 the object, so the lifetime of the buffer is guaranteed to live as
 long as the object using it.
-The pitfall, though, is that the developer need to guarantee that no
-re-allocations are ever done with any of the objects. Otherwise the
+On the other hand the developer needs to guarantee that no
+re-allocations are ever made with any of the objects. Otherwise the
 same memory would be re-used leading to undefined behaviour.
-A more clever custom allocator could be written that can keep track of how
-much of the buffer has actually been used and make new allocation in
-the style of the monotonic allocator, but then the same problems
-as with the original free-store fragmentation will apply to the stack
-buffer itself.
+A more clever custom allocator could be written that could keep track
+of how much of the buffer has actually been used and make new
+allocation in the style of the monotonic allocator, but then the same
+problems as with the original free-store fragmentation will apply to
+the stack buffer itself.
 
 \subsection{Use \texttt{new} with Stack Buffer}
 
-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:
+To be able to address all allocations in an application this last
+approach examines using the overloaded \texttt{new} and \texttt{delete} from
+section \ref{detect} expanding it with a mechanism for using supplying
+a stack-buffer used in (at most) one call to \texttt{new}.
+It looks like this:
 
 \footnotesize\begin{lstlisting}[language=C++]
 namespace memory
@@ -312,14 +336,20 @@ void* operator new(std::size_t n)// throw(std::bad_alloc)
 
   return ptr;
 }
+
+void operator delete(void*) throw() {}
+void operator delete(void*, std::size_t) throw() {}
 \end{lstlisting}\normalsize
 
 The \texttt{ptr} pointer and accompanying size \texttt{n} is put in a
-namespace to avoid name clashes but is otherwise left ``naked''. The
-pointer is used once and reset to \texttt{nullptr} to avoid being used
-multiple times.
+namespace to avoid name namespace pollution but is otherwise left
+``naked''.
+The pointer is used once in the \texttt{new} operator and reset
+to \texttt{nullptr} to avoid being used again.
+The \texttt{delete} operators must do nothing since the memory was
+owned elsewhere.
 
-The stack object itself can then be made with the following type:
+A stack buffer object is then made with the following type:
 
 \footnotesize\begin{lstlisting}[language=C++]
 template<std::size_t S, typename T = char>
@@ -337,8 +367,9 @@ private:
 };
 \end{lstlisting}\normalsize
 
-The code for these experiments can be found in the \texttt{stack\_new.cc} file.
-
+and the intention is now to have a \texttt{StackNew} instance create
+immediately before any calls to \texttt{new} would happen with an
+appropriate buffer size supplied.
 It both owns the memory and registers its pointer and size in the
 constructor which will be used in the firstcoming call
 to \texttt{new}.
@@ -349,20 +380,49 @@ StackNew<10, int> buffer; // stack buffer for 10 integers
 std::vector<int> vec{1,2,3,4,5,6,7,8,9,10};
 \end{lstlisting}\normalsize
 
-The upside that it works for all allocating object types, including
+The code for these experiments can be found in
+the \texttt{stack\_new.cc} file.
+
+The upside is that it works for all allocating object types, including
 \texttt{std::string}, \texttt{std::vector}, \texttt{std::function} and
-co-routines because the \texttt{new} operator is overridden for the
-entire application.
-The dangers of the mechanism is that it is up to the developer to
-ensure that the stack object outlives the objects that use it.
-The compiler cannot help with this so it must be done by convention.
+co-routines because the \texttt{new} operator is overridden at a
+global level, ie. for the entire application.
+The dangers of the mechanism, however, is that it is up to the developer to
+ensure that the stack objects are large enough for the allocation,
+which can be tricky, and also make sure that it outlives the objects
+that use it.
+The compiler cannot help with any of those properties so it must be
+done by convention and careful code reviews.
 
 \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 the price?
+None of the described methods work for all usecases, and many of them
+are overly complicated to use correctly.
+Even worse is that using them wrong will create bugs that can be very
+hard to find, so they may not be advisable to use.
+
+For the \texttt{std::vector} and \texttt{std::string} the most robust
+solution is probably to use the custom memory allocators and try to
+make the code in a way so that no re-allocations are needed, by
+reserving some known maximum size when creating the object.
+
+For the co-routines, supplying the \texttt{new} operator in
+the \texttt{promise\_type} is a relatively elegant solution, since
+the \texttt{promise\_type} is also the object carrying the rest of the
+state. But again the upper limit needs to be known in advance, which
+need careful attention (avoid recursion?).
+
+The best way to use \texttt{std::function} is likely to just try to
+keep lambda captures small.
+
+Even though the lastly described method works it should probably never
+be used in production code.
+
+So there is no single solution that works well for all constructs, but
+at least it is possible to use many of the contemporary features of
+the language and STL if one is willing to pay the price of extra
+cautiousness - and if this is the price to pay to be able to use
+co-routines in microcontrollers perhaps it is worth it?
 
 \printbibliography
 
diff --git a/a6/references.bib b/a6/references.bib
index 8616a99..af10361 100644
--- a/a6/references.bib
+++ b/a6/references.bib
@@ -59,4 +59,16 @@
   title = {Coroutines (C++20) - Dynamic allocation},
 	url = {https://en.cppreference.com/w/cpp/language/coroutines\#Dynamic_allocation},
 	author = {cppreference.com}
-}
\ No newline at end of file
+}
+
+@website{generator,
+  title = {Coroutines (C++20) - Generator example},
+	url = {https://en.cppreference.com/w/cpp/language/coroutines},
+	author = {cppreference.com}
+}
+
+@website{cs107e,
+  title = {Guide: GCC and Bare Metal Programming},
+	url = {https://cs107e.github.io/guides/gcc/},
+	author = {Pat Hanrahan and Julie Zelenski}
+}