Skip to content

Memory Management from the Ground Up 2: Bitmap Allocator

September 4, 2010

This is the second post of my series about memory management. The previous post was a basic introduction, covering how the operating system views memory. In this, and the next, post, we’re going to dive straight into the C++ code, and implement two very simplistic allocators. These two allocators are not useful for any form of production code, but they will (hopefully) provide a basic foundation for future, more advanced allocators.

We will look at a very trivial fixed size allocator – a bitmap allocator – and, following that (in the next post), we will look at a more flexible system.

2.1 Bitmap Allocator

A bitmap allocator is a trivial memory allocator algorithm, which, at its core, uses a structure called a bitmap to provide the book-keeping information. Fundamentally, a bitmap allocator has two regions of memory (that may be part of the same contiguous block), a management region – the bitmap – and the arena, a catch-all term for “usable memory”. The two regions are related by a mapping (or magnification) factor – each discrete element in the bitmap (often a single bit, hence the term), maps to some number of bytes in the arena. The bitmap itself is a contiguous array of these elements, which is like a scaled down version of the arena, only instead of storing the user data, it simply stores whether each section of the arena is used or not.

Key features:
  • Book-keeping and user memory are separate, which protects against the internal memory manager state being corrupted;
  • Allocation and deletion only requires that entries in the bitmap be marked as being used or free;
  • Smallest allocation size is one page;
  • Arena cannot be resized (without a large amount of work);
  • Very few calls to the underlying operating system – once to set up the arena, once to set up the management area (these may be stored in contiguous memory if required);
  • Trivial implementation has expensive allocation, cheap freeing.
Structure

The bitmap allocator is extremely simple to implement. It needs to maintain a pointer to the bitmap, as well as a pointer to the arena. In the simplest design, it needs only two more fields – the number of blocks it owns, and the size of each block. For simplicity, we will be using a bitmap where each element is of size unsigned char. The bitmap must contain slightly more information than used and free, we will need an additional state for boundary, a state indicating that it is the start of an allocated block.

Initialization

Initialization is very simple; it requires calculating the number of blocks given a specified arena size and factor, allocating the two regions, and setting all the entries in the bitmap to free. Our memory system will sit on top of the CRT malloc function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
BitmapAllocator::BitmapAllocator(int factor, int arenasize)
{
	// Calculate the number of blocks for a given arena size and allocate
	// We will round down when determining the number of blocks
	m_Factor = factor;
	m_Blocks = (arenasize / m_Factor);

	assert(m_Blocks > 0);

	m_Arena = malloc(m_Blocks * m_Factor);
	m_Bitmap = (unsigned char*)malloc(m_Blocks);

	// Set all blocks to free
	for (int i = 0; i < m_Blocks; i++)
	{
		m_Bitmap[i] = FreeBlock;
	}
}

The code above is, for the sake of simplicity, missing any form of sanity checks for the arena/factor size, but some things to remember:

  • Smaller factor sizes mean additional book-keeping (unusable memory). E.g., a factor of 4 means for each 4 bytes of usable memory, a byte of memory must be dedicated to book-keeping.
  • Larger factor sizes mean more wasted memory.
  • It is sensible to require that the factor size is a power of two, or a multiple of a power of two. In order to ensure happy calling code, it is good to assume that any memory request over 16 bytes should be aligned to a 16 byte address; something that can be done by requiring that the factor is a multiple of 16.
Shutdown

Shutdown is a trivial matter of freeing the two memory blocks we have requested from the CRT.

Allocation

To allocate a block, we must:

  1. Calculate the number of blocks required (rounding up)
  2. Iterate over the bitmap, looking for a series of (at least the requested amount of) contiguous free blocks (in this case, using a linear probe like a naive string search)
  3. Translate the bitmap address into an arena address
  4. Mark the blocks we have allocated as used in the bitmap, marking the first block as a boundary block

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
void* BitmapAllocator::Allocate(unsigned int size)
{
	if (size == 0)
	{
		// See note
		return NULL;
	}

	// Calculate the number of blocks required (rounding up)
	unsigned int requiredblocks = size / m_Factor + ((size % m_Factor) > 0 ? 1 : 0);

	// Linear probe
	unsigned int location = 0;
	while (location <= m_Blocks - requiredblocks)
	{
		// Count the number of available blocks
		unsigned int available = 0;
		for (unsigned int i = 0; i < requiredblocks; i++)
		{
			if (m_Bitmap[i + location] != FreeBlock)
				break;
			available++;
		}

		if (available == requiredblocks)
		{
			void* pointer = (unsigned char*)m_Arena + m_Factor * location;

			// Mark the blocks as used
			m_Bitmap[location++] = BoundaryBlock;
			for (int i = 1; i < requiredblocks; i++)
				m_Bitmap[location++] = UsedBlock;
			return pointer;
		}
		else
			location = location + available + 1;
	}

	// Allocation failed, return NULL
	return NULL;
}

The see note part of the code above is because, strictly speaking, the standard requires that a zero byte allocation returns a unique memory address. In this case, we will flaunt the standard and simply return null.

Freeing

Freeing memory in a bitmap allocator is also very simple, we must:

  1. Check for a null pointer
  2. Convert a non-null pointer to a block entry
  3. Begin marking blocks as free, the first block should be a boundary block.
  4. Iterate forwards over the blocks in the bitmap until another boundary block is encountered, then stop.
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
void BitmapAllocator::Free(void* pointer)
{
	if (pointer == NULL)
		return;

	// Convert pointer to block index
	unsigned int arenaptr = (unsigned int)((unsigned char*)pointer - (unsigned char*)m_Arena);
	unsigned int block = arenaptr / m_Factor;

	// Check for validity
	assert(block < m_Blocks);

	// Ensure this is the start of the allocation
	assert(arenaptr % m_Factor == 0);
	assert(m_Bitmap[block] == BoundaryBlock);

	// Mark blocks as free
	m_Bitmap[block++] = FreeBlock;
	while (block < m_Blocks && m_Bitmap[block] == UsedBlock)
	{
		m_Bitmap[block++] = FreeBlock;
	}
}

2.2 Where to now?

The bitmap allocator is an incredibly simple allocator. It has very little state information, and is the simplest form of allocator to implement. It is very fast at releasing memory, and a more serious version of the algorithm can speed up the allocation code enormously (using, for example, a free list, or by storing information about contiguous free counts in the bitmap). Unfortunately, it requires a large block of book-keeping memory to function, which remains constant. In addition, by its very design, it is inherently wasteful for small allocations (given that the size of an allocation is always a multiple of the block factor).

Nevertheless, in about 100 lines of code, we have come up with a workable memory manager. It doesn’t support resizing of the arena, and it doesn’t provide a particularly usable or scalable system for an actual application, but, it is a good contrast to the next allocator we will look at; which has a very different design. Once we have covered these two designs, we will look at more advanced algorithms to improve them, working towards a fully featured memory system.

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: