MEMORY SYSTEM AND METHOD FOR CONTROLLING A NONVOLATILE SEMICONDUCTOR MEMORY

• US 20090248964A1
• Filed: 02/27/2009
• Published: 10/01/2009
• Est. Priority Date: 03/01/2008
• Status: Active Grant

• Current Assignee: Kioxia Corporation
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Yano, Junji, Matsuzaki, Hidenori, Hatsuda, Kosuke, Okamoto, Wataru
• Granted Patent: US 8,745,313 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 2206/1014 One time programmable [OTP] memory, e.g. PROM, WORM
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 11/5628 Programming or writing circuits; Data input circuits
• 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
• CPC Class Codes: G11C 2211/5643 Multilevel memory comprising cache storage devices
• CPC Class Codes: G11C 2211/5646 Multilevel memory with flag bits, e.g. for showing that a "first page" of a word line is programmed but not a "second page"

Abstract

A memory system includes a nonvolatile semiconductor memory having blocks, the block being data erasing unit; and a controller configured to execute; an update processing for; writing superseding data in a block, the superseding data being treated as valid data; and invalidating superseded data having the same logical address as the superseding data, the superseded data being treated as invalid data; and a compaction processing for; retrieving blocks having invalid data using a management tablet the management table managing blocks in a linked list format for each number of valid data included in the block; selecting a compaction source block having at least one valid data from the retrieved blocks; copying a plurality of valid data included in the compaction source blocks into a compaction target block; invalidating the plurality of valid data in the compaction source blocks; and releasing the compaction source blocks in which all data are invalidated.

Claims

1. A memory system comprising:

a nonvolatile semiconductor memory having a plurality of blocks, the block having a plurality of pages, the block being data erasing unit and the page being data writing unit, the block being erased before rewriting to the same page; and

a controller configured to execute;

an update processing for;

writing superseding data in a block having at least one writable page, the superseding data being treated as valid data; and

invalidating superseded data having the same logical address as the superseding data, the superseded data being treated as invalid data; and

a compaction processing for;

retrieving blocks having invalid data using a management table, the management table managing blocks in a linked list format for each number of valid data included in the block;

selecting a compaction source block having at least one valid data from the retrieved blocks;

copying a plurality of valid data included in the compaction source blocks into a compaction target block;

invalidating the plurality of valid data in the compaction source blocks; and

releasing the compaction source blocks in which all data are invalidated.

2. The memory system according to claim 1, wherein the controller retrieves, in executing the compaction processing, the blocks in order from one with a smallest number of valid data from the management table according to a linked list.

3. The memory system according to claim 2, wherein the controller selects, in executing the compaction processing, the compaction source blocks until the sum of invalid data included in the compaction source blocks reaches a size of the block.

4. The memory system according to claim 3, wherein the controller selects, in executing the compaction processing, the compaction source blocks so that the sum of valid data included in the compaction source blocks reaches a size of the block.

5. The memory system according to claim 2, wherein the controller refers to, in executing the compaction processing, a list top pointer, the list top pointer indicates a block registered at the head of the linked list for each number of valid data included in the block.

6. The memory system according to claim 2, wherein the controller detects, in executing the compaction processing, any one of the blocks with the number of valid data as the retrieval target from the management table and retrieves the blocks from the management table according to the linked list.

7. The memory system according to claim 4, wherein the controller copies, in executing the compaction processing, the plurality of valid data into the compaction target block in which all pages are writable when the sum of valid data included in the compaction source blocks reaches a size of the block.

8. The memory system according to claim 7, wherein the controller manages the released block as a free block and allocates any one of the free blocks, after erasing, to the compaction target block.

9. The memory system according to claim 4, wherein the controller copies, in executing the compaction processing, the plurality of valid data into the compaction target block in which at least one page is written when the sum of valid data included in the compaction source blocks is smaller than a size of the block.

10. The memory system according to claim 9, wherein the compaction target block is, in executing the update processing, used for writing the superseding data.

11. The memory system according to claim 4, wherein the controller copies, in executing the compaction processing, after copying the plurality of valid data having a size of the block into a first compaction target block in which all pages are writable, the remainder of the valid data being smaller than a size of the block into a second compaction target block in which at least one page is written.

12. The memory system according to claim 11, wherein the controller manages the released block as a free block and allocates any one of the free blocks, after erasing, to the first compaction target block.

13. The memory system according to claim 12, wherein the second compaction target block is, in executing the update processing, used for writing the superseding data.

14. The memory system according to claim 1, wherein

in the management table, for each number of valid data included in the block, a next one of the block having the same number of valid data is correlated by a forward direction link, and

the controller retrieves the block from the management table using the forward direction link.

15. The memory system according to claim 7, wherein

in the management table, for each number of valid data included in the block unit, a previous one of the block having the same number of valid data is correlated by a reverse direction link, and

the controller links entries again in the management table using the reverse direction link.

16. The memory system according to claim 15, wherein the controller links entries again when the number of valid data included in the blocks changes.

17. The memory system according to claim 1, wherein the controller selects valid data, in the compaction processing, in a predetermined management unit, a size of the block is a natural number times as large as the predetermined management unit, and the predetermined management unit is larger than a size of the page.

18. The memory system according to claim 1 wherein the controller selects valid data, in the compaction processing, in a predetermined management unit, a size of the page is a natural number times as large as the predetermined management unit.

19. A method of controlling a nonvolatile semiconductor memory, the nonvolatile semiconductor memory having a plurality of blocks, the block having a plurality of pages, the block being data erasing unit and the page being data writing unit, the block being erased before rewriting to the same page, comprising:

executing an update processing which includes;

writing superseding data in a block having at least one writable page, the superseding data being treated as valid data; and

invalidating superseded data having the same logical address as the superseding data, the superseded data being treated as invalid data; and

executing a compaction processing which includes;

retrieving blocks having invalid data using a management table, the management table managing blocks in a linked list format for each number of valid data included in the block;

selecting a compaction source block having at least one valid data from the retrieved blocks;

copying a plurality of valid data included in the compaction source blocks into a compaction target block;

invalidating the plurality of valid data in the compaction source blocks; and

releasing the compaction source blocks in which all data are invalidated.

20. The method according to claim 19, wherein in executing the compaction processing, the blocks is retrieved in order from one with a smallest number of valid data from the management table according to a linked list.