source: doc/theses/mubeen_zulfiqar_MMath/allocator.tex @ a953c2e3

\chapter{Allocator}

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

Writing Points:
\begin{itemize}
\item
Objective of uHeapLmmm.
\item
Design philosophy.
\item
Background and previous design of uHeapLmmm.
\item
Distributed design of uHeapLmmm.

----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----

\PAB{Maybe. There might be an Implementation chapter.}
\item
figure.
\item
Advantages of distributed design.
\end{itemize}

The new features added to uHeapLmmm (incl. @malloc_size@ routine)
\CFA alloc interface with examples.
\begin{itemize}
\item
Why did we need it?
\item
The added benefits.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% uHeapLmmm Design
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Objective of uHeapLmmm}
UHeapLmmm is a lightweight memory allocator. The objective behind uHeapLmmm is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).

\subsection{Design philosophy}
The objective of uHeapLmmm's new design was to fulfill following requirements:
\begin{itemize}
\item It should be concurrent to be used in multi-threaded programs.
\item It should avoid global locks, on resources shared across all threads, as much as possible.
\item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
\item It should be a lightweight memory allocator.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Background and previous design of uHeapLmmm}
uHeapLmmm was originally designed by X in X (FIX ME: add original author after confirming with Peter).
(FIX ME: make and add figure of previous design with description)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Distributed design of uHeapLmmm}
uHeapLmmm's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:

\paragraph{Design 1: Decentralized}
Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
Kernel threads (KT) are assigned to the N heaps.
When KTs $\le$ N, the heaps are uncontented.
When KTs $>$ N, the heaps are contented.
By adjusting N, this approach reduces storage at the cost of speed due to contention.
In all cases, a thread acquires/releases a lock, contented or uncontented.
\begin{cquote}
\centering
\input{AllocDS1}
\end{cquote}
Problems: need to know when a KT is created and destroyed to know when to assign/un-assign a heap to the KT.

\paragraph{Design 2: Centralized}
One heap, but lower bucket sizes are N-shared across KTs.
This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
When KTs $\le$ N, the important bucket sizes are uncontented.
When KTs $>$ N, the free buckets are contented.
Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
\begin{cquote}
\centering
\input{AllocDS2}
\end{cquote}
Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).

Out of the two designs, Design 1 was chosen because it's concurrency is better across all bucket-sizes as design-2 shards a few buckets of selected sizes while design-1 shards all the buckets. Design-2 shards the whole heap which has all the buckets with the addition of sharding sbrk area.

\subsection{Advantages of distributed design}
The distributed design of uHeapLmmm is concurrent to work in multi-threaded applications.

Some key benefits of the distributed design of uHeapLmmm are as follows:

\begin{itemize}
\item
The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The lock on bump allocation (on memory taken from sbrk) will only be contended if KTs > N. The contention on sbrk area is less likely as it will only happen in the case if heaps assigned to two KTs get short of bump allocation reserve simultanously.
\item
N heaps are created at the start of the program and destroyed at the end of program. When a KT is created, we only assign it to one of the heaps. When a KT is destroyed, we only dissociate it from the assigned heap but we do not destroy that heap. That heap will go back to our pool-of-heaps, ready to be used by some new KT. And if that heap was shared among multiple KTs (like the case of KTs > N) then, on deletion of one KT, that heap will be still in-use of the other KTs. This will prevent creation and deletion of heaps during run-time as heaps are re-usable which helps in keeping low-memory footprint.
\item
It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
\item
Distributed design avoids unnecassry locks on resources shared across all KTs.
\end{itemize}

FIX ME: Cite performance comparison of the two heap designs if required

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Added Features}


\subsection{Methods}
Why did we need it?
The added benefits.


\subsection{Alloc Interface}
Why did we need it?
The added benefits.