Method and apparatus for high throughput short packet transfers with minimum memory footprint

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to a universal serial bus (USB) environment, and more particularly to a method and apparatus to improve an enhanced host controller interface (EHCI) performance for USB devices.

2. Description of the Related Art

In many of today's processors and systems, such as personal computer (PC) systems, there exist USB ports for connecting various USB devices. Many USB devices are frequently used by PC users. For example, USB devices may be printers, compact disc read-only memory (CD-ROM) drives, CD-ROM writer (CDRW) drives, digital versatile disc (DVD) drives, cameras, pointing devices (e.g., computer mouse), keyboards, joy-sticks, hard-drives, speakers, etc.

Different standards of USB technology have different bandwidths. For example, Universal Serial Bus Specification, revision 1.1, Sep. 23, 1998 (USB 1.1) devices are capable of operating at 12 Mbits/second (Mbps), and Universal Serial Bus Specification, revision 2.0, Apr. 27, 2000 (USB 2.0; also known as high-speed USB) devices are capable of operating at 480 Mbps. USB 2.0 defines a multiple speed-signaling environment where a single high-speed bus may support one or more USB 1.1 classic busses through a USB 2.0 hub (Transaction Translator). In this environment, system software (the Host Controller Driver) must allocate and manage the bandwidth of USB 1.1 classic busses.

The Enhanced Host Controller Interface (EHCI) specification for a Universal Serial Bus, revision 0.95, Nov. 10, 2000 describes the register-level interface for a host controller (HC) for USB 2.0. The USB 2.0 HC is a bus master on the peripheral component interconnect (PCI) bus. The HC independently traverses linked memory structures created and maintained by the HC driver to initiate transactions on the USB. In the USB EHCI specification, two data structures known as the queue head (QH) and the queue element transfer descriptor (qTD) are defined.

The QH contains all of the endpoint specific information required. The QH also contains links to a list of qTDs. A qTD represents all or part of a buffer passed to the HC driver from a higher level driver, or user level application. The QH contains all of the endpoint specific information required. The QH also contains links to a list of qTDs. A qTD represents all or part of a buffer passed to the HC driver from a higher level driver, or user level application.

The qTD data structure is only used with a QH. The qTD is used for one or more USB transactions. A qTD can, at most, transfer 20,480 (5*4,096) bytes. When the HC completes execution of a qTD, it will follow the next-pointer. When a USB device returns less data than requested by the qTD, a short packet condition results. When the HC receives a short packet, the HC follows the alternate-pointer.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is illustrated by way of example and not by way of limitation in the figures of the accompanying drawings in which like references indicate similar elements. It should be noted that references to “an” or “one” embodiment in this disclosure are not necessarily to the same embodiment, and such references mean at least one.

FIG. 1 illustrates a structure of a queue head.

FIG. 2 illustrates a structure of a queue element transfer descriptor (qTD).

FIG. 3 illustrates a Universal Serial Bus (USB) 2.0 system.

FIG. 4 illustrates an enhanced host controller interface (EHCI).

FIG. 5 illustrates a first method for organizing qTDs.

FIG. 6 illustrates a second method for organizing qTDs.

FIG. 7 illustrates an embodiment of the invention that organizes qTDs to improve throughput in the presence of short packets.

FIG. 8A illustrates a block diagram of a process of an embodiment of the invention that organizes qTDs to improve throughput in the presence of short packets when buffer contents are less than or equal to the storage capacity of qTDs in a bank.

FIG. 8B illustrates a block diagram of a process of an embodiment of the invention that organizes qTDs to improve throughput in the presence of short packets when buffer contents are greater than the storage capacity of qTDs in a bank (continued from FIG. <b>8</b>A).

DETAILED DESCRIPTION OF THE INVENTION

The invention generally relates to a method to reducing memory consumption of universal serial bus (USB) data structures and improving throughput of USB transactions. Referring to the figures, exemplary embodiments of the invention will now be described. The exemplary embodiments are provided to illustrate the invention and should not be construed as limiting the scope of the invention.

