Lazy flushing of translation lookaside buffers

• US 20060161734A1
• Filed: 02/03/2006
• Published: 07/20/2006
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cohen, Ernest S.
• Granted Patent: US 7,287,124 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• 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/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: G06F 2212/682 Multiprocessor TLB consistency

Abstract

Address translation control (ATC) limits the mappings between virtual and physical addresses in order to implement a memory access policy. Each processor in a multi-processor system maintains a translation lookaside buffer (TLB) that caches mappings to speed translation of virtual addresses. Each processor also maintains a counter. Each time a processor'"'"'s TLB is flushed, the processor'"'"'s counter is incremented. When a link to a page is removed from an address translation map, the counter values for all of the processors are recorded. When that page is accessed by a processor, the recorded counter values are compared with the processor'"'"'s current counter value to determine whether the processor'"'"'s TLB has been flushed since the link to the page was removed from the map. An expensive TLB flush operation is delayed until needed, but still occurs early enough to prevent an invalid TLB entry from being used to violate the access policy.

Claims

1. A method of clearing obsolete entries from a first one of a plurality of mapping caches, each of the plurality of mapping caches being associated with a corresponding one of a plurality of processing units of a computing device, each of the caches being used to translate virtual addresses to physical addresses and storing mappings based on an address translation map, the method comprising:

maintaining a counter;

updating said counter each time the first one of the plurality of mapping caches is flushed;

recording said counter'"'"'s value in response to a change in the address translation map, whereby a recorded counter value is stored;

determining, based on a comparison of said counter'"'"'s value with the recorded counter value, that the first one of the plurality of mapping caches has not definitely been flushed since said change in the address translation map occurred; and

flushing the first one of the plurality of mapping caches.

2. The method of claim 1, wherein said counter is one of a plurality of counters, each counter being associated with a corresponding one of the mapping caches.

3. The method of claim 2, wherein each of the plurality of counters is updated when a counter'"'"'s corresponding mapping cache is flushed.

4. The method of claim 1, wherein the address translation map comprises links to pages of memory including a first page, and wherein said change comprises placing the address translation map in a state in which the address translation map does not contain any links to said first page.

5. The method of claim 1, wherein the address translation map defines portions of a memory that are readable by an entity, said portions of said memory including a first portion, and wherein said change comprises placing the address translation map in a state in which said first portion is not readable by said entity.

6. The method of claim 1, wherein the address translation map defines portions of a memory that are writeable by an entity, said portions of said memory including a first portion, and wherein said change comprises placing the address translation map in a state in which said first portion is not writeable by said entity.

9. The method of claim 1, further comprising:

determining that an event has arisen that potentially makes use of the state of the address translation map prior to said change;

wherein flushing the first one of the plurality of map caches is performed in response to the determination that said event has arisen.

10. The method of claim 9, wherein said event comprises a translation of a virtual address to a physical address that is contained in a portion of memory that was de-linked from the address translation map by said change.

7-8. -8. (canceled)

11-17. -17. (canceled)

18. A computer-readable medium having encoded thereon computer-executable instructions to perform a method of managing the flushing of a translation lookaside buffer that caches address mappings, the method comprising:

receiving an access request that indicates a target location by virtual address;

translating said virtual address to obtain a physical address of said target location;

comparing (1) a stored counter value associated with a page that comprises said target address with (2) a current counter value;

determining based on the comparison between said stored counter value and said current counter value that the translation lookaside buffer has not been flushed since an event affecting a mapping of said page; and

flushing the translation lookaside buffer.

19. The computer-readable medium of claim 18, wherein the address mappings are defined by an address translation map stored in a memory, the translation lookaside buffer caching mappings that are based on said address translation map.

22. The computer-readable medium of claim 18, wherein an address translation control mechanism determines the membership of a set of pages of a memory that may be used to store portions of an address translation map, and wherein said event comprises a change in membership of said set.

20-21. -21. (canceled)

23. A method of clearing obsolete entries from a first one of a plurality of mapping caches, each of the plurality of mapping caches being associated with a corresponding one of a plurality of processing units of a computing device, each of the caches being used to translate virtual addresses to physical addresses and storing mappings based on an address translation map, the method comprising:

maintaining an object based on which the sequential progression of events can be determined;

recording said object'"'"'s value in response to a change to the address translation map that removes one or more of, (1) read access, or (2) read/write access, from a page, whereby a recorded value is created;

in response to a request to access said page, determining based on a comparison of said object'"'"'s current value with the recorded value that the first one of the plurality of mapping caches has been flushed since said change occurred; and

if it cannot be determined with certainty based on said comparison that the first one of the plurality of mapping caches has been flushed since said change occurred, then flushing the first one of the plurality of mapping caches.

24. The method of claim 23, wherein said object comprises a clock.

25. The method of claim 23, wherein said object comprises a counter that is incremented each time the first one of the plurality of mapping caches is flushed.

26. The method of claim 23, wherein said object comprises a plurality of counters, each of the counters corresponding to one of the plurality of mapping caches, wherein each of the counters is incremented when the counter'"'"'s corresponding mapping cache is flushed.

27. The method of claim 23, wherein said change comprises removing read access to said page, and wherein said access request comprises a request to read said page.

28. The method of claim 23, wherein said change comprises removing read/write access to said page, and wherein said access request comprises a request to write said page.