Non-volatile memory storage systems for phased garbage collection

• US 20080034174A1
• Filed: 08/04/2006
• Published: 02/07/2008
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Traister, Shai, Lin, Jason
• Granted Patent: US 7,451,265 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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

Abstract

A non-volatile memory storage system is provided. The non-volatile memory storage system includes a memory configured to store a storage system firmware and a non-volatile memory cell array configured to maintain a buffer. A processor in communication with the memory and the non-volatile memory cell array also is included in the non-volatile memory storage system. Here, the processor is configured to execute the storage system firmware stored in the memory. The storage system firmware comprises program instructions for receiving a write command to write data to the non-volatile memory cell array. The write command is allocated a timeout period to complete an execution of the write command. The storage system firmware also comprises program instructions for performing a portion of a garbage collection operation within the timeout period and for storing the data in the buffer.

Claims

1. A non-volatile memory storage system, comprising:

a memory configured to store a storage system firmware;

a non-volatile memory cell array configured to maintain a buffer; and

a processor in communication with the memory and the non-volatile memory cell array, the processor being configured to execute the storage system firmware stored in the memory, the storage system firmware comprising program instructions for,

receiving a write command to write a plurality of data to the non-volatile memory cell array, the write command being allocated a timeout period to complete an execution of the write command,

performing a portion of a garbage collection operation within the timeout period, and

storing the plurality of data in the buffer.

2. A non-volatile memory storage system, comprising:

a memory configured to store a storage system firmware;

a non-volatile memory cell array configured to maintain a write buffer block, the write buffer block being configured to span a plurality of logical addresses; and

a processor in communication with the memory and the non-volatile memory cell array, the processor being configured to execute the storage system firmware stored in the memory, the storage system firmware comprising program instructions for,

receiving a write command to write a plurality of data to the non-volatile memory cell array, the write command being allocated a timeout period to complete an execution of the write command,

asserting a busy signal,

performing a portion of a garbage collection operation for a garbage collection time period,

writing the plurality of data to the write buffer block, and

releasing the busy signal before the timeout period.

3. The non-volatile memory storage system of claim 2, wherein the program instructions for performing the portion of the garbage collection operation for the garbage collection time period comprises program instructions for copying a portion of a plurality of valid data from one or more first blocks to a second block for the garbage collection time period.

4. The non-volatile memory storage system of claim 2, wherein the storage system firmware further comprises program instructions for:

estimating an execution time for the execution of the write command before the performing the portion of the garbage collection operation and the writing the plurality of data to the write buffer block,

wherein the portion of the garbage collection operation is performed and the plurality of data is written to the write buffer block if the execution time is greater than the timeout period.

5. The non-volatile memory storage system of claim 2, wherein the program instructions for the writing the plurality of data to the write buffer block comprises program instructions for:

writing the plurality of data to a scratch pad block; and

copying the plurality of data from the scratch pad block to the write buffer block.

6. The non-volatile memory storage system of claim 2, wherein the write buffer block comprises a plurality of pages and wherein each of the plurality of pages is indexed.

7. The non-volatile memory storage system of claim 2, wherein the write buffer block comprises a plurality of sectors and wherein each of the plurality of sectors is indexed.

8. The non-volatile memory storage system of claim 2, wherein the write buffer block comprises a plurality of blocks.

9. A non-volatile memory storage system, comprising:

a read-only memory (ROM) configured to store a storage system firmware;

a memory cell array configured to maintain a write buffer block, the write buffer block being configured to span a plurality of logical addresses;

a non-volatile memory cell array; and

a processor in communication with the ROM, the memory cell array, and the non-volatile memory cell array, the processor being configured to execute the storage system firmware stored in the ROM, the storage system firmware comprising program instructions for,

receiving a first write command to write a first plurality of data to the non-volatile memory cell array, the first write command being allocated a first timeout period to complete a first execution of the first write command;

asserting a first busy signal,

copying a first portion of a plurality of valid data from one or more first blocks to a second block for a garbage collection time period,

writing the first plurality of data to the write buffer block,

releasing the first busy signal before the first timeout period,

receiving a second write command to write a second plurality of data to the non-volatile memory cell array, the second write command being received after the receiving the first write command, the second write command being allocated a second timeout period to complete a second execution of the second write command,

asserting a second busy signal,

copying a second portion of the plurality of valid data from the one or more first blocks to the second block for the garbage collection time period, and

