coursebook/malloc/malloc.tex

\chapter{Memory Allocators}

\epigraph{Memory memory everywhere but not an allocation to be made}{A fragmented heap}

\section{Introduction}

Memory allocation is important!
Allocating and deallocating heap memory is one of the most common operations in any application.
The heap at the system level is a contiguous series of addresses that the program can expand or contract and use as it sees fit \cite{mallocinternals}.
In POSIX, this is called the system break.
We use \keyword{sbrk} to move the system break.
Most programs don't interact directly with this call, they use a memory allocation system around it to handle chunking up and keeping track of which memory is allocated and which is freed.

We will mainly be looking into simple allocators.
Just know that there are other ways of dividing up memory like with \keyword{mmap} or other allocation schemes and methods like \keyword{jemalloc}.

\section{C Memory Allocation API}

\begin{itemize}

\item \keyword{malloc(size\_t bytes)} is a C library call and is used to reserve a contiguous block of memory that may be uninitialized \cite[P. 348]{jones2010wg14}.
Unlike stack memory, the memory remains allocated until \keyword{free} is called with the same pointer.
\keyword{malloc} can either return a pointer to at least that much free space requested or \keyword{NULL}.
That means that malloc can return NULL even if there is some space.
Robust programs should check the return value.
If your code assumes \keyword{malloc} succeeds, and it does not, then your program will likely crash (segfault) when it tries to write to address 0.
Also, malloc leaves garbage in memory because of performance -- check your code to make sure that all program values are initialized.

\item \keyword{realloc(void *space, size\_t bytes)} allows a program to resize an existing memory allocation that was previously allocated on the heap (via malloc, calloc, or realloc) \cite[P. 349]{jones2010wg14}.
The most common use of realloc is to resize memory used to hold an array of values.
There are two gotchas with realloc.
One, a new pointer may be returned.
Two, it can fail.
A naive but readable version of realloc is suggested below with sample usage.

\begin{lstlisting}[language=C]
void * realloc(void * ptr, size_t newsize) {
  // Simple implementation always reserves more memory
  // and has no error checking
  void *result = malloc(newsize);
  size_t oldsize =  ... //(depends on allocator's internal data structure)
  if (ptr) memcpy(result, ptr, newsize < oldsize ? newsize : oldsize);
  free(ptr);
  return result;
}

int main() {
  // 1
  int *array = malloc(sizeof(int) * 2);
  array[0] = 10; array[1] = 20;
  // Oops need a bigger array - so use realloc..
  array = realloc(array, 3 * sizeof(int));
  array[2] = 30;

}
\end{lstlisting}

The above code is fragile.
If \keyword{realloc} fails then the program leaks memory.
Robust code checks for the return value and only reassigns the original pointer if not NULL.

\begin{lstlisting}[language=C]
int main() {
  // 1
  int *array = malloc(sizeof(int) * 2);
  array[0] = 10; array[1] = 20;
  void *tmp = realloc(array, 3 * sizeof(int));
  if (tmp == NULL) {
    // Nothing to do here.
  } else if (tmp == array) {
    // realloc returned same space
    array[2] = 30;
  } else {
    // realloc returned different space
    array = tmp;
    array[2] = 30;
  }

}
\end{lstlisting}

