# Patent

## Title
Write interceptor for tracking changes to a disk image

## Abstract

Changes are tracked by tracking a change request which when performed by a disk driver changes a portion of disk storage. The change request is allowed to pass to the disk driver to be performed by the disk driver. Information associated with the change request is stored in an operating system's persistent storage. A differential backup is performed using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted.

## Background
CROSS REFERENCE TO OTHER APPLICATIONS
This application is a continuation of U.S. patent application Ser. No. 10/875,494 entitled WRITE INTERCEPTOR FOR TRACKING CHANGES TO A DISK IMAGE filed Jun. 23, 2004 (now U.S. Pat. No. 7,797,483 which issued on Sep. 14, 2010) which is incorporated herein by reference for all purposes.


FIELD OF THE INVENTION
The present invention relates generally to computer systems, more specifically, it relates to techniques for backing up computer systems.
BACKGROUND OF THE INVENTION
Data protection plays an increasingly important role in today's computer systems. Data protection often involves creating regular backups of data. Data may be backed up in various ways, such as a full backup or a differential backup. A full backup typically backs up an entire disk, while differential backups typically backup blocks that have been changed since the previous full backup. It would be desirable to be able to record the blocks that have changed since the last full back, even if the system has rebooted.



BRIEF DESCRIPTION OF THE DRAWINGS
Various embodiments of the invention are disclosed in the following detailed description and the accompanying drawings.
FIG. 1 is a block diagram illustrating an embodiment of a layered device I/O architecture that includes a write interceptor.
FIG. 2 is a flow diagram of a method according to some embodiments for recording changes to the disk during backup.
FIG. 3 is a flow diagram of a method according to some embodiments for committing the write interceptor's bitmap to the operating system's persistent storage.
FIG. 4 is a visual example of a Microsoft Windows Registry including a write interceptor according to some embodiments.
FIG. 5 is a flow diagram of a method according to some embodiments for tracking changes to a disk even after a computer shuts down and boots up.
FIG. 6 is a flow diagram of a method according to some embodiments for using a write interceptor.
FIG. 7 is a flow diagram of a method for tracking changes to a disk image according to some embodiments.



