Flexible translation storage buffers for virtual address translation

• US 5,899,994 A
• Filed: 06/26/1997
• Issued: 05/04/1999
• Est. Priority Date: 06/26/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Caceres, Adrian D., Mohamed, Ahmed H.
• Primary Examiner(s): Kulik, Paul
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/884,368
• Time in Patent Office: 677 Days
• Field of Search: 711/207, 711/202, 711/203, 711/206, 711/212, 711/118, 707/100
• US Class Current: 711/203
• CPC Class Codes: G06F 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/681 Multi-level TLB, e.g. microTLB and main TLB
• CPC Class Codes: Y10S 707/959 Network

Abstract

A technique for managing address translation storage buffers (TSBs) supports multiple pools of different TSB sizes and dynamically assigns a process to its own TSB of the proper size as the needs of the process change. A process is assigned a small TSB and the system migrates the process to a larger TSB if needed. One method includes the steps of identifying sizes of TSBs to support, allocating a TSB pool in memory with these sizes, selecting an appropriately sized TSB for a process, and migrating that process to a larger size should the process require more memory. A second method allocates a TSB pool by determining an appropriate size for the TSB pool, determining sizes of TSBs to support, allocating memory for the pool and initializing status block for each size of TSB. A third method selects an appropriate TSB for a process by selecting a smallest supported size of a TSB from the pool. A fourth method migrates a process to a larger size by determining whether the current TSB is of an inappropriate size, selecting a larger TSB size, invalidating the previous TSB, and selecting a TSB of the new size from the TSB pool. Variations on these methods require that the memory spaces shared by the TSBs of different sizes are coexistent, require that the TSBs be stored in virtual space or that entries in the translation look-aside buffer (TLB) be reserved for a separate user TSB and kernel (system) TSB.

Claims

1. A computer storage product including a computer-usable medium having computer-readable program code embodied thereon for managing a plurality of translation storage buffers (TSBs) for processes executing in a computer system, said TSBs being selected from a TSB pool in a memory of a computer system and having at least two different sizes, said computer storage product comprising computer-readable program code for effecting the following method:

identifying said at least two different sizes for said TSBs;

allocating a TSB pool of said TSBs;

selecting a small TSB having a first size from said TSB pool for a process; and

migrating said process from said small TSB to a large TSB having a second size from said TSB pool, said second size being larger than said first size.

3. A computer storage product as recited in claim 1 wherein an address of a starting location in memory for each of said plurality of TSBs is a virtual address, said method further comprising:

reserving an entry in a translation look-aside buffer (TLB) for a kernel TSB.

2. A computer storage product as recited in claim I wherein said TSBs of one size are coexistent with said TSBs of another size in said memory of said computer system.

4. A computer storage product as recited in claim I wherein said method includes the sub-steps of:

determining whether the number of physical pages of said process exceeds a percentage of the number of entries in said small TSB.

5. A translation storage buffer (TSB) management data structure embodied in a computer-readable medium suitable for use in a computer system, said TSB management data structure comprising:

a TSB pool including a plurality of first TSBs of a first size and a plurality of second TSBs of a second size, said plurality of first and second TSBs available to each be assigned to a process executing on said computer system;

a first TSB information structure arranged to manage said first TSBs and having at least one pointer arranged to indicate the location of said first TSBs in memory of said computer system; and

a second TSB information structure arranged to manage said second TSBs and having at least one pointer arranged to indicate the location of said second TSBs in memory of said computer system.

6. A TSB management data structure as recited in claim 5 wherein said first TSBs of said first size are arranged to occupy a region of memory in said computer system and said second TSBs of said second size are arranged to occupy said same region of memory.

7. A TSB management data structure as recited in claim 5 wherein an address of a starting location in memory for each of said first and second TSBs is a virtual address, and said computer system includes a CPU having a translation look-aside buffer (TLB) with a first reserved entry for a user TSB and a second reserved entry for a system TSB.

8. A computer storage product including a computer-usable medium having computerreadable program code embodied thereon for allocating a translation storage buffer (TSB) pool in a memory of a computer system, said TSB pool usable for address translation by a plurality of processes executing within said computer system, said computer storage product comprising computer-readable program code for effecting the following method:

determining a size for said TSB pool in said memory of said computer system;

indicating a first size for each of a plurality of first TSBs to be represented in said TSB pool;

indicating a second size for each of a plurality of second TSBs to be represented in said TSB pool, said second size being different from said first size;

allocating a portion of said memory of said computer system for said TSB pool, said TSB pool in said memory including said first TSBs and said second TSBs;

initializing a first TSB management means for managing said first TSBs in said TSB pool; and

initializing a second TSB management means for managing said second TSBs in said TSB pool, whereby each of said processes may be assigned to one of said first or second TSBs of said TSB pool.

9. A computer storage product as recited in claim 8 wherein said second TSBs are coexistent with said first TSBs in said memory of said computer system.