\item \keyword{calloc(size\_t nmemb, size\_t size)} initializes memory contents to zero and also takes two arguments: the number of items and the size in bytes of each item.
Programmers often use \keyword{calloc} rather than explicitly calling \keyword{memset} after \keyword{malloc}, to set the memory contents to zero because certain performance considerations are taken into account.
Doing that efficiently is harder than it looks: an implementation should skip zeroing memory that the operating system has already zeroed, and must catch the overflow when \keyword{nmemb} times \keyword{size} doesn't fit in a \keyword{size\_t}.
An advanced discussion of both problems is \href{https://locklessinc.com/articles/calloc/}{in this article}.
Note \keyword{calloc(x,y)} is identical to \keyword{calloc(y,x)}, but you should follow the conventions of the manual.
A naive implementation of calloc is below.

\begin{lstlisting}[language=C]
void *calloc(size_t n, size_t size) {
  size_t total = n * size; // Does not check for overflow!
  void *result = malloc(total);

  if (!result) return NULL;

  // If we're using new memory pages
  // allocated from the system by calling sbrk
  // then they will be zero so zero-ing out is unnecessary,
  // We will be non-robust and memset either way.
  return memset(result, 0, total);
}
\end{lstlisting}

\item \keyword{free} takes a pointer to the start of a piece of memory and makes it available for use in subsequent calls to the other allocation functions.
This is important because we don't want every process in our address space to take an enormous amount of memory.
Once we are done using memory, we stop using it with `free`.
A simple usage is below.

\begin{lstlisting}[language=C]
int *ptr = malloc(sizeof(*ptr));
do_something(ptr);
free(ptr);
\end{lstlisting}

If a program uses a piece of memory after it is freed - that is undefined behavior.

\end{itemize}

\subsection{Heaps and sbrk}

The heap is part of the process memory and varies in size.
Heap memory allocation is performed by the C library when a program calls \keyword{malloc} (\keyword{calloc}, \keyword{realloc}) and \keyword{free}.
By calling \keyword{sbrk} the C library can increase the size of the heap as your program demands more heap memory.
As the heap and stack need to grow, we put them at opposite ends of the address space.
Stacks don't grow like a heap, new parts of the stack are allocated for new threads.
For typical architectures, the heap will grow upwards and the stack grows downwards.

Nowadays, modern operating system memory allocators no longer need \keyword{sbrk}.
Instead, they can request independent regions of virtual memory and maintain multiple memory regions.
For example, gibibyte requests may be placed in a different memory region than small allocation requests.
However, this detail is an unwanted complexity.

Programs don't need to call \keyword{brk} or \keyword{sbrk} typically, though calling \keyword{sbrk(0)} can be interesting because it tells a program where your heap currently ends.
Instead programs use \keyword{malloc}, \keyword{calloc}, \keyword{realloc} and \keyword{free} which are part of the C library.
The internal implementation of these functions may call \keyword{sbrk} when additional heap memory is required.

\begin{lstlisting}[language=C]
void *top_of_heap = sbrk(0);
malloc(16384);
void *top_of_heap2 = sbrk(0);
printf("The top of heap went from %p to %p \n", top_of_heap, top_of_heap2);
// Example output: The top of heap went from 0x4000 to 0xa000
\end{lstlisting}

Note that the memory that was newly obtained by the operating system must be zeroed out.
If the operating system left the contents of physical RAM as-is, it might be possible for one process to learn about the memory of another process that had previously used the memory.
This would be a security leak.
Unfortunately, this means that memory for \keyword{malloc} requests before any memory has been freed is \emph{often} zero.
This is unfortunate because many programmers mistakenly write C programs that assume allocated memory will \emph{always} be zero.

\begin{lstlisting}[language=C]
char* ptr = malloc(300);
// contents is probably zero because we get brand new memory
// so beginner programs appear to work!
// strcpy(ptr, "Some data"); // work with the data
free(ptr);
// later
char *ptr2 = malloc(300); // Contents might now contain existing data and is probably not zero
\end{lstlisting}

\section{Intro to Allocating}

Let's try to write Malloc.
Here is our first attempt at it -- the naive version.

\begin{lstlisting}[language=C]
void* malloc(size_t size)
{
    // Ask the system for more bytes by extending the heap space.
    // sbrk returns -1 on failure
    void *p = sbrk(size);
    if(p == (void *) -1) return NULL; // No space left
    return p;
}
  void free() {/* Do nothing */}
\end{lstlisting}

Above is the simplest implementation of malloc, there are a few drawbacks though.

\begin{itemize}
\item System calls are slow compared to library calls.
  We should reserve a large amount of memory and only occasionally ask for more from the system.
\item No reuse of freed memory.
  Our program never re-uses heap memory - it keeps asking for a bigger heap.
\end{itemize}

If this allocator was used in a typical program, the process would quickly exhaust all available memory.
Instead, we need an allocator that can efficiently use heap space and only ask for more memory when necessary.
Some programs use this type of allocator.
Consider a video game allocating objects to load the next scene.
It is considerably faster to do the above and throw the entire block of memory away than it is to do the following placement strategies.

\subsection{Placement Strategies}

During program execution, memory is allocated and deallocated, so there will be a gap in the heap memory that can be re-used for future memory requests.
The memory allocator needs to keep track of which parts of the heap are currently allocated and which parts are available.
Suppose our current heap size is 64K.
Let's say that our heap looks like the following table.

\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth,alt={A heap of seven blocks in address order: 16KiB free, 10KiB allocated, 1KiB free, 1KiB allocated, 30KiB free, 4KiB allocated, and 2KiB free.}]{malloc/drawings/heap_empty.eps}
\caption{Empty heap blocks}
\end{figure}

