OPTIMIZED STARTUP VERIFICATION OF FILE SYSTEM INTEGRITY

• US 20110072061A1
• Filed: 12/01/2010
• Published: 03/24/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
• Granted Patent: US 8,051,114 B2
• Time in Patent Office: Days
• US Class Current: 707/826
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

A computer system that may be used in implementing a transaction based file system is disclosed. The computer system includes a processor, random access memory that may be accessible by the processor, and a persistent data storage device that is likewise accessible by the processor. The computer system also may include file system software. The file system software may be executed by the processor and operates to manage the file data and the file system structure of the files stored on the persistent data storage device. Additionally, the file system software may maintain 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 may include one or more fields that are designated to store information corresponding to a file transaction that is represented by the transaction record. If the operation of the file system software is interrupted, the file system software may resume its execution using a startup process in which a reconstructed file system may be generated in the random access memory. During system restart, the startup process may skip verification of the data section of a transaction record when the transaction record meets one or more predetermined criterion. For example, the startup process may make a distinction between transaction records merely affecting file data versus transaction records that affect the metadata of the file system. As transactions are found during the startup process, the file system software may identify whether a transaction impacts file data or metadata. Since only the metadata is required to ensure that the file system is in a consistent state after startup, the transaction records relating to metadata may be selected as the only subset of transaction records that are subject to complete verification. Verification of other transaction records may, for example, be limited to a check of the information contained in the header section of each remaining transaction record.

Claims

1. A computer-implemented method comprising:

providing a file system structure of files on a persistent data storage device;

maintaining a transaction file on the persistent data storage device;

including a plurality of transaction records in the transaction file with a processor, each of the transaction records comprising a header section and a data section, each of the transaction records representing a file transaction that affects at least one of the files stored on the persistent data storage device;

including header data in the header section of each of the transaction records, the header data corresponding to the file transaction represented by each of the transaction records;

identifying, in the header data of the header section of each of the transaction records, the at least one of the files affected by the file transaction represented by each of the transaction records;

including, in the data section of each of the transaction records, file data for the at least one of the files identified in the header section of each of the transaction records;

including, in the header section of each of the transaction records, a first error correction code for verification and correction of the header data of the header section of each of the transaction records;

including, in the header section of each of the transaction records, a second error correction code for verification and correction of the file data of the data section of each of the transaction records; and

generating a reconstructed file system in a random access memory with the processor in a startup process from the transaction records of the transaction file;

where, when the header data in the header section of each of the transaction records meets a first predetermined criterion, the startup process applies the first error correction code when verifying and, if required, when correcting the header data of the header section of each of the transaction records while skipping verification and correction of the file data of the data section of each of the transaction records as the startup process generates the reconstructed file system from each of the transaction records; and

where, when the header data in the header section of each of the 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 each of the transaction records as the startup process generates the reconstructed file system from each of the transaction records, where the startup process applies the first error correction code when verifying and, if required, correcting the header data of the header section of each of the transaction records, and the startup process applies the second error correction code when verifying and, if required, correcting the file data of the data section of each of the transaction records.

2. The method of claim 1 where the persistent data storage device comprises flash memory.

3. The method of claim 2 where the flash memory is organized into memory blocks, and where each memory block comprises multiple memory pages.

4. The method of claim 1 further comprising organizing the reconstructed file system as an inverted file hierarchy.

5. A computer-implemented method comprising:

storing a file system structure of files and directories on a persistent data storage device with a processor;

storing a transaction file on the persistent data storage device with the processor;

including a plurality of transaction records in the transaction file with the processor, at least one of transaction records for a metadata file that includes information relating to a hierarchical arrangement of the files and the directories of the file system structure, each of the transaction records representing a file transaction;

including a header section and a data section in each of the transaction records with the processor, where the header section of each of the transaction records comprises header data corresponding to the file transaction represented by each of the transaction records and identifies a file corresponding to the file transaction, where the data section of each of the transaction records comprises file data for the file identified in the header section, where the header section includes a first error correction code for verification and correction of the header data of the header section, and where the header section further includes a second error correction code for verification and correction of the file data of the data section; and

generating a reconstructed file system in a random access memory with the processor in a startup process from the transaction records of the transaction file;

where generating the reconstructed file system comprises, when the header data in the header section of each of the transaction records meets a first predetermined criterion, applying the first error correction code for verification and, if required, correction of the header data of the header section of each of the transaction records while skipping verification and correction of the file data of the data section of each of the transaction records; and

where generating the reconstructed file system further comprises, when the header data in the header section of each of the transaction records indicates that each of the transaction records applies to the metadata file, verifying and, if required, correcting both the file data of the data section and the header data of the header section of each of the transaction records, by applying the first error correction code when verifying or correcting the header data of the header section of each of the transaction records, and by applying the second error correction code when verifying or correcting the file data of the data section of each of the transaction records.

6. The method of claim 5 where the persistent data storage device comprises a flash memory.

7. The method of claim 6 where the flash memory is organized into memory blocks, and where each memory block comprises multiple memory pages.

8. The method of claim 5 further comprising organizing the reconstructed file system as an inverted file hierarchy with the processor.

9. A computer-implemented method comprising:

providing a file system structure of files on a persistent data storage device;

storing a transaction file in a flash media;

where the flash media is organized into memory blocks, and each of the memory blocks includes a plurality of memory pages;

including a plurality of transaction records in the transaction file with a processor, each of the transaction records comprising a header section and a data section and represents a file transaction, where the header section of each of the transaction records includes header data corresponding to the file transaction represented by each of the transaction records and identifies a file affected by the file transaction, the data section comprises file data for the file identified in the header section of each of the transaction records, where the header section includes an error correction code for verification and, if required, correction of the header section or data section of the each of the transaction records, and where at least one of the memory blocks include multiple transaction records of the transaction records;

generating a reconstructed file system in a random access memory with the processor in a startup process using the transaction records of the transaction file;

where the startup process verifies and, if necessary, corrects the header section or data section of each of a first occurring transaction record for a file in a sequence of transaction records stored in a memory block as the startup process generates the reconstructed file system, where the startup process determines that each of the first occurring transaction record is the first occurring transaction record for the 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 the 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. The method of claim 9 where the reconstructed file system is organized by the file system code as an inverted file hierarchy.

11. A computer-implemented method comprising:

providing a file system structure of files stored on a persistent data storage device;

providing a transaction file on the persistent data storage device, where the transaction file includes a plurality of transaction records, each of the transaction records comprises a header section and a data section, and each of the transaction records represents a type of file;

including header data in the header section of each of the transaction records with a processor, the header data identifying a file stored on the persistent data storage device and the type of file represented by each of the transaction records;

including file data in the data section of each transaction record of the transaction records with the processor, the file data for the file identified in the header section of each of the transaction records, where the header section includes verification information for verification of at least one of the header data and the file data of each of the transaction records;

generating a reconstructed file system in a random access memory with a processor in a startup process based on the transaction records of the transaction file;

where generating the reconstructed file system in the startup process comprises executing different verification actions on each of the transaction records depending on the header data that identifies the type of file represented by each of the transaction records, where the different verification actions include use of the verification information of the header section of each of the transaction records, and where the different verification actions have different computational costs.