Transparent address remapping for high-speed I/O

• US 6,725,289 B1
• Filed: 04/17/2002
• Issued: 04/20/2004
• Est. Priority Date: 04/17/2002
• Status: Expired due to Term

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Waldspurger, Carl A., Nelson, Michael, Govil, Kinshuk
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): NGUYEN, TANH Q
• Application Number:
  US10/124,783
• Time in Patent Office: 734 Days
• Field of Search: 718/1, 710/2, 710/3, 710/4, 710/8, 710/9, 711/1, 711/2, 711/3, 711/100, 711/152, 711/165, 711/200, 711/202, 711/203, 711/205, 711/206, 711/207, 711/208, 711/209, 711/218, 711/220, 711/221
• US Class Current: 710/9
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]

Abstract

A subsystem that is able to address a second memory region initiates I/O requests directed to a device that is able to address a first memory region that is different from the second memory region. Requests for memory are mapped at least once, for example from virtual to physical page numbers. The I/O requests are conditionally remapped to pages in the first region as a function of how often they are involved in the I/O operations and would normally otherwise need to be copied. Remapping may also be made conditional on a function of availability of memory in the first region. In a preferred embodiment of the invention, the I/O requests are initiated by a subsystem within a virtual machine, which runs via an intermediate software layer such as a virtual machine monitor on an underlying hardware and software platform. A typical application of the invention is DMA.

Claims

1. A method for performing an input/output (I/O) operation in a computer between an I/O-initiating subsystem and a device through a memory, in which:

the memory is arranged into portions that are separately addressable using first identifiers;

for the I/O operation, the device accesses a device-accessible space of the memory;

the subsystem addresses I/O requests to a device-inaccessible space of the memory using second identifiers;

the method comprising the following steps;

initially mapping the second identifiers to respective first identifiers that identify portions of the memory in the device-inaccessible memory space; and

for any I/O request that meets a remapping criterion, remapping the corresponding second identifier to one of the first identifiers that identifies a portion of the memory in the device-accessible space of the memory.

2. A method as in claim 1, in which the I/O operation is output of a data set from the subsystem to the device, the method further comprising the following step:

for any I/O request that meets the remapping criterion, and for as long as the I/O request meets the remapping criterion, creating and maintaining a single copy of the data set in a buffer in the device-accessible space of the memory and remapping the I/O request to the single copy.

3. A method as in claim 2, further comprising, for any I/O request that fails to meet the remapping criterion, creating a new copy of the data set in the buffer upon each instance of the I/O request.

4. A method as in claim 2, further comprising the following step:

for each second identifier that is currently mapped into the device-accessible space of the memory and that meets a remapping condition, again mapping the second identifier into the device-inaccessible space of the memory.

5. A method as in claim 4, further including the step of randomly selecting each second identifier that is to be again mapped into the device-inaccessible space of the memory, whereby the remapping condition is that each respective second identifier page is one of those that has been randomly selected.

6. A method as in claim 4, further comprising the step of freeing for reallocation the portion of the memory in the device-accessible space to which the second identifier had previously been remapped.

7. A method as in claim 1, in which the I/O operation is input of a data set from the device to the subsystem, the method further comprising the following step:

for any I/O request that meets the remapping criterion, storing the data set from the device in the device-accessible space of the memory at a location identified by the first identifier to which the second identifier has been remapped.

8. A method as in claim 1, further comprising the step of calculating an activity score for at least a subset of the second identifiers used by the subsystem in an I/O request during a current measurement period, in which the remapping criterion is that the activity score exceeds a high-activity threshold value.

9. A method as in claim 8, in which the activity score is a function of the frequency of use in I/O requests by the subsystem of the respective second identifier.

10. A method as in claim 9, in which the activity score is a function of the frequency of use in I/O requests by the I/O-initiating subsystem of the respective second identifier over both a current activity interval and over at least one previous activity interval.

11. A method as in claim 10, in which the function is a weighted sum.

12. A method as in claim 8, further comprising the following step:

for each second identifier that is currently mapped to one of the first identifiers identifying a portion of the memory in the device-accessible space of the memory and that meets a remapping condition, again mapping the second identifier to a first identifier identifying a portion of the memory in the device-inaccessible space of the memory.

13. A method as in claim 12, further including the step of randomly selecting each second identifier that is to be again mapped to a first identifier identifying a portion of the memory in the device-inaccessible space of the memory, whereby the remapping condition is that each respective second identifier page is one of those that has been randomly selected.

14. A method as in claim 12, in which the remapping condition is that the activity score of each respective page falls below a low-activity threshold during a most recent activity interval.

15. A method as in claim 12, further comprising the step of freeing for reallocation the portion of the memory in the device-accessible space to which the second identifier had previously been remapped.

16. A method as in claim 8, further comprising the following steps:

measuring a value of scarcity of portions of the memory in the device-accessible space that are available for allocation; and

adjusting the remapping criterion as a function of the value of scarcity.

17. A method as in claim 16, in which the step of adjusting the remapping criterion as a function of the value of scarcity comprises calculating the high-activity threshold value according to the value of scarcity.

18. A method as in claim 1, further comprising the step of evaluating a current cost of remapping for the current I/O request, whereby the remapping criterion is that the current cost is less than a cost threshold.

19. A method as in claim 1, is which the I/O-initiating subsystem is included within a guest system that runs on a host platform, the method further comprising the following steps:

within the guest system, remapping I/O requests issued by the I/O-initiating subsystem from third identifiers to the second identifiers;

the step of remapping the second identifiers to the first identifiers remaining transparent to both the I/O-initiating subsystem and the guest system.

20. A method as in claim 19, in which:

the guest system is a virtual machine;

remapping of the third identifiers to the second identifiers is done in a guest operating system within the virtual machine;

remapping the second identifiers to the first identifiers is done in an intermediate software layer between the guest system and the host platform;

the I/O requests are directed to a virtual device through a virtual memory within the virtual machine, whereby the third identifiers address the virtual memory; and

the first identifiers address a hardware memory.

21. A method as in claim 20, in which the I/O operation uses direct memory access (DMA).

22. A method as in claim 1, in which the memory portions are pages, and the first and second identifiers are page numbers.

23. A method as in claim 1, in which the step of remapping further comprises remapping second identifiers that identify contiguous memory portions such that the first identifiers to which they are remapped correspond to contiguous portions of the device-accessible space.

24. A method for performing an input/output (I/O) operation in a computer between an I/O-initiating subsystem and a device via a device-accessible space of a memory, in which:

the memory is arranged into portions that are separately addressable using first identifiers;

the subsystem addresses I/O requests to a device-inaccessible space of the memory using second identifiers;

the device accesses the device-accessible space of the memory;

the method comprising the following steps;

initially mapping the second identifiers to respective first identifiers that identify portions of the memory in the device-inaccessible space;

calculating an activity score for each second identifier used by the subsystem in an I/O request during a current measurement period as a function of the frequency of use in I/O requests by the subsystem of the respective second identifier; and

for any I/O request involving a second identifier whose activity score exceeds a high-activity threshold value that meets a remapping criterion, remapping the corresponding second identifier to one of the first identifiers that identifies a portion of the memory in the device-accessible space of the memory.

25. A method for performing an input/output (I/O) operation in a computer between an I/O-initiating subsystem and a physical device through a hardware memory, in which:

the hardware memory is arranged into portions that are separately addressable using first identifiers;

the physical device accesses a device-accessible space of the hardware memory;

the I/O-initiating subsystem is located within a virtual machine that has a guest operating system and that is running on a host platform via an intermediate software layer;

the I/O-initiating subsystem directs I/O requests, using third identifiers, to a virtual device through a virtual memory;

the method comprising the following steps;

in the guest operating system, remapping I/O requests issued by the I/O-initiating subsystem from the third identifiers to second identifiers, which identify portions of the virtual memory;

in the intermediate software layer, initially mapping intermediate identifiers to respective first identifiers that identify portions of the hardware memory in a device-inaccessible space of the hardware memory, where the intermediate identifiers are chosen from the group consisting of the second and the third identifiers; and

