KMDF: how can I get usb continuous reader callbacks always in order?

Hi all,
I'm using the continous reader functions in KMDF for a bulk read transfer on
a device that has a serial (CAN) bus. It's important that the data comes in
order in the driver's buffer, but I've seen issues on multi processor
machines. I know that the callback can run at the same time on different
processors, but how can I make sure to lock so all read buffer is processed
in the right order?

Currently, I use a spinlock in the beginning of the callback, but that is
not theoretically safe, as the thread can be interrupted before the spinlock
is acquired and the next callback eventually runs on the other processor
(or?). I've seen it happend when we used very small buffers for the usb
transfer (to get low bus latency). I use several queued reads, up to ten is
supported I suppose.

Regards,
Carl-Magnus Segerlund

Peter
Thu Feb 07 16:49:08 CST 2008

In general if you need I/O operations to be performed in a particular order
then you cannot overlap them.

How many concurrent read requests do you configure the reader for?

-p

--
This posting is provided "AS IS" with no warranties, and confers no rights.


"Carl-Magnus Segerlund" <news@deletethis.driverguru.se.deletethis> wrote in
message news:9421FEC9-8E68-433C-8770-4B59E4568AF0@microsoft.com...
> Hi all,
> I'm using the continous reader functions in KMDF for a bulk read transfer
> on a device that has a serial (CAN) bus. It's important that the data
> comes in order in the driver's buffer, but I've seen issues on multi
> processor machines. I know that the callback can run at the same time on
> different processors, but how can I make sure to lock so all read buffer
> is processed in the right order?
>
> Currently, I use a spinlock in the beginning of the callback, but that is
> not theoretically safe, as the thread can be interrupted before the
> spinlock is acquired and the next callback eventually runs on the other
> processor (or?). I've seen it happend when we used very small buffers for
> the usb transfer (to get low bus latency). I use several queued reads, up
> to ten is supported I suppose.
>
> Regards,
> Carl-Magnus Segerlund
>

Doron
Thu Feb 07 17:45:38 CST 2008

i agreee, if you need ordering you can only send one at a time. the design
of the cont reader is that the data can come back in unrelated blobs wrt
each other. the other alternative is that the buffer itself has a
counter/index that allows you to do reorder out of order packets

d

--
Please do not send e-mail directly to this alias. this alias is for
newsgroup purposes only.
This posting is provided "AS IS" with no warranties, and confers no rights.


"Peter Wieland [MSFT]" <peterwie@online.microsoft.com> wrote in message
news:DF0B05D4-8EC0-471D-82EF-E69AAE87AA1F@microsoft.com...
> In general if you need I/O operations to be performed in a particular
> order then you cannot overlap them.
>
> How many concurrent read requests do you configure the reader for?
>
> -p
>
> --
> This posting is provided "AS IS" with no warranties, and confers no
> rights.
>
>
> "Carl-Magnus Segerlund" <news@deletethis.driverguru.se.deletethis> wrote
> in message news:9421FEC9-8E68-433C-8770-4B59E4568AF0@microsoft.com...
>> Hi all,
>> I'm using the continous reader functions in KMDF for a bulk read transfer
>> on a device that has a serial (CAN) bus. It's important that the data
>> comes in order in the driver's buffer, but I've seen issues on multi
>> processor machines. I know that the callback can run at the same time on
>> different processors, but how can I make sure to lock so all read buffer
>> is processed in the right order?
>>
>> Currently, I use a spinlock in the beginning of the callback, but that is
>> not theoretically safe, as the thread can be interrupted before the
>> spinlock is acquired and the next callback eventually runs on the other
>> processor (or?). I've seen it happend when we used very small buffers for
>> the usb transfer (to get low bus latency). I use several queued reads, up
>> to ten is supported I suppose.
>>
>> Regards,
>> Carl-Magnus Segerlund
>>

Carl-Magnus
Fri Feb 08 01:15:45 CST 2008

I configured it for ten concurrent reads when I used 64 bytes block reads,
it's not a usb 2.0 device. Then I understood that Windows and usb buffer
sizes isn't the same and got the firmware modified (to send full buffers
when there is data and a null buffer when there's no more data) so the usb
driver could get more data in one read. This increase the latency but gives
me some performance. Thanks for the clarification on this matter.

