stack vs bitmap

[ucosty]

I have made a hybrid algorithm that takes basically backs a stack allocator with a bitmap to make deallocation safe.

Basically when memory is allocated, a value is popped off the stack and the address is marked in the bitmap. When it is time to free the memory, the bitmap is checked to ensure memory doesn't get double freed and then the value is pushed back on to the stack. It is speedy, operating in constant time for both alloc and free operations, and it is capable of fast consistency checking (unlike a stack, which would require expensive iterative operations to ensure there aren't duplicate entries on the stack).

[ucosty]

Before I made my hybrid algorithm I made a generic bitmap algo, like the one in JamesM's tutorial, and made a benchmark tool for it.

Code: Select all

273814 frames allocated in 1000 milliseconds (1069 MB)
387904 frames allocated in 2000 milliseconds (1515 MB)
472588 frames allocated in 3000 milliseconds (1846 MB)
542474 frames allocated in 4000 milliseconds (2119 MB)
603190 frames allocated in 5000 milliseconds (2356 MB)
670271 frames allocated in 6000 milliseconds (2618 MB)
724350 frames allocated in 7000 milliseconds (2829 MB)
774298 frames allocated in 8000 milliseconds (3024 MB)
821233 frames allocated in 9000 milliseconds (3207 MB)
864210 frames allocated in 10000 milliseconds (3375 MB)
901235 frames allocated in 11000 milliseconds (3520 MB)
941861 frames allocated in 12000 milliseconds (3679 MB)
979355 frames allocated in 13000 milliseconds (3825 MB)
1010964 frames allocated in 14000 milliseconds (3949 MB)

Basically it takes a whole 15 seconds to allocate 4gb of physical RAM. Also, the more ram that is used the slower allocations take to perform. This is compiled as a release build using Microsoft Visual C++ 2005.

edit:

A debug build of the same bitmap allocator:

Code: Select all

138307 frames allocated in 1000 milliseconds (540 MB)
195893 frames allocated in 2000 milliseconds (765 MB)
239543 frames allocated in 3000 milliseconds (935 MB)
273832 frames allocated in 4000 milliseconds (1069 MB)
303816 frames allocated in 5000 milliseconds (1186 MB)
328441 frames allocated in 6000 milliseconds (1282 MB)
352115 frames allocated in 7000 milliseconds (1375 MB)
371408 frames allocated in 8000 milliseconds (1450 MB)
390836 frames allocated in 9000 milliseconds (1526 MB)
408839 frames allocated in 10000 milliseconds (1597 MB)
429535 frames allocated in 11000 milliseconds (1677 MB)
446240 frames allocated in 12000 milliseconds (1743 MB)
465661 frames allocated in 13000 milliseconds (1818 MB)
482927 frames allocated in 14000 milliseconds (1886 MB)

In the same amount of time it allocates less than half the amount of memory.

[FlashBurn]

Maybe you could post your code to benchmark your algo, so that I can also test my algo.

Did you also use a 4MiB pages bitmap for speeding up the search for a free page? There are other options to speed the whole thing up.

[ucosty]

I have extracted the benchmarking code. It's fairly stupid and relies on windows api calls for the timing.

Code: Select all

	for(int test=0; test<15; test++)
	{
		start_time = GetTickCount();
		num_allocations = 0;

		while(GetTickCount() - start_time < test*1000)
		{
			results[num_allocations++] = bitmap_alloc();
		}

		unsigned long end_time = GetTickCount();
		unsigned long delta_time = end_time - start_time;

		cout << num_allocations << " frames allocated in " << delta_time << " milliseconds (" << (num_allocations * 4) / 1024 << " MB)" << endl;

		unsigned long num_frees = 0;
		start_time = GetTickCount();

		// Free test
		while(num_frees != num_allocations)
		{
			bitmap_free(results[num_frees++]);
		}

		end_time = GetTickCount();
		delta_time = end_time - start_time;

		//cout << num_frees << " frames freed in " << delta_time << " milliseconds" << endl;
	}

Edit:
Just in case anybody would like to compare, here is my implementation of my bitmap-backed stack allocator straight from my OS code. I appolagise for the quality of code in advance

Code: Select all

namespace memory
{
	FrameAllocator Frames;
	
	void FrameAllocator::InitFrameAllocator(unsigned int mmap_addr, unsigned int mmap_length)
	{
		// Locate the memory stack at end of kernel
		unsigned long end_of_kernel = (unsigned long) &_ebss;

		// Set the bitmap location (ebss + 64k)
		this->bitmap = (unsigned long *) end_of_kernel + 0x10000;
		
		// Set the stack location (after end of bitmap)
		this->stack = (unsigned long *) end_of_kernel + 0x30000;
		

		// Setup the bitmap
		for(unsigned long i=0; i< 32768; i++)
		{
			bitmap[i] = 0;
		}
		
		multiboot::MMAP * mmap = (multiboot::MMAP*) mmap_addr;
	
		for (mmap = (multiboot::MMAP*) mmap_addr; (unsigned long)mmap < mmap_addr + mmap_length;
			mmap = (multiboot::MMAP*) ((unsigned long) mmap	+ mmap->size + sizeof (mmap->size)))
		{
			// mmap type 1 is free memory
			if(mmap->type == 1)
			{
				for(unsigned int page = 0;  page< mmap->length / 4096;  page++)
				{
					if( (mmap->baseAddress + (page * 4096)) <= (end_of_kernel + 0x30000)) {
						continue;
					}
						
					// Push page into the high memory stack
					this->stack[this->stack_size++] = mmap->baseAddress + (page * 4096);
				}
			}
		}
		
		unsigned long stack_size_frames = (this->stack_size / 1024);
		this->stack_marker = stack_size_frames + 1;
	}
	
	void * FrameAllocator::Alloc()
	{
		if(this->stack_marker == this->stack_size) return 0;

		// Mark the bitmap
		unsigned long bitfield = this->stack[this->stack_marker] / 131072;
		unsigned long bit = (stack[this->stack_marker] - (bitfield * 131072)) / 4096;

		if((this->bitmap[bitfield] & (1 << bit)) == 0)
		{
			this->bitmap[bitfield] += (1 << bit);
			return (void *) this->stack[this->stack_marker++];
		}

		return (void *) 0;
	}
	
	void FrameAllocator::Free(void * addr)
	{
		if(this->stack_marker == 0) return;

		// Check the bitmap
		unsigned long bitfield = (unsigned long) addr / 131072;
		unsigned long bit = ((unsigned long)addr - (bitfield * 131072)) / 4096;

		if((bitmap[bitfield] & (1 << bit)) == 0) {
			bochs << "Attempted double free of address " << addr << "\n";
		}
		else
		{
			bitmap[bitfield] -= (1 << bit);
			stack[--this->stack_marker] = (unsigned long) addr;
		}
	}
	
	unsigned long FrameAllocator::GetOverheads()
	{
		unsigned long overhead = 0x30000 + (this->stack_size * 4);
		return overhead;
	}
}