DETAILED DESCRIPTION
The invention can be implemented in numerous ways, including as a process, an apparatus, a system, a composition of matter, a computer readable medium such as a computer readable storage medium or a computer network wherein program instructions are sent over optical or electronic communication links. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention.
A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.
FIG. 1 is a block diagram illustrating an embodiment of a layered device I/O architecture that includes a write interceptor. In his example, the layered device I/O architecture includes multiple layers of drivers 100, 102, and 106 that drive the disk drive 108. I/O requests are received by the file system driver 100 and passed through other drivers 102. The I/O requests are then processed through the write interceptor 104, then through the disk driver 106 and to the disk drive 108. Further details of the processing by the write interceptor 104 are discussed in conjunction with the remaining figures.
FIG. 2 is a flow diagram of a method according to some embodiments for recording changes to the disk during backup. In this example, a backup request is received (200). Any change activity, such as a write request on the backup drive is detected (202). The change requests are held (204). For example, write requests are placed in a queue and not allowed to execute. A change request, as used herein, includes any request that can alter the disk image of the file system. Examples of change requests, include a write request, requests to create a new file, open a new file for writing, rename, move, or delete a file, and change directory permission associated with a file.
The original content is cached (206). The write interceptor bitmap is then updated (208). The write interceptor bitmap tracks disk activity by storing a single bit to represent a block of the disk, such as 64K. For example, if a bit in the write interceptor's bitmap represents the third 64K block in the disk, and it is set to one, then this implies that the third block of 64K in the disk has been changed since the last full backup. In some embodiments, if a single block is changed multiple times, then the first change alters the bit in the bitmap corresponding to that block. The remaining changes to this same block do not affect the corresponding block in the bitmap in some embodiments.
The change requests, such as write requests, are then allowed to pass to the disk driver for change completion (210).
According to some embodiments, the write interceptor notes the blocks being changed in the disk and updates its bitmap, and the change requests are then executed. In some embodiments, once a full backup request is received, all change requests are updated to the write interceptor bitmap. Accordingly, if a differential backup is requested, the blocks that have been changed since the last full backup can be identified and backed up.
FIG. 3 is a flow diagram of a method according to some embodiments for committing the write interceptor's bitmap to the operating system's persistent storage during shutdown. The operating system's persistent storage, as used herein, includes any persistent storage used by the operating system, such as Microsoft Windows Registry or AIX's ODM. In this example, the operating system processes the shut down of the host computer (300). The write interceptor's bitmap is then committed to the operating system's persistent storage, such as the Window Registry (302). The write interceptor is then unloaded (304), and the operating system is shut down (306). In some embodiments, the write interceptor's bitmap is committed to the operating system's persistent storage after the other applications have shut down. Accordingly, it can be insured that all change requests have been noted by the write interceptor.
FIG. 4 is a visual example of a Microsoft Windows Registry including a write interceptor according to some embodiments. In this example, the registry is shown to include applications 400A-400D. The write interceptor 400D is shown to include files 402A-402D associated with blocks of the disk. When a block changes, a corresponding file 402A-402D reflects that the block has changed since the last full backup.
FIG. 5 is a flow diagram of a method according to some embodiments for tracking changes to a disk even after a computer shuts down and boots up. In this example, the operating system of the host machine begins booting up (500). The write interceptor is loaded and the bitmap is read from the operating system's persistent storage (502). In some embodiments, the write interceptor is one of the first things to be loaded so that if any application requests a change to the data blocks, the write interceptor will already be loaded and tracking these changes. Once loaded, the write interceptor begins tracking change activity (504). The operating system finishes booting (506). At some later time, a full backup request is received (508). When a full backup request is received, the write interceptor's bitmap is reinitialized (510) since all changes up to the time of the backup will be incorporated into the backup. Accordingly, the write interceptor can again begin tracking changes to the disk.
FIG. 6 is a flow diagram of a method according to some embodiments for using a write interceptor for a differential backup. In this example, the request for a differential backup is received (600). A request for the changed block list is also received (602). A list of changed blocks are then sent to the backup application (604). The backup application then backs up the changed blocks (606).
FIG. 7 is a flow diagram of a method for tracking changes to a disk image according to some embodiments. In this example, a change request is tracked, wherein the change request is associated with a disk block (700). The change request is allowed to pass to the disk driver (702). The change request is associated with an operating system's persistent storage (704).
Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.

## Claims

1. A method for tracking changes comprising:
tracking a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allowing the change request to pass to the disk driver to be performed by the disk driver;
storing information associated with the change request in an operating system's persistent storage;
using a processor to perform a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted;
receiving a request to perform a full backup; and
in response to receiving the request to perform a full backup, erasing information stored in a memory associated with the write interceptor.

2. The method of claim 1, wherein:
tracking includes updating a bitmap, wherein the bitmap includes a plurality of bits and each bit indicates whether a corresponding portion of the disk storage has been changed as a result of a change request; and
storing includes storing the bitmap in the operating system's persistent storage.

3. A method for tracking changes comprising:
tracking a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allowing the change request to pass to the disk driver to be performed by the disk driver;
storing information associated with the change request in an operating system's persistent storage;
using a processor to perform a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted; and
after the system has shut down and restarted, copying the information associated with the change request from the operating system's persistent storage to memory associated with the write interceptor, wherein performing a differential backup includes using information stored in the memory associated with the write interceptor.

4. The method of claim 3 further comprising receiving an indication that the system is shutting down, wherein the information associated with the change request is stored in the operating system's persistent storage in response to receiving the indication.

5. The method of claim 3 further comprising:
receiving a request to perform a full backup after the system has shut down and restarted; and
in response to receiving the request to perform a full backup, erasing the information stored in the memory associated with the write interceptor.

6. The method of claim 3, wherein performing includes:
determining, based at least in part on the stored information associated with the change request, which portions of the disk storage have changed since a last full backup; and
backing up only those portions of the disk storage that have changed since the last full backup.

