System and method for tracking data stored in a flash memory device

• US 6,901,499 B2
• Filed: 02/27/2002
• Issued: 05/31/2005
• Est. Priority Date: 02/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aasheim, Jered Donald, Yang, Yongqi
• Primary Examiner(s): Peikari, B. James
• Application Number:
  US10/087,590
• Publication Number:
  US 20030163631A1
• Time in Patent Office: 1,189 Days
• Field of Search: 365/185.29, 365/185.33, 365/230.01, 707/200, 707/205, 711/103, 711/202, 711/205, 711/207, 711/209, 711/221, 711/115
• US Class Current: 711/205
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A flash driver tracks data stored in a flash memory device through the use of logical-to-physical sector mapping. The mapping is stored in a data structure and allows data to be written into the next free physical sector in the flash memory medium. Write operations complete quickly, because there is no need to perform an erase operation in order to write new data on to the flash memory medium. Data loss due to power interruption during a write operation is also minimized by the described implementations. The logical-to-physical sector mapping stored in data structure is backed-up on the flash memory medium. In the event there is a catastrophic power interruption, logical-to-physical sector mapping can easily be reestablished by scanning the backed-up mapping in the flash memory medium. The backed-up information can be stored in a spare portion of a NAND or NOR flash memory medium.

Claims

1. A method comprising:

receiving a request to write data to a logical sector address of a flash memory medium;

selecting a physical sector address from a list of free physical sector addresses;

assigning the selected free physical sector address to the logical sector address forming a corresponding relationship between the addresses;

storing the corresponding relationship between the addresses in a data structure; and

writing the data into a physical sector of the flash memory medium at a location indicated by the selected free physical sector address.

2. The method as recited in claim 1, wherein the data structure is stored on the flash memory medium.

3. The method as recited in claim 1, wherein the data structure is contained in a random access memory device.

4. The method as recited in claim 1, wherein the request is received from a file system.

5. The method as recited in claim 1, further comprising storing the logical sector address in the physical sector of the flash memory medium along with the data.

6. The method as recited in claim 1, further comprising

storing the logical sector address in the physical sector of the flash memory medium along with the data;

if the data structure is erased, then scanning the flash memory medium to locate the logical sector address stored with the data;

assigning the physical sector address containing the data to the logical sector address forming a reestablished corresponding relationship between the addresses; and

storing the reestablished corresponding relationship between the addresses in a new data structure.

7. A computer-readable medium having computer-executable instructions for performing stops comprising:

receiving a request to write data to a logical sector address of a flash memory medium;

selecting a physical sector of the flash memory medium to store the data based on the ability of the physical sector to store the data without first being erased;

assigning a physical sector address of the selected physical sector to the logical sector address forming a corresponding relationship between the addresses;

storing the corresponding relationship between the addresses in a data structure;

writing the data into the physical sector, and

writing the logical sector address in the physical sector of the flash memory medium along with the data.

8. The method as recited in claim 7, further comprising:

if the data structure is erased, then scanning the flash memory medium to locate the logical sector address stored with the data;

assigning the physical sector address containing the data to the logical sector address forming a reestablished corresponding relationship between the addresses; and

storing the reestablished corresponding relationship between the addresses in a new data structure.

9. The method as recited in claim 7, wherein writing the logical sector address in the physical sector of the flash memory medium includes writing the logical sector address into a spare portion of the physical sector.

10. The method as recited in claim 7, wherein the data structure is contained in at least one memory device other than the flash memory medium.

11. The method as recited in claim 7, wherein the data structure is contained in a random access memory device.

12. The method as recited in claim 7, wherein the request is received from a file system.

13. A method comprising:

(a) receiving a request to write data to a logical sector address of a flash memory medium;

(b) assigning a physical sector address to the logical sector address forming a corresponding relationship between the addresses;

(c) storing the corresponding relationship between the addresses in a data structure;

(d) writing the data into a physical sector of the flash memory medium at a location indicated by the physical sector address;

(e) receiving a request to rewrite updated data to the logical sector address;

(f) assigning a new physical sector address to the logical sector address forming a corresponding relationship between the new physical sector address and the logical sector address;

