Optimized startup verification of file system integrity

• US 7,970,803 B2
• Filed: 07/01/2005
• Issued: 06/28/2011
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Company (Blackberry Limited)
• Inventors: Dodge, Dan
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Mitiku; Berhanu
• Application Number:
  US11/173,798
• Publication Number:
  US 20070005560A1
• Time in Patent Office: 2,188 Days
• Field of Search: 702/119, 707/202
• US Class Current: 707/822
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

A computer system having a transaction based file system is disclosed. The computer system includes file system software that manages the file data and the file system structure of files stored on a persistent data storage device and maintains a transaction file that includes a plurality of transaction records. Each of the transaction records has a header section and a data section. The header section of each transaction record includes one or more fields that are designated to store information corresponding to a file transaction that is represented by the transaction record. The file system software executes a startup process in which a reconstructed file system is generated in random access memory. The startup process skips verification of the data section of a transaction record when the transaction record meets one or more predetermined criterion.

Claims

1. A computer system comprising:

a persistent data storage device;

a file system code for managing data and a file system structure of files stored on the persistent data storage device;

a transaction file maintained by the file system code and stored on the persistent data storage device;

where the transaction file includes a plurality of transaction records, each of the plurality of transaction records comprises a header section and a data section, and each of the plurality of transaction records represents a file transaction affecting at least one of the files stored on the persistent data storage device;

where header data in the header section of each transaction record of the plurality of transaction records corresponds to the file transaction represented by the each transaction record of the plurality of transaction records and identifies the at least one of the files affected by the file transaction, and the data section of the each transaction record of the plurality of transaction records contains file data for the at least one of the files identified in the header section of the each transaction record of the plurality of transaction records, where the header section includes a first error correction code for verifying and correcting the header data of the header section of the each transaction record of the plurality of transaction records, and where the header section further includes a second error correction code for verifying and correcting the file data of the data section of the each transaction record of the plurality of transaction records;

where the file system code is executable to implement a startup process in which a reconstructed file system is generated in a random access memory using the plurality of transaction records of the transaction file;

where, when the header data in the header section of a transaction record of the plurality of transaction records meets a first predetermined criterion, the startup process applies the first error correction code to verify and, if required, correct the header data of the header section of the transaction record of the plurality of transaction records while skipping verification and correction of the file data of the data section of the transaction record of the plurality of transaction records as the startup process uses the transaction record of the plurality of transaction records to generate the reconstructed file system; and

where, when the header data in the header section of the transaction record of the plurality of transaction records meets a second predetermined criterion, the startup process verifies and, if required, corrects both the header data of the header section and the file data of the data section of the transaction record of the plurality of transaction records as the startup process uses the transaction record of the plurality of transaction records to generate the reconstructed file system, where the first error correction code is applied by the startup process to verify and, if required, correct the header data of the header section of the transaction record of the plurality of transaction records, and the second error correction code is applied by the startup process to verify and, if required, correct the file data of the data section of the transaction record of the plurality of transaction records.

2. A computer system as claimed in claim 1 where the persistent data storage device comprises flash memory.

3. A computer system as claimed in claim 2 where the flash memory is organized into memory blocks, and where each memory block comprises multiple memory pages.

4. A computer system as claimed in claim 1 where the reconstructed file system is organized by the file system code as an inverted file hierarchy.

5. A computer system comprising:

a persistent data storage device;

a file system code for managing data and a file system structure of files and directories stored on the persistent data storage device;

a transaction file maintained by the file system code and stored on the persistent data storage device;

a metadata file including information relating to a hierarchical arrangement of the files and the directories of the file system structure;

where the transaction file includes a plurality of transaction records including a plurality of transaction records for the metadata file, and each transaction record of the plurality of transaction records represents a file transaction and comprises a header section and a data section, where the header section of the each transaction record of the plurality of transaction records includes header data corresponding to the file transaction represented by the each transaction record of the plurality of transaction records and identifies a file corresponding to the file transaction and the data section contains file data for the file identified in the header section of the transaction record, where the header section includes a first error correction code for verifying and correcting the header data of the header section of the transaction record, and where the header section further includes a second error correction code for verifying and correcting the file data of the data section of the transaction record; and

