Command tag checking in a multi-initiator media controller architecture

• US 8,352,689 B2
• Filed: 11/23/2010
• Issued: 01/08/2013
• Est. Priority Date: 11/30/2009
• Status: Expired due to Fees

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Noeldner, David R., Bratvold, Michael, Smith, Paul H.
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US12/952,207
• Publication Number:
  US 20110131375A1
• Time in Patent Office: 777 Days
• Field of Search: 711/150, 711/156
• US Class Current: 711/150
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/1673 using buffers
• 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 13/385 for adaptation of a particular data processing system to different peripheral devices
• CPC Class Codes: G06F 3/00 Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Described embodiments provide a method of allocating resources of a media controller for a data transfer. A data transfer request is received from at least one host device, and includes a host device ID and a data transfer request ID. The media controller generates a Tag ID of the data transfer request based on the host device ID and the data transfer request ID, and generates a starting memory address of a tag table based on the Tag ID of the data transfer request. A tag count value is read from the starting memory address of the tag table. If the tag count value reaches a threshold, an absence of a tag overlap is determined and the Tag ID of the data transfer request is added to the tag table at the starting memory address.

Claims

1. A method of allocating resources of a media controller for a data transfer, the method comprising:

receiving a data transfer request from at least one host device, wherein the data transfer request includes a host device ID and a data transfer request ID;

generating, by the media controller, a Tag ID of the data transfer request based on the host device ID and the data transfer request ID;

generating, by the media controller, a starting memory address of a tag table based on the Tag ID of the data transfer request;

reading a tag count value from the starting memory address of the tag table;

if the tag count value reaches a threshold;

determining absence of a tag overlap; and

adding the Tag ID of the data transfer request to the tag table at the starting memory address.

2. The method of claim 1, further comprising:

if the tag count value has not reached the threshold;

reading a previous Tag ID stored at the starting memory address;

if the previous Tag ID and the Tag ID of the data transfer request are substantially equivalent;

determining a presence of a tag overlap;

otherwise, if the previous Tag ID and the Tag ID of the data transfer request are not substantially equivalent;

hashing the previous Tag ID to generate a hashed previous Tag ID;

if the hashed previous Tag ID is substantially equivalent to the starting search address;

decrementing the tag count of the starting search address;

incrementing the starting search address to read the tag count value stored at a next address of the tag table; and

reading a next tag count value stored at a next address of the tag table;

if the hashed previous Tag ID is not substantially equivalent to the starting search address;

incrementing the starting search address to read the next tag count value stored at the next address of the tag table.

3. The method of claim 1, wherein the data transfer request ID comprises a 16-bit Small Computer System Interface (SCSI) Command Tag, and the host device ID comprises a 64-bit Serial Attached SCSI (SAS) World Wide Name (WWN).

4. The method of claim 1, wherein the step of hashing the previous Tag ID to generate a hashed previous Tag ID further comprises:

selecting a corresponding hash algorithm based on i) a relative maximum number of host devices from which the media controller concurrently accepts data transfer requests, and ii) a relative maximum number of Tag ID'"'"'s allowed by the media controller per each host device.

5. The method of claim 4, wherein the relative maximum number of host devices is eight.

6. The method of claim 4, wherein the relative maximum number of Tag ID'"'"'s per each host device is a user-selectable variable.

7. The method of claim 4, wherein a maximum number of Tag ID'"'"'s corresponding to concurrently active data transfer requests for all host devices is 128.

8. The method of claim 4, further comprising:

employing a first hash algorithm for media controllers in communication with one host device;

employing a second hash algorithm for media controllers in communication with two host devices;

employing a third hash algorithm for media controllers in communication with four host devices; and

employing a fourth hash algorithm for media controllers in communication with eight host devices.

9. The method of claim 8, wherein:

a first hash algorithm is Hash=Tag ID[0;

7];

a second hash algorithm is Hash={host device ID[0], Tag ID[0;

6]};

a third hash algorithm is Hash={host device ID[0;

1], Tag ID[0;

5]}; and

a fourth hash algorithm is Hash={host device ID[0;

2], Tag ID[0;

4]}.

10. The method of claim 1, wherein the method is implemented by a machine executing program code encoded on a non-transitory machine-readable storage medium.

11. A method of deallocating resources of a media controller after data transfers are completed by the media controller, the method comprising:

providing, to a tag manager of the media controller, a Tag ID corresponding to a complete data transfer;

generating, by the tag manager, a starting memory address of a tag table based on the Tag ID of the data transfer;

reading a tag count value from the starting memory address of the tag table;

if the tag count value has not reached a threshold;

reading a Tag ID at the starting memory address;

if the read Tag ID and the Tag ID of the completed data transfer are substantially equivalent;

setting a status of the starting memory address to invalid;

otherwise, if the read Tag ID and the Tag ID of the completed data transfer are not substantially equivalent;

hashing the read Tag ID into a hashed read Tag ID;

if the hashed read Tag ID is substantially equivalent to the starting search address;

decrementing the tag count of the starting search address;

incrementing the starting search address to a next address; and

reading the tag count value stored at the next address of the tag table;

if the hashed read Tag ID is not substantially equivalent to the starting search address;

incrementing the starting search address; and

reading the tag count value stored at the next address of the tag table.

