Opportunistic tile-pulling, vacancy-filling method and apparatus for file-structure reorganization

• US 5,778,392 A
• Filed: 04/01/1996
• Issued: 07/07/1998
• Est. Priority Date: 04/01/1996
• Status: Expired due to Term

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Blackburn, John, Stockman, Steven
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HO, RUAY L
• Application Number:
  US08/626,673
• Time in Patent Office: 827 Days
• Field of Search: 395/616, 395/617, 395/618, 395/619, 395/620, 395/621, 395/622, 395/750, 395/800, 707/200, 707/201, 707/202, 707/203, 707/204, 707/205, 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/1724 Details of de-fragmentation 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 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 27/329 on a disc [VTOC]
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A storage reorganizing system subdivides a reorganizable storage space into tile areas. Each tile area either contains file data or does not contain file data. The data in a tile area that contains file data is referred to as a tile. A tile area that does not contain file data is referred to as a vacancy. Tiles that are not yet located in their goal positions, as defined by a recorded goal state definition, are opportunistically moved to available vacancies that are the goal positions for such tiles as the vacancies become available. Each tile move leaves behind it a new vacancy. The speed of opportunistic tile moving is optimized by first locating the largest vacancies that are each to be filled with the largest amount of tile data and by first moving tiles to such vacancies. One goal state produces a defragmented set of files. Another goal state produces an intentionally fragmented set of files. A third goal state produces a set of files that are fragmented and whose fragments are tightly interleaved on an access-wise basis so as to enable quick switching between a fragment of a first file and a fragment of a second file.

Claims

1. A method for reorganizing file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing data and where each file is defined by a directory structure as data contained in a directory-specified organization of storage sub-areas, said method comprising the steps of:

(a) identifying one or more files or groups of files that are to be reorganized, the identified files or file groups residing in the re-organizable storage space;