So now I have to choose between low latency and high performance, as
usual... or have someone change the device to usb 2.0 ;-)
Carl-Magnus Segerlund

"Peter Wieland [MSFT]" <peterwie@online.microsoft.com> wrote in message
news:DF0B05D4-8EC0-471D-82EF-E69AAE87AA1F@microsoft.com...
> In general if you need I/O operations to be performed in a particular
> order then you cannot overlap them.
>
> How many concurrent read requests do you configure the reader for?
>
> -p
>
> --
> This posting is provided "AS IS" with no warranties, and confers no
> rights.
>
>
> "Carl-Magnus Segerlund" <news@deletethis.driverguru.se.deletethis> wrote
> in message news:9421FEC9-8E68-433C-8770-4B59E4568AF0@microsoft.com...
>> Hi all,
>> I'm using the continous reader functions in KMDF for a bulk read transfer
>> on a device that has a serial (CAN) bus. It's important that the data
>> comes in order in the driver's buffer, but I've seen issues on multi
>> processor machines. I know that the callback can run at the same time on
>> different processors, but how can I make sure to lock so all read buffer
>> is processed in the right order?
>>
>> Currently, I use a spinlock in the beginning of the callback, but that is
>> not theoretically safe, as the thread can be interrupted before the
>> spinlock is acquired and the next callback eventually runs on the other
>> processor (or?). I've seen it happend when we used very small buffers for
>> the usb transfer (to get low bus latency). I use several queued reads, up
>> to ten is supported I suppose.
>>
>> Regards,
>> Carl-Magnus Segerlund
>>

chris
Fri Feb 08 09:54:17 CST 2008

On Feb 7, 5:45 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
wrote:

> i agreee, if you need ordering you can only send one at a time. the design
> of the cont reader is that the data can come back in unrelated blobs wrt
> each other. the other alternative is that the buffer itself has a
> counter/index that allows you to do reorder out of order packets

I'm trying to understand this. Say you issue three URBs
asynchronously which are each 64-byte reads. The device then sends a
single "A", "B", and then "C" over the bulk pipe (i.e. three short
packets). You're saying you could get cont. reader callbacks with
buffers that contain (say), "B", "C", "A"...in that order?

Doron
Fri Feb 08 13:09:22 CST 2008

yes, this is an artifact of NT itself, not KMDF. think of it this way: the
usb stack queues a DPC for ISR once the transfer is done. it completes the
IRP (transfer A) in this DPC. Another instance of the DPC can be queued on
another processor where it completes the second IRP (xfer B). Depending on
how the processors execute wrt each other, B can arrive before A

d


--
Please do not send e-mail directly to this alias. this alias is for
newsgroup purposes only.
This posting is provided "AS IS" with no warranties, and confers no rights.


<chris.aseltine@gmail.com> wrote in message
news:46e942a4-b786-41ad-910b-593e56acbb5d@h11g2000prf.googlegroups.com...
> On Feb 7, 5:45 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
> wrote:
>
>> i agreee, if you need ordering you can only send one at a time. the
>> design
>> of the cont reader is that the data can come back in unrelated blobs wrt
>> each other. the other alternative is that the buffer itself has a
>> counter/index that allows you to do reorder out of order packets
>
> I'm trying to understand this. Say you issue three URBs
> asynchronously which are each 64-byte reads. The device then sends a
> single "A", "B", and then "C" over the bulk pipe (i.e. three short
> packets). You're saying you could get cont. reader callbacks with
> buffers that contain (say), "B", "C", "A"...in that order?

chris
Fri Feb 08 14:54:15 CST 2008

On Feb 8, 1:09 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
wrote:

> yes, this is an artifact of NT itself, not KMDF. think of it this way: the
> usb stack queues a DPC for ISR once the transfer is done. it completes the
> IRP (transfer A) in this DPC. Another instance of the DPC can be queued on
> another processor where it completes the second IRP (xfer B). Depending on
> how the processors execute wrt each other, B can arrive before A

Okay, I agree that makes sense in principle, but that doesn't bode
well for maintaining integrity in an arbitrary stream of data that is
(say) being buffered inside the driver for usermode consumption,
right? You mentioned inserting index numbers into the data or what
not, but what if the device is not sending data in "frames" or any
sort of delineated fashion that can be chopped up like that? If this
is the case, isn't it extremely dangerous to set the default number of
submitted URBs in a continuous reader to be greater than one?

