System and method for performing host initiated mass storage commands using a hierarchy of data structures
First Claim
Patent Images
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.
11 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5)
-
-
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. - View Dependent Claims (7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20)
-
-
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. - View Dependent Claims (22, 23, 24, 25)
-
Specification