Linux Virtual Memory Algorithms
Since the early days of computing, there has been a need for more memory than there exists physically in a system. Strategies have been developed to overcome this limitation and the most successful of these is virtual memory. Virtual memory makes the system appear to have more memory than it actually has by sharing it between competing processes as they need it. This sleight of hand is invisible to those processes and to the users of the system. Virtual memory allows large address spaces, fair physical memory allocation, protection and shared virtual memory . The figure below shows a typical memory hierarchy.
As an example consider a model below (Figure 1) that shows a
mapping of the virtual memory to physical memory. 
Figure 1: Abstract model of Virtual to Physical address
mapping.
In this model, both virtual and physical memory are divided up into handy sized chunks called pages. These pages are all the same size, they need not be but if they were not the system would be very hard to administer. Linux on Alpha AXP uses 8 Kbyte pages. Each of these pages is given a unique number; the Page Frame Number (PFN). For every instruction in a program, for example to load a register with the contents of a location in memory, the CPU performs a mapping from a virtual address to a physical one. Also, if the instruction itself references memory then a translation is performed for that reference.
The address translation between virtual and physical memory is done by the CPU using page tables which contain all the information that the CPU needs. Typically there is a page table for every process in the system. Figure 1 shows a simple mapping between virtual addresses and physical addresses using page tables for Process X and Process Y. This shows that Process X's virtual PFN 0 is mapped into memory in physical PFN 1 and that Process Y's virtual PFN 1 is mapped into physical PFN 4. Each entry in the theoretical page table contains information about the virtual PFN, the physical PFN that it maps to, and access control information for that page. To translate a virtual address into a physical one, the CPU must first work out the addresses virtual PFN and the offset within that virtual page. If you make the page size a power of 2, then this can be easily done by masking and shifting. Looking again at Figure 1 and assuming a page size of 8192 bytes (which is hexadecimal 0x2000) and an address of 0x2194 in Process Y's virtual address space then the CPU would translate that address into offset 0x194 into virtual PFN 1. The CPU searches the process's page tables are searched for an entry which matches the virtual PFN. This gives us the physical PFN which we are looking for. The CPU then takes that physical PFN and multiplies it by the page size to get the address of the base of that page in physical memory. Finally, the CPU adds in the offset to the instruction or data that it needs. Using the above example again, Process Y's virtual PFN 1 is mapped to physical PFN 4 which starts at 0x8000 (4 x 0x2000). Adding in the 0x194 byte offset gives us a final physical address of 0x8194. As seen in Figure 1 Process X's virtual PFN 0 is mapped to physical PFN 1 whereas virtual PFN 7 is mapped to physical PFN 0 even though it is higher in virtual memory than virtual PFN 0. Thus the pages of virtual memory do not have to be present in physical memory in any particular order.
The figure below shows a typical schematic of vitrual and physical memory.
As there is much less physical memory than virtual memory the operating system must be careful that it does not use the physical memory inefficiently. One way to save physical memory is to only load virtual pages that are currently being used by the executing program. For example, a database program may be run to query a database. In this case not all of the database needs to be loaded into memory, just those data records that are being examined. Also, if the database query is a search query then the it does not make sense to load the code from the database program that deals with adding new records. This technique of only loading virtual pages into memory as they are accessed is known as demand paging. The figure below shows schematically how the physical and virtually memory addresses are related, are found.
When a process attempts to access a virtual address that is not currently in memory the CPU cannot find a page table entry for the virtual page referenced. For example, in Figure 1 there is no entry in Process X's page table for virtual PFN 2 and so if Process X attempts to read from an address within virtual PFN 2 the CPU cannot translate the address into a physical one. At this point the CPU cannot cope and needs the operating system to fix things up. It notifies the operating system that a page fault has occurred and the operating system makes the process wait whilst it fixes things up. The CPU must bring the appropriate page into memory from the image on disk. Disk access takes a long time, relatively speaking, and so the process must wait quite a while until the page has been fetched. If there are other processes that could run then the operating system will select one of them to run. The fetched page is written into a free physical page frame and an entry for the virtual PFN is added to the processes page table. The process is then restarted at the point where the memory fault occurred. This time the virtual memory access is made, the CPU can make the address translation and so the process continues to run. This is known as demand paging and occurs when the system is busy but also when an image is first loaded into memory. This mechanism means that a process can execute an image that only partially resides in physical memory at any one time.
The figure below shows how the page map or table is used to link the vitual page number with the physical address.
In dealing with the size of the page table parts of the page table generally resides in the virtual address space and parts are brought from the disk to the main memory when required. To this a hashing function is applied to the virtual address so that the page table size need only be the number of physical pages in main memory. The structure of the inverted page table is shown in the figure below.
When the physical memory in the system runs out and a process needs to bring a page into memory then the operating system must decide what to do. It must fairly share the physical pages in the system between the processes running in the system, therefore it may need to remove one or more pages from the system to make room for the new page to be brought into memory. How virtual pages are selected for removal from physical memory affects the efficiency of the system. Linux uses a page aging technique to fairly choose pages which might be removed from the system. This scheme involves every page in the system having an age which changes as the page is accessed. The more that a page is accessed, the younger it is; the less that it is accessed the older it becomes. Old pages are good candidates for swapping. If the page to be removed came from an image or data file and has not been written to then the page does not need to be saved. Instead it can be discarded and if the process needs that page again it can be brought back into memory from the image or data file again. However, if the page has been written to then the operating system must preserve the contents of that page so that it can be accessed at a later time. This type of page is known as a dirty page and it is saved in a special sort of file called the swap file. These unwanted dirty virtual pages are stored on hard disk in the swap file. Accesses to the disk are very long relative to the speed of the CPU and the operating system must juggle the need to write pages to disk with the need to retain them in memory to be used again. The operating system must use an algorithm which fairly swaps out the less used pages of the processes competing for resources. If the swapping algorithm is not efficient then a condition known as thrashing occurs. In this case, pages are constantly being written to disk and then being read back and the operating system is too busy to allow much real work to be performed. If, for example, physical PFN 1 in Figure 1 is being regularly accessed then it is not a good candidate for swapping to hard disk.
When programs are written, programmers take great care to make sure that code is not needlessly repeated. Subroutines to handle particular functions are written and used wherever possible. Subroutines that are useful to many programs are gathered together into libraries. These libraries are shareable so that running programs do not load several copies of the same code into memory. Instead only one copy of the code is loaded and all of the programs share that copy. Virtual memory makes it easy for processes to share memory as all memory accesses are decoded using page tables. For processes to share the same virtual memory, the same physical pages are referenced by many processes. The page tables for each process contain the Page Table Entries that have the same physical PFN. Figure 2 shows two processes that each have physical PFN 1 in their virtual memory map.
Figure 2:Sharing
Physical Memory Between Processes.
The page tables are also used by the CPU and the Operating System to control access to memory. Here the access control information in the page tables is used to check, again on each virtual memory access, that the action is allowable. Traditionally the code in an image is separated out from the data and made read only. In this way the code is protected from corruption by not allowing anything to write to it. Process specific data structures, for example those holding the environment variables, are also protected in this way. A process that attempted to access a page in a way that was not allowed would be terminated with an access violation. The access control information is held in the PTE and is CPU specific. Figure 3 shows the PTE for Alpha AXP.
Figure 3: Alpha AXP Page Table Entry.
The bit fields have the following meanings:
The following two bits are defined and used by Linux:
If you were to implement a system using this theoretical model then it would work, but not particularly efficiently. Both operating system and CPU designers try hard to extract more performance from the system. Apart from making the processors, memory and so on faster the best approach is to maintain caches of useful information and data that make some operations faster. Linux uses a number of memory management related caches: page, buffer and swap caches. One commonly implemented hardware cache is in the CPU; a cache of Page Table Entries. In this case, the CPU does not read the page table directly but instead caches translations for pages is it needs them. These are the Translation Look-aside Buffers and contain copies of the information kept in the operating system's page table. When the reference to the virtual address is made, the CPU will attempt to find a matching TLB entry. If it finds one, it can directly translate the virtual address into a physical one and perform the correct operation on the data. If the CPU cannot find a matching TLB entry then it must get the operating system to help. It does this by raising an exception. In essence this means signalling the the operating system that a TLB miss has occurred. A system specific mechanism is used to deliver that exception to the operating system code that can fix things up. That code fixes things up by generating a TLB entry for the address mapping. When the exception has been cleared, the CPU will make another attempt to translate the virtual address. This time it will work because there is now a valid entry in the TLB for that address. The drawback of using caches, hardware or otherwise, is that in order to save effort Linux must use more time and space maintaining these caches and if the caches become corrupted then the system will crash. Note that the TLB makes the page table faster as is shown in the figure below.
The figure below shows the TLB structure.
It does not make much sense for the operating system itself to run in virtual memory. This would be a ni.htmlre situation where the operating system must maintain page tables for itself. Most multi-purpose CPUs support the notion of a physical address mode as well as a virtual address mode. Physical addressing mode requires no page tables and the CPU does not attempt to perform any address translations in this mode. The Linux kernel is linked to run in physical address space.
The Alpha AXP processor does not have a special physical addressing mode. Instead, it divides up the memory space into several areas and designates two of them as physically mapped addresses. This kernel address space is known as KSEG address space and it encompasses all addresses upwards from 0xfffffc0000000000. In order to execute from code linked in KSEG (by definition, kernel code) or access data there, the code must be executing in kernel mode. The Linux kernel on Alpha is linked to execute from address 0xfffffc0000310000.
However address translation has its problems as will be shown. Consider the figure below. Here one sees that the problem with the physically addressed cached is increased latency. This is not the only problem. The second
is also known as the aliasing problem. The figure below depicts this. Here two vitual pages may correspond to the same physical page which is cached in 2 different location in the L1 cache.
Another case is illustrated in the figure below where there is a problem due to the limitation on the size of the L1 cache.
Thus in order to effectively manage virtual memory the operating system adopts the following memory management strategies: Demand Paging, Swapping, Discarding Pages and Shared Libraries. There has to be a close interaction between the operating system and the CPU in order to correctly utilize virtual memory. Linux runs on a number of very different hardware platforms and so it must separate out the hardware specific code and data structures from the operating specific code and data structures. The operating system always runs from physical memory.
We now take a look at Linux's methods for supporting virtual memory. They are independent from the underlying hardware architecture but they do rely on particular functions being available for every supported processor. Linux assumes that there are three levels of page tables. Each Page Table accessed contains the PFN of the next level of Page Table. Figure 4 shows how a virtual address can be broken into a number of fields; each field providing an offset into a particular Page Table. To translate a virtual address into a physical one, the CPU must take the contents of each level field, convert it into an offset into the physical page containing the Page Table and read the PFN of the next level of Page Table. This is repeated three times until the PFN of the physical page containing the virtual address is found. Now the final field in the virtual address, the byte offset, is used to find the data inside the page. Each platform that Linux runs on must provide translation macros that allow the kernel to traverse the page tables for a particular process. This way, the kernel does not need to know the format of a the entries or how they are arranged.
Figure 4: Three Level Page
Tables.
There are many demands on the physical pages in the system. For example, when an image is loaded into memory the operating system needs to allocate pages. These will be freed when the image has finished executing and is unloaded. Another use for physical pages is to hold kernel specific data structures such as the page tables themselves. The mechanisms and data structures used for page allocation and deallocation are perhaps the most critical in maintaining the efficiency of the virtual memory subsystem. All of the physical pages in the system are described by the mem_map data structure which is a list of mem_map_t structures. Each mem_map_t describes a single physical page in the system. Important fields (so far as memory management is concerned) are:
The free_area structure is used by the page allocation code to find and free pages. The whole buffer management scheme is supported by this mechanism and so far as the code is concerned, the size of the page and physical paging mechanisms used by the CPU are irrelevant. Each element of free_area contains information about blocks of pages. The first element in the array describes single pages, the next blocks of 2 pages and so on upwards in powers of two. The list element is used as a queue head and has pointers to the page structures in the mem_map array. Free blocks of pages are queued here. map is a pointer to a bitmap which keeps track of allocated groups of pages of this size. Bit N of the bitmap is set if the Nth block of pages is free. Figure 5 below shows the free_area structure. Element 0 has one free page (PFN 0) and element 2 has 2 free blocks of 4 pages, the first starting at PFN 4 and the second at PFN 56.
When memory becomes scarce the Linux memory management subsystem must attempt to free physical pages. This function is performed by the kernel swap daemon (kswapd). The name swap daemon is a bit of a misnomer as the daemon does more than just swap modified pages out to the swap file. Its task is to keep the memory management system operating efficiently. The Kernel swap daemon (kswapd kernel init process at startup time and sits waiting for the kernel swap timer to periodically expire. ) is started by the Every time the timer expires, the swap daemon looks to see if the number of free pages in the system is getting too low. Free pages in the system are too low if: (nr_tree_pages + nr_aync_pages < free_pages_high). To do this it follows the vm_next pointer along the list of vm_area_struct structures queued on the mm_struct for the process. Linux does not want too many pages being written to the swap file at the same time so it uses nr_async_pages to keep count of the number of pages currently being written to the swap file. free_pages_low and free_pages_high are set at system startup time and are related to the number of physical pages in the system. If there are enough free pages, the swap daemon sleeps until its timer expires again, otherwise the swap daemon tries three ways to reduce the number of physical pages being used by the system: Reducing the size of the buffer and page caches, Swapping out shared pages, Swapping out or discarding pages. By default, the swap daemon tries to free up 4 pages each time it runs. The above methods are each tried in turn until enough pages have been freed. The swap daemon then sleeps again until its timer expires. The swap daemon looks at each process in the system in turn to see if it is a good candidate for swapping. Good candidates are processes that can be swapped (some cannot) and that have one or more pages which can be swapped or discarded from memory. Pages are swapped only if the data in them cannot be retrieved another way. A lot of the contents of an executable image come from the image's file and can easily be re-read from that file. For example, the executable instructions of an image will never be modified by the image and so will never be written to the swap file. These pages can simple be discarded; when they are again referenced by the process, they will be brought back into memory from the executable image. Once the process to swap has been located, the swap daemon looks through all of its virtual memory regions looking for areas which are not shared or locked. Linux does not swap out all of the swappable pages of the process that it has selected; instead it removes only a small number of pages. . Pages cannot be swapped or discarded if they: are locked in memory, or are shared; there is a separate, explicit, mechanism for swapping out these pages. The swap algorithm uses page aging. Each page has a counter (held in the mem_map_t data structure) that gives the Kernel swap daemon some idea whether or not a page is worth swapping. Pages age when they are unused and rejuvinate on access; the swap daemon only swaps out old pages. The default action when a page is first allocated, is to give it an initial age of 3. Each time it is touched (by the memory management subsystem) it's age is increased by 3 to a maximum of 20. Each time the Kernel swap daemon runs it ages pages, decrementing their age by 1. These default actions can be changed and for this reason they (and other swap related information) are stored in swap_control .
If the page is old (vm_area_struct --> vm_ops), the swap daemon will process it further. Dirty pages are pages which can be swapped out. Linux uses an architecture specific bit in the PTE to describe pages this way (see Figure 3). However, not all dirty pages are neccessarily written to the swap file. Every virtual memory region of a process may have its own swap method (pointed at by shrink_mmap() in /mm/filemap.c) and, in this case, that method is used. Otherwise, the swap daemon will allocate a page in the swap file and write the page out to that device. If the swap file is used, the page's Page Table Entry is replaced by one which is marked as invalid but which contains information about where the page is in the swap file. Whatever the swap method used, the original physical page is made free by putting it back into the free_area . Clean (or rather not dirty) pages can be discarded and put back into the free_area for re-use. The PTEs for these pages are made invalid. These pages will be re-read from the executable image running when the process attempts to access them. As the processes PTEs have been changed, the CPU's Translation Look aside Buffers (TLB) which contain cached internal, CPU readable, copies of PTEs must be updated. This update mechanism is architecture specific. If enough of the swappable processes pages have been swapped out or discarded, the swap daemon will again sleep. The next time it wakes it will consider the next process in the system. In this way, the swap daemon nibbles away at each processes physical pages until the system is again in balance. This is much fairer than swapping out whole processes. Each time the Kernel swap daemon tries to shrink these caches it examines a number of pages in the mem_map page vector too see if any can be discarded from physical memory. The number of pages examined is defined by the priority the code is called at. The blocks of pages are examined in a cyclical manner; a different block of pages is examined each time an attempt is made to shrink the memory map. Each page being examined is checked to see if it is cached in either the page cache or the buffer cache. You should note that shared pages are not considered for discarding at this time and that a page cannot be in both caches at the same time. If the page is not in either cache then the next page in the mem_map page vector is examined. Pages are cached in the buffer cache (or rather the buffers within the pages are cached) to make buffer allocation and deallocation more efficient. The memory map shrinking code tries to free the buffers that are contained within the page being examined. If the all the buffers are freed, then the pages that contain them are also be freed. Pages are queued in the page cache to speed up access to images and data on disk. If the examined page is in this cache, it is removed from the page cache and freed. When enough pages have been freed on this attempt then the kernel swap daemon will wait until the next time it is periodically woken. As none of the freed pages were part of any process's virtual memory (they were cached pages), then no page tables need updating. If there were not enough cached pages discarded then the swap daemon will try to swap out some shared pages. Physical pages that have been shared between processes are swapped out separately from ordinary pages. When the swap daemon attempts to swap out shared pages, it uses shm_segs, a vector of pointers to shmid_ds data structures to look through the shared pages for good candidates for swapping. For each shmid_ds there is a list of vm_area_struct structures which each describe how the virtual memory of a particular process is related to this shared memory area. Just like non-shared memory, the page table entries must be modified to show that the page is in the swap file. However, the page tables of all of the sharing processes must be modified before the page is written to the swap file and freed. The page table entries for each process are found by following the vm_mm pointer in each vm_area_struct structure. handle_mm_fault() in /mm/memory.c points at the level 1 page table for the process.
When a process attempts to access data in page which is not in physical memory a page fault will occur. How this is reported by the CPU is architecture specific and system specific code is used to package the event and hand it off to architecture independent portion of the Linux kernel. Whatever architecture Linux is running on, the page fault handler is called. The relevant Page Table Entry is examined and if it is an invalid entry there are three possible ways of dealing with it:
The selections of a replacement algorithm and allocation policy are the major decisions to make for a paging system. There are may other considerations as well. These include prepaging, page size, inverted page table, program structure, I/O interlock, and real-time processing. An obvious property of a pure demand-paging system is the large number of page faults that occur when a process is started. This situation is a result of trying to get the initial locality into memory. The same thing may happen at other times. For instance, when a swapped-out process is restarted, all its pages are on the disk and each must be brought in by its own page fault. Prepaging is an attempt to prevent this high level of initial paging. The strategy is to bring into memory at one time all the pages that will be needed. Pre-fetching of pages is a flexible version of asynchronous I/O. An application passes a list of address/extent tuples that specify virtual memory regions to that will be accessed in the near future. The kernel makes a best-effort attempt to bring those pages into physical memory. This has several beneficial effects: overlapping the paging I/O with computation, reducing the total run-time of the application, and avoiding the overhead of predictable page faults. Traditional Unix asynchronous I/O is implemented with an asynchronous read system call which initiates the I/O operation and returns immediately. The process is sent a signal when the operation has completed. Much the same effect can be achieved for reading files by using mmap() and initiating pre-paging for the regions of interest. Drawbacks of this approach are: (i) The prepaging system call is advisory only. (ii) The is no indication when pages have arrived. Prepaging may be advantageous in some cases. The question is simply whether the cost of prepaging is less than the cost of servicing the corresponding page faults. It may well be the case that may of the pages brought back into memory by prepaging are not used. Assume that x pages are prepaged and a fraction a of these x pages are actually used (0 < a < 1). The question is whether the cost of the a saved page faults is greater or less than the cost of prepaging (1 - a) unnecassary pages. If a is close to zero, prepaging loses; if a is close to one, prepaging wins.
An application indicates the list of pages to be resolved by making a call to the operating system. The standard Linux C library does not have a wrapper for this system call, so the syscall() interface must be used instead.
The system call arguments are:
#include <unistd.h>
#include <types.h>
#define PREPAGE_MAGIC 42
struct prepage_tuple {
caddr_t addr;
size_t extent;
} prepage_list[NR_ELEMENTS];
int retval;
...
prepage_list[1].addr = 0;
prepage_list[1].extent = 0;
retval = syscall(165, PREPAGE_MAGIC, prepage_list);n
This new system call is implemented as a loadable module for the Linux kernel. While this implementation method results in some duplicated code, it greatly simplifies adding this functionality to an already configured system. To use the module download prepage.c and compile it using the compile command shown below. Load the module into the kernel using insmod prepage.o. For system security reasons you must be 'root' to do this. If the module loads successfully, the system call is now available.
compile-command for prepage.c: "gcc -DMODULE
-D__KERNEL__ -Wall -Wstrict-prototypes -O6 -c prepage.c"
BACK TO MICROWAY APPLICATION NOTE INDEX