Method and apparatus using slack area of file storage structures for file reconstruction

• US 5,832,526 A
• Filed: 01/24/1996
• Issued: 11/03/1998
• Est. Priority Date: 01/24/1996
• Status: Expired due to Term

• Current Assignee: Power Management Enterprises LLC (IPNav)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Schuyler, David E.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/592,873
• Time in Patent Office: 1,014 Days
• Field of Search: 395/621, 395/622, 395/611, 395/618, 395/182.03, 395/182.01, 707/205, 707/206, 707/200, 707/202, 711/173, 711/170, 711/171
• US Class Current: N/A
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

Available slack area in file storage structures is used for storing file-reconstruction data. The file-reconstruction data includes a unique end-of-file tag code (405) positioned within a vital core (403) section of limited length. The vital core section is located close to or against the end of the slack area. Less-essential file-reconstruction data is grown frontwards from the vital core section to the beginning of the slack area as room permits. During file recovery, the random access storage device (e.g., a disk whose directory structure has been damaged) is scanned for storage sub-areas (e.g., allocation blocks) containing the predefined, unique end-of-file tag code appropriately positioned within the vital core portion at the end of the sub-area. Each storage sub-area having such a properly-positioned end-of-file tag code is designated as a possible end-of-file sub-area. A file recovery program uses this and other available information to reconstruct the directory structure to whatever extent is made possible.

Claims

1. A tagging method for application to a random access storage device having plural pre-allocated storage sub-areas across which plural files are recorded, said method comprising the steps of:

(a) locating a logically-last storage sub-area of at least one of the files whose data is stored across the pre-allocated storage sub-areas of the random access storage device;

(b) determining if and how much storage slack space is available in the logically-last storage sub-area;

(c) in response to said determination of the available slack space, recording an end-of-file tagging code in the slack space, if sufficient slack space is available for such an end-of-file tagging code.

2. The tagging method of claim 1 wherein said storage slack space has a variably positioned beginning and an opposed end and said step (c) of recording includes:

(c.1) recording the end-of-file tagging code within the slack space at a position that is displaced from the end of the slack space by a non-zero, predefined displacement amount.

3. The tagging method of claim 1 further comprising, before said step (c) of recording, the additional step of:

(d) defining the end-of-file tagging code as a unique sequence of bits that is not commonly found in the majority of slack spaces of said random access storage device.

4. The tagging method of claim 3 wherein:

said unique sequence of bits does not include a consecutive sequence of eight bits each equal to logical zero; and

said unique sequence of bits does not include a consecutive sequence of eight bits each equal to logical one.

5. The tagging method of claim 3 wherein:

said unique sequence of bits does not include a consecutive sequence of eight bits defining a byte having the hexadecimal value, D6_hex.

6. The tagging method of claim 5 wherein:

said unique sequence of bits does not include a consecutive sequence of eight bits defining a byte having either the hexadecimal value, D6_hex, or the hexadecimal value, A5_hex.

7. The tagging method of claim 1 wherein said end-of-file tagging code is recorded in the slack space as first file-recovery assisting information and the method further comprises the step of:

(d) further recording other file-recovery assisting information in the slack space as the available slack space permits.

8. The tagging method of claim 7 wherein said other file-recovery assisting information that is recorded includes one or more items in the group consisting of:

(d.1) a tag-structure version number for defining a format used for a remainder of the other file-recovery assisting information;

(d.2) a fragmentation flag for indicating whether the corresponding file, within whose slack space the fragmentation flag resides, is fragmented or not; and

(d.3) a length value field for indicating the total number of bits of valid information contained within the slack space.

9. The tagging method of claim 8 wherein said other file-recovery assisting information further includes:

(d.4) a valid flag positioned at a predefined location within said slack space for indicating whether a neighboring subregion of the slack space does or does not contain valid information.

10. The tagging method of claim 7 wherein said other file-recovery assisting information that is recorded includes one or more items in the first group consisting of:

(d.1) a file-size field for indicating the total file size of the corresponding current file, within whose slack space the file-size field resides;

(d.2) a number of fragments field for defining a total number of fragments used for forming the current file;

(d.3) a plurality of fragment pointers for respectively pointing to a respective plurality of file fragments forming the current file;

