A6: WIP (text is more or less in place)

6 files changed, 441 insertions, 45 deletions

diff --git a/a6/.gitignore b/a6/.gitignore
new file mode 100644
index 0000000..95c9f84
--- /dev/null
+++ b/a6/.gitignore
@@ -0,0 +1,12 @@
+au_BentBisballeNyeng_A6.aux
+au_BentBisballeNyeng_A6.bbl
+au_BentBisballeNyeng_A6.bcf
+au_BentBisballeNyeng_A6.blg
+au_BentBisballeNyeng_A6.log
+au_BentBisballeNyeng_A6.pdf
+au_BentBisballeNyeng_A6.run.xml
+au_BentBisballeNyeng_A6.xdv
+custom
+fragmentation.pdf
+noalloc
+stack_new
diff --git a/a6/Makefile b/a6/Makefile
index bc38dd3..bd3743b 100644
--- a/a6/Makefile
+++ b/a6/Makefile
@@ -16,10 +16,10 @@ custom: custom.cc Makefile
 pdf: ${TEX_NAME}.pdf
 
 ${TEX_NAME}.bbl: ${TEX_NAME}.bcf
-	biber --onlylog $<
+	biber --onlylog $< || biber $<
 
 ${TEX_NAME}.bcf: ${TEX_NAME}.tex
-	xelatex --no-pdf --no-aux ${TEX_FLAGS} $<
+	xelatex --no-pdf ${TEX_FLAGS} $<
 
 ${TEX_NAME}.pdf: ${TEX_NAME}.tex ${TEX_NAME}.bbl
 #	xelatex --no-pdf ${TEX_FLAGS} $<
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
 
