Extending cluster allocations in an extensible file system

• US 10,585,868 B2
• Filed: 12/15/2016
• Issued: 03/10/2020
• 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:
  US15/380,341
• Publication Number:
  US 20170322961A1
• Time in Patent Office: 1,181 Days
• Field of Search: 707607, 707609, 707687, 707705, 707790, 707813, 707821
• 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 implements a file system for storing data on a storage medium, the storage medium comprising a plurality of clusters, a method comprising:

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

storing, on the storage medium, an allocation bitmap comprising, for each cluster of the storage medium, an entry that indicates whether the cluster is allocated or is available for storage;

storing, on the storage medium, a directory entry specifying information concerning data in a directory of the file system, wherein the directory entry comprises a flag that indicates that the data is stored in a chain of contiguous clusters, the directory entry further comprising information specifying a starting cluster of the chain of contiguous clusters and information indicative of a size of the chain of contiguous clusters;

obtaining a request to delete the data;

determining from the flag in the directory entry for the data that the data is stored in the chain of contiguous clusters;

identifying the contiguous clusters of the chain based on the information from the directory entry specifying the starting cluster of the chain and indicative of the size of the chain, without traversing the file allocation table; and

updating the entries of the allocation bitmap corresponding to each of the identified clusters of the chain of contiguous clusters to indicate that each cluster is available for storage.

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

storing, on the storage medium, another directory entry specifying information concerning other data in the directory of the file system, wherein the another directory entry comprises a flag that indicates that the other data is stored in one or more clusters of the storage medium that are not contiguous;

obtaining a request to delete the other data;

determining from the flag in the another directory entry that the other data is not stored in contiguous clusters;

identifying the one or more non-contiguous clusters in which the other data is stored by traversing entries of the file allocation table corresponding to each of the one or more non-contiguous clusters; and

updating the entries of the allocation bitmap corresponding to each of the identified one or more non-contiguous clusters to indicate that each cluster is available for storage.

4. The method recited in claim 1, the updating the corresponding entries of the allocation bitmap comprising clearing the entries.

5. The method recited in claim 1, the identifying the contiguous clusters of the chain being further based on a size of each cluster.

6. The method recited in claim 1, the flag comprising a single bit.

7. The method recited in claim 1, the storage medium comprising a portable storage medium.

2. A computing device that implements a file system for storing data on a storage medium, the storage medium comprising a plurality of clusters, the computing device configured to:

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

store, on the storage medium, an allocation bitmap comprising, for each cluster of the storage medium, an entry that indicates whether the cluster is allocated or is available for storage;

store, on the storage medium, a directory entry specifying information concerning data in a directory of the file system, wherein the directory entry comprises a flag that indicates that the data is stored in a chain of contiguous clusters, the directory entry further comprising information specifying a starting cluster of the chain of contiguous clusters and information indicative of a size of the chain of contiguous clusters;

obtain a request to delete the data;

determine from the flag in the directory entry for the data that the data is stored in the chain of contiguous clusters;

identify the contiguous clusters of the chain based on the information from the directory entry specifying the starting cluster of the chain and indicative of the size of the chain, without traversing the file allocation table; and

update the entries of the allocation bitmap corresponding to each of the identified clusters of the chain of contiguous clusters to indicate that each cluster is available for storage.

8. The computing device of claim 2, further configured to:

store, on the storage medium, another directory entry specifying information concerning other data in the directory of the file system, wherein the another directory entry comprises a flag that indicates that the other data is stored in one or more clusters of the storage medium that are not contiguous;

obtain a request to delete the other data;

determine from the flag in the another directory entry that the other data is not stored in contiguous clusters;

identify the one or more non-contiguous clusters in which the other data is stored by traversing entries of the file allocation table corresponding to each of the one or more non-contiguous clusters; and

update the entries of the allocation bitmap corresponding to each of the identified one or more non-contiguous clusters to indicate that each cluster is available for storage.

9. The computing device of claim 2, the computing device configured to update the corresponding entries of the allocation bitmap by clearing the entries.

10. The computing device of claim 2, the computing device configured to identify the contiguous clusters of the chain based further on a size of each cluster.

11. The computing device of claim 2, the flag comprising a single bit.

12. The computing device of claim 2, the storage medium comprising a portable storage medium.