OSDev.org

Posted: **Sat Jul 14, 2007 6:58 pm**

Ok, my kernel can determine the size of the ram memory. Let's see, imagine 512 mb, now how can I determine the free blocks? I know that's 512 mb but I don't know where are the free blocks and what is the max address that I can allocate.... The only think I now is that GDT, Kernel Stack and LDT are under 0x100000 and my kernel is at the 1 MB mark ( using 8 kbs )

Posted: **Sat Jul 14, 2007 7:23 pm**

Blocks As 4096KB Physical Pages
Can a 4096KB physical page be a block? Yes.

What could a block be?

Code: Select all

for(unsigned int x = 0; x < (1024 * 1024 * 512); x += 4096)
{
    // this is a page (considered a block)
    printf("My memory block is at address %x.\n", x);
   // How do I know what is in this block?
}

Is this block free? How do I know?

Code: Select all

for(unsigned int x = 0; x < (1024 * 1024 * 512); x += 4096)
{
    // this is a page (considered a block)
    printf("My memory block is at address %x...", x);
    // if block is above my kernel then... i do not think anything is using it.
    if(x > (0x100000 + (1024 * 28))
    {
        printf("This is a free block.\n");
     }
}

How can I store blocks in a list?

Code: Select all

unsigned long free_blocks_index = 0;
unsigned long free_blocks[1024];
for(unsigned int x = 0; x < (1024 * 1024 * 512); x += 4096)
{
    // this is a page (considered a block)
    printf("My memory block is at address %x...", x);
    // if block is above 16MB.. then it should have a great chance of not being used?
    if(x > (0x100000 + (1024 * 1024 * 16))
    {
        printf("This is a free block above 16MB.\n");
        free_blocks[free_blocks_index] = x;
        free_blocks_index = free_blocks_index + 1;
     }
}

Why would I store blocks in a list?

Code: Select all

unsigned long free_blocks_index = 0;
unsigned long free_blocks[1024];
void make_free_blocks_list()
{
  for(unsigned int x = 0; x < (1024 * 1024 * 512); x += 4096)
  {
      // this is a page (considered a block)
      printf("My memory block is at address %x...", x);
      // if block is above 16MB.. then it should have a great chance of not being used?
      if(x > (0x100000 + (1024 * 1024 * 16))
      {
          printf("This is a free block above 16MB.\n");
          free_blocks[free_blocks_index] = x;
          free_blocks_index = free_blocks_index + 1;
       }
}
unsigned long get_free_block()
{
    free_blocks_index = free_blocks_index - 1;
    return free_blocks[free_blocks_index];
}

make_free_blocks_list();
printf("A free block is %x\n", get_free_block());
printf("ANOTHER.. free block is %x\n", get_free_block());
printf("and ANOTHER.. free block is %x\n", get_free_block());

Posted: **Sat Jul 14, 2007 8:50 pm**

Ohh, it's clear for me now !!!

But what if user requests for only 1 byte of memory ??

Posted: **Sat Jul 14, 2007 11:11 pm**

Partition the block.

Posted: **Wed Jul 18, 2007 3:47 pm**

hum...
and what about the memory map?

Posted: **Wed Jul 18, 2007 3:50 pm**

The memory map tells you where you are allowed to allocate blocks, which you then partition to give away smaller amounts.

Posted: **Wed Jul 18, 2007 4:22 pm**

Hum.... you used 4kb memory blocks in the code above
and you were considering memory above 17 MB
This way, with 512 mb I'll have 495 MB. So It will take 126720 positions on the list.
If I want to relocate smaller clusters I need a dynamic list with some informations ( block size, is this block free and block position ).

Code: Select all

struct memorylist {

  unsigned short status;  // The higher bit is for telling if the block is free or not and the other bits are for the block size ( from 0 bytes to 32 kb )
  unsigned long pos; //memory position

};

so...

Code: Select all

//blocks starting with 4 kbs of size would use :
struck memorylist mblocks[ 1024 *  (512 - 17) / 4 ];

Is this ok?

Posted: **Wed Jul 18, 2007 6:44 pm**

Hi...

I think you're doing things in the wrong way,memory manager consists
of three layers:

*physical memory manager
*paging
*malloc/free

for the first layer you guys were talking about,it's simple
you just need a way to determine which block is free and which block
is used,each block 4KB,there are two common ways for doing this:
*using a bitmap
here you need one bit for each page,if bit is set this means the
block is allocated,else if it 0 block is not allocated.
*using stack
here you push the address of each free block in the stack and when you need
to allocate a block you just pop the address of the stack.
it's fast than bitmap but it needs more memory.

The second layer is paging I would recommended reading
Intel manual chapter 3.3.6

Last layer it's little bit more complicated,here in this stage
you can speak about allocating 1B or 100B or any size you want...

So first of all I would realy recommended reading this two tutorials
http://www.osdever.net/tutorials/memory1.php
http://www.osdever.net/tutorials/memory2.php

Thanx.

Posted: **Thu Jul 19, 2007 7:02 am**

but in the case of using a bitmap, the size of the bitmap will be the size of the ram / 8 ( since each byte has 8 bits ). How can someone allocate a dynamic bitmap?

Posted: **Thu Jul 19, 2007 3:08 pm**

simple,you could get the size of your RAM via GRUB info
or by using BIOS INTs

Posted: **Thu Jul 19, 2007 5:37 pm**

artrecks wrote:but in the case of using a bitmap, the size of the bitmap will be the size of the ram / 8 ( since each byte has 8 bits ). How can someone allocate a dynamic bitmap?

Mostly, you are handed or should be prepared to be handed a series of memory ranges instead of one large big ol' block of free memory at once. If you did get handed a big ol' large free range, and only one mine you. This entire process would be much easier since you would simply check if the range is large enough, then if it is subtract that amount from it for the bitmap.

CountOf4096ByteMemoryPages=FreeMemoryInBytes>>12;
SizeOfBitmapInBytes=CountOf4096ByteMemoryPages/8;

Unfortunately, like I said above the general case will be that RAM will be slightly fragmented. You can still expect a rather large free range on a system with a large amount of memory, but you will also get small ranges which fill in the gaps between BIOS areas and such other things (especially, in lower memory).

But do not fear since there is a way to get around this daunting brain teaser, and it sports some nice cookies at the end. Well.. no cookies but it would be nice if it did.

Two Pass
This is most likely the simple one to implement since it requires very little complexity. You can even implement this outside the memory manager if you wish. The idea is to scan over the list of free memory ranges, and pick the largest then hand this to the memory manager and let it use it for initialization to create the bitmap in.

// GRUB, gives us a memory map.
.... .. code .. ..
// (FIRST PASS) Lets scan this memory map, and pick the largest range.
.... .. code .. ..
// Subtract the amount we need for our bitmap, from this largest range.
... ... . code ... .
// (SECOND PASS) Start adding memory to our bitmap..

Linked
This one is not very helpful when implementing a basic bitmap, which needs to be contiguous in memory unless you are aiming for a implementation that fits into some _really_ fragmented memory. The idea is that your implementation, (which may be a bitmap, stack, or tree), can handle being fragmented. The most perfect fragment size is going to be a page of memory which is by default 4096 bytes on the IA32 when not using any extensions. What you want to do is always have one handy free page lying around doing nothing.. the way to do this is to always check if you have one.

Code: Select all

void memory_manager_init(unsigned long pageOffset, unsigned long pageCount)
{
    static unsigned long lazy_page = 0xFFFFFFFF;
    for(; pageOffset < ((pageCount * 4096) + pageOffset); pageOffset += 4096)
    {
          if(lazy_page == 0xFFFFFFFF)
          {
               lazy_page = pageOffset;     
          }else{
               // add pageOffset into the (fragmented bitmap, stack, or tree).
               // if you need a extra page for more storage get it from lazy_page
              // (set lazy_page to 0xFFFFFFFF if you use it)
          }
    }
    return;
}

This is a mock up example of the function calling the memory manager initialization function... or add memory function - whatever it might be.

Code: Select all

for(... loop through GRUB memory map ...)
{
    memory_manager_init(grub_mem_map_entry->address>>12, grub_mem_map_entry->sizeInBytes>>12);
}

You could add some code to also ensure that each address and size reside on a page boundary to prevent a rare and strange bug which I have yet to encounter when using GRUB, but just FYI.

OSDev.org

Memory Manager

Memory Manager