diff --git a/a6/generator.h b/a6/generator.h
new file mode 100644
index 0000000..c857a40
--- /dev/null
+++ b/a6/generator.h
@@ -0,0 +1,86 @@
+// -*- c++ -*-
+#pragma once
+
+// The code in this file has been taken directly from:
+// https://en.cppreference.com/w/cpp/language/coroutines
+
+#include <coroutine>
+#include <cstdint>
+#include <exception>
+#include <iostream>
+
+template <typename T>
+struct Generator
+{
+	// The class name 'Generator' is our choice and it is not required for coroutine
+	// magic. Compiler recognizes coroutine by the presence of 'co_yield' keyword.
+	// You can use name 'MyGenerator' (or any other name) instead as long as you include
+	// nested struct promise_type with 'MyGenerator get_return_object()' method.
+
+	struct promise_type;
+	using handle_type = std::coroutine_handle<promise_type>;
+
+	struct promise_type // required
+	{
+		T value_;
+		std::exception_ptr exception_;
+
+		Generator get_return_object()
+		{
+			return Generator(handle_type::from_promise(*this));
+		}
+		std::suspend_always initial_suspend() { return {}; }
+		std::suspend_always final_suspend() noexcept { return {}; }
+		void unhandled_exception() { exception_ = std::current_exception(); } // saving
+		// exception
+
+		template <std::convertible_to<T> From> // C++20 concept
+		std::suspend_always yield_value(From&& from)
+		{
+			value_ = std::forward<From>(from); // caching the result in promise
+			return {};
+		}
+		void return_void() { }
+	};
+
+	handle_type h_;
+
+	Generator(handle_type h)
+		: h_(h)
+	{
+	}
+	~Generator() { h_.destroy(); }
+	explicit operator bool()
+	{
+		fill(); // The only way to reliably find out whether or not we finished coroutine,
+		        // whether or not there is going to be a next value generated (co_yield)
+		        // in coroutine via C++ getter (operator () below) is to execute/resume
+		        // coroutine until the next co_yield point (or let it fall off end).
+		        // Then we store/cache result in promise to allow getter (operator() below
+		        // to grab it without executing coroutine).
+		return !h_.done();
+	}
+	T operator()()
+	{
+		fill();
+		full_ = false; // we are going to move out previously cached
+		// result to make promise empty again
+		return std::move(h_.promise().value_);
+	}
+
+private:
+	bool full_ = false;
+
+	void fill()
+	{
+		if (!full_)
+		{
+			h_();
+			if (h_.promise().exception_)
+				std::rethrow_exception(h_.promise().exception_);
+			// propagate coroutine exception in called context
+
+			full_ = true;
+		}
+	}
+};
diff --git a/a6/references.bib b/a6/references.bib
index 5e0e27a..8616a99 100644
--- a/a6/references.bib
+++ b/a6/references.bib
@@ -39,6 +39,24 @@
 
 @website{craig,
   author = {Ben Craig},
-	title = {P2268R0 - Freestanding Roadmap},
-	url = {https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2268r0.html}
+  title = {P2268R0 - Freestanding Roadmap},
+  url = {https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2268r0.html}
+}
+
+@website{mapo,
+  author = {MaPo},
+	title = {Stack Overflow: Template parametric type Allocator in C++},
+  url = {https://stackoverflow.com/questions/66891368/template-parametric-type-allocator-in-c}
+}
+
+@article{P0302R0,
+  title = {Deprecating Allocator Support in std::function},
+  url = {https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0302r0.html},
+  author = {Jonathan Wakely}
+}
+
+@website{coroutines,
+  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
diff --git a/a6/stack_new.cc b/a6/stack_new.cc
new file mode 100644
index 0000000..49f234f
--- /dev/null
+++ b/a6/stack_new.cc
@@ -0,0 +1,139 @@
+#include <iostream>
+#include <string>
+#include <functional>
+#include <stdexcept>
+
+#include "generator.h"
+
+// Universal allocator
+namespace memory
+{
+	void* ptr{};
+	std::size_t n{};
+}
+
+void* operator new(std::size_t n)// throw(std::bad_alloc)
+{
+	std::cout << "new (" << n << " bytes from "
+	          << memory::ptr << " which is size " << memory::n << ")\n";
+
+	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;
+}
+
+void operator delete(void*) throw()
+{
+	std::cout << "delete\n";
+	// Do nothing. actual memory is allocated on the stack
+}
+
+void operator delete(void*, std::size_t) throw()
+{
+	std::cout << "delete[]\n";
+	// Do nothing. actual memory is allocated on the stack
+}
+
+template<std::size_t S, typename T = char>
+class StackNew
+{
+public:
+	StackNew()
+	{
+		std::cout << "StackNew ptr=" << (void*)buf
+		          << " of size " << S * sizeof(T) << '\n';
+		memory::ptr = buf;
+		memory::n = S * sizeof(T);
+	}
+
+private:
+	T buf[S];
+};
+
+template<typename T>
+Generator<T> iota(T start)
+{
+	while(true)
+	{
+		co_yield start++;
+	}
+}
+
+int main()
+{
+	std::cout << " ** std::string:\n";
+	{
+		StackNew<100> buffer;
+		std::string str{"hello allocating string world"};
+
+		try
+		{
+			str.reserve(50); // no stack buffer supplied so throws std::bad_alloc
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "Stack buffer missing!\n";
+		}
+	}
+	std::cout << '\n';
+
+
+	std::cout << " ** std::vector:\n";
+	{
+		StackNew<10, int> buffer;
+		std::vector<int> vec{1,2,3,4,5,6,7,8,9,10};
+
+		StackNew<20, int> buffer2;
+		try
+		{
+			vec.resize(21); // throws std::bad_alloc
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "Stack buffer was too small!\n";
+		}
+	}
+	std::cout << '\n';
+
+
+	std::cout << " ** std::function:\n";
+	{
+		std::function<int()> f;
+		{
+			StackNew<32> buffer;
+			char foo[32]{};
+			f = [foo]()
+			    {
+				    int i = 0;
+				    for(auto v : foo)
+				    {
+					    i += v;
+				    }
+				    return i;
+			    };
+		}
+		[[maybe_unused]]auto x = f();
+	}
+	std::cout << '\n';
+
+
+	std::cout << " ** co-routines:\n";
+	{
+		StackNew<100> buffer;
+		auto gen = iota(0);
+		while(true)
+		{
+			auto i = gen();
+			if(i > 10) break;
+			std::cout << i << " ";
+		}
+		std::cout << '\n';
+	}
+	std::cout << '\n';
+
+}