Transactional file system for flash memory

• US 7,076,599 B2
• Filed: 05/25/2005
• Issued: 07/11/2006
• Est. Priority Date: 02/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aasheim, Jered, Kalkman, John, Yang, Yongqi
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): PATEL, HETUL B
• Application Number:
  US11/137,033
• Publication Number:
  US 20050216653A1
• Time in Patent Office: 412 Days
• Field of Search: 711/103, 714/14, 714/24, 714/36
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• 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 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A transactional file system developed to function with flash memory is described. The file system provides for efficient storage of file system meta-information, performs robust transaction logging, and performs other related features. In one described implementation, metadata is stored in-line with data. In another embodiment, a transaction log is maintained by storing transaction information associated with requests to perform file transactions. The transaction information is stored at arbitrary physical sector addresses on the flash medium. In still another embodiment, a transaction log is stored in a physical sector of a flash medium. The transaction log contains transaction information associated with performing a file request. Metadata is written into a spare area of the physical sector indicating that the physical sector contains transaction information.

Claims

1. A computer for storing data on a flash medium, comprising:

one or more processors; and

a file system, the file system configured to store data on the flash medium as a series of linked lists by storing pointers in each physical sector of the flash medium in which valid data is also stored, wherein each pointer indicates a next physical sector in the flash medium in which valid data is located, the file system further comprising;

a sector manager comprising a write pointer that indicates a physical sector that is free to receive new data, the write pointer configured to advance through the physical sectors on the flash medium as data is written on the flash memory medium; and

a power failure manager configured to store a data valid bit in each physical sector indicated by the write pointer at completion of writing data to the physical sector indicated by the write pointer, wherein the power failure manager is further configured to (i) search the physical sector indicated by the write pointer when the file system is initialized to ascertain whether the data valid bit exists in the physical sector;

(ii) conclude that a power-failure event occurred, if the data valid bit is not found in the physical sector; and

(iii) mark the physical sector dirty if the power-failure event occurred.

2. The computer as recited in claim 1, wherein the file system is further configured to store data in a first region of the physical sectors.

3. The computer as recited in claim 1, wherein the file system is further configured to store the pointer in a second region of the physical sectors.

4. The computer as recited in claim 1, wherein each pointer is metadata.

5. The computer as recited in claim 1, wherein the data comprises file system information including at least one of file data, directories, and file attributes.

6. A method for storing data on a flash medium, comprising:

storing valid data in a first region of a first physical sector of the flash medium;

storing a pointer in a second region of the first physical sector inline with the data in each physical sector in which valid data is stored, the pointer indicating a next physical sector in which valid data is located on the flash medium;

maintaining a write pointer to advance through a circular sequence of physical sectors in the flash medium indicating a physical sector that is available to receive data as the write pointer advances;

writing data into the physical sector indicated by the write pointer;

writing metadata into the physical sector indicated by the write pointer if the writing of data into the physical sector is completed;

searching the physical sector indicated by the write pointer to determine whether the metadata exists in the physical sector upon initializing the computer; and

marking the physical sector indicated by the write pointer dirty, if the metadata is does not exist in the memory location.

7. The method as recited in claim 6, wherein the pointer is metadata used to link locations of the first physical sector to the next physical sector in which valid data is stored on the flash medium.

8. The method as recited in claim 6, wherein the data comprises file system information including at least one of file data, directories, and file attributes.

9. The method as recited in claim 6, wherein the first region is larger than the second region.

10. The method as recited in claim 6, wherein the second region of the first physical sector is a spare area.

11. One or more computer-readable media comprising computer executable instructions that, when executed, direct a computer to:

store data in a first region of a physical sector of the flash medium; and

store a pointer in a second region of each physical sector in which data is stored, the pointer indicating a next physical sector in which valid data is located on the flash medium;

organize the flash memory medium as if the physical sectors of the flash memory form a continuous circle, wherein the lowest and highest physical sector are contiguous;

maintain a write pointer to indicate a physical sector that is free to receive new data, the write pointer configured to advance through the continuous circle of physical sectors as data is written to the flash memory medium;

store meta-information in each physical sector indicate by the write pointer at completion of a write operation to the physical sector indicated by the write pointer;

search the physical sector indicated by the write pointer when the file system is initialized to ascertain whether the meta-information exists in the physical sector;

conclude that a power-failure event occurred, if the meta-information is not found in the physical sector; and

mark the physical sector indicated by the write pointer dirty if a power-failure event is concluded.

12. One or more computer-readable media as recited in claim 11, wherein the pointer is metadata used to link locations of the first physical sector to the next physical sector in which valid data is stored on the flash medium.

13. One or more computer-readable media as recited in claim 11, wherein the data comprises file system information including at least one of file data, directories, and file attributes.

14. One or more computer-readable media as recited in claim 11, wherein the first region is larger than the second region.

15. One or more computer-readable media as recited in claim 11, wherein the second region is a metadata region within a data region of a physical sector.