OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Mar 29, 2024 8:34 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 13 posts ] 
Author Message
 Post subject: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 9:19 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
Hello, I have some problems with my paging code! :)

My page directories and tables (pml4, pdpe, pde, pte) are (if necessary) dynamically expanded, when a page needs to be allocated. If a required directory or table isn't created yet, I allocate some space using kmalloc, and create a new directory or table and add it to my existing structure.

When I need to find a specific page, I walk though this path "PML4 -> PDPE -> PDE -> PTE" using the pointer to the next level, e.g. a PML4 entry points to a PDPE which points to a PDE. The pointers is of cause the physical address to the next level, and this isn't a problem as long as the memory is identity mapped.

The first directories and tables are stored in an identity mapped area, right after the kernel, which is fine because then I can walk though the structure to find my requested page. The problem occurs when I enable paging and the heap. When the heap is enabled, and I need to malloc some space in order to expand my paging structure, it returns a virtual address in the heap, and optionally the physical address. And here is the problem:

When I expand my paging structure, I need to use the physical address to point to the next entry in the structure. But in order to walk though the stucture and modify it, I need the virtual address. This means that I either (a) need a method to convert the stored physical address to a virtual address or (b) have to store a lookup table, so I can lookup what virtual address that matched the physical, which will require even more memory.

I'm using a dymanic structure, because I don't want to support a fixed size of memory. Currently my memory manager is designed to handle 36-bit which equals 64 GB (this can easily be changed to more or less bits). A quick calculation tells me that it will require about 256 MB of memory to store the structures needed to map 64 GB of RAM.

Are there anyone who can suggest a solution to my problem? Should I implement this in another way?
Please ask if there's anything that doesn't make sense, I had a hard time explaing this!

It's the first time I've written code for handling paging and the heap myself, so I'm still learning :)

I have attached my function for dynamically expand the paging structure, when a page is requested. In this code, kmalloc doesn't return the physical address, because the first directories and tables are stored in identity mapped memory. But I can get both the physical and the virtual address by using kmalloc_ap instead.

Code:
pte_t *get_page(uint64_t addr, int make, pde_t *dir)
{
   pde_t *ptr;
   pte_t *page;

   uint32_t pml4 = ((addr >> 39) & 0x1FF);
   uint32_t pdpe = ((addr >> 30) & 0x1FF);
   uint32_t pde = ((addr >> 21) & 0x1FF);
   uint32_t pte = ((addr >> 12) & 0x1FF);

   if(dir[pml4].next_base)
   {
      ptr = (pde_t*)((uint64_t)dir[pml4].next_base << 12); // Pointer to pdpe
   }
   else if(make)
   {
      pde_t *tmp = create_pde();
      dir[pml4].next_base = (((uint64_t)tmp >> 12) & BIT_MASK);
      ptr = tmp;
   }
   else
   {
      return 0;
   }

   if(ptr[pdpe].next_base)
   {
      ptr = (pde_t*)((uint64_t)ptr[pdpe].next_base << 12); // Pointer to pde
   }
   else if(make)
   {
      pde_t *tmp = create_pde();
      ptr[pdpe].next_base = (((uint64_t)tmp >> 12) & BIT_MASK);
      ptr = tmp;
   }
   else
   {
      return 0;
   }

   if(ptr[pde].next_base)
   {
      page = (pte_t*)((uint64_t)ptr[pde].next_base << 12); // Pointer to pte
   }
   else if(make)
   {
      uint64_t tmp = kmalloc_a(sizeof(pte_t)*512);
      memset((void*)tmp, 0, 4096);
      ptr[pde].next_base = ((tmp >> 12) & BIT_MASK);
      page = (pte_t*)tmp;
   }
   else
   {
      return 0;
   }

   return &page[pte];
}

pde_t *create_pde()
{
   pde_t *pde = (pde_t*)kmalloc_a(sizeof(pde_t)*512);
   int i = 0;

   for(i=0;i<512;i++)
   {
      pde[i].present = 1;
      pde[i].write = 1;
      pde[i].mode = KERNEL;
      pde[i].pwt = 0;
      pde[i].pcd = 0;
      pde[i].accessed = 0;
      pde[i].ignored = 0;
      pde[i].next_base = 0;
      pde[i].unused = 0;
      pde[i].nx = 0;
   }

   return pde;
}


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 10:35 am 
Offline
Member
Member

