Efficient write-watch mechanism useful for garbage collection in a computer system

• US 7,065,617 B2
• Filed: 04/20/2004
• Issued: 06/20/2006
• Est. Priority Date: 07/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Landy
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US10/828,877
• Publication Number:
  US 20040199742A1
• Time in Patent Office: 791 Days
• Field of Search: None
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

An efficient write-watch mechanism and process. A bitmap is associated with the virtual address descriptor (VAD) for a process, one bit for each virtual page address allocated to a process having write-watch enabled. As part of the write-watch mechanism, if a virtual address is trimmed to disk and that virtual address page is marked as modified, then the corresponding bit in the VAD is set for that virtual address page. In response to an API call (e.g., from a garbage collection mechanism) seeking to know which virtual addresses in a process have been modified since last checked, the memory manager walks the bitmap in the relevant VAD for the specified virtual address range for the requested process. If a bit is set, then the page corresponding to that bit is known to have been modified since last asked. If specified by the API, the bit is cleared in the VAD bitmap so that it will reflect the state since this time of asking. If the bit is not set, to determine if the page was modified, the page table entry (PTE) is checked for that page, and if the PTE indicates the page was modified, the page is known to be modified, otherwise that page is known to be unmodified since the last call. One enhancement uses page directory tables to locate a series of trimmed pages, sometimes avoiding the need to access the PTE.

Claims

1. A computer-readable medium having computer-executable instructions, comprising:

maintaining information indicative of whether a page has been modified since last checked;

modifying the information upon the page being trimmed to storage to indicate that the page has been modified since last checked;

receiving a request as to whether the page has been modified since last checked; and

indicating in response to the request that the page has been modified since last checked based on the information.

2. The computer-readable medium of claim 1, wherein the information is maintained in a bitmap having one bit for each page of a plurality of pages, the plurality of pages including the page, each bit indicating whether its corresponding page has been changed since last checked.

3. The computer-readable medium of claim 2, wherein the bitmap is subject to modification each time one of the plurality of pages is trimmed to storage, the modification to the bitmap indicating that the page trimmed to storage has been modified since last checked.

4. The computer-readable medium of claim 1, wherein the request comprises a request for modification information for a range of a plurality of pages including the page, and wherein the response indicates whether each page in the range of pages has been changed since last checked.

5. The computer-readable medium of claim 4, wherein the plurality of pages were allocated by a process.

6. The computer-readable medium of claim 5, wherein the plurality of pages include all allocated pages of the process.

7. The computer-readable medium of claim 4, wherein the pages are virtual pages.

8. The computer-readable medium of claim 1, wherein the information is maintained in association with a linked-list comprising all virtual address descriptors that are watched for modification since last checked.

9. A method of write-watching memory, comprising

receiving a request as to whether a page has been modified since last checked;

determining whether a page directory indicates that a plurality of pages including the page have been trimmed to storage; and

if the plurality of pages have been trimmed to storage, examining information that indicates whether the page was modified since last checked and indicating whether the page was modified based on the information, wherein upon the page being trimmed to storage, the information is updated to indicate that the page was modified.

10. The method of claim 9, wherein the request comprises a request as to whether a range of pages have been modified since last checked, the range of pages including the page.

11. The method of claim 9, wherein determining whether the page directory indicates that the plurality of pages have been trimmed to storage comprises checking a flag in the page directory.

12. The method of claim 9, wherein the information indicates that the page was modified since last checked if the page was trimmed to storage since last checked.

13. The method of claim 9, further comprising, if the plurality of pages have not been trimmed to storage, examining a page table entry corresponding to the page to determine whether the page has been modified since last checked and indicating whether the page has been modified.

14. The method of claim 13, further comprising resetting data in the page table entry to indicate that the page has not been modified since last checked.

15. The method of claim 14, further comprising modifying information in memory other than the page table entry to indicate that the page is dirty.

16. The method of claim 15, wherein the memory other than the page table entry indicates which physical pages have been modified since they have been read from storage.

17. The method of claim 15 wherein the memory other than the page table entry is consulted when trimming pages to storage.

18. A computer-readable medium having computer-executable instructions, which when executed perform the method of claim 9.

19. A computer-readable medium having computer-executable instructions, comprising:

checking data other than a page table entry to determine whether a page has been trimmed to storage since last checked; and

if the page has been trimmed to storage since last checked, indicating that the page has been modified since last checked,

otherwise, checking the page table entry to determine whether the page has been modified since last checked and indicating whether the page has been modified since last checked.

20. The computer-readable medium of claim 19, wherein checking the page table entry to determine whether the page has been modified since last checked occurs only when the page remains in memory.