Extending cluster allocations in an extensible file system

• US 8,805,780 B2
• Filed: 05/24/2013
• Issued: 08/12/2014
• Est. Priority Date: 05/23/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pudipeddi, Ravisankar V., Ghotge, Vishal V., Havewala, Sarosh C., Thind, Ravinder S., Zbikowski, Mark J., Goebel, David A.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/901,997
• Publication Number:
  US 20130262379A1
• Time in Patent Office: 445 Days
• Field of Search: 707/610, 707/611, 707/614, 707/826
• US Class Current: 707/610
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• 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/18 File system types
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An extensible file system format for portable storage media is provided. The extensible file system format includes the specification of primary and secondary directory entry types that may be custom defined. The primary and secondary directory entry types can be further classified as critical and benign directory entries. The directory entry types can define whether a cluster chain corresponding to a file can be contiguously allocated.

Claims

1. A computer-readable storage medium on which computer-executable instructions are stored which, when executed by a computing device, cause the computing device to:

access a directory entry that specifies information concerning data in a file system, the directory entry containing a flag that indicates whether the data is stored in a contiguous chain of clusters;

determine that the data is stored in the contiguous cluster chain based on the flag; and

thereafter,

identify the clusters of the contiguous cluster chain that store the data without traversing a file allocation table associated with the file system based on other information, the other information comprising information within the directory entry specifying a starting cluster and information indicative of a size of the cluster chain.

2. The computer-readable storage medium recited in claim 1, wherein the computer-executable instructions further cause the computing device to:

access another directory entry for specifying information concerning other data in the file system;

determine that the other data is not stored in another contiguous cluster chain; and

identify the other data by traversing the file allocation table based on the determination that indicates the other data is not stored in the another contiguous cluster chain.

3. The computer-readable storage medium recited in claim 1, wherein the computer-executable instructions further cause the computing device to:

read the data in the file system by reading from the starting cluster to an ending cluster determined from the size of the cluster chain.

4. The computer-readable storage medium recited in claim 1, wherein the contiguous cluster chain is associated with a plurality of contiguously allocated clusters of a storage medium.

5. The computer-readable storage medium recited in claim 1, wherein the directory entry comprises a primary directory entry, and wherein the computer-executable instructions further cause the computing device to:

access a secondary directory entry for specifying information concerning data in a file system, the secondary directory entry corresponding to the primary directory entry and defining additional information associated with the primary directory entry.

6. A method performed by a computing device comprising:

accessing a directory entry for specifying information concerning data in a file system, the directory entry containing a flag that indicates whether the data is stored in a contiguous cluster chain;

determining that the data in the file system is stored in the contiguous cluster chain based on the flag;

obtaining starting cluster information and a cluster chain size associated with the plurality of contiguously allocated clusters; and

identifying each cluster in the contiguous cluster chain that stores the data in the file system without traversing a file allocation table associated with the file system based on the determination that the data is stored in the contiguous cluster chain, the starting cluster information, and the cluster chain size.

7. The method of claim 6, further comprising:

accessing another directory entry for specifying information concerning other data in the file system;

determining that the other data in the file system is not stored in another contiguous cluster chain; and

identifying the other data in the file system by traversing the file allocation table based on the determination that indicates the other data is not stored in the another contiguous cluster chain.

8. The method of claim 6, further comprising:

reading the data in the file system by reading from the starting cluster to an ending cluster determined from the cluster chain size.

9. The method of claim 6, wherein the contiguous cluster chain is associated with a plurality of contiguously allocated clusters of a storage medium.

10. The method of claim 6, wherein the directory entry comprises a primary directory entry, and wherein the method further comprises:

accessing a secondary directory entry for specifying information concerning data in a file system, the secondary directory entry corresponding to the primary directory entry and defining additional information associated with the primary directory entry.

11. A computing device comprising a processor and memory, the processor configured to:

access a directory entry that specifies information concerning data in a file system, the directory entry containing a flag that indicates whether the data is stored in a contiguous cluster chain;

determine that the data in the directory is stored in the contiguous cluster chain based on the flag; and

thereafter,

identify each cluster in the contiguous cluster chain that store the data without traversing a file allocation table associated with the file system based on other information, the other information comprising information within the directory entry specifying a starting cluster and information indicative of a size of the cluster chain.

12. The computing device of claim 11, wherein the processor is further configured to:

access another directory entry for specifying information concerning other data in the directory of the file system;

determine that the other data in the directory is not stored in another contiguous cluster chain; and

identify the other data in the directory by traversing the file allocation table based on the determination that indicates the other data is not stored in the another contiguous cluster chain.

13. The computing device of claim 11, wherein the processor is further configured to:

read the data in the directory by reading from the starting cluster to an ending cluster determined from the size of the cluster chain.

14. The computing device of claim 11, wherein the contiguous cluster chain is associated with a plurality of contiguously allocated clusters of a storage medium.

15. The computer-readable storage medium recited in claim 11, wherein the directory entry comprises a primary directory entry, and wherein the processor is further configured to:

access a secondary directory entry for specifying information concerning data in a file system, the secondary directory entry corresponding to the primary directory entry and defining additional information associated with the primary directory entry.