From the lowest address, the blocks are 16KiB free, 10KiB allocated, 1KiB free, 1KiB allocated, 30KiB free, 4KiB allocated, and 2KiB free.

If a new malloc request for 2KiB is executed (\keyword{malloc(2048)}), where should \keyword{malloc} reserve the memory?
It could use the last 2KiB hole, which happens to be the perfect size!
Or it could split one of the other two free holes.
These choices represent different placement strategies.
Whichever hole is chosen, the allocator will need to split the hole into two.
The first is the newly allocated space, which will be returned to the program, and the second is a smaller hole if there is spare space left over.
A best fit strategy finds the smallest hole that is of sufficient size (at least 2KiB):

\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth,alt={Best fit walks the whole list of blocks and picks the 2KiB free block at the end, an exact match for the 2KiB request.}]{malloc/drawings/heap_best_fit.eps}
\caption{Best fit finds an exact match}
\end{figure}

A worst-fit strategy finds the largest hole that is of sufficient size so break the 30KiB hole into two:

\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth,alt={Worst fit picks the largest hole, the 30KiB free block, and splits it into a 2KiB block for the request and a 28KiB free remainder.}]{malloc/drawings/heap_worst_fit.eps}
\caption{Worst fit finds the worst match}
\end{figure}

The request takes 2KiB of that hole and leaves a 28KiB hole behind it.


A first-fit strategy finds the first available hole that is of sufficient size so break the 16KiB hole into two.
We don't even have to look through the entire heap!

\begin{figure}[H]
\centering
\includegraphics[width=.5\textwidth,alt={First fit stops at the first hole that is large enough, the 16KiB free block, and splits it into a 2KiB block for the request and a 14KiB free remainder.}]{malloc/drawings/heap_first_fit.eps}
\caption{First fit finds the first match}
\end{figure}

One thing to keep in mind is that those placement strategies don't need to split the block.
For example, our first fit allocator could've returned the original block unbroken.
Notice that this would lead to about 14KiB of space being unused by the user and the allocator.
We call this internal fragmentation.

In contrast, external fragmentation is that even though we have enough memory in the heap, it may be divided up in a way so a contiguous block of that size is unavailable.
In our previous example, of the 64KiB of heap memory, 17KiB is allocated, and 47KiB is free.
However, the largest available block is only 30KiB because our available unallocated heap memory is fragmented into smaller pieces.

\subsection{Placement Strategy Pros and Cons}

