For many years, computers typically utilized only one hardware page size: 4 KB. Many software applications were built on assumptions about this page size and relied on its usage. Today, this hardware page size is still commonly in use (such as in x86 architectures), but for performance reasons, larger page sizes are created at the virtual memory level (i.e., within the operating system or software level, as distinguished from the 4 KB hardware pages allocated within physical memory). For example, some operating systems and databases utilize virtual memory pages which span multiple megabytes or even gigabytes.
Generally, an operating system creates a data structure to track each physical memory page utilized by virtual memory. For example, in Linux, each physical memory page frame has a small corresponding data structure (struct page) also stored in memory that is used to track the status of the page frame. These data structures by themselves consume a fixed percentage of the total physical memory in the machine, approximately 1% of a system's physical memory. For example, on a machine with 1TB of memory, about 10 GB of memory is dedicated these data structures. As the amount of physical memory in the system grows, so does the number and size of data structures needed to track the page frames in physical memory. (For simplicity, these data structures tracking physical memory page frames in the kernel are hereinafter referred to as “kernel memory management data structures”).
One ongoing trend in computer systems is an increase in page sizes used within an operating system's virtual memory. The use of larger page sizes within virtual memory provides significant advantages for modern software applications. However, the use of larger page sizes is also likely to waste a larger amount of memory with unnecessary kernel memory management data structures, as the number of base hardware pages assigned to each large page increases. For example, with 16 MB page mappings being used on a system with a 4K base page size, this would mean that there are 4096 hardware pages mapped to every 16 MB virtual memory page. Therefore, 4096 kernel memory management structures would be associated with each virtual memory page. In practice, however, only the information of the first 4K hardware page will be utilized to determine the starting point for the 16 MB page if the 16 MB page is located contiguously in 4K chunks in physical memory. With the use of larger virtual memory page sizes, a significant number of the kernel memory data structures tracking the hardware pages—as many as 4095 in the preceding example—would be redundant and unused.
One workaround to the problem of wasted memory allocated to kernel memory management structures might be to track every single hardware page in a tree structure, adding entries for pages one at a time. Although this would prevent wasting memory on redundant structures, such a tree would be slow and complex to access. Likewise, if all memory was managed in one single flat structure, it would be simple and fast to access, but would be inflexible and waste space for areas not currently in use. To enable performance by efficiently adding memory in the largest amounts possible (such as when hotplugging memory), enhanced techniques for managing existing kernel memory management structures are needed. The techniques utilized within the presently disclosed invention attempt to solve the above-described limitations by reducing the overhead of these memory structures and the need to store redundant memory structures in physical memory.