Extending cluster allocations in an extensible file system

• US 8,452,729 B2
• Filed: 01/13/2011
• Issued: 05/28/2013
• 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, Revinder S., Zbikowski, Mark J., Goebel, David A.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/006,063
• Publication Number:
  US 20110113077A1
• Time in Patent Office: 866 Days
• Field of Search: 707/205, 707/826, 707/610, 707/614, 707/620
• 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. In a computing device that includes a storage medium and that implements a file system, a method performed by the computing device comprising:

storing on the storage medium information defining a file allocation table associated with the file system;

storing on the storage medium a first directory entry for specifying information concerning data in a directory of the file system, wherein the first directory entry includes a first flag that indicates whether the data is stored in a first contiguous cluster chain;

subsequently accessing the first directory entry;

determining from the first flag that the data is stored in the first contiguous cluster chain; and

identifying each cluster in the first contiguous cluster chain that stores the data based on other information within the first directory entry and without traversing the file allocation table,

the other information within the first directory entry comprising information specifying a starting cluster of the first contiguous cluster chain and a cluster chain size of the first contiguous cluster chain.

4. The method recited in claim 1, further comprising:

storing on the storage medium a second directory entry for specifying information concerning other data in the directory of the file system, wherein the second directory entry includes a second flag that indicates whether the other data is stored in a second contiguous cluster chain;

subsequently accessing the second directory entry;

determining from the second flag that the other data is not stored in the second contiguous cluster chain; and

identifying the other data by traversing the file allocation table.

5. The method recited in claim 1, further comprising:

setting the first flag to a value that indicates that the data is stored in the first contiguous cluster chain; and

storing as part of the first directory entry information specifying the starting cluster of the first contiguous cluster chain and the contiguous cluster chain size of the first contiguous cluster chain.

6. The method recited in claim 1, wherein the first directory entry comprises a primary directory entry, and wherein the method further comprises:

storing on the storage medium a secondary directory entry corresponding to the primary directory entry and defining meta data associated with the primary directory entry.

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

store on another storage medium information defining a file allocation table associated with a file system;

store on the another storage medium a first directory entry for specifying information concerning data in a directory of the file system, wherein the first directory entry includes a first flag that indicates whether the data is stored in a first contiguous cluster chain;

subsequently accessing the first directory entry;

determine from the first that the data is stored in the first contiguous cluster chain; and

identify each cluster in the first contiguous cluster chain that stores the data based on other information within the first directory entry and without traversing the file allocation table,

the other information within the first directory entry comprising information specifying a starting cluster of the first contiguous cluster chain and a cluster size of the first contiguous duster chain.

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

storing on the storage medium a second directory entry for specifying information concering other data in the directory of the file system, wherein the second directory entry includes a second flag that indicates whether the other data is stored in a second contiguous cluster chain;

subsequently access the second directory entry;

determine from the second flag that the data is not stored in the second contiguous cluster chain; and

identify the data by traversing the file allocation table.

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

set the first flag to a value that indicates that the data is stored in the first contiguous cluster chain; and

store as part of the first directory entry information specifying the starting cluster of the first contiguous cluster chain and the contiguous cluster chain size of the first contiguous cluster chain.

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

store on the storage medium a secondary directory entry corresponding to the primary directory entry and defining meta data associated with the primary directory entry.

3. A computing device having storage that stores computer-executable instructions and a processor for executing the instructions, the instructions, when executed by the processor, causing the device to perform operations comprising:

storing on the storage medium information defining a file allocation table associated with the file system;

storing on the storage medium a first directory entry for specifying information concerning data in a directory of the file system, wherein the first directory entry includes a first flag that indicates whether the data is stored in a first contiguous cluster chain;

subsequently accessing the first directory entry;

determining from the first flag that the data is stored in the first contiguous cluster chain;

identifying each cluster in the first contiguous cluster chain that stores the data based on other information within the first directory entry and without traversing the file allocation table,

the other information within the first directory entry comprising information specifying a starting cluster of the first contiguous cluster chain and a cluster chain size of the first contiguous cluster chain.

10. The computing device of claim 3, the operations further comprising:

storing on the storage medium a second directory entry for specifying information concerning other data in the directory of the file system, wherein the second directory entry includes a second flag that indicates whether the other data is stored in a second contiguous cluster chain;

subsequently accessing the second directory entry;

determining from the second flag that the other data is not stored in the second contiguous cluster chain; and

identifying the other data by traversing the file allocation table.

11. The computing device of claim 3, the operations further comprising:

setting the first flag to a value that indicates that the data is stored in the first contiguous cluster chain; and

storing as part of the first directory entry information specifying the starting cluster of the first contiguous cluster chain and the contiguous cluster chain size of the first contiguous cluster chain.

12. The computing device of claim 3, the operations further comprising:

the first directory entry comprising a primary directory entry; and

storing on the storage medium a secondary directory entry corresponding to the primary directory entry and defining meta data associated with the primary directory entry.