Two-pass defragmentation of compressed hard disk data with a single data rewrite

• US 5,574,907 A
• Filed: 11/30/1994
• Issued: 11/12/1996
• Est. Priority Date: 11/30/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jernigan, Richard P. IV, Quinn, Scott D.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/346,853
• Time in Patent Office: 713 Days
• Field of Search: 395/600, 395/439, 360/48
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30

Abstract

A method and apparatus for defragmenting compressed file data stored on a disk. The method includes a first pass in which the FAT and MDFAT entries for each file stored on the disk are rearranged into adjacent clusters, but in which no movement of the compressed file data occurs. The method includes a second pass in which the actual compressed file data is rearranged on the disk in accordance with the FAT and MDFAT entries. A reference point is identified within the disk storage space such that no compressed file data will be stored beyond the reference point after the second pass is completed. During the rearrangement of data during the second pass, compressed file data is temporarily relocated beyond the reference point if possible. During all movements of compressed file data, the method transfers as much data as can be stored within the space to which the data is to be moved.

Claims

1. A method for defragmenting compressed data stored in files in non-adjacent variable-length clusters on a disk having a beginning and an end, each cluster comprising at least one sector, said method comprising the steps of:

maintaining a first data structure having an entry for each file stored on the disk, each entry identifying the cluster in which the first portion of the file data is contained;

maintaining a second data structure having an entry for each cluster on the disk, each entry identifying another cluster in which the next portion of the file data is contained;

maintaining a third data structure having an entry for each cluster on the disk, each entry identifying the sectors in which the file data of each respective cluster is contained;

rearranging the second and third data structures such that the respective entries for each file are located in adjacent clusters starting from the beginning of the disk;

updating the first data structure entries as necessary responsive to said step of rearranging the second and third data structures; and

rearranging the file data on the disk such that the file data is located in adjacent clusters as determined by the rearranged second and third data structures;

wherein file data is not moved during said step of rearranging the second and third data structures.

2. The method of claim 1 wherein said step of rearranging the file data is initiated only after said step of rearranging the second and third data structures and said step of updating the first data structure have been completed.

3. The method of claim 1 wherein said step of rearranging the file data comprises the steps of:

determining whether any file data is obstructing current file data to be moved into a location as determined by the second and third data structures;

moving obstructing file data to another location on the disk to create a vacant portion of disk space in which to store the current file data;

moving current file data into the vacant portion of disk space.

4. The method of claim 3 wherein said step of moving the obstructing file data comprises the steps of:

identifying a reference point at a predetermined location on the disk;

scanning forward from the reference point toward the end of the disk until a vacant portion of disk space large enough to store the obstructing file data is identified;

moving the obstructing data into the vacant portion of disk space.

5. The method of claim 4 wherein the reference point is located at a location on the disk such that no file data is stored between the reference point and the end of the disk after said step of rearranging the file data has completed.

6. The method of claim 4 wherein the reference point is determined by adding the size of all variable-length clusters used to store file data on the disk to the beginning of the disk storage space.

7. The method of claim 4 further comprising the step of scanning backward from the reference point toward the beginning of the disk to identify a vacant portion of disk space large enough to store the obstructing file data if said step of scanning forward does not identify a vacant portion of disk space large enough to store the obstructing file data.

8. The method of claim 7 wherein said step of scanning backward is continued until a predetermined number of vacant portions of disk space large enough to store the obstructing file data are identified.

9. The method of claim 8 wherein the obstructing file data is stored in the largest of the identified predetermined number of vacant portions of disk space.

10. The method of claim 8 wherein the predetermined number is approximately 100.

11. The method of claim 4 further comprising the step of determining the size of the vacant portion of disk space, and then determining how many subsequent clusters of file data from the same file as the obstructing file data can be stored within the vacant portion of disk space.

12. The method of claim 11 wherein the clusters of file data from the obstructing file, prior to movement, need not be located in adjacent clusters.

13. The method of claim 12 wherein the clusters of file data from the obstructing file are stored in adjacent clusters in the vacant portion of disk space.

14. The method of claim 3 further comprising the step of determining the size of the vacant portion of disk space, and then determining how may subsequent clusters of file data from the current file can be stored within the vacant portion of disk space.

15. The method of claim 14 wherein the clusters of file data from the current file, prior to movement, need not be located in adjacent clusters.

16. The method of claim 14 wherein the clusters of file data from the current file are stored in adjacent clusters in the vacant portion of disk space.

17. The method of claim 4 further comprising the step of scanning forward from the end of the file data previously stored, rather than from the reference point.

18. The method of claim 4 further comprising the step of scanning forward from the reference point after a predetermined number of clusters of obstructing file data have been moved.

19. The method of claim 18 wherein the predetermined number of clusters is approximately 100.

20. The method of claim 11 wherein said method includes maintaining a fourth data structure having an entry for each sector on the disk, the entry identifying whether each respective sector is being used for data storage or is vacant, and wherein said step of determining the size of the vacant portion of disk space is performed by examining the fourth data structure.

21. The method of claim 14 wherein said method includes maintaining a fourth data structure having an entry for each sector on the disk, the entry identifying whether each respective sector is being used for data storage or is vacant, and wherein said step of determining the size of the vacant portion of disk space is performed by examining the fourth data structure.

22. A method for defragmenting uncompressed file data stored in non-adjacent clusters on a disk having a beginning and an end, said method comprising the steps of:

maintaining a first data structure having an entry for each file stored on the disk, each entry identifying the cluster in which the first portion of the file data is contained;

maintaining a second data structure having an entry for each cluster on the disk, each entry identifying another cluster in which the next portion of the file data is contained;

rearranging the second data structure such that the respective entries for each file are located in adjacent clusters;

