Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[David Brownell]

[ Since Alan forwarded part the original question to LKML ... if you
follow up, please adjust CC's appropriately ]

----------  Forwarded Message  ----------

Subject: Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?
Date: Sunday 25 February 2007 8:53 am
From: David Brownell <david-b@pacbell.net>
To: Sarah Bailey <saharabeara@gmail.com>
Cc: greg@kroah.com, usb-hacking@svcs.cs.pdx.edu, linux-usb-devel@lists.sourceforge.net

On Sunday 25 February 2007 12:57 am, Sarah Bailey wrote:
> I've been doing some research into how asynchronous I/O is implemented,
> and I'm beginning to doubt the usefulness of implementing aio_read
> and aio_write in usbfs2.  More detail on what I've learned can be found
> at http://wiki.cs.pdx.edu/usb/asyncdebate.html

Those two links at the bottom aren't clickable ... :)


> It was a surprise to me that aio_read(3) and aio_write(3) don't actually
> end up calling aio_read and aio_write file operations.  Instead, GNU
> libc spawns threads that call the blocking read and write file
> operations.

As you observed, the answer is to use libaio instead of the GNU libc calls.
GNU libc does not use the Linux kernel AIO capabilities.

They're not all that closely matched, for reasons I won't speculate on here.
The gap between POSIX AIO and kernel AIO has been an ongoing problem.  This
syslet/fibril/yadda-yadda stuff is just the latest spin. 


> I haven't seen any evidence that the kernel-side aio is substantially
> more efficient than the GNU libc implementation,

Face it:  spawning a new thread is fundamentally not as lightweight
as just submitting an aiocb plus an URB.  And spawning ten threads
costs a *LOT* more than submitting ten aiocbs and URBs.  (Count just
the 4KB stacks associated with each thread, vs memory consumed by
using AIO ... and remember to count the scheduling overheads.)

Or to put it differently:  *adding thick layers* can hardly improve
things when the current layer (e.g. URB) already exposes the right
model.  In such cases you want as thin a layer as possible (or none).


> so it seems like it 
> would be better to leave the complexity in userspace. 

Thing is, the kernel *already* has URBs.  And the concept behind them
maps one-to-one onto AIOCBs.  All the kernel needs to expose is:
mechanisms to submit (and probably cancel) async requests, then collect
the responses when they're done.

You're right that associating a thread with an URB is complexity.

Presumably in your operating systems studies you have come across
the notion of a behavioral duality between (async) event models
and (synchronous) task models, as applied to systems.  Often a
great source of heated discussion; LKML no exception.  Both kinds of
model can be used to describe the same complex system.  In various
contexts, each modeling approach has advantages.

One point that's often (IMO) misstated is the one about "complexity".

All intro programming classes present single-threaded non-event models,
which biases many students (and graduates!) to think that model is
somehow less complex than event based models.    Yet the real world is
more often event based ... and hiding those events beyind a synchronous
model is often more complex (and error prone, and slower) than working
directly with the async/event model.  (Hence irqs, timers, etc).

When the problem is interfacing an event based reality with a stack of
legacy synch code, it's unfair to blame those translation costs on reality 
(asynchrony) not the _desire_ to coexist with that synchronous code.
For example, many operating systems have been written _only_ with async
interfaces exposed to userspace, and thus don't need these particular
silly arguments.  :)



> I also doubt that 
> most userspace application writers know they aren't getting kernel-side
> aio when they use aio_read(3) and aio_write(3).  Why implement something
> that isn't going to be used?

