Adaptive Extension of Leases for Entries in a Translation Lookaside Buffer

• US 20170277639A1
• Filed: 11/25/2016
• Published: 09/28/2017
• Est. Priority Date: 03/25/2016
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Awad, Amro, Blagodurov, Sergey, Basu, Arkaprava, Oskin, Mark H., Loh, Gabriel H., Kegel, Andrew G., Christie, David S., McGrath, Kevin J.
• Granted Patent: US 10,261,916 B2
• Time in Patent Office: Days
• 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 12/1036 for multiple virtual address spaces, e.g. segmentation G06F12/1045 takes precedence
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/65 Details of virtual memory and virtual address translation
• CPC Class Codes: G06F 2212/683 Invalidation

Abstract

The described embodiments include a computing device with two or more translation lookaside buffers (TLB). During operation, the computing device updates an entry in the TLB based on a virtual address to physical address translation and metadata from a page table entry that were acquired during a page table walk. The computing device then computes, based on a lease length expression, a lease length for the entry in the TLB. Next, the computing device sets, for the entry in the TLB, a lease value to the lease length, wherein the lease value represents a time until a lease for the entry in the TLB expires, wherein the entry in the TLB is invalid when the associated lease has expired. The computing device then uses the lease value to control operations that are allowed to be performed using information from the entry in the TLB.

Claims

1. A method for handling entries in a translation lookaside buffer (TLB) in a computing device, the method comprising:

updating an entry in the TLB based on a virtual address to physical address translation and metadata from a page table entry that were acquired during a page table walk;

computing, based on a lease length expression, a lease length for the entry in the TLB;

setting, for the entry in the TLB, a lease value to the lease length, wherein the lease value represents a time until a lease for the entry in the TLB expires, wherein the entry in the TLB is invalid when the associated lease has expired; and

controlling, using the lease value, operations that are allowed to be performed using information from the entry in the TLB.

2. The method of claim 1, further comprising:

keeping an extension counter for the TLB entry, the extension counter storing a value representing a number lease extensions for the entry in the TLB, wherein a lease is extended when the lease expires and another lease is established for the TLB entry;

wherein the lease length expression is a function of at least the extension counter.

3. The method of claim 2, wherein the lease length expression comprises a multiplication of the extension counter and a base lease value.

4. The method of claim 2, wherein the lease length expression comprises an exponential or linear function of the extension counter.

5. The method of claim 2, further comprising:

receiving from an entity in the computing device, a request to set the extension counter to a specified value; and

setting the extension counter to the specified value, thereby enabling the entity in the computing device to specify the lease length computed based on the lease length expression.

6. The method of claim 2, wherein keeping the extension counter comprises keeping the extension counter in a page table.

7. The method of claim 1, further comprising:

determining, based on one or more runtime conditions, that the lease length is to be computed, the runtime conditions comprising one or more indications that a lease length is longer or shorter than a desirable lease length.

8. The method of claim 7, wherein the indications that a lease length is longer or shorter than a desirable lease length comprise one or more of:

a number of page table walks caused by TLB misses based on expired TLB entries; and

a number of TLB shootdowns.

9. The method of claim 1, further comprising:

determining that the page table entry is to be modified in the page table;

determining that all leases for TLB entries associated with the page table entry have expired and therefore any TLB entries associated with the page table entry are no longer valid; and

modifying the page table entry in the page table without performing a TLB shootdown, the TLB shootdown comprising causing one or more TLBs in the computing device to invalidate corresponding TLB entries associated with the page table entry.

10. The method of claim 1, further comprising:

determining that the page table entry is to be modified in the page table;

determining that at least one lease for a TLB entry associated with the page table entry has not expired and therefore at least one TLB presently has a valid entry with information based on the page table entry;

performing a TLB shootdown, the TLB shootdown comprising causing one or more TLBs in the computing device to invalidate corresponding TLB entries associated with the page table entry; and