Or let me put it another way: in what situations would the driver or
system in general not care about the order in which it received data
from a device??

Doron
Fri Feb 08 16:53:33 CST 2008

nic data, bluetooth incoming packets, audio.

d

--
Please do not send e-mail directly to this alias. this alias is for
newsgroup purposes only.
This posting is provided "AS IS" with no warranties, and confers no rights.


<chris.aseltine@gmail.com> wrote in message
news:991ab71b-d953-49af-ae3d-86e5be191e45@l32g2000hse.googlegroups.com...
> On Feb 8, 1:09 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
> wrote:
>
>> yes, this is an artifact of NT itself, not KMDF. think of it this way:
>> the
>> usb stack queues a DPC for ISR once the transfer is done. it completes
>> the
>> IRP (transfer A) in this DPC. Another instance of the DPC can be queued
>> on
>> another processor where it completes the second IRP (xfer B). Depending
>> on
>> how the processors execute wrt each other, B can arrive before A
>
> Okay, I agree that makes sense in principle, but that doesn't bode
> well for maintaining integrity in an arbitrary stream of data that is
> (say) being buffered inside the driver for usermode consumption,
> right? You mentioned inserting index numbers into the data or what
> not, but what if the device is not sending data in "frames" or any
> sort of delineated fashion that can be chopped up like that? If this
> is the case, isn't it extremely dangerous to set the default number of
> submitted URBs in a continuous reader to be greater than one?
>
> Or let me put it another way: in what situations would the driver or
> system in general not care about the order in which it received data
> from a device??

Kalle
Fri Feb 08 16:56:35 CST 2008

"Doron Holan [MSFT]" <doronh@online.microsoft.com> writes:

> yes, this is an artifact of NT itself, not KMDF. think of it this
> way: the usb stack queues a DPC for ISR once the transfer is done.
> it completes the IRP (transfer A) in this DPC. Another instance of
> the DPC can be queued on another processor where it completes the
> second IRP (xfer B). Depending on how the processors execute wrt each
> other, B can arrive before A

If the IRPs were given to IoCallDriver in the order A,B,C, will
the buffer of A contain the data that the device sent first, even
if the IoCompletion routines of the IRPs get called in some other
order? If so, then the driver sending the IRPs can piece the
data back together based on the context parameters.

Maxim
Sat Feb 09 09:18:33 CST 2008

> In general if you need I/O operations to be performed in a particular order
> then you cannot overlap them.

Another idea:

- submit several overlapped IOs
- assign consecutive numbers to them in the order of their submission
- in completion path, check the order and reassemble the data stream

--
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
maxim@storagecraft.com
http://www.storagecraft.com

Tim
Sat Feb 09 19:38:01 CST 2008

"Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote:
>
>nic data, bluetooth incoming packets, audio.

You aren't really saying that it doesn't matter if packets from a
microphone arrive out of order, are you?

I can understand if URBs come back in an order different from the order I
submitted them, but there are tons of USB drivers in the world that rely on
the assumption that their URB completion routines get packets in the order
they arrived from the bus.
--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

Pavel
Sun Feb 10 05:30:12 CST 2008

"Maxim S. Shatskih" <maxim@storagecraft.com> wrote in message news:eHnhK8yaIHA.4140@TK2MSFTNGP04.phx.gbl...
>> In general if you need I/O operations to be performed in a particular order
>> then you cannot overlap them.
>
> Another idea:
>
> - submit several overlapped IOs
> - assign consecutive numbers to them in the order of their submission
> - in completion path, check the order and reassemble the data stream

But reassembling needs special handling, like tcp has for
out of order packets (on behalf on network drivers).
Do you mean that *any* driver needs to do same on SMP?
Well, at least it will have to detect out of order data and hope it occurs rarely... OMG.

Regards,
--PA

Maxim
Sun Feb 10 07:30:56 CST 2008

> But reassembling needs special handling, like tcp has for
> out of order packets (on behalf on network drivers).
> Do you mean that *any* driver needs to do same on SMP?

