OSDev.org

I am extremely confused about how Queue Heads are supposed to be structured in EHCI.

I create one queue head per endpoint, correct?
The queue heads must be joined together into a ring (using the "horizontal link pointer"), correct?

Each Queue Head has a "transfer overlay" area, and a current TD pointer. So the question is: what values do i initialize the transfer overlay / current TD fields with when there are no transfer descriptors in the queue yet? Do I just initialize them all to zero such that the "active" bit in the TD is clear? And when I want to transfer something, do I create a TD and just place it's physical address into "current TD" field, leaving the transfer overlay alone? And when done, what does EHCI do with the descriptor; how is it removed from the queue and how do I add a new one without race conditions with the hardware?

bump

mariuszp wrote:I am extremely confused about how Queue Heads are supposed to be structured in EHCI.

Don't be disappointed, EHCI is probably the most confusing one of the four common types.

mariuszp wrote:I create one queue head per endpoint, correct?

You may create as many or as few as you wish. However, due to some of the fields within the queue head, yes, you must create one for each endpoint.

mariuszp wrote:The queue heads must be joined together into a ring (using the "horizontal link pointer"), correct?

Each Queue Head has a "transfer overlay" area, and a current TD pointer. So the question is: what values do i initialize the transfer overlay / current TD fields with when there are no transfer descriptors in the queue yet? Do I just initialize them all to zero such that the "active" bit in the TD is clear? And when I want to transfer something, do I create a TD and just place it's physical address into "current TD" field, leaving the transfer overlay alone? And when done, what does EHCI do with the descriptor; how is it removed from the queue and how do I add a new one without race conditions with the hardware?

The overlay is not initialized by the user, but by the controller *after* a TD is executed. Before a TD is executed, only the first 4 DWORDs of the Queue Head need to be initialized. Once the first TD linked within this Queue Head is executed, then the remaining DWORDs will be written by the controller.

Might I suggest a good book on the subject?
http://www.fysnet.net/the_universal_serial_bus.htm
This book contains information for all four controller types, how to initialize them, how to create a working USB stack, and shows detailed examples on how to enumerate devices, such as Mice, Keyboards, USB thumb drives, etc. I've heard the author will even let you send him an email asking questions, once you have read the applicable chapters and tried the process yourself first. The book also has example source code, available upon request with proof of purchase.

Anyway, EHCI is probably the most difficult one to program. Be sure that the device you are trying to enumerate is actually a high-speed device. If it is a low- or full-speed device, you won't get the EHCI to work at all... (unless there are no companion controllers).

Ben

BenLunt wrote:Might I suggest a good book on the subject?
http://www.fysnet.net/the_universal_serial_bus.htm
This book contains information for all four controller types, how to initialize them, how to create a working USB stack, and shows detailed examples on how to enumerate devices, such as Mice, Keyboards, USB thumb drives, etc. I've heard the author will even let you send him an email asking questions, once you have read the applicable chapters and tried the process yourself first. The book also has example source code, available upon request with proof of purchase.

It seems that your book really helps many people on this board grasp USB but I feel like your advertisements should still be less subtle. I suggest adding at least a "Disclaimer: I'm the author.".

So, I have to set the current TD address, the controller will execute the TD, what then? I wait for it to complete, then to use a new TD, i just change the "current TD" address and wait again?

Korona wrote:It seems that your book really helps many people on this board grasp USB but I feel like your advertisements should still be less subtle. I suggest adding at least a "Disclaimer: I'm the author.".

Sorry, I thought everyone knew that, hence the smiley face...

My intention is not to advertise for sales. The profit from these books is minimal at best. I am advertising for the help of others. Thank you for the comment though. I will try to keep it more professional.

Ben

mariuszp wrote:So, I have to set the current TD address, the controller will execute the TD, what then? I wait for it to complete, then to use a new TD, i just change the "current TD" address and wait again?

Your TD's can link to each other and upon successful completion, the controller will continue with the next until there are no more.

You need a mechanism to indicate to your driver that the last TD in the queue, has been successfully executed, *or* that one of the TD's caused an error.

Ben

BenLunt wrote: Sorry, I thought everyone knew that, hence the smiley face...

My intention is not to advertise for sales. The profit from these books is minimal at best. I am advertising for the help of others. Thank you for the comment though. I will try to keep it more professional.

Nah, I got it, and I'm sure a lot of others too, but there's also a lot of new people who might not have realized it to imply that you're the author.. So might be useful to add it to your sig, that way there's no ambiguity. I remember in almost every post so far you've pointer it out..

this discussion definitely has morphed into something useful for crunching EHCI. not that Ben's "advertisement"

And how exactly is an empty queue indicated? With a specific value in "current TD"?

mariuszp wrote:And how exactly is an empty queue indicated? With a specific value in "current TD"?

