US6023744A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and mechanism for freeing disk space in a file system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-03-07
•
Granted: 2000-02-08
•
Expires: 2017-03-07
Abstract
Abstract A method and mechanism for rapidly freeing storage space allocated to any logical portion of a file. An application program provides the file system with information indicating a block of logical data to free. The file system converts the information to the physical allocation units such as the clusters corresponding to the logical block of data, and manipulates the file's meta data to indicate that the physical space is no longer allocated to the file. The file system then adds the space to disk free space. Applications such as merge applications and those managing FIFO queues may use the method and mechanism to shrink a file from the start of the file toward the end thereof without copying the logical data or adjusting internal pointers relative to the logical file data.
Inventors
- 👤 Srikanth Shoroff
- 👤 Kyle G. Peltonen
- 👤 Brian T. Berkowitz
- 👤 Mark J. Zbikowski
- 👤 Bartosz B. Milewski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 06:17
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0638; G06F3/0644; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G11; G11B; G11B20/00; G11B20/10; G11B20/12; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99956
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
126 words
A method of freeing storage space allocated to a file in a persistent storage medium wherein a file system maintains mapping data associating the file with physical storage space locations in the storage medium, comprising: providing the file system with information identifying the file and a selected logical block of data in the file that does not include a logical end of the data; receiving the information at the file system and accessing the mapping data to determine at least one physical location in the persistent storage medium corresponding to the selected logical block of data; and modifying the mapping data in the file system independent of a data write to indicate that the at least one physical location is no longer allocated to the file.
Claim 2
Independent Claim
126 words
A method of freeing storage space allocated to a file in a persistent storage medium wherein a file system maintains mapping data associating the file with physical storage space locations in the storage medium, comprising: providing the file system with information identifying the file and a selected logical block of data in the file that does not include a logical end of the data; receiving the information at the file system and accessing the mapping data to determine at least one physical location in the persistent storage medium corresponding to the selected logical block of data; and modifying the mapping data in the file system independent of a data write to indicate that the at least one physical location is no longer allocated to the file.
Claim 3
Dependent Claim
59 words
The method of claim 1 wherein the at least one physical location has a first indicator in the mapping data corresponding to the identity thereof, and modifying the mapping data in the file system comprises writing a second indicator in the mapping data in place of the first indicator and maintaining the second indicator in association with the file.
Claim 4
Dependent Claim
45 words
The method of claim 1 wherein the file system maintains free space information representing physical locations that are free space not allocated to any file, and further comprising modifying the free space information to indicate that the at least one physical location is free space.
Claim 5
Dependent Claim
49 words
The method of claim 3 wherein the free space information is maintained in a bitmap having bits corresponding to the physical locations on the disk, and wherein modifying the free space information comprises changing the value of at least one bit corresponding to the at least one physical location.
Claim 6
Dependent Claim
18 words
The method of claim 1 further comprising determining a fixed size for the selected logical block of data.
Claim 7
Dependent Claim
18 words
The method of claim 1 wherein providing the file system with information includes calling an application programming interface.
Claim 8
Dependent Claim
24 words
The method of claim 1 wherein providing the file system with information identifying the file includes providing a file handle to the file system.
Claim 9
Dependent Claim
30 words
The method of claim 1 wherein providing the file system with information identifying the logical block of data includes providing a size value representative of a size of the block.
Claim 10
Dependent Claim
39 words
The method of claim 8 wherein the size value is a number of bytes, and receiving the information at the file system and accessing the mapping data includes converting the number of bytes to a number of allocation units.
Claim 11
Dependent Claim
34 words
The method of claim 1 wherein providing the file system with information identifying the logical block of data includes providing an offset value representative of a logical location of the block within the file.
Claim 12
Dependent Claim
37 words
The method of claim 10 wherein the offset value is a number of bytes, and receiving the information at the file system and accessing the mapping data includes converting the logical location to a particular allocation unit.
Claim 13
Dependent Claim
28 words
The method of claim 1 wherein the mapping data for the file is maintained within a record corresponding to the file in a master file table of records.
Claim 14
Dependent Claim
28 words
The method of claim 1 wherein the allocation units are clusters, and wherein the mapping data for the file is maintained within an extent list of cluster runs.
Claim 15
Dependent Claim
24 words
The method of claim 1 wherein the allocation units are clusters, and wherein the mapping data is maintained within a block list of clusters.
Claim 16
Dependent Claim
32 words
The method of claim 1 wherein providing the file system with information identifying a selected logical block of data comprises selecting the block of data from the logical start of the file.
Claim 17
Dependent Claim
59 words
The method of claim 15 further comprising sequentially reading an amount of data from each of a plurality of source files, processing the data into combined data, and writing the combined data to a target file, and wherein selecting the block of data from the logical start of the file includes selecting the block from among the processed data.
Claim 18
Dependent Claim
44 words
The method of claim 15 further comprising dequeuing an amount of data from a first in, first out queue file and selecting the block of data from the logical start of the file includes selecting the block from among the dequeued amount of data.
Claim 19
Dependent Claim
125 words
In a computer system including a permanent storage medium having a plurality of physical locations for storing data, a mechanism for freeing physical storage space allocated to a file of logical data, comprising: a file system having mapping data, the mapping data associating the logical data of the file with physical locations of the storage medium; means for receiving a request to free a section of logical data allocated to the file; and means for processing the request including means for accessing the mapping data to determine at least one physical location corresponding to the section of logical data and for modifying the mapping data independent of a data write to disassociate the at least one physical location from the logical data of the file.
Claim 20
Dependent Claim
125 words
In a computer system including a permanent storage medium having a plurality of physical locations for storing data, a mechanism for freeing physical storage space allocated to a file of logical data, comprising: a file system having mapping data, the mapping data associating the logical data of the file with physical locations of the storage medium; means for receiving a request to free a section of logical data allocated to the file; and means for processing the request including means for accessing the mapping data to determine at least one physical location corresponding to the section of logical data and for modifying the mapping data independent of a data write to disassociate the at least one physical location from the logical data of the file.
Claim 21
Dependent Claim
44 words
The mechanism of claim 18 wherein the at least one physical location has a first indicator in the mapping data corresponding to the identity thereof, and the means for modifying the mapping data includes means for overwriting the first indicator with a second indicator.
Claim 22
Dependent Claim
53 words
The mechanism of claim 18 wherein the file system maintains free space information representing physical locations that are free space not allocated to any file, and wherein the means for processing the request includes means for modifying the free space information to indicate that the at least one physical location is free space.
Claim 23
Dependent Claim
29 words
The mechanism of claim 20 wherein the storage medium is a disk, and wherein the free space information is maintained in a bitmap stored in association with the disk.
Claim 24
Dependent Claim
31 words
The mechanism of claim 18 wherein the physical locations of the storage medium comprise clusters on a disk, and wherein the section of logical data corresponds to at least one cluster.
Claim 25
Dependent Claim
25 words
The mechanism of claim 18 wherein the logical section of data is identified by an offset value in bytes and a number of bytes thereafter.
Claim 26
Dependent Claim
28 words
The mechanism of claim 18 wherein the mapping data for the file is maintained within a record corresponding to the file in a master file table of records.
Claim 27
Dependent Claim
28 words
The mechanism of claim 18 wherein the allocation units are clusters, and wherein the mapping data for the file is maintained within an extent list of cluster runs.
Claim 28
Dependent Claim
24 words
The mechanism of claim 18 wherein the allocation units are clusters, and wherein the mapping data is maintained within a block list of clusters.
Claim 29
Dependent Claim
20 words
The mechanism of claim 18 wherein the selected section of data includes data from the logical start of the file.
Claim 30
Dependent Claim
17 words
The mechanism of claim 18 wherein the means for processing the request includes an application programming interface.
Claim 31
Dependent Claim
30 words
The mechanism of claim 28 wherein the application programming interface is called by an application program that sequentially merges a plurality of source files into at least one target file.
Claim 32
Dependent Claim
43 words
The mechanism of claim 28 wherein the application program interface is called by an application program that dequeues an amount of data from a first in, first out queue file wherein the selected section of data is within the dequeued amount of data.
Claim 33
Independent Claim
115 words
A method of freeing storage space allocated to a file in a persistent storage medium wherein a file system maintains mapping data associating the file with physical storage space locations in the storage medium, comprising: selecting a section of data beginning at the logical start of the file; providing the file system with information identifying the file and the section of data; accessing the mapping data via the file system to determine at least one physical location in the persistent storage medium corresponding to the selected logical section of data; and modifying the mapping data in the file system to indicate that the at least one physical location is no longer allocated to the file.
Claim 34
Independent Claim
115 words
A method of freeing storage space allocated to a file in a persistent storage medium wherein a file system maintains mapping data associating the file with physical storage space locations in the storage medium, comprising: selecting a section of data beginning at the logical start of the file; providing the file system with information identifying the file and the section of data; accessing the mapping data via the file system to determine at least one physical location in the persistent storage medium corresponding to the selected logical section of data; and modifying the mapping data in the file system to indicate that the at least one physical location is no longer allocated to the file.
Claim 35
Independent Claim
180 words
A method of merging source data from a plurality of source files into a target file, wherein the files are stored in a persistent storage medium and managed by a file system, comprising: reading a block of data from each of the source files; sequentially processing the data from each of the source files into a combined block of data, and tracking the amount of data processed from each of the source files; writing at least part of the combined block of data into the target file; selecting one of the source files as a selected file; selecting a section of data from the logical start of the selected file; providing the file system with information identifying the selected file and the selected section of data; accessing mapping data maintained by the file system for the selected file to determine at least one physical location in the persistent storage medium corresponding to the selected logical section of data; and modifying the mapping data to indicate that the at least one physical location is no longer allocated to the selected file.
Claim 36
Independent Claim
180 words
A method of merging source data from a plurality of source files into a target file, wherein the files are stored in a persistent storage medium and managed by a file system, comprising: reading a block of data from each of the source files; sequentially processing the data from each of the source files into a combined block of data, and tracking the amount of data processed from each of the source files; writing at least part of the combined block of data into the target file; selecting one of the source files as a selected file; selecting a section of data from the logical start of the selected file; providing the file system with information identifying the selected file and the selected section of data; accessing mapping data maintained by the file system for the selected file to determine at least one physical location in the persistent storage medium corresponding to the selected logical section of data; and modifying the mapping data to indicate that the at least one physical location is no longer allocated to the selected file.
Claim 37
Independent Claim
124 words
A method of cleaning data from a first in, first out (FIFO) queue file, wherein the FIFO queue file is stored in a persistent storage medium and managed by a file system, comprising: dequeuing an amount of data from the FIFO queue file; selecting a section of dequeued data from the logical start of the selected file; providing the file system with information identifying the selected section of data; accessing mapping data maintained by the file system for the FIFO queue file to determine at least one physical location in the persistent storage medium corresponding to the selected section of data; and modifying the mapping data to indicate that the at least one physical location is no longer allocated to the FIFO queue file.
Claim 38
Independent Claim
124 words
A method of cleaning data from a first in, first out (FIFO) queue file, wherein the FIFO queue file is stored in a persistent storage medium and managed by a file system, comprising: dequeuing an amount of data from the FIFO queue file; selecting a section of dequeued data from the logical start of the selected file; providing the file system with information identifying the selected section of data; accessing mapping data maintained by the file system for the FIFO queue file to determine at least one physical location in the persistent storage medium corresponding to the selected section of data; and modifying the mapping data to indicate that the at least one physical location is no longer allocated to the FIFO queue file.
Claim 39
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 1.
Claim 40
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 31.
Claim 41
Dependent Claim
40 words
The method of claim 31, wherein modifying the mapping data in the file system to indicate that the at least one physical location is no longer allocated to the file comprises modifying the mapping data independent of a data write.
Claim 42
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 32.
Claim 43
Dependent Claim
41 words
The method of claim 32, wherein modifying the mapping data in the file system to indicate that the at least one physical location is no longer allocated to the selected file comprises modifying the mapping data independent of a data write.
Claim 44
Dependent Claim
21 words
The method of claim 32, further comprising, comparing the amount of data processed from the selected file against a size value.
Claim 45
Dependent Claim
13 words
A computer-readable medium having computer-executable instructions for performing the method of claim 33.
Claim 46
Dependent Claim
38 words
The method of claim 33, wherein modifying the mapping data to indicate that the at least one physical location is no longer allocated to the FIFO queue file comprises modifying the mapping data independent of a data write.
Claim 47
Dependent Claim
22 words
The method of claim 33, further comprising, comparing the amount of data dequeued from the FIFO queue file against a size value.
References Cited (Backward Citations)
US5062042A
Cited
US5241673A
Cited
US5596736A
Cited
US5403639A
Cited
US5794229A
Cited
US5574952A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-07 | 2003-08-09 | 2004-02-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-07 | 2007-08-09 | 2008-02-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-07 | 2011-08-09 | 2012-02-08 | $7700.00 | Window Closed / Lapsed |