1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
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 <deva@aasimon.org> 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}
|
