Translation lookaside buffer invalidation by range

Patent metadata

Field	Value
Publication number	US-10725928-B1
Application number	US-201916243901-A
Country	US
Kind code	B1
Filing date	Jan 9, 2019
Priority date	Jan 9, 2019
Publication date	Jul 28, 2020
Grant date	Jul 28, 2020

Abstract

A system and method for efficiently performing maintenance on a cache. In various embodiments, control logic in a cache controller or elsewhere receives an indication for invalidating a range of virtual-to-physical mappings in a given translation lookaside buffer (TLB). The logic determines a first latency to invalidate entries of the TLB based on a number of addresses in the range and a number of supported page sizes simultaneously stored in the TLB. The logic determines a second latency based on a number of entries in the TLB. If the first latency is greater, then the logic traverses through each TLB entry and invalidates TLB entries storing a virtual address within the range. If the first latency is smaller, then the logic traverses through each address in the range and invalidates TLB entries storing a virtual address within the range.

First claim

What is claimed is:

1. An apparatus comprising:
a translation lookaside buffer (TLB) comprising a plurality of entries, each configured to store a mapping between a virtual address portion and a physical address portion; and
logic, wherein in response to receiving an indication to invalidate a range of virtual addresses beginning at a start virtual address, the logic is configured to:
determine a first latency to invalidate entries of the TLB based on a number of addresses in the range;
determine a second latency to invalidate each of the plurality of entries of the TLB based on a page size and the number of the plurality of entries;

in response to determining the first latency is greater than the second latency:
determine for each entry of the plurality of entries of the TLB whether a virtual address portion stored in an entry is within the range; and
invalidate an entry responsive to determining a virtual address portion stored in the entry is within the range.

2. The apparatus as recited in claim 1 , wherein the logic is further configured to:
read contents of an entry of the TLB to obtain a virtual address and a page size corresponding to a given virtual address; and
determine a virtual address portion to use for comparisons based on the page size.

3. The apparatus as recited in claim 2 , wherein the logic is further configured to compare the virtual address portion to each of an upper bound and a lower bound of the range.

4. The apparatus as recited in claim 1 , wherein in response to determining the first latency is less than the second latency, the logic is further configured to:
determine for each virtual address within the range whether a virtual address portion of the virtual address is stored in the plurality of entries of the TLB; and
invalidate a given entry of the TLB responsive to determining a virtual address portion is stored in the given entry of the TLB.

5. The apparatus as recited in claim 1 , wherein the logic is further configured to determine the first latency based at least in part on a number of page sizes in a plurality of supported page sizes.

6. The apparatus as recited in claim 5 , wherein the logic is further configured to:
select a first page size of the plurality of supported page sizes; and
determine a first virtual address portion to use for comparisons based on the selected first page size.

7. The apparatus as recited in claim 6 , wherein in response to determining the first virtual address portion is not stored in the plurality of entries of the TLB, the logic is further configured to:
select a second page size different from the first page size of the plurality of supported page sizes; and
determine a second virtual address portion to use for comparisons based on the selected second page size.

8. A method, comprising:
storing a mapping between a virtual address portion and a physical address portion in each entry of a plurality of entries in a translation lookaside buffer (TLB);
in response to receiving an indication to invalidate a range of virtual addresses beginning at a start virtual address:
determining a first latency to invalidate entries of the TLB based on a number of addresses in the range;
determining a second latency to invalidate each of the plurality of entries of the TLB based on a page size and the number of the plurality of entries;
in response to determining the first latency is greater than the second latency:
determining for each entry of the plurality of entries of the TLB whether a virtual address portion stored in an entry is within the range; and
invalidating an entry responsive to determining a virtual address portion stored in the entry is within the range.

9. The method as recited in claim 8 , further comprising:
reading contents of a given entry of the TLB to obtain a virtual address and a page size corresponding to the virtual address; and
determining a virtual address portion to use for comparisons based on the page size.

10. The method as recited in claim 9 , further comprising comparing the virtual address portion to each of an upper bound and a lower bound of the range.

11. The method as recited in claim 8 , wherein in response to determining the first latency is less than the second latency, the method further comprises:
determining for each virtual address within the range whether a virtual address portion of the virtual address is stored in the plurality of entries of the TLB; and
invalidating a given entry of the TLB responsive to determining the virtual address portion is stored in the given entry of the TLB.

12. The method as recited in claim 8 , further comprising determining the first latency based at least in part on a number of page sizes in a plurality of supported page sizes.

13. The method as recited in claim 12 , further comprising:
selecting a first page size of the plurality of supported page sizes; and
determining a first virtual address portion to use for comparisons based on the selected first page size.

14. The method as recited in claim 13 , wherein in response to determining the first virtual address portion is not stored in the plurality of entries of the TLB, the method further comprises:
selecting a second page size different from the first page size of the plurality of supported page sizes; and
determining a second virtual address portion to use for comparisons based on the selected second page size.

15. An execution core comprising:
a cache comprising a plurality of cache entries, each configured to store data;
a plurality of computation units, each configured to:
generate virtual addresses pointing to particular cache entries; and
process data retrieved from the cache; and

a translation lookaside buffer (TLB) comprising a plurality of TLB entries, each configured to store a mapping between a virtual address portion and a physical address portion; and
a cache controller, wherein the cache controller is configured to:
receive a virtual address from the plurality of computation units;
retrieve a physical address mapped to the received virtual address from the TLB;
send the physical address to the cache to retrieve data; and
in response to receiving an indication to invalidate a range of virtual addresses beginning at a start virtual address, the cache controller is configured to:
determine a first latency to invalidate TLB entries based on a number of addresses in the range;
determine a second latency to invalidate each of the plurality of TLB entries based on a page size and the number of the plurality of entries;
in response to determining the first latency is greater than the second latency:
determine for each TLB entry whether a virtual address portion stored in a TLB entry is within the range; and
invalidate a TLB entry responsive to determining a virtual address portion stored in the entry is within the range.

16. The execution core as recited in claim 15 , wherein the cache controller is further configured to:
read contents of a given entry of the TLB to obtain a virtual address and a page size corresponding to the virtual address; and
determine a virtual address portion to use for comparisons based on the page size.

17. The execution core as recited in claim 16 , wherein the cache controller is further configured to compare the virtual address portion to each of an upper bound and a lower bound of the range.

18. The execution core as recited in claim 15 , wherein in response to determining the first latency is less than the second latency, the cache controller is further co

Assignees

• Apple Inc

Inventors

• Mestan Brian R
• Kanapathipillai Pradeep
• Smith Joshua William

Classifications

• G06F2212/683

  Invalidation · CPC title

• G06F2212/652

  Page size control · CPC title

• G06F2212/502

  using adaptive policy · CPC title

• G06F12/1045 Primary

  associated with a data cache · CPC title

• G06F2212/657

  Virtual address space management · CPC title