Small problem about paging

[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?

[egos]

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.

[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?

[egos]

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.

[Jeko]

Where do you save your counters?
And do you save a counter for each page table?

[egos]

Where do you save your counters?

In local kernel area. It's like hyperspace in NT.

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.

[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?

[AJ]

If I'm unmapping a page, how can I decrease the counter of the page table?

Code: Select all

counter--;

[egos]

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.

[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)

[egos]

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).

[Brendan]

Hi,

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...

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

[Jeko]

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!

[Jeko]

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...

[egos]

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).