BlockAllocator.cc

////////////////////////////////////////////////////////////////////////////////
// -------------------------------------------------------------------------- //
//                                                                            //
//                      Copyright (C) 2013 David Krutsko                      //
//                                                                            //
// -------------------------------------------------------------------------- //
////////////////////////////////////////////////////////////////////////////////

//----------------------------------------------------------------------------//
// Prefaces                                                                   //
//----------------------------------------------------------------------------//

#include <mutex>
#include <cassert>
#include <cstdlib>
#include <cstdint>
#include <iostream>



//----------------------------------------------------------------------------//
// Classes                                                                    //
//----------------------------------------------------------------------------//

////////////////////////////////////////////////////////////////////////////////
/// <summary> Represents a block allocator which manages a single heap allocation
/// and allows fixed-sized blocks to be allocated. Allocated blocks are aligned
/// to the specified block alignment. Allocating and freeing memory is completely
/// thread safe and buffer overflow checks are performed automatically. </summary>

class BlockAllocator
{
public:
	// Constructors
	 BlockAllocator				(size_t blockSize,
								 size_t maxBlocks,
								 size_t blockAlignment);

	~BlockAllocator				(void);

public:
	// Functions
	template <typename Type>
	Type* Allocate (void);

	template <typename Type>
	void Free (Type* blockLocation);

private:
	// Fields
	size_t		mBlockSize;		// Size of memory block data

	uint8_t*	mAllocation;	// Heap allocation pointer
	uint8_t*	mFree;			// First free memory block

	std::mutex	mMutex;			// Allows for thread safety

	// Internal structure of memory blocks
	// +-------------+       +-------------+
	// | Padding   x |       | Padding   x |
	// | Check 1   2 |       | Check 1   2 |
	// +-------------+   +-->+-------------+
	// |             |   |   |             |
	// | Data      x |   |   | Data      x |
	// |             |   |   |             |
	// +-------------+   |   +-------------+
	// | Check 2   2 |   |   | Check 2   2 |
	// +-------------+   |   +-------------+
	// | NextFree  * |---+   | NextFree  * |
	// +-------------+       +-------------+
	//       |                   |          
	// +---+---+---+---+---+---+---+---+---+
	// |   | F |   |   |   |   | F |   |   |
	// +---+---+---+---+---+---+---+---+---+
};



//----------------------------------------------------------------------------//
// Constructors                                                BlockAllocator //
//----------------------------------------------------------------------------//

////////////////////////////////////////////////////////////////////////////////
/// <summary> Prepares this class using a single allocation. </summary>
/// <param name="blockSize"> Size of a single memory block. </param>
/// <param name="maxBlocks"> Maximum number of memory blocks. </param>
/// <param name="blockAlignment"> Memory block alignment. </param>
/// <runtime> Blocks are prepared linearly; O(MaxBlocks). </runtime>

BlockAllocator::BlockAllocator (size_t blockSize,
		size_t maxBlocks, size_t blockAlignment)
{
	mBlockSize = blockSize;

	// Compute size of single memory block
	const size_t size = blockAlignment +
		blockSize + 4 + sizeof (uint8_t*);

	// Precompute block alignment value
	const size_t align = blockAlignment - 1;

	mFree = nullptr;
	// Allocate enough memory to store all blocks
	mAllocation = new uint8_t[maxBlocks * size];
	
	// Loop through every block of memory
	for (size_t i = 0; i < maxBlocks; ++i)
	{
		// Determine location of current block
		uint8_t* block = &mAllocation[i * size] + 2;

		if (blockAlignment > 0)
		{
			// Align the memory block region
			block = (uint8_t*) ((uintptr_t)
				(block + align) & ~align);

			// Make sure memory was properly aligned
			assert (((uintptr_t) block & align) == 0);
		}

		// Add first buffer overflow check
		*(block - 2) = 0x48;
		*(block - 1) = 0x15;

		// Add second buffer overflow check
		*(block + blockSize + 0) = 0x16;
		*(block + blockSize + 1) = 0x23;

		// Set the next free block pointer
		*((uintptr_t*) (block + blockSize + 2)) = (uintptr_t) mFree;
		mFree = block;
	}
}

////////////////////////////////////////////////////////////////////////////////
/// <summary> Frees all blocks and deallocates used memory. </summary>
/// <remarks> Buffer overflow checks are not performed. </remarks>
/// <runtime> This function performs in constant time; O(1). </runtime>