FIG. 1 illustrates a typical structure layout of a queue head (QH). QH horizontal link pointer (QHLP) <b>110</b> comprises four fields. QHLP field <b>111</b> contains the address of the next data object to be processed in the horizontal list and corresponds to memory address signals [<b>31</b>:<b>5</b>], respectively. Field <b>112</b> is reserved, and bits <b>4</b>:<b>3</b> must be written as 0s. Field <b>113</b> comprising bits <b>2</b>:<b>1</b>, indicates to the hardware whether the item referenced by the link pointer is a isochronous transaction descriptor (iTD), split transaction isochronous transaction descriptor (siTD) or a QH. Field <b>113</b> allows the USB host controller to perform the proper type of processing on the item after it is fetched. Field <b>114</b>, bit <b>0</b>, is the terminate field. If the QH is in the context of the periodic list, a set (“1”) bit in field <b>114</b> indicates to the HC that this is the end of the periodic list. This bit, however, is ignored by the HC when the QH is in the asynchronous schedule.

Field <b>120</b> illustrates QH DWord<b>1</b>, and field <b>130</b> illustrates end point characteristics comprising QH DWord<b>2</b>. Field <b>121</b> is the not acknowledged or negative acknowledged (Nak) count re-load field. Field <b>121</b> contains a value, which is used by the HC to reload Nak counter field. Field <b>133</b> illustrates a control end-point flag. Field <b>123</b> represents the maximum packet length. The maximum packet length directly corresponds to the maximum packet size of the associated endpoint. The maximum value of field <b>123</b> is 0×400 (1024).

Field <b>124</b> illustrates head of reclamation list flag. Field <b>124</b> is set by system software to mark a QH as being the head of the reclamation list. Field <b>125</b> illustrates data toggle control. Field <b>125</b> specifies where the HC should get the initial data toggle on an overlay transition. Field <b>126</b> illustrates endpoint speed. Field <b>126</b> is the speed of the associated endpoint. Field <b>127</b> illustrates the endpoint number. Field <b>127</b> selects the particular endpoint number on the device serving as the data source or sink. Field <b>128</b> is a reserved bit. Field <b>129</b> illustrates the device address. Field <b>129</b> selects the specific device serving as the data source or sink.

Field <b>131</b> illustrates the high-bandwidth pipe multiplier. Field <b>131</b> is a multiplier used to key the HC as the number of successive packets the HC may submit to the endpoint in the current execution. The HC makes the simplified assumption that software properly initializes this field. Field <b>132</b> illustrates the port number. Field <b>132</b> is ignored by the HC unless field <b>126</b> indicates a full-speed or low-speed device. The value is the port number identifier on the USB 2.0 hub, below which the full- or low-speed device associated with this endpoint is attached. This information is used in the split-transaction protocol.

Field <b>133</b> illustrates the hub address. Field <b>133</b> is ignored by the HC unless field <b>126</b> indicates a full- or low-speed device. The value is the USB device address of the USB 2.0 hub below which the full- or low-speed device associated with this endpoint is attached. Field <b>134</b> illustrates the split-completion mask. Field <b>134</b> is ignored by the HC unless field <b>126</b> indicates the device is a low- or full-speed device and this QH is in the periodic list. Field <b>134</b> is used to determine during which micro-frames the HC should execute a complete-split transaction. When the criteria for using this field are met, a zero value in this field has undefined behavior. Field <b>135</b> illustrates the interrupt schedule mask. Field <b>135</b> is used for all endpoint speeds. When the QH is on the asynchronous schedule, software should set this field to a zero (“0”). A non-zero value in this field indicates an interrupt endpoint.

Field <b>140</b> illustrates the current queue transaction descriptor link pointer. Field <b>140</b> contains the address of the current transaction being processed in this queue and corresponds to memory address signals [<b>31</b>:<b>5</b>], respectively. Field <b>141</b> is reserved for future use. Field <b>142</b> illustrates the next queue element transfer descriptor (qTD) pointer. Field <b>143</b> illustrates the alternate next qTD pointer. Fields <b>150</b> through <b>154</b> illustrate buffer pointer pages 0-4, respectively.

FIG. 2 illustrates the structure of a qTD. As can be seen in FIG. 2, a qTD contains two structure pointers (next qTD pointer <b>210</b> and alternate next qTD pointer <b>220</b>) which are used for queue advancement, a data word (Dword) of transfer state (<b>230</b>), and a five-element array of data buffer pointers (<b>240</b>). The complete structure of qTD <b>200</b> consists of 32 bytes. Next qTD pointer <b>210</b> and alternate next qTD pointer <b>220</b> point to the next qTD to execute. Next qTD pointer <b>210</b> contains the physical memory address of the next qTD to be processed.

