Sub-page-granular cache coherency using shared virtual memory mechanism

• US 7,680,987 B1
• Filed: 03/29/2006
• Issued: 03/16/2010
• Est. Priority Date: 03/29/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: DesRoches, David W., Clark, Roy
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US11/393,174
• Time in Patent Office: 1,448 Days
• Field of Search: 711/147, 711/207, 711/155
• US Class Current: 711/147
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 2212/656 Address space sharing

Abstract

A technique involves providing access to shared data based on enhanced standard virtual memory mechanisms. Once data from a shared area of memory is moved into primary memory of a first computerized device from a second computerized device, the first computerized device can retain that data in order to shorten the latency of subsequent accesses. Such a technique can be configured to handle shared data at the sub-page-granular level using sparse virtual pages to minimize memory access contention and thus improve the likelihood of quick re-hits. Furthermore, such a technique can be conveniently accomplished through an enhancement to a common page fault handler of an operating system and utilizing atomic remote access support from a standard communications protocol thus alleviating the need to employ more costly and complicated solutions such as inflexible hardware implementations or independent programs that could pose additional design burdens and reliability concerns.

Claims

1. In a computerized device having (i) local physical memory and (ii) a page table which maps a local virtual memory range and a shared virtual memory range to the local physical memory, a method for accessing data, the method comprising:

receiving a request for data and determining whether a page hit or a page fault has occurred based on an examination of virtual memory metadata;

in response to a determined page hit where the data resides in the physical memory, providing access to the data residing in the physical memory;

in response to a determined page fault where the data resides in the physical memory, providing access to the data residing in the physical memory; and

in response to a determined page fault where the data does not reside in the physical memory, moving the data (i) from secondary memory into the physical memory when the virtual address of the request falls within the local virtual memory range and (ii) from another computerized device into the physical memory when the virtual address of the request falls within the shared virtual memory range;

wherein moving the data includes transferring the data from the other computerized device into a shared portion of the physical memory, and updating the page table to indicate that the data now resides in the shared portion of the physical memory;

wherein the method further comprises;

receiving another request for the data and determining whether a page hit or a page fault has occurred based on an examination of virtual memory metadata associated with the virtual address of the other request, and

in response to a determined page hit where the data now resides in the shared portion of the physical memory, providing access to the data now residing in the shared portion of the physical memory;

wherein the shared portion of the physical memory is a set of physical memory pages contiguously divided into equal-sized extents;

wherein providing access to the data residing in the physical memory includes;

when the virtual address of the request falls within the local virtual memory range, mapping the virtual address of the request to a page of the physical memory and enabling the data to be accessed from the page, and

when the virtual address of the request falls within the shared virtual memory range, mapping the virtual address to an extent of the shared portion of the physical memory and enabling the data to be accessed from the extent;

wherein the secondary memory is magnetic disk drive memory; and

wherein moving the data in response to the determined page fault includes;

when the virtual address of the request falls within the local virtual memory range, transferring the data from the magnetic disk drive memory into the page of the physical memory and permitting access to the data from the page, and

when the virtual address of the request falls within the shared virtual memory range, transferring the data from the other computerized device into the extent of the shared portion of the physical memory and permitting access the data to be accessed from the extent; and

wherein there are N computerized devices forming a distributed computer system;

wherein a shared physical memory range is divided into M extents;

wherein each of the N computerized devices is configured to be the home of a respective subset of the M extents in a predefined manner; and

wherein transferring the data from the other computerized device into the extent of the shared portion of the physical memory includes;

performing a set of masked atomic compare and swap operations to acquire, as the data, information which is shared among each of the N computerized devices forming the distributed computer system.

2. A method as in claim 1 wherein a first computerized device is the home of an extent, the first computerized device being responsible for tracking ownership of an extent;

wherein a second computerized device initially holds the information; and

wherein performing the set of masked atomic compare and swap operations includes;

directing the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to obtain the identity of the second computerized device among the N computerized devices,

directing the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner,

performing a remote direct memory access operation to obtain the information from the second computerized device,

directing the third computerized device to perform a masked atomic compare and swap operation on the third computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner, and

directing the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner.

3. A method as in claim 1 wherein a first computerized device is the home of an extent and also initially holds the information;

