How do I update UHCI frame list?

[pvc]

Let's assume I have my TDs and QHs all linked together and ready to be pushed to HC. I know I have to write its physical address to HCs frame list. But how do I do that without risking glitching and data corruption? I mean, HC is constantly reading the list and writing to it without any synchronization wouldn't be the best idea. What is the proper way of doing that?

[BenLunt]

Hi,

This is a question that can refer to most hardware that accesses memory, not just the UHCI. However, the answer is quite simple, as long as you write your Queue Heads to physical memory in the correct order. i.e.: Making sure you update the linked list pointers in the correct order.

For example, let's say that you have a schedule that already has a list of Queue Heads marked "A", "B", "C", and "D". Of course "A" points to "B", "B" points to "C", "C" points to "D", and "D" has the "End of list" mark.

Now you want to insert a Queue Head in between "B" and "C". Let's call this Queue Head "N".

Here are a few scenarios to look at:
- Inserting a Queue Head:
- - 1) If we update "B" to point to "N" as the first write, if the controller executes the memory before we write "N" to point to "C", after executing "N", the controller will run off into unknown territory.
- - 2) If we update "N" to point to "C" as the first write, if the controller executes the memory before we write "B" to point to "N", nothing bad happens and the controller and schedule stay intact. "N" is not executed until the next frame.
- Removing a Queue Head: (See below for more information)
- - 3) If we update "C" to point to "B" before we remove "N", if interrupted and we try to insert a Queue between "N" and "C", our previous pointer is not valid anymore.
- - 4) If we update "B" to point to "C", before updating "C" to point to "B", removing "N" from the schedule, the controller will execute the schedule as expected.

With this in mind, always update the existing Schedule's Queue Head, in this case "B", as the last write to physical memory.

Also, please note that a decent controller will cache some or all of the schedule in internal memory. Therefore, it might take one complete frame before the controller reads from external physical RAM to update the schedule. If this is the case, three scenarios above (1, 2, and 4) are valid, however, you cannot assume this and you *must* do scenario 2) when inserting a Queue Head.

For a little more information, because a Queue Head is eight bytes in size, and knowing that the Head Link pointer has the bottom four bits masked, we know that a Queue Head must occupy 16 bytes of memory. Therefore, there is room for two 32-bit user pointers in every Queue Head. You can use one of these pointer areas as a "Previous" pointer pointing to the Queue Head that points to us. This is in fact a requirement in scenario 4) above to know where to update "B" to point to "C" when removing a Queue Head from the schedule.

However, please again take caution when updating the Queues. If you update "B" to point to "C" *before* you update "C" to point to "B" and the process is interrupted with another task inserting a Queue Head between "B" and "C", your previous pointer for "C" will now point to the removed "N".

So you see, keeping a coherent schedule is actually quite simple as long as you update pointers in the correct sequence. It is also a good idea to use a spinlock when inserting and removing queues so that another task cannot interfere during an update.

Hope this helps,
Ben
- http://www.fysnet.net/the_universal_serial_bus.htm

[pvc]

Making changes in schedule to look atomic from HCs perspective, sure does make sense.

But I think I may have got something wrong from the beginning. You describe how to insert and remove QHs into/from single running frame schedule in a way that it doesn't break anything. And that's clear. But then, what's the point of these 1024 entries in Frame List and FRNUM register? Do you just initialize whole Frame List with a pointer to one (empty) frame schedule and forget about it?

I thought that you're supposed to build complete frame schedule first and then put it's pointer into one of Frame List entries. And I can't figure out which entry to use to avoid race condition with current FRNUM. Or how to schedule multiple frames in advance if there is a lot of URBs coming from higher driver layers.

BTW. I've came across your book multiple times, and I bet it's all in there. But, unfortunately, I can't buy it.

[Korona]

The frame list has one entry per frame. For control and bulk transfers, the schedule is not really important (i.e., you can attach them (possibly indirectly) to any frame list entry and/or make every frame list entry point to them). Interrupt and isochronous transfers, however, need to be scheduled at the correct frames. For example, a webcam might produce data (isochronously) exactly every 16 frames (for 60 FPS). In that case, you would attach the corresponding transfers to every 16th frame list entry.

[BenLunt]

Like Korona has stated, the 1024 separate frames are for periodic transfers; mice, keyboard, cameras, etc.

The way that you should create your schedule is to have the controller execute any periodic transfers first, then move to the Control/Bulk schedule.

For example, here is a simple image I posted on this forum a while back:



It uses the first 32 frames. Side note: Since there are 1024 actual frames, using this example, you simply initialize the first 32 as show, then next 32 exactly the same, etc. (32 * 32 = 1024)

The vertical arrows point to the first Queue Head that will be executed in that frame. Then the horizontal arrows, pointing to the left, point to the next Queue Head, continuing until the last Queue Head is executed, this QH being QH1 shown above.

This schedule only has the following Queue Heads, one each of: QH32, QH16, QH8, QH4, QH2, and QH1.

Six (6) total QHs in the whole (empty) schedule. Period, not counting the fact that QH1 then points to a set of Control/Bulk QHs.

Now, by inserting (linking) QHs into one of these six (6) main QHs, you can have something executed at a certain interval.

For example, insert a QH into QH16 and the controller will automatically execute that QH every 16ms, period. Assuming that as soon as it is executed, you update the TDs with in it, new TDs will be executed again in another 16ms. There is no need to poll for time, no need for your code to calculate time, the controller does it all for you.

If you need something executed every frame, link to QH1. If you need something executed every other frame (2ms), link to QH2, etc.

Granted, this schedule shown has a max (or min) frequency of 32ms. If you have a device that needs less frequency, simply create a schedule using the first 64 entries which will now add a single QH at 64ms.

QH64, QH32, QH16, QH8, QH4, QH2, and QH1.

Or use the first 128 entries:

QH128, QH64, QH32, QH16, QH8, QH4, QH2, and QH1.

Or use all of them separately:

QH1024, QH512, QH256, QH128, QH64, QH32, QH16, QH8, QH4, QH2, and QH1.

This will give you the ability to have something executed every second, half second, quarter, etc. The whole periodic schedule has a total of 11 main Queue Heads. Period.

Now all you have to do, as far as periodic transfers are concerned, is call an insert queue function as such:

insert_queue(pointer to schedule, frequency);

The "pointer to schedule" is simply a pointer to the schedule you have, and frequency is a number, power of two (1, 2, 4, 8, etc) of which queue you want to place it in, in turn having the schedule executed every "frequency" milliseconds.

If you want to get more technical, you can even create a schedule with a more detailed frequency. For example, what about "odd" frequencies? By odd meaning not a power of 2.

Let's look at the example again:



The left half is exactly the same as the right half, except for the entry at 32. What it I only modify the right half by inserting a queue between QH8 at 24 and QH4 at 20, let's call it QH24, this Queue Head will be executed every 24th ms.

A few notes about the "odd" entry at QH24:
1) Technically, you would want QH24 to be executed before QH8, so you would swap them. 24 would point to QH24, which would point to QH8, which would point to QH4, etc.
2) Second, if you use the example above, you cannot simply copy to the next 32 entries and expect QH24 to be accurate. It now would be 32 away from this one instead of 24. In every copy, you would modify the appropriate half. For example, in the first 32, QH24 is at 24, but in the second set of 32 it is now at 16, the third set it is at 8, etc. But you get the idea, correct?

Does this make sense?

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

[pvc]

Now it makes much more sense. I think I will be able to make it work. Thanks for your help.