Setting up EHCI queue heads

[Korona]

You really want one QH for each endpoint. Sharing QHs across multiple endpoints is more complicated than it is worthwhile and if you try to use more than one QH per endpoint you'll run into synchronization issues at the endpoint.

For the periodic schedule you want to link them in the way BenLunt described. Each vertex in his tree represents multiple QHs. Note that there are 128 vertices for 128 frame periods. However that does not mean that at most 128 endpoints are supported for this period as you can schedule multiple 128 frame period endpoints in the same frame. Note that you have to calculate the bandwidth requirements of each endpoint yourself. Not every possible schedule respects the USB bandwidth requirements; if you do not calculate those requirements you'll construct invalid schedules.

The asynchronous schedule is round-robin: At each frame the HCD executes as many transactions as possible until the next SOF. If a transaction NAKs the HCD just continues with the next one. The HCD remembers its position in the asynchronous schedule across (micro-)frame boundaries. It uses the "Head of Reclamation List" bit to detect empty schedules.

EDIT:

Also note that I started the frame numbers from 1, not zero. This is to show you that 1 is divisible by 1, so use QH1; 4 is divisible by 4, so use QH4, etc. Frame 6, (the 6th frame, or frame 5 if zero based) is only divisible by 2, so use QH2. Find the most significant 2 based divisor. You see the math?

Also note that QH1 is listed numerous times (as with others). There is only one Queue Head for QH1 in your schedule. Not 16 as shown above. The arrows point to the single queue head in the schedule of queue heads.

There is only a single QH1. There are two QH2, 4 QH4 and so on. The k-th QH_m is linked in frame i if i = k mod m. There are QHs for each period in every frame. Your image (with all QH_m identified) does not depict 32 frames but only part of a single frame (i.e. frame 32).

The real frame list is structured like this:

Code: Select all

Frame    0:    0th QH1024 ->   0th QH512 -> ... -> 0th QH4 -> 0th QH2 -> 0th QH1
Frame    1:    1st QH1024 ->   1th QH512 -> ... -> 1st QH4 -> 1st QH2 -> 0th QH1
Frame    2:    2nd QH1024 ->   2nd QH512 -> ... -> 2nd OH4 -> 0th QH2 -> 0th QH1
Frame    3:    3rd QH1024 ->   3rd QH512 -> ... -> 3rd OH4 -> 1st QH2 -> 0th QH1
Frame    4:    4th QH1024 ->   4th QH512 -> ... -> 0th OH4 -> 0th QH2 -> 0th QH1
...
Frame  512:  512th QH1024 ->   0th QH512 -> ... -> 0th OH4 -> 0th QH2 -> 0th QH1
...
Frame 1023: 1023th QH1024 -> 511th QH512 -> ... -> 3rd OH4 -> 1st QH2 -> 0th QH1

Note that the outgoing links are consistent (i.e. this is a valid EHCI schedule). And note again that those are vertices (possibly denoting multiple QHs) and not single QHs.

[Korona]

EDIT: Ah, I got ninja'd by BenLunt deleting his post. BenLunt stated that while the schedule I posted above is a better solution, it is harder to understand and probably overkill if you're new to USB.

That's fair. In this case let me suggest an even simpler 2-layer schedule:

Code: Select all

Frame 0: QH1
Frame 1: QH2 -> QH1
Frame 2: QH4 -> QH1
Frame 3: QH2 -> QH1
Frame 4: QH8 -> QH1
Frame 5: QH2 -> QH1
Frame 6: QH4 -> QH1
...

Basically it is produced by the following algorithm: Let m iterate through all possible periods (i.e. powers of 2) from 2 to 1024. Fill every m-th empty slot (except for the first one) of the schedule with QH_m. In other words: Set slot 0 to QH1 and slot i to QH_2^(ffs(i) + 1) where ffs(i) denotes the index of the lowest set bit in i. This is easily computed using bit arithmetic, the x86 bsf instruction or the GCC __builtin_ffs.

If you order those schedules by number of supportable endpoints then
BenLunt's schedule (least devices) < korona's 2-layer schedule < korona's multi-layer schedule (most devices)

That is because in BenLunt's schedule all endpoints share bandwidth. This is not the case in my schedules. The multi-layer schedule is superior to the two layer schedule because it allows different m-period endpoints to be scheduled in different frames while the two-layer schedule runs all m-period endpoints in the same frame.

But of course if you're interested in simplicity it's probably
korona's 2-layer schedule (most simple) > BenLunt's schedule > korona's multi-layer schedule (least simple)

[BenLunt]

There is only a single QH1. There are two QH2, 4 QH4 and so on. The k-th QH_m is linked in frame i if i = k mod m. There are QHs for each period in every frame. Your image (with all QH_m identified) does not depict 32 frames but only part of a single frame (i.e. frame 32).
Note that the outgoing links are consistent (i.e. this is a valid EHCI schedule). And note again that those are vertices (possibly denoting multiple QHs) and not single QHs.