(d.4) a primary name of file field for specifying a primary name given to the current file; and

(d.5) a last time of revision specifying field for specifying a time when the current file was last revised.

11. The tagging method of claim 10 wherein said storage slack space has a variably positioned beginning and an opposed end and said other file-recovery assisting information that is recorded includes one or more items in the second group consisting of:

(d.6) a tag-structure version number for defining a format used for a remainder of the other file-recovery assisting information;

(d.7) a fragmentation flag for indicating whether the corresponding file, within whose slack space the fragmentation flag resides, is fragmented or not; and

(d.8) a length value field for indicating the total number of bits of valid information contained within the slack space; and

wherein at least one member of said second group of other file-recovery assisting information is positioned closer to the end of the slack space than any member of said first group of other file-recovery assisting information.

12. The tagging method of claim 10 wherein said storage slack space has a variably positioned beginning and an opposed end and said step (c) of recording includes:

(c.1) recording the end-of-file tagging code at a position that is closer to the end of the slack space than any member of said first group of other file-recovery assisting information.

13. The tagging method of claim 7 wherein:

said at least one file can be composed of multiple forks or multiple fragments or both;

said step (a) of locating further includes locating additional logically-last storage sub-areas of respective additional forks or additional fragments of the at least one file, other than the logically-last storage sub-area of said logically-last fork or logically-last fragment of the at least one file;

said step (b) of determining further includes determining if and how much additional storage slack space is available in each of the located additional logically-last storage sub-areas;

said step (c) of recording further includes, in response to said determination of the available additional slack space, recording an end-of-fragment tagging code in the additional slack space, if sufficient slack space is available for such an end-of-fragment tagging code;

said step (d) of further recording includes additionally recording other file-recovery assisting information in the additional slack space as the available additional slack space permits; and

said other file-recovery assisting information that is recorded includes one or more items in the first group consisting of;

(d.1) an end-of-this-fork/fragment identifier for identifying the logical end of data of the respective fork or fragment using the storage sub-area in which said end-of-this-fork/fragment identifier resides;

(d.2) a further-extents-of-this-fork/fragment identifier for identifying the number of further forks or fragments if any that logically extend beyond the respective fork or fragment using the storage sub-area in which said further-extents-of-thisfork/fragment identifier resides; and

(d.3) a number of for-this-fork/fragment extent-records, said number being equal to that identified by the further-extents-of-this-fork/fragment identifier, each for-this-fork/fragment extent-record including a for-this-fork/fragment extent-pointer pointing to the start of the corresponding fork or fragment that logically extends beyond the respective fork or fragment using the storage sub-area in which said for-this-fork/fragment extent-pointer resides.

15. The tagging method of claim 7 wherein said random access storage device further has a directory structure for locating the pre-allocated storage sub-areas of each of said plural files and for optionally assigning one or more attributes to each such file and wherein said other file-recovery assisting information that is recorded includes one or more items in the group consisting of:

(d.1) a file-type specifying field for specifying a file-type for the at least one file, said file-type specifying field being for reconstructing a corresponding file-type attribute field of the directory structure in the case where the directory structure is damaged;

(d.2) a file-creator specifying field for specifying a file-creator for the at least one file, said file-creator specifying field being for reconstructing a corresponding file-creator attribute field of the directory structure in the case where the directory structure is damaged;

(d.3) a finder-flags specifying field for specifying one or more finder-flags for the at least one file, said finder-flags specifying field being for reconstructing a corresponding finder-flags attribute field of the directory structure in the case where the directory structure is damaged;

(d.4) a file-creation-time specifying field for specifying a creation-time for the at least one file, said file-creation-time specifying field being for reconstructing a corresponding file-creation-time attribute field of the directory structure in the case where the directory structure is damaged;

(d.5) a file-last-modification-time specifying field for specifying a last-modification-time for the at least one file, said file-last-modification-time specifying field being for reconstructing a corresponding file-last-modification-time attribute field of the directory structure in the case where the directory structure is damaged;

(d.6) a file-last-backup-time specifying field for specifying a last-backup-time for the at least one file, said file-last-backup-time specifying field being for reconstructing a corresponding file-last-backup-time attribute field of the directory structure in the case where the directory structure is damaged.

