AIO On Linux

Yesterday I talked about the AIO situation on Windows. Today, as well as I am able, I am going to talk about the current situation on Linux. I've done asychronous AIO programming before on Windows, so that was an easy start for me. I've never used the Linux equivalents before, so this post is going to be a little bit more shakey.

First, let me start by saying that my initial findings on Linux AIO looked pretty bleak. I've seen some pages that talk about long lists of possible routes, each with unresolved problems. I've seen some project pages that look like they haven't been updated since 2007 or earlier. I've seen quotes like "This is stupid" or "That is crap". However, on closer inspection it's looking like there are some real possibilities for good AIO as of kernel 2.6. Specifically, the POSIX AIO API looks like it has a lot of promise for us. Unfortunately, a Google search for "Asynchronous IO on Linux" returns so much negative information.

I have found a good documentation page that does a decent job of talking about the various structures and functions involved in the POSIX API. However, I do notice a problem immediately that things like console IO cannot be accessed asynchronously. That's an issue that we can work around, however. Also, I notice that this POSIX API appears to use the one thing that I didn't like: Separate threads of blocking IO primitives running in user space. So, that's a negative, but not something we can't really get around here since the other options are worse. It's my understanding that the POSIX API is going to manage the synchronization issues, so maybe it's not such a bad thing.

In the last post I talked about adding an IO queue structure to the concurrency scheduler. Whenever we have a message, we schedule a handler task to process it. In Linux, we don't have anything like an IO Completion Port that can be used to manage a long list of requests for us (that I know of), but we can manually manage a list of struct aiocb structures and poll them for changes.

My interest has also been piqued by the aio_suspend function to help in implementing blocking IO operations internally. I also keep looking into the lio_listio function as a great way to launch a number of simultaneous requests, but I don't know how useful it will be in practice. We'll see how things fall into place one work begins on the actual implementation. One thing is for sure though: these POSIX functions don't appear to be available prior to the 2.6 Linux Kernel. So we're definitely going to need good configure probes, and we're going to need a good Plan B so we can simulate AIO on systems that don't support it directly.

Next up in my little series about AIO in Parrot will be a discussion about how we're going to be writing an AIO implementation that will be sane across Windows and Linux, and will properly integrate with the rest of Parrot. If you have any thoughts about this issue, or if you know anything about AIO on Darwin, please let me know. There are a lot of things that I don't know about these topics, so any input is much appreciated.

AIO on Windows

I'm more familiar with Windows API programming then I am with the Linux Kernel, so I'm going to talk about the AIO implementation on Windows first.

In Windows, we have two basic methods for implementing AIO: Overlapped IO and Completion Ports. Overlapped IO uses the normal IO API (WriteFile, ReadFile, etc). The difference is that when we open a file handle we open it with the FILE_FLAG_OVERLAPPED flag. This tells the OS that all operations on this handle should be "overlapped", or asynchronous. We also have to create a special OVERLAPPED structure that includes information about timeouts and callbacks. Normal calls to WriteFile and ReadFile will then dispatch an asynchronous request instead of a synchronous one, so long as we also pass the OVERLAPPED structure to these calls.

An IO Completion Port is like a queue structure that contains and services many AIO requests. The completion port contains both a queue of AIO requests and a message queue. As requests are completed, messages are added to the message queue. The program can then poll this queue to determine which events have completed, if any. It's worth mentioning that IO Completion Ports can use callback routines too, so we don't lose that if we use completion ports.

In the Windows case it seems like it may be easier to retrofit the asynchronous operations into the FileHandle and Socket PMCs, instead of trying to create something new. We create a new FileHandle that is synchronous by default, although setting some kind of flag would open the handle instead as an overlapped handle. Maybe the simple act of setting a non-null callback function would cause this behavior. Of course, that doesn't really allow room for integrating AIO with Parrot's concurrency scheduler, and certainly isn't going to make things easy for having a smooth API that's usable with Windows AND Linux systems. So even though it seems like the more straight-forward method on Windows, I don't think it's going to be the way we should go in Parrot.

One thing that we could have instead is to add an "IO Request Queue" object to the scheduler, which in the Windows case would be an IO Completion Port structure. Asynchronous requests get added to the Queue, and the concurrency scheduler will regularly poll it to see when a message is received. When a message is received, the callback task is scheduled (or maybe even executed directly). There are lots of inefficiencies in this, and I don't have a lot of nice things to say about any system that blindly polls a flag, but it's a start for designing a unified AIO system.

