physical mm

[Freanan]

I decided to open a new thread for this, although it more or less belongs to the "enabling paging" thread...

I had asked there how it would be possible to swap out or delete the pageframe-stack (when it is empty) and use it's physical memory for other purposes.
Now i wrote some physical memory manager - i just wanted to ask if i got the idea right and if this is how to do it...

When the stack is empty (sp=-1) and someone still wants to allocate a page, i hand him the adress of the stack and set sp to -2 to indicate that not even the stack itsself is available any more.
When the stack was deleted and someone frees memory i first use this memory to set up a new pagestack...

Code: Select all

unsigned long* page_stack;  //"stack"
long page_sp;               //and stack pointer for pageframes


//!!! maybe it would safe space to use the numbers of the pageframes 
//!!! instead of their adresses, multiplying/dividing them by 4096 for use as adress


//How many pageframes are left?
unsigned int num_pageframes()
{
   //add 1 to sp because sp is an index and not a counter
   //add 1 more to sp because we can still use the mem for the stack itsself
   return page_sp+2;
};


//Allocate a pageframe. If none are left allocate the pageframe the stack is in.
unsigned long alloc_pageframe()
{
   unsigned long adress;
   
   //no page left - give away the space for the stack
   if(page_sp==-1)
   {
      page_sp=-2;
      return (unsigned long)page_stack;
   }
   
   //not even the space of the table left - out of memory 
   //0 is used as retvalue, as everybody knows that 0x00000 is reserved
   else if(page_sp==-2)
      return 0;     
   
   //else pop some adress
   else
   {
      adress=page_stack[page_sp];
      page_sp--;
      return adress;
   };
};


//Free pageframe starting at adress. If the pagestack was deleted, create a new stack at the given adress instead
void free_pageframe(unsigned long adress)
{
   //If the stack was empty and therefore deleted, create a new stack for the adress
   if(page_sp==-2)
   {
      page_stack=(unsigned long*)adress;
      page_sp++;
   }
   
   //Else just push the freed adress to the stack
   else
   {
      page_sp++;
      page_stack[page_sp]=adress;
   };
};


//setup the physical memory manager before first use
void setup_physmm(mbinfo* mbi)
{
   //use some page-aligned adress 
   page_stack= (unsigned long*) 0x9C000;
   //no free pageframes present
   page_sp=-1;
       
   //read free pages using the multiboot memory map 
   //!!!(here i have to add code to also reserve kernel regions!)
   puts("Reading multiboot memory map.\n");
   if(mmap_to_pagestack(page_stack, mbi)==false)
      puts("Failed!\n");
};

Thanks!

EDIT: i also missed out to reserve new pages when the stack gets larger then one page and needs more space.

more EDIT:
There is another problem: When the pagestack is larger then one page... how do i ensure that it gets as much continuous physical pages as it needs?
What if the page after the first one is already in use by some client?
Or is this done by virtual memory, ie mapping the pages the stack needs in a way that the stack thinks they were continuous - but then, wasn't physical memory management supposed to be one layer below paging?

[AR]

