Flash storage controller execute loop

• US 20090172263A1
• Filed: 04/08/2008
• Published: 07/02/2009
• Est. Priority Date: 12/27/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Pliant Technology, Inc. (Western Digital Corporation)
• Inventors: Olbrich, Aaron K., Prins, Douglas A.
• Granted Patent: US 8,621,138 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 13/1657 Access to multiple memories
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• 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/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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/10 Programming or data input circuits
• CPC Class Codes: G11C 7/1051 Data output circuits, e.g. read-out amplifiers, data output buffers, data output registers, data output level conversion circuits
• CPC Class Codes: G11C 7/1063 Control signal output circuits, e.g. status or busy flags, feedback command signals

Abstract

In a storage controller connected to a flash memory module, an execute loop used to carry out tasks related to reading or writing data from the module. The loop includes reading a data structure from a queue and carrying out a task specified by the data structure, unless resources required by the task are not available, in which event the loop moves on to another data structure stored in another queue. Data structures bypassed by the loop are periodically revisited, until all tasks required are completed. Data structures store state information that is updated when tasks are completed.

Claims

1. A method including performing the following steps in a system comprising a storage controller and a flash memory module:

(a) reading an identifier of a first data structure from a first queue;

(b) reading first state information from the first data structure, the first state information identifying a stage of a flash read or write command;

(c) based on the identified stage, identifying a task to be accomplished or a resource required by the first data structure;

(d) if a resource is required, checking to determine if it is available;

(e) if the resource is available, or if the stage does not require resource availability, performing a task related to reading or writing data from a first segment of the flash memory module;

(f) modifying the first data structure first state information to reflect the performance of the task;

(g) reading an identifier of a second data structure from a second queue;

(h) reading second state information from the second data structure, the second state information identifying a stage of a flash read or write command;

(i) based on the identified stage, identifying a task to be accomplished or a resource required by the second data structure;

(j) if a resource is required, checking to determine if it is available;

(k) if the resource is available, or if the stage does not require resource availability, performing a task related to reading or writing data from a second segment of the flash memory module;

(l) modifying the second data structure second state information to reflect the performance of the task;

(m) returning to step (a) and continuing to repeat the specified steps until the first state information or the second state information indicates that the operations required by the corresponding data structure is complete, at which point the pointer to that data structure is removed from the corresponding queue and the method continues for the other data structure until its state information indicates that the operation required by it are complete, at which point the pointer to that data structure is removed from the corresponding queue.

2. The method as in claim 1, in which:

if step (d) results in a determination that the resource is unavailable, steps (e) and (f) are skipped; and

if step (j) results in a determination that the resource is unavailable, steps (k) and (l) are skipped.

3. The method as in claim 2, in which:

the flash read or write command referenced in step (b) and the flash read or write command referenced in step (h) relate to the same host command.

4. The method as in claim 2, in which:

the flash read or write command referenced in step (b) and the flash read or write command referenced in step (h) relate to different host commands.

5. The method as in claim 2, further including:

(n) following removal of the pointer to the first data structure from the first queue in step (m), reading an identifier of a third data structure from the first queue, the third data structure relating to the same host command as the first data structure.

6. The method as in claim 2, in which:

the step (e) the task includes transmitting command and address information to the first flash module segment.

7. The method as in claim 2, in which:

in step (c) a first buffer is identified as a required resource, in step (d) the availability of the first buffer is checked, and, following a determination that the first buffer is available, in step (e) the first buffer is used as a recipient of data read from the first flash module segment or data to be written to the first flash module segment.

8. The method as in claim 7, in which the system also includes a volatile memory that is external to the storage controller, and in which:

in step (e) the first buffer is used as a recipient of data transferred from the volatile memory.

9. The method as in claim 8, in which:

based on the second state information read in step (h), in step (i) a second buffer is identified as a required resource, in step (j) the availability of the second buffer is checked, and, following a determination that the second buffer is available, in step (k) the second buffer is used as a recipient of data read from the second flash module segment or to be written to the second flash module segment.

10. The method as in claim 9, in which:

in step (k) the second buffer is used to store data to be transferred to the volatile memory.

11. A method including performing the following steps in a system comprising a storage controller and a flash memory module made up of a plurality of flash memory groups:

(a) writing state information into a first data structure related to performing a flash read or write in a first flash memory group, the state information reflecting a need to send command and address information to the first flash memory group;

(b) placing a first pointer to the first data structure on a first queue;

(c) writing state information into a second data structure related to performing a flash read or write in a second flash memory group, the state information reflecting a need to send command and address information to the second flash memory group;

