source: doc/theses/mubeen_zulfiqar_MMath/intro.tex @ 23f1065

ADTast-experimentalpthread-emulationqualifiedEnum
Last change on this file since 23f1065 was 23f1065, checked in by Peter A. Buhr <pabuhr@…>, 23 months ago

small wording changes to intro and background chapters, continue proofreading allocator chapter

  • Property mode set to 100644
File size: 12.5 KB
Line 
1\chapter{Introduction}
2
3% Shared-memory multi-processor computers are ubiquitous and important for improving application performance.
4% However, writing programs that take advantage of multiple processors is not an easy task~\cite{Alexandrescu01b}, \eg shared resources can become a bottleneck when increasing (scaling) threads.
5% One crucial shared resource is program memory, since it is used by all threads in a shared-memory concurrent-program~\cite{Berger00}.
6% Therefore, providing high-performance, scalable memory-management is important for virtually all shared-memory multi-threaded programs.
7
8\vspace*{-23pt}
9Memory management takes a sequence of program generated allocation/deallocation requests and attempts to satisfy them within a fixed-sized block of memory while minimizing the total amount of memory used.
10A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal.
11However, memory allocators do take advantage of regularities in allocation patterns for typical programs to produce excellent results, both in time and space (similar to LRU paging).
12In general, allocators use a number of similar techniques, each optimizing specific allocation patterns.
13Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
14
15
16\section{Memory Structure}
17\label{s:MemoryStructure}
18
19\VRef[Figure]{f:ProgramAddressSpace} shows the typical layout of a program's address space divided into the following zones (right to left): static code/data, dynamic allocation, dynamic code/data, and stack, with free memory surrounding the dynamic code/data~\cite{memlayout}.
20Static code and data are placed into memory at load time from the executable and are fixed-sized at runtime.
21Dynamic-allocation memory starts empty and grows/shrinks as the program dynamically creates/deletes variables with independent lifetime.
22The programming-language's runtime manages this area, where management complexity is a function of the mechanism for deleting variables.
23Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}.
24However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
25Stack memory is managed by the program call-mechanism using a simple LIFO technique, which works well for sequential programs.
26For multi-threaded programs (and coroutines), a new stack is created for each thread;
27these thread stacks are commonly created in dynamic-allocation memory.
28This thesis focuses on management of the dynamic-allocation memory.
29
30\begin{figure}
31\centering
32\input{AddressSpace}
33\vspace{-5pt}
34\caption{Program Address Space Divided into Zones}
35\label{f:ProgramAddressSpace}
36\end{figure}
37
38
39\section{Dynamic Memory-Management}
40\label{s:DynamicMemoryManagement}
41
42Modern programming languages manage dynamic-allocation memory in different ways.
43Some languages, such as Lisp~\cite{CommonLisp}, Java~\cite{Java}, Haskell~\cite{Haskell}, Go~\cite{Go}, provide explicit allocation but \emph{implicit} deallocation of data through garbage collection~\cite{Wilson92}.
44In general, garbage collection supports memory compaction, where dynamic (live) data is moved during runtime to better utilize space.
45However, moving data requires finding pointers to it and updating them to reflect new data locations.
46Programming languages such as C~\cite{C}, \CC~\cite{C++}, and Rust~\cite{Rust} provide the programmer with explicit allocation \emph{and} deallocation of data.
47These languages cannot find and subsequently move live data because pointers can be created to any storage zone, including internal components of allocated objects, and may contain temporary invalid values generated by pointer arithmetic.
48Attempts have been made to perform quasi garbage collection in C/\CC~\cite{Boehm88}, but it is a compromise.
49This thesis only examines dynamic memory-management with \emph{explicit} deallocation.
50While garbage collection and compaction are not part this work, many of the work's results are applicable to the allocation phase in any memory-management approach.
51
52Most programs use a general-purpose allocator, often the one provided implicitly by the programming-language's runtime.
53When this allocator proves inadequate, programmers often write specialize allocators for specific needs.
54C and \CC allow easy replacement of the default memory allocator with an alternative specialized or general-purpose memory-allocator.
55(Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.)
56However, high-performance memory-allocators for kernel and user multi-threaded programs are still being designed and improved.
57For this reason, several alternative general-purpose allocators have been written for C/\CC with the goal of scaling in a multi-threaded program~\cite{Berger00,mtmalloc,streamflow,tcmalloc}.
58This thesis examines the design of high-performance allocators for use by kernel and user multi-threaded applications written in C/\CC.
59
60
61\section{Contributions}
62\label{s:Contributions}
63
64This work provides the following contributions in the area of concurrent dynamic allocation:
65\begin{enumerate}[leftmargin=*]
66\item
67Implementation of a new stand-lone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
68
69\item
70Adopt @nullptr@ return for a zero-sized allocation, rather than an actual memory address, which can be passed to @free@.
71
72\item
73Extend the standard C heap functionality by preserving with each allocation:
74\begin{itemize}[itemsep=0pt]
75\item
76its request size plus the amount allocated,
77\item
78whether an allocation is zero fill,
79\item
80and allocation alignment.
81\end{itemize}
82
83\item
84Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ to zero-fill and align when storage is extended or copied.
85Without this extension, it is unsafe to @realloc@ storage initially allocated with zero-fill/alignment as these properties are not preserved when copying.
86This silent generation of a problem is unintuitive to programmers and difficult to locate because it is transient.
87
88\item
89Provide additional heap operations to complete programmer expectation with respect to accessing different allocation properties.
90\begin{itemize}
91\item
92@resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
93\item
94@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
95\item
96@realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
97\item
98@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
99\item
100@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
101\item
102@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
103\end{itemize}
104
105\item
106Provide additional heap wrapper functions in \CFA creating an orthogonal set of allocation operations and properties.
107
108\item
109Provide additional query operations to access information about an allocation:
110\begin{itemize}
111\item
112@malloc_alignment( addr )@ returns the alignment of the allocation pointed-to by @addr@.
113If the allocation is not aligned or @addr@ is the @nulladdr@, the minimal alignment is returned.
114\item
115@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory pointed-to by @addr@ is allocated with zero fill, e.g., by @calloc@/@cmemalign@.
116\item
117@malloc_size( addr )@ returns the size of the memory allocation pointed-to by @addr@.
118\item
119@malloc_usable_size( addr )@ returns the usable (total) size of the memory pointed-to by @addr@, i.e., the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
120\end{itemize}
121
122\item
123Provide mostly contention-free allocation and free operations via a heap-per-kernel-thread implementation.
124
125\item
126Provide complete, fast, and contention-free allocation statistics to help understand allocation behaviour:
127\begin{itemize}
128\item
129@malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@.
130\item
131@malloc_info( options, stream )@ print memory-allocation statistics as an XML string on the specified file-descriptor set by @malloc_stats_fd@.
132\item
133@malloc_stats_fd( fd )@ set file-descriptor number for printing memory-allocation statistics (default @STDERR_FILENO@).
134This file descriptor is used implicitly by @malloc_stats@ and @malloc_info@.
135\end{itemize}
136
137\item
138Provide extensive runtime checks to valid allocation operations and identify the amount of unfreed storage at program termination.
139
140\item
141Build 4 different versions of the allocator:
142\begin{itemize}
143\item
144static or dynamic linking
145\item
146statistic/debugging (testing) or no statistic/debugging (performance)
147\end{itemize}
148A program may link to any of these 4 versions of the allocator often without recompilation.
149(It is possible to separate statistics and debugging, giving 8 different versions.)
150
151\item
152A micro-benchmark test-suite for comparing allocators rather than relying on a suite of arbitrary programs.
153These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs
154\end{enumerate}
155
156\begin{comment}
157\noindent
158====================
159
160Writing Points:
161\begin{itemize}
162\item
163Introduce dynamic memory allocation with brief background.
164\item
165Scope of the thesis.
166\item
167Importance of memory allocation and micro-benchmark suite.
168\item
169Research problem.
170\item
171Research objectives.
172\item
173The vision behind cfa-malloc.
174\item
175An outline of the thesis.
176\end{itemize}
177
178\noindent
179====================
180
181\section{Introduction}
182Dynamic memory allocation and management is one of the core features of C. It gives programmer the freedom to allocate, free, use, and manage dynamic memory himself. The programmer is not given the complete control of the dynamic memory management instead an interface of memory allocator is given to the programmer that can be used to allocate/free dynamic memory for the application's use.
183
184Memory allocator is a layer between the programmer and the system. Allocator gets dynamic memory from the system in heap/mmap area of application storage and manages it for programmer's use.
185
186GNU C Library (FIX ME: cite this) provides an interchangeable memory allocator that can be replaced with a custom memory allocator that supports required features and fulfills application's custom needs. It also allows others to innovate in memory allocation and design their own memory allocator. GNU C Library has set guidelines that should be followed when designing a stand-alone memory allocator. GNU C Library requires new memory allocators to have at lease following set of functions in their allocator's interface:
187
188\begin{itemize}
189\item
190malloc: it allocates and returns a chunk of dynamic memory of requested size (FIX ME: cite man page).
191\item
192calloc: it allocates and returns an array in dynamic memory of requested size (FIX ME: cite man page).
193\item
194realloc: it reallocates and returns an already allocated chunk of dynamic memory to a new size (FIX ME: cite man page).
195\item
196free: it frees an already allocated piece of dynamic memory (FIX ME: cite man page).
197\end{itemize}
198
199In addition to the above functions, GNU C Library also provides some more functions to increase the usability of the dynamic memory allocator. Most stand-alone allocators also provide all or some of the above additional functions.
200
201\begin{itemize}
202\item
203aligned\_alloc
204\item
205malloc\_usable\_size
206\item
207memalign
208\item
209posix\_memalign
210\item
211pvalloc
212\item
213valloc
214\end{itemize}
215
216With the rise of concurrent applications, memory allocators should be able to fulfill dynamic memory requests from multiple threads in parallel without causing contention on shared resources. There needs to be a set of a standard benchmarks that can be used to evaluate an allocator's performance in different scenarios.
217
218\section{Research Objectives}
219Our research objective in this thesis is to:
220
221\begin{itemize}
222\item
223Design a lightweight concurrent memory allocator with added features and usability that are currently not present in the other memory allocators.
224\item
225Design a suite of benchmarks to evaluate multiple aspects of a memory allocator.
226\end{itemize}
227
228\section{An outline of the thesis}
229LAST FIX ME: add outline at the end
230\end{comment}
Note: See TracBrowser for help on using the repository browser.