From 025622f7ba344b1e47dd47c92ed380902ecbddfd Mon Sep 17 00:00:00 2001
From: Bent Bisballe Nyeng <deva@aasimon.org>
Date: Sun, 6 Aug 2023 18:18:31 +0200
Subject: A6: WIP (code is done)
---
a6/Makefile | 29 +++++++---
a6/au_BentBisballeNyeng_A6.tex | 117 +++++++++++++++++++++++++++++--------
a6/custom.cc | 128 +++++++++++++++++++++++++++++++++++++++++
a6/generator_stack.h | 94 ++++++++++++++++++++++++++++++
a6/noalloc.cc | 119 ++++++++++++++++++++++++++------------
5 files changed, 419 insertions(+), 68 deletions(-)
create mode 100644 a6/custom.cc
create mode 100644 a6/generator_stack.h
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';
}
--
cgit v1.2.3