and wherein performing the set of masked atomic compare and swap operations includes;

directing the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent establishing the second computerized device as the new owner,

performing a remote direct memory access operation to obtain the information from the first computerized device, and

directing the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the second computerized device as the new owner.

4. A method as in claim 1 wherein a first computerized device is the home of an extent;

wherein a second computerized device initially holds the information; and

wherein performing the set of masked atomic compare and swap operations includes;

directing the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to obtain the identity of the second computerized device among the N computerized devices,

directing the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the first computerized device as the new owner,

performing a remote direct memory access operation to obtain the information from the second computerized device, and

directing the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the first computerized device as the new owner.

5. A method as in claim 1 wherein each extent is less than a page in size and has an extent size which is a multiple of a cache line size of the computerized device.

6. A method as in claim 1 wherein each extent is mapped from a unique virtual page in the shared virtual memory range resulting in a sparse shared virtual address range corresponding to the shared physical memory range divided into the M extents.

7. A method as in claim 1 wherein physical memory of each of the N computerized devices includes a same shared physical memory range corresponding to the shared virtual memory space within the distributed computer system.

8. A method as in claim 1, further comprising:

performing a masked atomic compare and swap operation to confirm ownership of a particular extent.

9. A method as in claim 1 wherein the shared physical memory range is contiguous;

and wherein the method further comprises;

dividing the shared physical memory range into the M extents.

10. A method as in claim 1 wherein the distributed computer system formed by the N computerized devices effectively operates as an N-way mirror.

11. A computerized device, comprising:

local physical memory;

an internodal communications interface; and

a controller coupled to the physical memory and the internodal communications interface, the controller having virtual memory related components including (i) a translation lookaside buffer, (ii) a page table which maps a local virtual memory range and a shared virtual memory range to the physical memory, and (iii) a page fault handler, the page fault handler being configured to;

receive a request for data and determining whether a page hit or a page fault has occurred based on an examination of virtual memory metadata,

in response to a determined page hit where the data resides in the physical memory, provide access to the data residing in the physical memory,

in response to a determined page fault where the data resides in the physical memory, provide access to the data residing in the physical memory, and

in response to a determined page fault where the data does not reside in the physical memory, move the data (i) from secondary memory into the physical memory when the virtual address of the request falls within the local virtual memory range and (ii) from another computerized device through the internodal communications interface into the physical memory when the virtual address of the request falls within the shared virtual memory range;

wherein the page fault handler, when moving the data, is configured to transfer the data from the other computerized device into a shared portion of the physical memory, and update the page table to indicate that the data now resides in the shared portion of the physical memory;

wherein the page fault handler is further configured to;

receive another request for the data and determining whether a page hit or a page fault has occurred based on an examination of virtual memory metadata associated with the virtual address of the other request; and

in response to a determined page hit where the data now resides in the shared portion of the physical memory, provide access to the data now residing in the shared portion of the physical memory;

wherein the shared portion of the physical memory is a set of physical memory pages contiguously divided into equal-sized extents;

wherein the page fault handler, when providing access to the data residing in the physical memory, is configured to;

when the virtual address of the request falls within the local virtual memory range, map the virtual address of the request to a page of the physical memory and enable the data to be accessed from the page, and

when the virtual address of the request falls within the shared virtual memory range, map the virtual address to an extent of the shared portion of the physical memory and enable the data to be accessed from the extent;

wherein the secondary memory is magnetic disk drive memory; and

wherein the page fault handler, when moving the data in response to the determined page fault, is configured to;

when the virtual address of the request falls within the local virtual memory range, transfer the data from the magnetic disk drive memory into the page of the physical memory and permit access to the data from the page, and

when the virtual address of the request falls within the shared virtual memory range, transfer the data from the other computerized device into the extent of the shared portion of the physical memory and permit access the data to be accessed from the extent; and

wherein there are N computerized devices forming a distributed computer system;

wherein a shared physical memory range is divided into M extents;

wherein each of the N computerized devices is configured to be the home of a respective subset of the M extents in a predefined manner; and

wherein the page fault handler, when transferring the data from the other computerized device into the extent of the shared portion of the physical memory, is configured to;

