Flash Recovery Employing Transaction Log

• US 20090287874A1
• Filed: 05/13/2008
• Published: 11/19/2009
• Est. Priority Date: 05/13/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Patel, Sachin, Rogers, Andrew M.
• Granted Patent: US 7,979,626 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory

Abstract

A transaction log for flash recovery includes a chained sequence of blocks specifying the operations that have been performed, such as a write to a sector or an erase to a block. Checkpoints are performed writing the entire flash state to flash. Once a checkpoint is performed, all of the log entries prior to the checkpoint are deleted and the log processing on recovery begins with the latest checkpoint. If the system is able to safely shutdown, then a checkpoint may be performed before the driver unloads, and on initialization, the entire persisted flash state may be loaded into the flash memory with a minimal amount of flash scanning. If a power failure occurs during system operation, then on the next boot-up, only the sectors or blocks specified in the log entries after the latest checkpoint have to be scanned, rather than all the sectors on the part.

Claims

1. A method to be executed at least in part in a computing device for flash memory recovery employing a transaction log, the method comprising:

during flash memory operations, generating the transaction log comprising a chained sequence of blocks specifying performed flash memory operations;

performing a checkpoint by writing an entire flash memory state into a specified location in the flash memory;

upon completing the checkpoint, deleting all transaction log entries, wherein a final checkpoint is performed prior to a flash driver unload during a safe shutdown;

if the flash memory is initialized following the safe shutdown, loading the entire flash state based on the final checkpoint; and

if the flash memory is initialized following an unexpected shutdown without performing a complete checkpoint prior to the flash driver unload, recovering the flash memory state by scanning transaction log entries after a last checkpoint.

2. The method of claim 1, wherein each block on the flash memory includes a forward pointer to a next block in the chain and a backwards pointer to a previous block in the chain, wherein each sector within any block stores a single log entry, and wherein the transaction log is stored in an arbitrary location in the flash memory without being pre-reserved to a specific set of blocks.

3. The method of claim 2, wherein each log block is identified by a special log bit in a spare area of the flash memory within each corresponding sector, and each block is scanned from a beginning of the flash memory until a block with the special log bit is found in order to locate the transaction log upon initialization.

4. The method of claim 3, further comprising:

upon locating the block with the special log bit, locating a remainder of the transaction log by following the forward and backward pointers; and

locating the last checkpoint by starting at an end of the transaction log and examining each of the log entries backwards until the last checkpoint is found.

5. The method of claim 2, wherein each log entry is of a type comprising one from a set of:

a write log entry, an erase log entry, a checkpoint log entry, and a recover write log entry.

6. The method of claim 5, wherein a master mapping table, a dirty block list, and a free block list are flushed upon recording of a checkpoint entry in the transaction log.

7. The method of claim 1, further comprising:

prior to performing a write operation, allocating a predefined set of blocks for future write operations;

recording a transaction log entry specifying the allocated set of blocks; and

performing subsequent write operations to the allocated set of blocks without recording any additional log entries.

8. The method of claim 1, further comprising:

recording a transaction log entry for every erase operation involved in a compaction to reclaim dirty sectors.

9. The method of claim 1, wherein recovering the flash memory state by scanning transaction log entries after the last checkpoint following an unexpected shutdown comprises:

locating the transaction log upon initialization;

determining the last checkpoint entry; and

constructing a write block list for data writes, a write block list for mapping table writes, and an erase block list for erased blocks subsequent to the last checkpoint.

10. The method of claim 9, wherein constructing the write block list for data writes, the write block list for mapping table writes, and the erase block list for erased blocks comprises:

re-performing the write operations subsequent to the last checkpoint by updating a new logical to physical sector mapping for each mapping table block and data block; and

adding all blocks in the erase block list to a free block list.

11. The method of claim 10, further comprising:

subsequent to each update, determining whether the corresponding write operation is the last write operation;

if the write operation is the last write operation validating a checksum for detecting partially written sectors;

else

repeating the update for a subsequent block.

12. The method of claim 1, wherein recovering the flash memory state by scanning transaction log entries after the last checkpoint following an unexpected shutdown further comprises:

