High performance file system

• US 5,371,885 A
• Filed: 08/29/1989
• Issued: 12/06/1994
• Est. Priority Date: 08/29/1989
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Letwin, James G.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/400,533
• Time in Patent Office: 1,925 Days
• Field of Search: 395/600, 364/DIG. 1 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/1794 Details of file format conversion
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G11B 20/1252 for discontinuous data, e.g. digital information signals, computer programme data
• CPC Class Codes: G11B 27/329 on a disc [VTOC]
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A system and method for allocating contiguous portions of memory to a file. On or more file nodes are provided for allocating memory to one or more files, and the location of these file nodes is maintained. Within these file nodes, the location of one or more runs of contiguous portions of memory are maintained. These contiguous portions of memory are allocated to a file in accordance with the corresponding file node. In one embodiment, the file nodes can be extended in a binary tree structure of additional nodes each storing locations of runs of contiguous portions of memory.

Claims

1. A method in a computer system for tracking allocations of memory, the memory comprising a plurality of bands, each band comprising a plurality of sectors, each sector comprising a plurality of memory locations, the method comprising the steps of:

allocating a bitmap for each of the plurality of bands, each bitmap having a bit for each sector within the band;

when allocating a sector of memory, setting a bit in the bitmap of the band that contains the sector to indicate that the sector is allocated; and

when deallocating a sector of memory, setting a bit in the bitmap of the band that contains the sector to indicate that the sector is deallocated.

2. The method of claim 1 wherein the step of allocating a bitmap further includes the step of selecting a portion of memory proximate to each band for the allocation of the bitmap.

3. The method of claim 1 wherein the step of allocating a bitmap further includes the step of selecting a portion of memory such that bitmaps for pairs of logically contiguous bands are allocated in logically contiguous memory locations.

4. The method of claim 1 wherein the step of allocating the bitmap further includes the step of selecting a portion of memory at a head or a tail of each band for allocation of the bitmap such that two bitmaps are allocated adjacent memory locations between alternate bands.

5. The method of claim 3 or 4 including the steps of allocating to one file a group of logically contiguous sectors from two logically contiguous bands and identifying the group of logically contiguous sectors by an indicator of a first sector and an indicator of a last sector in the group.

6. A method in a computer system for tracking the allocation of memory locations to a file, the computer system having a memory with a plurality of memory locations, the method comprising the steps of:

allocating memory locations for a file FNODE, the file FNODE having memory locations for storing indicators of variable-length runs of logically contiguous memory locations allocated to the file;

allocating a plurality of variable-length runs of logically contiguous memory locations to the file;

for each run allocated to the file, setting an indicator in the file FNODE to identify a location and length of the run; and

when the number of runs exceeds the capacity of the file FNODE for storing indicators of runs, storing in the file FNODE pointers to portions of memory locations, the portions for storing indicators of the runs allocated to the file.

9. The method of claim 6 or 8 including the step of increasing the length of a last run of the file to indicate an increase in file size.

10. The method of claim 6 or 8 including the step of when accessing a logical location within the file, summing the lengths of a plurality of runs of the file to determine the memory location of the logical file location.

7. A method in a computer system for tracking the allocation of memory locations to a file, the computer system having a memory with a plurality of memory locations, the method comprising the steps of:

allocating memory locations for a file FNODE, the file FNODE having memory locations for storing indicators of variable-length runs of logically contiguous memory locations allocated to the file;

allocating a plurality of variable-length runs of logically contiguous memory locations to the file; and

for each run allocated to the file, setting an indicator in the file FNODE to identify a location and length of the run wherein the indicators are stored in a tree structure.

8. The method of claim 7 wherein the tree structure is a B+ tree.

11. A method in a computer system of maintaining a directory hierarchy on a file storage device, the method comprising the steps of:

for each directory,

allocating a directory FNODE, each directory FNODE having a pointer to a directory structure; and