Joined: Wed Oct 25, 2006 5:12 am
Posts: 94
Location: Barcelona España
>are there anyone who can suggest a solution to my problem?
what is your problem?


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 11:51 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
zity wrote:
When I expand my paging structure, I need to use the physical address to point to the next entry in the structure. But in order to walk though the stucture and modify it, I need the virtual address. This means that I either (a) need a method to convert the stored physical address to a virtual address or (b) have to store a lookup table, so I can lookup what virtual address that matched the physical, which will require even more memory.


My problem is, that the pointers in the paging structures (pml4, pdpe, pde) has to be the physical address of the next structure. But when I'm walking though the structure to find a specific page table entry, I need to know the virtual address. Since paging is enabled, I cannot access the structure only knowing the physical addresses.

Of cause, when I'm expading the structure I have both the virtual and the physical address, but the next time I walk though it, only the physical address is stored as the pointer to the next structure, and here I need the virtual address.


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 12:08 pm 
Offline
Member
Member
User avatar

Joined: Sat Nov 29, 2008 1:07 pm
Posts: 550
Location: Throw a dart at central Texas
You are forgetting that where the entry is stored corresponds to the virtual address. I.E. the first page entry of the first page table of the first page directory always corresponds to the range 0x00000000-0x00000FFF (assuming 4K pages) no matter what physical address. This means that all you need to find the virtual address of a specific entry, as long as you know the index of each level, is to do some shifting.

_________________
Owner of Fawkes Software.
Wierd Al wrote:
You think your Commodore 64 is really neato,
What kind of chip you got in there, a Dorito?


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 12:39 pm 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
Firestryke31 wrote:
I.E. the first page entry of the first page table of the first page directory always corresponds to the range 0x00000000-0x00000FFF (assuming 4K pages) no matter what physical address.

Yes, virtually, no matter what physical address it points to..

But I don't understand, how you mean that I can figure out what virtual address that is mapped to a the physical address. I'm not sure if we're understanding each other correctly, or I fail to see how it can be done..


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 12:55 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
You can walk page tables when you need to get the physical address corresponding to a virtual address. The inverse operation is seldom used because physical pages can have an unlimited number of mappings in virtual address spaces. Also, the operation is not used since memory management only goes about what memory can be used, and not where it comes from. Especially in userland there is no particular need for the application to know what physical addresses are used for what bit of usable memory, it does however care about the virtual address since that's where data needs to be written.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Mon Nov 16, 2009 3:18 pm 
Offline
Member
Member

Joined: Tue Apr 15, 2008 6:37 pm
Posts: 191
Location: Gotham, Batmanistan
Easiest way is to recursively map the PML4 page itself. I.e setting one of the PML4 entries to the PML4 page itself. It has no memory overhead and allows you to calculate a virtual address for the table structures themselves without table crawling or excessive metadata. There's a good post on it here.

_________________
Reserved for OEM use.


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Tue Nov 17, 2009 1:01 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
I'm trying to wrap my mind around the self-reference trick, it seems like a smart way of doing it. I don't really understand the concept in all details, though. I fail to see, how you can map a specific virtual address to a physical. I understand that you can map the pml4 to itself, and use it as pml4, pdpe, and pde. But when you get to the pte, I loose the track.

I think I'll need some more time to figure out the concept in my mind :)


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Thu Nov 19, 2009 1:02 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
I've been trying to figure out exactly how the self referece trick works, but I still don't get it. I understand that you can map the last PML4 entry to the PML4 itself, and use the PML4 as both pml4, pdpe, pde and pte. In this way, the PML4 is located at 0xFFFFFFFFFFFF000 right? But I still don't see, how I can map a random physical address to a virtual address? Won't I still need to create new page tables as the need of mapping rises?


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Thu Nov 19, 2009 3:19 am 
Offline
Member
Member
User avatar

Joined: Sun Oct 22, 2006 7:01 am
Posts: 2646
Location: Devon, UK
Hi,