16. The tagging method of claim 7 wherein said random access storage device further has a directory structure for locating the pre-allocated storage sub-areas of each of said plural files and for optionally assigning one or more attributes to each such file and wherein said files are accessible through a graphical user interface (GUI) and further wherein said other file-recovery assisting information that is recorded includes one or more items in the group consisting of:

(d.1) an icon-location specifying field for specifying one or more icon-locations associated with the at least one file, said icon-location specifying field being for reconstructing a corresponding icon-location attribute field of the directory structure in the case where the directory structure is damaged, said icon-location attribute field being for indicating one or more locations in the GUI of a corresponding one or more icons representing the at least one file;

(d.2) a file_-- system flags specifying field for specifying one or more file_-- system flags for the at least one file, said file_-- system flags specifying field being for reconstructing corresponding file_-- system flags of the directory structure in the case where the directory structure is damaged, said file_-- system flags of the directory structure serving as global system flags for the corresponding file;

(d.3) a file_-- system file-identification-number specifying field for specifying a file_-- system identification-number for the at least one file, said file_-- system file-identification-number specifying field being for reconstructing a corresponding file_-- system file-identification-number field of the directory structure in the case where the directory structure is damaged, said file_-- system file-identification-number field being for assigning a system-wide unique identification-number to the at least one file;

(d.4) a comments-locations specifying field for specifying one or more comments-locations for the at least one file, said comments-locations specifying field being for reconstructing a corresponding comments-locations attribute field of the directory structure in the case where the directory structure is damaged, said comments-locations attribute field being for specifying locations of one or more comment files associated with the at least one file;

(d.5) a Put-away specifying field for specifying a return location for the at least one file, said Put-away specifying field being for reconstructing a corresponding Put-away attribute field of the directory structure in the case where the directory structure is damaged, said Put-away attribute field being for specifying a return location for the at least one file in case the file'"'"'s graphical icon is displaced to a desktop area not having a storage directory assigned thereto; and

(d.6) a Clump-size specifying field for specifying an incremental clump size for the at least one file, said Clump-size specifying field being for reconstructing a corresponding Clump-size attribute field of the directory structure in the case where the directory structure is damaged, said Clump-size attribute field being for defining an integral number of storage sub-areas by which the file is to grow or shrink when its stored data correspondingly grows or shrinks.

17. The tagging method of claim 7 wherein said random access storage device further has a directory structure for locating the pre-allocated storage sub-areas of each of said plural files and for defining a number of primitive storage regions used for forming each of the pre-allocated storage sub-areas and wherein said other file-recovery assisting information that is recorded includes:

(d.1) a primitives-per-storage sub-area specifying field for specifying said number of primitive storage regions used for forming each of the pre-allocated storage sub-areas.

18. The tagging method of claim 7 wherein:

said storage slack space has a variably positioned beginning and an opposed end;

said other file-recovery assisting information that is recorded includes one or more members in the core group consisting of;

(d.1) a length value field for indicating the total number of bits of valid information contained within the slack space;

(d.2) a length valid flag positioned at a predefined location within said slack space either adjacent to or spaced apart from said length value field, if the slack space can contain such a length value field in another location of the slack space, the length valid flag being for indicating whether the other location of the slack space does or does not contain valid length information;

(d.3) a fragmentation flag for indicating whether the corresponding file, within whose slack space the fragmentation flag resides, is fragmented or not; and

(d.4) a tag-structure version number for defining a positioning format used for positioning other parts of the file-recovery assisting information within said slack space; and

said step (c) of recording includes;

(c.1) recording the end-of-file tagging code at a position that is closer to the end of the slack space than any of the other file-recovery assisting information except for members of the core group, any one or more members of the core group being optionally positioned closer to the end of the slack space than is the end-of-file tagging code.

19. The tagging method of claim 1 wherein said steps of (a) locating, (b) determining, and (c) recording are performed for every file of said random access storage device that has sufficient slack space available for the end-of-file tagging code.

14. A tagging method for application to a random access storage device having plural pre-allocated storage sub-areas across which plural files are recorded, said method comprising the steps of:

