Direct file data programming and deletion in flash memories

• US 8,214,583 B2
• Filed: 05/07/2010
• Issued: 07/03/2012
• Est. Priority Date: 02/16/2005
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sinclair, Alan W., Smith, Peter J.
• Primary Examiner(s): Dudek, Jr., Edward
• Assistant Examiner(s): Chrzanowski, Matthew
• Application Number:
  US12/775,639
• Publication Number:
  US 20100223423A1
• Time in Patent Office: 788 Days
• Field of Search: 711/103
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/16 for erasing blocks, e.g. arrays, words, groups

Abstract

Host system data files are written directly to a large erase block flash memory system with a unique identification of each file and offsets of data within the file but without the use of any intermediate logical addresses or a virtual address space for the memory. Directory information of where the files are stored in the memory is maintained within the memory system by its controller, rather than by the host. The file based interface between the host and memory systems allows the memory system controller to utilize the data storage blocks within the memory with increased efficiency.

Claims

1. A method of operating a re-programmable non-volatile memory system with a host system that generates a plurality of data files having unique individual file identifiers and offsets, the memory system having blocks of memory cells that are erased prior to new data being written therein, comprising:

maintaining a pool of erased blocks available for storage of data of the files, the blocks in the pool having been erased prior to being needed for the storage of data of the files,

receiving from the host data of the files and their unique individual file identifiers and offsets,

storing the received data files individually in one or more of the erase pool blocks of the memory system,

recording in a directory the identity of the blocks and locations therein in which data of the uniquely identified files are stored by their offset addresses without the use of any intermediate logical address conversion,

thereafter receiving from the host a command to delete from the memory system one of the stored data files by its unique file identifier,

thereafter identifying each of one or more blocks of memory cells containing data of the file being deleted,

thereafter rendering obsolete all the data of the file being deleted that are stored in the identified one or more blocks, wherein thereafter no valid data remain in the memory system for the unique identifier of the file being deleted, and

thereafter reclaiming space occupied by the obsolete data of the file being deleted in a manner that increases a number of erased blocks in the pool,

wherein executing the received command to delete said one of the stored data files causes the number of erased blocks in the pool to be increased and no data to remain in the memory system for the unique identifier of the deleted file.

2. The method of claim 1, wherein at least one block of memory cells identified to contain data of the file being deleted is full of obsolete data of the file being deleted.

3. The method of claim 1, wherein at least one block of memory cells identified to contain data of the file being deleted also contains valid data from at least one other file.

4. The method of claim 3, wherein reclaiming space occupied by the obsolete data of the file being deleted additionally comprises copying into another block in the pool of erased blocks the data from the at least one block of memory cells identified to also contain valid data from at least one other file and thereafter erasing data from the at least one block of memory cells identified to also contain valid data from at least one other file.

5. The method of claim 1, wherein receiving from the host data of the files and their unique file identifiers includes receiving data of the files and their unique file identifiers generated by application programs being run on the host and addressed with offsets of data within the individual identified files.

6. A memory system capable of storing data of multiple files that are received by the memory system with unique file identifiers and offsets of data within individual files, comprising:

an array of non-volatile charge storing semiconductor memory cells organized into a plurality of individual blocks of memory cells that are simultaneously erased prior to new data being written therein,

a directory including records that identify one or more of the blocks of memory cells in which data of individual ones of the received files are stored, and

a controller connected with the memory cell array that operates to (a) maintain a pool of erased blocks available for storage of data of the files, (b) cause data received by the memory system of the uniquely identified files to be individually stored in an identified one or more of the erase pool blocks of memory cells, (c) record in the directory the identity of the blocks of memory cells and locations therein in which data of the uniquely identified files are stored by their offset addresses without the use of any intermediate logical address conversion, (d) in response to receiving a command to delete a specific file, identify from the directory one or more blocks of memory cells in which data of the specific file are stored, (e) cause all the data of the specific file stored in the identified one or more blocks of memory cells to be marked as obsolete, and (f) thereafter cause the obsolete data of the selected file to be erased in a manner that adds at least one erased block to the erase pool blocks, and (g) remove the directory record for the selected file, wherein all data and the directory record of the selected file are deleted from the memory system.