10. A computer storage product as recited in claim 8 wherein an address of a starting location in memory for each of said first and said second TSBs is a virtual address, said method further comprising:

reserving an entry in a translation look-aside buffer (TLB) for a kernel TSB.

11. A computer storage product as recited in claim 8 wherein said method further comprises:

initializing at least one pointer of said first TSB management means to indicate the location of said first TSBs in said TSB pool; and

initializing at least one value of said second TSB management means to indicate the location of said second TSBs in said TSB pool.

12. A computer storage product including a computer-usable medium having computer-readable program code embodied thereon for selecting a translation storage buffer (TSB) for a process, said TSB being selected from a TSB pool in a memory of a computer system, said TSB pool having a plurality of TSBs of at least two different sizes and being usable for address translation by a plurality of processes executing within said computer system, said computer storage product comprising computer-readable program code for effecting the following method:

allocating a process context for said process;

determining a first size of a TSB to select for said process from among said at least two different sizes of said plurality of TSBs in said TSB pool;

accessing a TSB information structure associated with said first size of a TSB, said TSB information structure including information on locations of TSBs of said first size in said TSB pool;

selecting a TSB of said first size from said TSB pool; and

assigning said selected TSB to said process.

13. A computer storage product as recited in claim 12 wherein said plurality of TSBs of at least two different sizes are coexistent with each other in said memory of said computer system.

14. A computer storage product as recited in claim 12 wherein an address of a starting location in memory for each of said plurality of TSBs is a virtual address, and said computer system includes a CPU having a translation look-aside buffer (TLB) with a first reserved entry for a kernel TSB.

15. A computer storage product as recited in claim 12 wherein said step of selecting a TSB includes the sub-steps of:

accessing a next pointer of said TSB information structure to determine the location of said TSB of said first size, and

updating said next pointer of said TSB information structure to indicate the location of a next available TSB of said first size.

16. A computer storage product as recited in claim 12 wherein a CPU on which said process is executing includes a translation look-aside buffer (TLB) and a single TSB register, said step of assigning said selected TSB includes the sub-steps of:

updating said TSB register with an address of said selected TSB; and

entering said address of said selected TSB in a first reserved entry in said TLB.

17. A computer storage product including a computer-usable medium having computer-readable program code embodied thereon for assigning a process in a computer system to a new translation storage buffer (TSB) having a new size from a current TSB having a current size, said new TSB being selected from a TSB pool in a memory of a computer system, said TSB pool having a plurality of TSBs of at least two different sizes and being usable for address translation by a plurality of processes executing within said computer system, said computer storage product comprising computer-readable program code for effecting the following method:

determining whether said current size of said current TSB is no longer suitable for said process;

wherein when it is determined that said current size of said current TSB is no longer suitable for said process, selecting a new size of a TSB for said process;

accessing a TSB information structure associated with said new size;

selecting a new TSB having said new size from said TSB pool; and

assigning said new TSB to said process.

18. A computer storage product as recited in claim 17 wherein said TSBs of one size are coexistent with said TSBs of another size in said memory of said computer system.

19. A computer storage product as recited in claim 17 wherein an address of a starting location in memory for each of said plurality of TSBs is a virtual address, and said computer system includes a CPU having a translation look-aside buffer (TLB) with a first reserved entry for a kernel TSB.

20. A computer storage product as recited in claim 17 wherein said step of selecting a new TSB includes the sub-steps of:

accessing a next pointer of said TSB information structure to determine the location of said new TSB of said new size, and

updating said next pointer of said TSB information structure to indicate the location of a next available TSB of said new size.

21. A computer storage product as recited in claim 17 wherein a CPU on which said process is executing includes a translation look-aside buffer (TLB) and a single TSB register, said step of assigning said new TSB includes the sub-steps of:

updating said TSB register with an address of said new TSB; and

entering said address of said new TSB in a first reserved entry in said TLB.

22. A computer storage product as recited in claim 17 wherein said method includes the sub-steps of:

determining whether the number of physical pages of said process exceeds a percentage of the number of entries in said current TSB;

selecting a larger size for said new size of a TSB.

23. A computer implemented method for managing a plurality of translation storage buffers (TSBs) for processes executing in a computer system, said TSBs being selected from a TSB pool in a memory of a computer system and having at least two different sizes, said method comprising the steps of:

identifying said at least two different sizes for said TSBs;

allocating a TSB pool of said TSBs;

selecting a small TSB having a first size from said TSB pool for a process; and

migrating said process from said small TSB to a large TSB having a second size from said TSB pool, said second size being larger than said first size.

24. A computer implemented method as recited in claim 23 wherein said TSBs of one size and said TSBs of another size reside contemporaneously in said memory of said computer system.

25. A computer implemented method as recited in claim 23 wherein an address of a starting location in memory for each of said plurality of TSBs is a virtual address, said computer implemented method further including the step of reserving an entry in a translation look-aside buffer (TLB) for a kernel TSB.

