System and method for defragmenting a file system

• US 6,397,311 B1
• Filed: 05/22/1995
• Issued: 05/28/2002
• Est. Priority Date: 01/19/1990
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Capps, James A.
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US08/445,592
• Time in Patent Office: 2,563 Days
• Field of Search: 395/400,425 711/11,1,3,4,165,170 709/1
• US Class Current: 711/165
• 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

Abstract

A system and method of defragmenting a file system is described which includes the steps of building a block descriptor array and reading a portion of the file system to a section of RAM creating new free space within the file system. The file blocks from the RAM are then written to free space within the file system. The pointers identifying the file blocks are then repaired on the disk. Files are then retrieved into the section of RAM for contiguous placement in the newly created free space within the file system. These files are then placed in contiguous manner into the new free space and the pointers identifying these files are repaired on the disk. The method of the present invention uses several optimization techniques and is designed such that it is secure from power loss during the defragmentation process.

Claims

1. A system for defragmenting a disk film system by arranging each block without gaps and in proper logical order, comprising:

a storage circuit;

a first circuitry for reading a first contiguous portion of the disk file system comprising a fragmented plurality of blocks into a first buffer in a storage circuit, and wherein said first contiguous portion has a size of n blocks, and wherein n is an integer;

a second circuitry for writing said fragmented plurality of blocks from said first buffer into a free space in the disk file system;

a third circuitry for continuous placing a second plurality of n blocks into a second buffer in the storage circuit; and

a fourth circuitry for contiguously writing said second plurality of blocks from said second buffer into said first contiguous portion of the disk file system without leaving gaps of said free space between adjacent blocks and in proper logical order, thereby writing said n blocks into said first contiguous portion of the disk file system,

wherein said system further comprises;

a plurality of file system control structures, each of which is associated with a block, comprises a pointer to said block, and having a location;

circuitry for creating a block descriptor array comprising data describing the location of said file system control structure for each block in the disk file system;

circuitry for storing said block descriptor array; and

circuitry for updating said block descriptor array during the defragmentation process as the locations of said blocks are changed,

wherein said system further comprises circuitry for changing values of pointers of said file system control structures associated with blocks which are moved during the defragmentation process,

wherein said circuitry for changing comprises inode cache circuitry for storing inodes having multiple pointers to be changed during the defragmentation of the disk file system such that said multiple pointers are adapted to be changed in said inode cache circuitry and wherein said inodes are adapted to be updated in said disk file system using a single write operation for each block of said inodes.

2. A system for defragmenting a disk film system by arranging each block without gaps and in proper logical order, comprising:

a storage circuit;

a first circuitry for reading a first contiguous portion of the disk file system comprising a fragmented plurality of blocks into a first buffer in a storage circuit, and wherein said first contiguous portion has a size of n blocks, and wherein n is an integer;

a second circuitry for writing said fragmented plurality of blocks from said first buffer into a free space in the disk file system;

a third circuitry for continuous placing a second plurality of n blocks into a second buffer in the storage circuit; and

a fourth circuitry for contiguously writing said second plurality of blocks from said second buffer into said first contiguous portion of the disk file system without leaving gaps of said free space between adjacent blocks and in proper logical order, thereby writing said n blocks into said first contiguous portion of the disk file system,

wherein said system further comprises;

a plurality of file system control structures, each of which is associated with a block, comprises a pointer to said block, and having a location;

circuitry for creating a block descriptor array comprising data describing the location of said file system control structure for each block in the disk file system;

circuitry for storing said block descriptor array; and

circuitry for updating said block descriptor array during the defragmentation process as the locations of said blocks are changed,

wherein said system further comprises circuitry for changing values of pointers of said file system control structures associated with blocks which are moved during the defragmentation process,

wherein said circuitry for changing comprises indirect cache circuitry for storing indirect blocks having multiple pointers to be changed during the defragmentation of the disk file system such that said multiple pointers are adapted to be changed in said indirect cache circuitry and wherein said indirect blocks are adapted to be updated in said disk file system using a single write operation per one of said indirect blocks.

3. A system for defragmenting a disk file system by arranging each block without gaps and improper logical order wherein each file of said disk file system corresponds to a file system control structure having a pointer to each block contained within said each file, comprising:

a storage circuit;

circuitry for sequentially reading into the storage circuit a plurality of contiguous portions containing n blocks of the disk file system, each of said contiguous portion comprising a fragmented plurality of blocks;

circuitry for writing each of said fragmented plurality of blocks into a free space in the disk file system;

circuitry for contiguous placing selected pluralities of blocks in each of said contiguous portions of the disk file system into the storage circuit;

circuitry for contiguously writing each of said selected pluralities of blocks into each of said plurality of contiguous portions of the disk file system without gaps of said free space between said blocks and in proper logical order, respectively;

circuitry for creating a block descriptor array comprising data describing a location of the file system control structure for each file in the disk file system;

circuitry for storing said block descriptor array;

circuitry for updating said block descriptor array during the degragmentation process as locations of said blocks are changed; and

circuitry for changing values of pointers associated with blocks moved during the defragmentation process,

wherein said circuitry for changing comprises inode cache circuitry for storing inodes having multiple pointers to be changed during the defragmentation of the disk file system such that said multiple pointers are adapted to be changed in said inode cache circuitry and wherein said inodes are adapted to be updated in said disk file system using a single write operation per each block of said inodes.

4. A system for defragmenting a disk file system by arranging each block without gaps and improper logical order wherein each file of said disk file system corresponds to a file system control structure having a pointer to each block contained within said each file, comprising:

