AIO: All the rage

Excitement about AIO has been steadily building recently, and a number of contributors have been talking about it and asking me questions about it. I personally have been blocking on the io_cleanups branch which I've been working on with Infinoid. However both he and I have been pretty busy lately with work and life, and haven't been able to lock that branch down as I would have liked.

The io_cleanups branch is a little bit poorly named. I had originally intended it to be a short, fast, cleanup branch to get a few things in line before AIO. But, we took the opportunity to try and add in a proper implementation of pipes too. I would rather have all the pieces present (Files, Pipes, Sockets) when we start AIO so I can remember to make things general enough, then have fewer things implemented but the whole subsystem is a little more clean.

Astute observers will notice that we've already had pipes, in a fashion. Previously we've been able to open pipes to child processes using the FileHandle PMC. However, this mechanism was never very good and was only unidirectional. So Infinoid went through and created a proper bi-directional pipes implementation, which we're working on and testing right now.

The last problem that we're wrestling with is that this new "proper" implementation is a little bit messy. Parrot's IO system was basically written with only FileHandles in mind, and Pipes are a little bit shoehorned in right now. So ironically the "io_cleanups" branch actually introduced a new feature that is a little messy and didn't actually perform many cleanups. As much as I would like to resolve this little irony, I would far prefer to get a working Pipes implementation merged into trunk now. The branch is already too long-lived as it stands, and I really want to just reach the nearest stable point and merge it into trunk so we can start planning out the next moves.

Japhb was talking about adding D-Bus support to Parrot by wrapping the D-Bus libraries in PIR. Unfortuately, this is going to require better support in Parrot for asynchronous events and asynchronous IO operations. So, this is a good motivator to get AIO working, and is also a good use-case to help drive AIO development.

So as soon as the pipes thing stabilizes in the branch, I want to lock it down and merge it in. Then, I want to get started on AIO shortly thereafter. There is enough interest and even demand building at this point that I don't want to delay any more then necessary.

Path to AIO on Parrot

In the last few blog posts I've put out about Asynchronous IO (AIO) on Parrot, I've looked at some issues including how things work on Windows and Linux, and how things could start looking on Parrot. The series started with this post and ends with this one. Notice that I haven't provided all the answers here, so I'm still hoping to get some feedback from readers. I'm also pretty well convinced that we will learn some lessons quickly as work progresses. The biggest hassle is going to be creating a system which is semantically transparent on Windows and Linux, so that PIR users don't need to care about the differences.

PDD22 contains some information about AIO although it's all speculative. I've been pouring over this document for a few days and I think I'm really understanding a lot of the nuances about it and some of the methodology that the original designers had in mind. I think it's a decent approach, and I think we will be able to follow it reasonably closely without too many issues popping up. I showed some speculative PIR examples in a previous blog post, but I'm starting to think now that I will follow the PDD more and pursue that idea less.

The PDD has this to say about the relationship between synchronous and asynchronous opcodes:

Parrot only implements synchronous I/O operations. Initially,the asynchronous operations will be implemented separately from the synchronous ones. There may be an implementation that uses one variant to implement the other someday, but it's not an immediate priority.

and it says this about how the interface to PIR will look:

Synchronous opcodes are differentiated from asynchronous opcodes by the presence of a callback argument in the asynchronous calls. Asynchronous calls that don't supply callbacks (perhaps if the user wants to manually check later if the operation succeeded) are enough of a fringe case that they don't need opcodes.

The main point to take away from this is that asynchronous IO requests are not implemented as a PMC (at least not as one that the user needs to be aware of) and they are not handled using Parrot's existing concurrency opcodes like schedule. Here's a PIR example for something that, I think, will perform an asynchronous file write according to the specification in the PDD:

$P0 = open "/path/to/file.txt", "w"
$P1 = find_global("io_callback_sub")
$P2 = print $P0, "hello world", $P1

In the example above, $P0 is the FileHandle PMC that we are writing to, $P1 is the callback subroutine, and $P2 is the IO request status object that keeps track of the status of the request. The PDD says that there should be a division between the synchronous and asynchronous opcodes. However, on Windows platforms at least the file handle will need to be opened in asynchronous mode before any asynchronous operations can be performed on it. I don't see any real way to avoid immediate unification in this case, unless:

1. The print opcode closes the filehandle and reopens it in asynchronous mode (bad)
   
2. We add an additional specifier to the open opcode that specifies that the file handle should be opened in asynchronous mode ("wn" would be "write, non-blocking", for instance).
3. We always open file handles in asynchronous mode and just implement all the blocking opcodes in terms of underlying asynchronous operations.

I like idea #3 the best personally, but I imagine there is going to be some significant support for #2 as well. I'm just worried about cases where a non-asynchronous filehandle object is passed to an asynchronous opcode, or any other related combination of things that can and will happen.

Here are some notes that I'm following in general (I will discuss some caveats below):

1. All streams are opened in asynchronous mode by default, except for streams that don't support it.
2. Asynchronous opcodes will accept as a callback either a Sub, a Continuation, or PMCNULL. In the case of a Sub, the opcode will perform asynchronously and call the sub in a separate thread when an event occurs. If it's a Continuation, the operation will block until completed and then resume execution at the Continuation. If PMCNULL, it will launch the asynchronous request and ignore any results.
3. We need to create a new PMC for the AIO status object. I'm thinking we call it "IORequest". The IORequest object will have interfaces to check for the current status (in progress, complete, error) and the result (number of bytes read/written on success). I am not sure how we will handle errors, there are a few options for this that I won't talk about here.
   

The problem with this approach that I can see is that nowhere in here do we interact with the concurrency scheduler at all, unless the C-level callback function of the request schedules the PIR-level callback Task instead of executing it directly, or for systems that don't support AIO directly and we need to fudge it. Relying on the direct callbacks is definitely better performance-wise then polling a result flag internally. However, I've been told now by a handful of people that the better way to go in Linux anyway is probably a poll loop using epoll anyway.

An alternative idea, that I personally like less but which might cause fewer headaches, would be to create the IORequest object as a simple flag accessor. The scheduler would need to poll the pending requests regularly (using epoll in linux and an IO Completion Port in Windows) and when it finds one that needs handling, it would update the flag in the IO request object and schedule the callback for us (if one is provided). The difference to this approach, of course, is who is checking the status and who is scheduling the callback (kernel vs Parrot). I feel like this way is going to have a lot of performance drawbacks, but then again the biggest performance drawback in any IO system isn't going to be the callback scheduler anyway. The differences might be negligible.

So we don't even know how we're going to do simple read/write operations yet, but we might be able to nail down the specifics of a few other tasks. A listener object or a Select/Poll object for instance might be registered with the scheduler to repeatedly check their status and call callbacks when an incoming event occurs. This would be useful on a server-side network app where we could listen on an array of sockets for incoming data passively and let the scheduler take care of checking flags and scheduling callbacks.

Here's a straight-forward example of code to create a passive listener (which some Unix/Perl folk would probably prefer we called "Select") PMC which calls a callback when an incoming event occurs:

$P0 = new 'Socket'
# ... Connect the socket here
$P1 = new 'IOListener'
push $P1, $P0
schedule $P1

So at the end of that snippet, we have a listener object in the the scheduler. The scheduler will poll the IOListener, which in turn will poll the Socket and all other PMCs that it contains, and for every event that it finds it will add the corresponding callback to the scheduler for execution.

So the PDD definitely offers a nice base to start working on, but there are a ton of questions to be answered about some of the implementation specifics. We'll know as we start breaking ground and writing code what does work and what doesn't. I'm sure I'll be reporting on these issues as they arise.

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.