diff options
Diffstat (limited to 'a6')
| -rw-r--r-- | a6/Makefile | 29 | ||||
| -rw-r--r-- | a6/au_BentBisballeNyeng_A6.tex | 117 | ||||
| -rw-r--r-- | a6/custom.cc | 128 | ||||
| -rw-r--r-- | a6/generator_stack.h | 94 | ||||
| -rw-r--r-- | a6/noalloc.cc | 119 |
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'; } |