(a) locating a logically-last storage sub-area of at least one of the files whose data is stored across the pre-allocated storage sub-areas of the random access storage device;

(b) determining if and how much storage slack space is available in the logically-last storage sub-area;

(c) in response to said determination of the available slack space, recording an end-of-file tagging code in the slack space, if sufficient slack space is available for such an end-of-file tagging code; and

(d) further recording other file-recovery assisting information in the slack space as the available slack space permits;

wherein;

(a.1) said at least one file can be composed of multiple forks or multiple fragments or both;

(a.2) said step (a) of locating further includes locating additional logically-last storage sub-areas of respective additional forks or additional fragments of the at least one file, other than the logically-last storage sub-area of said logically-last fork or logically-last fragment of the at least one file;

(b.1) said step (b) of determining further includes determining if and how much additional storage slack space is available in each of the located additional logically-last storage sub-areas;

(c.1) said step (c) of recording further includes, in response to said determination of the available additional slack space, recording an end-of-fragment tagging code in the additional slack space, if sufficient slack space is available for such an end-of-fragment tagging code;

(d.1) said step (d) of further recording includes additionally recording other filerecovery assisting information in the additional slack space as the available additional slack space permits; and

(d.2) said other file-recovery assisting information that is recorded includes one or more items in the first group consisting of;

(d.21) an end-of-this-fork/fragment identifier for identifying the logical end of data of the respective fork or fragment using the storage sub-area in which said end-of-thisfork/fragment identifier resides;

(d.22) a further-extents-of-this-fork/fragment identifier for identifying the number of further forks or fragments if any that logically extend beyond the respective fork or fragment using the storage sub-area in which said further-extents-of-this-fork/fragment identifier resides; and

(d.23) a number of for-this-fork/fragment extent-records, said number being equal to that identified by the further-extents-of-this-fork/fragment identifier, each for-thisfork/fragment extent-record including a for-this-fork/fragment extent-pointer pointing to the start of the corresponding fork or fragment that logically extends beyond the respective fork or fragment using the storage sub-area in which said for-this-fork/fragment extentpointer resides;

(d.23a) wherein each for-this-fork/fragment extent-record further includes a forthis-fork/fragment extent-length specifier for specifying the logical length of data in the corresponding fork or fragment that logically extends beyond the respective fork or fragment using the storage sub-area in which said for-this-fork/fragment extent-length specifier resides.

20. A tagging method for application to a random access storage device having plural pre-allocated storage sub-areas across which plural files are recorded, said random access storage device further having a directory structure for defining storage sub-areas allocated to each of said plural files and for optionally assigning one or more attributes to each such file, wherein the directory definition of each file may change over time as a consequence of file-modification requests made to an operating system, said method comprising the steps of:

(a) intercepting each file-modification request made to the operating system and for each given file that has been or is to be so-modified;

(b) locating a logically-last storage sub-area of the given file;

(c) determining if and how much storage slack space is available in the located logically-last storage sub-area;

(d) in response to said determination of the available slack space, recording an end-of-file tagging code in the slack space, if sufficient slack space is available for such an end-of-file tagging code.

21. The tagging method of claim 20 further comprising the step of:

(e) further recording other file-recovery assisting information in the slack space as the available slack space permits.

22. The tagging method of claim 21 wherein:

said storage slack space has a variably positioned beginning and an opposed end;

said file-recovery assisting information that is recorded in the slack space can include one or both of a core group and a non-core group, the core group including said end-of-file tagging code;

said steps (d) and (e) of recording include, in addition to recording the end-of-file tagging code, recording the remainder of the core group in the slack space, if sufficient slack space is available for such remainder of the core group;

said steps (d) and (e) of recording further include the additional step of determining whether, in addition to having sufficient slack space for storing the core group, there is sufficient slack space for storing at least part of the non-core group, and if so, recording the at least part of the non-core group for which there is sufficient slack space, the recorded non-core group being positioned farther away from the end of the slack space than is the core group.

23. The tagging method of claim 22 wherein said core group includes:

(d.1) a length value field for indicating the total number of bits of valid information contained within the slack space; and