From what I know, IO completion path in Windows from IopCompleteRequest to user
mode - return from the syscall or GetOverlappedResult or
GetQueuedCompletionStatus - is preemptable.

So, you cannot rely on _completion order_ in Windows.

Nevertheless, with most drivers you can rely on _IRP submit order_, that the
order of data portions in the IRPs will be the same as IRP submit order.

So, just keep a serial number in your IRP context - completion context for
kernel, OVERLAPPED wrapper for user, generate the numbers on IRP submit, and
deal with the (reassembling) in the completion path.

--
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
maxim@storagecraft.com
http://www.storagecraft.com

Doron
Mon Feb 11 11:57:26 CST 2008

audio is a bit of a corner case, it can cause a glitch or swapped slice, but
it is not the end of the world. the usb stack does its best to make sure
that packets return back to the caller in order, but out of order packets
can happen.

d

--
Please do not send e-mail directly to this alias. this alias is for
newsgroup purposes only.
This posting is provided "AS IS" with no warranties, and confers no rights.


"Tim Roberts" <timr@probo.com> wrote in message
news:04lsq3l4rlhqpapr03l5lid2vapq057anm@4ax.com...
> "Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote:
>>
>>nic data, bluetooth incoming packets, audio.
>
> You aren't really saying that it doesn't matter if packets from a
> microphone arrive out of order, are you?
>
> I can understand if URBs come back in an order different from the order I
> submitted them, but there are tons of USB drivers in the world that rely
> on
> the assumption that their URB completion routines get packets in the order
> they arrived from the bus.
> --
> Tim Roberts, timr@probo.com
> Providenza & Boekelheide, Inc.

Pavel
Tue Feb 12 08:10:47 CST 2008

"Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote in message news:u4rvQeNbIHA.484@TK2MSFTNGP06.phx.gbl...
> audio is a bit of a corner case, it can cause a glitch or swapped slice, but it is not the end of the world. the usb stack
> does its best to make sure that packets return back to the caller in order, but out of order packets can happen.
>

Doron, but can be more serious than swapped slice...
suppose that USB data comes in a continuous stream
and the driver parses it to logical messages (like in tcp),
then out-of-order receive will break the protocol and resync
would be required.

Regards,
--PA

> --
> Please do not send e-mail directly to this alias. this alias is for
> newsgroup purposes only.
> This posting is provided "AS IS" with no warranties, and confers no rights.
>
>
> "Tim Roberts" <timr@probo.com> wrote in message news:04lsq3l4rlhqpapr03l5lid2vapq057anm@4ax.com...
>> "Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote:
>>>
>>>nic data, bluetooth incoming packets, audio.
>>
>> You aren't really saying that it doesn't matter if packets from a
>> microphone arrive out of order, are you?
>>
>> I can understand if URBs come back in an order different from the order I
>> submitted them, but there are tons of USB drivers in the world that rely on
>> the assumption that their URB completion routines get packets in the order
>> they arrived from the bus.
>> --
>> Tim Roberts, timr@probo.com
>> Providenza & Boekelheide, Inc.
>

Doron
Tue Feb 12 13:27:22 CST 2008

correct. the driver needs to be aware that io can come out of order if it
sends more than one read on an endpoint at a time.

d

--
Please do not send e-mail directly to this alias. this alias is for
newsgroup purposes only.
This posting is provided "AS IS" with no warranties, and confers no rights.


"Pavel A." <pavel_a@NOwritemeNO.com> wrote in message
news:uFThqIYbIHA.1164@TK2MSFTNGP02.phx.gbl...
> "Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote in message
> news:u4rvQeNbIHA.484@TK2MSFTNGP06.phx.gbl...
>> audio is a bit of a corner case, it can cause a glitch or swapped slice,
>> but it is not the end of the world. the usb stack does its best to make
>> sure that packets return back to the caller in order, but out of order
>> packets can happen.
>>
>
> Doron, but can be more serious than swapped slice...
> suppose that USB data comes in a continuous stream
> and the driver parses it to logical messages (like in tcp),
> then out-of-order receive will break the protocol and resync
> would be required.
>
> Regards,
> --PA
>
>> --
>> Please do not send e-mail directly to this alias. this alias is for
>> newsgroup purposes only.
>> This posting is provided "AS IS" with no warranties, and confers no
>> rights.
>>
>>
>> "Tim Roberts" <timr@probo.com> wrote in message
>> news:04lsq3l4rlhqpapr03l5lid2vapq057anm@4ax.com...
>>> "Doron Holan [MSFT]" <doronh@online.microsoft.com> wrote:
>>>>
>>>>nic data, bluetooth incoming packets, audio.
>>>
>>> You aren't really saying that it doesn't matter if packets from a
>>> microphone arrive out of order, are you?
>>>
>>> I can understand if URBs come back in an order different from the order
>>> I
>>> submitted them, but there are tons of USB drivers in the world that rely
>>> on
>>> the assumption that their URB completion routines get packets in the
>>> order
>>> they arrived from the bus.
>>> --
>>> Tim Roberts, timr@probo.com
>>> Providenza & Boekelheide, Inc.
>>
>
>