Well, you can do that in numerous ways. For example, let's say that you are sending the Get Device Descriptor request, requesting only the first 8 bytes. You would need two TD's to start with, one for the SETUP packet and one for the DATA packet. If you use polling, you can wait until the error indicator for the DATA packet is written as successful. Then to complete the transaction, send the STATUS packet, one TD.

If you wish to do something else, choose a good elapsed time that you think the transaction should take, successfully, then check each TD (two in this case) to see if the controller marked them all as successful. If the last one is still marked "active", it never got processed, so there was an error sometime before this.

There are many ways to do so. Some OSes call this URBs (USB Request Blocks), a thread/task/or other process that sends out a request, waits for the response, then reports the outcome.

Remember, that you can have the EHCI trigger an interrupt when it processes a certain TD, though keep in mind that it may only trigger that interrupt at end of (micro-)frame.

It is up to you to find out how you want to do it, how best fits with your kernel design, how best fits with your total driver design.

The example code I give with my book starts with the first TD and waits for it to be updated. If successful, moves on to the next TD, waiting for it to be updated, continuing on until I reach the last TD, stopping at any TD that fails. However, this is not a good design for a finished product, it is simply to show you what happens. It is up to you to come up with a better design. (I did not write my book to allow the reader to copy/paste code into their project. I wrote it to show what the hardware does and how to watch it do what it does, leaving the actual driver design to the reader.)

Ben

I meant, how do I initialise a queue head when the queue is empty. Does it still need to have a TD pointer, but with the TD having the "active" bit clear?

An empty queue head simply points to another queue head, which could be empty or have valid TD's within it. In a typical Asynchronous List, you have a Round-robin type list. Each Queue Head points to the next, with the last pointing to the first. Then your schedule can insert TD's as it see's fit.

However, a point needs to be made. Let's say that you have a USB keyboard attached and it indicates that you should poll for data every 128ms (for example). Does your driver keep track of the time? Does your driver have a timer to wait 128ms and then poll the keyboard? No, it should not.

This is what makes the USB shine. You place a Queue Head/TD combination within a frame relative to 128ms, or as close as you can get it. Then the hardware will follow the frame list and if you placed your Queue Head in the correct frame, it will be processed every 128ms.

For example, you know that each frame is 1ms. Therefore, you need a queue head in the 128th frame that points to a TD to retrieve the data from the keyboard.

Create a queue head list, calling each queue head by a name, such as QH128, QH64, QH32, QH16, QH8, QH4, QH2, and QH1. Now, point each frame pointer to one of the queue heads so that the first points to QH1, the second QH2, the third QH1, the fourth QH4, etc, each frame pointer pointing to the log() of its frame position. Then each queue head points to the next smaller queue head, i.e.: 128 points to 64 which points to 32, etc.

This way, the QH128 will only be parsed by the controller every 128th frame time. QH32 will be parsed every 32th frame time, yet QH1 will be pointed to every frame. Then when you see a device that needs to be polled every 128ms, place it in the 128th frame by adding a TD to the QH128 queue. If a device wishes to be polled every 50ms, place a TD in the QH32 queue which will poll every 32ms. (To get even better resolution, keep track of which queue head you used last (QH32 or QH16) and place a TD in the opposite. 32 + 16 = 48, pretty darn close to 50ms.)

Without sounding like I am trying to discourage you, I suggest that you do a lot of reading and studying before you start writing code. Draw on paper what your idea of the EHCI schedule should look like, then once you have a working idea, then start coding the driver.

Hope this helps,
Ben

Here is a diagram that I quickly drew up:



It is only the first 32 frames, but you can get the idea.

In that image, you have a total of 6 Queue Heads, QH32, QH16, QH8, QH4, QH2, and QH1. The QH32 points to QH16 which points to QH8, etc., all the way to QH1.

Now, if you point the frame list pointers to the correct queue heads, as shown above, any TD's in the QH16 queue, for example, will be processed every 16ms. If you need a TD to be processed every 2ms, place it in the QH2 list of TD's.

Now, all your driver has to do is insert TD's into the respected queue heads to have them processed at those intervals, noting that you have to update the TD once it has been processed, so that it gets executed again next time. No need for the driver to pause, wasting time, waiting for the TD to be processed. The driver can continue on with other things knowing that the hardware will process the TD at the correct interval.

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.

Does this help? Clear as mud? USB is a vast subject of confusion until you get the idea. I spent a long time (years) working on my book and I still don't grasp it all.

Anyway, hope this helps,
Ben
http://www.fysnet.net/the_universal_serial_bus.htm

That makes sense but what if there are TWO devices to be polled every 128ms? I would need 2 separate queue heads for them.

And, if I understand correctly, what you said applies to the PERIODIC schedule, correct? Asynchronous schedule (which, if I understand correct, is used for control/bulk transactions) is just Round Robin?