Out of Order completion!

Hi,

UMDF COM port driver with sequential read queue calling on KMDF USB device driver with sequential read queue - occasionally I get completions from KMDF -> UMDF out of order i.e. packets received over USB (these ARE in order as verified with CATC analyser) are re-ordered in time.
Any ideas

Thanks

Adrian

Are these YOUR drivers (both of them)??

If so, are you taking any measures to assure that the requests are completed in order?

And what, for you, does “re-ordered in time” mean?

Let’s say your UMDF driver sends 4 read requests to the KMDF driver

UMDF

Req 1 —>
Req 2 —>
Req 3 —>
Req 4 —>

Are you saying, for example:

a) That sometimes Req 4 completes before Req 2? But the data in the buffers is correctly ordered?

b) That sometimes Req 4 completes before Req 2, and the data in the buffers is out of order – corresponds to the order in which your being informed of the completion?

Or something else?

Peter
OSR

Peter,

Yes (unfortunately) both are my drivers. I have assumed that, as the USB packets/requests are completed in time order, then everything else above would do the same - I guess that that’s not the case!
Re-ordered in time means …
UMDF –> KMDF –> USB –> device –> USB –> KMDF –> UMDF
#1 –> #1 –> #1 –> device –> #1 –> #1 –> #2
#2 –> #2 –> #2 –> device –> #2 –> #2 –> #1
occasionally
Therefore data on USB and in KMDF driver is correctly ordered but by the time it reaches the UMDF buffers it’s re-ordered based on, as you say, the order in which I am informed of completion.

Thanks

Adrian

So… Just to be clear:

The data in #1 is the data received by the HCD first… and the data in #2 is the data received by the HCD second. But the requests themselves are completed out of order?

If so, this is the way Windows works. It is NEVER safe to assume, under ANY circumstances, that two asynchronous operations will be completed in the order in which they are initiated. It’s a multi-processor system, and The Wonders of Scheduling will have their way with you.

Peter
OSR

Peter,

How succinctly you put it in the first paragraph!
OK, so what can I do about it? There’s no way I can tag the data content - help (please)

A

The solution is for the READING driver to keep some context that allows it to remember the order.

In terms of implementation: How are you sending the request from your UMDF driver to your KMDF driver? You using IWDFIoRequest::Send?? Setting a completion callback with IWDFIoRequest::SetCompletionCallback?? Both of these offer the opportunity to keep some context hanging around…

Will that work??

Peter
OSR

Peter,

Yes, I am using ::Send & CompletionCallback so I can use context info to determine order - there again reordering into the buffer will be a pain (but my pain):wink:

thanks

A

Btw, IWDFIoRequest::Send gives you the option send requests down synchronously if that is viable solution for you.

http://msdn.microsoft.com/en-us/library/ff559149(VS.85).aspx
http://msdn.microsoft.com/en-us/library/ff561462(v=VS.85).aspx

You could also use AssignContext to associate some context with each request.

Thanks.

xxxxx@osr.com wrote:

So… Just to be clear:

The data in #1 is the data received by the HCD first… and the data in #2 is the data received by the HCD second. But the requests themselves are completed out of order?

If so, this is the way Windows works. It is NEVER safe to assume, under ANY circumstances, that two asynchronous operations will be completed in the order in which they are initiated. It’s a multi-processor system, and The Wonders of Scheduling will have their way with you.

Well, there ARE certain guarantees, at least in USB. We have been
promised (by USB team members in this forum, if not in the
documentation) that the USB host controller completes URBs in the order
that their packets completed. We have also been promised, because of
the way completion is done, that the USB client driver will get
completion callbacks in the order they happened. We have even been
promised that, if one is using a completion port, requests will arrive
at the completion port in proper order.

Where things usually go awry is on top of that. Once the requests are
back in an asynchronous or multi-threaded user-mode application,
anything can happen. As you so eloquently put it, the Wonders of
Scheduling come in to play.


Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

Shyamal, Tim,

Combining your replies …
If I use a synchronous request, will the UMDF driver be, as Tim put it, asynchronous, or can I assume (again as Tim put it) that the USB guarantees re URB completion etc… will work in my favour (English spelling :-)?

thanks
A

Do you notice reordering in the UMDF driver or the application (assuming that UMDF driver is processing app requests)?

If UMDF driver is submitting I/O from a sequential queue, there is only one I/O outstanding at a time, so there shouldn’t be any reordering.

Is the application doing async I/O with multiple outstanding I/O? If yes, it is quite possible that these get queued in UMDF in order different from the order app sent them in (even if app is using a single thread to send them).

In general, there is no order guarantee with multiple outstanding I/O. To ensure order, app can either submit one I/O at a time or use some info in the packets to order them correctly.

HTH,
Praveen

But none of those cases of guarantees apply to the situation in which he’s having the problem, right? He’s got a UMDF driver for a widget that sends requests to a KMDF driver (it doesn’t MATTER if it’s USB). He’s got multiple requests in progress from the Widget Driver to the KMDF driver.

