System and method for performing host initiated mass storage commands using a hierarchy of data structures

• US 7,934,052 B2
• Filed: 04/08/2008
• Issued: 04/26/2011
• 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.
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US12/082,202
• Publication Number:
  US 20090172257A1
• Time in Patent Office: 1,113 Days
• Field of Search: None
• 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

Disclosed is a mass storage system and method for breaking a host command into a hierarchy of data structures. Different types of data structures are designed to handle different phases of tasks required by the host command, and multiple data structures may be used to handle portions of the host command in parallel, thereby allowing increased performance. The disclosed embodiments include a flash memory controller designed to allow a high degree of pipelining and parallelism.

Claims

1. Performing the following steps in a system including a storage controller and storage:

(a) in the storage controller, receiving a communication specifying a host read command and a first logical address range consisting of a starting logical address and a transfer length;

(b) in the storage controller, creating a first data structure, the data structure including a command, and specifying a second logical address range, the second logical address range being a subset of the first logical address range and including a first logical address and a second logical address, the second logical address being higher in the logical address range than the first logical address;

(c) in the storage controller, creating a second and third data structure, including;

(1) specifying in each data structure one or more storage commands necessary to carry out a portion of the host read command;

(2) specifying in each data structure a physical address corresponding to a different portion of the second logical address range, such that the second data structure includes a first physical address corresponding to the first logical address and the third data structure includes a second physical address corresponding to the second logical address;

(d) commencing execution of a storage command associated with the third data structure prior to commencing execution of a storage command associated with the second data structure;

such that data associated with the second logical address is read from the storage prior to data associated with the first logical address.

2. The method as in claim 1, further including performing the following steps after step (d):

(e) storing the data associated with the second logical address at a first buffer address in a buffer contained in the storage controller;

(f) storing the data associated with the first logical address at a second buffer address in the buffer, this step (f) occurring after step (e), the first buffer address being at a higher address than the second buffer address, such that the data is stored in the buffer in an order that corresponds to the order of the first and second logical addresses.

3. The method as in claim 2 in which the storage includes one or more flash memory devices.

4. The method as in claim 2, in which the second data structure further specifies information from which the second buffer address can be derived and the third data structure further specifies information from which the first buffer address can be derived.

5. A method as in claim 1, in which the step (d) execution of the storage command associated with the second data structure begins before the execution of the storage command associated with the third data structure is complete.

6. In a system including a storage controller and storage, a method comprising the following steps:

(a) in the storage controller, receiving a host read command specifying a logical address range;

(b) in the storage controller, creating a primary data structure that specifies the entire logical address range;

(c) in the storage controller, creating first and second secondary data structures, each of which specifies a read command and a portion of the logical address range;

(d) in the storage controller, creating a plurality of tertiary data structures for each of the secondary data structures, each of the tertiary data structures specifying a storage read command and an address relating to a portion of the logical address range specified by the secondary data structure with which the tertiary data structure is associated;

(e) for each tertiary data structure, executing at least one storage read command in the storage, such that a storage read command for a first tertiary data structure relating to a relatively higher portion of the logical address range completes prior to execution of a storage read command for a second tertiary data structure relating to a relatively lower portion of the logical address range.

7. The method of claim 6, in which the first and second tertiary data structures are associated with the same secondary data structure.

8. The method of claim 7, further including:

(f) storing the data returned from each tertiary data structure storage read command in a buffer, the data being stored in an order corresponding to the ordering of the logical address range, such that data relating to the first tertiary data structure is stored at a higher buffer address than data relating to the second tertiary data structure.

9. The method of claim 8, in which the execution of the first tertiary data structure storage read command in the storage commences before the execution of the second tertiary data structure read command has completed in the storage.

10. The method of claim 9, in which the execution of the first and second tertiary data structure storage read commands overlaps execution of a storage read command relating to a third tertiary data structure, the third tertiary data structure relating to a secondary data structure that is different than the secondary data structure to which the first and second tertiary data structures are related.

11. In a system including a storage controller and storage, performing the following steps:

(a) receiving from a host a first command block containing a first host read command and specifying a first logical address range;

(b) creating a first data structure that holds information from the first command block plus an identifier of an initiator responsible for the first command block;

(c) checking to determine whether any portion of the first logical address range is the subject of a previously received command, and, if so, taking an action;

(d) creating a second data structure that specifies a first buffer address range for storing data obtained from storage as a result of the first host read command;

(e) creating multiple third data structures, each specifying (i) an address or address range that corresponds to a portion of the first logical address range and (ii) a buffer address that is within the first buffer address range;

(f) reading from the storage data corresponding to the third data structure address or address ranges; and

(g) storing the data read in step (f) in the buffer, the data being stored in locations corresponding to the first buffer address range, the data being received out of address order such that later-received data is stored at a lower buffer address than earlier-received data;

whereby the data is stored in the buffer in an order corresponding to the location of the data within the first logical address range, but is read from the storage in a temporal order that does not correspond to the order of the data within the first logical address range.

12. The method as in claim 11 in which the action taken in step (c) includes stalling execution of the host read command until handling of the previously received command has reached a specified point.

13. The method as in claim 12 further including:

(h) receiving from a host a second command block containing a second host read command and specifying a second logical address range;

(i) creating a fourth data structure that holds information from the second command block plus an identifier of an initiator responsible for the second command block;

(j) checking to determine whether any portion of the second logical address range is the subject of a previously received command, and, if so, taking an action;

