OSDev.org

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

Lukand wrote:

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.

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);
			}
}

Busybox wrote: 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 wrote:

Why do you devide mem_size by 4?

4 bytes in an int.

carbonBased wrote:

stdcall wrote:

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

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

carbonBased wrote:

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...
    }
}

Busybox wrote:

Lukand wrote:

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);
			}
}

:

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

Code: Select all

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