The challenges of writing a heap allocator are
\begin{itemize}
\item Need to minimize fragmentation (i.e.~maximize memory utilization)
\item Need high performance
\item Fiddly implementation -- lots of pointer manipulation using linked lists and pointer arithmetic.
\item Both fragmentation and performance depend on the application allocation profile, which can be evaluated but not predicted and in practice, under specific usage conditions, a special-purpose allocator can often out-perform a general-purpose implementation.
\item The allocator doesn't know the program's memory allocation requests in advance. Even if we did, this is the \href{http://en.wikipedia.org/wiki/Knapsack_problem}{Knapsack problem} which is known to be NP-hard!
\end{itemize}

Different strategies affect the fragmentation of heap memory in non-obvious ways, which only are discovered by mathematical analysis or careful simulations under real-world conditions (for example simulating the memory allocation requests of a database or webserver).

First, we will have a more mathematical, one-shot approach to each of these algorithms \cite{Garey:1972:WAM:800152.804907}.
The paper describes a scenario where you have a certain number of bins and a certain number of allocations, and you are trying to fit the allocations in as few bins as possible, hence using as little memory as possible.
The paper discusses theoretical implications and puts a nice limit on the ratios in the long run between the ideal memory usage and the actual memory usage.
For those who are interested, the paper concludes that actual memory usage over ideal memory usage as the number of bins increases -- the bins can have any distribution -- is about 1.7 for First-Fit and lower bounded by 1.7 for best fit.
The problem with this analysis is that few real-world applications need this type of one-shot allocation.
Video game object allocations will typically designate a different subheap for each level and fill up that subheap if they need a quick memory allocation scheme that they can throw away.

In practice, we'll be using the result from a more rigorous survey conducted in 1995 \cite{10.1007/3-540-60368-9_19}.
The survey makes sure to note that memory allocation is a moving target.
A good allocation scheme to one program may not be a good allocation scheme for another program.
Programs don't uniformly follow the distribution of allocations.
The survey talks about all the allocation schemes that we have introduced as well as a few extra ones.
Here are some summarized takeaways

\begin{enumerate}
\item Best fit may have problems when a block is chosen that is almost the right size, and the remaining space is split so small that a program probably won't use it.
  A way to get around this could be to set a threshold for splitting.
  This small splitting isn't observed as frequently under a regular workload.
  Also, the worst-case behavior of Best-Fit is bad, but it doesn't usually happen [p. 43].
\item The survey also talks about an important distinction of First-Fit.
  There are multiple notions of first.
  First could be ordered in terms of the time of `free`'ing, or it could be ordered through the addresses of the start of the block, or it could be ordered by the time of last free -- first being least recently used.
  The survey didn't go too in-depth into the performance of each but did make a note that address-ordered and Least Recently Used (LRU) lists ended up with better performance than the most recently used first.
\item The survey concludes by first saying that under simulated random (assuming uniform at random) workloads, best fit and first fit do as well. Even in practice, both best and address ordered first fit do about as equally as well with a splitting threshold and coalescing. The reasons why aren't entirely known.
\end{enumerate}

Some additional notes we make

\begin{enumerate}
\item Best fit may take less time than a full heap scan. When a block of perfect size or perfect size within a threshold is found, that can be returned, depending on what edge-case policy you have.
\item Worst fit follows this as well. Your heap could be represented with the max-heap data structure and each allocation call could simply pop the top off, re-heapify, and possibly insert a split memory block.
  Fancier heaps don't buy much here: a Fibonacci heap has better amortized bounds on paper, but each node carries parent, child, two sibling pointers, degree and mark fields.
  In an allocator every free block would have to hold all of that overhead, which raises the minimum block size, and in practice its pointer chasing makes it slower than a simple binary heap anyway.
\item First-Fit needs to have a block order. Most of the time programmers will default to linked lists which is a fine choice. There aren't too many improvements you can make with a least recently used and most recently used linked list policy, but with address ordered linked lists you can speed up insertion from O(n) to O(log(n)) by using a randomized skip-list in conjunction with your singly-linked list.
  An insert would use the skip list as shortcuts to find the right place to insert the block and removal would go through the list as normal.
\item There are many placement strategies that we haven't talked about, one is next-fit, which is like first fit except that each search resumes where the previous search stopped instead of starting at the beginning of the heap. This adds deterministic randomness -- pardon the oxymoron. You won't be expected to know this algorithm, but know that as you are implementing a memory allocator as part of a machine problem, there are more than these.
  \end{enumerate}

\section{Memory Allocator Tutorial}

A memory allocator needs to keep track of which bytes are currently allocated and which are available for use.
This section introduces the implementation and conceptual details of building an allocator, or the actual code that implements \keyword{malloc} and \keyword{free}.

Conceptually, we are thinking about creating linked lists and lists of blocks!
Please enjoy the following ASCII art.
bt is short for boundary tag.


\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth,alt={Three adjacent blocks, each laid out as metadata, then space, then a boundary tag: a free block, a used block about to be freed, and another free block.}]{malloc/drawings/malloc_patching.eps}
\caption{3 Adjacent Memory blocks}
\end{figure}