Please define "valid EHCI schedule". Mine is almost as your definition, though only one QH per number. Let's look at it again.



There is only 1 (one) Queue head for each value 1 through 1024, though I am only showing the first 32.

Code: Select all

Frame    0: ->  QH1
Frame    1: ->  QH2 ->  QH1
Frame    2: ->  QH1
Frame    3: ->  QH4 ->  QH2 ->  QH1
Frame    4: ->  QH1
Frame    5: ->  QH2 ->  QH1
Frame    6: ->  QH1
Frame    7: ->  QH8 -> QH4 -> QH2 ->  QH1
... repeat frame 0 -> frame 6 ....
Frame   15: ->  QH16 -> QH8 -> QH4 -> QH2 ->  QH1
... repeat frame 0 -> frame 14 ....
Frame   31: ->  QH32 -> QH16 -> QH8 -> QH4 -> QH2 ->  QH1
... repeat frame 0 -> frame 30
... all the way up to frame 1023
Frame 1023: ->  QH1024 -> QH512 -> QH128 -> QH64 -> QH32 -> QH16 -> QH8 -> QH4 -> QH2 ->  QH1

Knowing that there is only 1 (one) of each QHx, where x is 1,2,4,8,16,32,64,128,512,1024, each frame ends with QH1, the only QH1. Now, knowing this, QH1 will be executed every frame. QH2 will be executed every other frame. QH4 will be executed every fourth frame, etc., while QH1024 will be executed only once per "revolution", once per 1,024ms, roughly 1 second. You can have one of these periodical Queue lists for each endpoint only having a total of 10 queues per endpoint (for the Periodical list anyway). Much simpler to manage, much less memory.

Granted, you do have to have a bandwidth management system to link in all endpoint queue lists, but this is a different subject.

Also, sorry for the deletion of the post. I decided to comment differently, and yes, I am going for simplicity. Let the reader walk before he/she can run.

Thanks,
Ben

[BenLunt]

EDIT: Ah, I got ninja'd by BenLunt deleting his post. BenLunt stated that while the schedule I posted above is a better solution, it is harder to understand and probably overkill if you're new to USB.

Sorry about that. Here is what I had previously posted and decided to withdraw to post what is above:

Hi Korona,

Thanks for your comments, which show another way, and not denying that it is probably a better solution. However, my intention is to show a newbie how to start with a lawnmower engine, working his/her way up to a four-banger, then a V8, to possibly a V12 with two super chargers, rather than going right to the V12. Let him walk before he can run.

Thanks,
Ben

[Korona]

By valid EHCI schedule I mean a graph that has only one outgoing edge per vertex. If you draw random graphs it's easy to draw things that EHCI cannot actually process . Your schedule is valid. However it can be improved both if you consider simplicity and if you consider number of supported endpoints (see my post above).

[mariuszp]

Now a simple question. What about the STATUS transaction? Does it require a TD, or is the STATUS transaction handled by the controller and the results placed in the "status" field of the TD/QH?

So for example, with SET_ADDRESS, I only need one TD for the SETUP packet, and then I just look at the status bits of the QH?

[Korona]

You still need a TD with zero total bytes to receive the status stage of a control transaction. The status fields of the setup TD will only indicate the results of the setup transaction. An endpoint might (actually should always) ACK the setup transaction but STALL the status transaction (or any data transaction that take place between those two stages). STALL in the status stage will indicate an error with the control transaction (e.g. the device does not support the request that you're trying to issue or you got the arguments wrong).

[BenLunt]

By valid EHCI schedule I mean a graph that has only one outgoing edge per vertex. If you draw random graphs it's easy to draw things that EHCI cannot actually process . Your schedule is valid. However it can be improved both if you consider simplicity and if you consider number of supported endpoints (see my post above).

Agreed. Again, I appreciate you comments. It is always nice to see another point of view on the subject.

Now a simple question. What about the STATUS transaction? Does it require a TD, or is the STATUS transaction handled by the controller and the results placed in the "status" field of the TD/QH?

So for example, with SET_ADDRESS, I only need one TD for the SETUP packet, and then I just look at the status bits of the QH?

As Korona stated, you need a STATUS TD, but I will put it another way. It is your job to send the STATUS packet which has two purposes, one each, depending on the direction of the transaction.

If you are sending data, even zero bytes as with the SET_ADDRESS command, you send a STATUS packet to see if the packet NAK's, STALLS, or ACK's. This is the device telling you that it received the command, either in error (STALL or NAK) or in good standing (ACK).

If you are receiving data, you send the STATUS packet telling the device that you received all expected data.

As Korona put it "but STALL the status transaction (or any data transaction that take place between those two stages)". With this in mind, there are many things to remember about USB devices. The most important quirk I have found is that no device is 100% USB compatible. For example, some devices will stall if you request more than the first 8 bytes of the Device Descriptor when first enumerating a device, just after a reset. Some devices will stall if you don't request 64 bytes (High Speed devices on low-/full-speed controllers, but you don't know it is a high-speed device yet).