Bit <b>0</b> in qTD pointer <b>210</b> is the terminate field. If bit <b>0</b> of qTD pointer <b>210</b> is set (“1”), bit <b>0</b> indicates the pointer is invalid. If bit <b>0</b> of qTD pointer <b>210</b> is not set (“0”), the pointer is valid. Alternate qTD pointer <b>220</b> contains the physical memory address of the next qTD to be processed in the event that the current qTD execution encounters a short packet. Like qTD pointer <b>210</b>, alternate qTD pointer <b>220</b> has bit <b>0</b> as a terminate bit. The third Dword <b>230</b>, known as the qTD token, contains most of the information the HC needs to execute a USB transaction.

Bit <b>0</b> is data toggle sequence bit <b>231</b>. The use of data toggle sequence bit <b>231</b> depends on the setting of the data toggle control bit (illustrated as <b>125</b> in FIG. 1) in the QH. Total bytes to transfer <b>232</b> specifies the total number of bytes to be moved with the particular transfer descriptor. Total bytes to transfer <b>232</b> is decremented by the amount of bytes actually moved during the transaction. If the interrupt on complete (IOC) <b>233</b> bit is set (“1”), then when the particular qTD execution is completed, the HC should issue an interrupt at the next interrupt threshold. Current page <b>234</b> is used as an index into the qTD buffer pointer list.

Error counter <b>235</b> is a 2-bit down counter that keeps track of the number of consecutive errors detected while executing the particular qTD. Program identification (PID) code <b>236</b> is an encoding of the token that should be used for transactions associated with the particular transfer descriptor. Status <b>237</b> is used by the HC to communicate individual command execution states back to the HC driver. Status <b>237</b> contains the status of the last transaction performed on the particular qTD. Each buffer pointer in buffer pointer list <b>240</b> contains a 4 K page aligned, physical memory address. The lower bits (<b>0</b>-<b>12</b>) are reserved in all pointers except the first one (i.e., page 0).

A USB host system is composed of a number of hardware and software layers. FIG. 3 illustrates a block diagram of building block layers in a USB 2.0 system. System <b>300</b> is comprised of client driver software <b>310</b>, universal serial bus driver (USBD) <b>320</b>, companion host controller (HC) driver <b>330</b>, companion HC <b>340</b>, enhanced host controller driver (EHCD) <b>350</b>, universal host controller (UHC) <b>360</b> and USB device <b>370</b>. In system <b>300</b>, system software consists of client driver software <b>310</b>, USBD <b>320</b>, companion HC driver <b>330</b>, and EHCD <b>350</b>. In system <b>300</b> the hardware comprises companion HC <b>340</b>, UHC <b>360</b>, and USB device <b>370</b>.

Client driver software <b>310</b> typically executes on the host personal computer (PC) corresponding to a particular USB device. Client driver software <b>310</b> is typically part of the operating system (OS) or may be provided with a USB device. USBD <b>320</b> is a system bus driver that abstracts the details of the particular HC driver for a particular OS. Companion HC Driver <b>330</b> is typically a UHC interface (UHCI) driver or an open HCI (OHCI) driver for USB. The HC driver provides a software layer between specific HC hardware and the USBD. Companion HC <b>340</b>, is typically UHCI or OHCI standards. Companion HC <b>340</b> is the specific hardware implementation of the HC. There is one HC specification for USB 2.0 functionality, and two specifications for full- and low-speed HCs.

FIG. 4 illustrates the general architecture of enhanced host controller interface (EHCI) <b>400</b>. EHCI <b>400</b> comprises three interface spaces: peripheral component interconnect (PCI) configuration <b>410</b>, register <b>420</b>, and schedule interface <b>430</b>. PCI configuration <b>410</b> includes PCI registers used for system component enumeration and PCI power management. PCI configuration registers in PCI configuration <b>410</b> comprise PCI class code <b>411</b>, USB base address <b>412</b>, and PCI power management interface <b>413</b>. Register <b>420</b> comprises memory based input/output (I/O) registers. Memory based I/O registers are comprised of capability registers <b>421</b> and operational registers <b>422</b>. Register <b>420</b> must be implemented as memory-mapped I/O. Schedule interface <b>430</b> is typically memory allocated and managed by the HC driver for the periodic and asynchronous schedules. EHCI <b>400</b> allows software to enable or disable each schedule.

There are typically two (2) methods for organizing qTDs. FIG. 5 illustrates the first method. In the method illustrated in FIG. 5, all of the qTDs <b>510</b> necessary to represent at least two buffers are created. Each alternate-pointer of buffer N <b>520</b> points to the first qTD <b>510</b> of buffer N+1 <b>530</b>. This method, however, requires a large memory footprint to initialize all of the qTDs <b>510</b> required to represent both buffers.