for any I/O request that meets a remapping criterion, remapping the corresponding intermediate identifier to one of the first identifiers that identifies a portion of the memory in the device-accessible space of the memory.

26. A method as in claim 25, in which the I/O operation is output of a data set from the subsystem to the physical device, the method further comprising the following step:

for any I/O request that meets the remapping criterion, and for as long as the I/O request meets the remapping criterion, creating and maintaining a single copy of the data set in a buffer in the device-accessible space of the memory and remapping the I/O request to the single copy.

27. A method as in claim 26, further comprising the following step:

for each intermediate identifier that is currently mapped into the device-accessible space of the memory and that meets a remapping condition, again mapping the intermediate identifier into the device-inaccessible space of the memory.

28. A method as in claim 25, in which the I/O operation is input of a data set from the physical device to the subsystem, the method further comprising the following step:

for any I/O request that meets the remapping criterion, storing the data set from the device in the device-accessible space of the memory at a location identified by the first identifier to which the intermediate identifier has been remapped.

29. A method as in claim 25, further comprising the step of calculating an activity score for each intermediate identifier used in an I/O request during a current measurement period, in which the remapping criterion is that the activity score exceeds a high-activity threshold value.

30. A method as in claim 29, in which the activity score is a function of the frequency of use in I/O requests of the respective intermediate identifier.

31. A method as in claim 29, further comprising the following step:

for each intermediate identifier that is currently mapped to one of the first identifiers identifying a portion of the memory in the device-accessible space of the memory and that meets a remapping condition, again mapping the intermediate identifier to a first identifier identifying a portion of the memory in the device-inaccessible space of the memory.

32. A method as in claim 29, further comprising the following steps:

measuring a value of scarcity of portions of the memory in the device-accessible space that are available for allocation; and

adjusting the remapping criterion as a function of the value of scarcity.

33. A method as in claim 25, further comprising the step of evaluating a current cost of remapping for the current I/O request, whereby the remapping criterion is that the current cost is less than a cost threshold.

34. A method as in claim 25, in which the memory portions are pages, and all the identifiers are page numbers.

35. A method as in claim 25, in which the step of remapping further comprises remapping intermediate identifiers that identify contiguous memory portions such that the first identifiers to which they are remapped correspond to contiguous portions of the device-accessible memory space.

36. A system for performing an input/output (I/O) operation in a computer between an I/O-initiating subsystem and a device through a memory, in which:

the memory is arranged into portions that are separately addressable using first identifiers;

for the I/O operation, the device accesses a device-accessible space of the memory;

the subsystem addresses I/O requests to a device-inaccessible space of the memory using second identifiers;

the system comprising;

a manager that forms an interface between the I/O-initiating subsystem on the one hand and the device and memory on the other hand and that includes;

a memory map initially mapping the second identifiers to respective first identifiers that identify portions of the memory in the device-inaccessible memory space; and

a remapping module forming means for remapping at least one of the second identifiers that is used in any I/O request and that meets a remapping criterion to one of the first identifiers that identifies a portion of the memory in the device-accessible space of the memory.

37. A system as in claim 36, in which the I/O operation involves output of a data set from the subsystem to the device, the system further comprising:

a page copy buffer in the device-accessible space of the memory for storing, for any I/O request that meets the remapping criterion, and for as long as the I/O request meets the remapping criterion, a single copy of the data set;

the remapping module being further provided for remapping the I/O request to the single copy.

38. A system as in claim 37, in which the remapping module is further provided for again mapping into the device-inaccessible space of the memory each second identifier that is currently mapped into the device-accessible space of the memory and that meets a remapping condition.

39. A system as in claim 36, further comprising an activity-measuring module forming means for calculating an activity score for at least a subset of the second identifiers used by the subsystem in an I/O request during a current measurement period, the remapping criterion being that the activity score exceeds a high-activity threshold value.

40. A system as in claim 39, in which the remapping module is further provided for again mapping into the device-inaccessible space of the memory each second identifier that is currently mapped into the device-accessible space of the memory and that meets a remapping condition.

