From b4e8a41aca5a22fc02da3b1a29ca10e4d472b6c7 Mon Sep 17 00:00:00 2001 From: Bent Bisballe Nyeng Date: Fri, 4 Aug 2023 21:30:35 +0200 Subject: A6: WIP --- a6/Makefile | 15 ++ a6/au_BentBisballeNyeng_A6.tex | 154 ++++++++++++++++++++ a6/exercise.tex | 50 ------- a6/fragmentation.svg | 321 +++++++++++++++++++++++++++++++++++++++++ a6/noalloc.cc | 68 +++++++++ a6/references.bib | 44 ++++++ 6 files changed, 602 insertions(+), 50 deletions(-) create mode 100644 a6/Makefile create mode 100644 a6/au_BentBisballeNyeng_A6.tex delete mode 100644 a6/exercise.tex create mode 100644 a6/fragmentation.svg create mode 100644 a6/noalloc.cc create mode 100644 a6/references.bib diff --git a/a6/Makefile b/a6/Makefile new file mode 100644 index 0000000..61ea860 --- /dev/null +++ b/a6/Makefile @@ -0,0 +1,15 @@ +all: noalloc pdf + +noalloc: noalloc.cc Makefile + g++ -g -O0 -Wall -Werror -Wextra -Wconversion -std=c++20 $< -o $@ + +pdf: au_BentBisballeNyeng_A6.pdf +au_BentBisballeNyeng_A6.bbl: au_BentBisballeNyeng_A6.bcf + biber $< + +au_BentBisballeNyeng_A6.bcf: au_BentBisballeNyeng_A6.tex + xelatex -halt-on-error $< + +au_BentBisballeNyeng_A6.pdf: au_BentBisballeNyeng_A6.tex au_BentBisballeNyeng_A6.bbl + xelatex -halt-on-error $< + xelatex -halt-on-error $< diff --git a/a6/au_BentBisballeNyeng_A6.tex b/a6/au_BentBisballeNyeng_A6.tex new file mode 100644 index 0000000..ad4cc0d --- /dev/null +++ b/a6/au_BentBisballeNyeng_A6.tex @@ -0,0 +1,154 @@ +\title{Essay: Applying Contemporary C++ in Enviroments Without +Free-Store} +\documentclass[11pt]{article} +\usepackage{graphicx} +%\usepackage{xcolor} +\usepackage{fancyhdr} +\usepackage{listings} +\usepackage{subfig} +\usepackage{biblatex} +\addbibresource{references.bib} +\renewcommand{\floatpagefraction}{.8}% +%\renewcommand{\thesubfigure}{Figure \arabic{subfigure}} +\captionsetup[subfigure]{labelformat=simple, labelsep=colon} +\pagestyle{fancy} +\author{Bent Bisballe Nyeng University of Aarhus} +\begin{document} +\maketitle + +\begin{abstract} +%\section*{Abstract} + +In this essay I want to examine to which extend it is possible to use +free-store allocating constructs from the standard template library +(STL) and C++ core-language in enviroments without access to a +free-store. +\end{abstract} + +\section{Introduction} +C++ contains a lot of helpful constructs that can be widely used, +including in environments without a free-store, such +as \texttt{concepts}, \texttt{module}s, \texttt{template}s in general, +and functions from \texttt{algorithm} in particular but some parts of +the language and the STL is off-limits when building applications in +environments without free-store such as the perhaps obvious, but +useful \texttt{std::vector} or \texttt{std::string}, but also the less +obvious co-routines\cite{belson} or storing lambdas +in \texttt{std::function}s\cite{elbeno}. +This also inherently means that RAII cannot be used for managing memory +allocations (such as smart-pointers), but can still be used for +managing other types of resources, such as locks or hardware +peripheral access. + +\subsection{Dynamic Memory Allocation} + +There can be many reasons for not allocating on the free-store, either +by convention; ``no allocations allowed after the engines has +started'', or because the hardware or operating system doesn't +have a virtual memory abstraction, ie. doesn't have a memory +management unit (MMU)\cite{tannenbaum}, and therefore, over time, is +at risk at fragmenting the memory available ultimately leading to +memory depletion\cite{weis}. + +In the case of memory fragmentation one might argue that it is not the +allocation that is the problem but rather the free'ing since this is +when the fragmentation happens. This problem is shown in +figure \ref{frag}, which might be possible to circumvent in singular +concrete cases, but cannot be solved in general without the page +indirections of the virtual memory\cite{weis}. + +\begin{figure} +\makebox[\textwidth][c]{% +\includegraphics[scale=0.8]{fragmentation.pdf}} +\caption{\textit{(a) visualizes the full, free, memory of a system. +Then, in (b), 4 equal-sized chunks of memory has been allocated +filling up the whole memory. In (c) chunk 2 and 4 has been free'd and +finally, in (d), a chunk which can fit in the total amount of +free memory, is being allocated but fails because of memory +fragmentation.}} +\label{frag} +\end{figure} + +This can to some degree be prevented by monotonic allocations which +might work for not very practical in real-world +software and certainly not for the dynamic allocations in the STL or +the core-language. + +In particular, a lambda stored in a \texttt{std::function} might +allocate memory on the free-store if the lambda exceeds the size of +the (compiler dependent) small-buffer optimization (SBO) buffer inside +the \texttt{std::functions}\cite{elbeno}. In much the same way as +the \texttt{std::string} has its small string optimization (also +compiler dependent). + +\subsection{Free-Standing} + +Work is being done to modify the ``free-standing C++'' towards, among +other things, making it run on systems without free-store by isolating +the parts of the STL that can be used entirely without allocating +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. +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 +limitations. + +\section{Method} +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. +\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. + +\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. + +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 +use. + +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. + +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. + +\printbibliography + +\end{document} diff --git a/a6/exercise.tex b/a6/exercise.tex deleted file mode 100644 index 2cdace6..0000000 --- a/a6/exercise.tex +++ /dev/null @@ -1,50 +0,0 @@ -\title{Essay: Applying contemporary C++ in applications for embedded -microcontrollers.} -\documentclass[11pt]{article} -\usepackage{graphicx} -%\usepackage{xcolor} -\usepackage{fancyhdr} -\usepackage{listings} -\usepackage{subfig} -\renewcommand{\floatpagefraction}{.8}% -%\renewcommand{\thesubfigure}{Figure \arabic{subfigure}} -\captionsetup[subfigure]{labelformat=simple, labelsep=colon} -\pagestyle{fancy} -\author{Bent Bisballe Nyeng University of Aarhus} -\begin{document} -\maketitle - -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. - -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 -use. - -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. - -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. - - - -\end{document} diff --git a/a6/fragmentation.svg b/a6/fragmentation.svg new file mode 100644 index 0000000..4aa629d --- /dev/null +++ b/a6/fragmentation.svg @@ -0,0 +1,321 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + (a) + (b) + (c) + (d) + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/a6/noalloc.cc b/a6/noalloc.cc new file mode 100644 index 0000000..0da4025 --- /dev/null +++ b/a6/noalloc.cc @@ -0,0 +1,68 @@ +#include +#include + +// Universal allocator +namespace memory +{ +void* ptr{}; +} + +void* operator new([[maybe_unused]]std::size_t n) // throw(std::bad_alloc) - don't throw +{ + std::cout << "new\n"; + // Just return the supplied stack pointer + return memory::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 +} + +//void foo() __attribute__((noinline)) +int main() +{ + char buf[256]; + memory::ptr = buf; + + std::cout << " ** strings:\n"; + { // strings + // now this is ok: + std::string str(32, 'a'); + std::cout << str << '\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"; + + // this is also ok, but due to SSO + std::string sso{"hello"}; + } + + std::cout << " ** lambdas:\n"; + { // lambdas + std::function f; + { + 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 + } + [[maybe_unused]]auto x = f(); + } +} diff --git a/a6/references.bib b/a6/references.bib new file mode 100644 index 0000000..5e0e27a --- /dev/null +++ b/a6/references.bib @@ -0,0 +1,44 @@ +@book{tannenbaum, + added-at = {2011-05-03T00:00:00.000+0200}, + author = {Tanenbaum, Andrew S.}, + biburl = {https://www.bibsonomy.org/bibtex/2e90b050159c1629022a54a2bf947f318/dblp}, + interhash = {c97d1fa1663502cf42aaf310cc07056f}, + intrahash = {e90b050159c1629022a54a2bf947f318}, + isbn = {978-0-13-852872-0}, + keywords = {dblp}, + pages = {I-XVII, 1-587}, + publisher = {Prentice Hall}, + timestamp = {2011-05-04T11:32:41.000+0200}, + title = {Structured computer organization, 3rd Edition.}, + year = 1990 +} + +@article{belson, + author = {Belson, Bruce and Xiang, Wei and Holdsworth, Jason and Philippa, Bronson}, + year = {2020}, + month = {02}, + pages = {1-1}, + title = {C++20 Coroutines on Microcontrollers -What We Learned}, + volume = {PP}, + journal = {IEEE Embedded Systems Letters}, + doi = {10.1109/LES.2020.2973397} +} + +@website{elbeno, + author = {Ben Deane}, + title = {Why is a raven like a writing desk? Another myth, about C++ lambdas}, + url = {https://www.elbeno.com/blog/?p=1068} +} + +@website{weis, + author = {Andreas Weis}, + title = {Taming dynamic memory - Andreas Weis - Meeting C++ 2018}, + url = {https://github.com/ComicSansMS/presentations/releases/download/meetingcpp2018/taming_dynamic_memory.pdf}, +% url = {https://www.youtube.com/watch?v=R3cBbvIFqFk} +} + +@website{craig, + author = {Ben Craig}, + title = {P2268R0 - Freestanding Roadmap}, + url = {https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2268r0.html} +} \ No newline at end of file -- cgit v1.2.3