26. A computer implemented method as recited in claim 23 further including the substep of determining whether the number of physical pages of said process exceeds a percentage of the number of entries in said small TSB.

27. A computer system comprising:

a central processing unit (CPU);

a read only memory (ROM) coupled to said CPU;

a random access memory (RAM) coupled to said CPU;

a computer readable medium storing a translation storage buffer (TSB) management data structure, said TSB management data structure including;

a TSB pool including a plurality of first TSBs of a first size and a plurality of second TSBs of a second size, said plurality of first and second TSBs available to each be assigned to a process executing on said computer system;

a first TSB information structure arranged to manage said first TSBs and having at least one pointer arranged to indicate the location of said first TSBs in memory of said computer system; and

a second TSB information structure arranged to manage said second TSBs and having at least one pointer arranged to indicate the location of said second TSBs in memory of said computer system.

28. A computer system as recited in claim 27 wherein said first TSBs of said first size are arranged to occupy a certain region of memory in said computer system and said second TSBs of said second size are arranged to occupy said certain region of memory, and further wherein an address of a starting location in memory for each of said first and second TSBs is a virtual address, and said computer system includes a CPU having a translation look aside buffer (TLB) with a first reserved entry for a user TSB and a second reserved entry for a system TSB.

29. A computer system as recited in claim 27 wherein said computer system is one of a plurality of computer systems coupled together via a computer network, said TSB pool enabling the implementation of virtual memory distributed across the computer network.

30. A computer system as recited in claim 29 wherein said virtual memory is able to hide its distributed nature.

31. A computer implemented method for allocating a translation storage buffer (TSB) pool in a memory of a computer system, said TSB pool usable for address translation by a plurality of processes executing within said computer system, said computer implemented method comprising the steps of:

determining a size for said TSB pool in said memory of said computer system;

indicating a first size for each of a plurality of first TSBs to be represented in said TSB pool;

indicating a second size for each of a plurality of second TSBs to be represented in said TSB pool, said second size being different from said first size;

allocating a portion of said memory of said computer system for said TSB pool, said TSB pool in said memory including said first TSBs and said second TSBs;

initializing a first TSB management means for managing said first TSBs in said TSB pool; and

initializing a second TSB management means for managing said second TSBs in said TSB pool, whereby each of said processes may be assigned to one of said first or second TSBs of said TSB pool.

32. A computer implemented method as recited in claim 31 wherein said second TSBs are coexistent with said first TSBs in said memory of said computer system.

33. A computer implemented method as recited in claim 31 wherein an address of a starting location in memory for each of said first and said second TSBs is a virtual address, said computer implemented method further comprising reserving an entry in a translation look-aside buffer (TLB) for a kernel TSB, said computer implemented method further comprising the steps of:

initializing at least one pointer of said first TSB management means to indicate the location of said first TSBs in said TSB pool; and

initializing at least one value of said second TSB management means to indicate the location of said second TSBs in said TSB pool.

34. A computer implemented method for selecting a translation storage buffer (TSB) for a process, said TSB being selected from a TSB pool in a memory of a computer system, said TSB pool having a plurality of TSBs of at least two different sizes and being usable for address translation by a plurality of processes executing within said computer system, said computer implemented method comprising the steps of:

allocating a process context for said process;

determining a first size of a TSB to select for said process from among said at least two different sizes of said plurality of TSBs in said TSB pool;

accessing a TSB information structure associated with said first size of a TSB, said TSB information structure including information on locations of TSBs of said first size in said TSB pool;

selecting a TSB of said first size from said TSB pool; and

assigning said selected TSB to said process.

35. A computer implemented method as recited in claim 34 wherein said step of selecting a TSB includes the sub-steps of:

accessing a next pointer of said TSB information structure to determine the location of said TSB of said first size, and

updating said next pointer of said TSB information structure to indicate the location of a next available TSB of said first size.

36. A computer implemented method for assigning a process in a computer system to a new translation storage buffer (TSB) having a new size from a current TSB having a current size, said new TSB being selected from a TSB pool in a memory of a computer system, said TSB pool having a plurality of TSBs of at least two different sizes capable of being coexistent in said memory of said computer system, and being usable for address translation by a plurality of processes executing within said computer system, said computer implemented method comprising the steps of:

determining whether said current size of said current TSB is no longer suitable for said process;

wherein when it is determined that said current size of said current TSB is no longer suitable for said process, selecting a new size of a TSB for said process;

accessing a TSB information structure associated with said new size;

selecting a new TSB having said new size from said TSB pool, said step of selecting a new TSB including the sub-steps of a) accessing a next pointer of said TSB information structure to determine the location of said new TSB of said new size and b) updating said next pointer of said TSB information structure to indicate the location of a next available TSB of said new size; and

assigning said new TSB to said process, said step of assigning said new TSB to said process including the sub-steps of a) updating said TSB register with an address of said new TSB and entering said address of said new TSB in a first reserved entry in said TLB.