Physical management is below paging, but the management data is stored on top of paging (ie. in the virtual memory). It does not need contiguous physical memory as the virtual memory will make it think that the stack is contiguous. [The manager only manages the physical memory, it doesn't live in the physcal memory though (you cannot avoid going through the MMU)]

This will require some back mapping to the virtual manager to map and unmap the virtual pages (The page stack can POP from itself, call the virtual manager's map. Or in reverse it can PUSH and call unmap).

I'll have to review the logic later though.

[Freanan]

Okay, so i could have my pagestack at a fixed virtual adress and map all the memory it needs so that it thinks it was contigous...
So i would have to add code that maps the newly created pagestack in the right way in free_pageframe and setup_physmm above.

But.. if the physical memory manager lives in virtual memory as well - how can it hand out physical adresses when called for?
Virtual adresses consist of three parts and are mapped to who-knows-where while physical adresses are just linear numbers that are not mapped at all.
Would i have to add code to free_pageframe that first reads the physical location of the adress to be freed from the pagetable and then push this adress to the stack?

This is very confusing.
I also wonder why i am able to use linear pointers like 0xb8000 for the video memory when i am using paged memory.

[AR]

I'll repeat what I said to "chaisu chase":

page_directory[1]->page_table[3]
Equation: (page_dir_index * 0x400000) + (page_table_index * 0x1000)
So for the above example: 1 * 0x400000 + 3 * 0x1000 = 0x403000 Virtual

The manager doesn't need to touch physical memory to carry out it's task, it could be handing out pointers from an array of NULLs as far as it cares, the values that it hands out do not make any difference to the manager itself. There is nothing stopping you from going "pstack_push(1); pstack_push(9); printf("%d, %d", pstack_pop(), pstack_pop());", it does not interact with the physical memory itself, only the virtual manager actually touches and maps the physical memory.

To access 0xB8000 you would have something like page_dir[1023]->page_table[1023] = 0xB8003, then anything you write at 0xFFFFF000 will be put at 0xB8000 physically.

[Freanan]

Thank you! That clarifies much.
So actually i only have to rewrite my code at the point where i free the space in which the emptied stack resides, so that not the virtual, but the physical adress is pushed (and i have to allocate and map more virtual memory when the stack needs it).

EDIT: So my code, still without reserving/freeing new pages for the stack if needed, should look rather like that:

Code: Select all

unsigned long* pageframestack=SOME_CONSTANT_VIRTUAL_ADRESS;

unsigned long alloc_pageframe()
{
   if(page_sp==-2)
      return 0;
   else if(page_sp==-1)
   {
      page_sp--;
      return virt2phys(pageframestack);
   };
   else
   {
      page_sp--;
      return pageframestack[page_sp+1];
   };
};


void free_pageframe(unsigned long adress)
{
   if(page_sp==-2)
   {
      map(pageframestack,adress);
      page_sp++;
   }
   else
   {
      page_sp++;
      pageframestack[page_sp]=adress;
   };
};

Did i get it right this time?
Thanks for your patient explanations anayway !

[Pype.Clicker]

added to our collection of MM algorithms in the FAQ

[AR]

I can't see anything obviously wrong with it, it should work fine.

[Freanan]

Thanks so far!
Here is my function to translate a virtual adress into a physical one by extracting the dir-index and table-index from the adress and looking them up in page directory and page table.
I am posting it because it might be a helpfull addition as this thread is in the wiki now, and also because i am a bit awkward about that bit-manipulation stuff and would like to know if i did it right.

Code: Select all

//Look up to which physical adress the virtual one is mapped
unsigned long virt2phys(unsigned long virtual)
{
   unsigned long table= virtual & 0xffc00000; //ten 1's, 22 0's in binary             --> only first 10 bits
   unsigned long entry= virtual & 0x003ff000; //ten 0's, 10 1's and 12 0's in binary  --> only middle 10 bits

   //shift to ge the right numbers
   table >> 22; 
   entry >> 12;
   
   unsigned long tab = (unsigned long) page_dir[table] & 0xffc00000; //remove controll bits
   unsigned long* tabpointer= (unsigned long*)tab;
   return tabpointer[entry] & 0xffc00000;                            //remove them here as well
};

[AR]

There are some problems with that, try this:

Code: Select all

//Look up to which physical adress the virtual one is mapped
unsigned long virt2phys(unsigned long virtual)
{
   unsigned long table= (virtual & 0xffc00000) >> 22; 
   unsigned long entry= (virtual & 0x003ff000) >> 12; 
   
   unsigned long *tabpointer = (unsigned long*) (page_dir[table] & 0xfffff000);
   return tabpointer[entry] & 0xfffff000;
}

[Freanan]

Okay, i noticed.
I wrote a function to output unsigned long numbers which works fine and used it to output the physical adress belonging to 0x00000
- that should be 0x00000 again, as i set up the memory corresponding to the first pagetable to point to itsself.
But the result is some largish number.
I guess i will use my number-output function to test every step in the virt2phys function...

[Freanan]

I finally managed to get some more time for coding (or debugging):
The output of my
Table and entry are both 0, which is right.
Tabis 0 too, which is wrong, as my table is somewhere farther up in memory.
Maybe a problems with the types of my variables..?

@AR: Your status-bit-clearing-bitmask is clearing the first twenty bits instead of the first ten bits as in my code... This might be the problem (i'll look it up). Still you write there was something wrong with the code that you posted as well..
And, the error occurs in the line where tab is defined, which lies above..

[AR]

"0xF = 1111" in binary, 0xFFFFF000 means "take everything except the first 12bits". Note that the bits that are ON (ie. 1) are the ones that are kept, the ones that are OFF (ie. 0) are 'deleted'.

I didn't change the table/entry variables, I merely compacted them into 2 lines instead of 4.

The difference between tab and tabpointer isn't significant enough to require it's own intermediate variable so I merely compacted that as well, there may be a problem with operation order, you may want to wrap the operation in brackets:

Code: Select all

unsigned long *tabpointer = (unsigned long*) (page_dir[table] & 0xfffff000);

[Freanan]

Thanks, your code works fine

Now i will add code to add and delete new virtual pages for the stack, when needed...

I abandoned the idea of saving only the indexes of the free physical pages in the stack, because if i am not wrong it brings no usable decrease in size.

[AR]

I abandoned the idea of saving only the indexes of the free physical pages in the stack, because if i am not wrong it brings no usable decrease in size.

Can you define this a bit more thouroughly? The free page stack is meant to store pointers to the currently unused physical pages. Basically the idea here is that you can have something like:

Code: Select all

page_dir[1]->page_tab[1] = freestack_pop() | 0x3;

[Freanan]

Yes, i understand what you mean.
The "idea" that i had, was not to store the physical starting adresses of free pages, but their "numbers", ie starting_adress/4096, hoping to need a smaller integer-type and safe space that way.
But when i calculated how many bit those numbers would need, i found out that i would still have to use unsigned long - integers for the stack.

I changed the free and alloc funtions now to use (or free) new physical pages for the stack, when needed.
I think logically my code is right, but i am not quite sure, if my pointer arithmetic is right:
Since the stack consists of dwords and a dword = 4 bytes, the stack needs a new page, when page_sp has reached a multiple of 4096/4=1024. Similiar calculations are in the alloc and free functions to calculate virtual adresses for the new/deleted page.

I also wonder if there is a better solution than using the boolean variables f and a, as in the code below.

These are the new alloc and free functions:

Code: Select all

unsigned long alloc_pageframe()
{
   static bool f;
   unsigned long adress;
   
   //not even the space of the table left - out of memory 
   //0 is used as retvalue, as everybody knows that 0x00000 is reserved
   if(page_sp==-2)
      return 0;     
   //give away space from the stack, if a stackpage becomes available now
   else if((page_sp+1)%1024==0 && f==false)
   {
      //next call, page_sp will not have changed, still we do 
      //not want to re-allocate the stackpage, but act as in "else"-case
      f=true;
      
      return physical((unsigned long)page_stack + ((page_sp+1)*4));
   }
   //else pop some adress
   else
   {
      f=false;
      //do the pop and return the adress
      adress=page_stack[page_sp];
      page_sp--;
      return adress;
   };
};


void free_pageframe(unsigned long adress)
{
   static bool a;
   
   //If we need more space for the stack, get another pageframe for it
   if((page_sp+2)%1024==0 && a==false)
   {
      //next call, page_sp will be unchanged, yet we do not
      //want to map another pageframe, but act as in "else"-case
      a=true;
      
      //use the given adress for the new stackpage. Do not free it.
      set_pagetableentry(page_sp+2)/1024, adress, stack_table, 3);
   }
   //Else just push the freed adress to the stack
   else
   {
      a=false;
      //do the push
      page_sp++;
      page_stack[page_sp]=adress;
   };
};

My post might be a bit unorganized and weird.
If the code fails to explain the parts my language missed as well, just complain