I can't much help application writers that don't bother to read the
relevant documentation (after it's been pointed out to them).


> There are few examples in the kernel where the aio API is implemented in
> a truly asynchronous manner, and that leads me to wonder if the aio
> system has been thoroughly tested.  The majority of aio_read and
> aio_write file operations simply block and wait for their transactions
> to complete.

It bothers me too that the current AIO framework is so little used
except in the context of the block layer.  The folk doing AIO work
seem to have been aiming to support database loads, more than doing
real work to support async IO ... which, historically, generalized
from I/O to filesystems (rather than, as with Linux AIO, starting
with filesystems).  And the changes they have made to the AIO stack
over the past few years have not (AFAICT) been done with the least
reference to non-database scenarios; certainly, consulting anyone
other than blockdev-oriented developers was exception-not-rule.

On the other hand, that infrastructure is in place and works today.


> The only "proper" async examples I could find were gadgetfs, NFS, and
> block devices.  NFS and block devices only use aio when the O_DIRECT
> flag is set, so that code may not be well tested.  I just found a bug in
> gadgetfs that has been there for six months that means the code wasn't
> tested for when io_submit is called in readv mode.

That's the problem you noticed with the vectorized I/O?  Added by the
AIO team, but not in a gadgetfs AIO path that had previously been used.
As you noted, easily fixed.  And as you implied, not previously present.
It's something that a "must provide test suite for API" rule would have
prevented in the first place.


> So, why do I want a non-blocking aio_read and aio_write file operation?

Without it, how would you achieve I/O overlap, and thus maximize the
I/O throughput accessible when streaming data to/from userspace?  The
description you gave of glibc aio support sure sounded to me like it
was incapable of achieving much in the way of I/O overlap.

Treat your target data rate as 24 MB/sec high bandwidth ISO or interrupt
data streams.  USB hardware can sustain those transfer rates without any
real hiccups ... but *ONLY* if the driver stack never lets the transfer
queue empty.  (Now think about costs on a low-MIPS processor... where
context switch costs are disproportionately high; ARMv5 at 200 MIPS.)


> It's useful to have read and readv implemented automatically from
> aio_read, but I see no substantial benefit to implementing aio_read in a
> non-blocking way.

Actually I wouldn't care much at all about readv/writev, those are
just nice things to fall out.  The main motivation IMO is to make
sure that data can stream at peak USB bus rates, without any regular
stuttering associated with task scheduling.

- Dave

-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
linux-usb-devel@lists.sourceforge.net
To unsubscribe, use the last form field at:
https://lists.sourceforge.net/lists/listinfo/linux-usb-devel


-------------------------------------------------------

[linux-usb-devel] usbfs2: Why asynchronous I/O?

[Alan Stern]

This deserves to be discussed on LKML.

Alan Stern

---------- Forwarded message ----------
Date: Sun, 25 Feb 2007 00:57:55 -0800
From: Sarah Bailey <saharabeara@gmail.com>
To: David Brownell <david-b@pacbell.net>, greg@kroah.com
Cc: usb-hacking@svcs.cs.pdx.edu, linux-usb-devel@lists.sourceforge.net
Subject: [linux-usb-devel] usbfs2: Why asynchronous I/O?

I've been doing some research into how asynchronous I/O is implemented,
and I'm beginning to doubt the usefulness of implementing aio_read
and aio_write in usbfs2.  More detail on what I've learned can be found
at http://wiki.cs.pdx.edu/usb/asyncdebate.html

It was a surprise to me that aio_read(3) and aio_write(3) don't actually
end up calling aio_read and aio_write file operations.  Instead, GNU
libc spawns threads that call the blocking read and write file
operations.

I haven't seen any evidence that the kernel-side aio is substantially
more efficient than the GNU libc implementation, so it seems like it
would be better to leave the complexity in userspace.  I also doubt that
most userspace application writers know they aren't getting kernel-side
aio when they use aio_read(3) and aio_write(3).  Why implement something
that isn't going to be used?

There are few examples in the kernel where the aio API is implemented in
a truly asynchronous manner, and that leads me to wonder if the aio
system has been thoroughly tested.  The majority of aio_read and
aio_write file operations simply block and wait for their transactions
to complete.

The only "proper" async examples I could find were gadgetfs, NFS, and
block devices.  NFS and block devices only use aio when the O_DIRECT
flag is set, so that code may not be well tested.  I just found a bug in
gadgetfs that has been there for six months that means the code wasn't
tested for when io_submit is called in readv mode.

So, why do I want a non-blocking aio_read and aio_write file operation?
It's useful to have read and readv implemented automatically from
aio_read, but I see no substantial benefit to implementing aio_read in a
non-blocking way.

Sarah Bailey

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[Greg KH]

On Sun, Feb 25, 2007 at 11:51:46AM -0500, Alan Stern wrote:
> This deserves to be discussed on LKML.

Are you sure?  I thought it already got pretty well answered on the USB
mailing list (see David's response for one such response.)

thanks,

greg k-h

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[Alan Stern]

On Sun, 25 Feb 2007, Greg KH wrote:

> On Sun, Feb 25, 2007 at 11:51:46AM -0500, Alan Stern wrote:
> > This deserves to be discussed on LKML.
> 
> Are you sure?  I thought it already got pretty well answered on the USB
> mailing list (see David's response for one such response.)

Well, I was sure at the time I forwarded the message, which was hours 
before David's response arrived.

Besides, Sarah's message did bring up issues of interest to the kernel 
community at large, such as why AIO is supported by so few drivers.

Alan Stern

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[Sarah Bailey]

[-- Attachment #1: Type: text/plain, Size: 4602 bytes --]

On Sun, Feb 25, 2007 at 08:53:03AM -0800, David Brownell wrote:
> On Sunday 25 February 2007 12:57 am, Sarah Bailey wrote:
> > I haven't seen any evidence that the kernel-side aio is substantially
> > more efficient than the GNU libc implementation,
> 
> Face it:  spawning a new thread is fundamentally not as lightweight
> as just submitting an aiocb plus an URB.  And spawning ten threads
> costs a *LOT* more than submitting ten aiocbs and URBs.  (Count just
> the 4KB stacks associated with each thread, vs memory consumed by
> using AIO ... and remember to count the scheduling overheads.)

Yes, spawning a new thread is costly.  However, if someone writes their
own thread-based program and allocates the threads from a pool, that
argument is irrelevant.  Even with fibrils, you have a stack and
scheduling overhead.  With kernel AIO, you have also have some memory
overhead, and you also have context switch overhead when you call
kick_iocb or aio_complete.

Can someone point me at hard evidence one way or another?

> > so it seems like it would be better to leave the complexity in
> > userspace. 
> 
> Thing is, the kernel *already* has URBs.  And the concept behind them
> maps one-to-one onto AIOCBs.  All the kernel needs to expose is:
> mechanisms to submit (and probably cancel) async requests, then collect
> the responses when they're done.

It seems to me that you're arguing that URBs and AIOCBs go together on
the basis that they are both asynchronous and both have some sort of
completion function.  Just because two things are alike doesn't mean
that it's better to use them together.

> You're right that associating a thread with an URB is complexity.

That's not what I said.  I don't think that the libc implementation is
more complex than the kernel AIO implementation.  The libc code is
smaller than the kernel AIO (the core code in aio_misc.c is 721 lines,
while the kernel AIO core code is 1769 lines).  The libc code is simpler
and easier to understand, and therefore may be less error prone.

> > I also doubt that 
> > most userspace application writers know they aren't getting kernel-side
> > aio when they use aio_read(3) and aio_write(3).  Why implement something
> > that isn't going to be used?
> 
> I can't much help application writers that don't bother to read the
> relevant documentation (after it's been pointed out to them).

Where is this documentation?  There's a man page on io_submit, etc., but
how would an application writer know to look for it?  I've grepped
through the Documentation directory, and I didn't find anything that
looked relevant. 

> The gap between POSIX AIO and kernel AIO has been an ongoing problem.  This
> syslet/fibril/yadda-yadda stuff is just the latest spin.

Do you think that fibrils will replace the kernel AIO?  It seems like a
logicial conclusion, but does the kernel AIO give you anything more?
For example, I think it currently allows drivers to guarantee that the
requests will be queued in the order they are submitted.  GNU libc and
fibrils can't make that guarantee because the operations may block
before the request enters the hardware queue.  

On Sun, Feb 25, 2007 at 09:33:02AM -0800, Eric Blossom wrote:
> On Sun, Feb 25, 2007 at 08:53:03AM -0800, David Brownell wrote:
> > Without it, how would you achieve I/O overlap, and thus maximize the
> > I/O throughput accessible when streaming data to/from userspace?  The
> > description you gave of glibc aio support sure sounded to me like it
> > was incapable of achieving much in the way of I/O overlap.
> 
> I heartily agree with this sentiment.  The only way we've been able to
> sustain 32MB/s read and write bulk transfers across the USB from user
> space is by using the usbfs USBDEVFS_SUBMITURB ioctl.  We typically
> run with 8 to 16 outstanding requests, each around 4kB.

GNU libc can overlap I/O.  It implements the userland equivalent of
fibrils.  No one is arguing that we don't need I/O overlap. :)

> FWIW, the peripheral we're using is the Universal Software Radio
> Peripheral (USRP).  It's basically an FX2, FPGA, ADC's and DAC's.
>
> The code we use for this is in the GNU Radio code base,
> http://gnuradio.org/trac/wiki
> 
> The relevant part is usrp/host/lib/fusb*.{h,cc}

Yes, a sane interface to the USRP was one of the main motivations for
the new USB filesystem.  It remains to be seen whether we need a
non-standard interface like io_submit, or whether threads with blocking
I/O is fast enough and has the right semantics.

Sarah Bailey

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[Greg KH]

On Mon, Feb 26, 2007 at 12:54:31AM -0800, Sarah Bailey wrote:
> Yes, a sane interface to the USRP was one of the main motivations for
> the new USB filesystem.  It remains to be seen whether we need a
> non-standard interface like io_submit, or whether threads with blocking
> I/O is fast enough and has the right semantics.

So, just for the sake of argument, how would one submit multiple urbs to
a single endpoint to ensure that the pipe is full with blocking I/O?
Would they have to:

  - open endpoint
  - create thread 1
  - create thread 2
  - create thread 3
  - create thread 4
  - send first packet to thread 1 to have it write to the endpoint.
  - send next packet to thread 2 to have it write to the endpoint.
  ...  and so on?

This seems very "hard" on userspace for something as simple as "I want
to send this data stream to the USB device as fast as is possible".

With async I/O you can just:
  - open endpoint
  - send first packet to endpoint with async write
  - send second packet to endpoint
  ... and so on


I'm all for using threads in userspace, as they are good ideas and very
powerful, but for a single data stream, they really seem like a complex
solution.

thanks,

greg k-h

Re: [linux-usb-devel] usbfs2: Why asynchronous I/O?

[David Brownell]

On Monday 26 February 2007 12:54 am, Sarah Bailey wrote:
> On Sun, Feb 25, 2007 at 08:53:03AM -0800, David Brownell wrote:
> > On Sunday 25 February 2007 12:57 am, Sarah Bailey wrote:
> > > I haven't seen any evidence that the kernel-side aio is substantially
> > > more efficient than the GNU libc implementation,
> > 
> > Face it:  spawning a new thread is fundamentally not as lightweight
> > as just submitting an aiocb plus an URB.  And spawning ten threads
> > costs a *LOT* more than submitting ten aiocbs and URBs.  (Count just
> > the 4KB stacks associated with each thread, vs memory consumed by
> > using AIO ... and remember to count the scheduling overheads.)
> 
> Yes, spawning a new thread is costly.  However, if someone writes their
> own thread-based program and allocates the threads from a pool, that
> argument is irrelevant. 

I don't see how that would follow from that assumption.  But even if
it did, the assumption isn't necessarily valid.  People who can write
threaded programs are the minority; people who can write correct ones
are even more rare!

We all hope that changes.  It's been hoped for at least a decade now.
Maybe in another decade or two, such skills can safely be assumed.


> Even with fibrils, you have a stack and 
> scheduling overhead.  With kernel AIO, you have also have some memory
> overhead, and you also have context switch overhead when you call
> kick_iocb or aio_complete.
> 
> Can someone point me at hard evidence one way or another?

(stack_size + other_thread_costs + urb_size) > (aoicb_size + urb_size)

There was recent discussion on another LKML thread pointing out how an
event-driven server ran at basically 100% of hardware capacity, where
a thread-one ran at 60%.  (That was, as I infer by skimming archives of
that threadlet discussion, intended to be a fair comparison...)


> > > so it seems like it would be better to leave the complexity in
> > > userspace. 
> > 
> > Thing is, the kernel *already* has URBs.  And the concept behind them
> > maps one-to-one onto AIOCBs.  All the kernel needs to expose is:
> > mechanisms to submit (and probably cancel) async requests, then collect
> > the responses when they're done.
> 
> It seems to me that you're arguing that URBs and AIOCBs go together on
> the basis that they are both asynchronous and both have some sort of
> completion function.  Just because two things are alike doesn't mean
> that it's better to use them together.

I pointed out that any other approach must accordingly add overhead.
One of the basic rules of thumb in system design is to avoid such
needless additions.


> > You're right that associating a thread with an URB is complexity.
> 
> That's not what I said.

No ... but you *were* avoiding that consequence what you did say, though.


> > I can't much help application writers that don't bother to read the
> > relevant documentation (after it's been pointed out to them).
> 
> Where is this documentation?  There's a man page on io_submit, etc., but
> how would an application writer know to look for it?

How did *you* know to look for it?  How did *I* know to look for it?

ISTR asking Google, and finding that "libaio" is how to get access
to the Linux kernel AIO facility.  Very quickly.  I didn't even need
to make the mistake of trying to use POSIX calls then finding they
don't work ...


> > The gap between POSIX AIO and kernel AIO has been an ongoing problem.  This
> > syslet/fibril/yadda-yadda stuff is just the latest spin.
> 
> Do you think that fibrils will replace the kernel AIO?

Still under discussion, but I hope not.  But remember two different things
are being called AIO -- while in my book, only one of them is really AIO.

 - The AIO VFS interface ... which is mostly ok, though the retry stuff
   is wierd as well as misnamed, and the POSIX hookery should also be
   improved.  (Those POSIX APIs omit key functionality, like collecting
   multiple results with one call, and are technically inferior.  Usually
   that's so that vendors can claim conformance without kernel updates.
   It could also be that the functionality is "optional", and so not part
   of what I find in my systems's libc.)

 - Filesystem hookery and direct-io linkage ... which has been trouble,
   and I suspect was never the right design.  The filesystem stacks in
   Linux were designed around thread based synch, so trying to slide
   an event model around the edges was probably never a good idea.

I see fibrils/threadlets/syslets/etc as a better approach to that hookery;
something like EXT4 over a RAID is less likely to break if that complex
code is not forced to restructure itself into an event model.

But for things that are already using event models ... the current AIO
is a better fit.  And maybe getting all that other stuff out of the mix
will finally let some of the "real I/O, not disks" AIO issues get fixed.

All of the "bad" things I've heard about AIO in Linux boil down to either
(a) criticisms about direct-IO and that filesystem hookery, rather than
about the actual AIO infrastructure; or else (b) some incarnation of the
can-never-end threads-vs-events discussion, taking a quasi-religious
stance against the notion of events.


> It seems like a 
> logicial conclusion, but does the kernel AIO give you anything more?

I'm repeating myself here:  it's the lowest overhead access to the
underlying I/O interface, which is fundamentally asynchronous ... so
there's no impedence mismatch.

Trying to match impedence of the "async I/O" core to threads gives
a lot of opportunities for bugs to join the party, of course.

And a lot of the most reliable systems code (in both user space and
kernel space) tends to follow event models.  Real time systems, for
example, like the way event handling costs can be bounded.  (A better
way to view "real time" systems is as "guaranteed response time"
systems".)  The analysis needed to prove correctness is usually less
difficult using event models than threading.

On the other hand, threads can be very quick-to-code, and if you
don't need/want such an "is it correct" analysis/review (i.e. it's
OK to hit bugs-in-the-field that are really painful to discover).


> For example, I think it currently allows drivers to guarantee that the
> requests will be queued in the order they are submitted.  GNU libc and
> fibrils can't make that guarantee because the operations may block
> before the request enters the hardware queue.  

That'd be an important issue, yes.  Though I'd certainly expect that if
userspace synchronized its submissions correctly (W1 then W2 then W3),
then no lower level code (libc, kernel, etc) would even contemplate
re-ordering that as W2, W1, W3 ...

- Dave