if a last transaction log entry is a checkpoint entry, validating a checksum of the flash state to determine whether the flash state has been completely written prior to the unexpected shutdown; and

if the flash state is incomplete, erasing blocks containing the flash state and writing a new flash state may be written to the same blocks once the transaction log is completely scanned.

13. The method of claim 1, wherein recovering the flash memory state by scanning transaction log entries after the last checkpoint following an unexpected shutdown further comprises:

if a last transaction log entry if an erase operation following a plurality of write operations forming a compaction operation, repeating the erase operation.

14. The method of claim 1, wherein recovering the flash memory state by scanning transaction log entries after the last checkpoint following an unexpected shutdown further comprises:

if a last transaction log entry if a write operation, examining each of the blocks specified in the write log entry to determine if any partially written sectors exist by scanning the blocks sector by sector from the beginning and validating a checksum of each sector;

in response to detecting a free sector, examining whether any bits are set, wherein a bit being set indicates a partially written sector; and

skipping a remainder of the sectors in an examined block, upon validating the detected free sector.

15. The method of claim 1, wherein the checkpoint is performed in response to one of:

existence of sufficient free space to perform a checkpoint and existence of extra transaction log blocks to be reclaimed in order to prevent the free space from falling below an amount required to perform checkpoint;

the transaction log reaching a predefined size in order to free available space optimal performance of flash data write operations; and

a system processor entering an idle state in a periodical manner such that one of the transaction log size and the free space are prevented from reaching a predefined threshold.

16. A computing device capable of flash memory recovery employing a transaction log, comprising:

a flash memory; and

a processor coupled to the flash memory arranged to execute;

a flash driver configured to interact with flash memory hardware, implement programming and erasing algorithms, and implement error correction algorithms;

a flash abstraction layer configured to process input/output requests from a file system, implement wear-leveling operations, maintain data integrity, and manage recovery following an unexpected shutdown by recovering flash memory state employing the transaction log recorded during regular flash memory operations and a checkpoint reflecting an entire state of the flash memory at a time point prior to the unexpected shutdown; and

the file system.

17. The computing device of claim 16, wherein the flash abstraction layer includes:

a main flash abstraction layer object for handling read/write operations in a predefined flash region and for building logical to physical mapping during initialization;

a sector manager for managing a list of free and dirty sectors in the flash hardware;

a mapping table for maintaining the logical to physical sector mapping by translating logical sector addresses from the file system into corresponding physical sector addresses on the flash hardware.

18. The computing device of claim 17, wherein the flash abstraction layer further includes:

a compactor for recycling dirty sectors into free sectors by analyzing each flash block to determine which sectors are dirty and are to be recycled, such that any sectors in the flash block that are not dirty are re-mapped to another portion of the flash hardware.

19. A computer-readable storage medium with instructions stored thereon for flash memory recovery employing a transaction log, the instructions comprising:

during flash memory operations, generating the transaction log comprising a chained sequence of blocks specifying performed flash memory operations;

performing a checkpoint by writing an entire flash memory state into a specified location in the flash memory;

upon completing the checkpoint, deleting all transaction log entries, wherein a final checkpoint is performed prior to a flash driver unload during a safe shutdown;

if the flash memory is initialized following the safe shutdown, loading the entire flash state based on the final checkpoint; and

if the flash memory is initialized following an unexpected shutdown without performing a complete checkpoint prior to the flash driver unload, recovering the flash memory state by;

scanning each block from a beginning of the flash memory until a block with a special log bit is found in order to locate the transaction log, wherein each log block is identified by the special log bit in a spare area of the flash memory within each corresponding sector;

upon locating the block with the special log bit, locating a remainder of the transaction log by following forward and backward pointers in each block of the transaction log; and

locating a last checkpoint by starting at an end of the transaction log and examining each log entry backwards until the last checkpoint is found.

20. The computer-readable storage medium of claim 19, wherein instructions further comprise:

when a new checkpoint is to be performed while another exists, de-allocating the transaction log before a checkpoint log entry from the beginning such that a linked list structure of the transaction log is preserved.