We will have implicit pointers in our next block, meaning that we can get from one block to another using addition.
This is in contrast to an explicit \keyword{metadata *next} field in our meta block.

\begin{figure}[H]
\centering
\includegraphics[width=.5\textwidth,alt={Pointer arithmetic on one block: p points at the metadata, p plus sizeof(meta) at the usable space, adding the block size reaches the boundary tag, and adding the tag size reaches the start of the next block.}]{malloc/drawings/malloc_addition.eps}
\caption{Malloc addition}
\end{figure}

One can grab the next block by finding the end of the current one.
That is what we mean by ``implicit list''.

The actual spacing may be different.
The metadata can contain different things.
A minimal metadata implementation would simply have the size of the block.

Since we write integers and pointers into memory that we already control, we can later consistently hop from one address to the next.
This internal information represents some overhead.
Meaning even if we had requested 1024 KiB of contiguous memory from the system, an allocation of that size will fail.

Our heap memory is a list of blocks where each block is either allocated or unallocated.
Thus there is conceptually a list of free blocks, but it is implicit in the form of block size information that we store as part of each block.
Let's think of it in terms of a simple implementation.
\begin{lstlisting}[language=C]
typedef struct {
  size_t block_size;
  char data[0];
} block;
// Stored at the end of each block (bt in the figures above)
typedef struct {
  size_t block_size;
} boundary_tag;
block *p = sbrk(100);
p->block_size = 100 - sizeof(*p) - sizeof(boundary_tag);
// Other block allocations
\end{lstlisting}

We could navigate from one block to the next block by adding the block's size.

\begin{lstlisting}[language=C]
p + sizeof(metadata) + p->block_size + sizeof(boundary_tag)
\end{lstlisting}

Make sure to get your casting right!
Otherwise, the program will move an extreme amount of bytes over.

The calling program never sees these values.
They are internal to the implementation of the memory allocator.
As an example, suppose your allocator is asked to reserve 80 bytes (\keyword{malloc(80)}) and requires 8 bytes of internal header data.
The allocator would need to find an unallocated space of at least 88 bytes.
After updating the heap data it would return a pointer to the block.
However, the returned pointer points to the usable space, not the internal data!
Instead, we would return the start of the block + 8 bytes.
In the implementation, remember that pointer arithmetic depends on type. For example, \keyword{p\ +=\ 8} adds \keyword{8\ *\ sizeof(p)}, not necessarily 8 bytes!

\subsection{Implementing a Memory Allocator}

The simplest implementation uses First-Fit.
Start at the first block, assuming it exists, and iterate until a block that represents an unallocated space of sufficient size is found, or we've checked all the blocks.
If no suitable block is found, it's time to call \keyword{sbrk()} again to sufficiently extend the size of the heap.
For this class, we will try to serve every memory request until the operating system tells us we are going to run out of heap space.
Other applications may limit themselves to a certain heap size and cause requests to intermittently fail.
Besides, a fast implementation might extend it a significant amount so that we will not need to request more heap memory soon.

When a free block is found, it may be larger than the space we need.
If so, we will create two entries in our implicit list.
The first entry is the allocated block, the second entry is the remaining space.
There are ways to do this if the program wants to keep the overhead small.
We recommend first going with readability.

\begin{lstlisting}[language=C]
typedef struct {
  size_t block_size;
  int is_free;
  char data[0];
} block;
block *p = sbrk(100);
p->block_size = 100 - sizeof(*p) - sizeof(boundary_tag);
// Other block allocations
\end{lstlisting}

If the program wants certain bits to hold different pieces of information, use bit fields!

\begin{lstlisting}[language=C]
typedef struct {
  unsigned int block_size : 7;
  unsigned int is_free : 1;
} size_free;

typedef struct {
  size_free info;
  char data[0];
} block;
\end{lstlisting}

The compiler will handle the shifting.
After setting up your fields then it becomes simply looping through each of the blocks and checking the appropriate fields.

Here is a visual representation of what happens.
If we assume that we have a block that looks like this, we want to split if the allocation is let's say 16 bytes.
The split we'll have to do is the following.

