Fat directory structure for use in transaction safe file

• US 8,024,383 B2
• Filed: 11/02/2009
• Issued: 09/20/2011
• Est. Priority Date: 01/16/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rogers, Andrew, Gopalan, Yadhu, Patel, Sachin
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US12/611,046
• Publication Number:
  US 20100049776A1
• Time in Patent Office: 687 Days
• Field of Search: 707/611, 707/828, 707/999.205, 707/821, 711 1- 2, 711/100, 711/170, 711/206
• US Class Current: 707/821
• 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 computing device, comprising:

a data storage device comprising a directory, the directory comprising at least two data clusters including a first data 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 the directory, the placeholder cluster referencing a next data cluster in the sequence that comprises transaction-safe data;

a second file allocation table, the second file allocation table comprising a copy of the first file allocation table; and

one or more computer storage media including computer readable instructions that when executed perform operations comprising;

modifying a third data cluster of the data storage device to contain modified transaction-safe data of the directory,

modifying the second file allocation table to reference the third data cluster in the sequence of transaction-safe data while retaining the placeholder cluster in the second file allocation table as the starting cluster in the sequence of data clusters for the directory, and

after modifying the second file allocation table and after the modifying the third data cluster, modifying a last known good indicator (LKG indicator) to indicate a last known good file allocation table.

2. The computing device of claim 1 wherein the directory for which transaction-safe data is modified comprises a root directory.

3. The computing device of claim 1 wherein the computer readable instructions further perform operations comprising:

after the modifying the LKG indicator, synchronize the first file allocation table with the second file allocation table.

4. The computing device of claim 1 wherein the data storage device comprises a second directory, wherein the computer readable instructions further perform operations comprising moving the second directory.

5. The computing device of claim 1 wherein the last known good file allocation table is the second file allocation table.

6. The computing device of claim 5 wherein the computer readable instructions further perform operations comprising:

after modifying the LKG indicator to indicate the last known good file allocation table is the second file allocation table, synchronize the first file allocation table with the second file allocation table.

7. The computing device of claim 6 wherein the computer readable instructions further perform operations comprising:

after the first file allocation table is synchronized with the second file allocation table, modify the LKG indicator to indicate the first file allocation table is the last known good file allocation table.

8. The computing device of claim 1, further comprising:

a first bitmap image indicating which clusters are allocated; and

a second bitmap image being synchronized with the first bitmap image, the LKG indicator further adapted to indicate a last known good bitmap image.

9. The computing device of claim 1 wherein the third data cluster is a second cluster in the sequence of data clusters for the directory.

10. The computing device of claim 1 wherein the LKG indicator is selected from a group consisting of a flag and a pointer.

11. A computing device, comprising:

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

a plurality of directories, a first directory of the plurality of directories comprising at least two data clusters including a first data cluster having no transaction-safe data and at least one remaining data cluster comprising transaction-safe data;

a second file allocation table as a synchronized copy of the first file allocation table;

a first bitmap image indicating which clusters are allocated;

a second bitmap image as a synchronized copy of the first bitmap image;

a last known good indicator (LKG indicator) of a last known good file allocation table, the LKG indicator being further adapted to indicate a last known good bitmap image; and

one or more computer storage media including computer readable instructions that when executed perform operations comprising;

modifying the first directory by operations comprising;

determining a third data cluster is unused;

storing a change to the transaction-safe data of the at least one remaining data cluster in the third data cluster;

updating the second file allocation table to reflect the change by modifying the second file allocation table to reference the third data cluster via the sequence of data storage clusters, while retaining a placeholder cluster in the second file allocation table as a starting cluster;

updating the second bitmap image to reflect the change; and

after storing the change, updating the second file allocation table and updating the second bitmap image, setting the LKG indicator to indicate the second file allocation table as the last known good file allocation table and the second bitmap image as the last known good bitmap image.

12. The computing device of claim 11 wherein the computer readable instructions further perform operations comprising

synchronizing the first file allocation table with the second file allocation table;

and

synchronizing the first bitmap image with the second bitmap image.