There’s no reason to believe that the completion routines in his UMDF driver will be called in the order in which the requests were submitted. As far as I can see, at best there’s a multi-CPU race to get the completion callbacks to the UMDF driver. (Consider what happens when the KMDF driver completes two pending requests on two separate threads on two separate processors).

Peter
OSR

Adrian,

Yes, I am using ::Send & CompletionCallback so I can use context info to determine order

You mentioned a sequential queue of reads in UMDF driver. Is that correct? In that case I don’t understand how multiple outstanding requests go to KMDF driver and USB stack to cause any reordering - unless there are additional queues involved.

Would you please also let us know whether you are sending app generated requests from UMDF driver or are you sending driver generated requests?

If these are app requests (as I asked before) do you see reordering in UMDF driver or the app? If it is in the app, then it is due to app sending multiple outstanding I/O (app requests may get queued in UMDF in different order) so your ensuring order in UMDF driver won’t solve the problem. App would need to send one request at a time or reassemble the packets in the correct order.

HTH,
Praveen

Completions in Windows were never guaranteed to occur in order.


Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

wrote in message news:xxxxx@ntdev…
> Hi,
>
> UMDF COM port driver with sequential read queue calling on KMDF USB device driver with sequential read queue - occasionally I get completions from KMDF -> UMDF out of order i.e. packets received over USB (these ARE in order as verified with CATC analyser) are re-ordered in time.
> Any ideas
>
> Thanks
>
> Adrian
>
>

> Yes (unfortunately) both are my drivers. I have assumed that, as the USB packets/requests are

completed in time order

No. No IRP completion order is maintained.

If you have submitted 2 IRPs - IRP1 and then IRP2, and you have a guarantee that IRP2 is surely submitted after IRP1 - then you have a guarantee that they will really be processed and filled with data in the submission order. I.e. the completed IRP1 will have first data portion, and IRP2 - then next one.

But the timing of completions is not guaranteed at all. You can easily see IRP2 completion before IRP1 completion, and you will need to reorder yourself in this case.

One of the ways is to keep the submission sequence number in your IRP context (in user mode, IRP context is usually the wrapper around OVERLAPPED, or even a C++ descendant of OVERLAPPED).

Your code must ensure that the IRP with larger such number is always submitted after the IRP with the smaller number.

Then, in the completion path, you must reassemble the data flow using these numbers.


Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

> -----Original Message-----

From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Maxim
S. Shatskih
Sent: Thursday, July 01, 2010 2:03 PM
To: Windows System Software Devs Interest List
Subject: Re:[ntdev] Out of Order completion!

One of the ways is to keep the submission sequence number in
your IRP context (in user mode, IRP context is usually the
wrapper around OVERLAPPED, or even a C++ descendant of OVERLAPPED).

Your code must ensure that the IRP with larger such number is
always submitted after the IRP with the smaller number.

Then, in the completion path, you must reassemble the data
flow using these numbers.

Even simpler. Create queue of submitted requests in the same order they
were submitted and always wait for the head request only (wait for
overlapped event). No need for reordering because out-of-order submitted
requests are in the queue behind the first one.

Best regards,

Michal Vodicka
UPEK, Inc.
[xxxxx@upek.com, http://www.upek.com]

Michal,

Now that’s a nice idea - tonight’s fun I think :slight_smile:

Adrian

>Even simpler. Create queue of submitted requests in the same order they

were submitted and always wait for the head request only (wait for
overlapped event).

Good idea if you really want to create an event for each in-progress IRP.


Maxim S. Shatskih
Windows DDK MVP
xxxxx@storagecraft.com
http://www.storagecraft.com

If you want even more, I’m using 3 queues. Empty, in progress (this one)
and completed. Requests are originally all in the empty queue.
Communication thread takes N requests (one by one) from empty queue,
submits them and pushes to the in progress one. Then waits for queue
head. When satisfied, removes the first one from in progress, adds some
data (length, error code…) and places in to the completed queue. Takes
one request from empty one, submits it, adds to in progress and waits
for head again. Data processing thread takes a request from completed
queue, processes data and places request to the empty one. Circular
buffer without synchronization nightmare.

Best regards,

Michal Vodicka
UPEK, Inc.
[xxxxx@upek.com, http://www.upek.com]

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of
xxxxx@villasoft.co.uk
Sent: Thursday, July 01, 2010 8:45 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Out of Order completion!

Michal,

Now that’s a nice idea - tonight’s fun I think :slight_smile:

Adrian


NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online
at http://www.osronline.com/page.cfm?name=ListServer

When you talk about lack of ordering guarantee, it’s correct in generic case.

In some particular cases the driver stack authors may give some guarantee, with constraints.

For example, completions can only be delivered to the application in order if they are issued from the same thread. There is no ordering between different threads. Also, if the hardware may deliver interrupts to different processors, that may lose any ordering. Suppose, your USB host got an interrupt on processor 1 and a DPC pulled all completed requests from the hardware list. At about same time another interrupt happened on processor 2, and the DPC pulled more completed requests for the same pipe. Now, IoCompleteRequest would schedule APCs to the originator thread, but these IoCompReq calls could get out of order because they run on different processors at the same time.