Virtual Memory Manager

Goals

1. Managing virtual address space

2. Managing available physical memory

3. Managing VA to PA mapping(page tables)

Virtual Address Space Sharing

The purpose of kernel is to dynamically allocate the maximum available resources to applications. However in case of virtual memory, most of the kernels statically divide to avoid complexity. Ace OS also does it in the same way. It allows only 3 GB of available 4GB to applications.

Kernel sits above (3GB-4GB) all applications and drivers.

Each user application and device driver will get 0-3GB VA range.

Note:

1. Kernel’s max size is only 1GB.
2. The first page (0-4KB) is a guard page and not accessible to kernel/application. It is used to detect null pointer references.

Overall Design

Managing fixed 4GB virtual address space

Managing available physical memory

Important Data Structures

· virtual_map

· vm_descriptor

· vm_unit

· virtual_page

· vmVtoP

· VaMapList

· physical_map

virtual_map

• The sparse virtual address space of a process will be represented in a tree structure called virtual map.
• Architecture depended physical address translation details will be stored in structure called physical_map.
• In x86 architecture physical map will contain pointers to level 1 page table. This in turn can be used in combination with any virtual address to get access to the corresponding physical page

struct virtual_map {

physical_map;

vm_descriptor;

Count of descriptors;

};

vm_descriptor

• Each node in the virtual map tree structure will be called vm_descriptor and it represents a valid va range.
• It is a link between the virtual_map and vm_unit data structure. This structure is needed because vm units are shared and can have different va range in different processes.

struct virtual_descriptor {

Starting VA;

Ending VA;

vm_unit;

My virtual_map;

};
vm_unit

• There will be one vm_unit for every vm_descriptor.
• vm_unit can be of different type – TEXT, DATA, SHARED_DATA, STACK, ANON etc
• A type specific vm_unit will contain information according to it’s type.
  Ex: for an anon vm_unit: swap location, current status…

· It should contain pointer to virtual page list which is used in that vm_unit.

vm units are distinguished only by protection and other attributes. In other words there are no different vm unit types.

Type	Protection	ZeroFill	WriteBack	ReadBack
Text	Execute	No	No	Yes
Data	Read/Write	No	No	No
Stack	Read/Write	Yes	No	No

How backing stores are handled?

FS(file system) should give a unique key for each open file. This key in combination with offset can be used as backing store. FS design should take care of sharing file data.

How to create a valid vm range?

1) Create a valid vm unit

2) Attach it to the process at a specified address

How to create a valid vm unit?

1) Allocate structure

2) Fill attributes (zero, writeback, readback)

3) Set backing store

4) Assign vm unit operation handlers

Handlers:

1) Fault

2) PageOut

3) Remove

struct vm_unit {

vmVtoP_Array;

Count of no of ppl referencing me;

Unit type……ANON or STACK or SHM;

}
virtual_page

· All available physical memory is logically (virtually) divided into small units of PAGE_SIZE. These divisions are identified using physical frame number. For each physical frame number, there will be an associated data structure to represent the physical page called virtual_page.

· These virtual_pages are created during boot time and created as an array called virtual page array.

· “In use” virtual pages are linked using LIST structure. This link is used as LRU list.

· “Free” virtual pages are linked a AVL Tree structure and the key used is size of continuous free virtual pages. This allows faster searching for a particular size. However from the usage it seems no subsystem will require to get a physical page of size more than a default PAGE_SIZE. So this functionality is not required. It can be modified to a LIST. The only known advantage is TLB can be saved by allocating contious pages.

“Free virtual pages region” can be defined as a group of continuous free virtual pages. For a free virtual page region only one entry will be placed in the free tree.

struct virtual_page {

list of virtual_pages belonging to same unit;

Flag to say whether:

Page is free, busy, error, dirty;

Physical address corresponding to this virtual page;

}

vmVtoP

• Any addressable portion of virtual address can be either present in main memory or secondary memory. To keep things simple, a range of addressable portion of virtual address can be either backed by main memory or secondary memory. In most of the OSes the range is minimum size of a physical page supported by architecture.
• This structure is used to find whether the given VA range is mapped to main memory or swap.

struct vmVtoP {

Flag to say InMemory or InSwap

Virtual_page

};
VaMapList

struct VaMap_List {

VA

Pointer to next VA in the linked list

Pointer to L1 page table.

};
Memory Management

It is important to reiterate that kernel manages virtual address space, physical memory, virtual to physical memory translation. Kernel is responsible for updating/modifying page table entries and some hardware circuitry will walk through it.

• Virtual address space is managed using sparse tree data structures.
• Physical memory is managed by using statically allocated vm_page structures.
• Virtual to Physical translations are managed using VaMapList data structures.

Lazy Mapping

Also it is important that Ace kernel does a lazy VA to PA mapping. That is user allocated VAs won’t have any backing physical memory and page table entries until the first access to the VA. The kernel will allocate physical memory and enters corresponding page table entry, on the first access. (The first access is caught by memory management fault).

Functions

1. AllocateVirtualAddress(UINT32 size)

– Allocates contiguous virtual address for the size requested only on page aligned boundary.

2. FreeVirtualAddress(void * VA, UINT32 size);