(b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(c) recording as a definition of a goal state, indications of goal locations for each tile in the re-organizable storage space;

(d) identifying an already-existing vacancy space within the re-organizable storage space, and if none;

creating at least one such vacancy space within the re-organizable storage space and identifying the created vacancy space; and

(e) moving (pulling) into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the goal state as the goal location for the moved one or more source tiles.

2. A machine-implemented file data reorganizing method according to claim 1 further comprising the step of:

(f) automatically repeating said vacancy identifying step (d) and said tile moving step (e) until the goal state is achieved.

3. A file data reorganizing method according to claim 1 further comprising the step of:

(f) repeating said vacancy identifying step (d) and said tile moving step (e).

4. A file data reorganizing method according to claim 3 further comprising the step of:

(g) upon completion of a move of a last source tile of a given source file to that tile'"'"'s destination as defined by the goal state, updating the directory structure to reflect the new organization of the re-organized given file.

5. A file data reorganizing method according to claim 4 further comprising the step of:

(h) upon completion of a move of a last source tile to that tile'"'"'s destination as defined by the goal state, said last move achieving the goal state, updating the directory structure to reflect consequential changes to free space within the re-organizable storage space as a result of the achieved goal state.

6. A file data reorganizing method according to claim 3 further comprising the steps of:

(g.1) for each identified vacancy space and corresponding one or more source tiles that have that identified vacancy space defined as their goal location, generating and recording a respective move request;

(g.2) collecting a plurality of move requests; and

(g.3) sorting through the collected move requests to identify as a set of adjacency partners those move requests whose servicing either calls for respective reads of data from respective and access-wise adjacent source tiles or calls for respective writes of data to respective and access-wise adjacent vacancy areas.

7. A file data reorganizing method according to claim 6 wherein for each set of adjacency partners whose servicing calls for respective reads of data from respective and access-wise adjacent source tiles, said method further comprises the step of:

(g.4) combining into a unitary data read operation, the data from said respective and access-wise adjacent source tiles.

8. A file data reorganizing method according to claim 6 wherein for each set of adjacency partners whose servicing calls for respective writes of data to respective and access-wise adjacent vacancy areas, said method further comprises the step of:

(g.4) combining into a unitary data write operation, the data filling said respective and access-wise adjacent vacancy areas.

9. A file data reorganizing method according to claim 1

wherein said step (d) of identifying a vacancy space includes, for the case where there are plural already-existing vacancy spaces,

(d.1) identifying a largest one of said plural already-existing vacancy spaces that is to be occupied in accordance with the goal state by a correspondingly largest amount of file data;

and

wherein said step (e) of moving one or more tiles includes,

(e.1) before filling smaller vacancy areas, moving into the identified largest vacancy space the corresponding largest amount of file data that is contained in the one or more source tiles that have said identified largest vacancy space defined as their respective goal location.

10. A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a nonvolatile memory device selected from the group consisting of:

magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.

11. A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a magnetic disk.

12. A file data reorganizing method according to claim 11 wherein each of said storage sub-area comprises an integral number of one or more disk sectors.

13. A file data reorganizing method according to claim 1 wherein said re-organizable storage space is in a random access memory device having the capacity to store voluminous amounts of data, said voluminous amounts of data being at least two hundred megabytes.

14. A file data reorganizing method according to claim 1 wherein said step of recording indications of goal locations for each tile is characterized by:

(c.1) a goal state that changes the relative order of two or more tiles with respect to address in said re-organizable storage space.

15. A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in said storage sub-areas, said method comprising the steps of:

(a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the storage space of the re-organizable storage means;

(c) identifying an already-existing vacancy space within the re-organizable storage space; and

(d) moving into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recorded goal state as the goal resting position for the moved one or more source tiles.

16. A machine-implemented data reorganizing method according to claim 15 further comprising the step of:

(e) automatically repeating said vacancy identifying step (c) and said tile moving step (d) until the goal state is achieved.

17. A data reorganizing method according to claim 15 further comprising the step of:

(e) repeating said vacancy identifying step (c) and said tile moving step (d).

18. A data reorganizing method according to claim 17 further comprising within said step (e) of repeating,

(e.1) automatically testing the size of one or more recent tile moves;

and

(e.2) in cases where the size of the tested one or more recent tile moves falls below a predefined threshold, creating a new vacancy area within said re-organizable storage space even if there are other vacancy areas already available within the re-organizable storage space.

19. A data reorganizing method according to claim 17 further comprising within said step (e) of repeating,

(e.1) automatically testing the degree of fragmentation of current files that are being re-organized by one or more one or more recent tile moves;

and

(e.2) in cases where the degree of fragmentation of the tested files falls above a predefined threshold, creating a new vacancy area within said re-organizable storage space even if there are other vacancy areas already available within the re-organizable storage space.

20. A rearranging method according to claim 17 wherein said step of (c) of identifying an already-existing vacancy space further includes:

(c.1) creating at least one vacancy space within the re-organizable storage space if none is already-existing and identifying the just-created vacancy space as the already-existing vacancy space.

21. A rearranging method according to claim 15 wherein said data storage means is selected from the group consisting of:

magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.

22. A rearranging method according to claim 15 wherein said data storage means includes a magnetic disk.

23. A rearranging method according to claim 22 wherein each of said storage sub-area comprises an integral number of one or more disk sectors.

24. A rearranging method according to claim 15 wherein said data storage means includes a random access memory device having the capacity to store voluminous amounts of data, said voluminous amounts of data being at least two hundred megabytes.

25. A rearranging method according to claim 15 wherein said step of providing pre-recorded indications of goal resting positions for each tile includes:

(c.1) providing a goal state that changes the relative order of two or more tiles with respect to the addresses of the tiles in said data storage means.

26. A method for defragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

(a) identifying one or more files or groups of files that are to be defragmented, the identified files or file groups residing in the re-organizable storage space;

(b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise closer adjacency relative to one another than such tiles are in their original state; and

(d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state, where a majority of said tile moves are performed just once for each of the moved tiles.

27. A file defragmenting method according to claim 26 wherein said re-organizable storage space is in a nonvolatile memory device selected from the group consisting of:

magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.

28. A method for fragmenting file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

(a) identifying one or more files or groups of files that are to be fragmented, the identified files or file groups residing in the re-organizable storage space;

(b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(c) recording as a definition of a goal state, indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places logically adjacent tiles of each file in access-wise non-adjacency relative to one another; and

(d) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

29. A file data fragmenting method according to claim 28 further comprising the steps of:

(e) after moving said tiles, using the identified one or more files to test the speed of a file-accessing application program.

30. A method for increasing fragmentation of file data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, and where parts of the data of each file are defined as being logically adjacent to one another, said method comprising the steps of:

(a) identifying one or more files or groups of files whose degree of fragmentation is to be increased, the identified files or file groups residing in the re-organizable storage space;

(b) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(c) recording as a definition of an original tile state, indications of original resting positions for each tile in the re-organizable storage space;

(d) providing as a definition of a recorded goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where for each identified file whose degree of fragmentation is to be increased, said goal state places one or more of plural and respective source tiles that are access-wise adjacent to one another in the original tile state to one or more destination tiles that are each access-wise non-adjacent with respect to either one of the source tiles or another, logically-adjacent destination tile; and

(e) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

31. A method for interleave-wise fragmenting file data of two or more files, where said file data is stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, where said sub-areas are logically linked to one another to thereby define a logical organization for the data contained in each said file, where parts of the data of each file are defined as being logically adjacent to one another within the file, and where respective first, second and third parts that respectively belong to at least two different ones of said files are to be interleave-wise accessed one after the other by a predefined program, said method comprising the steps of:

(a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(b) providing as a recorded definition of a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space, where said goal state places the respective first through third parts in interleaved access-wise adjacency to one another; and

(c) moving said tiles each from a current position to the corresponding goal resting position defined by the goal state.

32. An interleave-wise fragmenting method according to claim 31 wherein

(c.1) a majority of said tile moves are performed just once for each of the moved tiles.

33. A method for rearranging storage locations of data stored in a re-organizable storage space of a data storage means, where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, said method comprising the steps of:

(a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and

(c) in accordance with the goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.

34. An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage space, where the storage space has addressable storage sub-areas each for storing a predefined maximum amount of data, said instructing apparatus providing instructions for causing said target data processing system to perform the steps of:

(a) subdividing the data of the re-organizable storage space into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(b) identifying as a goal state, pre-recorded indications of goal resting positions for each tile in the re-organizable storage space; and

(c) in accordance with the identified goal state, opportunistically moving tiles that are not in their goal resting positions to such goal resting positions when such goal resting positions are vacant.

35. An instructing apparatus according to claim 34 further providing instructions for causing said target data processing system to perform the steps of:

(d) searching said re-organizable storage space for largest ones of currently available vacancies that are to be filled in accordance with the identified goal state with largest amounts of data; and

(c.1) within said step (c) of opportunistically moving tiles, if said searching step (d) results in a finding of one or more largest ones of currently available vacancies, moving those tiles that have the found largest ones of the currently available vacancies as their goal resting positions before moving tiles that have smaller ones of the currently available vacancies as their goal resting positions.

36. An instructing apparatus according to claim 35 further providing instructions for causing said target data processing system to perform the step of:

(e) creating a vacancy within said re-organizable storage space that is a goal resting position for at least one tile not currently in its goal resting position if said searching step (d) fails to find any currently available vacancies that are also goal resting positions for tiles not currently in their goal resting positions.

37. An instructing apparatus according to claim 34 further providing

(d) machine-readable indications defining a goal state that is identifiable by said step (b) as the identified goal state.

38. An instructing apparatus according to claim 37 further providing

(e) machine-readable indications defining an original tile map, the original tile map indicating original positions of tiles and vacancies in the re-organizable storage space prior to the start of reorganization;

and

(f) instructions for causing said target data processing system to perform the step of;

(f.1) after beginning said opportunistic moving of tiles in accordance with a first identified goal state, changing the identification of the goal state to be said original tile map as the identified goal state and continuing with opportunistic moving of tiles in accordance with the re-defined goal state to thereby return the stored data to its original storage organization.

39. An instructing apparatus according to claim 37 further providing

(e) machine-readable indications defining a current tile map, the current tile map indicating essentially current positions of tiles and vacancies in the re-organizable storage space during reorganization;

and

(f) instructions for causing said target data processing system to perform the step of;

(f.1) after beginning said opportunistic moving of tiles, periodically updating said current tile map so that the updated current tile map indicates the most current positions of tiles and vacancies in the re-organizable storage space.

40. An instructing apparatus according to claim 39 further providing instructions for causing said target data processing system to perform the step of:

(g) searching said updated current tile map for largest ones of currently available vacancies that are to be filled in accordance with the goal state with largest amounts of data; and

(c.1) within said step (c) of opportunistically moving tiles, if said searching step (d) results in a finding of one or more largest ones of currently available vacancies, moving those tiles that have the found largest ones of the currently available vacancies as their goal resting positions before moving tiles that have smaller ones of the currently available vacancies as their goal resting positions.

41. A machine system for carrying out data structure reorganization comprising:

(a) a primary storage for storing a plurality of files in a file storage space in accordance with a first file storage organization, where the first file storage organization may be represented as a first mapping of tiles of data each in a corresponding tile space of the file storage space; and

(b) file storage reorganizing means, operatively coupled to the primary storage, for reorganizing the storage organization of the primary storage such that one or more of the files are stored after the reorganization in the primary storage in accordance with a pre-defined second file storage organization that is different from said first file storage organization, where the pre-defined second file storage organization may be represented as a second mapping of the tiles of data each in a corresponding tile space; and

where the file storage reorganizing means includes;

(b.1) vacancy locating means for searching through the file storage space of the primary storage looking for a to-be-filled vacant space that is to be ultimately occupied according to the second mapping by a corresponding tile of data; and

(b.2) tile moving means, operatively coupled to the vacancy locating means, for moving, in response to the finding of said to-be-filled vacant space, the corresponding tile of data from its currently occupied storage space to the found vacant space.

42. A machine system according to claim 41 wherein said vacancy locating means includes:

(b.1a) best vacancy finding means for finding a preferred one or more vacancies among plural vacancies that can be currently filled with corresponding one or more tiles that are not yet in their goal position in accordance with the second file storage organization and outputting identifications of the found one or more vacancies, the preferred one or more vacancies being those currently fillable with the largest amount of tile data in accordance with the second file storage organization; and

(b.1b) first-in first-out buffer means, operatively coupled to the best vacancy finding means, for receiving and storing said identifications of the preferred one or more vacancies and for outputting the stored identifications on a first-in first-out basis.

43. A machine system according to claim 42 wherein said tile moving means includes:

(b.2a) move request generating means for generating move requests that request a move of a given tile to a given vacancy; and

(b.2b) request sorting means for sorting generated move requests according to access-wise adjacent source tiles or access-wise adjacent destination vacancies.

44. A machine system according to claim 43 wherein said tile moving means includes:

(b.2c) a move buffer for sequentially receiving access-wise adjacent plurality of tiles, for storing the received tiles, and for sequentially outputting data to access-wise adjacent destination vacancies.

45. A machine system according to claim 41 wherein said primary storage includes a nonvolatile memory device selected from the group consisting of:

magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.

46. A machine system according to claim 45 wherein said primary storage includes a magnetic hard disk.

47. An instructing apparatus for instructing a target data processing system to re-organize storage locations for data stored in a re-organizable storage means,

where the storage means has addressable storage sub-areas each for storing a predefined maximum amount of data, and

where the storage means includes a directory structure for defining files of the storage means each as data contained in a respective directory-specified organization of said storage sub-areas and for further defining vacancy spaces each as provided by a respective directory-specified organization of said storage sub-areas,

said instructing apparatus providing instructions for causing said target data processing system to perform the steps of:

(a) subdividing the data of the re-organizable storage means into tiles, each tile corresponding to one or more access-wise adjacent storage sub-areas;

(b) recognizing as a definition of a goal state, pre-recorded indications of goal locations for tiles in the re-organizable storage space;

(c) identifying an already-existing vacancy space within the re-organizable storage means; and

(d) opportunistically pulling into the identified vacancy space the data of one or more source tiles that have that identified vacancy space defined by the recognized goal state as the goal location for the moved one or more source tiles.

48. An instructing apparatus according to claim 47 wherein said storage means includes a nonvolatile memory device selected from the group consisting of:

magnetic disk, writable-optical disk, flash EEPROM, EEPROM, and magnetic bubble memory.

49. An instructing apparatus according to claim 47 further providing instructions for causing said target data processing system to perform the step of:

(e) in a case where prior to the execution of said step (d) of opportunistically pulling it is determined that there is no already-existing vacancy space within the re-organizable storage mean, creating such a vacancy space and identifying the created vacancy space for use by said step (d) of opportunistically pulling.

50. An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of:

(e) limiting said opportunistic pulling of tiles to tiles associated with pre-identified files.

51. An instructing apparatus according to claim 50 further providing instructions for causing said target data processing system to perform the step of:

(f) updating the directory structure to define the logical linkages of sub-areas for a given file after the goal state for that given file is reached by said opportunistic pulling of tiles.

52. An instructing apparatus according to claim 50 further providing instructions for causing said target data processing system to perform the step of:

(f) updating the directory structure to define the logical linkages of sub-areas for remaining free spaces after the goal state for said pre-identified files is reached by said opportunistic pulling of tiles.

53. An instructing apparatus according to claim 47 wherein each tile corresponds to one storage sub-area.

54. An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of:

(e) generating and recording indications of goal locations for tiles so as to define a goal state that defragments one or more of said files.

55. An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of:

(e) generating and recording indications of goal locations for tiles so as to define a goal state that places pre-identified ones of said files in an access-wise fastest portion of said storage means.

56. An instructing apparatus according to claim 47 wherein said storage means includes a directory structure that defines logical linkages of said sub-areas as respective files or free spaces and wherein the instructing apparatus further provides instructions for causing said target data processing system to perform the step of:

(e) generating and recording indications of goal locations for tiles so as to define a goal state that leaves a pre-identified subset of said files in their original organization within said storage means.