7. The memory system of claim 6, wherein the controller further operates (d) in response to identifying at least one of the one or more blocks to contain received data of only the specific file, to then (f) subsequently cause the at least one block to be erased.

8. The memory system of claim 7, wherein the controller further operates (d) in response to identifying at least one of the one or more blocks to also contain valid data of another file, then (f) subsequently causing the valid data of the at least one block to be consolidated with other valid data in another block, and thereafter causing the at least one block to be erased.

9. The memory system of claim 6, wherein the controller further operates to cause data of the specific file stored in the selected one or more blocks to be deleted by first listing the selected one or more blocks in a queue that also lists other blocks as a result of operations not involving receipt of a command to delete a file, and then later deleting the data of the selected one or more blocks and other blocks in order of their position within the queue.

10. The memory system of claim 6, additionally comprising:

a first queue that lists a plurality of said blocks of memory cells which contain only data identified in the directory records to be obsolete, and

a second queue that lists a plurality of said blocks of memory cells which are storing obsolete data of one of the multiple files and valid data of at least one other of the multiple files, and

wherein the controller further operates to (d) list in the first queue any of the one or more blocks of memory cells identified to store data of the specific file whose data are all marked in the directory records to be obsolete, and list in the second queue any of the one or more blocks of memory cells identified to store data of the specific file that also stores valid data of some other file, and (f) thereafter erase the data stored in the blocks listed in the first queue and garbage collect the data stored in the blocks of memory cells listed in the second queue.

11. A memory system capable of storing data of multiple files that are received by the memory system with unique file identifiers and offsets of data within individual files, comprising:

an array of non-volatile charge storing semiconductor memory cells organized into a plurality of individual blocks of memory cells that are simultaneously erased prior to new data being written therein, the individual blocks of memory cells being further divided into a plurality of pages of memory cells that are individually programmable with data of the multiple files,

a directory including records that identify one or more of the blocks and pages of memory cells within the identified blocks in which data of individual ones of the received files are stored,

at least one queue in which a plurality of blocks of memory cells containing obsolete data are listed, and

a controller connected with the memory cell array that is configured to (a) cause data of the uniquely identified files received by the memory system to be stored in pages of one or more of the blocks of memory cells, (b) record in the directory the identity of the blocks of memory cells and locations therein in which data of the uniquely identified files are stored by their offset addresses, the controller directly translating the file identifiers and offsets received from a host into physical addresses of blocks and pages of memory cells in which data of the individual files are written without the use of any intermediate logical address conversion, (c) read data of the stored individual files by first accessing the directory records of the individual files to ascertain the blocks and pages of memory cells in which data of the individual files are stored, (d) in response to receiving a command to delete a specific file, identify from the directory one or more blocks of memory cells and pages therein in which data of the specific file are stored, (e) cause the identified one or more blocks of memory cells and pages therein to be listed in the at least one queue, (f) thereafter cause the data stored in the blocks of memory cells and pages therein that are listed in the at least one queue to be erased and the records of the specific file in the directory to be removed.

12. The memory system of claim 11, wherein the at least one queue comprises at least first and second queues that individually list a plurality of blocks, and wherein the controller is further configured to (e) cause (i) those of the identified one or more blocks of memory cells that contain only data of the specific file to be listed in the first queue, and (ii) those of the identified one or more blocks of memory cells that contain data of the specific file as well as valid data of another file to be listed in the second queue.

13. The memory system of claim 12, wherein the controller is further configured to (f) cause the valid data of the other file stored in one of the blocks of memory cells listed in the second queue to first be copied into another block not listed in the second queue and thereafter cause the data of the specific file and the other file in the one block of memory cells listed in the second queue to be erased.

14. A memory system capable of storing data of multiple files that are received by the memory system with unique file identifiers and offsets of data within individual files, comprising:

an array of non-volatile charge storing semiconductor memory cells organized into a plurality of blocks of memory cells, wherein the memory cells of individual blocks are simultaneously erased prior to new data being written therein,

a directory including a plurality of records that individually identify locations within at least one of the blocks of memory cells in which data of one the received files are stored, and

a controller connected with the memory cell array that operates in a manner comprising;

(a) causing data received by the memory system of the uniquely identified files to be individually stored in an identified at least one of the blocks of memory cells,

(b) recording in the directory the identity of the at least one of the blocks of memory cells and locations therein in which data of the uniquely identified files are stored by their offset addresses, without the use of any intermediate logical address conversion,

(c) in response to receiving a command to replace at least a portion of the data of a first one of the received files with update data,

(i) causing update data received by the memory system along with the command to update data of the first one of the received files to be written into one or more blocks of memory cells,

(ii) causing one of the records in the directory for the first one of the received files to be updated to identify the one or more blocks of memory cells in which update data are stored,

(iii) marking as obsolete the at least a portion of the data stored for the first one of the received files that was replaced by the update data, and

(iv) thereafter causing the obsolete data of the first one of the received files to be erased,

(d) in response to receiving a command to delete a second one of the received files,

(i) identifying from the directory one or more blocks of memory cells in which data of the second one of the received files are stored,

(ii) causing all the data of the second one of the received files stored in the identified one or more blocks of memory cells to be marked as obsolete, and

(iii) thereafter causing the obsolete data of the second one of the received files to be erased and the directory record for the second one of the received files to be removed from the directory, whereby the second one of the received files has been removed from the memory system.

15. The memory system of claim 14, wherein the controller operations of causing the obsolete data of the first or second one of the received files to be erased comprises:

recognizing when one or more blocks of memory cells contain only data marked obsolete, and

thereafter causing all the data of the one or more recognized blocks of memory cells to be erased.

16. The memory system of claim 14, wherein the controller operations of causing the obsolete data of the first or second one of the received files to be erased comprises:

recognizing when one or more blocks of memory cells contain both data marked obsolete and valid data,

thereafter causing the valid data of the recognized one or more blocks of memory cells to be consolidated with other valid data that are together stored in another block of memory cells, and

thereafter causing the recognized one or more blocks to be erased.

17. The memory system of claim 14, wherein the controller additionally maintains a first queue of a plurality of blocks of memory cells that contain only data marked obsolete and a second queue of a plurality of blocks of memory cells that contain both data marked obsolete and valid data, wherein the controller operations of causing the obsolete data of the first or second of the received files to be erased comprises:

recognizing when one or more blocks of memory cells contain only data marked obsolete, and add the one or more blocks of obsolete data to the first queue,

thereafter causing all the data of the one or more blocks of memory cells listed in the first queue to be erased in an order specified by their position in the first queue,

recognizing when one or more blocks of memory cells contain both data marked obsolete and valid data, and add the one or more blocks of obsolete and valid data to the second queue, and

thereafter causing the data within the one or more blocks of memory cells listed in the second queue to be garbage collected in an order specified by their position in the second queue.

18. In a re-programmable non-volatile memory system with memory cells organized into blocks of memory cells that are erased together prior to new data being written into the blocks of memory cells, a method of operating the memory system when connected with a host, comprising:

receiving data of files from the host, along with unique identifiers of the individual data files received,

writing the individual received data files into one or more erased blocks of the memory system in which data of the identified files are written without the use of any intermediate logical address conversion,

maintaining a directory of records for the data files written in the memory system, the records individually listing, for one of the unique file identifiers, the one or more blocks in which data of the identified file have been written,

reading data of individual files stored in the memory system by first identifying the directory records for the files by their unique file identifiers, and thereafter reading data from the one or more blocks listed in the directory records for the individual files,

receiving from the host a command to delete from the memory system one of the data files identified by its unique file identifier,

identifying one or more blocks of memory cells containing data of the file to be deleted by reference to the directory record for the unique file identifier received from the host for the file to be deleted,