FIG. 6 illustrates the second method. The second method initializes all the alternate-pointers of the qTDs <b>510</b> to a “dummy” qTD. When a short packet is received, the HC will vector to dummy qTD <b>620</b>. Software then detects the short packet and re-initializes qTDs <b>610</b>. The software can only detect a short packet condition when the hardware asserts an interrupt. Since interrupts occur at fixed intervals, the time after the short packet is received and before the interrupt is serviced is unused. Therefore, this second approach, while having a small memory footprint, has low throughput.

FIG. 7 illustrates a block diagram of an embodiment of the invention comprising N small banks of qTDs <b>710</b> for each buffer <b>720</b> posted to the HC driver. In this embodiment of the invention, N may be a small number such as “3” (three). One should note that N can be other numbers besides 3. Each bank of qTDs <b>710</b> is circularly linked. Next-pointer <b>730</b> in each qTD <b>705</b> points to the next qTD <b>705</b> in qTD bank <b>710</b>. The last next-pointer <b>730</b> in a qTD <b>705</b> points to the first qTD <b>705</b> in qTD bank <b>710</b>. Alternate-pointer <b>740</b> of each qTD <b>705</b> in qTD bank <b>710</b> points to the first qTD <b>705</b> in the next bank of qTDs (representing the next sequential buffer posted to the HC driver). In this embodiment of the invention, as the HC consumes data from qTDs <b>705</b> and executes transactions on the USB, the HC driver continually re-initializes and re-uses the statically defined qTDs corresponding to the buffer currently active.

When the HC driver initializes the last qTD's buffer, the HC driver sets the next-pointer in the last initialized qTD and begins servicing the qTDs in buffer N+1. If any of qTDs <b>705</b> in buffer N <b>720</b> terminate with a short packet, the HC will follow the alternate-pointer to the first qTD of buffer N+1. The same pattern continues for N buffers. This embodiment of the invention can be incorporated into a USB HC (e.g., USB 2.0 enhanced host controller) coupled with a USB HC driver (e.g., an enhanced host controller driver). This embodiment can also be incorporated into a USB system, such as USB 2.0 system <b>300</b> illustrated in FIG. <b>3</b>.

In one embodiment of the invention, for buffer contents that are smaller than the maximum contents that can fit into N small banks of qTDs <b>710</b> (e.g., N=3), the HC reads the first qTD for the first buffer. If the execution of the first qTD completes normally, the HC follows the next pointer and executes the transactions contained in the second qTD. Since the last qTD in the transfer has the next pointer pointing to the next buffer, the HC will vector to the next buffer when the execution of the qTD completes. If the buffer returns a short packet, the HC follows the alternate pointer to execute the next buffer.