allocating a directory structure, the directory structure comprising a plurality of directory entries, each directory entry having a pointer to a file FNODE or a directory FNODE.

12. The method of claim 11 including the step of organizing the directory structure as a tree structure of directory entries.

13. The method of claim 12 including the step of organizing the tree structure as a B tree.

14. The method of claim 11 wherein the file storage device is a disk device, the method including the step of designating a band of memory locations as a directory band wherein the step of allocating a directory structure selects the directory band for allocating the directory structure.

15. The method of claim 14 wherein the step of designating a directory band designates a directory band near a seek center of the disk device.

16. The method of claim 11 including the steps of:

designating a directory as a root directory; and

storing a pointer to the directory FNODE of the root directory at a predefined location on the file storage device.

17. A method in a computer system for organizing files in a hierarchical manner on a storage device, the hierarchy of files comprising a plurality of directories and files, the storage device having a plurality of logically contiguous sectors, each sector having a plurality of logically contiguous locations, the method comprising the steps of:

allocating a descriptive block portion of the storage device, the descriptive block portion having a file system information portion and a sector allocation portion, the file system information portion having a pointer to a root directory, the sector allocation portion containing information describing the allocation of the sectors;

for each directory, allocating a directory portion of the storage device for storing information relating to the directory, the directory portion having a directory FNODE portion and a directory block portion, the directory FNODE portion containing information describing the directory, the directory block portion containing entries describing each directory and file within the directory; and

for each file, allocating a file portion of the storage device for storing information relating to the file, the file portion having a file FNODE portion and a data portion, the file FNODE portion containing information identifying the file and a plurality of run indicators, each run indicator identifying a run of a plurality of logically contiguous locations, the data portion comprising a plurality of runs.

18. The method of claim 17 wherein the step of allocating a descriptive portion includes the step of allocating the sector allocation portion as a plurality of bitmaps, one bitmap associated with each band of sectors, each bitmap having a bit for each sector within the associated band, the bit indicating allocation status of the sector.

19. The method of claim 18 wherein the step of allocating the sector allocation portion as a plurality of bitmaps includes the step of allocating the bitmaps such that each bitmap is proximate to the associated band.

20. The method of claim 18 wherein the step of allocating the sector allocation portion as a plurality of bitmaps includes the step of allocating the bitmaps at a tail or a head of the associated bands such that bitmaps are adjacent between alternate bands.

21. The method of claim 18 wherein the step of allocating the sector allocation portion as a plurality of bitmaps includes the step of allocating the bitmaps such that the bitmaps for logically contiguous bands are allocated in logically contiguous sectors.

22. The method of claim 17 wherein the step of allocating a descriptive block portion includes the step of allocating the file system information portion to include a super block portion, the super block portion containing a directory block band pointer, the directory block band pointer pointing to a band of sectors in which directory blocks are stored based on a preference.

23. The method of claim 22 including the step of allocating the directory block band near a seek center of the storage device.

24. The method of claim 17 wherein the step of allocating a descriptive block portion includes the step of allocating the file system information portion to include a spare block portion, the spare block portion containing a hot fix map, the hot fix map identifying a good sector as a replacement for a bad sector.

25. The method of claim 24 including the steps of:

when a read request is directed to a bad sector, mapping the bad sector to the good sector based on the hot fix map; and

redirecting the read request to the good sector.

26. The method of claim 17 wherein the step of allocating a directory portion includes the steps of designating a band of sectors as a directory band and allocating the directory portion within the directory band.

27. The method of claim 26 wherein the step of designating designated a band of sectors near seek center of the storage device.

28. The method of claim 17 wherein the step of allocating a directory portion includes the step of allocating the directory block portion as a tree structure.

29. The method of claim 28 wherein the step of allocating the directory block portion as a B tree structure.

30. The method of claim 17 wherein the step of allocating a descriptive block portion includes the step of allocating the file system information portion to include a boot block portion, the boot block portion containing a bootstrap program.