BlockAllocator::~BlockAllocator (void)
{
	delete[] mAllocation;
}



//----------------------------------------------------------------------------//
// Functions                                                   BlockAllocator //
//----------------------------------------------------------------------------//

////////////////////////////////////////////////////////////////////////////////
/// <summary> Allocates a memory block capable of storing BlockSize. </summary>
/// <returns> Address to allocated data, or nullptr if out of memory. </returns>
/// <remarks> Constructors are not called on generic class types. </remarks>
/// <runtime> This function performs in constant time; O(1). </runtime>

template<typename Type>
Type* BlockAllocator::Allocate (void)
{
	mMutex.lock();

	// Ran out of memory
	if (mFree == nullptr)
	{
		mMutex.unlock();
		return nullptr;
	}

	// Get first free block
	uint8_t* block = mFree;

	// Mark block as in use
	*(block + mBlockSize + 1) = 0x42;

	// Set next free block
	mFree = (uint8_t*) *((uintptr_t*) (block + mBlockSize + 2));

	mMutex.unlock();
	return (Type*) block;
}

////////////////////////////////////////////////////////////////////////////////
/// <summary> Frees a previously allocated block of memory. Does nothing if
///			  the memory block specified is nullptr. Crashes if the specified
///			  block is either invalid or has already been freed. </summary>
/// <remarks> Function crashes on detection of buffer overflows. </remarks>
/// <runtime> This function performs in constant time; O(1). </runtime>

template<typename Type>
void BlockAllocator::Free (Type* blockLocation)
{
	// Check if block location is valid
	if (blockLocation == nullptr) return;

	mMutex.lock();

	// Convert the specified block location
	uint8_t* block = (uint8_t*) blockLocation;

	// Assert magic overflow values
	assert (*(block - 2) == 0x48 &&
			*(block - 1) == 0x15 &&
			*(block + mBlockSize + 0) == 0x16 &&
			*(block + mBlockSize + 1) == 0x42);

	// Mark block as not in use
	*(block + mBlockSize + 1) = 0x23;

	// Set the next free block pointer
	*((uintptr_t*) (block + mBlockSize + 2)) = (uintptr_t) mFree;
	mFree = block;
	mMutex.unlock();
}



//----------------------------------------------------------------------------//
// Tests                                                                      //
//----------------------------------------------------------------------------//

////////////////////////////////////////////////////////////////////////////////

static void TestBasic (void)
{
	// Print everything using hex
	std::cout.setf (std::ios::hex, std::ios::basefield);

	{
		BlockAllocator a (sizeof (uint32_t), 4, 32);
		uint32_t *a1, *a2, *a3, *a4, *a5;

		a1 = a.Allocate<uint32_t>();
		a2 = a.Allocate<uint32_t>();

		*a1 = 0x12345678;
		*a2 = 0x87654321;
		std::cout << *a1 << " == " << 0x12345678 << " " << (*a1 == 0x12345678) << std::endl;
		std::cout << *a2 << " == " << 0x87654321 << " " << (*a2 == 0x87654321) << std::endl;
	
		a3 = a.Allocate<uint32_t>();
		a4 = a.Allocate<uint32_t>();

		*a1 = 0x11223344;
		*a2 = 0x44332211;
		*a3 = 0x55667788;
		*a4 = 0x88776655;

		std::cout << *a1 << " == " << 0x11223344 << " " << (*a1 == 0x11223344) << std::endl;
		std::cout << *a2 << " == " << 0x44332211 << " " << (*a2 == 0x44332211) << std::endl;
		std::cout << *a3 << " == " << 0x55667788 << " " << (*a3 == 0x55667788) << std::endl;
		std::cout << *a4 << " == " << 0x88776655 << " " << (*a4 == 0x88776655) << std::endl;

		a5 = a.Allocate<uint32_t>();
		std::cout << a5 << " == " << 0 << " " << (a5 == nullptr) << std::endl;

		a.Free (a1);

		a5 = a.Allocate<uint32_t>();
		std::cout << a5 << " != " << 0 << " " << (a5 != nullptr) << std::endl;

		a.Free (a2);
		a.Free (a3);
		a.Free (a4);
		a.Free (a5);
	}
	{
		BlockAllocator b (sizeof (uint16_t), 4, 16);
		uint16_t *b1, *b2, *b3, *b4;

		b1 = b.Allocate<uint16_t>();
		b2 = b.Allocate<uint16_t>();
		b3 = b.Allocate<uint16_t>();
		b4 = b.Allocate<uint16_t>();

		std::cout << "Aligned? " << b1 << " " << (((uintptr_t) b1 & 15) == 0) << std::endl;
		std::cout << "Aligned? " << b2 << " " << (((uintptr_t) b2 & 15) == 0) << std::endl;
		std::cout << "Aligned? " << b3 << " " << (((uintptr_t) b3 & 15) == 0) << std::endl;
		std::cout << "Aligned? " << b4 << " " << (((uintptr_t) b4 & 15) == 0) << std::endl;

		b.Free (b1);
		b.Free (b2);
		b.Free (b3);
		b.Free (b4);
	}

	// Unset hex printing
	std::cout.unsetf (std::ios::hex);
}

