| Now that we have examined the various components of the lmv, we must put it all together and consider the two tasks of memory allocation and memory freeing. Figure 6-18 ties the structures into a single view. Figure 6-18. Physical Memory Allocator 
Allocating Memory The kernel routine allocate_page() is responsible for the allocation of physical pages of a specific requested size. It works with the views, pools, and ponds. The basic algorithm works as follows: An allocation is attempted from the uncached ponds of all pools for the desired size (or larger). The initial pool is determined by CHOOSE_VIEW_AND_POOL(), which is keyed to the underlying system architecture. If the initial pool can not fill the request, NEXT_POOL_TO_TRY() is called to select the next victim. If the request is for an equivalently mapped page, the processor's own lmv EQUIV_MAPPED_POOL is tried first; then the other lmv EQUIV_MAPPED_POOLs are tried. If the request is for a nonequivalently mapped page, we first try our own lmv NON_EQUIV_MAPPED_POOL followed by the other lmv NON_EQUIV_MAPPED_POOLs, and then the EQUIV_MAPPED_POOLs are tried. If all uncached ponds of all pools have been tried, then we try the cached ponds of all the pools. If we still can't find the needed page size, we step the request down to the next smaller page size and repeat the above steps. If we still can't make the requested allocation and the call doesn't permit blocking, then we return a NULL and let the thread handle the failure. If blocking is allowed, the thread will be put to sleep after tickling the paging daemon and the unhash daemon.
Freeing Memory Freeing memory when you have multiple free lists and the added challenge of coalescing pages to form larger page_groups has complicated this part of the process. Figure 6-19 illustrates the concept of multiple free lists. Figure 6-19. Free Lists Revisited 
The kernel routine used for this daunting task is freepfd(). The first rule for freepfd() is to decrement the pf_use in the page's pfdat structure. If the pf_use is now a zero, the physical page is ready for assignment to a free list following the cleanup of its hash, region, and pfn_to_virt table entries. The routine freeup_page() is called to assign the page to the appropriate free pool. Finally, the global free memory count, freemem, is incremented following any coalescing that may occur.
Coalescing Free Pages As pages are placed on free lists, we must check if their neighbors are also free and if they can be combined to form larger sized free pages. This process is called page coalescing. Pages next to each other in the physical memory map are called buddies, and the routine responsible for coalescing pages is place_on_freelist(). The freeup_page() routine calls place_on_freelist() and passes it the physical page frame number it is trying to free up. Find the page's buddy. This is a simple task of changing the bit corresponding to the page's current size and checking whether it is free. Confirm that the page to be freed and its buddy are in the same pond. Coalescence is only attempted for pages in the cached pond if at least one-third of the pond's pages are currently free. In the case of uncached pages, coalescence is always attempted. The resulting page (coalesced if possible) is then placed at the end of the appropriate free list.
|