Ben

[mariuszp]

And how then do I send this "STATUS" packet? In the EHCI spec, it specifies that the transfer descriptor types can only be IN, OUT or SETUP...

EDIT: And I am still confused. If a queue head is empty, what value should "current TD" and other fields have in that case?

[BenLunt]

And how then do I send this "STATUS" packet? In the EHCI spec, it specifies that the transfer descriptor types can only be IN, OUT or SETUP...

The Status packet is an empty (bytes to transfer = 0) TD and is the opposite of what you sent before. For example, if you are doing a Control Transfer OUT, you do an IN Status packet. If you are doing a Control Transfer IN, you do an OUT Status packet. Remember that the DATA0/1 bit is always set for the STATUS TD, no matter if the last one was set or clear.

EDIT: And I am still confused. If a queue head is empty, what value should "current TD" and other fields have in that case?

The "current TD" is written to by the controller and is set to the current TD being processed. If you have an "empty" QH, then no TD is being processed, so write a zero to this field. The Next TD field has bit 0 as the "T" bit, terminating bit. If this bit is set, the rest of the field is undefined. Therefore, set this bit for an empty QH.

DWORDS 0, 1, and 2 are read-only by the controller. You set them and they will be preserved by the controller. DWORDS 3 and on are writeable by the controller and have the (very close) same format as a TD. DWORD 4 is the next TD link. If you have a TD for this QH, it is the address of this TD. If not, set bit 0. To be safe, set bit 0 of the Alt TD pointer too.

Remember that an Async list should never have the "T" bit set for Horz Ptr, it should always point back to the beginning with one of the QH's marked as "Head". The Periodic list will have the last QH marked with a "T" bit set in the Horz Ptr (unless you move on to a reclaim list).

So, for an empty QH, meaning you only link to this QH and then link to another QH, zero the QH being sure to set bit 0 in DWORD4 (and 5).

The EHCI 1.0 specifications show this in section 3.6.

Ben
http://www.fysnet.net/the_universal_serial_bus.htm

[mariuszp]

That makes sense. And as yuo stated, if there is a companion controller then EHCI only handles high-speed transactions. Does that mean that the default control pipe should be high-speed when using EHCI? Or do all ports need to be routed to OHCI/UHCI and initialized there before EHCI can be used to talk to the device?

[Korona]

Yes, all default contol pipes for devices attached to the root hub should be high-speed (and are fixed to 64 byte max packet size). Devices are always attached to the EHCI first and only attached to the companion after you explicitly release them (because EHCI cannot handle them). Take a look at the CONFIGFLAG register and at the "Port Owner" bit in the PORTSC register. The mechanism is described in section 4.2 of the EHCI spec.

Note that EHCI can support low-/full-speed devices on hubs other than the root hub. However this requires split transactions and is probably something you only want to implement after everything else works.

[mariuszp]

I now got the idea but it doesn't seem to work yet. I have the following function for creating queue heads:

Code: Select all

static EhciQueue* ehciCreateQueue(uint8_t devaddr, uint8_t endpoint, int speed, size_t maxPacketLen, uint32_t flags)
{
	EhciQueue *queue = NEW(EhciQueue);
	queue->next = NULL;
	
	if (dmaCreateBuffer(&queue->dmabuf, sizeof(EhciQH), DMA_32BIT) != 0)
	{
		kfree(queue);
		return NULL;
	};
	
	queue->qh = (EhciQH*) dmaGetPtr(&queue->dmabuf);
	queue->physQH = (uint32_t) dmaGetPhys(&queue->dmabuf);
	
	// zero out the queue head
	memset(queue->qh, 0, sizeof(EhciQH));
	
	// initialize "horptr" to point to nothing, just in case
	queue->qh->horptr = EHCI_HORPTR_TERM;
	queue->qh->endpointInfo = devaddr		/* low 7 bits = device address */
							/* bit 7 = invalidate bit (initialize to 0) */
		| (endpoint << 8)			/* bits 11:8 = endpoint number */
		| (speed << 12)				/* bits 13:12 = endpoint speed */
		| (maxPacketLen << 16)			/* bits 26:16 = maximum packet length */
		| flags;				/* any extra flags */
	queue->qh->endpointCaps = (1 << 30);		// TODO: hubs and stuff
	
	// no transfer in progress
	queue->qh->overlay.horptr = EHCI_HORPTR_TERM;
	queue->qh->overlay.altHorptr = EHCI_HORPTR_TERM;
	
	return queue;
};

