Method and system for detecting cross linked files

A method for detecting and correcting cross-linked files while accessing data on a storage media. Each file includes control file information that defines a plurality of blocks on storage media allocated to the file. When a program identifies a volume of storage media that may include cross-linked files, the program intercepts requests to access a file on the storage device. The program then reads the control information for the file and identifies the blocks allocated to the file. The program compares the allocation to a free space map, identifying allocated and unallocated blocks on the storage media, and corrects any inconsistency between the free space map and the control information. The program also maintains a secondary map, which identifies the blocks on the storage media allocated to the files that have been previously been examined. If the program determines, based on the secondary map, a block on the storage media is allocated to at least a first file and a second file, the program modifies the allocation of the first file so that it does not reference a block allocated to the second file. The program is capable of correcting and detecting cross-linked files while the storage media is accessed by other programs such as applications.

TECHNICAL FIELD

This invention relates generally to operating systems, and more particularly, relates to methods and systems that allow a file system to detect cross-linked files.

BACKGROUND OF THE INVENTION

Computers interface to one or more storage devices that incorporate removable or non-removable storage media. Examples of storage media include floppy disks, hard disks, CD ROMs, digital versatile disks (DVD) and the like. The storage media is used to store various types of information. For example, when a user creates a document with a word processing application program, the document can be saved as data on the storage media. A request is sent from the application program to an operating system executing in the computer. The operating system in turn sends a request to the storage device to store the data. The storage device then stores the data as part of a file on the storage media. The user can then later retrieve the data via the operating system, further manipulate the document, and resave the data as needed.

Data for the file is stored onto individual units on the storage media referred to as blocks or clusters. The storage media is organized so that the operating system can locate unallocated blocks (without stored data), to store new data and so that the operating system can locate and retrieve the data for the file. Thus, each file typically includes not only the data to be stored but also certain control information. For example, the control information identifies blocks on the storage media that include data for the file. The storage media also includes a free space map identifying blocks on the storage media that include stored data, i.e. allocated blocks; and blocks that are available to store new data, i.e. unallocated blocks.

To properly create a file, the operating system completes a series of transactions. The operating system reads the free space map to identify unallocated blocks on the storage media that can be used to store the data for the file. After a sufficient number of unallocated blocks are identified, the operating system sends a request to the storage device to store the data to the identified unallocated blocks. The operating system also updates the free space map on the storage media so that the blocks containing the file data are identified as allocated.

If the operating system fails to complete one or more of the transactions, the integrity of the storage media can become corrupted. Specifically, an inconsistency may occur between the free space map and the control information associated with one or more of the files on the storage media. For example, the operating system sends a request to the storage device to store the data associated with a first file along with its control information. However, the computer may crash or be shut off before the operating system updates the free space map. As a result, the free space map identifies one or more blocks, which include data for the first file, as unallocated. During a subsequent write operation for a second file, one or more of the blocks that include data for the first file are allocated to the second file because the blocks are identified in the free space map as unallocated. A loss of data can then occur when the data for the second file is stored on blocks allocated to both the first file and the second file. When one or more blocks are allocated to two or more files, the files are said to be “cross-linked.”

The methods presently available to detect and correct cross-linked files are slow and inefficient. In known systems, a utility reads the data storage control information for all of the files on a storage media to identify cross-linked files. The amount of time required to read the control information for all of the files on the storage media can be on the order of many minutes or even hours depending on the media type, size and also the device speed. Data on the storage media cannot, for example, be accessed by other applications while the utility is executing. Because the storage media cannot be accessed while the utility is running, the methods presently available provide an inconvenient means to detect and correct cross-linked files.

SUMMARY OF THE INVENTION

In accordance with the foregoing, a method and system for detecting cross-linked files on a storage media is provided. The invention allows a file system to detect cross-linked files while data on the storage media is accessed.

In one embodiment of the invention, a program executing as part of the operating system enables a cross-link file detection function when a corrupted storage media volume is detected. The cross-link file detection function maintains a secondary map and an examined files data structure. The examined files data structure identifies the files previously examined by the cross-linked file detection function. The secondary map identifies blocks allocated to files that the cross-link file detection function has already examined.