[quote]But I still don't see, how I can map a random physical address to a virtual address? Won't I still need to create new page tables as the need of mapping rises?[quote]

Absolutely, but this system has the advantage that the you know the virtual location of the virtual PTE already. Let me explain the way things flow:

1. An address in your user heap (0x400000 for arguments sake) page faults. The Kernel PFE Handler is entered.
2. The kernel does a quick check - has the faulting address been assigned to the user process? If not, terminate the process. If so, continue with...
3. You know the exact location of the PTE. Because the last entry in your PML4 points to itself, the last 0x800000000 bytes (IIRC - it's been a while since I worked on any 64 bit paging - you can work this out :) ). Represent the page tables. This means that the page table for 0-2MiB will be at 0xFFFFFF8000000000. The page table for 2-4MiB will be at 0xFFFFFF8000001000 etc...
4. You want to map in a physical page from your page frame allocator. Pick the next available physical page and write its address to 0xFFFFF8000002000 (this will be the PTE representing 0x400000-0x401000 - your faulting address).
5. One of two things can now happen. Either:
a) The write was successful in which case you can now return to the faulting user process or
b) There is another page fault, this time relating to the address 0xFFFFFF8000002000. This means that the PT did not exist, you you need a new page Directory. In this case:
6. You basically follow steps 3-5, for the new faulting address. If you get another page fault, you follow steps 3-5, but this time for the new address, which will be relating to the PDPT (all PDPT's are accessible over the last 4MiB of your upper-memory paging structures area) . This is the worst case scenario - where you need to create a new PML4E.
7. The next time your user heap page faults at, say 0x401000, the paging structures will already be present and you'll just find yourself simply writing a PTE for that location.

Because steps 3-5 can be repeated, the actual size of your paging-in function will be pretty small, even though my explanation is very wordy!

HTH,
Adam


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Thu Nov 19, 2009 10:00 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
Thanks AJ, it helped me a lot! :)

I've made some calculations, and got the following memory map of the upper 512 GB, where the paging structures are located:

Code:
Structure   Size (bytes)        Start               End
----------------------------------------------------------------------
PML4        4096                0xFFFFFFFFFFFFF000  0xFFFFFFFFFFFFFFFF
PDPE        2093056             0xFFFFFFFFFFE00000  0xFFFFFFFFFFFFEFFF
PDE         1071644672          0xFFFFFFFFC0000000  0xFFFFFFFFFFDFFFFF
PTE         548682072064        0xFFFFFF8000000000  0xFFFFFFFFBFFFFFFF


I furthermore "created" this function to find the PTE associated with a faulting address: (fault_address / 0x1000) * 8 + 0xFFFFFF8000000000

So if we say that I have a page fault at 0x401000, the PTE is, according to the above function, located at 0xFFFFFF8000002008 which should be correct.

But when there's no page associated with 0xFFFFFF8000002008, we get another page fault. If I use my function to find the PTE associated with this address, it does not work. The function will return 7FFFFFC0000000 + 0xFFFFFF8000000000 which is outside the virtual memory. What am I missing?


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Thu Nov 19, 2009 10:35 am 
Offline
Member
Member
User avatar

Joined: Sun Oct 22, 2006 7:01 am
Posts: 2646
Location: Devon, UK
Hi,

The problem here seems to be adding canonical addresses. As I said - it's a while since I worked with this and it's the end of a very long day, so forgive me if I'm wrong. Because you have divided the faulting address by 0x1000, it should no longer be in canonical form. 7FFFFFC0000000 becomes 0xC0000000.

Oh - and that divide by 0x1000 followed by a multiply by 8 can be optimised with a right shift by 9 places :)

Cheers,
Adam


Top
 Profile  
 
 Post subject: Re: Dynamical expansion of paging structures
PostPosted: Fri Nov 20, 2009 3:13 am 
Offline
Member
Member
User avatar

Joined: Mon Jul 13, 2009 5:52 am
Posts: 99
Location: Denmark
I had some time to try it out this morning, and it seems to be working (after some small adjustments) :) Thanks a lot for all the help!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 13 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot] and 173 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group