Fat analysis for optimized sequential cluster management

• US 20060020745A1
• Filed: 12/23/2004
• Published: 01/26/2006
• Est. Priority Date: 07/21/2004
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sinclair, Alan Welsh, Conley, Kevin M., Smith, Peter John
• Granted Patent: US 8,607,016 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• 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]

Abstract

Techniques for managing data in a non-volatile memory system (e.g., Flash Memory) are disclosed. A controller can use information relating to a host'"'"'s file system, which is stored by the host on non-volatile memory, to determine if one or more clusters (or sectors with clusters) are currently allocated. The controller can use the information relating to the host'"'"'s file system to identify when the host is sending data to the next free cluster and to store such data in a sequential format by copying data from other locations in the non-volatile memory.

Claims

1. A method of storing portions of data, in an adaptive manner, in a memory system that includes a controller and a non-volatile memory array, comprising:

the controller obtaining an attribute of a logical address range from information stored by a host in a File Allocation Table or directory in the non-volatile memory array;

the controller selecting a storage scheme from a plurality of storage schemes for a portion of data having a logical address within the logical address range according to the attribute of the logical address range; and

the controller storing the portion of data according to the selected storage scheme.

2. The method of claim 1 wherein the attribute of the logical address range is that the logical address range is the next free logical address range for storage of host data.

3. The method of claim 2 wherein the storage scheme selected includes storage of the portion of data in a sequential update block.

4. The method of claim 1 wherein the attribute of the logical address range is that the logical address range is not the next free logical address range for storage of host data.

5. The method of claim 4 wherein the storage scheme selected includes storage of the portion of data in a chaotic update block.

6. The method of claim 1 wherein the portion of data is previously stored at a first location in the non-volatile memory array, the attribute of the logical address range is that the logical address range is allocated by the host and the storage scheme selected includes copying the portion of data from the first location to a second location in the non-volatile memory array.

7. The method of claim 6 wherein the portion of data is previously stored at a first location in the non-volatile memory array, the attribute of the logical address range is that the logical address range is deallocated by the host and the storage scheme selected maintains the portion of data at the first location without copying the portion of data from the first location to a second location

8. The method of claim 1 wherein the attribute that is obtained from a Data Attribute Store that is derived from the File Allocation Table or directory.

9. A method of storing data received from a host in a non-volatile memory array, comprising:

receiving one or more addressable units of data from the host;

analyzing information stored by the host in the non-volatile memory array to identify a plurality of logical address ranges available to the host for storage of data;

comparing the plurality of logical address ranges available to the host with logical addresses of the one or more addressable units of data to determine if the one or more addressable units of data are allocated to the next range of logical addresses available to the host; and

storing the one or more addressable units of data in a manner that is dependent on the determination.

10. The method of claim 9 wherein the manner of storing the one or more addressable units is a sequential manner if the one or more addressable units are assigned to the next sequential locations available, and the manner of storing is a non-sequential manner if the one or more addressable units are not assigned to the next sequential locations available.

11. The method of claim 9 wherein storing the one or more addressable units of data is in a manner that is dependent on additional factors including whether a logical address gap between the logical addresses of the one or more addressable units of data and the logical address of the last written addressable unit of data exceeds a predetermined amount.

12. The method of claim 11 wherein an additional factor is whether an update block for storing the one or more addressable units of data contains more than a predetermined amount of data in a sequential form.

13. A memory device for storing data in non-volatile memory, the data being received from a host in addressable units of data, comprising:

a non-volatile memory array that contains a copy of a host File Allocation Table; and

a memory controller in communication with the non-volatile memory array, the memory controller monitoring the contents of the copy of the host File Allocation Table, the memory controller determining an allocation state of a portion of logical address space from the copy of the host File Allocation Table and, the memory controller selecting a data management scheme for an addressable unit of data having a logical address within the portion of logical address space in response to the allocation state.

14. The memory device of claim 13 wherein the memory device forms part of a removable memory card that is removably connected to a controller.

15. The memory device of claim 13 wherein the memory controller records the allocation state of the portion of logical address space in a Data Attribute Store.

16. The memory device of claim 13 wherein the addressable unit of data is received from a host for storing in the non-volatile memory array, the data management scheme comprises storage in a sequential block if the portion of logical address space is the next free portion and the data management scheme comprises storage in a chaotic block if the portion of logical address space is not the next free portion.

17. The memory device of claim 13 wherein the addressable unit of data is stored in a first location in the non-volatile memory array when the memory device carries out a garbage collection operation, the data management scheme is copying the addressable unit of data to a second location in the non-volatile memory array if the portion of logical address space is allocated and the data management scheme is maintaining the addressable unit of data in the first location without copying if the portion of logical address space is not allocated.

18. A computer readable medium including program code for selecting between alternative storage schemes available to a memory controller for storage of host data in a non-volatile memory, comprising:

computer program code that identifies an allocation status of a plurality of portions of logical address space from information stored by a host in the non-volatile memory and provides the allocation status to the memory controller; and

computer program code that selects a data management scheme for a portion of host data according to an allocation status of a portion of logical address space that includes the logical address of the portion of data.

19. The computer readable medium of claim 18 further comprising computer program code that operates on the portion of host data according to the selected management scheme to store the portion of data in a sequential block if the portion of logical address space is the next portion of logical address space that is not allocated and store the portion of data in a chaotic block otherwise.

20. The computer readable medium of claim 18 further comprising computer program code that operates on the portion of host data according to the selected management scheme to copy the portion of data from an old location to a new location if the portion of logical address space is allocated and to leave the portion of data in the old location without copying to a new location if the portion of logical address space is not allocated.

21. The computer readable medium of claim 18 further comprising computer program code that provides a Data Attribute Store containing the allocation status of the plurality of portions of logical address space.