– Frees the virtual address as requested. It’s assumed that VA is contiguous.

3. Memory Fault Handler()

– Memory fault handler gets the correct vm_unit from virtual_map

– To check if VA range is mapped to main memory or swap, we use VtoP structure. If it points to NULL, then a new virtual page is allocated and corresponding page table entry is updated.

– Or else VtoP will point to some valid swap structure. So it tries to bring the requested memory from swap to main memory and puts the swapped in content into a new allocated virtual page.

Pinning

For some applications the lazy mapping approach is not feasible.

For example: if some drivers wants to do an IO on a memory then it needs physical page before the first access. (Hardware access won’t generate memory management exceptions). Such applications can use pinning. Pinned virtual memory areas are always mapped immediately and always mapped to main memory. That is it won’t participate in swapping.

Functions

1. VA = AllocateVirtualAddress(UINT32 size)
1. Allocates contiguous virtual address for the size requested.
2. virtual_pages = AllocateVirtualPages(int count)
1. Allocates contiguous free <count> number of virtual pages.
3. MapVaToPa(VA, size, virtual_pages);
1. Maps the given VA range with the virtual_page
4. UnmapVa(VA, Size);
5. FreeVirtualPages(virtual_page v, int count);
1. Frees contiguously free virtual pages.

Function List

CreateVmMap()

• This will be called during the creation of a process.

DeleteVmMap()

• This function will be called when a process is terminated
• This function should iterate through all vm_descriptors and delete them

CreateVmDescriptior()

• This will create valid VA range for an applications
• VmUnit should be created before calling this function

DeleteVmDescriptor()

• Removes itself from the map

CreateVmUnit()

DeleteVmUnit()

AllocateVmPages()

FreeVirtualPages()
System Calls

OS standard calls

1. sbrk
2. mmap
3. copyin
4. copyout

Ace Specific

1. VirtualAlloc
2. VirtualUnalloc
   

Physical Memory

Physical memory can have holes, reserved areas, memory mapped IO space and available RAM. Further, a system can have multiple memory areas with different access speeds (NUMA). So the data structure for maintaining physical memory should accommodate all these.

In the above example, the system has two physical memory areas. And the first memory area has three available memory region and the second memory area has four available memory region.

To maintain available memory in one memory region, virtual_page array is used. Each virtual_page in virtual_page array represents a PAGE_SIZE physical memory in the system. Virtual page structure will tell the status of a particular physical memory.

To maintain memory regions in one memory area, physical_memory_region structure is used.

To maintain the memory areas in the system, memory_area structure is used.

To avoid complexity, the following array sizes are fixed at compile time.

Memory area – size 32. That is maximum 32 different memory areas are allowed.

Memory region – size 16. That is maximum 16 different memory regions are allowed.

Virtual Page array is dynamically created on every available memory region at boot time.

Initialization:

The first task is to create virtual page array before the kernel switches to Paged Mode because after initializing paging it will be very difficult to access the memory in scattered way. However, initializing virtual page array before enabling paging will lead to invalid kernel pointer. Because after paging enabled all the pointers (memory references) will have 3GB+ value, so initializing with 1MB+ pointers wont help.

To solve this problem, before enabling paging, only the virtual address mapping for virtual page array and kernel code/data is created. Then paging is enabled after that virtual page array is initialized.

Initialization of virtual page array is done by the function InitMemoryArea() defined in pmem_init.c. This function creates virtual page array for all the physical memory areas doing so it also ensures that these virtual page arrays don’t overwrite the kernel text and data and kernel modules. Up to this point everything is handled as physical memory, to switch to paged mode, the kernel has to create page table entries for its code/data, kernel modules and also for virtual page array. This is done by InitKernelPageDirectory(). This routine creates va to pa mapping for kernel code/data, kernel modules, virtual page array and kernel self map. The VA starts from KERNEL_VIRTUAL_ADDRESS_START and incremented by PAGE_SIZE for each translation. The pa is calculated from the kernel variables so pa to va need not to have some relation.

During initialization physical pages fro page table entries are taken based on the following logic.

1) Go to last physical memory region

2) If the memory region has a page, take the first page and decrement the page count.

3) Go to the next memory region.

Page Directories and Page Tables

User page directories and page tables will reside in user address space (at a predefined space). This approach makes it easy to manipulate the process’s page table entries.

However the above approach makes difficult to access page table of another process. To do so, the only way is to use temporary mapping.

Mapped Page Tables

When kernel wants to insert or remove a Page Table Entry, it has to do the following checks

1) Whether the Page Directory Entry exists

2) Whether the Page Table Entry exists

The problem is processor can access only virtual addresses. But Page Table address that the kernel gets from PDE is a physical address. So to access any page table, kernel has to get the physical address from the PDE then map the address to virtual address and then access using the virtual address.

To avoid the above cumbersome process, page tables are mapped into the virtual address space of the application. This is done by mapping the page directory physical address in one of the PDE.

Note: Page Directory is present and unique for all tasks and kernel has its own page directory which is shared with all tasks. Although the CR3 register has physical address of the current page directory, page directories are has virtual address when a process is created. Kernel page directory’s virtual address is the symbol - kernel_page_directory.