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

• US 6,738,875 B1
• Filed: 07/31/2000
• Issued: 05/18/2004
• Est. Priority Date: 07/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Landy
• Primary Examiner(s): Bragdon, Reginald G.
• Application Number:
  US09/628,708
• Time in Patent Office: 1,387 Days
• Field of Search: 711/156, 711/159, 711/170, 711/144, 707/206
• 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 processs 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, said computer-executable instructions comprising:

receiving a request from a process for allocation of memory;

allocating at least one page of memory to the process;

maintaining information indicative of whether each page allocated to the process has been modified since last checked, wherein maintaining the information includes maintaining a bitmap having at least one bit per page, wherein maintaining the bitmap includes marking a bit representative of a page when the page is trimmed to disk and modified, and wherein the marking of the bit indicates at least that the page has been modified;

receiving a request to return information on whether a range of at least one page has been modified since last checked; and

returning a result in response to the request identifying each page in the range that has been modified since last checked.

2. The computer-readable medium of claim 1 wherein returning the result in response to the request identifying each page includes returning an array of virtual page addresses.

3. The computer-readable medium of claim 1 wherein receiving a request to return information includes handling an application programming interface call.

4. The computer-readable medium of claim 1 wherein maintaining information indicative of whether each page allocated to the process has been modified since last checked includes maintaining a bitmap including one bit per page, and wherein returning the result in response to the request identifying each page includes evaluating the bitmap.

5. The computer-readable medium of claim 1 further comprising maintaining a list of page addresses allocated to a process for which information indicative of whether each page allocated to the process has been modified since last checked is maintained.

6. A method of write-watching virtual memory pages, comprising:

associating a bitmap with a process, the bitmap representing a range of memory wherein each bit in the bitmap represents a page in the range; and

marking the bitmap upon detection of a modified page being trimmed to disk, the marking of the bitmap indicating that the modified page has been modified.

7. The method of claim 6 further comprising, receiving a request to report information indicative of pages in the range that have been modified, and accessing the bitmap to determine if at least some of the pages have been modified.

8. The method of claim 6 further comprising, receiving a request to report information indicative of pages in the range that have been modified, accessing the bitmap to determine if at least some of the pages have been modified, and returning the information indicative thereof.

9. The method of claim 8 further comprising, accumulating an array of virtual page addresses that have been modified.

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

receiving a request from a process for allocation of memory;

allocating at least one page of memory to the process;

maintaining information indicative of whether each page allocated to the process has been modified since last checked including maintaining a bitmap including one bit per page;

receiving a request to return information on whether a range of at least one page has been modified since last checked; and

returning a result in response to the request identifying each page in the range that has been modified since last checked including evaluating the bitmap to determine if a bit representing a page is marked as modified, and if so, maintaining information that the page is modified, and if not, accessing other information to determine if the page is modified.

11. The computer-readable medium of claim 10 wherein accessing other information to determine if the page is modified includes accessing a page table entry maintained for that page.

12. The computer-readable medium of claim 11 wherein the page table entry includes a flag having a value indicating that the page is modified, and further comprising, setting the flag to unmodified in the page table entry maintained for that page, and setting another flag in a database to modified.

13. The computer-readable medium of claim 10 wherein accessing other information to determine if the page is modified includes accessing page directory information corresponding to that page.

14. The computer-readable medium of claim 13 wherein if the page directory information corresponding to that page indicates the page is invalid, determining whether the page is modified based on a value of the bit representing the page in the bitmap.

15. A method of write-watching virtual memory pages, comprising:

associating a bitmap with a process, the bitmap representing a range of memory wherein each bit in the bitmap represents a page in the range;

marking the bitmap upon detection of a modified page being trimmed to disk;

receiving a request to report information indicative of pages in the range that have been modified;

accessing the bitmap to determine if at least some of the pages have been modified; and

for each bit in the bitmap that is not marked, accessing other information to determine if a page corresponding thereto has been modified.

16. The method of claim 15 wherein accessing other information includes accessing a page table entry maintained for that page.

17. The method of claim 16 wherein the page table entry includes a flag having a value indicating that the page is modified, and further comprising, setting the flag to unmodified in the page table entry maintained for that page, and setting another flag in a database to modified.

18. The method of claim 15 wherein accessing other information to determine if the page is modified includes accessing page directory information corresponding to that page.

19. The method of claim 18 wherein if the page directory information indicates the page is invalid, determining whether the page is modified based on a value of the bit representing the page in the bitmap.

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

maintaining information indicative of whether each page allocated to a process has been modified since last checked;

when the page is trimmed to a storage device, modifying the information to indicate that a page has been modified; and

accessing the information to provide data that indicates that a range that includes at least one page has been modified since last checked.

21. The computer-readable medium of claim 20, wherein maintaining information indicative of whether each page allocated to a process has been modified since last checked includes maintaining a bitmap having at least one bit per page.

22. The computer-readable medium of claim 21, wherein modifying the information to indicate that a page has been modified when the page is trimmed to disk includes marking a bit in the bitmap that corresponds to the page.

23. The computer-readable medium of claim 22, further comprising if a bit corresponding to a page is not marked, accessing other information to provide the data.

24. The computer-readable medium of claim 23, wherein the other information includes a page table entry maintained for the page corresponding to the bit.

25. The computer-readable medium of claim 20, wherein the data is accessed through an application programming interface (API).