Memory manager

[Busybox]

Hello everybody! I wrote a memory manager about 2 weeks, but I could not. Can you give a good example of memory management (paging, heap) without bugs ? So I can understand the design and make my implementation. Thank you in advance.

[irvanherz]

Recently I've successfully turning my kernel to 0x80000000, and now I still developing the virtual memory manager too. Currently I still completed in page frame allocation.
I suggest to fork some design from these linux's docs below.
www.tldp.org/LDP/tlk/kernel/processes.html
http://www.tldp.org/LDP/tlk/mm/memory.html

[Ycep]

I wrote a memory manager about 2 weeks, but I could not.

Hmmm... that means you failed.
Let's start with second simplest one (and yes, paging and heap gonna wait until you have working physical memory manager):
For now you could use bitmap allocator, which works basically like this:
We have array of bits (yes, bits, not bytes) where each bit represents a block.
To allocate a block, find first bit in array which is zero. When it is found, fill that bit and return calculated address of that block.
==Example start==
We have a system containing of 64KB free memory, and each block has to be 4KB.
If we have 64KB of free memory, amount of blocks is 16, so we need 2 bytes for bitmap array.
At beginning, we shall have bitmap array filled with zeros ( 0000000000000000 ), which represents that all of these blocks are unused.
First block starts in 32KB.
Bitmap array : 100000000000000 (notice that first bit is used, which means that first block has taken.
Now, to allocate three blocks, do same above but instead one bit try to find three empty bits in row. When found, fill them all.
Bitmap array : 111100000000000 (Three more blocks taken)
==Example end==
To free block located with given memory address, calculate the block no. and empty that bit in bitmap array.
Calculation for getting block no. from address stands like this : (address-offset)/blocksize.
==Example start==
If we want to free a block located at 48 KB, block size is 8KB and first block address, i.e. offset is 16KB, we do this:
(48KB-16KB)/8KB=4, which means that 4th block is located at 48KB memory address.
==Example end==
I hope you understood the theory.

[Busybox]

I wrote a memory manager about 2 weeks, but I could not.

Hmmm... that means you failed.
Let's start with second simplest one (and yes, paging and heap gonna wait until you have working physical memory manager):
For now you could use bitmap allocator, which works basically like this:
We have array of bits (yes, bits, not bytes) where each bit represents a block.
To allocate a block, find first bit in array which is zero. When it is found, fill that bit and return calculated address of that block.
==Example start==
We have a system containing of 64KB free memory, and each block has to be 4KB.
If we have 64KB of free memory, amount of blocks is 16, so we need 2 bytes for bitmap array.
At beginning, we shall have bitmap array filled with zeros ( 0000000000000000 ), which represents that all of these blocks are unused.
First block starts in 32KB.
Bitmap array : 100000000000000 (notice that first bit is used, which means that first block has taken.
Now, to allocate three blocks, do same above but instead one bit try to find three empty bits in row. When found, fill them all.
Bitmap array : 111100000000000 (Three more blocks taken)
==Example end==
To free block located with given memory address, calculate the block no. and empty that bit in bitmap array.
Calculation for getting block no. from address stands like this : (address-offset)/blocksize.
==Example start==
If we want to free a block located at 48 KB, block size is 8KB and first block address, i.e. offset is 16KB, we do this:
(48KB-16KB)/8KB=4, which means that 4th block is located at 48KB memory address.
==Example end==
I hope you understood the theory.

Thank you for reply!
Does this function right?

Code: Select all

uint32_t* pmm_alloc()
{
	for(uint32_t i = 0; i < mem_size / 4; i++)
		for(uint32_t j = 0; j < 8; j++)
			if(!CHECK_BIT(bitmap[i], j))
			{
				SET_BIT(bitmap[i], j);
				return (uint32_t*)(kernel_end + i * 4096);
			}
}

:

[capstrovor]

Does this function right?

Code: Select all

uint32_t* pmm_alloc()
{
	for(uint32_t i = 0; i < mem_size / 4; i++)
		for(uint32_t j = 0; j < 8; j++)
			if(!CHECK_BIT(bitmap[i], j))
			{
				SET_BIT(bitmap[i], j);
				return (uint32_t*)(kernel_end + i * 4096);
			}
}

:

Why do you devide mem_size by 4?

[stdcall]

Why do you devide mem_size by 4?

4 bytes in an int.

[irvanherz]

In my OS, I'm using page frame linked list.

Code: Select all

PDWORD pFrameTable;
DWORD iFrameFirstFree = 0;
DWORD iFrameFirstCommit = 0;
DWORD iFrameFirstReserved = 0;

void _KiVmmFrameAddAvail(DWORD dwFrame){
	DWORD iFrame = dwFrame / PAGE_SIZE;
	pFrameTable[iFrame] = iFrameFirstFree;
	iFrameFirstFree = iFrame;
}

PDWORD KiVmmBuildFrameTable(){
	extern PMA PmaTbl[MAX_PMA];
	KPrintf("Building free page list...\n");
	DWORD dwTotalMem = PmmTotalPmaMem();
	DWORD dwBufSize = (dwTotalMem / PAGE_SIZE) * 4;
	pFrameTable = (PDWORD) KiVmmValloc(dwBufSize);
	PPMA pPma = PmaTbl;
	while(pPma->dwStart){
		pPma++;
	}
	for(;(UINT)pPma >= (UINT)PmaTbl;pPma--){
		DWORD dwMemStart = KiAlignValue(pPma->dwStart,PAGE_SIZE);
		DWORD dwMem = KiAlignValue(dwMemStart + pPma->dwSize, PAGE_SIZE);
		if(pPma->dwFlags == PMA_AVAILABLE){
			for(;dwMem >= dwMemStart;dwMem-=PAGE_SIZE){
				_KiVmmFrameAddAvail(dwMem);
				//KPrintf("%x, ",dwMem);
			}
		}
	}
}
//KAllocFrame()
DWORD KCommitFrame(){
	DWORD iFree = iFrameFirstFree;
	DWORD iCommit = iFrameFirstFree;
	DWORD dwResult = iFree * PAGE_SIZE;
	iFrameFirstFree = pFrameTable[iFree];
	pFrameTable[iCommit] = iFrameFirstCommit;
	iFrameFirstCommit = iCommit;
	return dwResult;
}

void KFreeFrame(DWORD dwAddress){
	DWORD dwFrame = dwAddress / PAGE_SIZE;
	DWORD iFree = iFrameFirstCommit;
	pFrameTable[iFree] = iFrameFirstFree;
	iFrameFirstFree = dwFrame;
	iFrameFirstCommit = pFrameTable[dwFrame];
}

The benefit using linked list is, we can allocate faster. But also we can check availability by providing some bits in frame address as flags.
I provide KiVmmAlloc and another Ki... function for allocating virtual memory in initialization. It will allocate frame and VA contiguously without writing any data structures. But it has variable to track next free contiguous frame address and VA. After initialization completed, I call KVmmInit and other K... functions to make full working allocation, with data structures for tracking allocated and free memory and VA

[carbonBased]

Why do you devide mem_size by 4?

4 bytes in an int.

But you're building a page allocator, so mem_size would either be divided by PAGE_SIZE, or would be a multiple of PAGE_SIZE, so no division (or shifting) required.

Also, to add on to what you've got, a stack of available pages would be faster than a linear search of a bitmap.

To initialize, push every page onto the stack.
To allocate, pop the head of the stack.
To free, add the pointer back to the stack.

The last step ideally has some security to ensure the page you're freeing is actually a page that was allocated.

Cheers,
Jeff

[carbonBased]

Why do you devide mem_size by 4?

4 bytes in an int.

But you're building a page allocator, so mem_size would either be divided by PAGE_SIZE, or would be a multiple of PAGE_SIZE, so no division (or shifting) required.

Also, to add on to what you've got, a stack of available pages would be faster than a linear search of a bitmap.

To initialize, push every page onto the stack.
To allocate, pop the head of the stack.
To free, add the pointer back to the stack.

The last step ideally has some security to ensure the page you're freeing is actually a page that was allocated.

Cheers,
Jeff

n/m, I see what your intent is with the /8.

Alternatively (less branching, likely faster on most modern targets)...

Code: Select all

for(unsigned p = 0; p < num_pages; p++)
{
    if(!CHECK_BIT(bitmap[p>>3], p & 7))
    {
      // etc...
    }
}

Cheers,
Jeff

[MichaelFarthing]

Alternatively (less branching, likely faster on most modern targets)...

Code: Select all

for(unsigned p = 0; p < num_pages; p++)
{
    if(!CHECK_BIT(bitmap[p>>3], p & 7))
    {
      // etc...
    }
}

Really? With both that p>>3 and p&7 in every iteration? Far exceeds the cost of a double iteration since the outer loop only happens once in 32 and the jumps are tiny.

But why not actually look at the generated code and then you can make a fairly certain judgement.

[Ycep]

I wrote a memory manager about 2 weeks, but I could not.

Hmmm... that means you failed.
Let's start with second simplest one (and yes, paging and heap gonna wait until you have working physical memory manager):
For now you could use bitmap allocator, which works basically like this:
We have array of bits (yes, bits, not bytes) where each bit represents a block.
To allocate a block, find first bit in array which is zero. When it is found, fill that bit and return calculated address of that block.
==Example start==
We have a system containing of 64KB free memory, and each block has to be 4KB.
If we have 64KB of free memory, amount of blocks is 16, so we need 2 bytes for bitmap array.
At beginning, we shall have bitmap array filled with zeros ( 0000000000000000 ), which represents that all of these blocks are unused.
First block starts in 32KB.
Bitmap array : 100000000000000 (notice that first bit is used, which means that first block has taken.
Now, to allocate three blocks, do same above but instead one bit try to find three empty bits in row. When found, fill them all.
Bitmap array : 111100000000000 (Three more blocks taken)
==Example end==
To free block located with given memory address, calculate the block no. and empty that bit in bitmap array.
Calculation for getting block no. from address stands like this : (address-offset)/blocksize.
==Example start==
If we want to free a block located at 48 KB, block size is 8KB and first block address, i.e. offset is 16KB, we do this:
(48KB-16KB)/8KB=4, which means that 4th block is located at 48KB memory address.
==Example end==
I hope you understood the theory.

Thank you for reply!
Does this function right?

Code: Select all

uint32_t* pmm_alloc()
{
	for(uint32_t i = 0; i < mem_size / 4; i++)
		for(uint32_t j = 0; j < 8; j++)
			if(!CHECK_BIT(bitmap[i], j))
			{
				SET_BIT(bitmap[i], j);
				return (uint32_t*)(kernel_end + i * 4096);
			}
}

:

Well, yes, actually! You understood my words very quick... Bravo.
The only thing that seems to be wrong is that mem_size. If you use kernel_end, you shall probably do the (mem_size-kernel_end)/4...
Anyways, good start. Now try to create alloc function with support for using more than one block, and a free function.
If you want different design, you could try use free lists, or even buddy allocator, which are much more efficent.
Althrough buddy allocator has large overhead (If you know what overhead means) if you mix it with bitmaps.

[Busybox]

Thanks for the theory!

Can i do something like this?

Code: Select all

uint32_t* pmm_allocn(uint32_t size)
{
	if(!size) return 0;
	uint32_t* first = pmm_alloc();
	if(size > 1)
		for(; size > 1; size--)
			pmm_alloc();

	return first;
}

[crunch]

Instead of asking if you can do those things, why don't you just implement them and debug? See what kinds of output you get, determine if there are memory leaks or holes.

[Busybox]

Should i divide by 4 or 4096?
mem = RAM size in KB.

Code: Select all

bitmap_size = ((mem - kernel_end) / 4096) / 8;

[MichaelFarthing]

Should i divide by 4 or 4096?
mem = RAM size in KB.

Code: Select all

bitmap_size = ((mem - kernel_end) / 4096) / 8;

Well I'm tempted to say "both".
There was some ambiguity in the original that you are quoting. (mem-kernel_end) was intended to be measured in pages not bytes.

If you have any understanding of what is going on you should be able to work it out. It should also be fairly obvious that your bitmap size is not going to be a quarter of your available memory

That divide by 4 though? What was that for? Well, I'm sorry, I am not going to give you the answer. Look at the code you have been given. Look at the rival code also suggested by someone else (this gives a clue). Work out what they are both doing and what the differences are.
Blood sweat and tears are needed.

Am I being cruel? As my parents said to me when I was a small childe, 'We're being cruel to be kind'.