Large-Page Optimization in Virtual Memory Paging Systems

• US 20090182976A1
• Filed: 01/15/2008
• Published: 07/16/2009
• Est. Priority Date: 01/15/2008
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Agesen, Ole
• Granted Patent: US 8,352,705 B2
• Time in Patent Office: Days
• US Class Current: 711/207
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/652 Page size control
• CPC Class Codes: G06F 2212/68 Details of translation look-aside buffer [TLB]

Abstract

A computer system that is programmed with virtual memory accesses to physical memory employs multi-bit counters associated with its page table entries. When a page walker visits a page table entry, the multi-bit counter associated with that page table entry is incremented by one. The computer operating system uses the counts in the multi-bit counters of different page table entries to determine where large pages can be deployed effectively. In a virtualized computer system having a nested paging system, multi-bit counters associated with both its primary page table entries and its nested page table entries are used. These multi-bit counters are incremented during nested page walks. Subsequently, the guest operating systems and the virtual machine monitors use the counts in the appropriate multi-bit counters to determine where large pages can be deployed effectively.

Claims

1. A memory management unit of a computer system that employs page tables to map virtual memory pages to physical memory pages, comprising:

a translation lookaside buffer (TLB) for storing a number of mappings of virtual memory pages to physical memory pages; and

a hardware page walker for accessing the page tables when a mapping of a particular virtual memory page to a particular physical memory page is not stored in the TLB, and causing an incrementing of multi-bit counters that are associated with entries of the page tables.

2. The memory management unit according to claim 1, wherein the page tables are arranged in a hierarchical manner, and the hardware page walker accesses page table entries at successive lower levels in the page table hierarchy until a stop bit is encountered.

3. The memory management unit according to claim 2, wherein, for each page table entry that is accessed by the hardware page walker, the hardware page walker increments a multi-bit counter associated with said page table entry unless said multi-bit counter has saturated.

4. The memory management unit according to claim 2, wherein the hardware page walker has an increment enable bit and if the increment enable bit is set, the hardware page walker increments a multi-bit counter associated with a page table entry when said page table entry is accessed and if the increment enable bit is not set, the hardware page walker does not increment a multi-bit counter associated with a page table entry when said page table entry is accessed.

5. The memory management unit according to claim 2, wherein the hardware page walker inserts a mapping of the particular virtual memory page to the particular physical memory page in the TLB.

6. In a virtual memory system having page tables, a method for mapping a virtual memory address to a physical memory address, comprising:

accessing a page table entry of a page table using a first pointer to a physical memory location and a first portion of the virtual memory address;

incrementing a multi-bit counter associated with said page table entry; and

accessing a physical memory address associated with the virtual memory address using a second pointer to a physical memory location and a second portion of the virtual memory address,

wherein the second pointer to the physical memory location is stored in said page table entry.

7. The method according to claim 6, wherein said page table entry includes the multi-bit counter.

8. The method according to claim 6, wherein the page tables are arranged in a hierarchical manner and said page table entry further includes a stop bit that indicates whether the page table entry is pointing to an address of another page table in the page table hierarchy.

9. The method according to claim 8, wherein if the multi-bit counter associated with a page table entry which is not at the lowest level of the page table hierarchy reaches a predetermined threshold:

a large page is allocated in the physical memory;

data from a collection of small pages previously accessed through lower level page table entries associated with said page table entry is copied to the large page in physical memory;

a stop bit of said page table entry is set to 1; and

a page number of the large page in physical memory is stored as a pointer in said page table entry.

10. The method according to claim 9, wherein the predetermined threshold differs depending on where the page table entry resides in the page table hierarchy.

11. The method according to claim 6, wherein an interrupt is generated when the multi-bit counter saturates.

12. The method according to claim 6, wherein each of a plurality of page table entries includes a multi-bit counter which increments when a page table entry associated therewith is accessed.

13. The method according to claim 12, further comprising:

generating an interrupt each time a multi-bit counter saturates; and

allocating large pages based on the interrupts.

14. The method according to claim 12, wherein the multi-bit counter associated with a page table entry, even prior to its saturation, does not increment each and every time said page table entry is accessed.

15. The method according to claim 6, further comprising:

storing a virtual memory page number that includes at least the first portion of the virtual memory address in a first location of a translation lookaside buffer (TLB); and

storing a physical memory page number that includes at least the first portion of the accessed physical memory address in a second location of the TLB that is associated with the first location,

wherein the virtual memory system employs a default page size and the stored virtual memory page number and the stored physical memory page number correspond to a page size that is greater than the default page size.

16. In a virtual memory system of a virtual machine having nested page tables and primary page tables, wherein the nested page tables have multiple page table entries, each of which includes a pointer to a host physical memory location, and the primary page tables have multiple page table entries, each of which includes a pointer to a virtualized physical memory location, a method for mapping a virtual memory address to a host physical memory address, comprising:

retrieving a virtualized physical memory address from a page table entry of one of the primary page tables using a portion of the virtual memory address;

accessing a page table entry of a nested page table using a first pointer to a host physical memory location and a first portion of the virtualized physical memory address;

incrementing a multi-bit counter associated with the page table entry of said nested page table; and

accessing a host physical memory address associated with the virtualized physical memory address using a second pointer to a host physical memory location and a second portion of the virtualized physical memory address,

wherein the second pointer to the host physical memory location is stored in the page table entry of said nested page table.

17. The method according to claim 16, wherein an interrupt is generated when the multi-bit counter saturates.