////////////////////////////////////////////////////////////////////////////////

static void TestZero (void)
{
	{
		BlockAllocator a (sizeof (uint32_t), 0, 32);
		uint32_t* a1 = a.Allocate<uint32_t>();
		std::cout << a1 << " == " << 0 << " " << (a1 == nullptr) << std::endl;
		a.Free (a1);
	}
	{
		BlockAllocator b (0, 1, 0);
		void* b1 = b.Allocate<void>();
		std::cout << b1 << " != " << 0 << " " << (b1 != nullptr) << std::endl;
		b.Free (b1);
	}
	{
		BlockAllocator c (0, 1, 16);
		void* c1 = c.Allocate<void>();
		std::cout << c1 << " != " << 0 << " " << (c1 != nullptr) << std::endl;
		c.Free (c1);
	}
	{
		BlockAllocator d (sizeof (uint32_t), 1, 0);
		uint32_t* d1 = d.Allocate<uint32_t>();
		std::cout << d1 << " != " << 0 << " " << (d1 != nullptr) << std::endl;
		d.Free (d1);
	}
}

////////////////////////////////////////////////////////////////////////////////

static void TestBig (void)
{
	BlockAllocator a (sizeof (uint32_t), 5000, 32);
	uint32_t* ax[5000] = { nullptr };

	for (size_t i = 0; i < 2000; ++i)
		ax[i] = a.Allocate<uint32_t>();

	for (size_t i = 0; i < 1000; ++i)
		a.Free (ax[i]);

	for (size_t i = 0; i < 1000; ++i)
		ax[i] = a.Allocate<uint32_t>();

	for (size_t i = 2000; i < 5000; ++i)
		ax[i] = a.Allocate<uint32_t>();

	for (size_t i = 0; i < 5000; ++i)
	{
		if (ax[i] == nullptr)
		{
			std::cout << i << " is not allocated..." << std::endl;
			return;
		}

		if (((uintptr_t) ax[i] & 31) != 0)
		{
			std::cout << i << " is not aligned..." << std::endl;
			return;
		}

		*ax[i] = (uint32_t) i * 0x123456;
	}

	for (size_t i = 0; i < 5000; ++i)
		a.Free (ax[i]);
}

////////////////////////////////////////////////////////////////////////////////

static void TestClass (void)
{
	// Print everything using hex
	std::cout.setf (std::ios::hex, std::ios::basefield);

	class MyClass
	{
	public:
		void Init() { A = 0; B = 0; }
		uint32_t A, B;
	};

	BlockAllocator a (sizeof (MyClass), 2, 32);
	MyClass *a1, *a2;

	a1 = a.Allocate<MyClass>();
	a2 = a.Allocate<MyClass>();
	a1->Init();
	a2->Init();

	std::cout << a1->A << " == " << 0 << " " << (a1->A == 0) << std::endl;
	std::cout << a1->B << " == " << 0 << " " << (a1->B == 0) << std::endl;
	std::cout << a2->A << " == " << 0 << " " << (a2->A == 0) << std::endl;
	std::cout << a2->B << " == " << 0 << " " << (a2->B == 0) << std::endl;

	a1->A = 0x11223344;
	a1->B = 0x44332211;

	a2->A = 0x55667788;
	a2->B = 0x88776655;

	std::cout << a1->A << " == " << 0x11223344 << " " << (a1->A == 0x11223344) << std::endl;
	std::cout << a1->B << " == " << 0x44332211 << " " << (a1->B == 0x44332211) << std::endl;
	std::cout << a2->A << " == " << 0x55667788 << " " << (a2->A == 0x55667788) << std::endl;
	std::cout << a2->B << " == " << 0x88776655 << " " << (a2->B == 0x88776655) << std::endl;

	a.Free (a1);
	a.Free (a2);

	// Unset hex printing
	std::cout.unsetf (std::ios::hex);
}

