Page 1 of 1
Small problem about paging
Posted: Fri Sep 05, 2008 3:08 am
by Jeko
I have a function that map pages, called MemMap
Code: Select all
int __attribute__((__regparm__(3))) MemMap(unsigned int virt, unsigned int phys, unsigned int virt_end, unsigned short attribs)
virt is the virtual start address of the area
phys is the physical start address of the area
virt_end is the virtual end address
attribs are the paging flags for the virtual pages.
The function that unmap pages is MemUnmap
Code: Select all
#define MemUnmap(virt, virt_end) MemMap(virt, 0, virt_end, 0)
It works fine, but I've a small problem. When and how can I deallocate physical frames for page tables that aren't used?
Re: Small problem about paging
Posted: Sat Sep 06, 2008 1:32 am
by egos
Jeko wrote:When and how can I deallocate physical frames for page tables that aren't used?
For non-global regions only (user space & local kernel area): I'm using array of page counters, each of which corresponds to trans page (page table). When counter has is equal to 0, the trans page is unmapped and freed.
Re: Small problem about paging
Posted: Sun Sep 07, 2008 4:09 pm
by Jeko
Maybe I can check every time I unmap pages if the page table can be deallocated (if there aren't entries in the page table). But I find this a slow method...
How do you do in your kernels?
Re: Small problem about paging
Posted: Mon Sep 08, 2008 1:20 am
by egos
Jeko wrote:Maybe I can check every time I unmap pages if the page table can be deallocated (if there aren't entries in the page table). But I find this a slow method...
How do you do in your kernels?
See above. In my kernel when page is unmapped, the counter of trans page, which used for translation that page, is decremented. When counter is decremented to 0, the trans page is unmapped too.
Edit: The counters are ordered by index of trans page.
Re: Small problem about paging
Posted: Mon Sep 08, 2008 9:12 am
by Jeko
Where do you save your counters?
And do you save a counter for each page table?
Re: Small problem about paging
Posted: Tue Sep 09, 2008 1:25 am
by egos
Jeko wrote:Where do you save your counters?
In local kernel area. It's like hyperspace in NT.
Jeko wrote:And do you save a counter for each page table?
Yes, I do, except for global trans pages and trans page, which used for mapping the full 4 mb page table.
Re: Small problem about paging
Posted: Tue Sep 09, 2008 1:42 am
by Jeko
Ok. But how do you save your counters?
If I'm unmapping a page, how can I decrease the counter of the page table?
Re: Small problem about paging
Posted: Tue Sep 09, 2008 1:48 am
by AJ
Jeko wrote:If I'm unmapping a page, how can I decrease the counter of the page table?
Re: Small problem about paging
Posted: Tue Sep 09, 2008 2:35 am
by egos
Jeko wrote:If I'm unmapping a page, how can I decrease the counter of the page table?
The counters are stored separately of the region where trans pages are placed. You are calculating index of counter from the address of freeing page. Then just decrementing the counter and checking it for 0.
Re: Small problem about paging
Posted: Wed Sep 10, 2008 5:58 am
by Jeko
Aren't there any other solutions?
I don't know if yours is enough fast, for each page free I must calculate the index of the counter, decrement it and check if it's zero. Isn't it slow?
However how you calculate the index of the counter? (this was my previous question)
Re: Small problem about paging
Posted: Wed Sep 10, 2008 6:58 am
by egos
Jeko wrote:Isn't it slow? However how you calculate the index of the counter? (this was my previous question)
It's very fast and easy!
Index of counter = page address shr 22 (for user space).
Re: Small problem about paging
Posted: Wed Sep 10, 2008 7:34 am
by Brendan
Hi,
Jeko wrote:Aren't there any other solutions?
There's always more ways... You could leave the page table allocated (good for areas in kernel space that are allocated/freed often), or check if the page table contains all zero (e.g. "repe cmpsd"), or use a mySQL database on the network to keep track, or only allow 4 MiB areas to be allocated and freed, or...
Jeko wrote:I don't know if yours is enough fast, for each page free I must calculate the index of the counter, decrement it and check if it's zero. Isn't it slow?
However how you calculate the index of the counter? (this was my previous question)
Doh - Ego's beat me to it...
Anyway, here's an example of freeing a page (for "plain 32-bit" paging):
Code: Select all
;Input
; ebx Linear address of page to free
free_page:
mov eax,0xFFFFF000 ;eax = mask
and ebx,eax ;Make sure linear address of page to free is aligned
mov esi,ebx ;esi = linear address of page to free
mov edx,ebx ;edx = linear address of page to free
shr esi,22 ;esi = index into page directory mapping
shr edx,12 ;edx = index into page table mapping
test dword [page_directory_mapping + esi * 4],1 ;Is the page table present?
je .error_not_present ; no, can't free a page that isn't present
test dword [page_table_mapping + edx * 4],1 ;Is the page present?
je .error_not_present ; no, can't free a page that isn't present
and eax,[page_table_mapping + edx * 4] ;eax = physical address of page to free
call free_physical_page ;Free the physical page
mov dword [page_table_mapping + edx * 4],0 ;Clear the page table entry
invlpg [ebx] ;Invalidate the page in the TLB
sub [array_of_counters + esi * 2],1 ;Reduce the number of pages using this page table
jne .done ;Skip the rest if the page table is still in use
mov eax,[page_directory_mapping + esi * 4] ;eax = page directory entry
mov dword [page_directory_mapping + esi * 4],0 ;Clear the page directory entry
invlpg [page_table_mapping + edx * 4] ;Invalidate the area in the page table mapping
and eax,0xFFFFF000 ;eax = physical address of page table
call free_physical_page_in_EAX ;Free the physical page that was used for the page table
.done:
ret
Cheers,
Brendan
Re: Small problem about paging
Posted: Wed Sep 10, 2008 7:40 am
by Jeko
egos wrote:Jeko wrote:Isn't it slow? However how you calculate the index of the counter? (this was my previous question)
It's very fast and easy!
Index of counter = page address shr 22 (for user space).
Ah ok!
So:
Code: Select all
if(counter[virt_addr>>22]-- == 0) {
//DEALLOCATE THE PAGE TABLE
}
But for example for the address 0xB0000000 the counter's index is 0xFFFFFEC0... How much this counter must be big?
Thanks for the help!
Re: Small problem about paging
Posted: Wed Sep 10, 2008 7:45 am
by Jeko
Brendan wrote:Jeko wrote:Aren't there any other solutions?
There's always more ways... You could leave the page table allocated (good for areas in kernel space that are allocated/freed often), or check if the page table contains all zero (e.g. "repe cmpsd"), or use a mySQL database on the network to keep track, or only allow 4 MiB areas to be allocated and freed, or...
Which is the faster method between keeping a counter and check if the page table contains all zero?
Can you make example optimized code to check if the page table contains all zero?
I think my code for doing this is really slow:
Code: Select all
// Check if it is possible to deallocate the frame
// of the page table used to map the address
// So let's examine all entries in the page table
// where the address is mapped.
for (temp = PAGE_DIR_ALIGN(vir_addr); temp < PAGE_DIR_ALIGN_UP(vir_addr); temp += PAGE_SIZE)
if ((*ADDR_TO_PTE(temp) & P_PRESENT) == P_PRESENT)
return;
// No PTEs found... deallocate the page table!
EDIT: Or maybe I can deallocate page tables only when a task dies, starting from its PDBR...
Re: Small problem about paging
Posted: Thu Sep 11, 2008 1:39 am
by egos
Jeko wrote:But for example for the address 0xB0000000 the counter's index is 0xFFFFFEC0... How much this counter must be big?
Take the calculator. 0xB0000000 shr 22 = 0x2C0. The max value of counter is 1024. It is the number of pages in the 4 mb address range (i.e. the number of entries in the trans page).