Memory management for virtual address space with translation units of variable range size

• US 7,797,510 B1
• Filed: 04/30/2008
• Issued: 09/14/2010
• Est. Priority Date: 01/30/2004
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Lorensen, Gary D., Clay, Sharon Rose, Case, Colyn S.
• Primary Examiner(s): RUTZ, JARED IAN
• Application Number:
  US12/112,602
• Time in Patent Office: 867 Days
• Field of Search: 711/207, 345/543
• US Class Current: 711/207
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• 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/652 Page size control

Abstract

In a virtual memory system, address translation information is provided using a cluster that is associated with some range of virtual addresses and that can be used to translate any virtual address in its range to a physical address, where the sizes of the ranges mapped by different clusters may be different. Clusters are stored in an address translation table that is indexed by virtual address so that, starting from any valid virtual address, the appropriate cluster for translating that address can be retrieved from the translation table. The clusters are dynamically created from a fragmented pool of physical addresses as new virtual address mappings are requested by consumers of the virtual memory space.

Claims

1. A method for managing a virtual memory space, the method comprising:

providing a pool of physical addresses;

receiving a request for a virtual memory allocation from a client;

creating a plurality of clusters from the pool, wherein each cluster represents a plurality of physical addresses selected from the pool and wherein the respective pluralities of physical addresses represented by different ones of the plurality of clusters correspond to different amounts of memory, and wherein different ones of the clusters include references to different numbers of blocks of contiguous physical addresses;

removing from the pool the physical addresses represented by each cluster that is created;

for each of the clusters, defining a mapped virtual address representing a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster; and

returning a reference to the mapped virtual address to the client.

2. The method of claim 1 wherein the act of providing a pool of physical memory includes:

allocating memory from an operating system; and

adding physical addresses for the allocated pool to the memory.

3. The method of claim 2 wherein the act of allocating memory from the operating system includes allocating an amount of memory that is independent of a size of the virtual memory allocation requested by the client.

4. The method of claim 1 wherein each cluster includes a format field indicating the number of block references included in that cluster.

5. The method of claim 1 wherein defining a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster further comprises:

adding an entry into a cluster table, the entry comprising a virtual address and a set of one or more physical addresses associated with the virtual address.

6. The method of claim 1 wherein defining a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster further comprises:

translating the virtual addresses from a tiled memory addressing memory space to a physical memory addresses using a tiling aperture.

7. A method for managing a virtual memory space, the method comprising:

providing a pool of physical addresses;

receiving a request for a virtual memory allocation from a client;

iteratively forming clusters from the physical addresses for at least portion of the physical addresses, wherein forming clusters from the physical address includes;

sorting the pool of physical addresses into groups of contiguous addresses;

determining whether all groups in the pool can be represented by a same cluster;

if all of the groups cannot be represented by the same cluster, dividing the pool into two subpools and iteratively forming clusters from each of the subpools;

if all of the groups can be represented by the same cluster, accepting the cluster and removing from the pool the physical addresses represented by the cluster; and

for each of the clusters, defining a mapped virtual address representing a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster;

selecting a range of mapped virtual addresses to be allocated to the client, the range of mapped virtual address being associated with one or more clusters; and

returning a reference to the selected range of mapped virtual addresses to the client.

8. The method of claim 7 wherein each cluster comprises references to multiple blocks of contiguous physical addresses.

9. The method of claim 7 wherein the step of iteratively forming clusters is performed until at least enough memory has been mapped to satisfy the request for virtual memory allocation from the client or until the memory in the pool has been mapped.

10. The method of claim 7 wherein determining whether all groups in pool can be represented by a same cluster further comprises:

determining if all of the groups in the pool have a same size.

11. The method of claim 10 wherein the size of each of the groups in the pool is a multiple of a page size associated with the pool of physical addresses.

12. The method of claim 7 wherein dividing the pool into two subpools further comprises:

forming a first subpool from groups comprising a largest allowable block size that does not exceed a group size; and

forming a second subpool from groups not included in the first subpool.

13. The method of claim 7 wherein dividing the pool into two subpools further comprises:

forming a first subpool from groups comprising an allowed block size until the first subgroup includes at least half of the memory in the pool;

forming a second subpool from groups not included in the first subpool,

wherein the first subpool and the second subpool include approximately an equal amount of memory.

14. A method for managing a virtual memory space, the method comprising:

providing a pool of physical addresses;

receiving a request for a virtual memory allocation from a client;

sorting the pool of physical addresses into groups of contiguous addresses;

setting a target range size to a maximum threshold size;

forming as many clusters from the groups of contiguous addresses as possible from the groups of contiguous addresses;

removing from the pool the physical addresses represented by each cluster that is created;

for each of the clusters, defining a mapped virtual address representing a mapping between a range of virtual addresses in the virtual memory space and the physical addresses represented by the cluster; and

returning a reference to the mapped virtual address to the client.

15. The method of claim 14, further comprising:

determining whether enough clusters have been formed to satisfy the request; and

if the enough clusters have not been formed to satisfy the request, iteratively decrementing the target range size and forming as many clusters from the groups of contiguous addresses as possible from the groups of contiguous addresses until the enough clusters have been formed to satisfy the request or the entire pool of physical addresses has been allocated.

16. The method of claim 14 wherein the maximum threshold size is the smaller of a largest supported cluster size or a total size of the pool of physical addresses.