modifying the page table entry in the page table.

11. The method of claim 1, wherein controlling, using the lease value, the operations that are allowed to be performed using information from the entry in the TLB comprises:

acquiring a virtual address to be translated into a physical address;

determining that the entry in the TLB includes a corresponding virtual address to physical address translation;

checking the lease value for the entry in the TLB to determine if the lease for the entry has expired;

when the lease has expired, performing a page table walk to acquire the virtual address to physical address translation or the metadata; and

when the lease has not expired, acquiring the virtual address to physical address translation or the metadata from the entry in the TLB.

12. A computing device, comprising:

a processor comprising a core;

a memory comprising a page table; and

a translation lookaside buffer (TLB) in the core;

wherein the processor is configured to;

update an entry in the TLB based on a virtual address to physical address translation and metadata from a page table entry that were acquired during a page table walk;

compute, based on a lease length expression, a lease length for the entry in the TLB;

set, for the entry in the TLB, a lease value to the lease length, wherein the lease value represents a time until a lease for the entry in the TLB expires, wherein the entry in the TLB is invalid when the associated lease has expired; and

control, using the lease value, operations that are allowed to be performed using information from the entry in the TLB.

13. The computing device of claim 12, wherein the processor is further configured to:

keep an extension counter for the TLB entry, the extension counter storing a value representing a number lease extensions for the entry in the TLB, wherein a lease is extended when the lease expires and another lease is established for the TLB entry;

wherein the lease length expression is a function of at least the extension counter.

14. The computing device of claim 13, wherein the lease length expression comprises a multiplication of the extension counter and a base lease value.

15. The computing device of claim 13, wherein the lease length expression comprises an exponential or linear function of the extension counter.

16. The computing device of claim 13, wherein the processor is further configured to:

receive from an entity in the computing device, a request to set the extension counter to a specified value; and

set the extension counter to the specified value, thereby enabling the entity in the computing device to specify the lease length computed based on the lease length expression.

17. The computing device of claim 13, wherein the processor is further configured to:

keep the extension counter in a page table.

18. The computing device of claim 12, wherein the processor is further configured to:

determine, based on one or more runtime conditions, that the lease length is to be computed, the runtime conditions comprising one or more indications that a lease length is longer or shorter than a desirable lease length.

19. The computing device of claim 18, wherein the indications that a lease length is longer or shorter than a desirable lease length comprise one or more of:

a number of page table walks caused by TLB misses based on expired TLB entries; and

a number of TLB shootdowns.

20. The computing device of claim 12, wherein the processor is further configured to:

determine that the page table entry is to be modified in the page table;

determine that all leases for TLB entries associated with the page table entry have expired and therefore any TLB entries associated with the page table entry are no longer valid; and

modify the page table entry in the page table without performing a TLB shootdown, the TLB shootdown comprising causing one or more TLBs in the computing device to invalidate corresponding TLB entries associated with the page table entry.

21. The computing device of claim 12, wherein the processor is further configured to:

determine that the page table entry is to be modified in the page table;

determine that at least one lease for a TLB entry associated with the page table entry has not expired and therefore at least one TLB presently has a valid entry with information based on the page table entry;

perform a TLB shootdown, the TLB shootdown comprising causing one or more TLBs in the computing device to invalidate corresponding TLB entries associated with the page table entry; and

modify the page table entry in the page table.

22. The computing device of claim 12, wherein, when controlling, using the lease value, operations that are allowed to be performed using information from the entry in the TLB, the processor is configured to:

acquire a virtual address to be translated into a physical address;

determine that the entry in the TLB includes a corresponding virtual address to physical address translation;

check the lease value for the entry in the TLB to determine if the lease for the entry has expired;

when the lease has expired, perform a page table walk to acquire the virtual address to physical address translation or the metadata; and

when the lease has not expired, acquire the virtual address to physical address translation or the metadata from the entry in the TLB.