(d.2) a length valid flag positioned at a predefined location within said slack space either adjacent to or spaced apart from said length value field, if the slack space can contain such a length value field in another location of the slack space, the length valid flag being for indicating whether the other location of the slack space does or does not contain valid length information.

24. The tagging method of claim 23 wherein said core group further includes:

(d.3) a tag-structure version number for defining a positioning format used for positioning other parts of the file-recovery assisting information within said slack space.

25. A tagged data storage medium having:

(a) a plurality of files recorded across respective pre-allocated storage sub-areas of the recording medium; and

(b) file tagging information recorded in available slack space of the allocated storage sub-areas of each said file.

26. A data storage medium according to claim 25 wherein the slack space of each file has a variably positioned beginning and an opposed end and wherein the file tagging information includes:

a unique end-of-file tagging code recorded within the slack space at a position that is displaced from the end of the slack space by a predefined displacement amount, said unique end-of-file tagging code being one that is not normally found recorded at said position of all slack spaces of a hypothetical like, but non-tagged, replica of the data storage medium.

27. A data storage medium according to claim 26 wherein:

the unique end-of-file tagging code is defined by a unique sequence of bits;

said unique sequence of bits does not include a consecutive sequence of eight bits each equal to logical zero; and

said unique sequence of bits does not include a consecutive sequence of eight bits each equal to logical one.

28. The tagging method of claim 27 further wherein:

said unique sequence of bits does not include a consecutive sequence of eight bits defining a byte having the hexadecimal value, D6_hex.

29. A data storage medium according to claim 26 wherein said displacement amount is greater than zero bits.

30. A data storage medium according to claim 25 wherein the slack space of each file has a variably positioned beginning and an opposed end and wherein the file tagging information includes one or more members in the core group consisting of:

(b.1) a length value field for indicating the total number of bits of valid information contained within the slack space;

(b.2) a length valid flag positioned at a predefined location within said slack space either adjacent to or spaced apart from said length value field, if the slack space can contain such a length value field in another location of the slack space, the length valid flag being for indicating whether the other location of the slack space does or does not contain valid length information;

(b.3) a fragmentation flag for indicating whether the corresponding file, within whose slack space the fragmentation flag resides, is fragmented or not; and

(b.4) a tag-structure version number for defining a positioning format used for positioning other parts of information recorded within said slack space.

31. A data storage medium according to claim 30 wherein the slack space further has a non-core group of information recorded within said slack space, the non-core group being positioned further away from end of the slack space than is the core group;

and said non-core group includes one or more members in the group consisting of;

(b.5) an end-of-this-fork/fragment identifier for identifying the logical end of data of the respective fork or fragment using the storage sub-area in which said end-of-this-fork/fragment identifier resides;

(b.6) a further-extents-of-this-fork/fragment identifier for identifying the number of further forks or fragments if any that logically extend beyond the respective fork or fragment using the storage sub-area in which said further-extents-of-thisfork/fragment identifier resides; and

(b.7) a number of for-this-fork/fragment extent-records, said number being equal to that identified by the further-extents-of-this-fork/fragment identifier, each for-this-fork/fragment extent-record including a for-this-fork/fragment extent-pointer pointing to the start of the corresponding fork or fragment that logically extends beyond the respective fork or fragment using the storage sub-area in which said for-this-fork/fragment extent-pointer resides.

43. A data storage medium according to claim 25 wherein the slack space of each file has a variably positioned beginning and an opposed end and wherein the file tagging information includes:

a unique end-of-file tagging code recorded within the slack space at a position that is displaced from the end of the slack space by a predefined displacement amount, said unique end-of-file tagging code being one that is not found with relatively great likelihood recorded at said position in randomly selected storage sub-areas of a hypothetical like, but non-tagged, replica of the data storage medium.

32. A file recovery method for application to a random access storage device having files defined by data stored storage sub-areas of the device, some of said storage sub-areas having slack areas tagged by a predefined end-of-file tagging code, said file recovery method comprising the steps of:

(a) scanning the random access storage device to identify as tagged, each storage sub-area containing the end-of-file tagging code;

(b) in response to the identification of such tagged storage sub-areas, forming and storing file recovery information that indicates the ending locations of the identified storage sub-areas as respective, possible end positions or beginning positions of corresponding files or file fragments; and