where the file system code includes a startup process in which a reconstructed file system is generated in a random access memory using the plurality of transaction records of the transaction file;

where, when the header data in the header section of a transaction record of the plurality of transaction records meets a first predetermined criterion, the startup process applies the first error correction code to verify and, if required, correct the header data of the header section of the transaction record of the plurality of transaction records while skipping verification and correction of the file data of the data section of the transaction record of the plurality of transaction records as the startup process uses the transaction record of the plurality of transaction records to generate the reconstructed file system; and

where, when the header data in the header section indicates that the transaction record of the plurality of transaction records applies to the metadata file, the startup process verifies and, if required, corrects both the file data of the data section and the header data of the header section of the transaction record of the plurality of transaction records as the startup process uses the transaction record of the plurality of transaction records to generate the reconstructed file system, where the first error correction code is applied by the startup process to verify and, if required, correct the header data of the header section of the transaction record of the plurality of transaction records, and the second error correction code is applied by the startup process to verify and, if required, correct the file data of the data section of the transaction record of the plurality of transaction records.

6. A computer system as claimed in claim 5 where the persistent data storage device comprises a flash memory.

7. A computer system as claimed in claim 6 where the flash memory is organized into memory blocks, and where each memory block comprises multiple memory pages.

8. A computer system as claimed in claim 5 where the reconstructed file system is organized by the file system code as an inverted file hierarchy.

9. A computer system comprising:

a persistent data storage device;

a file system code for managing data and a file system structure of files stored on the persistent data storage device;

transaction file maintained by the file system code and stored in a flash media;

where the flash media is organized into memory blocks, and each memory block includes a plurality of memory pages, where the transaction file includes a plurality of transaction records, each of the plurality of transaction records comprises a header section and a data section and represents a file transaction, and where the header section of the each transaction record of the plurality of transaction records includes header data corresponding to the file transaction represented by the each transaction record of the plurality of transaction records and identifies a file affected by the file transaction, the data section contains file data for the file identified in the header section of the each of the plurality of transaction records, where the header section includes an error correction code for verifying and, if required, correcting the header section or data section of the each of the plurality of transaction records, and where some of the memory blocks include multiple transaction records of the plurality of transaction records;

where the file system code is executable to implement a startup process in which a reconstructed file system is generated in a random access memory using the plurality of transaction records of the transaction file;

where the startup process verifies and, if necessary, corrects the header section or data section of a transaction record of a first occurring transaction record for a file in a sequence of transaction records stored in the memory block as the startup process generates the reconstructed file system, where the startup process determines that the transaction record is the first occurring transaction record for a file in the sequence of transaction records using the header data in the header section of the transaction record; and

where the startup process skips any verification and correction of the header data of the header sections and the file data of the data sections of tailing transaction records in the memory block when the first occurring transaction record and tailing transaction records are stored in the same memory block and affect the same file, where the startup process determines that the transaction records stored in the same memory block affect the same file using the header data of the header section of the transaction records stored in the memory block.

10. A computer system as claimed in claim 9 where the reconstructed file system is organized by the file system code as an inverted file hierarchy.

11. A computer system comprising:

a persistent data storage device;

a file system code for managing data and a file system structure of files stored on the persistent data storage device;

a transaction file maintained by the file system code and stored on the persistent data storage device;

where the transaction file includes a plurality of transaction records, each of the plurality of transaction records comprises a header section and a data section and each of the plurality of transaction records represents a type of file;

where the header section of each transaction record of the plurality of transaction records includes header data identifying a file stored on the persistent data storage device and the type of file represented by the each transaction record of the plurality of transaction records, and the data section contains file data for the file identified in the header section of the each transaction record of the plurality of transaction records, where the header section includes verification information for verifying the header data of the header section and/or the file data of the data section of the each transaction record of the plurality of transaction records;

where the file system code is executable to implement a startup process in which a reconstructed file system is generated in a random access memory using the plurality of transaction records of the transaction file;

where the startup process uses the header data identifying the type of file represented by a transaction record of the plurality of transaction records to execute different verification actions on the transaction record of the plurality of transaction records as the transaction record of the plurality of transaction records is used to generate the reconstructed file system, where the different verification actions include use of the verification information of the header section of the transaction record of the plurality of transaction records, and where the different verification actions have different computational costs.