7. A system for tracking changes comprising:
a processor; and
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:
track a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allow the change request to pass to the disk driver to be performed by the disk driver;
store information associated with the change request in an operating system's persistent storage;
perform a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted; and
after the system has shut down and restarted, copy the information associated with the change request from the operating system's persistent storage to memory associated with the write interceptor, wherein performing a differential backup includes using information stored in the memory associated with the write interceptor.

8. The system of claim 7, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to receive an indication that the system is shutting down, wherein the information associated with the change request is stored in the operating system's persistent storage in response to receiving the indication.

9. The system of claim 7, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to:
receive a request to perform a full backup after the system has shut down and restarted; and
in response to receiving the request to perform a full backup, erase the information stored in the memory associated with the write interceptor.

10. The system of claim 7, wherein:
tracking includes updating a bitmap, wherein the bitmap includes a plurality of bits and each bit indicates whether a corresponding portion of the disk storage has been changed as a result of a change request; and
storing includes storing the bitmap in the operating system's persistent storage.

11. A computer program product for tracking changes, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
tracking a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allowing the change request to pass to the disk driver to be performed by the disk driver;
storing information associated with the change request in an operating system's persistent storage;
performing a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted;
receiving a request to perform a full backup; and
in response to receiving the request to perform a full backup, erasing information stored in a memory associated with the write interceptor.

12. The computer program product of claim 11 further comprising computer instructions for receiving an indication that the system is shutting down, wherein the information associated with the change request is stored in the operating system's persistent storage in response to receiving the indication.

13. The computer program product of claim 11, wherein:
the computer instructions for tracking include computer instructions for updating a bitmap, wherein the bitmap includes a plurality of bits and each bit indicates whether a corresponding portion of the disk storage has been changed as a result of a change request; and
the computer instructions for storing include computer instructions for storing the bitmap in the operating system's persistent storage.

14. The computer program product of claim 11, wherein the computer instructions for performing include computer instructions for:
determining, based at least in part on the stored information associated with the change request, which portions of the disk storage have changed since a last full backup; and
backing up only those portions of the disk storage that have changed since the last full backup.

15. A system for tracking changes comprising:
a processor; and
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:
track a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allow the change request to pass to the disk driver to be performed by the disk driver;
store information associated with the change request in an operating system's persistent storage;
perform a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted;
receive a request to perform a full backup; and
in response to receiving the request to perform a full backup, erase information stored in a memory associated with the write interceptor.

16. The system of claim 15, wherein:
tracking includes updating a bitmap, wherein the bitmap includes a plurality of bits and each bit indicates whether a corresponding portion of the disk storage has been changed as a result of a change request; and
storing includes storing the bitmap in the operating system's persistent storage.

17. The system of claim 15, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to receive an indication that the system is shutting down, wherein the information associated with the change request is stored in the operating system's persistent storage in response to receiving the indication.

18. A computer program product for tracking changes, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
tracking a change request which when performed by a disk driver changes a portion of disk storage, wherein tracking is performed by a write interceptor configured to operate between a file system driver and the disk driver;
allowing the change request to pass to the disk driver to be performed by the disk driver;
storing information associated with the change request in an operating system's persistent storage;
performing a differential backup using the information associated with the change request stored in the operating system's persistent storage after a system, which includes the disk driver and the disk storage, has shut down and restarted; and
after the system has shut down and restarted, copying the information associated with the change request from the operating system's persistent storage to memory associated with the write interceptor, wherein performing a differential backup includes using information stored in the memory associated with the write interceptor.

19. The computer program product of claim 18, wherein:
the computer instructions for tracking include computer instructions for updating a bitmap, wherein the bitmap includes a plurality of bits and each bit indicates whether a corresponding portion of the disk storage has been changed as a result of a change request; and
the computer instructions for storing include computer instructions for storing the bitmap in the operating system's persistent storage.

20. The computer program product of claim 18 further comprising computer instructions for:
receiving a request to perform a full backup after the system has shut down and restarted; and
in response to receiving the request to perform a full backup, erasing the information stored in the memory associated with the write interceptor.