Contiguous file allocation in an extensible file system

• US 10,303,650 B2
• Filed: 01/20/2017
• Issued: 05/28/2019
• Est. Priority Date: 12/17/2004
• 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., Thind, Ravinder S., Goebel, David A.
• Primary Examiner(s): Pyo, Monica M
• Application Number:
  US15/411,376
• Publication Number:
  US 20170132218A1
• Time in Patent Office: 858 Days
• Field of Search: 707821, 707770, 707620
• 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/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• 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

Abstract

Disclosed is a method for creating and reading a contiguous file in an extensible file system. During the creation of a file on the storage media, the file system format check the bitmap to determine if there are areas of free space on the media that would permit the storage of the file in a contiguous manner. By storing the file in a contiguous manner the file may later be read without resorting to the file allocation table, because the file itself would not be fragmented on the storage media. Once an area of free space has been identified, the file is written to the media in a contiguous manner. Further, an associated entry for the file in the directory entry is updated or created to indicate that the file is a contiguous file and also provides basic parameters necessary to read the file without resorting to accessing the file allocation table.

Claims

1. A computing device comprising:

a non-transitory computer readable storage medium that stores information within a volume on the non-transitory computer readable storage medium, the volume comprising;

a plurality of directory entries, each of the plurality of directory entries containing information designating the directory entry as either a primary directory entry or a secondary directory entry, each secondary directory entry being associated with a primary directory entry, and each of the primary and secondary directory entries being typed and including a type designation that identifies the type of the directory entry, at least some of the primary and secondary directory entries being associated with a respective file stored on the volume and containing a flag that indicates whether or not data of the respective file is stored in one or more contiguous clusters on the volume; and

a file system, the file system;

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

storing the data of a file in one or more contiguous clusters on the storage medium;

storing on the storage medium at least one directory entry associated with the file;

setting a flag contained in said at least one directory entry to a value that indicates that the data of the file associated with that directory entry is stored in the one or more contiguous clusters;

storing as part of said at least one directory entry information specifying a starting cluster of the one or more contiguous clusters and information indicating a size of the one or more contiguous clusters;

receiving an indication that the file is to be read from the storage medium;

accessing the at least one directory entry that is associated with the file that is to be read;

determining from the flag contained in the at least one directory entry that the data of the file associated with that directory entry is stored in one or more contiguous clusters on the volume;

in response to determining from the flag that the data of the file associated with the at least one directory entry is stored in one or more contiguous clusters, identifying each cluster of the one or more contiguous clusters based on other information within the at least one directory entry and without traversing the file allocation table, the other information within the at least one directory entry comprising the information specifying the starting cluster of the one or more contiguous clusters and the information indicating the size of the one or more contiguous clusters; and

reading the data of the file from the identified clusters.

2. The computing device recited in claim 1, the file system:

accessing a second directory entry stored on the storage medium, the second directory entry being associated with a different file stored on the storage medium;

determining from the flag contained in the second directory entry that data of the file associated with that second directory entry is not stored in one or more contiguous clusters on the volume; and

identifying the data of the file associated with the second directory entry by traversing the file allocation table.

3. The computing device recited in claim 1, the information indicating a size of the one or more contiguous clusters comprising a value specifying a size of the file associated with the one directory entry.

4. The computing device recited in claim 1, each secondary directory entry extending metadata associated with the primary directory entry with which the secondary directory entry is associated.

5. The computing device recited in claim 1, the type designation comprising a type value that identifies the type of the directory entry.

6. The computing device recited in claim 1, the file allocation table storing, for any file that does not have its data stored in one or more contiguous clusters, an indication of the non-contiguous chain of clusters that store the data of that file.

7. In a computing device comprising a non-transitory computer readable storage medium that stores information within a volume on the computer readable storage medium, the volume comprising a plurality of directory entries, each of the plurality of directory entries containing information designating the directory entry as either a primary directory entry or a secondary directory entry, each secondary directory entry being associated with a primary directory entry, and each of the primary and secondary directory entries being typed and including a type designation that identifies the type of the directory entry, at least some of the primary and secondary directory entries being associated with a respective file stored on the volume and containing a flag that indicates whether or not data of the respective file is stored in one or more contiguous clusters on the volume, a method comprising:

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

storing the data of a file in one or more contiguous clusters on the storage medium;

storing on the storage medium at least one directory entry associated with the file;

setting a flag contained in said at least one directory entry to a value that indicates that the data of the file associated with that directory entry is stored in the one or more contiguous clusters;

storing as part of said at least one directory entry information specifying a starting cluster of the one or more contiguous clusters and information indicating a size of the one or more contiguous clusters;

receiving an indication that the file is to be read from the storage medium;

accessing the at least one directory entry that is associated with the file that is to be read;

determining from the flag contained in the at least one directory entry that the data of the file associated with that directory entry is stored in one or more contiguous clusters on the volume;

in response to determining from the flag that the data of the file associated with the at least one directory entry is stored in one or more contiguous clusters, identifying each cluster of the one or more contiguous clusters based on other information within the at least one directory entry and without traversing the file allocation table, the other information within the at least one directory entry comprising the information specifying the starting cluster of the one or more contiguous clusters and the information indicating the size of the one or more contiguous clusters; and

reading the data of the file from the identified clusters.

8. The method recited in claim 7, further comprising:

accessing a second directory entry stored on the storage medium, the second directory entry being associated with a different file stored on the storage medium;

determining from the flag contained in the second directory entry that data of a file associated with that second directory entry is not stored in one or more contiguous clusters on the volume; and

identifying the data of the file associated with the second directory entry by traversing the file allocation table.

9. The method recited in claim 7, the information indicating a size of the one or more contiguous clusters comprising a value specifying a size of the file associated with the one directory entry.

10. The method recited in claim 7, each secondary directory entry extending metadata associated with the primary directory entry with which the secondary directory entry is associated.

11. The method recited in claim 7, the type designation comprising a type value that identifies the type of the directory entry.

12. The method recited in claim 7, further comprising storing in the file allocation table, for any file that does not have its data stored in one or more contiguous clusters, an indication of the non-contiguous chain of clusters that store the data of that file.