Memory system and method for controlling a nonvolatile semiconductor memory

• US 8,745,313 B2
• Filed: 02/27/2009
• Issued: 06/03/2014
• Est. Priority Date: 03/01/2008
• Status: Active Grant

• Current Assignee: Kioxia Corporation
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Yano, Junji, Hatsuda, Kosuke, Matsuzaki, Hidenori, Okamoto, Wataru
• Primary Examiner(s): Parikh, Kalpit
• Application Number:
  US12/394,632
• Publication Number:
  US 20090248964A1
• Time in Patent Office: 1,922 Days
• Field of Search: 711/103, 711/165, 711/166, 707/800, 707/818
• 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 including a plurality of blocks, each one of the plurality of blocks being a data erasing unit and being capable of storing N pieces of valid data, valid data being managed by a size of a management unit, the size of the management unit being larger than a size of one page which is a writing unit for the nonvolatile semiconductor memory, and being smaller than a size of one block;

a volatile semiconductor memory including a storage area; and

a controller configured to;

manage the plurality of blocks in a plurality of linked lists, each one of the plurality of linked lists linking blocks with a same number of valid data, a first linked list managing blocks with a first number of valid data and a second linked list managing blocks with a second number of valid data, the first number being smaller than the second number, the first and second numbers being selected from among numbers of 1 to N−

1;

retrieve compaction source blocks from among the blocks managed by the first linked list, and if there are no blocks managed by the first linked list, thereafter retrieving the compaction source blocks from among the blocks managed by the second linked list;

select valid data stored in the compaction source blocks, rewrite the selected valid data in a first compaction target block different from the compaction source blocks, and release the compaction source blocks after rewriting the selected valid data; and

store write data in the storage area, the write data being sent from a host apparatus,

wherein when the sum of valid data included in the compaction source blocks reaches a size of one block, the controller is configured to acquire the first compaction target block and rewrite the selected valid data in the first compaction target block, when the sum of valid data included in the compaction source blocks does not reach a size of one block, the controller is configured to rewrite the selected valid data in a block allocated to an input buffer of the nonvolatile semiconductor memory as a first valid data, when the write data stored in the storage area reaches the size of the management unit, the controller is configured to copy the write data stored in the storage area to the input buffer as a second valid data, and when a total size of the first and second valid data included in the input buffer reaches a size of one block, the controller is configured to rewrite the first and second valid data included in the input buffer in a second compaction target block, and release the block allocated to the input buffer after rewriting the first and second valid data included in the input buffer.

2. The memory system according to claim 1, wherein the controller is further configured to set a first top pointer at one of the blocks managed by the first linked list and to set a second top pointer at one of the blocks managed by the second linked list.

3. The memory system according to claim 2, wherein the controller is further configured to retrieve the compaction source blocks by tracing the blocks from the first pointer in the first linked list and to retrieve the compaction source blocks by tracing the blocks from the second pointer in the second linked list.

4. The memory system according to claim 3, wherein each entry in one of the plurality of linked lists includes a next pointer, the blocks managed by the linked list are linked in a forward order by the next pointer, and the controller is further configured to trace the blocks by referring to the next pointer.

5. The memory system according to claim 4, wherein each entry in one of the plurality of linked lists includes a previous pointer, the blocks managed by the linked list are linked in a reverse order by the previous pointer, and when the number of valid data included in the block decreases, the controller is further configured to change a link between entries by referring to the next pointer and the previous pointer.

6. The memory system according to claim 1, wherein the size of the management unit is smaller than that of the data erasing unit.

7. The memory system according to claim 6, wherein each one of the plurality of blocks includes a plurality of pages, each one of the plurality of pages is a data programming, and a reading unit and a size of the management unit is a natural number times as large as that of one page.

8. The memory system according to claim 6, wherein each one of the plurality of blocks includes a plurality of pages, each one of the plurality of pages is a data programming, and a reading unit and a size of one page is a natural number times as large as that of the management unit.

9. A compaction method comprising:

storing data in a nonvolatile semiconductor memory, the nonvolatile memory including a plurality of blocks, each one of the plurality of blocks being a data erasing unit and being capable of storing N pieces of valid data, valid data being managed by a size of a management unit, the size of the management unit being larger than a size of one page which is a writing unit for the nonvolatile semiconductor memory, and being smaller than a size of one block;

managing the plurality of blocks in a plurality of linked lists, each one of the plurality of linked lists linking blocks with a same number of valid data, a first linked list managing blocks with a first number of valid data and a second linked list managing blocks with a second number of valid data, the first number being smaller than the second number, the first and second numbers being selected from among numbers of 1 to N−

1;

retrieving compaction source blocks from among the blocks managed by the first linked list, and if there are no blocks managed by the first linked list, thereafter retrieving the compaction source blocks from among the blocks managed by the second linked list;

selecting valid data stored in the compaction source blocks, rewriting the selected valid data in a first compaction target block different from the compaction source blocks, and releasing the compaction source blocks after rewriting the selected valid data;

storing write data in a storage area included in a volatile semiconductor memory, the write data being sent from a host apparatus; and

further comprising;

when the sum of valid data included in the compaction source blocks reaches a size of one block, acquiring the first compaction target block and rewriting the selected valid data in the first compaction target block, when the sum of valid data included in the compaction source blocks does not reach a size of one block, rewriting the selected valid data in a block allocated to an input buffer of the nonvolatile semiconductor memory as a first valid data, when the write data stored in the storage area reaches the size of the management unit, copying the write data stored in the storage area to the input buffer as a second valid data, and when a total size of the first and second valid data included in the input buffer reaches a size of one block, rewriting the first and second valid data included in the input buffer in a second compaction target block and releasing the block allocated to the input buffer after rewriting the first and second valid data included in the input buffer.

10. The method according to claim 9, further comprising:

setting a first top pointer at one of the blocks managed by the first linked list and setting a second top pointer at one of the blocks managed by the second linked list.

11. The method according to claim 10, wherein the retrieving includes tracing the blocks from the first pointer in the first linked list and tracing the blocks from the second pointer in the second linked list.

12. The method according to claim 11, wherein each entry in one of the plurality of linked lists includes a next pointer, the blocks managed by the linked list are linked in a forward order by the next pointer, and the tracing includes tracing the blocks by referring to the next pointer.

13. The method according to claim 12, wherein each entry in one of the plurality of linked lists includes a previous pointer, the blocks managed by the linked list are linked in a reverse order by the previous pointer, and when the number of valid data included in the block decreases, further comprising:

changing a link between entries by referring to the next pointer and the previous pointer.

14. The method according to claim 9, wherein the size of the management unit is smaller than that of the data erasing unit.

15. The method according to claim 14, wherein each one of the plurality of blocks includes a plurality of pages, each one of the plurality of pages is a data programming, and a reading unit and a size of the management unit is a natural number times as large as that of one page.

16. The method according to claim 14, wherein each one of the plurality of blocks includes a plurality of pages, each one of the plurality of pages is a data programming, and a reading unit and a size of one page is a natural number times as large as that of the management unit.