When the cross-link file detection function is enabled, and the operating system requests access to file data on the storage media, the function reads the allocation of the file, i.e., an identification of blocks on the storage media including file data. The cross-link file detection function compares the allocation of the file with a free space map that identifies allocated and unallocated blocks on the storage media. If the primary map identifies, as unallocated, any blocks allocated to the file, the blocks allocated to the file are reconciled with the primary map.

The cross-link file detection function also compares the allocation of the file with the secondary map. If the secondary map identifies, as allocated, any blocks allocated to the file, the file is cross-linked with at least one other file on the storage media. The cross-link file detection function reconciles the allocation of the file with the secondary map.

In one embodiment of the invention, the cross-link file detection function reconciles the allocation of the file with the primary and secondary map by truncating the allocation of the file. The detection function removes, from the allocation of the file, any blocks that conflict with the primary or secondary map.

In an alternative embodiment of the invention, the cross-link file detection function reconciles the allocation of the file with the primary and secondary map by copying the data in blocks allocated to the file that conflict with the primary or secondary map to a new set of blocks on the storage media. The allocation of the file is modified to reference the new set of blocks.

Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments which proceeds with reference to the accompanying figures.

DETAILED DESCRIPTION OF THE INVENTION

The invention is generally directed to a method and system for detecting cross-linked files on a storage media divided into a plurality of blocks. A plurality of files are stored on the storage media. Each file includes data to be stored and control information identifying the blocks on the storage media that include data for the file, i.e., blocks that are allocated to the file. A free space map on the storage media identifies blocks on the media that include stored data, i.e. allocated blocks, and blocks that are available to store new data, i.e. unallocated blocks. When the control information for two or more files identify one or more common block, the files are cross-linked and one file may overwrite the data for another file.

In an embodiment of the invention, a secondary map is provided. The secondary map identifies the blocks on the storage media that are known to be allocated to other files. The program also maintains an examined files data structure. The examined files data structure allows the operating system to identify the files on the storage media that have been examined during a mount session. In an embodiment of the invention, files are only examined once per mount session.

A program intercepts requests to access data stored on the storage media. The program reads the control information for the file containing the data to be accessed and compares the blocks allocated to the file with a free space map. The program modifies the file's allocation to be consistent with free space map. The program also compares the file's allocation with the secondary map. The program further modifies the file's allocation to be consistent with the secondary map.

Turning to the drawings, wherein like reference numerals refer to like elements, the invention is illustrated as being implemented in a suitable computing environment. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a personal computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

FIG. 2illustrates an exemplary operating arrangement that allows information to be stored on storage media. The operating arrangement includes a computer200. An operating system202executes within computer200. The operating system202includes various components such as a file system driver204and a device driver206that facilitate communication between applications and utilities and a storage device208. The storage device208further includes a storage media210capable of storing information such as, for example, computer readable instructions, data structures, program modules and other data processed within the computer200.

By way of example, application211, such as a word processing program, under direction from a user, creates application data212, such as a document. The user requests the application211to save the document. To save the document, the application211passes a request to the operating system202. The file system driver204and device driver206translate the request into an appropriate form and forward the request to the storage device208. The storage device208stores the data from the document, such as text and formatting information, to a file on the storage media210.

Exemplary types of the storage devices208include hard disk drives, floppy disk drives, DVD disk drives, CD ROM drives and the like. Potential forms of the storage media210include both removable and non-removable media. For example, a DVD disk is a type of removable media that is inserted into or removed from a DVD disk drive storage device. A fixed hard disk is a type of non-removable media that is included as part of a fixed hard disk drive. The storage media210is divided into one or more volumes. A volume corresponds to a logical partition on the storage media. For example, a floppy disk may include a single partition or volume while a hard disk may include a plurality of partitions or volumes. The exemplary storage media208shown inFIG. 2comprises a single volume.

The storage media210is further divided into a plurality of units referred to as blocks and each block stores a certain amount of data. In the example shown, the storage media210includes file data214, control information216, a free space map218and status data220. The file data214, control information216, free space map218and status data220are stored on the plurality of blocks on the storage media210.

The file data214comprises the data to be stored for a file. For example, in the case of word processing document, the file data214includes the text and formatting information for the document. In the case of a program, such as an application211, the file data214includes a set of computer executable instructions. As those skilled in the art will recognize, file data214may comprise part of a file object, data stream or similar structure. However, for simplicity, file data214is referred to herein as simply comprising part of a file.