a storage circuit;

circuitry for sequentially reading into the storage circuit a plurality of contiguous portions containing n blocks of the disk file system, each of said contiguous portion comprising a fragmented plurality of blocks;

circuitry for writing each of said fragmented plurality of blocks into a free space in the disk file system;

circuitry for contiguous placing selected pluralities of blocks in each of said contiguous portions of the disk file system into the storage circuit;

circuitry for contiguously writing each of said selected pluralities of blocks into each of said plurality of contiguous portions of the disk file system without gaps of said free space between said blocks and in proper logical order, respectively;

circuitry for creating a block descriptor array comprising data describing a location of the file system control structure for each file in the disk file system;

circuitry for storing said block descriptor array;

circuitry for updating said block descriptor array during the degragmentation process as locations of said blocks are changed; and

circuitry for changing values of pointers associated with blocks moved during the defragmentation process,

wherein said circuitry for changing comprises indirect cache circuitry for storing indirect blocks having multiple pointers to be changed during the defragmentation of the disk file system such that said multiple pointers are adapted to be changed in said indirect cache circuitry and said indirect blocks are adapted to be updated in said disk file system using a single write operation per one of said indirect blocks.

5. A computerized method for degragmenting a disk file system by arranging each block without gaps and in proper logical order, comprising the steps of:

reading a first contiguous portion of the disk file system comprising a fragmented plurality of blocks into a storage circuit, and wherein said first contiguous portion stores n blocks;

writing contiguously the fragmented plurality of blocks into a free space in the disk file system;

contiguous placing in the disk file system a second plurality of blocks in the storage circuit of n blocks from the disk file system;

writing the second plurality of blocks into the first contiguous portion of the file system, without gaps of said free space between blocks and in proper logical order,

wherein said method further comprises the step of;

changing the values of pointers associated with blocks which are moved during the defragmentation of the disk file system;

wherein said step of changing comprises the steps of;

storing inodes having multiple pointers to be changed during the defragmentation of the disk file system in an inode cache circuit; and

changing the multiple pointers in the inode cache circuit such that the inodes are adapted to be updated in the disk file system using a single write operation per each block of inodes.

6. A computerized method for degragmenting a disk file system by arranging each block without gaps and in proper logical order, comprising the steps of:

reading a first contiguous portion of the disk file system comprising a fragmented plurality of blocks into a storage circuit, and wherein said first contiguous portion stores n blocks;

writing contiguously the fragmented plurality of blocks into a free space in the disk file system;

contiguous placing in the disk file system a second plurality of blocks in the storage circuit of n blocks from the disk file system;

writing the second plurality of blocks into the first contiguous portion of the file system, without gaps of said free space between blocks and in proper logical order,

wherein said method further comprises the step of;

changing the values of pointers associated with blocks which are moved during the defragmentation of the disk file system;

wherein said step of changing comprises the steps of;

storing indirect blocks having multiple pointers to be changed during the defragmentation of the disk file system in a indirect cache circuit; and

changing the multiple pointers in the indirect cache circuit such that the indirect blocks are adapted to be updated in the file system using a single write operation per one of the indirect blocks.

7. A method for defragmenting a disk file system by arranging each block without gaps and in proper logical order, comprising the steps of:

creating a block descriptor array comprising data describing the location of a pointer to each block in the disk file system,

storing the block descriptor array

reading sequentially a plurality of contiguous portions of the disk file system into a storage circuit, each of the plurality of contiguous portions comprising a fragmented plurality of blocks, wherein each contiguous portion is adapted for storing n blocks;

writing each of the fragmented plurality of blocks into a free space in the disk file system;

reading selected pluralities of blocks into the storage circuit and contiguous placing the selected pluralities of blocks in each of the contiguous portions of the disk file system;

writing contiguously each of the selected pluralities of blocks into each of the plurality of contiguous portions of the disk file system, respectively, without introducing gaps of said free space between said blocks and in proper logical order;

updating the block descriptor array during the defragmentation process as the locations of the blocks change; and

changing values of pointers associated with blocks moved during the defragmentation process;

wherein said step of changing comprises the steps of;

storing inodes having multiple pointers to be changed during the defragmentation of the disk file system in an inode cache circuit; and

changing the multiple pointers in the inode cache circuit such that the inodes are adapted to be updated in the disk file system using a single write operation per one of the inodes.

8. A method for defragmenting a disk file system by arranging each block without gaps and in proper logical order, comprising the steps of:

creating a block descriptor array comprising data describing the location of a pointer to each block in the disk file system,

storing the block descriptor array

reading sequentially a plurality of contiguous portions of the disk file system into a storage circuit, each of the plurality of contiguous portions comprising a fragmented plurality of blocks, wherein each contiguous portion is adapted for storing n blocks;

writing each of the fragmented plurality of blocks into a free space in the disk file system;

reading selected pluralities of blocks into the storage circuit and contiguous placing the selected pluralities of blocks in each of the contiguous portions of the disk file system;

writing contiguously each of the selected pluralities of blocks into each of the plurality of contiguous portions of the disk file system, respectively, without introducing gaps of said free space between said blocks and in proper logical order;

updating the block descriptor array during the defragmentation process as the locations of the blocks change; and

changing values of pointers associated with blocks moved during the defragmentation process;

wherein said step of changing comprises the steps of;

storing indirect blocks having multiple pointers to be changed during the defragmentation of the disk file system in an indirect cache circuit; and

changing the multiple pointers in the indirect cache circuit such that the indirect blocks are adapted to be updated in the file system using a single write operation per block of the indirect blocks.