(k) creating a fifth data structure that specifies a second buffer address range for storing data obtained from storage as a result of the second host read command;

(l) creating multiple sixth data structures, each specifying (i) an address or address range that corresponds to a portion of the second logical address range and (ii) a buffer address that is within the second buffer address range;

(m) reading from the storage data corresponding to the sixth data structure address or address ranges; and

(n) storing the data read in step (m) in the buffer, the data being stored in locations corresponding to the second buffer address range;

whereby, step (m) overlaps step (f) in time.

14. The method as in claim 13 further including:

(o) receiving from a host a third command block containing a third host read command and specifying a third logical address range;

(p) creating a seventh data structure that holds information from the third command block plus an identifier of an initiator responsible for the third command block;

(q) checking to determine whether any portion of the third logical address range is the subject of a previously received command, and, if so, taking an action;

(r) creating an eighth data structure that specifies a third buffer address range for storing data obtained from storage as a result of the third host read command;

(s) creating multiple ninth data structures, each specifying (i) an address or address range that corresponds to a portion of the third logical address range and (ii) a buffer address that is within the third buffer address range;

(t) reading from the storage data corresponding to the ninth data structure address or address ranges; and

(u) storing the data read in step (t) in the buffer, the data being stored in locations corresponding to the third buffer address range;

whereby, step (t) overlaps steps (m) and (f) in time.

15. The method as in claim 14 further including:

(v) receiving from a host a fourth command block containing a fourth host read command and specifying a fourth logical address range;

(w) creating a tenth data structure that holds information from the fourth command block plus an identifier of an initiator responsible for the fourth command block;

(x) checking to determine whether any portion of the fourth logical address range is the subject of a previously received command, and, if so, taking an action;

(y) creating an eleventh data structure that specifies a fourth buffer address range for storing data obtained from storage as a result of the fourth host read command;

(z) creating multiple twelfth data structures, each specifying (i) an address or address range that corresponds to a portion of the fourth logical address range and (ii) a buffer address that is within the fourth buffer address range; and

(aa) reading from the storage data corresponding to the twelfth data structure address or address ranges; and

(bb) storing the data read in step (aa) in the buffer, the data being stored in locations corresponding to the fourth buffer address range;

whereby, step (aa) overlaps steps (t), (m) and (f) in time.

16. A flash memory controller comprising:

a first memory holding a first data structure, the first data structure including a command, a specification of a first logical address range received from a host, and a pointer to a second data structure;

a second memory holding a second data structure, the second data structure including a specification of a second logical address range that is a subset of the first logical address range and a pointer to the first data structure;

a third memory holding a third data structure, the third data structure including a specification of a third logical address range that is a subset of the first logical address range but does not overlap the second logical address range, and a pointer to the first data structure;

a fourth memory further holding a first and a second set of data;

the first set of data corresponding to a portion, but not all, of the second logical address range, and the second set of data corresponding to a portion, but not all, of the third logical address range.

17. The controller as in claim 16, in which:

the second memory holds a fourth data structure, the fourth data structure including a pointer to the second data structure and a specification of a first physical address that corresponds to a first subset of the second logical address range.

18. The controller as in claim 17, in which:

the second memory holds a fifth data structure, the fifth data structure including a pointer to the second data structure and a specification of a second physical address that corresponds to a second subset of the second logical address range, the first and second subsets of the second logical address range being non-overlapping.

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

the third memory holds a sixth data structure, the sixth data structure including a pointer to the third data structure and a specification of a third physical address that corresponds to a first subset of the third logical address range.

20. The controller as in claim 19, in which:

the third memory holds a seventh data structure, the seventh data structure including a pointer to the third data structure and a specification of a fourth physical address that corresponds to a second subset of the third logical address range.

21. In a system including a flash memory controller and a flash memory module made up of a plurality of groups of flash memory devices, a method including the following steps:

(a) receiving a first host communication specifying a first read command and a first logical address range;

(b) generating a first data structure including a first portion of the first logical address range;

(c) generating a second data structure including a second portion of the first logical address range, the second portion of the first logical address range not overlapping the first portion of the first logical address range and being higher in the first logical address range than the first portion of the first logical address range;

(d) storing the first data structure in a first storage controller memory;

(e) storing the second data structure in a second storage controller memory;

(f) reading data corresponding to the first portion of the first logical address range from a first flash memory group; and

(g) reading data corresponding to the second portion of the first logical address range from a second flash memory group.

22. The method as in claim 21, in which step (g) concludes prior to the conclusion of step (f).

23. The method as in claim 22, further including:

(h) receiving a second host communication specifying a second read command and a second logical address range;

(i) generating a third data structure including a first portion of the second logical address range;

(j) generating a third data structure including a second portion of the second logical address range, the second portion of the second logical address range not overlapping the first portion of the second logical address range and being higher in the address range than the first portion of the second logical address range;

(k) storing the first data structure in a first storage controller memory;

(l) storing the second data structure in a second storage controller memory;

(m) reading data corresponding to the first portion of the first logical address range from a third flash memory group; and

(n) reading data corresponding to the second portion of the second logical address range from a fourth flash memory group;

whereby step (m) overlaps step (f).

24. The method as in claim 23, whereby step (a) completes before step (h), and step (n) completes before step (g).

25. The method as in claim 22, further including:

(h) storing the data read from storage locations corresponding to the first and second portions of the first logical address range in a buffer, the data corresponding to the second portion being stored in a buffer location with a higher buffer address than the data corresponding to the first portion.