41. A system as in claim 36, further comprising a cost evaluation module forming means for evaluating a current cost of remapping the current I/O request and for comparing the current cost with a cost threshold, the remapping criterion being that the current cost is less than the cost threshold.

42. A system as in claim 36, in which:

the I/O-initiating subsystem is included within a guest system that runs on a host platform;

the guest system includes memory mapping means for mapping I/O requests issued by the I/O-initiating subsystem from third identifiers to the second identifiers; and

the remapping module is further provided for remapping the second identifiers to the first identifiers such that the remapping remains transparent to both the I/O-initiating subsystem and the guest system.

43. A system as in claim 42, further comprising:

an intermediate software layer;

in which;

the guest system is a virtual machine that includes a guest operating system, a virtual memory, and a virtual device;

the intermediate software layer forms an interface between the virtual machine and the host platform;

the remapping module is in the intermediate software layer;

the memory mapping means in the guest system is part of a guest operating system within the virtual machine;

the I/O requests are directed to the virtual device through the virtual memory, the third identifiers addressing the virtual memory; and

the first identifiers address a hardware memory.

44. A system as in claim 36, in which the I/O operation involves direct memory access (DMA).

45. A system as in claim 36, in which the memory portions are pages, and the first and second identifiers are page numbers.

46. A system as in claim 36, in which the remapping module is further provided for remapping second identifiers that identify contiguous memory portions such that the first identifiers to which they are remapped correspond to contiguous portions of the device-accessible space.

47. A system for performing an input/output (I/O) operation in a computer between an I/O-initiating subsystem and a device through a hardware memory, in which:

the hardware memory is arranged into portions that are separately addressable using first identifiers;

the physical device accesses a device-accessible space of the hardware memory for the I/O operation;

the I/O-initiating subsystem is located within a virtual machine that has a guest operating system, a virtual memory, and a virtual device;

the I/O-initiating subsystem directs I/O requests, using third identifiers, to the virtual device through the virtual memory;

the system comprising;

an intermediate software layer that forms an interface between the virtual machine on the one hand and the physical device and hardware memory on the other hand and that includes;

a memory map initially mapping intermediate identifiers to respective first identifiers that identify portions of the memory in the device-inaccessible memory space, the intermediate identifiers being chosen from the group consisting of the second and the third identifiers; and

a remapping module forming means for remapping at least one of the intermediate identifiers that is used in any I/O request and that meets a remapping criterion to one of the first identifiers that identifies a portion of the hardware memory in the device-accessible space of the hardware memory.

48. A system as in claim 47, in which the I/O operation involves output of a data set from the subsystem to the physical device, the system further comprising:

a page copy buffer in the device-accessible space of the hardware memory for storing, for any I/O request that meets the remapping criterion, and for as long as the I/O request meets the remapping criterion, a single copy of the data set;

the remapping module being further provided for remapping the I/O request to the single copy.

49. A system as in claim 48, in which the remapping module is further provided for again mapping into the device-inaccessible space of the hardware memory each intermediate identifier that is currently mapped into the device-accessible space of the hardware memory and that meets a remapping condition.

50. A system as in claim 47, further comprising an activity-measuring module forming means for calculating an activity score for at least a subset of the intermediate identifiers used an I/O request during a current measurement period, the remapping criterion being that the activity score exceeds a high-activity threshold value.

51. A system as in claim 50, in which the remapping module is further provided for again mapping into the device-inaccessible space of the hardware memory each second identifier that is currently mapped into the device-accessible space of the hardware memory and that meets a remapping condition.

52. A system as in claim 47, further comprising a cost evaluation module forming means for evaluating a current cost of remapping the current I/O request and for comparing the current cost with a cost threshold, the remapping criterion being that the current cost is less than the cost threshold.

53. A system as in claim 47, in which the remapping module is further provided for remapping intermediate identifiers that identify contiguous portions of the hardware memory such that the first identifiers to which they are remapped correspond to contiguous portions of the device-accessible space of the hardware memory.