\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth,alt={A 52-byte block, with 8 bytes of metadata, 40 bytes of space and a 4-byte boundary tag, split for a 16-byte request into a block with 16 bytes of space ending at 0x1C and a new block with 12 bytes of space ending at 0x34.}]{malloc/drawings/malloc_split.eps}
\caption{Malloc split}
\end{figure}

The original block is 52 (0x34) bytes: 8 bytes of metadata, 40 bytes of space, and a 4-byte boundary tag.
After the split, the first block keeps 16 bytes of space and ends at 0x1C, and the remaining 24 bytes become a new block with 8 bytes of metadata, 12 bytes of space, and its own 4-byte tag.

This is before alignment concerns as well.

\subsection{Alignment and rounding up considerations}

Many architectures expect multibyte primitives to be aligned to some multiple of 2 (4, 16, etc).
For example, it's common to require 4-byte types to be aligned to 4-byte boundaries and 8-byte types on 8-byte boundaries.
If multi-byte primitives are stored on an unreasonable boundary, the performance can be significantly impacted because it may require an additional memory read.
On some architectures the penalty is even greater - the program will crash with a \href{http://en.wikipedia.org/wiki/Bus_error\#Unaligned_access}{bus error}.
Most of you have experienced this in your architecture classes if there was no memory protection.

As \keyword{malloc} does not know how the user will use the allocated memory, the pointer returned to the program needs to be aligned for the worst case, which is architecture-dependent.

The glibc manual states the alignment guarantee \cite{vma_paging}:

\begin{quote}
The block that \keyword{malloc} gives you is guaranteed to be aligned so that it can hold any type of data. In the GNU system, the address is always a multiple of eight on most systems, and a multiple of 16 on 64-bit systems.
\end{quote}

So if your allocator hands out memory in 16-byte units, remember to round up when you work out how many units a request needs.

This is what the math would look like in C.

\begin{lstlisting}[language=C]
int s = (requested_bytes + tag_overhead_bytes + 15) / 16
\end{lstlisting}

The additional constant ensures incomplete units are rounded up. Note, real code is more likely to use symbol sizes e.g. \keyword{sizeof(x)\ -\ 1}, rather than coding numerical constant 15.
\href{https://web.archive.org/web/20190313121701/https://www.ibm.com/developerworks/library/pa-dalign/}{Here's a great article on memory alignment, if you are further interested}.

Another added effect is internal fragmentation, which happens when the given block is larger than the allocation size.
Let's say that we have a free block of size 16B (not including metadata).
If they allocate 7 bytes, the allocator may want to round up to 16B and return the entire block.
This gets sinister when implementing coalescing and splitting.
If the allocator doesn't implement either, it may end up returning a block of size 64B for a 7B allocation!
There is a \emph{lot} of overhead for that allocation which is what we are trying to avoid.

\subsection{Implementing free}

When \keyword{free} is called we need to re-apply the offset to get back to the `real' start of the block -- to where we stored the size information.
A naive implementation would simply mark the block as unused.
If we are storing the block allocation status in a bitfield, then we need to set the \keyword{is\_free} bit:

\begin{lstlisting}[language=C]
p->info.is_free = 1;
\end{lstlisting}

However, we have a bit more work to do.
If the current block and the next block (if it exists) are both free we need to coalesce these blocks into a single block.
Similarly, we also need to check the previous block, too.
If that exists and represents unallocated memory, then we need to coalesce the blocks into a single large block.

To be able to coalesce a free block with a previous free block we will also need to find the previous block, so we store the block's size at the end of the block, too.
These are called ``boundary tags'' \cite{knuth1973art}.
These are Knuth's solution to the coalescing problem both ways.
As the blocks are contiguous, the end of one block sits right next to the start of the next block.
So the current block (apart from the first one) can look a few bytes further back to look up the size of the previous block.
With this information, the allocator can now jump backward!

Take for example a double coalesce.
If we wanted to free the middle block we need to turn the surrounding blocks into one big block.

\begin{figure}[H]
\centering
\includegraphics[width=.9\textwidth,alt={Freeing a used block that sits between two free blocks. The two free spaces, the freed block, and all the metadata and boundary tags between them merge into one large free block with a single metadata header and a single tag.}]{malloc/drawings/malloc_double_coalesce.eps}
\caption{Free double coalesce}
\end{figure}

\subsection{Performance}

With the above description, it's possible to build a memory allocator.
Its main advantage is simplicity - at least simple compared to other allocators!
Allocating memory is a worst-case linear time operation -- search linked lists for a sufficiently large free block.
De-allocation is constant time.
No more than 3 blocks will need to coalesce into a single block, and using a most recently used block scheme, only one linked list entry needs to be updated.

Using this allocator it is possible to experiment with different placement strategies.
For example, the allocator could start searching from the last deallocated block.
If the allocator stores pointers to blocks, it needs to update the pointers so that they always remain valid.

\subsection{Explicit Free Lists Allocators}

Better performance can be achieved by implementing an explicit doubly-linked list of free nodes.
In that case, we can immediately traverse to the next free block and the previous free block.
This can reduce the search time because the linked list only includes unallocated blocks.
A second advantage is that we now have some control over the ordering of the linked list.
For example, when a block is deallocated, we could choose to insert it into the beginning of the linked list rather than always between its neighbors.
We may update our struct to look like this.

\begin{lstlisting}[language=C]
typedef struct {
  size_t info;
  struct block *next;
  char data[0];
} block;
\end{lstlisting}

Here is what that would look like along with our implicit linked list.

\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth,alt={An explicit free list: dotted pointers link only the free blocks, running from the first free block to the next free block and skipping the used block between them, while the blocks stay next to each other in memory.}]{malloc/drawings/free_list.eps}
\caption{Free list}
\end{figure}


Where do we store the pointers of our linked list?
A simple trick is to realize that the block itself is not being used and store the next and previous pointers as part of the block, though you have to ensure that the free blocks are always sufficiently large to hold two pointers.
We still need to implement Boundary Tags, so we can correctly free blocks and coalesce them with their two neighbors.
Consequently, explicit free lists require more code and complexity.
With explicitly linked lists a fast and simple `Find-First' algorithm is used to find the first sufficiently large link.
However, since the link order can be modified, this corresponds to different placement strategies.
If the links are maintained from largest to smallest, then this produces a `Worst-Fit' placement strategy.

There are edge cases though, consider how to maintain your free list if also double coalescing.
We've included a figure with a common mistake.

\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth,alt={Freeing and coalescing a used block between two free blocks, shown with the free-list pointers. The version marked wrong leaves a pointer aimed at the old header of the absorbed block, now inside the merged block; the version marked correct links the merged block straight to the next free block.}]{malloc/drawings/free_list_ptrs.eps}
\caption{Free list good and bad coalesce}
\end{figure}

In the incorrect version, the merged block still points to where the right-hand block used to start, which is now in the middle of the merged block.
In the correct version, the merged block takes over the right-hand block's link, so the list goes from the merged block straight to the next free block.

We recommend when trying to implement malloc that you draw out all the cases conceptually and then write the code.

\subsubsection{Explicit linked list insertion policy}

The newly deallocated block can be inserted easily into two possible positions: at the beginning or in address order.
Inserting at the beginning creates a LIFO (last-in, first-out) policy.
The most recently deallocated spaces will be reused. Studies suggest fragmentation is worse than using address order \cite{10.1007/3-540-60368-9_19}.

Inserting in address order (``Address ordered policy'') inserts deallocated blocks so that the blocks are visited in increasing address order.
This policy requires more time to free a block because the boundary tags (size data) must be used to find the next and previous unallocated blocks.
However, there is less fragmentation.

\section{Case Study: Buddy Allocator, an example of a segregated list}

A segregated allocator is one that divides the heap into different areas that are handled by different sub-allocators dependent on the size of the allocation request.
Sizes are grouped into powers of two and each size is handled by a different sub-allocator and each size maintains its free list.

A well-known allocator of this type is the buddy allocator \cite[P. 85]{rangan1999foundations}.
We'll discuss the binary buddy allocator which splits allocation into blocks of size $2^n; n = 1, 2, 3, ...$ times some base unit number of bytes, but others also exist like Fibonacci split where the allocation is rounded up to the next Fibonacci number.
The basic concept is simple: If there are no free blocks of size $2^n$, go to the next level and steal that block and split it into two.
If two neighboring blocks of the same size become unallocated, they can coalesce together into a single large block of twice the size.

Buddy allocators are fast because the neighboring blocks to coalesce with can be calculated from the deallocated block's address, rather than traversing the size tags.
Ultimate performance often requires a small amount of assembler code to use a specialized CPU instruction to find the lowest non-zero bit.

The main disadvantage of the Buddy allocator is that it suffers from \emph{internal fragmentation} because allocations are rounded up to the nearest block size.
For example, a 68-byte allocation will require a 128-byte block.

\section{Case Study: SLUB Allocator, Slab allocation}

The SLUB allocator is a slab allocator that serves different needs for the Linux kernel \href{http://en.wikipedia.org/wiki/SLUB_\%28software\%29}{SLUB}.
Imagine you are creating an allocator for the kernel, what are your requirements?
Here is a hypothetical shortlist.

\begin{enumerate}
\item First and foremost is that you want a low memory footprint to have the kernel be able to be installed on all types of hardware: embedded, desktop, supercomputer, etc.
\item Then, you want the actual memory to be as contiguous as possible to make use of caching. Every time a system call is performed, the kernel's pages need to get loaded into memory. This means that if they are all contiguous, the processor will be able to cache them more efficiently.
\item Lastly, you want your allocations to be fast.
\end{enumerate}

Enter the SLUB allocator \keyword{kmalloc}.
The SLUB allocator is a segregated list allocator with minimal splitting and coalescing.
The difference here is that the segregated list focuses on more realistic allocation sizes, instead of powers of two.
SLUB also focuses on a low overall memory footprint while keeping pages in the cache.
There are blocks of different sizes and the kernel rounds up each allocation request to the lowest block size that satisfies it.
One of the big differences between this allocator and the others is that it usually conforms to page sizes.
We'll talk about virtual memory and pages in another chapter, but the kernel will be working with direct memory pages in spans of 4KiB or 4096 Bytes.

\section{Further Reading}

Guiding questions

\begin{itemize}
\item Is malloc'ed memory initialized? How about calloc'ed or realloc'ed memory?
\item Does realloc accept, as its argument, the number of elements or space (in bytes)?
\item Why may the allocation functions error?
\end{itemize}

See \href{http://man7.org/linux/man-pages/man3/malloc.3.html}{the man page} or the appendix of the book \ref{man_malloc}!

\begin{itemize}
\item \href{https://en.wikipedia.org/wiki/Slab_allocation}{Slab Allocation}
\item
  \href{http://en.wikipedia.org/wiki/Buddy_memory_allocation}{Buddy Memory Allocation}
\end{itemize}

\section{Topics}

\begin{itemize}
\item
  Best Fit
\item
  Worst Fit
\item
  First Fit
\item
  Buddy Allocator
\item
  Internal Fragmentation
\item
  External Fragmentation
\item
  sbrk
\item
  Natural Alignment
\item
  Boundary Tag
\item
  Coalescing
\item
  Splitting
\item
  Slab Allocation/Memory Pool
\end{itemize}

\section{Questions/Exercises}

\begin{itemize}
\tightlist
\item
  What is Internal Fragmentation? When does it become an issue?
\item
  What is External Fragmentation? When does it become an issue?
\item
  What is a Best Fit placement strategy? How is it with External Fragmentation? Time Complexity?
\item
  What is a Worst Fit placement strategy? Is it any better with External Fragmentation? Time Complexity?
\item
  What is the First Fit Placement strategy? It's a little bit better with Fragmentation, right? Expected Time Complexity?
\item
  Let's say that we are using a buddy allocator with a new slab of 64KiB. How does it go about allocating 1.5KiB?
\item
  When does the 5 line \keyword{sbrk} implementation of malloc have a use?
\item
  What is natural alignment?
\item
  What is Coalescing/Splitting? How do they increase/decrease fragmentation? When can you coalesce or split?
\item
  How do boundary tags work? How can they be used to coalesce or split?
\end{itemize}

\bibliographystyle{plainnat}
\bibliography{malloc/malloc}