marking as obsolete all the data of the file being deleted that are written in the identified one or more blocks,

reclaiming data storage space occupied by the data of the file marked as obsolete in a manner to provide at least one erased block for the storage of additional data of files from the host, and

deleting from the directory the record for the unique file identifier of the file being deleted,

wherein execution of the command to delete from the memory system said one of the data files increases a number of erased blocks available for storing data files by at least one and neither data nor the directory record remain in the memory system for the unique file identifier of the deleted file.

19. The method of claim 18, wherein the blocks of memory cells of the memory system are individually divided into a plurality of pages of memory cells, and wherein the records of the directory also specify one or more pages of the blocks in which data of the files have been written.

20. The method of claim 18, wherein reclaiming data storage space occupied by the data of the file marked as obsolete additionally comprises:

scheduling for erase any of the blocks containing only data of the file to be deleted that have been marked as obsolete, and

scheduling for garbage collection any of the blocks containing valid data of another file in addition to data of the file to be deleted that have been marked as obsolete.

21. The method of claim 18, wherein receiving data of files and unique identifiers of the individual data files includes receiving data of files and unique identifiers for the individual data files that are generated by application programs being run on the host and includes receiving offset addresses of data within the received individual files.

22. The method of claim 21, wherein writing the individual received data files into one or more blocks of the memory system comprises writing the data as a plurality of separately identified groups of data contained within individual memory cell blocks and which individually contain data of the received files with continuous offset addresses.

23. The method of claim 22, further wherein the individual directory records additionally list the groups of data making up the data file represented by the record, the individual groups of data being designated by at least a physical memory cell block address and a corresponding offset address of data within the group.

24. The method of claim 23, further wherein marking as obsolete the data of the file to be deleted comprises marking one of the data groups of the record at a time as obsolete until all the data groups of the file to be deleted have been marked as obsolete.

25. The method of claim 24, further wherein (1) the marking as obsolete of a data group within one of the blocks into which data of only single file are written are placed in a queue for subsequent erasure, and (2) the marking as obsolete of a data group within one of the blocks into which data of another file exists is placed in a queue for subsequent garbage collection.

26. The method of claim 18, wherein reclaiming data storage space occupied by the data of the file marked as obsolete additionally comprises causing valid data of another file to be moved from at least one of the identified one or more blocks to another one or more blocks, and then the identified one or more blocks to be erased.

27. The method of claim 18, wherein receiving data of files from the host includes receiving data of files containing different amounts of data.

28. A method of operating a re-programmable non-volatile memory system with a host system whose application programs generate a plurality of data files assigned unique individual file identifiers with offsets of data within the individual files, the memory system having blocks of memory cells that are erased together prior to new data being written therein, comprising:

maintaining a pool of erased blocks available for storage of data of the files, the blocks in the pool having been erased prior to being needed for the storage of data of the files,

receiving from the host data of the files and their unique individual file identifiers,

storing the received data files individually in one or more of the erase pool blocks of the memory system,

directly translating file identifiers and offsets received from a host into physical addresses of blocks and pages of memory cells in which data of the individual files are written without the use of any intermediate logical address conversion,

in response to receiving from the host a command to update one of the stored data files identified by its unique file identifier and an offset address that designates a portion of the data within the file that are to be replaced,

writing into at least one block of the memory system updated data received from the host for the identified file, and

marking obsolete original data of the identified file that have been updated,

in response to receiving from the host a command to delete from the memory system one of the stored data files identified by its unique file identifier,

identifying each of one or more blocks of memory cells containing data of the file being deleted,

thereafter rendering obsolete all the data of the file being deleted that are stored in the identified one or more blocks, wherein thereafter no valid data remain in the memory system for the unique identifier of the file being deleted, and

thereafter reclaiming space occupied by the obsolete data of the file being deleted in a manner that increases a number of erased blocks in the pool,

wherein executing the received command to delete said one of the stored data files causes the number of erased blocks in the pool to be increased and no data to remain in the memory system for the unique identifier of the deleted file.