chris
Tue Feb 12 16:14:20 CST 2008

On Feb 12, 1:27 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
wrote:

> correct. the driver needs to be aware that io can come out of order if it
> sends more than one read on an endpoint at a time.

I guess I'm still of the opinion that this is a HUGE gotcha and should
be called out in the documentation as such, as long as the default
pended URB count for the continuous reader is > 1. Who would normally
expect data blocks to arrive in their callback out of order, compared
to how the device sent them?

Peter
Tue Feb 12 18:22:40 CST 2008

Agreed - I'll make sure we get a warning about this in the documentation.

-p

--
This posting is provided "AS IS" with no warranties, and confers no rights.


<chris.aseltine@gmail.com> wrote in message
news:bd66cd03-1dc0-4cfc-bf2c-e4209de5994e@s13g2000prd.googlegroups.com...
> On Feb 12, 1:27 pm, "Doron Holan [MSFT]" <dor...@online.microsoft.com>
> wrote:
>
>> correct. the driver needs to be aware that io can come out of order if
>> it
>> sends more than one read on an endpoint at a time.
>
> I guess I'm still of the opinion that this is a HUGE gotcha and should
> be called out in the documentation as such, as long as the default
> pended URB count for the continuous reader is > 1. Who would normally
> expect data blocks to arrive in their callback out of order, compared
> to how the device sent them?

m
Tue Feb 12 19:23:33 CST 2008

<SNIP>
> 1. Who would normally
> expect data blocks to arrive in their callback out of order, compared
> to how the device sent them?

Anyone who works on preemptive multi-tasking operating systems!

Pavel
Thu Feb 14 08:29:52 CST 2008

"Maxim S. Shatskih" <maxim@storagecraft.com> wrote in message news:e9g9rk%23aIHA.4684@TK2MSFTNGP06.phx.gbl...
>> But reassembling needs special handling, like tcp has for
>> out of order packets (on behalf on network drivers).
>> Do you mean that *any* driver needs to do same on SMP?
>
> From what I know, IO completion path in Windows from IopCompleteRequest to user
> mode - return from the syscall or GetOverlappedResult or
> GetQueuedCompletionStatus - is preemptable.
>
> So, you cannot rely on _completion order_ in Windows.
>
> Nevertheless, with most drivers you can rely on _IRP submit order_, that the
> order of data portions in the IRPs will be the same as IRP submit order.
>
> So, just keep a serial number in your IRP context - completion context for
> kernel, OVERLAPPED wrapper for user, generate the numbers on IRP submit, and
> deal with the (reassembling) in the completion path.
>
> --
> Maxim Shatskih, Windows DDK MVP
> StorageCraft Corporation
> maxim@storagecraft.com
> http://www.storagecraft.com

Thanks. this makes sense. Even so, I really hope that
the DPCs of the host controller are serialized on same cpu;
and this serialization keeps up to the client callbacks at DISPATCH.
Otherwise it looks like major PITA - especially if this applies also to
other protocol buses like SDIO.

--PA

Maxim
Thu Feb 14 09:36:55 CST 2008

> Thanks. this makes sense. Even so, I really hope that
> the DPCs of the host controller are serialized on same cpu;

Again no guarantees.

BTW - this is important for streaming devices (like a TCP socket or USB bulk
pipe) only. For random-addressing devices like storage this is not important.

--
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
maxim@storagecraft.com
http://www.storagecraft.com