(c) reconstructing a directory structure in accordance with the formed file recovery information.

33. A file recovery method according to claim 32 wherein the slack space of each file or a fragment thereof has a variably positioned beginning and an opposed end and wherein said step (a) of scanning is characterized by:

(a.1) only identifying as tagged, each storage sub-area that contains the end-of-file tagging code positioned at a predefined displacement from the end of the corresponding storage sub-area containing that end-of-file tagging code.

34. A file recovery method according to claim 32 wherein the slack space of each file or a fragment thereof has a variably positioned beginning and an opposed end and wherein said step (a) of scanning is characterized by:

(a.1) only identifying as tagged, each storage sub-area that contains the end-of-file tagging code positioned within a predefined displacement distance measured from the end of the corresponding storage sub-area containing that end-of-file tagging code.

35. A file recovery method according to claim 32 wherein:

the slack space of each file or a fragment thereof has a variably positioned beginning and an opposed end;

depending on available storage room in each slack space, each given slack space may contain other filerecovery assisting information in addition to said end-of-file tagging code;

said file recovery method further comprises the steps of;

(d) in response to the identification of each such tagged storage sub-area, testing data neighboring the end-of-file tagging code for predefined validating code that indicates whether further portions of the slack space of the tagged storage sub-area contain a valid form of the other file-recovery assisting information and to what extent; and

(e) if said predefined validating code is found, and to the extent that the validating code indicates that further portions of the slack space of the tagged storage sub-area contain a valid form of the other file-recovery assisting information, including said valid form of the other file-recovery assisting information in the file recovery information formed and stored in said step (b) of forming and storing file recovery information.

36. A file recovery method according to claim 35 wherein said validating code includes a predefined length valid flag positioned at a predefined location relative to the end of said slack space for indicating whether a neighboring subregion of the slack space does or does not contain valid length information.

37. A file recovery method according to claim 35 wherein said validating code includes a predefined tag-structure version number positioned at a predefined location relative to the end of said slack space for defining a format used in a remainder of the other file-recovery assisting information recorded in the slack space of the tagged storage sub-area.

38. A file recovery method according to claim 35 wherein said other file-recovery assisting information includes one or more items in the group consisting of:

(e.1) a tag-structure version number for defining a format used for a remainder of the other file-recovery assisting information;

(e.2) a fragmentation flag for indicating whether the corresponding file, within whose slack space the fragmentation flag resides, is fragmented or not; and

(e.3) a length value field for indicating the total number of bits of valid information contained within the slack space.

39. A file recovery method according to claim 35 wherein said other file-recovery assisting information includes one or more items in the group consisting of:

(e.1) a file-size field for indicating the total file size of the corresponding current file, within whose slack space the file-size field resides;

(e.2) a number of fragments field for defining a total number of fragments used for forming the current file;

(e.3) a plurality of fragment pointers for respectively pointing to a respective plurality of file fragments forming the current file;

(e.4) a primary name of file field for specifying a primary name given to the current file; and

(e.5) a last time of revision specifying field for specifying a time when the current file was last revised.

40. A data-recovery assisting apparatus for operatively coupling to a system processing unit of a computer system having a random access storage device with a damaged directory structure, where the random access storage device stores files whose respective file data is distributed across plural storage sub-areas of the random access storage device and where at least some of the sub-areas contain slack areas tagged by a predefined unique tagging code, said data-recovery assisting apparatus containing instructions for causing the system processing unit to carry out a recovery process including the steps of:

(a) scanning the random access storage device to identify as tagged, each storage sub-area containing the end-of-file tagging code;

(b) in response to the identification of such tagged storage sub-areas, forming and storing file recovery information that indicates the ending locations of the identified storage sub-areas as respective, possible end positions or beginning positions of corresponding files or file fragments; and

(c) reconstructing a directory structure in accordance with the formed file recovery information.

41. A data-recovery assisting apparatus according to claim 40 wherein said apparatus includes a magnetically or optically encoded medium defining said instructions for said system processing unit.

42. A data-recovery assisting apparatus according to claim 40 wherein said random access storage device includes a magnetically or optically encoded and re-writable medium in which said respective file data of the files is stored.