releasing the second busy signal before the second timeout period.

10. The non-volatile memory storage system of claim 9, wherein the storage system firmware further comprises program instructions for writing the second plurality of data to the write buffer block.

11. The non-volatile memory storage system of claim 9, wherein the storage system firmware further comprises program instructions for writing the second plurality of data to an update block.

12. The non-volatile memory storage system of claim 9, wherein the storage system firmware further comprises program instructions for erasing the one or more first blocks if the second portion of the plurality of valid data is a last portion of the plurality of valid data.

13. The non-volatile memory storage system of claim 9, wherein the storage system firmware further comprises program instructions for copying the first plurality of data from the write buffer block to an update block.

14. The non-volatile memory storage system of claim 9, wherein the write buffer block comprises a plurality of pages, and wherein the first plurality of data is written to a first page associated with the write buffer block and the second plurality of data is written to a second page associated with the write buffer block.

15. The non-volatile memory storage system of claim 9, wherein the write buffer block comprises a plurality of sectors, and wherein the first plurality of data is written to a first sector associated with the write buffer block and the second plurality of data is written to a second sector associated with the write buffer block.

16. The non-volatile memory storage system of claim 9, wherein the non-volatile memory storage system comprises a plurality of buffering levels, the write buffer block being associated with one of the plurality of buffering levels.

17. The non-volatile memory storage system of claim 9, wherein the program instructions for the writing the first plurality of data to the write buffer block comprises program instructions for:

writing the first plurality of data to a sector of a scratch pad block, wherein a page associated with the sector comprises a plurality of sectors; and

copying the page to the write buffer block when the plurality of sectors associated with the page is filled.

18. The non-volatile memory storage system of claim 17, wherein the scratch pad block is associated with a first buffer level and the write buffer block is associated with a second buffer level.

19. The non-volatile memory storage system of claim 9, wherein the program instructions for writing the plurality of data comprises program instructions for:

writing the plurality of data to a first buffer level; and

copying the plurality of data from the first buffer level to the write buffer block, the write buffer block being associated with a second buffer level.

20. A non-volatile memory storage system, comprising:

a memory configured to store a storage system firmware;

a non-volatile memory cell array configured to maintain a write buffer block, the write buffer block being configured to span a plurality of logical addresses; and

a processor in communication with the memory and the non-volatile memory cell array, the processor being configured to execute the storage system firmware stored in the memory, the storage system firmware comprising program instructions for,

receiving a write command to write a plurality of data to the non-volatile memory cell array, the non-volatile memory cell array being allocated a timeout period to complete an execution of the write command,

asserting a busy signal,

copying a portion of a plurality of valid data from one or more first blocks to a second block for a garbage collection time period,

writing the plurality of data to the write buffer block, and

releasing the busy signal before the timeout period.

21. The non-volatile memory storage system of claim 20, wherein the program instructions for the copying the portion of the plurality of valid data comprises program instructions for:

tracking a time for the copying the portion of the plurality of valid data from the one or more first blocks to the second block; and

stopping the copying the portion of the plurality of valid data before the time exceeds the garbage collection time period.

22. The non-volatile memory storage system claim 20, wherein the storage system firmware further comprises program instructions for:

estimating an execution time for the execution of the write command before the copying the plurality of valid data and the writing the plurality of data,

wherein the portion of the plurality of valid data is copied and the plurality of data is written to the write buffer block if the execution time exceeds the timeout period.

23. The non-volatile memory storage system of claim 20, wherein the program instructions for the writing the portion of the plurality of data comprises program instructions for:

providing a scratch pad block comprising a page, the page comprising a plurality of sectors;

writing the plurality of data to a sector associated with the page; and

copying the page from the scratch pad block to the write buffer block when the page is full.

24. The non-volatile memory storage system of claim 20, wherein the garbage collection time period is a difference between the timeout period and a programming time associated with the writing the plurality of data.

25. The non-volatile memory storage system of claim 20, wherein the write buffer block is configured to span an entire logical address space.

26. The non-volatile memory storage system of claim 20, wherein the write buffer block is configured for a sector level index.

27. The non-volatile memory storage system of claim 20, wherein the write buffer block is configured for a page boundary index.

28. The non-volatile memory storage system of claim 20, wherein the storage system firmware further comprises program instructions for allocating a plurality of sectors to the write buffer block, the plurality of sectors being greater than a total number of metablocks in the non-volatile memory storage system.