Extending cluster allocations in an extensible file system

• US 9,122,695 B2
• Filed: 08/11/2014
• Issued: 09/01/2015
• Est. Priority Date: 05/23/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (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:
  US14/456,419
• Publication Number:
  US 20140351299A1
• Time in Patent Office: 386 Days
• Field of Search: 707/610, 707/611, 707/614, 707/826
• US Class Current: 1/1
• 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 method, comprising:

obtaining a request for an extension of a plurality of clusters, the plurality of clusters comprising a cluster chain of two or more clusters stored contiguously, the extension comprising an additional allocation of one or more clusters to the cluster chain;

determining that the extension and the plurality of clusters are not contiguously allocatable;

allocating an entry in a file allocation table for each of the clusters of the plurality of clusters;

setting a flag to indicate that the plurality of clusters are not contiguously allocated;

allocating an entry in the file allocation table for each of the clusters of the extension; and

updating an allocation bitmap to indicate the allocation of the clusters for the plurality of clusters and the extension.

2. The method of claim 1 wherein determining that the extension and the plurality of clusters are not contiguously allocatable comprises locating a last cluster in the cluster chain by identifying a first cluster in the cluster chain and determining the cluster chain size.

3. The method of claim 2, further comprising referring to the allocation bitmap to determine whether contiguous clusters are available for the extension.

4. The method of claim 1 wherein before obtaining the request for the extension of the plurality of clusters, the flag indicates the plurality of clusters are contiguously allocated.

5. The method of claim 1 wherein the flag indicates the plurality of clusters and the extension are not contiguously allocated.

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

obtaining a request for an extension of a plurality of clusters, the plurality of clusters comprising a cluster chain of two or more clusters stored contiguously, the extension comprising an additional allocation of one or more clusters to the cluster chain;

determining that the extension and the plurality of clusters are not contiguously allocatable;

allocating an entry in a file allocation table for each of the clusters of the plurality of clusters;

setting a flag to indicate that the plurality of clusters are not contiguously allocated;

allocating an entry in the file allocation table for each of the clusters of the extension; and

updating an allocation bitmap to indicate the allocation of the clusters for the plurality of clusters and the extension.

7. The computer-readable storage medium of claim 6 wherein to determine that the extension and the plurality of clusters are not contiguously allocatable, the computer-executable instructions further cause the computing device to locate a last cluster in the cluster chain by identifying a first cluster in the cluster chain and determining the cluster chain size.

8. The computer-readable storage medium of claim 7, wherein the computer-executable instructions further cause the computing device to refer to the allocation bitmap to determine whether contiguous clusters are available for the extension.

9. The computer-readable storage medium of claim 6, wherein before the computer-executable instructions cause the computing device to obtain the request for the extension of the plurality of clusters, the flag indicates the plurality of clusters are contiguously allocated.

10. The computer-readable storage medium of claim 6 wherein the flag indicates the plurality of clusters and the extension are not contiguously allocated.

11. A computing device, comprising:

one or more computer-readable storage media on which computer-executable instructions are stored which, when executed by the computing device, cause the computing device to perform operations comprising;

obtaining a request for an extension of a plurality of clusters, the plurality of clusters comprising a cluster chain of two or more clusters stored contiguously, the extension comprising an additional allocation of one or more clusters to the cluster chain;

determining that the extension and the plurality of clusters are not contiguously allocatable;

allocating an entry in a file allocation table for each of the clusters of the plurality of clusters;

setting a flag to indicate that the plurality of clusters are not contiguously allocated;

allocating an entry in the file allocation table for each of the clusters of the extension; and

updating an allocation bitmap to indicate the allocation of the clusters for the plurality of clusters and the extension.

12. The computing device of claim 11 wherein to determine that the extension and the plurality of clusters are not contiguously allocatable, the computer-executable instructions further cause the computing device to locate a last cluster in the cluster chain by identifying a first cluster in the cluster chain and determining the cluster chain size.

13. The computing device of claim 12, wherein the computer-executable instructions further cause the computing device to refer to the allocation bitmap to determine whether contiguous clusters are available for the extension.

14. The computing device of claim 11, wherein before the computer-executable instructions cause the computing device to obtain the request for the extension of the plurality of clusters, the flag indicates the plurality of clusters are contiguously allocated.

15. The computing device of claim 11 wherein the flag indicates the plurality of clusters and the extension are not contiguously allocated.