perform a set of masked atomic compare and swap operations to acquire, as the data, information which is shared among each of the N computerized devices forming the distributed computer system.

12. A computerized device as in claim 11 wherein a first computerized device is the home of an extent;

wherein a second computerized device initially holds the information; and

wherein the page fault handler, when performing the set of masked atomic compare and swap operations, is configured to;

direct the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to obtain the identity of the second computerized device among the N computerized devices,

direct the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner,

perform a remote direct memory access operation to obtain the information from the second computerized device,

direct the third computerized device to perform a masked atomic compare and swap operation on the third computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner, and

direct the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the third computerized device as the new owner.

13. A computerized device as in claim 11 wherein a first computerized device is the home of an extent and also initially holds the information;

and wherein the page fault handler, when performing the set of masked atomic compare and swap operations from a second computerized device, is configured to;

direct the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent establishing the second computerized device as the new owner,

perform a remote direct memory access operation to obtain the information from the first computerized device, and

direct the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the second computerized device as the new owner.

14. A computerized device as in claim 11 wherein a first computerized device is the home of an extent;

wherein a second computerized device initially holds the information; and

wherein the page fault handler, when performing the set of masked atomic compare and swap operations, is configured to;

direct the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to obtain the identity of the second computerized device among the N computerized devices,

direct the second computerized device to perform a masked atomic compare and swap operation on the second computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the first computerized device as the new owner,

perform a remote direct memory access operation to obtain the information from the second computerized device, and

direct the first computerized device to perform a masked atomic compare and swap operation on the first computerized device to a page table entry associated with a shared virtual address which corresponds to the extent to establish the first computerized device as the new owner.

15. A computerized device as in claim 11 wherein each extent is less than a page in size and has an extent size which is a multiple of a cache line size of the computerized device.

16. A computerized device as in claim 11 wherein each extent is mapped from a unique virtual page in the shared virtual memory range resulting in a sparse shared virtual address range corresponding to the shared physical memory range divided into the M extents.

17. A computerized device as in claim 11 wherein physical memory of each of the N computerized devices includes a same shared physical memory range corresponding to the shared virtual memory space within the distributed computer system.

18. A computerized device as in claim 11 wherein the controller is further configured to:

perform a masked atomic compare and swap operation to confirm ownership of a particular extent.

19. A computerized device as in claim 11 wherein the shared physical memory range is contiguous;

and wherein the controller is further configured to;

divide the shared physical memory range into the M extents.

20. A computerized device as in claim 11 wherein the distributed computer system formed by the N computerized devices is configured to effectively operate as an N-way mirror.

21. A shared memory system, comprising:

multiple computerized devices; and

a communications medium connecting the computerized devices to each other;

each computerized device having local physical memory, an internodal communications interface, and a controller coupled to the physical memory and the internodal communications interface, the controller having virtual memory related components including (i) a translation lookaside buffer, (ii) a page table which maps a local virtual memory range and a shared virtual memory range to the physical memory, and (iii) a page fault handler, the page fault handler being configured to;

receive a request for data and determining whether a page hit or a page fault has occurred based on an examination of virtual memory metadata;

in response to a determined page hit where the data resides in the physical memory, provide access to the data residing in the physical memory;

in response to a determined page fault where the data resides in the physical memory, provide access to the data residing in the physical memory; and

in response to a determined page fault where the data does not reside in the physical memory, move the data (i) from secondary memory into the physical memory when the virtual address of the request falls within the local virtual memory range and (ii) from another computerized device through the internodal communications interface and the communications medium into the physical memory when the virtual address of the request falls within the shared virtual memory range;

wherein moving the data from the other computerized device into the physical memory involves performing a set of masked atomic compare and swap operations to acquire, as the data, information which is distributed among the multiple computerized devices.

22. A shared memory system as in claim 21 wherein each computerized device is configured to:

perform a masked atomic compare and swap operation to confirm ownership of a particular extent.

23. A shared memory system as in claim 21 wherein the shared physical memory range is contiguous;

and wherein each computerized device is configured to;

divide the shared physical memory range into the M extents.

24. A shared memory system as in claim 21 wherein the multiple computerized devices are configured to effectively operate as an N-way mirror.