////////////////////////////////////////////////////////////////////////////////

static void TestDoubleFree (void)
{
	BlockAllocator a (sizeof (uint32_t), 1, 32);

	uint32_t* a1 = a.Allocate<uint32_t>();
	*a1 = 0x12345678;
	a.Free (a1);
	a.Free (a1);
}

////////////////////////////////////////////////////////////////////////////////

static void TestOverflow1 (void)
{
	BlockAllocator a (sizeof (uint32_t), 1, 32);

	uint32_t* a1 = a.Allocate<uint32_t>();
	a1[0] = 0x12345678;
	a1[1] = 0x87654321;
	a1[2] = 0x12345678;
	a.Free (a1);
}

////////////////////////////////////////////////////////////////////////////////

static void TestOverflow2 (void)
{
	BlockAllocator a (sizeof (uint16_t), 1, 16);

	uint32_t* a1 = a.Allocate<uint32_t>();
	*a1 = 0x12345678;
	a.Free (a1);
}



//----------------------------------------------------------------------------//
// Main                                                                       //
//----------------------------------------------------------------------------//

////////////////////////////////////////////////////////////////////////////////
/// <summary> Main execution point for this application. </summary>
/// <param name="argc"> Argument count in the command line. </param>
/// <param name="argv"> Arguments from the command line. </param>
/// <returns> Zero for success, error code for failure. </returns>

int main (int argc, const char* argv[])
{
	// Class testing was performed in three separate parts. The first part involved using
	// perfect induction in order to show that all possible states a function encountered
	// would be handled and worked as expected. Due to the similarities this problem shares
	// with linked lists, the number of potential states were minimal and could be stepped
	// through easily. The second part involved using a debugger and inspecting changes in
	// memory as each operation was executed. The third and final part of testing involved
	// writing unit tests which illustrated each state working. This can be seen by running
	// the application using the test case functions. Additionally, performance tests were
	// also ran using a high resolution timer and showed that, in ideal conditions, the
	// BlockAllocator class allocated memory fourteen times faster than the standard new and
	// delete supplied with the compiler. This is a phenomenal increase in speed which will
	// prove very useful in areas where continuous allocations are performed.

//	TestBasic();		// Basic allocator usage
//	TestZero();			// Passing zeroes in constructor
//	TestBig();			// Testing big allocations
//	TestClass();		// Use various class types
//	TestDoubleFree();	// Perform a double free (crash)
//	TestOverflow1();	// Perform buffer overflow (crash)
//	TestOverflow2();	// Perform buffer overflow (crash)

	std::cout << "Jobs done\n";
	getchar();
	return 0;
}

/*
Coding assignment for GPU Software Developer Technologies engineer.

1. Implement a block allocator that will manage a single heap allocation to allocate
   fixed-sized regions (blocks) of memory.
   
    - The block allocator is initialized with a block size, a max blocks count and a
      block alignment. Regions returned by Allocate() must at least be able to store
      blockSize bytes. Addresses returned by Allocate() must have an alignment of
      blockAlignment. A region sufficiently large to store maxBlocks blocks should
      be created.

    - The destructor should free the allocator's heap allocation. You do not need to
      reference count.

    - Allocate() must return an address to a region inside the block allocator's
      heap allocation aligned to the specified block alignment and capable of
      storing at least blockSize bytes. If there is no free memory, nullptr (0) must
      be returned.

    - Free() must mark the passed block as free. If the address is invalid, the
      program should crash. If the address is nullptr (0), Free should be a no-op.

You may implement any additional methods you may need, but you cannot change the
public interface defined below.

2. Use the main() function to unit test your allocator and demonstrates that it
   operates properly.
   
   You can break up your tests into multiple functions called from main as you see
   fit. You cannot add new public functions to BlockAllocator for testing purposes
   (black box testing only).

3. (Optional) If you want, you can consider the following ideas in your
   implementation.

    - Thread safety.
    - Detecting buffer overflows in Free().
    - Template allocator that allocates and frees objects of a template type instead
      of raw memory.

The program must compile using GCC or clang using an invocation like:
    
    clang -std=c++0x --stdlib=libc++ -Wall -o assignment assignment.cpp

You cannot use STL algorithms or collections. You may only use new[] or malloc() in the
BlockAllocator constructor.

You may use C99 and/or C++11.
*/