A6: WIP (code is done)

5 files changed, 419 insertions, 68 deletions

diff --git a/a6/Makefile b/a6/Makefile
index 61ea860..bc38dd3 100644
--- a/a6/Makefile
+++ b/a6/Makefile
@@ -1,15 +1,26 @@
+TEX_FLAGS=-halt-on-error -file-line-error -interaction=batchmode
+TEX_NAME=au_BentBisballeNyeng_A6
+CXX_FLAGS=-g -O2 -fconcepts -fcoroutines -Wall -Werror -Wextra -Wconversion -std=c++20
+
 all: noalloc pdf
 
 noalloc: noalloc.cc Makefile
-	g++ -g -O0 -Wall -Werror -Wextra -Wconversion -std=c++20 $< -o $@
+	g++ ${CXX_FLAGS} $< -o $@
+
+stack_new: stack_new.cc Makefile
+	g++ ${CXX_FLAGS} $< -o $@
+
+custom: custom.cc Makefile
+	g++ ${CXX_FLAGS} $< -o $@
+
+pdf: ${TEX_NAME}.pdf
 
-pdf: au_BentBisballeNyeng_A6.pdf
-au_BentBisballeNyeng_A6.bbl: au_BentBisballeNyeng_A6.bcf
-	biber $<
+${TEX_NAME}.bbl: ${TEX_NAME}.bcf
+	biber --onlylog $<
 
-au_BentBisballeNyeng_A6.bcf: au_BentBisballeNyeng_A6.tex
-	xelatex -halt-on-error $<
+${TEX_NAME}.bcf: ${TEX_NAME}.tex
+	xelatex --no-pdf --no-aux ${TEX_FLAGS} $<
 
-au_BentBisballeNyeng_A6.pdf: au_BentBisballeNyeng_A6.tex au_BentBisballeNyeng_A6.bbl
-	xelatex -halt-on-error $<
-	xelatex -halt-on-error $<
+${TEX_NAME}.pdf: ${TEX_NAME}.tex ${TEX_NAME}.bbl
+#	xelatex --no-pdf ${TEX_FLAGS} $<
+	xelatex ${TEX_FLAGS} $<
diff --git a/a6/au_BentBisballeNyeng_A6.tex b/a6/au_BentBisballeNyeng_A6.tex
index ad4cc0d..c6ad150 100644
--- a/a6/au_BentBisballeNyeng_A6.tex
+++ b/a6/au_BentBisballeNyeng_A6.tex
@@ -90,9 +90,11 @@ 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.
+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 most) features, but with a potential known set of restictions or
+least more) features, but with a potential known set of restictions or
 limitations.
 
 \section{Method}
@@ -100,28 +102,73 @@ In the following, 3 methods for managing memory allocations will be
 investigated, and their suitability for real-life applications be
 evaluated:
 \begin{itemize}
-\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 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}
 
-Each of the three will be evaluated with large lambda
-captures, \texttt{std::vector} allocation and some simple co-routines.
-The epxeriments are done on a linux PC using the gcc-11.2 compiler.
+\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}
 
-
-----------------------------------------
-
-
-No access to MMU, implicitly, prohibits calls to delete after
-initialization phase. Otherwise this will lead to memory fragmentation
-which again might lead to free-store depletion and ultimately
-application failure.
+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
@@ -132,6 +179,17 @@ 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
@@ -141,13 +199,26 @@ 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.
 
-No way of telling the compiler that ``no allocations allowed, fail if
-one is made'' exists, but one could wish for such a mechanism in the
-wake of the ``free-standing C++'' subset work.
-One thing is to prohibit use of language constructs that are
-guaranteed to allocate, but quite another is to allow using constructs
-in ways that doesn't make them allocate.
-This, I think, is not part of the ``free-standing C++'' work.
+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
 