In one embodiment of the invention, for buffer contents larger than the maximum contents that can fit into N small banks of qTDs <b>710</b> (e.g., N=3), The HC first reads the first qTD in the first buffer. After the first qTD completes execution, the HC asserts an interrupt to the HC driver. The HC then begins executing the transactions contained in the second qTD. The HC driver simultaneously clears out status in the first qTD and re-initializes it for the next section of the buffer (i.e., it would be the fourth qTD's worth of information). The HC driver will continue initializing/re-initializing and reusing the three (“3”) qTDs (where N=3) until either the buffer “shorts out,” and the HC vectors off to the next buffer via the alternate pointer, or until the transfer completes normally (in which case the HC driver has modified the next pointer to point to the next bank, not to the next qTD in the same bank).

FIG. 8A illustrates a block diagram of a process of an embodiment of the invention that organizes qTDs to improve throughput in the presence of short packets when buffer contents are less than or equal to the storage capacity of qTDs in a bank. Process <b>800</b> begins with block <b>810</b> where a plurality of buffers posted to the HC driver. Block <b>820</b> then creates a bank of N qTDs for each buffer posted (N is a number, e.g., 3). Block <b>825</b> determines whether the size of the contents of the buffer is less than or equal to the maximum storage capacity of the qTDs in the bank. If block <b>825</b> does determine that the size of the contents of the buffer is less than or equal to the maximum storage capacity of the qTDs in the bank, process <b>800</b> continues with block <b>830</b>.

Block <b>830</b> reads the first qTD for the associated buffer. Block <b>835</b> executes the qTD. Process <b>800</b> continues with block <b>840</b> that determines whether execution of the qTD completed normally (i.e., not a short packet condition). If block <b>840</b> determines that execution of the qTD completed normally, process <b>800</b> continues with block <b>850</b>. Block <b>850</b> determines whether the current qTD is the last qTD in the bank. If block <b>850</b> determines that the qTD recently executed is not the last qTD in the bank, process <b>800</b> continues with block <b>860</b>. Block <b>860</b> follows the next qTD pointer to the next qTD in the same bank. Block <b>865</b> then executes the next qTD that is pointed to by the next pointer. Process <b>800</b> then continues with block <b>840</b>.

If block <b>850</b> determines that the qTD recently executed is the last qTD in the bank, process <b>800</b> continues with block <b>855</b>. Block <b>855</b> follows the next qTD pointer to the next qTD in the same bank. Process <b>800</b> then continues with block <b>825</b>. One should note that the next buffer that is vectored to increments up to the last buffer. After the last buffer is vectored to, the next buffer to be vectored to would be the first buffer. For example, in a three (“3”) buffer configuration, after buffer “3,” buffer “1” is vectored back to.

If block <b>840</b> determines that the execution of the qTD did not complete normally, i.e. a short packet condition, process <b>800</b> continues with block <b>845</b>. Block <b>845</b> follows the alternate pointer to the next buffer. Process <b>800</b> then continues with block <b>825</b>. If block <b>825</b> determines that the size of the contents of the buffer is greater than the maximum storage capacity of the qTDs in the bank, process <b>800</b> continues with block <b>870</b> (illustrated in FIG. <b>8</b>B).

Block <b>870</b> reads the first qTD for the respective buffer. Block <b>871</b> then executes the first qTD. Block <b>872</b> determines whether the execution of the contents of the buffer completed normally (not “shorted out” by a short packet condition). If block <b>872</b> determines that the execution of the contents of the buffer completed normally (i.e., all contents executed), then process <b>800</b> continues with block <b>890</b>. Block <b>890</b> follows the next pointer to the next bank. The next pointer to the next bank increments up until the last bank, then the next pointer points to the first bank.

If block <b>872</b> determines that the execution of the buffer contents are not completed, process <b>800</b> continues with block <b>880</b>. Block <b>880</b> determines whether execution of the current qTD resulted in a short packet condition. If block <b>880</b> determines that the execution of the current qTD resulted in a short packet condition, then process <b>800</b> continues with block <b>881</b>. Block <b>881</b> follows the alternate pointer to the next buffer. Process <b>800</b> then continues with block <b>825</b>.

If block <b>880</b> determines that the execution of the current qTD did not result in a short packet condition, process <b>800</b> continues with block <b>873</b>. Block <b>873</b> asserts an interrupt to the HC driver. In block <b>874</b>, the HC driver clears the status of the qTD while simultaneously re-initializing the qTD. Process <b>800</b> continues with block <b>875</b> that determines whether the current qTD is the last qTD in the bank. If block <b>875</b> determines that the current qTD is the last qTD in the bank, process <b>800</b> continues with block <b>882</b>. Block <b>882</b> modifies the next pointer to point to the first qTD in the next buffer. Process <b>800</b> then continues with block <b>825</b>.

If block <b>875</b> determines that the current qTD is not the last qTD in the bank, process <b>800</b> continues with block <b>876</b>. Block <b>876</b> follows the next qTD pointer to the next qTD in the same bank. Block <b>877</b> then executes the qTD pointed to by the next pointer. Process <b>800</b> continues with block <b>872</b>.

For input devices, such as Ethernet controllers, hard drives, compact disk read-only-memory (CD-ROM) drives, CD-ROM Writer (CDRW) drives, etc., it is impossible for the host to know in advance how much data the device will return for any given transaction. For these devices, the HC initializes qTDs to account for the largest possible transaction that can be received from the device. The device then typically returns short packets to the host. By implementing the presented embodiments of the invention, efficiency of the HC driver is improved, in terms of memory footprint and bus utilization, in the presence of input devices, such as discussed above.

The above embodiments can also be stored on a device or machine-readable medium and be read by a machine to perform instructions. The machine-readable medium includes any mechanism that provides (i.e., stores and/or transmits) information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.). The device or machine-readable medium may include a solid state memory device and/or a rotating magnetic or optical disk. The device or machine-readable medium may be distributed when partitions of instructions have been separated into different machines, such as across an interconnection of computers.

While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications may occur to those ordinarily skilled in the art.