Best way to allocate virtual memory page

[mmurfin87]

I have implemented a free page stack in the manner suggested by Brendan here: http://forum.osdev.org/viewtopic.php?f=15&t=25702. I have quoted the relevant post here:

Stacks can also be done where the "next" field for the linked list is inside the free page itself, and the free pages still don't need to be mapped into any virtual address space.

Kernel has a "physical address for the page on the top of the stack" variable. To free a page at a virtual address:

• kernel stores the current "top of stack" in the page (which is still mapped)
• kernel unmaps the page and flushes the TLB for that page (INVLPG)
• kernel sets the "top of stack" to the physical address from the page table

To allocate a page at a virtual address:

• kernel maps the "top of stack" page into the page table
• kernel flushes the TLB for that page (INVLPG)
• kernel gets the "next" field from the (now mapped) page and puts stores it in it's "top of stack" variable for next time

I am at the point where I am going to allocate the frame pointed to by topOfStack, so I need to pop the next address. To do that, I need to map the physical address pointed to by topOfStack into virtual memory so I can read the address stored there, which will become the new topOfStack value. My question concerns how to get a free virtual memory page to map the physical address to.

At first I thought it would be appropriate to use the kernel heap to allocate a page aligned address, but then I realized any address the heap would return would be already mapped to a physical frame, and that frame would be lost if I remapped it another. I realized that I had no mechanism for allocating virtual memory addresses beyond those managed by the heap.

My next thought was to just search the page directory for a null entry. A proper algorithm should take no more than 1024 + 1024 iterations to complete. I could use one of the unused bits in the page directory entries to store whether the page table, if present, was full. Then I would just iterate over the page directory until I found either an empty table or preferably a page table with a free page left, then iterate through the page table until I found a free page table entry, and return the appropriate address as a free virtual memory address where the frame could be mapped. I wonder if there are no free existing page tables and I must create one using the heap, but the heap is full and thus needs an addition page and frame, then I will be deadlocked and have to panic. That seems avoidable...

Is that the proper way to do this? Is there a better way?

[bluemoon]

I do this by slice the address space into zones, and allocate address space from it - something like multiple heaps.

For your case of mapping such page, the address space needed only in the critical function, is recycled upon the action,
that you may just allocate/hardcode a fixed address per cpu core for that purpose.

[Brendan]

Hi,

Is that the proper way to do this? Is there a better way?

The way it was intended to be used is something like this:

Code: Select all

int allocate_virtual_page(void *virtual_address, int page_flags) {
    address_of_page_table_entry = get_address_of_page_table_entry(virtual_address);
    if( (*address_of_page_table_entry & PAGE_PRESENT_FLAG) != 0) {
        return ALREADY_ALLOCATED;
    }
    *address_of_page_table_entry = physical_address_of_page_on_top_of_free_page_stack | page_flags;
    invalidate_TLB_entry_for_page(virtual_address);
    physical_address_of_page_on_top_of_free_page_stack = *virtual_address;
    return ALLOCATED_OK;
}

int free_virtual_page(char *virtual_address) {
    address_of_page_table_entry = get_address_of_page_table_entry(virtual_address);
    if( (*address_of_page_table_entry & PAGE_PRESENT_FLAG) == 0) {
        return NOT_ALLOCATED;
    }
    *virtual_address = physical_address_of_page_on_top_of_free_page_stack;
    physical_address_of_page_on_top_of_free_page_stack = *address_of_page_table_entry & PAGE_PHYSICAL_ADDRESS_MASK;
    *address_of_page_table_entry = 0;
    invalidate_TLB_entry_for_page(virtual_address);
    return FREED_OK;
}

My question concerns how to get a free virtual memory page to map the physical address to.

In both cases (allocating and freeing virtual pages) you have a virtual address already and don't need to use/find a different temporary virtual address to use.


Cheers,

Brendan

[mmurfin87]

you may just allocate/hardcode a fixed address per cpu core for that purpose.

This was my fallback plan, but I sort of didn't want to "waste" 4kB by keeping it around mostly unused and only for this one purpose. Thanks for the response.

The way it was intended to be used is something like this:

Code: Select all

...

In both cases (allocating and freeing virtual pages) you have a virtual address already and don't need to use/find a different temporary virtual address to use

Ahh, thats exactly the sort of brilliance I was hoping someone would suggest. I was trying to keep physical and virtual memory complete separate, so that there would simply be an AllocateFrame() and a MapPage(page, frame) function. I wanted frame allocation to be completely separated from paging code. When they get intermingled my mind starts to explode, but its getting better with practice.

I wonder if you have any comments about the practicality of keeping them separated like that?

[Brendan]

Hi,

I wonder if you have any comments about the practicality of keeping them separated like that?

You can keep the virtual memory manager's code separated from the physical memory manager's code easily enough, but allocating a physical page ends up being 2 functions ("allocate" and "post_allocate()").

For example:

Code: Select all

int allocate_virtual_page(void *virtual_address, int page_flags) {
    address_of_page_table_entry = get_address_of_page_table_entry(virtual_address);
    if( (*address_of_page_table_entry & PAGE_PRESENT_FLAG) != 0) {
        return ALREADY_ALLOCATED;
    }
    *address_of_page_table_entry = allocate_physical_page() | page_flags;
    invalidate_TLB_entry_for_page(virtual_address);
    post_allocate_physical_page(virtual_address);
    return ALLOCATED_OK;
}

int free_virtual_page(char *virtual_address) {
    address_of_page_table_entry = get_address_of_page_table_entry(virtual_address);
    if( (*address_of_page_table_entry & PAGE_PRESENT_FLAG) == 0) {
        return NOT_ALLOCATED;
    }
    free_physical_page(virtual_address, *address_of_page_table_entry & PAGE_PHYSICAL_ADDRESS_MASK );
    *address_of_page_table_entry = 0;
    invalidate_TLB_entry_for_page(virtual_address);
    return FREED_OK;
}

Code: Select all

// WARNING: This function leaves the free page stack's reentrancy lock in an "acquired" state.

uint64_t allocate_physical_page(void) {
    return physical_address_of_page_on_top_of_free_page_stack;
}
    
// WARNING: This function expects the free page stack's reentrancy lock to be an "acquired" state
//          and will release the free page stack's reentrancy lock.

void post_allocate_physical_page(void *virtual_address) {
    physical_address_of_page_on_top_of_free_page_stack = *virtual_address;
}

void free_physical_page(void *virtual_address, uint64_t physical_address) {
    *virtual_address = physical_address_of_page_on_top_of_free_page_stack;
    physical_address_of_page_on_top_of_free_page_stack = physical_address;
}

Cheers,

Brendan