\chapter{Introduction}

% Shared-memory multi-processor computers are ubiquitous and important for improving application performance.
% 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.
% One crucial shared resource is program memory, since it is used by all threads in a shared-memory concurrent-program~\cite{Berger00}.
% Therefore, providing high-performance, scalable memory-management is important for virtually all shared-memory multi-threaded programs.

\vspace*{-23pt}
Memory 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.
A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal.
However, 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).
In general, allocators use a number of similar techniques, each optimizing specific allocation patterns.
Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.


\section{Memory Structure}
\label{s:MemoryStructure}

\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}.
Static code and data are placed into memory at load time from the executable and are fixed-sized at runtime.
Dynamic-allocation memory starts empty and grows/shrinks as the program dynamically creates/deletes variables with independent lifetime.
The programming-language's runtime manages this area, where management complexity is a function of the mechanism for deleting variables.
Dynamic 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}.
However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
Stack memory is managed by the program call-mechanism using a simple LIFO technique, which works well for sequential programs.
For multi-threaded programs (and coroutines), a new stack is created for each thread;
these thread stacks are commonly created in dynamic-allocation memory.
This thesis focuses on management of the dynamic-allocation memory.

\begin{figure}
\centering
\input{AddressSpace}
\vspace{-5pt}
\caption{Program Address Space Divided into Zones}
\label{f:ProgramAddressSpace}
\end{figure}


\section{Dynamic Memory-Management}
\label{s:DynamicMemoryManagement}

Modern programming languages manage dynamic-allocation memory in different ways.
Some 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}.
In general, garbage collection supports memory compaction, where dynamic (live) data is moved during runtime to better utilize space.
However, moving data requires finding pointers to it and updating them to reflect new data locations.
Programming languages such as C~\cite{C}, \CC~\cite{C++}, and Rust~\cite{Rust} provide the programmer with explicit allocation \emph{and} deallocation of data.
These 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.
Attempts have been made to perform quasi garbage collection in C/\CC~\cite{Boehm88}, but it is a compromise.
This thesis only examines dynamic memory-management with \emph{explicit} deallocation.
While 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.

Most programs use a general-purpose allocator, often the one provided implicitly by the programming-language's runtime.
When this allocator proves inadequate, programmers often write specialize allocators for specific needs.
C and \CC allow easy replacement of the default memory allocator with an alternative specialized or general-purpose memory-allocator.
(Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.)
However, high-performance memory-allocators for kernel and user multi-threaded programs are still being designed and improved.
For 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}.
This thesis examines the design of high-performance allocators for use by kernel and user multi-threaded applications written in C/\CC.


\section{Contributions}
\label{s:Contributions}

This work provides the following contributions in the area of concurrent dynamic allocation:
\begin{enumerate}[leftmargin=*]
\item
Implementation 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).

\item
Adopt @nullptr@ return for a zero-sized allocation, rather than an actual memory address, which can be passed to @free@.

\item
Extend the standard C heap functionality by preserving with each allocation:
\begin{itemize}[itemsep=0pt]
\item
its request size plus the amount allocated,
\item
whether an allocation is zero fill,
\item
and allocation alignment.
\end{itemize}

\item
Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ to zero-fill and align when storage is extended or copied.
Without this extension, it is unsafe to @realloc@ storage initially allocated with zero-fill/alignment as these properties are not preserved when copying.
This silent generation of a problem is unintuitive to programmers and difficult to locate because it is transient.

\item
Provide additional heap operations to complete programmer expectation with respect to accessing different allocation properties.
\begin{itemize}
\item
@resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
\item
@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
\item
@realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
\item
@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
\item
@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
\item
@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
\end{itemize}

\item
Provide additional heap wrapper functions in \CFA creating an orthogonal set of allocation operations and properties.

\item
Provide additional query operations to access information about an allocation:
\begin{itemize}
\item
@malloc_alignment( addr )@ returns the alignment of the allocation pointed-to by @addr@.
If the allocation is not aligned or @addr@ is the @nulladdr@, the minimal alignment is returned.
\item
@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@.
\item
@malloc_size( addr )@ returns the size of the memory allocation pointed-to by @addr@.
\item
@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 )@.
\end{itemize}

\item
Provide mostly contention-free allocation and free operations via a heap-per-kernel-thread implementation.

\item
Provide complete, fast, and contention-free allocation statistics to help understand program behaviour:
\begin{itemize}
\item
@malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@.
\item
@malloc_info( options, stream )@ print memory-allocation statistics as an XML string on the specified file-descriptor set by @malloc_stats_fd@.
\item
@malloc_stats_fd( fd )@ set file-descriptor number for printing memory-allocation statistics (default @STDERR_FILENO@).
This file descriptor is used implicitly by @malloc_stats@ and @malloc_info@.
\end{itemize}

\item
Provide extensive runtime checks to valid allocation operations and identify the amount of unfreed storage at program termination.

\item
Build 4 different versions of the allocator:
\begin{itemize}
\item
static or dynamic linking
\item
statistic/debugging (testing) or no statistic/debugging (performance)
\end{itemize}
A program may link to any of these 4 versions of the allocator often without recompilation.
(It is possible to separate statistics and debugging, giving 8 different versions.)

\item
A micro-benchmark test-suite for comparing allocators rather than relying on a suite of arbitrary programs.
These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs
\end{enumerate}

\begin{comment}
\noindent
====================

Writing Points:
\begin{itemize}
\item
Introduce dynamic memory allocation with brief background.
\item
Scope of the thesis.
\item
Importance of memory allocation and micro-benchmark suite.
\item
Research problem.
\item
Research objectives.
\item
The vision behind cfa-malloc.
\item
An outline of the thesis.
\end{itemize}

\noindent
====================

\section{Introduction}
Dynamic 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.

Memory 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.

GNU 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:

\begin{itemize}
\item
malloc: it allocates and returns a chunk of dynamic memory of requested size (FIX ME: cite man page).
\item
calloc: it allocates and returns an array in dynamic memory of requested size (FIX ME: cite man page).
\item
realloc: it reallocates and returns an already allocated chunk of dynamic memory to a new size (FIX ME: cite man page).
\item
free: it frees an already allocated piece of dynamic memory (FIX ME: cite man page).
\end{itemize}

In 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.

\begin{itemize}
\item
aligned\_alloc
\item
malloc\_usable\_size
\item
memalign
\item
posix\_memalign
\item
pvalloc
\item
valloc
\end{itemize}

With 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.

\section{Research Objectives}
Our research objective in this thesis is to:

\begin{itemize}
\item
Design a lightweight concurrent memory allocator with added features and usability that are currently not present in the other memory allocators.
\item
Design a suite of benchmarks to evaluate multiple aspects of a memory allocator.
\end{itemize}

\section{An outline of the thesis}
LAST FIX ME: add outline at the end
\end{comment}