So there are two basic methods that I can think of right now to implement an AIO system in Parrot. The first, as I mentioned above, uses a poll loop to keep track of completed IO events and schedules callbacks when they are received. The second, which I think I would like to avoid as much as possible is to use threading.

In a threaded AIO system, every new IO request launches a new thread. That worker thread executes various blocking operations, handles the callback, and then terminates. A big problem with this is that we can get into race conditions and data corruption issues if we launch two separate requests on the same IO target, unless we do lots of costly error checking and synchronization in Parrot. Instead, I think it's much better to let the OS's AIO API (now there's an alphabet soup for you!) handle the ordering and serializing of the requests.

I have to get some resources together and do a little research, but tomorrow or the day after I'll talk about the AIO situation on unixy systems too.

Update: I found some more interesting links:

• http://technet.microsoft.com/en-us/sysinternals/bb963891.aspx
• http://msdn.microsoft.com/en-us/magazine/cc302334.aspx
  

Using AIO from PIR

Last time I talked a little bit about how AIO would probably be implemented in PMC form, where each request or event was encapsulated in various PMC types. Let's take a quick look to explore how these might be used from PIR code.

First, a polled write:

.local pmc request
request = new 'AIOWriteRequest'
say request, "Hello World!"
poll_loop_top:
unless request goto poll_loop_top
say "Done!";

This would be, coincidentally, a way to implement a blocking call to the "say" opcode, in terms of an asynchronous variant. Of course, we would probably write it in C, but the steps would be the same. Now let's look at the same kind of idea, but using a callback to restore control flow instead of a polling loop to stall:

.local pmc request
request = new 'AIOWriteRequest'
.local pmc continue
continue = new Continuation
set_addr continue, resume_point
request.set_callback(continue)
say request, "Hello World Again!"
end

resume_point:
say "Done!"

A lot of this is speculative, I don't really know what would be considered the best way to halt the current execution thread but allow a scheduled task to continue execution later in the future. The "end" opcode is probably not a good one for this use, but I don't think any others exist. In either case, we probably want some kind of guarantee internally that all outstanding IO requests (besides a passive "listen") will be handled prior to interpreter termination, so calling "end" with an outstanding IO request could cause execution to resume as we expect. Again, speculative. Regardless of the specific details, this method performs the same blocking "say" call, but has the added benefit that it's not looping endlessly and eating resources the entire time. The currently running thread simply stops, and Parrot is free to use that time to do other work (such as handle the IO call).

I'm also ignoring some details about how buffering would work. For instance, if we were writing lots of little snippets to a file in a loop, would we buffer multiple snippets together into a single request, or would we dispatch each separately. Would we write:

loop_top:
$S0 = 'get_next_snippet'()
print requestobj, $S0 # Add $S0 to the buffer
unless ready_to_exit goto loop_top
schedule requestobj # Start the write operation with all snippets

Or maybe:

loop_top:
$S0 = 'get_next_snippet'()
print requestobj, $S0 # Set the payload
schedule requestobj # Schedule it, one snippet at a time
unless ready_to_exit goto loop_top

Obviously lots of questions to answer as we talk about implementing this system. One thing you will notice in the two previous examples, but you did not see in the first two was the use of the "schedule" opcode to actually dispatch the requests. For something like an asynchronous write operation, would the "say"/"print" opcodes actually schedule the IO, or would they just write data to the request buffer and then the "schedule" opcode would schedule it? Lots of questions to answer.

Let's look now at a passive listening PMC, such as a socket connection that would receive incoming data, or a PMC that listens to the OS to receive filesystem events:

.local pmc listener
listener = new 'AIOListen'
.local pmc callback
callback = find_global 'callback_sub'
listener.set_callback(callback)
listener.listen() # Could also be "schedule listener"
...

Every time the listener PMC received input, it would pass it along to the callback function:

.sub 'callback_sub'
.param pmc aiolisten # The AIOListen object
.param string data # The incoming data
...

In all the examples I've obviously left out some details. For instance, on none of the objects did I specify a filename or streamname, nor did I specify anything like a timeout, and I certainly didn't talk at all about buffering. Those details are necessary, but not important for these examples.

Here's another idea: What if instead of PIR-exposed AIO PMCs we had opcodes that managed these requests automatically?

writerequest filehandle, "Hello World!", callback1
readrequest filehandle, 20, callback2

And maybe an optional fourth argument would specify whether the current executing thread should suspend, terminate, or continue while the request is executing (which would enable us to do blocking IO very simply.

So these are some conceptual ideas about how AIO would be usable from PIR code. I'd be very interested to hear ideas that other people had about how it could be used. What I would like to see is example code that people think should work. Show me what you think these code examples should look like. There isn't anything firm on the design board yet, although I have a few more blog posts left to write about this topic.

AIO Variants

In a previous post I wrote a basic introduction to AIO and started alluding to some of the steps that would be needed to get a proper AIO system working in Parrot. The Wikipedia article on AIO mentions several different implementations or "flavors" of AIO that have been used throughout the years, and it should be apparent to most readers that several of these implementations are not useful for Parrot. However, I think there are three particular implementations that we probably do want to support in some fashion:

1. Callbacks. These are probaby the most basic and also the easiest to implement directly in Parrot. An IO stream is opened and callbacks are provided to handle events. Events can be a variety of things, including the completion of a scheduled write request, the completion of a fixed-width read request, or the receipt of unscheduled incoming data. When the particular event is triggered, a callback subroutine is invoked to deal with it.
2. Completion Ports: As I mentioned in the last post, completion ports use queued messages to indicate the completion of an IO task, instead of invoking a callback. The program must regularly poll the completion port to determine what, if anyhing, is happening. A completion port object with a queue of length one is identical to the VMS-style flagged IO
3. Select/Poll Loops. These kinds of AIO are commonly used in networking applications like webservers, although there are many other uses for them as well. Select/Poll loops let us keep track of several IO streams through a single interface. When an event is triggered in any stream, the select/poll loop can pass control to it's handler. These can be implemented as an event loop over a series of filehandles, although there are plenty of risks for performance problems.
   

In Parrot, AIO jobs are likely to be encapsulated in a PMC type (or several types) and are likely to inherit from the Task PMC or Event PMC types. Each AIO task object will probably have to contain:

1. The request itself, which is information about whether it's a read or a write, and the data to write or a count of characters to read.
2. The destination of the IO. So, an AIORead PMC would contain a reference to a FileHandle PMC that would control where the data was coming from.
   
3. A buffer or two to receive inputs and possibly to combine together outputs that have been made too closely together for the request to have been completed
4. An optional callback object, which could be any invokable PMC such as Continuation, Sub, or Coroutine. There would likely be one callback object for each type of IO event. So there will be one callback for when a read completes, or when a write completes, or when information is received asynchronously without being requested.
5. An internal flag or flags cache that can be polled to determine if an event has happened, if callbacks for those events have not been supplied.
   

It might make sense to have multiple AIO objects, such as an AIORead, AIOWrite, and AIOListen. This demarcation glosses over the need for bidirectional streams, but that could be resolved in a number of ways.

Asynchronous IO in Parrot

There are a few new features which are slated for implementation by Parrot 2.0, which is scheduled for release in January. That sure seems like a long way away, but it's never too early to be thinking about it. There are two large tasks that I'm particularly keen about working on: Garbage-collectable contexts and asynchronous IO. I'm waiting on the former because Allison Randal is doing some serious related work and I don't want to even think about it until her dust settles. The asynchronous IO (AIO) system in Parrot is something that I can start thinking about right now, so that's what I'm going to do.

When we think about normal IO, we think about calling a function that performs an IO operation and then returns when that operation is completed. Think about the "printf" function in C, or the "print" statement in Perl. Both of these are synchronous, or "blocking" IO calls. They take control away from your program, perform their operation, and then return when it is completed, blocking your program from continuing until they are finished. This can be significantly wasteful in some situations, although the effects can be mitigated through aggressive buffering.

AIO, in contrast to blocking IO, is a little different. Instead of making an IO call directly, you make a request for the system to perform the IO action. Control flow returns to your program immediately while the underlying system (usually the Operating System or the Virtual Machine) processes the request. On a multicore system, or just one that supports a good threading model, this can save a lot of time and resources. Plus, it lets your program start preparing the next request while the last one is processing.

Think back to your first class about programming, where the instructor probably drew out a quick diagram about the parts of the computer: The hard disks, the ram, the processor, etc. Storage in your computer moves from largest but slowest (hard disk) to smallest and fastest (processor registers). Writing to an uncached portion of memory can waste a few cycles, but writing to a poorly-buffered HDD can waste a hell of a lot more then that. And the entire time your drive is seeking, writing, and verifying (and maybe encrypting!) the data, your program needs to just sit and wait it out. At least, it needs to wait in a traditional blocking IO system. AIO systems leave the waiting to the operating system, and let your program get on with more important work.

When you make the request, the system usually creates a new thread to process it, or adds it into a queue for an existing thread, or something. The system executes the request on it's own time, and then it invokes a callback function to let your program know that the IO has been handled. Actually, this isn't always the case, users of recent Windows versions have probably heard of I/O Completion Ports, which are asynchronous IO objects that return status results in a queue that can be checked by your program, instead of invoking a callback. It's worth noting that a message-based AIO system could easily be built on top of a callback-based one, so Parrot could easily end up with both. This is yet another simplification on my part, there are several forms of AIO, many of which are described on Wikipedia.

So let's look at some implementation details as they pertain to Parrot:

1. AIO is going to need some sort of asynchronous execution mechanism. Some operating systems provide an AIO API already that Parrot can piggyback on. Some systems might not, however (although I don't think any of our current target platforms fall into this category). If the OS doesn't have an AIO API available, we could put together our own using Parrot's threads implementation
2. AIO is going to need a scheduling and dispatching mechanism, both to schedule the outgoing request and to schedule a callback when the request is complete. Parrot has a robust event scheduler already that we can use for this.
3. At first you might think that we need two IO systems, one for the asynchronous and one for the blocking variants. However, this is not the case. All blocking IO calls can be implementing using AIO primitives. A blocking "print" call, for instance, can be implemented by scheduling an asynchronous write operation and then waiting on some kind of synchronizer (a spinlock or mutex or something). So, once we have AIO we only need to maintain one system (although that means a lot of Parrot's current IO system will need to be closely reviewed, if not reworked)

I'm going to be talking more about Parrot and AIO (and some other Parrot-related projects I have in my todo list) here in the next few days.

Lost: Daniels Monologue

Did this blow anybody else's mind out of the water last night, or was it just me? Daniels soliloquy last night in the forrest, when he talked about the "Variables" of time and changing the past to affect the future was so...unexpected.

I was expecting things to go as they were laying out: the past was unchangable and the losties were in 1977 not to change things, but to learn about the island and take that knowledge with them (eventually) to the present day. The logical end result would be using this knowledge to "save the world". Not so. Now it seems that their goal is not only to observe and report, but actually to change events so that the planes never crashed, so the various people never died, etc. I wonder how well it's all going to work out.

The universe, as they have pointed out on numerous occasions, is self-correcting. Bringing the losties back to the seventies apparently is the universe's way of correcting for the huge mistake made by the Dharma people in releasing the electromagnetic energy, and thus causing a bunch of people to die who weren't "ready". Previously I had posited that Locke was the only "special" person, and the rest of the Ajira 316 passengers were only there to ensure Locke could return to the island as intended. Now, this doesn't seem to be the case, the rest of the members appear to be special too and are each going to play a unique role in this huge Rube Goldberg device to save the world.

This does raise some new questions from me now:
1) In show-time, they only have about 4 hours to detonate that bomb and stop the events from happening. Once that occurs, they obviously won't just fade away (a la Back To The Future) and resume their lives from where they would have been without it. There's no way that they could just resume normal lives and still have any material left over for a sixth season.
2) A lot of people have met loved ones as a result of the various show events (Swayer/Juliet, Jack/Kate sortof, Kate/Aaron) Kate even suggested that it was crazy that she would never have met the people on the plane. Are these people going to let the past be "undone" like Daniel suggests?

So I'm very much looking forward to the episode next week and then the 2-hr season finale sometime after that. Something tells me that the finale this year is going to be BIG.

Small Relocation

As my last post indicates, I'm a family man now. My wife and I are going to be doing all our personal and family-related blogging on a new dedicated family blog. This blog is instead going to be dedicated to my other interests: Wikibooks, Wikimedia, Parrot, Perl, and some of the technical things that I do at work.