FAT directory structure for use in transaction safe file system

• US 7,613,738 B2
• Filed: 01/16/2007
• Issued: 11/03/2009
• Est. Priority Date: 01/16/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rogers, Andrew, Patel, Sachin, Gopalan, Yadhu
• Primary Examiner(s): Le; Debbie M
• Application Number:
  US11/653,585
• Publication Number:
  US 20080172425A1
• Time in Patent Office: 1,022 Days
• Field of Search: 707200-204, 711/170, 711/206, 714/19
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1865 Transactional file systems

Abstract

Directories in a file system are defined with a dummy cluster in a file allocation table as the initial entry. Subsequent clusters in a directory'"'"'s definition may define any data for the directory that can be changed in a transaction-safe mode. A directory may be modified in a transaction-safe mode by modifying any of the subsequent clusters while tracking changes in a second file allocation table. When the changes have been made to the directory, a pointer to the second file allocation table may be switched to indicate that the second file allocation table is now last known good. The first file allocation table may then be synchronized with the second.

Claims

1. A system comprising:

a data storage device to store data in a plurality of directories, each of said directories comprising at least two data clusters;

a first cluster having no transaction-safe data and at least one remaining data cluster comprising transaction-safe data;

a first file allocation table that defines a placeholder cluster as a starting cluster in a sequence of data clusters for a directory, said placeholder cluster referencing a next data cluster in said sequence that comprises transaction-safe data;

a second file allocation table being a synchronized copy of said first file allocation table; and

a processor to modify transaction-safe data of said directory using said first cluster of said directory, modify said second file allocation table to reference said first cluster of said directory while retaining said placeholder cluster in said second file allocation table as said starting cluster in said sequence of data clusters for said directory, and set a pointer to one of said first file allocation table and said second file allocation table after modifying said transaction-safe data to indicate a last known good file allocation table.

2. The system of claim 1 wherein said directory for which transaction-safe data is modified comprises a root directory.

3. The system of claim 1 wherein said processor sets said pointer to said second file allocation table and synchronizes said first file allocation table to said second file allocation table.

4. The system of claim 1 wherein said processor moves one of said directories.

5. The system of claim 1 wherein said processor sets said pointer to said first file allocation table after synchronizing said first file allocation table to said second file allocation table.

6. The system of claim 1 wherein said processor makes a change to one of said at least one remaining data cluster and updates said first file allocation table to reflect said change.

7. The system of claim 1 further comprising:

a first bitmap image having at least one bit allocated for each of said data storage clusters; and

a second bitmap image being synchronized with said first bitmap image, said pointer being further adapted to point to a last known good bitmap image.

8. A system comprising:

a first file allocation table adapted to define a sequence of data storage clusters;

a plurality of directories, each of said directories comprising at least two data clusters;

a first cluster having no transaction-safe data and at least one remaining data cluster comprising transaction-safe data;

a second file allocation table being a synchronized copy of said first file allocation table;

a first bitmap image having at least one bit allocated for each of said data storage clusters;

a second bitmap image being synchronized with said first bitmap image;

a pointer to a last known good file allocation table, said pointer being further adapted to point to a last known good bitmap image; and

a processor adapted to modify one or more of said directories by a method comprising;

making a change to said transaction-safe data of said at least one remaining data cluster using said first cluster;

updating said second file allocation table to reflect said change by modifying said second file allocation table to reference said first cluster while retaining a placeholder cluster in said second file allocation table as a starting cluster, said placeholder cluster referencing a next data cluster in said sequence of data storage clusters that comprises transaction-safe data;

updating said second bitmap image to reflect said change;

after completing said change, setting said pointer to said second file allocation table and said second bitmap image;

synchronizing said first file allocation table to said second file allocation table; and

synchronizing said first bitmap image to said second bitmap image.

9. A system comprising:

a first file allocation table adapted to define a sequence of data storage clusters;

a plurality of directories, each of said directories comprising at least two data clusters;

a first cluster having no transaction-safe data and at least one remaining data cluster comprising transaction-safe data;

a second file allocation table being a synchronized copy of said first file allocation table;

a first bitmap image having at least one bit allocated for each of said data storage clusters;

a second bitmap image being synchronized with said first bitmap image;

a pointer to a last known good file allocation table, said pointer being further adapted to point to a last known good bitmap image; and

a processor adapted to modify one or more of said directories by a method comprising;

setting said pointer to said first file allocation and said first bitmap image;

making a change to said transaction-safe data of said at least one remaining data cluster using said first cluster;

modifying said second file allocation table to reference said first cluster while retaining a placeholder cluster in said second file allocation table as a starting cluster, said placeholder cluster referencing a next data cluster in said sequence that comprises transaction-safe data;

updating said first file allocation table to reflect said change by synchronizing to said second file allocation table; and