As generally shown, each set of file data214includes corresponding control information216. The control information216identifies which blocks on the storage media210include the file data214, i.e. which blocks on the storage media are allocated to the file. For example, the data for a word processing document may require 50 blocks of storage media space. The control information216identifies which 50 blocks on the storage media include the word processing document file data214. The control information216also includes other information, such as the date and time the file was created and the file size. The operating system202reads the control information216to locate the blocks that store data214for a particular file.

The free space map218identifies blocks on the storage media that are allocated and blocks that remain unallocated. An allocated block contains stored data. For example, allocated blocks include blocks containing file data214for at least one file, control information216, status data220, or the free space map218. The free space map218is implemented in any suitable manner. By way of example, the free space map is a bitmap where each bit corresponds to one of the plurality of blocks that exist on the storage media210. A bit with a value of “1” indicates an allocated block while a value of “0” indicates an allocated block.

The status data220provides information concerning a current state of the storage media210. For example, the status data220identifies whether the disk is “open” or “closed.” The function of the status data220is described in further detail below.

The method of implementing stored data, such as file data214, status data220, control information216, and the free space map218depends on file system types. Examples of file system types include New Technology File System (NTFS), File Allocation Table (FAT) and Universal Disk Format (UDF) to name a few. Such file systems are known and need not be described in detail. Of course, as will become apparent, the invention is not limited to any particular file system type.

To store data214for a file on the storage media210, the operating system completes a plurality of transactions. For example, the operating system202reads the free space map218to identify enough unallocated blocks on the storage media210to store the file data214and its corresponding control information216. The operating system202then sends a request to the storage device208to store the file data214and the control information216. The operating system also updates the free space map218to identify blocks containing the file data214and control information216as allocated.

The operating system202updates the status data218on the storage media210while performing the transactions. For example, before the operating system requests storage of the file data214and control information216on the storage media208the operating system202updates the status data218to indicate that the storage media210volume is open. After the operating system202completes all necessary transactions to store the data on the storage media210, including updating the free space map218, the status data220is changed to indicate that the storage media is closed.

If the operating system202fails to complete all required transactions when storing data to a file, the storage media208can become corrupted. For example, the control information216for one or more of the sets of file data214becomes inconsistent with the free space map218. As a result, the control information216for a plurality of files identifies one or more common block. As a specific example, the operating system202sends a request to the storage device208to store the file data214and the control information216for a first file, but because of a system error or power down sequence, the operating system202fails to update free space map218even though the first file, itself designates blocks as allocated. The operating system202subsequently reads the free space map218and identifies one or more blocks as unallocated even though the one or more blocks include data for the first file. As a result, the operating system202allocates one or more of the blocks containing data for the first file to a second file thereby creating cross-linked files. File data for the second file may overwrite the file data of the first file and vice versa causing a loss of data for at least one file.

FIG. 3illustrates an example of two cross-linked files, FILE A and FILE B. Each file includes control information216identifying data blocks 230 within a set of allocated data blocks. The blocks on the storage media are sequentially numbered to represent the offset from the beginning of the storage media volume.

As previously described, the control information216for each file includes file attributes232, such as the date the file was created and the file size. The control information216also includes other data such as user implementation data234. The control information216further includes information236identifying the blocks allocated to the file. In the example shown, the blocks allocated to the file are identified by one or more entries including a block number and a length. The block number identifies a starting block referenced from the beginning of storage media volume. The length identifies the total number of contiguous blocks, including the starting block, that include data for the file.

In the example shown, FILE A includes data starting at block50with a length of 100 blocks. Thus, FILE A purportedly includes data within blocks50through149. FILE A also includes data starting at block200with a length of 5 blocks, i.e. includes data at blocks200through204. The control information for FILE B indicates that it includes data at blocks25through34and blocks100through199. As shown inFIG. 3, both FILE A and FILE B claim blocks100-149, thus indicating cross-linking of FILE A and FILE B.

Returning toFIG. 2, when a volume of the storage media210is first accessed, for example, after the computer is turned on or after a new storage media210is inserted into the storage device208, the operating system202reads the status data218. If the status data218indicates that the disk is open, previous write transactions may not have been completed and the storage media210may include an inaccurate free space map218, cross-linked files or both. The operating system202notifies the user that the files on the storage media210may be corrupted.

