Method and apparatus for maintaining data on non-volatile memory systems

• US 7,395,384 B2
• Filed: 07/21/2004
• Issued: 07/01/2008
• Est. Priority Date: 07/21/2004
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Sinclair, Alan Welsh, Smith, Peter John
• Primary Examiner(s): Thai; Tuan V.
• Assistant Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US10/897,049
• Publication Number:
  US 20060020744A1
• Time in Patent Office: 1,441 Days
• Field of Search: 711/156
• US Class Current: 711/156
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

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 filing 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 filing system to ensure that one or more clusters (or one or more sectors within a cluster) are not copied from one location to another location in the memory during a garbage collection cycle. As a result, some unnecessary operations (e.g., copying data) which are conventionally performed can be avoided and system performance can be enhanced.

Claims

1. A method of performing garbage collection of data stored on a non-volatile memory storage device, said method comprising:

providing a Data Allocation Table (DAT) which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories, to determine whether one or more sectors of one or more of said clusters have been deallocated;

updating said Data Allocation Table (DAT) based on said monitoring;

reading a deallocation status in said Data Allocation Table (DAT), wherein said deallocation status is associated with a first cluster that is stored as a first portion of a first block of non-volatile memory; and

copying one or more sectors of said first portion of said first block to a second block only when said deallocation status is set to allocated to indicate allocation of data to a file.

2. A method as recited in claim 1, wherein said monitoring, updating, reading, and copying are performed by a non-volatile memory controller.

3. A method as recited in claim 1,

wherein said data deallocation table is provided in non-volatile memory;

and

wherein said data deallocation table includes an indexing mechanism provided to update said data deallocation table in non-volatile memory.

11. A method as recited in claim 1;

wherein each clusters is represented by four (4) bits in said Data Allocation Table (DAT), and

wherein one (1) bit of said four bits represents an deallocation status that indicates whether the cluster if fully deallocated, and three (3) other bits of said four bits indicate what portion of the cluster has been deallocated.

4. A memory device that provides non-volatile memory, wherein said memory device is capable of:

providing a data deallocation table which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories to determine whether one or more of said clusters have been deallocated; and

updating said deallocation table based on said monitoring.

5. A memory device as recited in claim 4, wherein said memory device is further capable of:

reading a deallocation status associated with a first cluster that is stored as a first portion of a first block of non-volatile memory; and

copying said first portion of said first block to a second block only when said deallocation status is set to allocated.

6. A method for managing data stored in non-volatile memory, wherein said method comprises:

receiving data from a host, wherein said data is to be stored in non-volatile memory;

monitoring a File Allocation Table (FAT) used by said host to logically organize data stored in said non-volatile memory;

determining based on said monitoring whether one or more clusters which have been previously allocated to one or more files have been deallocated by said host; and

not copying data associated with said one or more clusters from one portion to another portion of said non-volatile memory when said determining determines that said one or more clusters have been deallocated by the host.

7. A method as recited in claim 6, wherein said method further comprises:

monitoring a root directory, one or more subdirectories, and a File Allocation Table (FAT).

8. A method as recited in claim 7, wherein said method further comprises:

generating an Attribute Store (AS) that includes at least one deallocation status about a plurality of data portions of data stored on said non-volatile memory; and

updating said Attribute Store (AS) based on said monitoring of said root directory, one or more subdirectories, and File Allocation Table (FAT).

9. A method as recited in claim 8,

wherein said Attribute Store (AS) further includes at least one deallocation status of one or more sectors of one or more clusters;

wherein said not coping of said one or more clusters comprises;

not copying one or more sectors of said one or more clusters.

10. A method as recited in claim 9, wherein said Attribute Store (AS) is implemented as a Data Allocation Table (DAT).

12. A memory device that provides non-volatile memory, wherein said memory device is capable of:

providing a Data Allocation Table (DAT) which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories, to determine whether one or more sectors of one or more of said clusters have been deallocated;

updating said Data Allocation Table (DAT) based on said monitoring,

reading a deallocation status in said Data Allocation Table (DAT) after said updating, wherein said deallocation status is associated with a first cluster that is stored as a first portion of a first block of non-volatile memory; and

copying one or more sectors of said first portion of said first block to a second block only when said deallocation status is set to allocated to indicate allocation of data to a file.

13. A computer readable medium storing computer program code for performing garbage collection of data stored on a non-volatile memory storage device, wherein said computer readable medium includes:

computer program code for providing a Data Allocation Table (DAT) which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

computer program code for monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories, to determine whether one or more sectors of one or more of said clusters have been deallocated;

computer program code for updating said Data Allocation Table (DAT) based on said monitoring;

computer program code for reading a deallocation status in said Data Allocation Table (DAT), wherein said deallocation status is associated with a first cluster that is stored as a first portion of a first block of non-volatile memory; and

computer program code for copying one or more sectors of said first portion of said first block to a second block only when said deallocation status is set to allocated to indicate allocation of data to a file.

14. A computer-implemented method for managing data stored in a non-volatile memory device, said method comprising:

providing a data deallocation table which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories to determine whether one or more of said clusters have been deallocated; and

updating said deallocation table based on said monitoring.

15. A computer readable medium storing computer program code for managing data stored in a non-volatile memory device, wherein said computer readable medium includes:

computer program code for providing a data deallocation table which includes a deallocation status for each one of a plurality of clusters used by a host to logically organize data;

computer program code for monitoring a root directory, a File Allocation Table (FAT), and one or more subdirectories to determine whether one or more of said clusters have been deallocated; and

computer program code for updating said deallocation table based on said monitoring.

16. A non-volatile memory device for storing and managing data stored therein, wherein said memory device is capable of:

receiving data from a host, wherein said data is to be stored in non-volatile memory of said non-volatile memory;

monitoring a File Allocation Table (FAT) stored on said non-volatile memory and used by said host to logically organize data on said non-volatile memory device;

determining based on said monitoring whether one or more clusters which have been previously allocated to one or more files have been deallocated by said host; and

not copying data associated with said one or more clusters from one portion to another portion of said non-volatile memory when said determining determines that said one or more clusters have been deallocated.

17. A computer readable medium storing computer program code for storing and managing data stored in a non-volatile memory device, wherein said computer readable medium includes:

computer program code for receiving data from a host, wherein said data is to be stored in non-volatile memory of said non-volatile memory;

computer program code for monitoring a File Allocation Table (FAT) stored on said non-volatile memory and used by said host to logically organize data on said non-volatile memory device;

computer program code for determining based on said monitoring whether one or more clusters which have been previously allocated to one or more files have been deallocated by said host; and

computer program code for not copying data associated with said one or more clusters from one portion to another portion of said non-volatile memory when said determining determines that said one or more clusters have been deallocated.