(d) placing a second pointer to the second data structure on a second queue;

(e) writing state information into a third data structure related to performing a flash read or write in a third flash memory group, the state information reflecting a need to send command and address information to the third flash memory group;

(f) placing a third pointer to the third data structure on a third queue;

(g) reading the first pointer from the first queue;

(h) based on the first pointer, reading the first data structure state information;

(i) based on the first data structure state information, transmitting address and command information to the first flash memory group;

(j) modifying the first data structure state information so that the state information reflects the need for a first buffer;

(k) reading the second pointer from the second queue;

(l) based on the second pointer, reading the second data structure state information;

(m) based on the second data structure state information, transmitting address and command information to the second flash memory group;

(n) modifying the second data structure state information so that the state information reflects the need for a second buffer;

(o) reading the third pointer from the third queue;

(p) based on the third pointer, reading the third data structure state information;

(q) based on the third data structure state information, transmitting address and command information to the third flash memory group;

(r) modifying the third data structure state information so that the state information reflects the need for a third buffer;

(s) reading the first pointer from the first queue;

(t) determining whether the first buffer is available;

(u) if the first buffer is available, causing a transfer from the first flash memory group to the first buffer, but if the first buffer is not available, skipping this step (u) and step (v);

(v) modifying the first data structure state information;

(w) reading the second pointer from the second queue.

12. The method as in claim 11, in which:

the first data structure, the second data structure and the third data structure are related to the same host command.

13. The method as in claim 11, in which:

the first data structure relates to a first host command and the second data structure relates to a second host command.

14. The method as in claim 13, in which:

the first host command is a read command and the second host command is a write command.

15. The method as in claim 11, in which:

step (s) is preceded by a step of evaluating a fourth queue and determining that the fourth queue does not contain any pointer to any data structure.

16. The method as in claim 11, further including:

(x) determining whether the second buffer is available;

(y) if the second buffer is available, causing a transfer from the second flash memory group to the second buffer, but if the second buffer is not available, skipping this step (y) and step (z);

(z) modifying the second data structure state information;

(aa) reading the third pointer from the third queue;

(bb) determining whether the third buffer is available;

(cc) if the third buffer is available, causing a transfer from the third flash memory group to the third buffer, but if the third buffer is not available, skipping this step (cc);

(dd) modifying the third data structure state information; and

(ee) reading the first pointer from the first queue.

17. The method as in claim 11, further including:

(x) following the completion of flash read or write operations relating to the first data structure, removing the first pointer from the first queue.

18. The method as in claim 17, further including:

(y) at some point following removal of the first pointer from the first queue, reading a fourth pointer from the first queue, the fourth pointer relating to a fourth data structure.

19. The method as in claim 18, in which:

the step (u) transfer is a DMA transfer.

20. The method as in claim 11, in which:

step (i) triggers a read from flash memory devices of the first flash memory group to page buffers associated with those devices, and this read overlaps step (m).

21. A system comprising a storage controller connected to a flash memory module, the storage controller including the following:

a first data structure containing state information relating to the stage of completion of a first flash read or write operation, the first flash operation relating to a first group of flash memory devices within the flash memory module;

a second data structure containing state information relating to the stage of completion of a second flash read or write operation, the second flash operation relating to the first group of flash memory devices within the flash memory module;

a third data structure containing state information relating to the stage of completion of a third flash read or write operation, the third flash operation relating to a second group of flash memory devices within the flash memory module;

a fourth data structure containing state information relating to the stage of completion of a fourth flash read or write operation, the fourth flash operation relating to a third group of flash memory devices within the flash memory module;

a first queue holding a pointer to the first data structure and the second data structure;

a second queue holding a pointer to the third data structure; and

a third queue holding a pointer to the fourth data structure.

22. The system as in claim 21, in which:

the first and second flash operations relate to a first host command,

the third flash operation relates to a second host command, and

the fourth flash operation relates to a third host command.

23. The system as in claim 21, in which:

the first and third flash operations relate to a first host command;

the second flash operation relates to a second host command, and

the fourth flash operation relates to a third host command.

24. The system as in claim 21, in which:

the first queue is associated with the first flash memory group, the second queue is associated with the second flash memory group, the third queue is associated with the third flash memory group, and the storage controller further includes;

a first buffer associated with the first queue and the first flash memory group, a second buffer associated with the second queue and the second flash memory group and a third buffer associated with the third queue and the third flash memory group.

25. The system as in claim 21, in which:

the first state information includes information indicating that the first data structure requires a resource to proceed with the first flash operation.