FAT directory structure for use in transaction safe file system

• US 8,499,013 B2
• Filed: 09/19/2011
• Issued: 07/30/2013
• Est. Priority Date: 01/16/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Patel, Sachin, Gopalan, Yadhu, Rogers, Andrew
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US13/235,957
• Publication Number:
  US 20120011179A1
• Time in Patent Office: 680 Days
• Field of Search: 707/738, 707/826, 707/828, 707/829
• US Class Current: 707/828
• 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 storing a directory, the directory comprising a placeholder cluster having no transaction-safe data, a data cluster containing transaction-safe data, and an unused cluster;

a first file allocation table indicated to be a last known good file allocation table, the first file allocation table defining the placeholder cluster as a starting cluster in a sequence of data clusters for the directory, the placeholder cluster referencing the data cluster containing transaction-safe data;

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

one or more computer storage media storing computer readable instructions for;

initiating a transaction for modifying the data cluster containing transaction-safe data,

copying the data cluster containing transaction-safe data to the unused cluster, modifying the placeholder cluster in the second file allocation table to reference the unused cluster, and

retaining the first file allocation table as the last known good file allocation table when an interruption occurs before the transaction completes.

2. The computing device of claim 1 wherein the computer readable instructions comprise instructions for synchronizing the second file allocation table to the first file allocation table after the interruption.

3. The computing device of claim 1 wherein the transaction comprises moving the data cluster containing transaction-safe data.

4. The computing device of claim 3 wherein the directory comprises a root directory and the data cluster containing transaction-safe data is moved to a subdirectory of the root directory.

5. The computing device of claim 1 wherein the transaction comprises modifying data in the data cluster containing transaction-safe data.

6. The computing device of claim 1 wherein the transaction comprises writing data to the data cluster containing transaction-safe data.

7. The computing device of claim 1 wherein the transaction comprises deleting data from data cluster containing transaction-safe data.

8. The computing device of claim 1 further comprising:

a first bitmap image associated with the first file allocation table, the first bitmap image indicated to be a last known good bitmap image;

a second bitmap image comprising a copy of the first bitmap image.

9. The computing device of claim 8, wherein the computer readable instructions comprise instructions for:

modifying the second bitmap image in response to modifying the placeholder cluster in the second file allocation table, and

retaining the first bitmap image as the last known good bitmap image when the interruption occurs before the file modification transaction completes.

10. A method comprising:

storing a directory in a data storage device, the directory comprising a placeholder cluster having no transaction-safe data, a data cluster containing transaction-safe data, and an unused cluster;

indicating a first file allocation table as a last known good file allocation table, the first file allocation table defining the placeholder cluster as a starting cluster in a sequence of data clusters for the directory, the placeholder cluster referencing the data cluster containing transaction-safe data;

synchronizing a second file allocation table to the first file allocation table resulting in the second file allocation table comprising a copy of the first file allocation table;

initiating a transaction for modifying the data cluster containing transaction-safe data;

copying the data cluster containing transaction-safe data to the unused cluster;

modifying the placeholder cluster in the second file allocation table to reference the unused cluster; and

retaining the first file allocation table as the last known good file allocation table when an interruption occurs before the file modification transaction completes.

11. The method of claim 10 further comprising synchronizing the second file allocation table to the first file allocation table after the interruption.

12. The method of claim 10 wherein the transaction comprises one or more of:

moving the data cluster containing transaction-safe data,

modifying data in the data cluster containing transaction-safe data,

writing data to the data cluster containing transaction-safe data, and deleting data from data cluster containing transaction-safe data.

13. The method of claim 10 further comprising:

indicating a first bitmap image associated with the first file allocation table to be a last known good bitmap image; and

synchronizing a second bitmap image to the first bitmap image resulting in the second bitmap image comprising a copy of the first bitmap image.

14. The method of claim 13 further comprising:

modifying the second bitmap image in response to modifying the placeholder cluster in the second file allocation table; and

retaining the first bitmap image as the last known good bitmap image when the interruption occurs before the file modification transaction completes.

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

16. A computer-readable storage medium having computer readable instructions that, when executed on at least one processor, configure the at least one processor to perform a method, the method comprising:

synchronizing a first file allocation table and a second file allocation table resulting in the second file allocation table comprising a copy of the first file allocation table, the first file allocation table indicated as a last known good file allocation table, the first file allocation table defining a directory in a file system, the directory comprising a first data cluster having no transaction-safe data and a subsequent data cluster containing transaction-safe data, the first file allocation table further defining a location for the first data cluster, the location for the first data cluster storing an address for the second data cluster;

initiating a transaction for modifying the second data cluster;

determining that a third data cluster in the directory is currently not allocated;

copying the second data cluster to the third data cluster;

modifying the second file allocation table to update the address for the second data cluster to an address for the third data cluster; and

retaining the first file allocation table as the last known good file allocation table when an interruption occurs before the transaction completes.

17. The A computer-readable storage medium of claim 16 further comprising:

synchronizing a first bitmap image associated with the first file allocation table and a second bitmap image associated with the second file allocation table, the first bitmap image and the second bitmap image identically indicating allocated clusters of the file system, the first bitmap image indicated as a last known good bitmap image.

18. The A computer-readable storage medium of claim 17 further comprising:

changing the second bitmap image to indicate that the second data cluster is not allocated and that the third data cluster is allocated; and

retaining the first bitmap image as the last known good bitmap image when the interruption occurs before the transaction completes.

19. The A computer-readable storage medium

moving the second data cluster, modifying data in the second data cluster, writing data to the second data cluster, and deleting data from second data cluster.