The horizontal pointer (horptr) isn't set by ehciCreateQueue() because i'll have another function, ehciAddQueue(), which adds it to a list (async or periodic).

And I create the queue for the default address and default endpoint, so that I may send SET_ADDRESS requests (it is also the head of the list, so I set the H bit):

Code: Select all

qAsync = ehciCreateQueue(0, 0, EHCI_SPEED_HIGH, 64, EHCI_QH_HEAD);

And I set up the horizontal pointer and the asynchronous schedule:

Code: Select all

		qAsync->qh->horptr = qAsync->physQH | EHCI_HORPTR_QH;
		qAsync->next = qAsync;

		ehciRegs->asyncListAddr = qAsync->physQH;
		ehciRegs->usbcmd |= EHCI_USBCMD_ASYNC_ENABLE;
		while ((ehciRegs->usbsts & EHCI_USBSTS_ASYNC) == 0) __sync_synchronize();	// wait until enabled

Then I have the following structure that I want to allocate in a DMA buffer (which is basically physically contiguous memory):

Code: Select all

typedef struct
{
	EhciTD				tdSetup;
	EhciTD				tdData;
	EhciTD				tdStatus;
	USBSetupPacket			setupData;
} EhciSetAddr;

Which I then use as follows to set up a SET_ADDRESS request (right after restting the port):

Code: Select all

						sleep(100);
						ehciRegs->ports[i] |= EHCI_PORT_RESET;
						sleep(50);
						ehciRegs->ports[i] &= ~EHCI_PORT_RESET;
						
						// allocate an address for the new device
						usb_addr_t addr = usbAllocAddr();
						if (addr == 0)
						{
							kprintf_debug("ehci: error: out of USB addresses\n");
							continue;
						};
						
						// set up the transaction
						uint32_t transPhys = dmaGetPhys(&dmaSetAddr);
						memset(reqSetAddr, 0, sizeof(EhciSetAddr));
						reqSetAddr->tdSetup.horptr = transPhys + offsetof(EhciSetAddr, tdData);
						reqSetAddr->tdSetup.altHorptr = EHCI_HORPTR_TERM;
						reqSetAddr->tdSetup.token = 0
							| (8 << 16)			/* 8 bytes to transfer */
							| (EHCI_PID_SETUP << 8)		/* SETUP packet */
							| EHCI_TD_ACTIVE;
						reqSetAddr->tdSetup.bufs[0] = transPhys + offsetof(EhciSetAddr, setupData);
						
						reqSetAddr->tdData.horptr = transPhys + offsetof(EhciSetAddr, tdStatus);
						reqSetAddr->tdData.altHorptr = EHCI_HORPTR_TERM;
						reqSetAddr->tdData.token = 0
							| (EHCI_PID_OUT << 8)		/* OUT packet */
							| EHCI_TD_ACTIVE;
						
						reqSetAddr->tdStatus.horptr = EHCI_HORPTR_TERM;
						reqSetAddr->tdStatus.altHorptr = EHCI_HORPTR_TERM;
						reqSetAddr->tdStatus.token = 0
							| (EHCI_PID_IN << 8)		/* IN packet */
							| EHCI_TD_ACTIVE;
						
						reqSetAddr->setupData.bmRequestType = 0;
						reqSetAddr->setupData.bRequest = USB_REQ_SET_ADDRESS;
						reqSetAddr->setupData.wValue = addr;
						reqSetAddr->setupData.wIndex = 0;
						reqSetAddr->setupData.wLength = 0;
						
						uint32_t tokenOrg = reqSetAddr->tdSetup.token;
						// send the request
						qAsync->qh->overlay.horptr = transPhys;
						
						while (1)
						{
							kprintf("TOKEN WAS: 0x%08X, TOKEN IS: 0x%08X\n", tokenOrg, reqSetAddr->tdSetup.token);
						};

The kprintf() indicates that for the tdSetup (SETUP stage) transfer descriptor, EHCI clears the "Active" bit (bit 7) and sets the "Transmission error" bit (bit 3).

As shwon above, according to what Korona said I assumed the default endpoint to be high-speed, 64 max packet size. I tried other combinations too (full-speed, "Control" bit set) but none of them seem to work. Where coudlthe problem lie?

[BenLunt]

I just quickly looked over your stuff, sorry don't have enough time at the moment to look at it more closely, but the main thing that stood out to me is that you are trying to send a DATA packet after the SETUP packet and before the STATUS packet. This is not correct. For a SET_ADDRESS request, you send the SETUP packet and then the STATUS packet. No DATA packet.

In fact, you should never send a zero sized DATA packet. Only the STATUS packet is zero sized. Remove the middle DATA packet and try again.

Ben

[mariuszp]

I now removed the empty DATA packet. However, the same problem still occurs (the transmission error on the SETUP packet).