Management of memory blocks that directly store data files

• US 8,055,832 B2
• Filed: 05/08/2006
• Issued: 11/08/2011
• Est. Priority Date: 08/03/2005
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sinclair, Alan W., Wright, Barry
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US11/382,224
• Publication Number:
  US 20070033328A1
• Time in Patent Office: 2,010 Days
• Field of Search: 711/103, 711/E12.008
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• 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/0483 comprising cells having several storage transistors connected in series
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators

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. A type of memory block is selected to receive additional data of a file that depends upon the types of blocks into which data of the file have already been written. Blocks containing data are selected for reclaiming any unused capacity therefrom by a process that selects blocks in order starting with those containing the least amount of valid data.

Claims

1. A method of storing data in blocks of re-programmable non-volatile memory as uniquely identified individual files, which comprises:

assigning a plurality of states to the individual files, wherein one of said plurality of states is assigned to a given one of the individual files having data stored in the blocks of the non-volatile memory, wherein the assigning of said one state to the given file is based upon a number of the blocks of the non-volatile memory that are partially filled with data of the given file and that also contain erased capacity in which data may be written,

maintaining records for the individual files of said plurality of file states that are based upon how data of the individual files are distributed among one or more of a plurality of types of blocks, and

writing additional data of the given file to a type of block that is selected based upon the state in the record of the given file.

2. The method of claim 1, wherein a record for an individual file includes an identification of any blocks of a type in which data of the individual file are stored along with data from another file.

3. The method of claim 1, wherein writing additional data additionally includes transitioning the state of the given file from a first state to second state, wherein the first and second file states are based upon storage of data of the given file in at least one different type of block.

4. The method of claim 1, wherein writing additional data additionally includes transitioning the state of the given file so that additional data of the given file are written to a type of block that limits the number of blocks in the memory that contain data of the file and also contain data of another file to be below a predetermined number.

5. The method of claim 1, wherein writing additional data includes writing data received from outside of the memory.

6. The method of claim 1, wherein writing additional data includes copying data from another location within the memory.

7. A method of operating a non-volatile memory system with storage cells grouped into blocks of memory cells that are erased prior to reprogramming with data of uniquely identified files, comprising:

designating a set of a plurality of data block types in terms of a structure of file data stored within individual blocks so designated,

designating a set of a plurality of permitted file states in terms of a combination of types of one or more blocks in which data of individual files so designated are stored,

maintaining a record of the file states of individual data files stored in the memory system, and

writing data for an individual file to a type of block selected according to the current state of the file in the record;

wherein the designated plurality of data block types includes a first plurality of types in which data of only one file are stored in a single block and a second plurality of types in which data of two or more files are stored in a single block, and wherein the permitted file states limit a maximum number of blocks of the second plurality of types to which data of a single one of the files may be written, and wherein the maximum number is two.

8. The method of claim 7, wherein the memory cells are flash erasable.

9. The method of claim 8, wherein the memory cells individually include electrical charge storage elements.

10. The method of claim 8, wherein the storage cells are individually operated to store multiple levels of charge in order to store more than one bit of data.

11. A method of operating a non-volatile memory system with memory storage cells grouped into blocks of memory cells that are simultaneously erased prior to reprogramming and which stores data as a plurality of distinctly identified data files, comprising:

identifying blocks storing data of individual files by one of a plurality of types of blocks including a first type of block containing valid data of two or more files and a second type of block containing data of only one file,

designating one of a plurality of permitted states for individual files stored in one or more blocks of the memory system in terms of an allowed one or more types of the blocks,

maintaining a set of a plurality of permitted transitions between file states that limit a number of blocks of the first type that can store data of a single file in favor of blocks of the second type,

in response to a need to write additional data to a given file stored in the memory system, identify one of the blocks to which data of the given file have most recently been written but if this identified block cannot accept additional data of the given file then transition the state of the given file to a next permitted state within the set of permitted file state transitions and identify an additional block having a type allowed by the next permitted state, and

thereafter writing the additional data to the type of block so identified;

wherein the set of plurality of permitted transitions between file states limit the number of blocks of the first type that can store data of a single file to two.

12. The method of claim 11, wherein writing additional data includes writing data received from a host system to which the memory system is connected.

13. The method of claim 11, wherein writing additional data includes copying data from another location within the memory system.

14. The method of claim 11, wherein the method is carried out in a portable memory card or drive.

15. A method for programming a plurality of files of data in a reprogrammable non-volatile memory system, comprising a plurality of blocks of non-volatile memory cells characterized by the memory cells of individual blocks being simultaneously erased prior to reprogramming data therein, comprising:

assigning and storing a state for each of the plurality of files of data programmed in the plurality of blocks of non-volatile memory cells, the assigned state of each of the plurality of files being based on at least;

a number of the blocks of non-volatile memory cells that are partially filled with data of the file, and

a number of the blocks of non-volatile memory cells that are partially filled with data of the file that also contain erased capacity in which additional data may be programmed, and

selecting one or more of the blocks of non-volatile memory cells in which data of a given one of the individual files of data are to be programmed based on the stored state of the given one of the individual files of data, and

programming the data of the given one of the individual files of data into the selected one or more blocks.

16. The method of claim 15, wherein the assigned state of each of the plurality of files is additionally based on a number of the blocks of non-volatile memory cells that are partially filled with data of the file that also contain data of one or more other of the plurality of files.

17. The method of claim 15, wherein the selecting selects one or more of the blocks of non-volatile memory cells in which data of the given one of the individual files are to be programmed based on the stored state of the given one of the individual files in order to maintain a number of the blocks of memory cells partially containing data of the given one of the files below a preset limit.

18. The method of claim 16, wherein the selecting is based on the stored state of the given one of the individual files in order to maintain a number of the blocks of memory cells partially containing data of the given one of the files below a preset limit.

19. A method for programming a plurality of files of data in a reprogrammable non-volatile memory system comprising a plurality of blocks of non-volatile memory cells characterized by the memory cells of individual blocks being simultaneously erased prior to reprogramming data therein, said method comprising:

assigning and storing a state for each of the plurality of files of data programmed in the plurality of blocks of non-volatile memory cells, the assigned state of each of the plurality of files being based on at least;

a number of the blocks of non-volatile memory cells that are partially filled with data of the file, and

a number of the blocks of non-volatile memory cells that are partially filled with data of the file that also contain data of one or more other of the plurality of files, and

selecting one or more of the blocks of non-volatile memory cells in which data of a given one of the individual files of data are to be programmed based on the stored state of the given one of the individual files of data, and

programming the data of the given one of the individual files of data into the selected one or more blocks.

20. The method of claim 19, wherein the selecting is based on the stored state of the given one of the individual files in order to maintain a number of the blocks of memory cells partially containing data of the given one of the files below a preset limit.