Thereafter, the user elects to run a utility222that attempts to identify and resolve cross-linked files on the storage media210. The utility222reads the control information216for all of the files stored on the storage media210to determine whether any block on the storage media is allocated to more than one file. However, while the utility222is checking the storage media208for cross-linked files, other programs, such as application211cannot access the storage media204. Thus, when such known utilities are running, the computer200is generally unavailable to a user.

An example of the operating environment in which the present invention is utilized is depicted in FIG.4. Unlike the environment shown inFIG. 2, the operating system202includes a program250that facilitates detecting and correcting cross-linked files while, for example, application211, through the operating system202, accesses storage media210, e.g. sends a request to the storage device208to read data from or write data to the storage media210.

The program250maintains a secondary map252and examined file data254to facilitate the detection of cross-linked files. In an embodiment of the invention, the cross-linked file detection function only examines each file on the volume one time during a mount session. The examined files data254identifies files on the storage media210volume examined by the program250during a mount session. A mount session is the time during which the storage media210is accessible for read and write operations. For example, for a fixed hard disk, the mount session is the period of time that the computer is turned on. For removable media, such as a DVD disk, the mount session is the time during which the media is inserted into the storage device208.

During the mount session, the program250intercepts requests to access the storage media210from, for example, the application211. When the storage media210is first accessed during the mount session, the program250reads the status data220. If the status data220indicates that the storage media210is closed, the storage media210is accessed as previously described with reference to FIG.2. If, however, the status data210indicates that the storage media is open, one or more write transactions may not have been successfully completed with that volume and the storage media210may be corrupted. As a result, the program250enables a cross-linked file detection function.

When the cross-linked file detection function is enabled, and a file on the storage media210is accessed for the first time during the mount session, the program250reads the control information216to identify blocks on the storage media allocated to the file.

The program250then compares the blocks allocated to the file with the free space map218. If the control information216identifies any blocks allocated to the file that are identified as unallocated in the free space map218, the program250reconciles the free space map218and the control information216so that the control information216only identifies, as allocated to the file, blocks that are identified as allocated in the free space map218.

The secondary map252identifies blocks that that are allocated to any file on the volume that the program250has previously examined during the current mount session. The program250compares the allocation of the file, as reconciled with the free space map218, with the secondary map252. If any blocks allocated to the file are also identified as allocated in the secondary map, the file is cross-linked with at least one other file on the storage media210. The program250then further reconciles the control information216and the secondary map252so that the control information216does not identify any blocks, as allocated to the file, if those blocks are also identified by the secondary map252as allocated to another file. After the secondary map252and control information216for the file being examined are reconciled, as necessary, the secondary map252is updated. Specifically, any blocks identified in the control information216as being allocated to the file are set in the secondary map252as allocated.

After the control information216for the file is reconciled with the free space map218and the secondary map252, the program250updates the examined file data254. Specifically, the examined file data254is updated to indicate that the file has been examined.

It will be understood by those skilled in the art that, although the invention is shown as implemented in a single computer, the invention may be implemented in a computer network environment. For example, the program250may reside on a server and be used to detect cross-linked files on storage media210accessible by a client computer. It will further be understood that, although the secondary map252and examined file data254are illustratively shown as memory accessible by the operating system202, the secondary map252and examined objects data224may be stored in non-volatile memory, such as data on the storage media210.

The program250is, by way of example, implemented as any set of computer executable instructions. Although shown as part of the operating system202, the program250is alternatively implemented outside of the operating system. For example, the program252is implemented as an application211. The program250is also potentially implemented as a part of the file system driver204.

The secondary map252is implemented in any of a number of suitable ways. For example, the secondary map252is implemented as a bitmap. In the case of a bitmap, the secondary map252comprises a plurality of bits and each bit corresponds to a block on the storage media. A bit with a value of 1 in a particular bitmap portion means that the corresponding block is allocated to at least one file. A value of 0 means that the program250has not examined the control information216, since commencing the current mount session, for any file that identifies that block as allocated.

Alternatively, the secondary map252may is implemented as an extent list as shown in Table 1 below.

In the example shown in Table 1, the extent list includes a series of entries. Each entry includes a “Starting Block” and a “Length” corresponding to a set of contiguous blocks identified as allocated to a file examined by the program250. For example, the first entry identifies a set of 50 contiguous blocks, beginning with block100. Thus, the program250has examined a file with a block allocation including blocks100-149. The second entry identifies a set of 25 contiguous blocks beginning with block200. Thus, the program has examined a file that has a block allocation including blocks200-224.