updating the first data structure as necessary responsive to said step of rearranging the second data structure;

rearranging the file data on the disk such that the file data is located in adjacent clusters, wherein the clusters in which the rearranged file data are stored is determined by the rearranged second data structure;

wherein said step of rearranging the file data is initiated only after said step of rearranging the second data structure and said step of updating the first data structure have been completed;

wherein said step of rearranging the file data comprises the steps of;

determining whether any file data is obstructing current file data to be moved into a location as determined by the second data structure;

moving obstructing file data to another location on the disk to create a vacant portion of disk space in which to store the current file data;

moving current file data into the vacant portion of disk space;

wherein said step of moving the obstructing file data comprises the steps of;

identifying a reference point at a predetermined location on the disk;

scanning forward from the reference point toward the end of the disk until a vacant portion of disk space large enough to store the obstructing file data is identified;

moving the obstructing data into the vacant portion of disk space;

wherein the reference point is located at a location on the disk such that no file data is stored between the reference point and the end of the disk after said step of rearranging the file data has completed.

23. A system for defragmenting compressed data stored in files in non-contiguous clusters on a disk having a beginning and an end, each cluster comprising at least one sector, said system comprising:

a computer having a memory;

an operating system stored within said memory;

a magnetic disk drive connected to said computer for storing compressed files including compressed file data;

a compression device driver for facilitating communication between said operating system and said compressed file data on said disk drive; and

a defragmentation program stored within said operating system;

wherein said disk drive comprises;

first means for maintaining a first data structure having an entry for each file stored on said disk, each said entry identifying the cluster in which the first portion of said file data is contained;

second means for maintaining a second data structure having an entry for each cluster on said disk, each said entry identifying another cluster in which the next portion of said file data is contained;

third means for maintaining a third data structure having an entry for each cluster on the disk, each said entry identifying the sectors in which the file data of each respective cluster is contained;

fourth means for rearranging said second and third data structures such that the respective entries for each said file are located in adjacent clusters starting from the beginning of said disk;

fifth means for updating said first data structure entries as necessary responsive to said rearrangement of said second and third data structures; and

sixth means for rearranging said file data on said disk such that said file data is located in adjacent clusters as determined by said rearranged second and third data structures;

wherein said file data is not moved during said rearrangement of said second and third data structures.

24. The system of claim 23 wherein said sixth means operates to rearrange said file data only after said fourth means operates to rearrange said second and third data structures and said fifth means operates to update said first data structure.

25. The system of claim 23 wherein said sixth means comprises:

means for determining whether any said file data is obstructing current file data to be moved into a location as determined by said second and third data structures;

means for moving said obstructing file data to another location on said disk to create a vacant portion of disk space in which to store said current file data;

means for moving said current file data into said vacant portion of said disk space.

26. The system of claim 25 wherein said means for moving said obstructing file data comprises:

means for identifying a reference point at a predetermined location on said disk;

means for scanning forward from said reference point toward the end of said disk until a vacant portion of disk space large enough to store said obstructing file data is identified;

means for moving said obstructing file data into said vacant portion of disk space.

27. The system of claim 26 wherein said reference point is located at a location on said disk such that no file data is stored between said reference point and the end of said disk after the rearrangement of said file data has completed.

28. The system of claim 26 wherein said reference point is determined by adding the size of all clusters used to store said file data on said disk to the beginning of the disk storage space.

29. The system of claim 26 further comprising means for scanning backward from said reference point toward the beginning of said disk to identify a vacant portion of disk space large enough to store said obstructing file data if the operation of scanning forward does not identify a vacant portion of disk space large enough to store said obstructing file data.

30. The system of claim 29 wherein said means for scanning backward operates to continue said backward scan until a predetermined number of vacant portions of disk space large enough to store said obstructing file data are identified.

31. The system of claim 30 wherein said obstructing file data is stored in the largest of said identified predetermined number of vacant portions of disk space.

32. The system of claim 30 wherein said predetermined number is approximately 100.

33. The system of claim 26 further comprising means for determining the size of said vacant portion of disk space, and means for determining how many subsequent clusters of said file data from the same file as said obstructing file data can be stored within said vacant portion of disk space.

34. The system of claim 33 wherein said clusters of file data from the obstructing file, prior to movement, need not be located in adjacent clusters.

35. The system of claim 33 wherein said clusters of file data from the obstructing file are stored in adjacent clusters in said vacant portion of disk space.

36. The system of claim 23 further comprising means for determining the size of said vacant portion of disk space, and means for determining how may subsequent clusters of said file data from the current file can be stored within said vacant portion of disk space.

37. The system of claim 36 wherein said clusters of file data from the current file, prior to movement, need not be located in adjacent clusters.

38. The system of claim 36 wherein said clusters of file data from the current file are stored in adjacent clusters in said vacant portion of disk space.

39. The system of claim 26 further comprising means for scanning forward from the end of the file data previously stored, rather than from said reference point.

40. The system of claim 26 further comprising means for scanning forward from said reference point after a predetermined number of clusters of obstructing file data have been moved.

41. The system of claim 30 wherein said predetermined number of clusters is approximately 100.

42. The system of claim 33 further comprising a seventh means for maintaining a fourth data structure having an entry for each sector on said disk, each said entry identifying whether each respective sector is being used for data storage or is vacant, and wherein said means for determining the size of said vacant portion of disk space operates by examining said fourth data structure.

43. The method of claim 26 further comprising an eighth means for maintaining a fourth data structure having an entry for each sector on said disk, each said entry identifying whether each respective sector is being used for data storage or is vacant, and wherein said means for determining the size of said vacant portion of disk space operates by examining said fourth data structure.