(g) storing the corresponding relationship between the addresses from the aforementioned paragraph (f) in the data structure;

(h) writing the updated data into a physical sector of the flash memory medium at a location indicated by the new physical sector address; and

(i) marking the physical sector address from the aforementioned paragraph (b) as dirty.

14. The method as recited in claim 13, wherein the data structure is contained in at least one memory device other than the flash memory medium.

15. The method as recited in claim 13, wherein the data structure is contained in a random access memory device.

16. The method as recited in claim 13, wherein the requests are received from a file system.

17. The method as recited in claim 13, wherein the data structure is maintained by a flash abstraction logic of a flash memory driver.

18. A system, comprising:

flash medium logic, configured to store data in a physical sector of a flash memory medium;

a table, configured to map logical sector addresses received from a file system to physical sector addresses on the flash memory medium; and

flash abstraction logic, configured to ascertain a next free physical sector on a flash memory medium and assign an address associated with the free physical sector to a logical sector address associated with a write request received from the file system.

19. The system as recited in claim 18, wherein the flash abstraction logic is further configured to update the map of the logical sector addresses to the physical sector addresses, after assigning the address associated with the free physical sector to the logical sector address associated with the write request.

20. The system as recited in claim 18, wherein the flash medium logic marks a physical sector address as dirty after contents associated with the physical sector address are rewritten to a new physical sector address.

21. The system as recited in claim 18, wherein the flash medium logic is further configured to store the logical sector address within a portion of the physical sector associated with the write request.

22. The system as recited in claim 18, wherein the flash medium logic is further configured to:

store the logical sector address within a portion of the physical sector associated with the write request; and

scan the flesh memory medium for the portion of the physical sector storing the logical sector address after initialization of the system.

23. The system as recited in claim 18, wherein the table is contained in a memory device other than the flash memory medium.

24. The system as recited in claim 18, wherein the table is contained in a random access memory device.

25. The system as recited in claim 18, wherein the system is a flash driver system.

26. A computer-readable medium for a flash driver, comprising computer-executable instructions that, when executed, direct the flash driver to:

receive a request to write data to a logical sector address of a flash memory medium;

selecting a physical sector address from a list of free physical sector addresses;

assign the selected physical sector address to the logical sector address forming a corresponding relationship between the addresses;

store the corresponding relationship between the addresses in a table; and

write the data into a physical sector of the flash memory medium at a location indicated by the physical sector address.

27. A computer-readable medium for a flash driver, comprising computer-executable instructions that, when executed, direct the flash driver to:

receive a request to write data to a logical sector address of a flash memory medium;

assign a physical sector address to the logical sector address forming a corresponding relationship between the addresses;

store the corresponding relationship between the addresses in a table;

write the data into a physical sector of the flash memory medium at a location indicated by the physical sector address;

write the logical sector address in the physical sector of the flash memory medium along with the data;

if the table is erased, then scan the flash memory medium to locate the logical sector address stored with the data;

assign the physical sector address containing the data to the logical sector address forming a reestablished corresponding relationship between the addresses; and

store the reestablished corresponding relationship between the addresses in a new table.

28. A system for tracking sectors in a flash memory medium, comprising:

means for receiving a request to retrieve data stored in the flash memory medium from a location indicated by a logical sector address;

means for locating a physical sector address corresponding to the specific logical sector address in a table; and

means for reading the data stored in the flash memory medium from the physical sector address located from the table.

29. The system as recited in claim 28, further comprising:

means for storing the logical sector address with the data in the flash memory medium at a location indicated by the physical sector address;

means for reestablishing a portion of the table in the event of a power interruption, by scanning the physical sector address for the associated logical sector address; and

means for storing the logical sector address in the table at a location corresponding to the physical sector address.

30. The system as recited in claim 28, wherein the request is received from a file system.

31. The system as recited in claim 28, wherein the table is maintained by a flash abstraction logic of a flash driver.

32. The system as recited in claim 28, wherein the means for reading of the data is performed by flash media logic of a flash driver.

33. The system as recited in claim 28, wherein the memory device is a type of random access memory.