18. The method according to claim 17, wherein the multi-bit counter associated with the page table entry of said nested page table, even prior to its saturation, does not increment each and every time the page table entry of said nested page table is accessed.

19. The method according to claim 16, wherein the page table entry of said nested page table includes the multi-bit counter.

20. The method according to claim 19, wherein the nested page tables are arranged in a hierarchical manner and page table entries of the nested page tables further include a stop bit that indicates whether the corresponding page table entry is pointing to an address of another nested page table in the nested page table hierarchy.

21. The method according to claim 20, wherein if the multi-bit counter associated with a nested page table entry that is not at the lowest level of the nested page table hierarchy reaches a predetermined threshold:

a large page is allocated in the host physical memory;

data from a collection of small pages previously accessed through lower level nested page table entries associated with said nested page table entry is copied to the large page in the host physical memory;

a stop bit of said nested page table entry is set to 1; and

a page number of the large page in the host physical memory is stored as a pointer in said nested page table entry.

22. The method according to claim 16, wherein page table entries of the primary page tables include a multi-bit counter that is incremented when the corresponding page table entry is accessed.

23. The method according to claim 22, wherein the primary page tables are arranged in a hierarchical manner and page table entries of the primary page tables further include a stop bit that indicates whether the corresponding page table entry is pointing to an address of another primary page table in the primary page table hierarchy.

24. The method according to claim 23, wherein if the multi-bit counter associated with said primary page table entry that is not at the lowest level of the primary page table hierarchy reaches a predetermined threshold:

a large page is allocated in the virtualized physical memory;

data from a collection of small pages previously accessed through lower level primary page table entries associated with said primary page table entry is copied to the large page in the virtualized physical memory;

a stop bit of said primary page table entry is set to 1; and

a page number of the large page in the virtualized physical memory is stored as a pointer in said primary page table entry.

25. The method according to claim 22, wherein an interrupt is generated when a multi-bit counter associated with a page table entry of a primary page table saturates.

26. The method according to claim 25, wherein the multi-bit counter associated with said primary page table entry, even prior to its saturation, does not increment each and every time said primary page table entry is accessed.

27. The method according to claim 16, further comprising:

storing a virtual memory page number that includes a portion of the virtual memory address in a first location of a translation lookaside buffer (TLB); and

storing a host physical memory page number that includes a portion of the accessed host physical memory address in a second location of the TLB that is associated with the first location,

wherein the virtual memory system employs a default page size and the stored virtual memory page number and the stored physical memory page number correspond to a page size that is greater than the default page size.

28. A computer system programmed with an operating system that employs virtual memory and page tables to map virtual memory addresses to physical memory addresses, the computer system comprising a first memory unit including the physical memory, and a second memory unit that provides faster memory access than the first memory unit and storing entries for mapping virtual memory pages of various sizes to physical memory pages, wherein when a page table entry in one of the page tables is accessed, a multi-bit counter associated with said page table entry is incremented by one.

29. The computer system according to claim 28, wherein the multi-bit counter is part of said page table entry.

30. The computer system according to claim 29, wherein the page tables are arranged in a hierarchical manner and said page table entry further includes a stop bit that indicates whether said page table entry is pointing to an address of another page table in the page table hierarchy

31. The computer system according to claim 28, wherein the first memory unit is a random access memory (RAM) and the second memory unit is a translation lookaside buffer (TLB).

32. The computer system according to claim 28, wherein the page tables are arranged in a hierarchical manner and page tables at the bottom level in the page table hierarchy map virtual memory pages of a first size and page tables that are at one level higher than the bottom level map virtual memory pages of a second size that is larger than the first size.

33. The computer system according to claim 32, wherein one of the entries of the second memory unit maps a virtual memory page of the first size and another one of the entries of the second memory unit maps a virtual memory page of the second size.

34. A computer system having hardware resources including a host processor and a host memory, the computer system being programmed with a virtual machine having a virtualized processor and a virtualized physical memory that are operatively coupled to the hardware resources under the control of a virtualization software, wherein the virtual machine is programmed with an operating system that employs virtual memory and primary page tables to map virtual memory addresses to locations in the virtualized physical memory, and when a page table entry in one of the primary page tables is accessed, a multi-bit counter associated with said page table entry is incremented by one.

35. The computer system according to claim 34, wherein the computer system is programmed to map virtualized physical memory addresses to host physical memory addresses using nested page tables, and when a page table entry in one of the nested page tables is accessed, a multi-bit counter associated with said page table entry is incremented by one.

36. The computer system according to claim 35, wherein the nested page tables are arranged in a hierarchical manner and nested page tables at the bottom level in the page table hierarchy map virtualized physical memory pages of a first size and nested page tables that are at one level higher than the bottom level map virtualized physical memory pages of a second size that is larger than the first size.

37. The computer system according to claim 36, wherein the hardware resources further includes a translation lookaside buffer (TLB) that stores entries for mapping virtual memory pages of various sizes to host physical memory addresses.

38. The computer system according to claim 37, wherein one of the entries of the TLB maps a virtual memory page of the first size and another one of the entries of the TLB maps a virtual memory page of the second size.

39. The computer system according to claim 35, wherein said page table entry in one of the nested page tables includes the multi-bit counter and a stop bit that indicates whether said page table entry is pointing to an address of another nested page table in the nested page table hierarchy.

40. The method according to claim 34, wherein the primary page tables are arranged in a hierarchical manner and said page table entry in one of the primary page tables includes the multi-bit counter and a stop bit that indicates whether said page table entry is pointing to an address of another primary page table in the primary page table hierarchy.