updating said first bitmap image to reflect said change.

10. A method comprising:

storing a directory in a file system on a computing device by creating a first cluster having no transaction-safe data and a subsequent second cluster comprising transaction-safe data;

storing a first address for said second cluster in a first file allocation table that defines a placeholder cluster as a starting cluster in a sequence of data clusters for said directory, said placeholder cluster referencing said first address as a next data cluster in said sequence of data clusters for said directory;

synchronizing said first file allocation table with a second file allocation table;

toggling a pointer to indicate that said first file allocation table is a known good file allocation table;

making a change to said transaction-safe data using said first cluster of said directory;

updating said second file allocation table to reflect said change by modifying said second file allocation table to reference said first cluster of said directory while retaining said placeholder cluster in said second file allocation table as said starting cluster in said sequence of data clusters for said directory;

after completing said change, setting said pointer to said second file allocation table; and

synchronizing said first file allocation table to said second file allocation table.

11. The method of claim 10 wherein said directory is a root directory.

12. The method of claim 10 wherein said change comprises moving said directory.

13. The method of claim 10 further comprising:

defining a first bitmap image having at least one bit assigned for each data storage cluster within said file system; and

synchronizing a second bitmap image with said first bitmap image, said pointer being further adapted to point to a last known good bitmap image.

15. A computer readable storage media comprising computer executable instructions causing a computer to perform the method of claim 11.

14. A method comprising:

storing a directory in a file system on a computing device by creating a first cluster having no transaction-safe data and a subsequent second cluster comprising transaction-safe data;

storing a first address for said second cluster in a first file allocation table that defines a sequence of data storage clusters, said first address being stored in a location for said first cluster;

defining a first bitmap image having at least one bit assigned for each data storage cluster within said file system;

synchronizing said first file allocation table with a second file allocation table;

synchronizing a second bitmap image with said first bitmap image;

toggling a pointer to indicate that said first file allocation table is a known good file allocation table, said pointer being further adapted to point to a last known good bitmap image;

making a change to said transaction-safe data using said first cluster;

updating said second file allocation table to reflect said change by modifying said second file allocation table to reference said first cluster while retaining a placeholder cluster in said second file allocation table, said placeholder cluster referencing said first address as a next data cluster in said sequence of data storage clusters;

updating said second bitmap image to reflect said change;

after completing said change, setting said pointer to said second file allocation table and said second bitmap image;

synchronizing said first file allocation table to said second file allocation table; and

synchronizing said first bitmap image to said second bitmap image.

20. A computer readable storage media comprising computer executable instructions causing a computer to perform the method of claim 14.

16. A method comprising:

storing a directory in a file system on a computing device by creating a first cluster having no transaction-safe data and a subsequent second cluster comprising transaction-safe data;

storing a first address for said subsequent second cluster in a first file allocation table that defines a placeholder cluster as a starting cluster in a sequence of data clusters for said directory, said placeholder cluster referencing said first address as a next data cluster in said sequence of data clusters for said directory;

synchronizing said first file allocation table with a second file allocation table;

setting a pointer to indicate that said first file allocation table is a last known good file allocation table;

updating said second cluster by creating a third cluster having a second address;

updating said first address referenced by said placeholder in said second file allocation table to said second address while retaining said placeholder cluster in said second file allocation table as said starting cluster in said sequence of data clusters for said directory;

toggling said pointer to indicate said second file allocation table is a last known good file allocation table; and

updating said first file allocation table to said second file allocation table.

17. The method of claim 16 wherein said directory is a root directory.

19. A computer readable storage media comprising computer executable instructions causing a computer to perform the method of claim 16.

18. A method comprising:

storing a directory in a file system on a computing device by creating a first cluster having no transaction-safe data and a subsequent second cluster comprising transaction-safe data;

storing a first address for said subsequent second cluster in a first file allocation table, said first address being stored in a location for said first cluster;

synchronizing said first file allocation table with a second file allocation table;

defining a first bitmap image having at least one bit assigned for each data storage cluster within said file system;

synchronizing a second bitmap image with said first bitmap image;

setting a pointer to indicate that said first file allocation table is a last known good file allocation table, said pointer being further adapted to point to a last known good bitmap image;

updating said second cluster by creating a third cluster having a second address;

updating said first address in said second file allocation table to said second address;

changing said second bitmap image to indicate said third cluster is used;

changing said second bitmap image to indicate said subsequent cluster is not used;

toggling said pointer to indicate said second file allocation table is a last known good file allocation table;

setting said pointer to further indicate said second bitmap image is last known good;

updating said first file allocation table to said second file allocation table; and

synchronizing said first bitmap image to said second bitmap image.

21. A computer readable storage media comprising computer executable instructions causing a computer to perform the method of claim 18.