The examined file data254is also implemented in any of a number of suitable ways. For example, when the program250examines a file on the storage media volume, the program250stores data in the control information216that tags the file as examined. Such information can, for example, be stored in the user implementation area234in the control information216(FIG.3).

The examined file data is also implemented as data identifying the control information216for each examined file. As previously described, the control information for each set of file data is stored on one or more blocks on the storage media208. The examined file data may include data that identifies the one or more block numbers on which the control information is stored.

Another method used to implement the examined file data by using existing memory structures. For example, in the case of the NTFS file system, the operating system creates a stream control block (SCB) in memory for each accessed file. Typically, the SCB is only maintained while the file is accessed. However, in one embodiment, the program252keeps all SCBs open for all files accessed on a volume until the mount session for that volume ends. Thus, any file that has a corresponding SCB has already been examined by the program250. Other similar memory structures are available for other file systems such as UDF. These structures are well known and need not be described further herein.

Alternatively, the secondary map252and examined files data254comprise a single set of data as shown, for example, in Table 2.

The data includes a series of entries. Each entry comprises a “Starting Block,” a corresponding “Length” and a “File Identifier.” The “Starting Block” and “Length” define a set of contiguous blocks allocated to the file. For example, the first entry includes a starting block of 50 and a length of 100. Thus, blocks50through149are allocated to at least one file. The “File Identifier” identifies files previously examined by program250during the current mount session by including data unique to the file. In the example, the file identifier is a block number of a block including control information216for the file having the corresponding blocks, as defined by the starting block and length, allocated to it. For example, the first entry includes a file identifier of 5000. Thus, the file having an allocation including blocks50through149has corresponding control information at block5000on the storage media208.

As illustrated in Table 1, a file may have more than one data entry. For example, the first two entries in the table both have control information216at block5000. Thus, the first two entries have the same control information216and the blocks identified as allocated by the first two entries are part of the same file.

FIG.5andFIG. 6illustrate an exemplary method that program250uses to detect and correct cross-linked files on the storage media volume210.

When a new volume of storage media210is first accessed during a mount session, for example after the computer is turned on or after a new storage media210is inserted into the storage device208, the program250reads the status data220as shown in step260. The program250then determines if the status of the storage media210is open or closed as shown at step262. If the status data220indicates that the storage media210status is “closed” all previous write transactions associated with the storage media210were completed and the cross-linked file detection function is disabled as shown at step264.

If the status data220indicates that the storage media210is “open” one or more pending write transactions may not have been completed during a previous mount session for that particular volume of storage media210. As a result, the storage media210may be corrupted. For example, one or more cross-linked files may be present on the storage media210or an inconsistency may exist between the free space map218and the control information216for one or more files. When the status data220indicates that the storage media is open, a cross-linked file detection mode of file access is enabled as shown in step266.

As shown in step268, after the cross-linked file detection function is enabled, the secondary map222is created. The secondary map222is initialized to identify each block on the storage media210as unallocated. For example, if the secondary map is implemented as a bitmap, each bit in the bitmap is initially set to a value of 0.

In step270, the examined file data254is created. As previously described, the examined file data254identifies files on the storage media previously examined by the program250during the current mount session.

FIG. 6illustrates the cross-linked file detection function, labeled278. The function278is carried out each time file data214on the storage media210is accessed. At step280, the program250intercepts a request, for example from an application, to access the file data214on the storage media210. The request is, for example, a request to read data from, or write data to, the storage media210.

The program250compares the file containing the file data to be accessed with the examined file data254to determine whether that file has been previously examined by the program250during the current mount session as shown at step282. If the file has been examined, the access request is processed by the operating system202and the sequence280terminates until another access request for the storage media volume is received, and the process begins again at step280.

If the file has not previously been examined, the program250reads the control information216corresponding to the file data214to identify the blocks allocated to the file as shown at step284. The blocks allocated to the file are then compared to the free space map218. The program250then determines if any blocks allocated to the file are identified as unallocated in the free space map218as shown in step286. If any blocks allocated to the file are marked unallocated in the free space map, the free space map218and control information216are reconciled as shown in step288. An exemplary process for reconciling the free space map218and control information216is described in more detail below Reconciling the control information216of the file and the free space map218prevents additional files on the storage media210from becoming cross-linked.