13. The computing device of claim 11 wherein storing the change in the third unused cluster occurs prior to the updating the second file allocation table to reflect the change.

14. The computing device of claim 11 wherein updating the second file allocation table further comprises updating the placeholder cluster to reference the third data cluster as the next data cluster in the sequence of data storage clusters that comprises transaction-safe data.

15. The computing device of claim 11 wherein the LKG indicator is selected from the group consisting of a flag and a pointer.

16. A computing device, comprising:

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

a first file allocation table adapted to define a sequence of data storage clusters, the first file allocation table comprising a placeholder cluster as a starting cluster of the first directory, the placeholder cluster referencing a next cluster in the sequence;

a second file allocation table, the second file allocation table comprising a copy of the first file allocation table;

a last known good indicator (LKG indicator) of a last known good file allocation table, the LKG indicator indicating the first file allocation table is the last known good file allocation table; and

one or more computer storage media including computer readable instructions that when executed perform operations comprising;

modifying the first directory by operations comprising;

determining a next data cluster is an unallocated data cluster;

making a change to the transaction-safe data of the at least one remaining data cluster in the next data cluster;

modifying the second file allocation table to define the next data cluster as part of the at least one remaining data cluster comprising transaction-safe data for the directory while retaining the first placeholder cluster in the second file allocation table as a starting cluster; and

updating the first file allocation table to reflect the change by synchronizing with the second file allocation table.

17. A method, comprising:

determining a first file allocation table is a last known good file allocation table;

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

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

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

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

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

after completing the change, the modifying a last known good indicator (LKG indicator) to indicate the second file allocation table as a last known good file allocation table.

18. The method of claim 17 wherein the synchronizing operation occurs after the modifying operation.

19. The method of claim 17, further comprising:

defining a first bitmap image designating which clusters are allocated; and

synchronizing a second bitmap image with the first bitmap image, the LKG indicator being further adapted to indicate a last known good bitmap image.

20. A method, comprising:

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

storing an address for the second data cluster in a placeholder cluster in a first file allocation table, the first file allocation table defines a sequence of data clusters, the placeholder cluster being stored in a location for the first data cluster in the first file allocation table;

defining a first bitmap image designating which clusters are allocated within the file system;

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

synchronizing a second bitmap image with the first bitmap image;

modifying a last known good indicator (LKG indicator) to indicate that the first file allocation table is a last known good file allocation table, the LKG indicator being further adapted to indicate a last known good bitmap image;

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

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

updating the second bitmap image to reflect the change;

after completing the change, setting the LKG indicator to indicate the second file allocation table is the last known good file allocation table and the second bitmap image is the last known good bitmap image.

21. A method, comprising:

synchronizing a first file allocation table (FAT) with a second FAT, the first FAT defining a directory in a file system, the directory comprising a first data cluster having no transaction-safe data and a subsequent second data cluster having transaction-safe data, the first FAT further defining a placeholder cluster as a starting cluster in a sequence of data clusters for the directory, the placeholder cluster comprising a second address for the second data cluster, the placeholder cluster defining the second address as a next data cluster in the sequence of data clusters for the directory;

updating the second data cluster by creating a third data cluster having a third address;

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

modifying a last known good indicator (LKG indicator) to indicate the second file allocation table is a last known good file allocation table.

22. A method, comprising:

synchronizing a second file allocation table (FAT) with a first FAT, the first FAT defining a directory in a file system, the directory comprising a first data cluster having no transaction-safe data and a subsequent second data cluster having transaction-safe data, the first FAT further defining a location for the first data cluster, the location for the first cluster storing a second address for the second data cluster;

synchronizing a second bitmap image with a first bitmap image, the bitmap images designating which clusters are allocated within the file system;

determining a third data cluster is currently not allocated;

updating the second cluster by using the third data cluster having a third address;

updating the second address in the second FAT to the third address;

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

changing the second bitmap image to indicate the second cluster is not used;

modifying a last known good indicator (LKG indicator) to indicate the second file allocation table is a last known good file allocation table and the second bitmap image is a last known good bitmap image.