Method for phased garbage collection

• US 20080082596A1
• Filed: 09/29/2006
• Published: 04/03/2008
• Est. Priority Date: 09/29/2006
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Corporation (Western Digital Corporation)
• Inventors: Gorobets, Sergey Anatolievich
• Granted Patent: US 7,464,216 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

A method for phased garbage collection is described, the method including receiving a write command to write a memory write to a metablock, performing a first portion of a garbage collection operation, and storing the memory write in a buffer portion of the metablock.

Claims

1. A method, comprising:

receiving a write command to write a memory write to a metablock;

performing a first portion of a garbage collection operation; and

storing the memory write in a buffer portion of the metablock.

2. The method of claim 1, further comprising:

allocating a first timeout period to the write command to complete an execution of the write command within the first timeout period.

3. The method of claim 1, wherein performing the first portion of the garbage collection operation comprises performing the garbage collection operation for another metablock.

4. The method of claim 1, further comprising performing additional portions of the garbage collection operation until an update block is available.

5. The method of claim 4, further comprising writing the memory write from the buffer portion to the update block.

6. The method of claim 2, further comprising:

determining whether the garbage collection operation is complete; and

if the garbage collection operation is not complete, performing a second portion of the garbage collection operation during a second timeout period.

7. The method of claim 1, wherein performing the first portion of the garbage collection operation comprising performing the garbage collection operation for the metablock.

8. The method of claim 1, further comprising allocating the metablock comprising a logical group and the buffer portion.

9. A method, comprising:

allocating a first memory block comprising a first logical group and a first buffer portion;

receiving a memory write command and writing the memory write command to a second buffer portion of a second memory block;

performing at least a portion of a garbage collection of a second logical group;

opening an update block for the first logical group; and

performing a phased garbage collection of the first logical group.

10. The method of claim 9, further comprising converting the memory block to an intact block after the performing the phased of garbage collection.

11. The method of claim 9, further comprising:

indicating that the buffer portion is available using a first intact state;

indicating that the memory block is full using a second intact state; and

indicating that a first phase of the phased garbage collection is completed using a half full state.

12. The method of claim 9, further comprising compacting the memory block if the memory block comprises invalid data.

13. The method of claim 9, further comprising allocating a reserve buffer portion of the memory block to store another memory write received before the second memory write command.

14. A method, comprising:

allocating a memory block comprising a logical group and a buffer portion and indicating that the memory block is in a sequential update state;

performing a first phase of garbage collection and indicating that the memory block is in a half full state;

performing a second phase of garbage collection and indicating that the memory block is in a first intact state; and

writing a memory write of a memory write command to the buffer portion and indicating that the memory block is in a second intact state.

15. The method of claim 14, further comprising:

asserting a first timeout period before the performing the first phase of garbage collection; and

asserting a second timeout period before the performing the second phase of garbage collection.

16. The method of claim 15,

wherein the asserting the first timeout period is in response to receiving another memory write command;

and

wherein the asserting the second timeout period is in response to receiving the memory write command.

17. The method of claim 14, wherein the indicating that the memory block is in a first intact state comprises indicating that the buffer portion may be written to.

18. The method of claim 14, wherein the indicating that the memory block is in a second intact comprises indicating that no more data may be written to the memory block.

19. The method of claim 14, further comprising:

receiving another memory write updating the memory block when the memory block is in the sequential update state; and

indicating that the memory block is in a chaotic update state.

20. The method of claim 19, further comprising:

compacting the memory block; and

indicating that the memory block is in the sequential update state.

21. A method comprising:

allocating a memory block comprising a logical group and a buffer portion;

receiving a first memory write command including a first memory write to update an original block and copying the memory write to the memory block;

asserting a first timeout period in response to the receiving the first memory write and asserting a busy signal to notify a memory host of the first timeout period;

performing a first phase of a garbage collection of the memory block;

receiving a second memory write command including a second memory write to update the memory block;

asserting a second timeout period in response to the receiving the second memory write and asserting the busy signal to notify a memory host of the second timeout period;

performing a second phase of the garbage collection of the memory block; and

writing the second memory write to the buffer portion.

22. The method of claim 21, further comprising:

indicating that the memory block is in a sequential update state in response to the receiving the first memory write;

indicating that the memory block is in a half full state in response to the performing the first phase of the garbage collection;

indicating that the memory block is in a first intact state in response to the performing the second phase of the garbage collection; and

indicating that the memory block is in a second intact state in response to the writing the second memory write.

23. The method of claim 22, wherein the indicating that the memory block is in a first intact state comprises indicating that that the buffer portion may be written to.

24. The method of claim 22, wherein the indicating that the memory block is in a second intact state comprises indicating that no more data may be written to the memory block.

25. The method of claim 21, further comprising compacting the memory block after the receiving the first memory write command if the memory block has invalid data.