Memory management - Still not getting it.

[espenfjo]

I've read a bit about memory management now, both here in the forums, the wiki and over at bonafide. I'm still not really sure where to start with memory management, its easy to say i have to implement paging, bitmap structures and so on. The question is how

I think i need a hint that also your grandmother would understand

[Poseidon]

what you first should do, is keeping track of the free space in your physical memory (your real memory in your computer, with their own addresses). An easy and fast way to do is to have somewhere in your memory a stack of free memory addresses. When your kernel boots, it's empty. Then it uses the memory map from grub or the bootloader to see what space can be used. You loop through every block from the bootloader, if it's usable, loop through the length of the block itself with steps of 4096 bytes (that's the size of one page), and push everytime the address on the stack. When you allocate a bit of memory, it pops the latest address from the stack.
When you've done that, it's time for your virtual memory manager. This sets up a pagedirectory, which contains a pagetables and in there you can put your pages. You create a page by allocing one address from the real memory, set the priviliges and put it in the pagetable. The power of paging is that you can map any physical address to a virtual address: the virtual adddress 0xC0000000 can be at the physical address 0x100000. This is mine function to create a page:

Code: Select all

uint mm_page_bind(uint v_addr, char cpl, char wr) {
   uint pde = v_addr >> 22;
   uint pte = (v_addr >> 12) & 1023;
   uint page = mm_alloc_page();
   
   uint *pagedir = (uint *) MEM_PAGEDIR;
   uint *pagetable = (uint *) MEM_PAGETABLE;
   pagetable += pde * 1024;
   
   pagetable[pte] = page | (1 + (cpl << 2) + (wr << 1));
   return page;
}    

I believe there are some bugs somewhere in my memory manager, so i can't say this piece of code has no bugs but it gives you an idea of how it works. for further reading about paging, I recommend tim robinson's tutorial at www.osdever.net

hope this helps

[Brendan]

Hi,

I'd recommend seperating things properly. For example, write a "physical memory manager", then write a "linear memory manager" and then write any heap management code after that (malloc/free) if you want.

Also, make sure that your physical memory manager can handle 64 bit physical addresses - I've seen too many OS's that would crash horribly if you run them on a computer with over 4 GB of memory. I'd suggest splitting physical memory management into a least 2 seperate memory managers, one for 32 bit physical addresses and another for 64 bit addresses (even if the 64 bit physical memory manager never does anything).

This makes it much easier to add support for PAE later on, because with PAE you need 32 bit physical addresses for CR2 (even though everything else can use 64 bit physical addresses).

For example, use several seperate sub-directories in your source code:
- memory detection
- 32 bit physical memory manager
- 64 bit physical memory manager (possibly just a stub)
- normal linear memory manager
- optional PAE linear memory manager
- optional heap management

I use a seperate memory manager for memory below 16 MB due to ISA DMA constraints, with a bitmap for memory < 16 MB, sets of free page stacks for memory between 16 MB and 4 GB and seperate sets of free page stacks for memory above 4 Gb. Each "set of free page stacks" consists of a pair of stacks for clean pages and dirty pages, for each "page colour" (and/or NUMA memory range). For physical memory management I can have up to 1024 individual free page stacks in addition to the bit map for memory below 16 MB .

This gives me:
- memory detection
- low memory physical memory manager
- middle memory physical memory manager
- high memory physical memory manager
- normal linear memory manager
- PAE linear memory manager
- heap management

Note: "page colouring" is a technique for optimizing cache usage - use google if you're interested.

The general idea is to build a list of RAM areas within the memory detection code, then loop through each page in each RAM area in the list. For each page you'd check if it's actually in use, and if not call the appropriate physical memory manager's "freePage()" function.

You'd also need to be careful when doing this, as some areas may not start or end on a page boundary. For example, you could have RAM from 0x00000000 to 0x0009F800 - the last page (from 0009F000 to 0009FFFF) can't be used.




Cheers,

Brendan

[Poseidon]

You'd also need to be careful when doing this, as some areas may not start or end on a page boundary. For example, you could have RAM from 0x00000000 to 0x0009F800 - the last page (from 0009F000 to 0009FFFF) can't be used.

happened to me a few days ago.. took me 3 days to find this bug ;D

[espenfjo]

Ok, i have now followed a tutorial about paging, http://www.osdever.net/tutorials/paging.php?the_id=43 , i have modified a bit like this:

Code: Select all

// Theese are defined in paging.h
extern unsigned int write_cr3();
extern unsigned int write_cr0();
extern unsigned int read_cr3();
extern unsigned int read_cr0();
unsigned long *page_directory;
unsigned long *page_table;
unsigned int page_list_high;
//Done with paging.h

void set_page_table()
{
        page_directory = (unsigned long *) ((unsigned long) end | 0x4000);
        page_table = (unsigned long *) ((unsigned long) page_directory +4096); // the page table comes right after the page     directory
        printint((unsigned long)page_directory);
        printint((unsigned long)page_table);
        printint((unsigned long) end);
        unsigned long address = 0; // holds the physical address of where a page is
        unsigned int i;
        // map the memory
        for(i=0; i< memsize / 4; i++)
        {
                        page_table[i] = address | 3; // attribute set to: supervisor level, read/write, present(011 in binary)
                        address = address + 4096; // 4096 = 4kb
        };
        page_directory[0] = (int) page_table; // attribute set to: supervisor level, read/write, present(011 in binary)
        page_directory[0] = page_directory[0] | 3;

        for(i=1; i< 1024; i++)
        {
                page_directory[i] = 0 | 2; // attribute set to: supervisor level, read/write, not present(010 in binary)
        };

        write_cr3(page_directory); // put that page directory address into CR3
        write_cr0(read_cr0() | 0x80000000); // set the paging bit in CR0 to 1


}

I'm not sure it works, but it compiles, and the OS starts :O

How should i proceed after this?

[calpis]

Hi all, I have the paging set up. But I didn't want to link it the C0000000 as suggested from Tim Robinson tutorial. I m writing the kmalloc. But I think I am still confuse with the address that I m dealing with.

I think still don't understood how it really works. I was told that paging deals with virtual memory, the pagedirectory index(31to21bit), pagetable index(21to11bit) and offset(11to0). But when I bind the 3 informations, it gives the physical address.

I am working 8MB ram.

I initialized the first directory and page with. setcr3 and cr0. Paging enabled.

I wrote a kind of kmalloc which take a size input. Then I got confuse with what I am doing. Can anyone tell me what I have done in the code below is right or I am just doing something total wrong please. Coz I feel its not right~!
Mycode is here(Its expire in 24hours)
http://rafb.net/paste/results/O3tdoU78.html

Thanks in advance. Don't laugh~! I know is bad programming.
-----------------------------------------------------------------------------

Code: Select all

int page_required;
unsigned long *free_pages_stack = (unsigned long) 0x3FF000;
unsigned long *used_pages_stack = (unsigned long) 0x3FE000;
unsigned int linear_address;
unsigned int used_pages_top;
unsigned int free_pages_top;
unsigned long temp_page;

int i, pto, free_stack_index =0, used_stack_index = 0, first_time = 1 ; //page table offset

[calpis]

Code: Select all

void *kmalloc(int bytes)
{
    page_required = 0;
???///find how many page is needed.
???kprintf(" Bytes is : %d\n", bytes);
???build_page_stack(page_directory[0]);

???kprintf(" The lenght of free page stack: %d   used page stack are: %d\n\n", free_stack_index, used_stack_index);
???kprintf(" Top free page stack: %h   Top used page stack are: %h\n", free_pages_top, used_pages_top);
???

???kprintf(" Top free page stack(3FC000): %h   Top used page stack are(3FD000): %h\n", free_pages_top, used_pages_top);

???if (bytes <= 4096 && bytes > 0) //means bytes how many page its required
???{
??????page_required = 1;
??????
??????temp_page = pop(free_pages_stack);
??????push(used_pages_stack, temp_page);
??????//return (void *) temp_page;
??????return temp_page;
??????kprintf(" Kmalloc temp_page : %d\n", temp_page);
???}
???else if ( bytes % 4096 == 0)
???{
??????page_required = (bytes / 4096);
??????kprintf(" Memory greater than 4KB not supported, Page required B is : %d\n", page_required);
???}else
???{
??????page_required = (bytes / 4096) + 1;
??????kprintf(" Memory greater than 4KB not supported, Page required C is : %d\n", page_required);

???}

???kprintf("Kernel end address : %h\n", kernel_end_addr);
???kprintf("Free page stack start address : %h\n", free_pages_stack);

}

[calpis]

Code: Select all

void build_page_stack(int *page_d)
{
???page_offset = 0;

???int page_directory_index = page_d;
???int page_directory_offset = page_d;
???//check and see if the page_directory is present
???page_directory_offset = page_directory_offset << 20 ; 
???page_directory_offset >>=  20 ; ??????
??????
???if (page_directory_offset != ( page_directory_offset | 1)) //not present
??????kprintf("Directory %d not present. Its to be loaded\n",page_directory_index);
???else //its present
???{
???int page_directory_index = page_d;
???page_directory_index = (page_directory_index >> 12); //page_directory_init_index = 0
???page_directory_index = (page_directory_index << 12 ) - (0x9D000); 
???
???kprintf("build_page_stack parameter is (9D)%d\n",page_directory_index);
???//initialize page stack
???
???//build page table;
???

???for (i = 0; i<1024; i++)
???{
??????
??????page_table_index = page_table[i] >> 12;
??????//kprintf(" PTab Idx:[ %d ]..", page_table_index);
??????page_table_offset = page_table[i] << 20 ; 
??????page_table_offset >>= 20 ; 
??????//kprintf(" PTab Offset:[ %b ]..", page_table_offset);
??????pto = page_table_offset >> 5;
??????if (pto == (pto | 3 ) || pto == ( pto | 1) || pto == ( pto | 2))
??????{????????????//add to used stack
?????????//kprintf("No Linear address.\n");
?????????linear_address = page_binder(page_directory_index, page_table_index, page_offset);
?????????used_pages_top = used_pages_stack[used_stack_index] = linear_address;
?????????used_stack_index++;

??????}???
??????else if (first_time != 1)
??????{???
?????????
?????????//means it is a free page, add to free stack
?????????linear_address = page_binder(page_directory_index, page_table_index, page_offset);
?????????//kprintf("Lin_addr: %h.\n",linear_address);
?????????free_pages_top = free_pages_stack[free_stack_index] = linear_address; 
?????????
?????????//kprintf(" Stacka:%h. stackP:%h\n",free_pages_stack[free_stack_index],free_pages_stack);

?????????free_stack_index++;

??????}else 
??????{
?????????
?????????linear_address = page_binder(page_directory_index, page_table_index, page_offset);
?????????//kprintf("Linear Address is :%h.A.\n", linear_address);
?????????free_pages_top = free_pages_stack[free_stack_index] = linear_address; 
?????????
??????    //kprintf(" Stacka:%h. stackP:%h\n",free_pages_stack[stack_index] ,free_pages_stack);
?????????free_stack_index++;

??????   // kprintf(" Stacka:%h. stackP:%h\n",free_pages_stack[stack_index] ,free_pages_stack);

?????????first_time = 0; //set first time flag to NO
?????????kprintf("\nPage free stack constructed..\n");
?????????//kprintf("\n.0.\n");
?????????
??????}
???
???}
???
???int k;
???for (k=1008; k<1015; k++)
???    kprintf(" Free stack pages:%h. at:%h\n",free_pages_stack[k],free_pages_stack);
???for (k=10; k<15; k++)
???    kprintf(" Used stack pages:%h. at:%h\n",used_pages_stack[k],used_pages_stack);
???//find the used pages on another stack.
???//write an allocator for use later
???
???}
}

unsigned int page_binder( int *directory, int *table, int *offset)
{
???unsigned int bind_directory = directory;
???unsigned int bind_table = table;
???unsigned int bind_offset = offset;
???unsigned int mem_address;

???mem_address = bind_directory << 22;
???//kprintf(" Mem_address:[ %b ] ", mem_address);
???mem_address += bind_table << 12;
???//kprintf(" Mem_address:[ %b ] ", mem_address);
???mem_address += bind_offset;
???//kprintf(" Mem_address:[ %b ] \n", mem_address);
???//kprintf(" Mem_address:[ %h ] \n", mem_address);
???//kprintf(".B.");
???

???return mem_address;
}

[calpis]

Code: Select all

void push(unsigned long *p, unsigned long pages)
{
???if (p == free_pages_stack)
???{
??????kprintf("Free pages top1 %h\n", free_pages_top);

??????free_pages_stack[free_stack_index] = pages;
??????free_pages_top = free_pages_stack[free_stack_index];
??????kprintf("Free pages top2 %h\n", free_pages_top);
??????free_stack_index++;
???}
???else if (p == used_pages_stack)
???{
??????kprintf("Used pages top1 %h\n", used_pages_top);

??????used_pages_stack[used_stack_index] = pages;
??????used_pages_top = used_pages_stack[used_stack_index];
??????kprintf("Used pages top2 %h\n", used_pages_top);
??????used_stack_index++;
???}

}
unsigned long pop(unsigned long *p)
{
???unsigned long temp;
???
???kprintf("Lenght of p is %h\n", p);
???if (p == free_pages_stack)
???{
??????kprintf("Free pages top1 %h\n", free_pages_top);
??????free_stack_index-=2;
??????kprintf("free_pages_stack[free_stack_index] %h\n",free_pages_stack[free_stack_index]);
??????free_pages_top = free_pages_stack[free_stack_index];
??????
??????kprintf("Free pages top2 %h\n", free_pages_top);
??????free_stack_index++;
??????temp = free_pages_stack[free_stack_index];
??????free_pages_stack[free_stack_index]=NULL;
??????return temp;
???}
???else if (p == used_pages_stack)
???{
?????? kprintf("Used pages top1 %h\n", used_pages_top);
?????? used_stack_index-=2;
?????? kprintf("Used_pages_stack[used_stack_index] %h\n",used_pages_stack[used_stack_index]);
?????? used_pages_top = used_pages_stack[used_stack_index];
?????? 
?????? kprintf("Used pages top2 %h\n", used_pages_top);
?????? used_stack_index++;
?????? temp = used_pages_stack[used_stack_index];
?????? used_pages_stack[used_stack_index]=NULL;
?????? return temp;

???}

}

If I annoyed you for the huge message. I am really sorry!

[Warrior]

Hmm this is a good read, wonder why I missed it

Anyway, why do you neglect your [ code ] [ / code ] tags?

[calpis]

hi, sorry I don't understand what you mean by your last post Nelson. ???

Coz I am pretty confuse at the moment with what I have done so far with the memory allocator.

Thanks in advance.

[Kemp]

If you type [ code ] and [ /code ] around things (without the spaces) then it shows it as being code, like this:

Code: Select all

procedure foo(bar:integer);
begin
   showmessage('Why am I using Delphi/Pascal?');
end;

[Crazed123]

Code: Select all

void foo(unsigned int* bar) {
printf("Yeah, why shouldn't all other languages but C be purged from the Net?  Who needs %d languages to use except those stupid people who like them?",*i);
}

[calpis]

did I miss something, coz I really don't have any idea what

Code: Select all

 and 

are... ???

Help...!!! What does it related to

[Kemp]

When you post code you're meant to put it between those so that it's marked as code and nothing in it is accidently used as formatting tags.