31. The method of claim 17 wherein the step of allocating a descriptive block portion includes the step of allocating the file system information portion to include a super block portion, the super block portion containing a bitmap list pointer to a list of bitmap pointers, each bitmap pointer pointing to a bitmap that describes the allocation of a band of sectors.

32. The method of claim 17 wherein the step of allocating a descriptive block portion includes the step of allocating the file system information portion to include a spare block portion, the spare block portion containing a pointer to a free block list of unallocated sectors for use to ensure sufficient unallocated sector are available for balancing of a B tree hierarchy of directories.

33. The method of claim 17 wherein the step of allocating a directory portion includes the step of, for each entry in the directory block portion, storing a pointer to a directory FNODE or file FNODE.

34. The method of claim 17 wherein the step of allocating a file portion includes the step of allocating the plurality of run indicators as a tree directory structure.

35. The method of claim 17 wherein the step of allocating a file portion includes the step of allocating the plurality of run indicators as a B+ tree directory structure.

36. A computer system for tracking storage device allocations, comprising:

a storage device having a plurality of bands, each band having a plurality of sectors, each sector having a plurality of storage locations;

means for allocating a bitmap for each of the plurality of bands, each bitmap having a bit for each sector within the band;

means for setting a bit in the bitmap of the band that contains the sector to indicate that the sector is allocated; and

means for setting a bit in the bitmap of the band that contains the sector to indicate that the sector is deallocated.

37. The system of claim 36 including means for selecting storage locations near to each band for the allocation of the bitmap.

38. The system of claim 36 including means for selecting storage locations such that bitmaps for pairs of logically contiguous bands are allocated in logically contiguous storage locations.

39. The system of claim 36 including means for selecting storage locations at a head or a tail of each band for allocation of the bitmap such that two bitmaps are allocated adjacent storage locations between alternate bands.

40. The system of claim 38 or 39 including means for allocating to one file a group of logically contiguous sectors from two logically contiguous bands and means for identifying the group of logically contiguous sectors by an indicator of a first sector and an indicator of a last sector in the group.

41. A computer system for maintaining a directory hierarchy, comprising:

a file storage device;

means for allocating a first directory structure within the file storage device, each first directory having a pointer to a second directory structure; and

means for allocating a second directory structure within the file storage device, the second directory structure comprising a plurality of directory entries, each directory entry having an identifier of a file or a directory whereby the first directory structures and the second directory structures form a directory hierarchy.

42. The system of claim 41 including means for organizing the second directory structure as a tree structure of directory entries.

43. The system of claim 42 including means for organizing the tree structure as a B tree.

44. The system of claim 41 including means for designating a directory as a root directory, and means for storing an identifier of the first directory structure of the root directory at a location on the file storage device.

45. The system of claim 41, 42, 43, or 44 wherein the file storage device is a disk device, and including means for designating a band of memory locations as a directory band and wherein the means for allocating a second directory structure selects the directory band for allocating the second directory structure.

46. The system of claim 45 wherein the means for designating a directory band designates a directory band near a seek center of the disk device.

47. A computer system for tracking the allocation of memory locations to a file, comprising:

a memory with a plurality of memory locations;

means for allocating memory locations for a file node, the file node having memory locations for storing indicators of variable-length runs of logically contiguous memory locations allocated to the file;

means for allocating a plurality of variable-length runs of logically contiguous memory locations to the file; and

means for setting an indicator in the file node to identify a location and length of the run; and

means for storing in the file node identifiers of portions of memory locations, when the number of runs exceeds the capacity of the file node for storing indicators of runs, the portions for storing indicators of the runs allocated to the file.

48. The system of claim 47 wherein the means for storing the indicators stores the indicators in a B+ tree.

50. The system of claim 47, 48, or 49 including means for increasing the length of a last run of the file to indicate an increase in file size.

