malloc/Report.tex at master · miscer/malloc · GitHub

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
\documentclass{article}
\usepackage{listings}
\usepackage{csquotes}
\usepackage[margin=0.8in]{geometry}

\title{CS3104 Practical 1 Report}
\author{140015533}
\date{11 Oct 2016}

\lstset{basicstyle=\ttfamily}

\begin{document}

\maketitle

\section{Introduction}

In this practical our task was to implement the two basic C memory allocation functions - \lstinline{malloc} and \lstinline{free}.

These functions are used to allocate memory on the heap. This is useful if we cannot allocate the memory for these objects at compile time.

\section{Design}

The library's strategy is to incrementally allocate one or more regions of virtual memory. These regions form a linked list: each region has a header that stores the address of the next region's header. The address of the first region is stored in a global variable.

The regions are then split into free and used blocks as required. When a region is first allocated, it contains one large free block. This block is then split into smaller blocks when memory is allocated. After blocks are freed, they are coalesced with their free neighbours, if there are any.

\subsection{Block header and footer}

To be able to facilitate this, all blocks have a header structure associated to them. It contains the size of the block (including the header - this is to simplify the calculations when iterating the list of blocks) and three boolean values: is this block used, is the previous block used and is this the last block in the region. Free blocks also have a footer structure, located at the end of the block, containing just the size of the block.

The block size value in the header is used when iterating the blocks in a region. If we know the location of one block header, we can calculate the location of the next block by adding the block size to the address of the block.
The ``last block in the region'' value is also used, to be able to recognise the end of the list.

Knowing whether the block is used is needed when looking for a free block, but also for coalescing.

\subsection{Coalescing}

During coalescing, a combination of various block header and footer values is used. When a block is freed, it is possible that there is another free block after or before it, but also that there is no block at all before or after it.

To find out if there is a block before it and if it is free, the ``is previous block used'' value is used. It is set to true if the previous block is used, or if there is no block (this is the first block in the region.) If the previous block is free, its footer is used to determine the location of the header by subtracting the block size from the address of the freed block.

Whether there is any next block can be found out using the ``is last block in the region'' value. Whether it is free is determined by looking at the value of ``is block used'' in the header of the next block.

\subsection{Searching and splitting}

When looking for a suitable free block, the regions and blocks are linearly searched. The best-fit algorithm is used, meaning that all blocks in the memory have to be searched.

As \cite{Wilson95dynamicstorage} mentions, \textquote{The classic linear-list implementations may not scale well to large heaps, in terms of time costs; as the number of free blocks grows, the time to search the list may become unacceptable.} This is even worse when the best-fit search is used, as potentially all blocks need to be searched, which will get very slow for a large number of blocks. However, I have used it instead of first-fit because it \textquote{generally exhibits quite good memory usage} \cite{Wilson95dynamicstorage}.

For every used region the best-fitting block is found by iterating the blocks in the region and selecting the smallest block that is still large enough to fit the requested memory. The same criteria are then used to select the region with the best-fitting block.

When the block is found and it is bigger then needed, it is split into a used and a free block.

If no suitable block is found, a new region is created. This region will have a minimum size to avoid creating many small regions. If the requested memory size is bigger than the minimum size, a region with the suitable size is created. This is essentially a region that will be used solely for this one block - after the block is freed, the region will contain no used blocks and will be released back to the operating system.

\subsection{Releasing virtual memory}

The region header stores the number of used blocks inside of it. This number is updated after allocate or free action. If after a free action a region contains no used blocks, the memory is released back to the operating system. For this reason the size of the region is also stored in the header.

When freeing a block, the parent region is found by going through all regions and checking whether the block is located in each one. I chose this over iterating backwards through the blocks until the first one in the region is found, as it is more likely that there will be more blocks than regions to go through.

\section{Implementation}

The whole library is located in one file, as required by the practical specification.

This file contains the two required functions - \lstinline{myalloc} and \lstinline{myfree}.

The library uses one global variable for storing the address of the first used region. From this address we can then find all other regions and their blocks.

New regions of the memory are allocated using the \lstinline{mmap} function. The size of the region is always rounded up to the system page size, retrieved with the \lstinline{getpagesize} function.

Functions dealing with block headers and footers hide the exact details for the structure. This way I was able to do one optimisation with minimal modifications to other functions.

\subsection{Optimisations}

I have optimised the block header structure to be only the size of the \lstinline{size_t} type. This way the headers take less memory - for example, on a 64-bit system the difference is from 16 to 8 bytes for the header.

Before the optimisation, the header structure contained one field with type \lstinline{size_t} and three \lstinline{bool} fields. After it there is only one \lstinline{size_t} field.

The last three bits of the block size are used to store the three boolean fields. The size then has to be rounded up to the nearest multiple of 8 bytes. This means that a part of the 8 bytes we save on reducing the size of the header we might ``waste'' on the extra size. However, the extra size will be always less than 8 bytes, saving us at least one byte.

The last three bits in the size are then set and read using bit operators.

\section{Testing}

I have used the provided test programs during development, as well as my programs designed to test a specific functionality.

To check if the library correctly allocated and freed large blocks, I allocated a block with size that is bigger than the minimum region size. Then I wrote to the memory at the start and the end, to check that there is no segfault - this makes sure that the block is properly allocated. After that I freed the large block and tried to write to the memory again, expecting a segfault. If a segfault occurred, it meant that the virtual memory was properly released back to the operating system.

After doing the block header optimisation I wanted to make sure that it works correctly and that using the last three bits of the block size for boolean values won't break the library. Knowing that the block size will be rounded up to a multiple of the size of \lstinline{size_t}, I allocated multiple blocks with the size of \lstinline{size_t} next to each other. I wrote a specific number in each one, to make sure that the whole block content is used. Then I went through the allocated blocks and checked that their value is correct.

To check splitting coalescing, I have allocated one large block and then freed it. Then I allocated two smaller blocks and checked they use the same memory as the previous large block - this means that the large block was split. Afterwards I freed the two smaller blocks and allocated a large block again, making sure that it has the same address as the first large block - if it has, the two smaller blocks were coalesced into one bigger block.

\section{Conclusion}

I have implemented a basic memory allocator library that supports incremental virtual memory allocation, splitting and coalescing of memory blocks and uses some optimisations to reduce its memory footprint. It uses a free list to keep track of the block and the best-fit algorithm for finding a suitable free block of memory.

This practical was an interesting exercise on memory management. It helped me understand how memory allocators work and what problems there are when implementing them. I learned why writing outside of allocated memory can cause not just segfaults, but corruption of the data structures used by the allocator. The practical has also broadened my experience with pointer arithmetic and memory addressing in C.

\bibliographystyle{plain}
\bibliography{Report}

\end{document}