12. The method of claim 11, further comprising:

if the tag count value reaches a threshold;

determining a presences of an error condition.

13. The method of claim 11, further comprising:

reading the status of the starting memory address;

if the status of the starting memory address is not valid;

incrementing the starting search address a next address;

reading the status stored at the next address of the tag table;

otherwise;

reading the Tag ID stored at the starting memory address.

14. The method of claim 11, wherein the Tag ID is based on an ID of the host device and an ID of the data transfer, wherein the ID of the data transfer comprises a 16-bit Small Computer System Interface (SCSI) Command Tag, and the ID of the host device comprises a 64-bit Serial Attached SCSI (SAS) World Wide Name (WWN).

15. The method of claim 11, wherein the step of hashing the read Tag ID to generate a hashed read Tag ID further comprises:

selecting a corresponding hash algorithm based on a relative maximum number of host devices from which the media controller concurrently performs data transfers, and based on a relative maximum number of Tag ID'"'"'s allowed by the media controller per each host device.

16. The method of claim 11, wherein the method is implemented by a machine executing program code encoded on a non-transitory machine-readable storage medium.

17. A media controller for allocating and deallocating resources for a data transfer, the media controller comprising:

for allocating resources for a data transfer;

a received data path configured to receive a data transfer request from at least one host device, wherein the data transfer request includes a host device ID and a data transfer request ID;

a tag manager configured to i) generate a Tag ID of the data transfer request based on the host device ID and the data transfer request ID, ii) generate a starting memory address of a tag table based on the Tag ID of the data transfer request, and iii) read a tag count value from the starting memory address of the tag table;

if the tag count value reaches a threshold;

the tag manager is configured to i) determine an absence of a tag overlap, and ii) add the Tag ID of the data transfer request to the tag table at the starting memory address;

if the tag count value has not reached the threshold;

the tag manager is configured to i) read a previous Tag ID stored at the starting memory address, and ii) if the previous Tag ID and the Tag ID of the data transfer request are substantially equivalent, determine a presence of a tag overlap.

18. The media controller as recited in claim 17, further comprising:

for deallocating resources of a completed data transfer;

the tag manager is configured to i) receive a Tag ID corresponding to a complete data transfer, ii) generate a starting memory address of a tag table based on the Tag ID of the data transfer, and iii) read a tag count value from the starting memory address of the tag table;

if the tag count value has not reached a threshold;

the tag manager is configured to (i) read a Tag ID at the starting memory address, (ii) set a status of the starting memory address to invalid if the read Tag ID and the Tag ID of the completed data transfer are substantially equivalent, (iii) if the read Tag ID and the Tag ID of the completed data transfer are not substantially equivalent;

(a) hash the read Tag ID into a hashed read Tag ID;

(b) if the hashed read Tag ID is substantially equivalent to the starting search address;

 

(1) decrement the tag count of the starting search address,

 

(2) increment the starting search address to a next address; and

 

(3) read the tag count value stored at the next address of the tag table;

and (iv) if the hashed read Tag ID is not substantially equivalent to the starting search address;

(a) increment the starting search address; and

(b) read the tag count value stored at the next address of the tag table.

19. The media controller as recited in claim 17, wherein the media controller is coupled to a storage media comprising a Redundant Array of Independent Disks (RAID) array.

20. The media controller as recited in claim 17, wherein the RAID array comprises at least one of a solid state disk (SSD), a hard disk drive (HDD), or a hybrid magnetic and solid state storage system.

21. The media controller as recited in claim 17, wherein the media controller is implemented in an integrated circuit.

22. A non-transitory machine-readable storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of allocating resources of a media controller for a data transfer, the method comprising:

receiving a data transfer request from at least one host device, wherein the data transfer request includes a host device ID and a data transfer request ID;

generating, by the media controller, a Tag ID of the data transfer request based on the host device ID and the data transfer request ID;

generating, by the media controller, a starting memory address of a tag table based on the Tag ID of the data transfer request;

reading a tag count value from the starting memory address of the tag table;

if the tag count value reaches a threshold;

determining absence of a tag overlap; and

adding the Tag ID of the data transfer request to the tag table at the starting memory address.

23. A non-transitory machine-readable storage medium, having encoded thereon program code, wherein, when the program code is executed by a machine, the machine implements a method of deallocating resources of a media controller after data transfers are completed by the media controller, the method comprising:

providing, to a tag manager of the media controller, a Tag ID corresponding to a complete data transfer;

generating, by the tag manager, a starting memory address of a tag table based on the Tag ID of the data transfer;

reading a tag count value from the starting memory address of the tag table;

if the tag count value has not reached a threshold;

reading a Tag ID at the starting memory address;

if the read Tag ID and the Tag ID of the completed data transfer are substantially equivalent;

setting a status of the starting memory address to invalid;

otherwise, if the read Tag ID and the Tag ID of the completed data transfer are not substantially equivalent;

hashing the read Tag ID into a hashed read Tag ID;

if the hashed read Tag ID is substantially equivalent to the starting search address;

decrementing the tag count of the starting search address;

incrementing the starting search address to a next address; and

reading the tag count value stored at the next address of the tag table;

if the hashed read Tag ID is not substantially equivalent to the starting search address;

incrementing the starting search address; and

reading the tag count value stored at the next address of the tag table.