51. The system of claim 47, 48, or 49 including means for summing the lengths of a plurality of runs of the file to determine the memory location of the logical file location when accessing a logical location within the file.

49. A computer system for tracking the allocation of memory locations to a file, comprising:

a memory With a plurality of memory locations;

means for allocating memory locations for a file node, the file node having memory locations for storing indicators of variable-length runs of logically contiguous memory locations allocated to the file;

means for allocating a plurality of variable-length runs of logically contiguous memory locations to the file; and

means for setting an indicator in the file node to identify a location and length of the run; and

means for storing the indicators in a tree structure.

52. A computer system for organizing files in a hierarchical manner, the hierarchy of files comprising a plurality of directories and files, comprising:

a storage device having a plurality of logically contiguous sectors, each sector having a plurality of logically contiguous locations;

means for allocating a descriptive block portion of the storage device, the descriptive block portion having a file system information portion and a sector allocation portion, the file system information portion having an indicator of a root directory, the sector allocation portion containing information describing the allocation of the sectors;

means for allocating a directory portion of the storage device for storing information relating to the directory, the directory portion having a directory node portion and a directory block portion, the directory node portion containing information describing the directory, the directory block portion containing entries describing each directory and file within a directory; and

means for allocating a file portion of the storage device for storing information relating to the file, the file portion having a file node portion and a data portion, the file node portion containing information identifying the file and a plurality of run indicators, each run indicator identifying a run of a plurality of logically contiguous locations, the data portion comprising a plurality of runs.

53. The system of claim 52 including means for allocating the sector allocation portion as a plurality of bitmaps, one bitmap associated with each band of sectors, each bitmap having a bit for each sector within the associated band, the bit indicating allocation status of the sector.

54. The system of claim 53 including means for allocating the bitmaps at a tail or a head of the associated bands such that bitmaps are adjacent between alternate bands.

55. The system of claim 53 including means for allocating the bitmaps such that each bitmap is proximate to the associated band.

56. The system of claim 53 including means for allocating the bitmaps such that the bitmaps for logically contiguous bands are allocated in logically contiguous sectors.

57. The system of claim 52 including means for allocating the file system information portion to include a super block portion, the .super block portion containing a directory block band pointer, the directory block band pointer pointing to a band of sectors in which directory blocks are stored based on a preference.

58. The system of claim 57 including means for allocating the directory block band near a seek center of the storage device.

59. The system of claim 52 including means for designating a band of sectors as a directory band, and means for allocating the directory portion within the directory band.

60. The system of claim 59 including means for designating a band of sectors near seek center of the storage device.

61. The system of claim 52 including means for allocating the file system information portion to include a spare block portion, the spare block portion containing a hot fix map, the hot fix map identifying a good sector as a replacement for a bad sector.

62. The system of claim 61 including means for:

mapping the bad sector to the good sector based on the hot fix map when a read request is directed to a bad sector, and means for redirecting the read request to the good sector.

63. The system of claim 52 including means for allocating the file system information portion to include a boot block portion, the boot block portion containing a bootstrap program.

64. The system of claim 52 including means for allocating the file system information portion to include a super block portion, the super block portion containing a bitmap list pointer to a list of bitmap pointers, each bitmap pointer pointing to a bitmap that describes the allocation of a band of sectors.

65. The system of claim 52 including means for allocating the file system information portion to include a spare block portion, the spare block portion containing a pointer to a free block list of unallocated sectors for use to ensure sufficient unallocated sector are available for balancing of a B tree hierarchy of directories.

66. The system of claim 52 including means for storing a pointer to a directory node or file node for each entry in the directory block portion.

67. The system of claim 52 including means for allocating the plurality of run indicators as a B+ tree directory structure.

68. The system of claim 52 including means for allocating the directory block portion as a B tree structure.

69. The system of claim 52 including means for allocating the plurality of run indicators as a tree directory structure.

70. The system of claim 52 including means for allocating the directory block portion as a tree structure.