From 5e9ffc26c26cbcb85a9e18f719fde1b9c178477f Mon Sep 17 00:00:00 2001
From: Bent Bisballe Nyeng <deva@aasimon.org>
Date: Sun, 6 Aug 2023 20:10:14 +0200
Subject: A6: WIP (text is more or less in place)

---
 a6/au_BentBisballeNyeng_A6.tex | 223 +++++++++++++++++++++++++++++++++--------
 1 file changed, 182 insertions(+), 41 deletions(-)

(limited to 'a6/au_BentBisballeNyeng_A6.tex')

diff --git a/a6/au_BentBisballeNyeng_A6.tex b/a6/au_BentBisballeNyeng_A6.tex
index c6ad150..107e62a 100644
--- a/a6/au_BentBisballeNyeng_A6.tex
+++ b/a6/au_BentBisballeNyeng_A6.tex
@@ -122,7 +122,18 @@ 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 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 reworked free-standing specification might make this possible in
 the future, similarly to how exceptions and run-time type information
@@ -139,15 +150,24 @@ 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.
+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 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
+The code could simply look something like this:
+
+\footnotesize\begin{lstlisting}[language=C++]
+void* operator new(std::size_t)
+{
+  throw std::bad_alloc();
+}
+\end{lstlisting}\normalsize
+
+The 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.\\
 
 \noindent\begin{tabular}{| l | c | l |}
@@ -156,69 +176,190 @@ 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). \\
+\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
+this is not the case, and therefore other 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
+Write allocator that uses stack-buffer and fails when depleted and try
+it out (monotonic allocations)
 
+\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:
+
+\footnotesize\begin{lstlisting}[language=C++]
+template <typename T, std::size_t S>
+struct StackAllocator
+{
+  ...
+  pointer allocate(size_type n) {
+    if(n > S) throw std::bad_alloc();
+    return buf;
+  }
+
+  void deallocate(void*, size_type) {}
+
+private:
+  T buf[S];
+};
+\end{lstlisting}\normalsize
+
+This allocator can now be used in the following ways:
+
+\footnotesize\begin{lstlisting}[language=C++]
+std::basic_string<char, std::char_traits<char>,
+                  StackAllocator<char, 32>> str(31, 'a');
+
+std::vector<int, StackAllocator<int, 10>> vec{42};
+
+// Pre-c++17 syntax (not verified)
+//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:
+
+\footnotesize\begin{lstlisting}[language=C++]
+template<std::size_t S>
+using String = std::basic_string<char, std::char_traits<char>,
+                                 StackAllocator<char, S>>;
+\end{lstlisting}\normalsize
+
+\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
+removed - so this is no longer supported\cite{P0302R0}.
+
+Co-routines doesn't support custom allocator 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.
+This new implementation resides in \texttt{generator\_stack.h} and the
+main change is these few lines:
+
+\footnotesize\begin{lstlisting}[language=C++]
+template <typename T, std::size_t S>
+struct Generator
+{
+  ...
+  struct promise_type // required
+  {
+    ...
+    void* operator new(std::size_t n)
+    {
+      static char buf[S];
+      if(n < S) throw std::bad_alloc();
+      return buf;
+    }
+  };
+};
+\end{lstlisting}\normalsize
+
+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
+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.
 
 \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.
+\footnotesize\begin{lstlisting}[language=C++]
+namespace memory
+{
+  void* ptr{};
+  std::size_t n{};
+}
+
+void* operator new(std::size_t n)// throw(std::bad_alloc)
+{
+  if(memory::ptr == nullptr) throw std::bad_alloc();
+  if(n > memory::n) throw std::bad_alloc();
+
+  auto ptr = memory::ptr;
+  memory::ptr = nullptr; // use only once
+  memory::n = 0;
+
+  return ptr;
+}
+\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.
+
+The stack object itself can then be made with the following type:
+
+\footnotesize\begin{lstlisting}[language=C++]
+template<std::size_t S, typename T = char>
+class StackNew
+{
+public:
+  StackNew()
+  {
+    memory::ptr = buf;
+    memory::n = S * sizeof(T);
+  }
+
+private:
+  T buf[S];
+};
+\end{lstlisting}\normalsize
+
+The code for these experiments can be found in the \texttt{stack\_new.cc} file.
+
+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}.
+This means that objects can be made with the following syntax:
+
+\footnotesize\begin{lstlisting}[language=C++]
+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
+\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.
 
 \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.
+microcontrollers perhaps it is worth the price?
 
 \printbibliography
 
-- 
cgit v1.2.3