After the free space map218and control information216are reconciled, the program250proceeds to step290. During step290, the program250compares the secondary map252to the blocks allocated to the file, i.e. the blocks identified in the control information for the file. At step292, the program250determines if the file being examined is cross-linked with any previously examined file. If the program250determines that all of the blocks allocated to the file are identified as unallocated in the secondary map, the existence of cross-linked files is not detected (based upon the information currently available). The program250updates the secondary map to identify the blocks allocated to the file as allocated in the secondary map. For example, if the secondary map is implemented as a bitmap, each bit corresponding to an allocated block is set to a value of “1.”

If the program250determines, during step292, that one or more blocks allocated to the file are identified in the secondary map252as allocated, then at least two cross-linked files are known to exist since at least one other file has also identified the one or more blocks in its control information. The program250reconciles the secondary map252and the blocks allocated to the file as shown in step296. An exemplary method for reconciling the blocks allocated to the file216and the secondary map252is described in more detail below. After the blocks allocated to the file and the secondary map252are reconciled, the secondary map is updated as shown in step294as previously described. Specifically, the secondary map is updated to identify, as allocated, the blocks allocated to the file.

The program250next determines whether all files on the storage media volume have been examined as shown in step298. If all files have not been examined, the program250waits for the next access request and when the next access request is received, the program begins the process again at step280.

If, at step298, the program250determines that all files on the volume have been examined, the detection function280ends. As previously described, the process shown inFIG. 5begins when a new volume is accessed. Optionally, before terminating, the program250replaces the free space map218on the storage media with the secondary map252. Replacing the free space map218on the storage media frees any orphaned blocks. An orphaned block is a block that is identified in the free space map as allocated, but no file on the storage media has the block allocated to it.

Exemplary methods for reconciling the blocks allocated to the file and either the free space map218or the secondary map252will now be described. In one embodiment of the invention, when the program250reconciles the blocks allocated to the file and the free space map218as shown in step288(FIG.6), the program250truncates the blocks in the control information216of the file so that it does not identify any blocks identified in the primary map as unallocated. By way of example, assume that the control information for the file identifies blocks100-149, but the primary map identifies blocks140-149as unallocated. The program250truncates the control information216so that it identifies only blocks100-139as including data for the file.

A similar method is used to reconcile the blocks allocated to the file and the secondary map252, as shown in step296For example, assume that the control information216for a first file identifies blocks100-149as allocated to the file. However, the secondary map252identifies blocks100-125as allocated meaning that a previously examined second file on the storage media volume includes control information that identifies blocks100-125as allocated to the second examined file. The program truncates the control information for the first file to only identify blocks126-149.

As described with reference toFIG. 2, the allocation of a file236may comprise a series of entries and each entry may define a set of contiguous blocks allocated to the file. The program250only truncates the entries that conflict with the free space map218or the secondary map252.

In another embodiment of the invention, the program250reconciles the blocks allocated to the file and either the free space map218or the secondary map252by moving file data to a new set of blocks. When the program250identifies blocks allocated to a file but that are marked unallocated in the free space map218, the program250copies the data in the blocks identified by the free space map as unallocated to a new set of blocks. The program250then modifies the control information216so that it references the new set of blocks and modifies the primary map to identify the new set of blocks as allocated. For example, assume that the control information216for a first file identifies blocks100-149as including data for the first file, but the free space map identifies blocks145-149as unallocated. The free space map also identifies blocks160-164as unallocated. The program250copies the data from blocks145-149and stores the data in blocks160-164. The program then modifies the control information216for the first file to identify blocks100-144and160-164and removes blocks145-149from the file's allocation. The program250then updates the free space map218to identify blocks160-164as allocated.

A similar method is used to reconcile the blocks identified in the control information216for a file and the secondary map252. For example, assume that the control information216for a first file identifies blocks100-149as allocated to the file but that the secondary map identifies blocks100-125as also allocated to at least a second file. Assume also that the primary map identifies blocks200-225as unallocated. The program250copies the data from blocks100-125and stores the data in blocks200-225and modifies the first file's control information to identify blocks126-149and200-225while removing blocks100-125. The primary map is also updated to now identify blocks200-225as allocated.

All of the references cited herein, including are hereby incorporated in their entireties by reference.