diff --git a/a6/custom.cc b/a6/custom.cc
new file mode 100644
index 0000000..4b95e0b
--- /dev/null
+++ b/a6/custom.cc
@@ -0,0 +1,128 @@
+#include <iostream>
+#include <functional>
+#include <limits>
+#include <memory>
+#include <vector>
+#include <cstddef>
+#include <memory>
+
+#include "generator_stack.h"
+
+void* operator new([[maybe_unused]]std::size_t n)
+{
+	std::cout << "new\n";
+	throw std::bad_alloc();
+}
+
+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
+}
+
+// Code heavily inspired by:
+//  https://stackoverflow.com/questions/66891368/template-parametric-type-allocator-in-c
+template <typename T, std::size_t S>
+struct StackAllocator
+{
+	using value_type = T;
+	using size_type = size_t;
+	using pointer = value_type*;
+
+	template<class U> struct rebind { using other = StackAllocator<U, S>; };
+
+	StackAllocator() = default;
+	StackAllocator(const StackAllocator&) = default;
+	template <typename U> StackAllocator(const StackAllocator<U, S>&) {}
+
+	pointer allocate(size_type n)
+	{
+		if(n > S) throw std::bad_alloc();
+		return buf;
+	}
+
+	void deallocate(void*, size_type)
+	{
+	}
+
+private:
+	T buf[S];
+};
+
+template<typename T>
+Generator<T, 64> iota(T start)
+{
+	while(true)
+	{
+		co_yield start++;
+	}
+}
+
+int main()
+{
+	std::cout << " ** std::string:\n";
+	{
+		std::basic_string<char, std::char_traits<char>, StackAllocator<char, 32>> str(31, 'a');
+		std::cout << str << " " << sizeof(str) << '\n';
+
+		std::basic_string<char, std::char_traits<char>, StackAllocator<char, 64>> str2(31, 'a');
+		std::cout << str2 << " " << sizeof(str2) << '\n';
+	}
+	std::cout << '\n';
+
+	std::cout << " ** std::vector:\n";
+	{
+		try
+		{
+			std::vector<int, StackAllocator<int, 10>> vec{42};
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "No SBO for std::vector!\n";
+		}
+	}
+	std::cout << '\n';
+
+
+	std::cout << " ** std::function:\n";
+	{
+//		{ // Support for allocators with std::function removed in C++17
+//			std::function<std::allocator_arg, StackAllocator<int, 10>, int()> f;
+//			char foo[16]{};
+//			f = [foo]() // capture up to 16 bytes is ok for std::function
+//			    {
+//				    int i = 0;
+//				    for(auto v : foo) i += v;
+//				    return i;
+//			    };
+//		}
+	}
+	std::cout << '\n';
+
+
+	std::cout << " ** co-routines:\n";
+	{
+		try
+		{
+			auto gen = iota(0);
+			while(true)
+			{
+				auto i = gen();
+				if(i > 10) break;
+				std::cout << i << " ";
+			}
+			std::cout << '\n';
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "Co-routines always allocate!\n";
+		}
+	}
+	std::cout << '\n';
+}
diff --git a/a6/generator_stack.h b/a6/generator_stack.h
new file mode 100644
index 0000000..682b8e8
--- /dev/null
+++ b/a6/generator_stack.h
@@ -0,0 +1,94 @@
+// -*- 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, std::size_t S>
+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() { }
+
+		void* operator new(std::size_t n)
+		{
+			static char buf[S];
+			std::cout << "alloc!\n";
+			if(n < S) throw std::bad_alloc();
+			return buf;
+		}
+	};
+
+	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/noalloc.cc b/a6/noalloc.cc
index 0da4025..898efb4 100644
--- a/a6/noalloc.cc
+++ b/a6/noalloc.cc
@@ -1,17 +1,12 @@
 #include <iostream>
 #include <functional>
 
-// Universal allocator
-namespace memory
-{
-void* ptr{};
-}
+#include "generator.h"
 
-void* operator new([[maybe_unused]]std::size_t n) // throw(std::bad_alloc) - don't throw
+void* operator new([[maybe_unused]]std::size_t n)
 {
 	std::cout << "new\n";
-	// Just return the supplied stack pointer
-	return memory::ptr;
+	throw std::bad_alloc();
 }
 
 void operator delete(void*) throw()
@@ -26,43 +21,95 @@ void operator delete(void*, std::size_t) throw()
 	// Do nothing. actual memory is allocated on the stack
 }
 
-//void foo() __attribute__((noinline))
+template<typename T>
+Generator<T> iota(T start)
+{
+	while(true)
+	{
+		co_yield start++;
+	}
+}
+
 int main()
 {
-	char buf[256];
-	memory::ptr = buf;
+	std::cout << " ** std::string:\n";
+	{
+		std::string str(15, 'a'); // 15 characters +  zero termination - ok
+		str = "123456789012345"; // 15 characters +  zero termination - ok
+		try
+		{
+			str = "1234567890123456"; // 16 characters +  zero termination
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "Too big for SSO!\n";
+		}
+	}
+	std::cout << '\n';
 
-	std::cout << " ** strings:\n";
-	{ // strings
-		// now this is ok:
-		std::string str(32, 'a');
-		std::cout << str << '\n';
+	std::cout << " ** std::vector:\n";
+	{
+		try
+		{
+			std::vector<int> vec{42}; // even one element is too much, no SBO
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "No SBO for std::vector!\n";
+		}
+	}
+	std::cout << '\n';
 
-		std::string str2(24, 'b');
-		std::cout << str << '\n'; // the contents of str has been overwritten
 
-		// this will also allocate, but supply the same buffer - ok
-		str = "hello world hello world hello world";
+	std::cout << " ** std::function:\n";
+	{
+		{
+			std::function<int()> f;
+			char foo[16]{};
+			f = [foo]() // capture up to 16 bytes is ok for std::function
+			    {
+				    int i = 0;
+				    for(auto v : foo) i += v;
+				    return i;
+			    };
+		}
 
-		// this is also ok, but due to SSO
-		std::string sso{"hello"};
+//		try // this line seem to break gcc...
+//		{
+//			std::function<int()> f;
+//			char foo[17]{};
+//			f = [foo]()
+//			    {
+//				    int i = 0;
+//				    for(auto v : foo) i += v;
+//				    return i;
+//			    };
+//		}
+//		catch(std::bad_alloc &e)
+//		{
+//			std::cout << "Too big for SBO in std::function!\n";
+//		}
 	}
+	std::cout << '\n';
+
 
-	std::cout << " ** lambdas:\n";
-	{ // lambdas
-		std::function<int()> f;
+	std::cout << " ** co-routines:\n";
+	{
+		try
 		{
-			char foo[16]{};
-			f = [=]()__attribute__((noinline)) // capture up 16 bytes - ok
-				{
-					int i = 0;
-					for(auto v : foo)
-					{
-						i += v;
-					}
-					return i;
-				}; // capture foo by copy - inlined
+			auto gen = iota(0);
+			while(true)
+			{
+				auto i = gen();
+				if(i > 10) break;
+				std::cout << i << " ";
+			}
+			std::cout << '\n';
+		}
+		catch(std::bad_alloc &e)
+		{
+			std::cout << "Co-routines always allocate!\n";
 		}
-		[[maybe_unused]]auto x = f();
 	}
+	std::cout << '\n';
 }