Blog Closed

This blog has moved to Github. This page will not be updated and is not open for comments. Please go to the new site for updated content.

Monday, May 11, 2009

Reading Data from the Serial Port

At work I'm building a program that is, in part, a serial port console like HyperTerminal. It's not a pure drop-in replacement, we have some specific requirements that HyperTerminal didn't quite meet. However, a lot of the port-handling logic in my program could probably be repurposed for creating a more faithful drop-in replacement if the need arose.

The biggest problem for me at the beginning was deciding how to read data from the port. Obviously, we can't do the reading synchronously, in the case of a TTY-like program that just doesn't make any sense. I had two real options for asychronous operation:
  1. Create a worker thread that reads from the port, sleeps for a certain timeout, and then repeats.
  2. Use the DataReceived handler on the SerialPort object to automatically call a callback when incoming data is received.
People who read my discussion about AIO in Parrot will probably recognize that item #1 does not appeal to me at all. First there is the issue of synchronizing the thread and getting it to start and stop when I need it to do each. I also need to be able to pass settings to the reader, which would require cross-thread synchronization logic that could get really messy really quickly. Plus, if we have a thread timeout of 1second for example, there could be up to a one second delay between the time data is received and when it becomes visible to the user. We could easily set a timeout to zero seconds, but then we have a background thread endlessly looping over the port, usually reading nothing. Not exactly a performance killer, but still needlessly wasteful. Nothing we are doing is so time-critical that a 1second sleep timer for instance between reads would kill us, but it's still a clunky-feeling mechanism that will make the interface look amateur.

On top of all those reasons, as if I need another one, I feel like using an explicitly-managed thread here is a particularly inelegant solution. In short, I decided to use the DataReceived event handler to do my port reading (when I put my port into asynchronous read mode, that is).

That question out of the way, I needed to decide how to do input buffering. Do I buffer by line (SerialPort.ReadLine), "buffer" by character (SerialPort.ReadChar), or do I not buffer (SerialPort.ReadExisting)? On the one hand I need to support both buffered and non-buffered input. On the other hand I don't want to be stacking up DataReceived events with Timeout events endlessly, because that could create a stability problem.

My design goes as follows: I use the DataReceived event handler to signal me when data is ready. From within the handler I use SerialPort.ReadExisting to read the incoming data into a buffer, and from there slice and dice the input into the forms needed by modules higher up in my program. I admit that this may not be the most attractive or elegant code I have ever written, but it has demonstrated itself to be very performant and robust solution for my needs:
private string readBuffer;
private SerialPort port;
private bool unBuffNeedNewline = false;

private void InitPort()
{
this.port = new SerialPort();
this.port.DataReceived += new SerialDataReceivedHandler(DataReceiver_Handler);
}

private void DataReceiver_Handler(object sender, SerialDataReceivedEventArgs e)
{
if(this.bufferMode == ConnectionHelpers.ReadBuffering.LineBuffered)
this.DataReceiverLineBuffered();
else
this.DataReceiverCharBuffered();
}

private void DataReceiverLineBuffered()
{
try {
string x;
lock(this.readBuffer) {
x = this.readBuffer + this.port.ReadExisting();
}
char[] delim = new char[2] {'\n', '\r'};
while(x.Length > 1 && (x.Contains("\n") || x.Contains("\r"))) {
String[] ary = x.Split(delim, 2);
this.ReadHandler(ary[0], true);
x = ary[1] + this.port.ReadExisting();
}
lock(this.readBuffer) {
this.readBuffer = x;
}
} catch(Exception e) {
this.StatusReporter("Serial Read Error: " + e.ToString());
}
}

private void DataReceiverCharBuffered()
{
try {
string x;
lock(this.readBuffer) {
x = this.readBuffer + this.port.ReadExisting();
}
while(x.Length >= 1) {
string c = x.Substring(0, 1);
if(c == "\r" || c == "\n") {
this.unBuffNeedNewline = true;
x = x.Substring(1) + this.port.ReadExisting();
}
else if(this.unBuffNeedNewline) {
this.ReadHandler("", true);
this.unBuffNeedNewline = false;
} else {
this.ReadHandler(c, false);
x = x.Substring(1) + this.port.ReadExisting();
}
}
} catch(Exception e) {
this.StatusReporter("Serial Read Error: " + e.ToString());
}
}


The function "ReadHandler" takes two arguments: The string value that's read (without carriage return or linefeed characters) and a boolean value indicating whether the given string is followed by a newline or not. Further up the call chain the display function will take that information to display timestamps and do other per-line formatting fanciness. It's worth noticing that since we are calling from within an event handler, ReadHandler probably needs to call BeginInvoke to pass it's incoming data to the GUI (that's what my code does, anyway).

The way I lock the readBuffer repeatedly was something that I figured out later. When data is incoming quickly (like 115200 baud or higher) we can get multiple DataReceived events being triggered and stacking up if we lock through the entire function. This can cause noticeable program slowdowns when a number of event handlers acquire the lock subsequently. Instead, I lock smaller parts of the code and let additional handler instances run concurrently but with no input. Throughput performance is better in these cases, and is not noticeably different otherwise.

So that's my implementation of a buffered asynchronous serial port reader in C#. It's not perfect, but it gets the job done, has pretty good throughput, and is relatively fault tolerant.

Sunday, May 10, 2009

Turning Contexts into PMCs

I merged the GC branch in yesterday, and though the work wasn't without it's issues the GC API is now in a much better condition then it has been. That out of the way, and AIO still on the back burner, it's time to start looking towards the next project in my list.

This week, the project is converting Parrot's context structures, which at the moment are just normal C structures, into garbage-collectable "Context" PMCs. TT #596 contains some information about the work, although it's currently very sparse. This is not a new idea by any stretch: I've been thinking about it since last summer when I was doing my GC work, and my ambitions were so high I was convinced that all memory allocations in Parrot could be done through the GC—I still think that, but I'm more humbled by the sheer amount of effort required to make that happen. Not only does this project make it easier to manage contexts without all sorts of manual reference counting, there is also going to be a lot of potential for streamlining and optimizing parts of the codebase.

Parrot_Context structures form a linked list of sorts that represent the current calling context and all parent contexts. The context structure contains the array of I, N, S, and P registers too. It also contains a few data fields to help manage the CPS calling system. In short, Contexts are pretty central to Parrot and are very important.

The calling conventions system as it currently stands is pretty inefficient and messy. This isn't a new sentiment, I've blogged about it before (although I can't find a link right now). There are about half a dozen different ways to execute a PIR subroutine, many of those have multiple special-purpose interfaces. Allison is doing some great work in getting things to be more unified, and once she gets her work merged into trunk we will be able to start optimizing the new unified pipeline. A major part of those optimizations is going to be converting Contexts into PMCs.

For an idea of why, consider what happens in the unified calling path when we make a call (note that these aren't exactly in order):
  1. Arguments come in as an array, either as a va_list variadic argument array or as an opcode_t* serialization in bytecode. We also get an invocant object (if any) and a return address. The reason for the difference here is because we can be invoking a subroutine from PIR (via the invoke opcode) or via C (using Parrot_pcc_invoke_from_sig_object)
  2. Arguments and the invocant are added into a CallSignature PMC, which needs to be allocated and initialized.
  3. A new context is created, initialized, and a reference is made to it.
  4. The arguments from the CallSignature PMC are added into the registers of the Context
  5. The invocant, if any, is extracted from the CallSignature PMC and put into the interpreter structure as the current "self".
  6. A new RetContinuation PMC is created to handle a return call and stored in the Context.
  7. Using a series of Call_State structures, and a long loop, extract arguments from the context registers and associate them with parameters in the called sub.
RetContinuations are like Continuations, but single-purpose and lighter-weight, and they're only really used in these cases to provide the behavior of the "return" opcode. If Contexts are a PMC type, we can combine this with the RetContinuation PMC, since the later is never really used without the former. This kills step # 6 in the list above. We can then combine the Context PMC with the CallSignature PMC (since again, the one is almost never used without the other), we can get rid of steps 3, 4, and 5. Finally, combining the Call_State structure with the Context PMC and creating a custom iterator for it will leave us with only this:
  1. Arguments come in as an array, either as a va_list variadic argument array or as an opcode_t* serialization in bytecode. We also get an invocant object (if any) and a return address.
  2. The arguments, the invocant, and the return address are added to the Context PMC
  3. A custom iterator is created for the Context PMC and the subroutine parameters are extracted from it directly.
Quite a bit more streamlined, no? In addition to having fewer steps in the algorithm we also have a number of other significant savings: Fewer PMC allocations, Context PMCs can be allocated from Parrot's memory pools instead of needing to be malloc'd from the OS, and a large number of copying operations can be avoided since the data is put into one place and kept there. Plus, since the Context PMC would suddenly become garbage collectable, we can get rid of all the reference-counting code, and the custom GC hooks to clean up dead context memory. This is only just the beginning, there are major optimizations to be had throughout Parrot once this change happens. It all starts with turning contexts into PMCs though.

Some of my recent work on the GC API refactor has really exposed the current Context system API, and has made it easier to pull individual functions out into the new Context PMC VTABLEs. This is going to be a big project, but it's not unmanageably big. I'm probably going to get started on this work sometime after the next release (which is going to be on May 19th I think). I'll definitely be planning and prototyping before that, however.

Saturday, May 9, 2009

Parrot GC Refactor work

I spent a lot of time yesterday and this morning working on the GC API refactor for Parrot, and I've made some pretty good progress so far. One cool result from this work is that I am finding all sorts of places where the GC internal data structures were being manipulated throughout the codebase, some instances of which are very likely to have been causing the problems I experienced over the summer.

That aside, I'm pleased to say that this morning I managed to get the GC almost entirely properly encapsulated. All external-facing GC functions are in the API, and all other functions are kept private. In addition, data structures like struct Arenas, struct Small_Object_Pool and struct Small_Object_Arena are now only accessible from within the GC subsystem. This prevents the rest of Parrot from monkeying around in these structures, but also makes it easier for alternate GC cores to redefine them as necessary. The API isn't particularly clean or elegant right now, but it is encapsulated and that's a start. It's certainly more then we've had since I've been a Parroteer.

The downside to this work is that the number of functions in the GC API has increased pretty substantially, both from creating new functions and by moving old functions into it. Many of the new functions are simple accessors for internal datastructures. I've managed not to have all the new functions listed as "PARROT_EXPORT", which is a win for dynamic link time, so thats good at least. Some of the macros that controlled blocking and unblocking the GC are now redefined as API functions, which is something I've wanted to do for a long time now.

In my last GC post I guessed at which functions would be necessary in the API. Now that I've finished encapsulating it, I can tell you what functions are actually in the API now:
  1. Function to mark an object as being alive.
  2. Functions to initialize and deinitialize the GC subsystem.
  3. Functions to perform mark/sweep and compact actions
  4. Functions to manipulate pools between interpreters, such as merging pools, moving shared objects between pools, etc.
  5. Header allocation functions for PMCs, STRINGs, and other Buffer-like objects (ListChunks, Stack_Chunks, etc).
  6. Header reclamation functions to take unused PMCs, STRINGs, and other Buffer-like objects and add them back to the free list.
  7. Functions to add extension objects (pmc_ext and Sync) to existing PMCs, and functions to remove them again.
  8. Memory block allocation functions for allocating buffers of arbitrary sizes, such as storage for STRINGs. Also, functions to deallocate these memory blocks, and functions to resize them.
  9. Functions to determine if a given pointer is in a particular pool
  10. Functions to block and unblock various GC phases, and functions to determine if they are blocked currently
  11. Accessor functions to get information from the Arenas structure.
  12. Function to mark PMCs that need timely destruction
So this is a basic list of the things we have in the API right now. I'm sure there are more features we would like to add here eventually, but these are the operations that are currently used by the rest of Parrot from the GC.

I'm still not entirely happy with the encapsulation status as it stands now. There are a few places such as the freeze/thaw subsystem where accesses are made to the memory system internals that I really wish weren't being made. But, that's a relatively small issue because most of those routines happen at interpreter destruction time after the GC has already been blocked/finalized.

I want to get my branch merged back into trunk soon. I've hit a good milestone now and I don't want this branch to live for too long lest new problems arise. Probably some small cleanup and documentation work to do first, but it's not far off now.

Friday, May 8, 2009

Darbelo's New Blog

Darbelo, the GSOC student that I am backup-mentoring, has finally started his blog. The blog will be used throughout the summer to post updates about his project. I can say that his progress so far is pretty fantastic, and some initial prototypes of various things are already checked into his googlecode repo.

It's going to be an interesting project to watch, and the stage is set for a pretty exciting and productive summer.

Inheritable Menus in C#

I've been coding a program at work that is supposed to interface with and control a wireless sensor network. It's a heterogeneous network where each node may be one of several different types with different capabilities, represented internally by child classes of an abstract "WirelessSensorNode" parent class. To keep track of things, I display all the nodes and their children (things, including other nodes that connect through them) in a TreeView.

The problem I ran into was trying to create a context menu that would be displayed when I right-clicked on a TreeNode in the tree. Because each node class was different, I needed to display slightly different menus for each. I started the naive way, trying to create a new ContextMenuStrip item for each different class, and I ended up with a huge messy piece of logic like this:

object o = myTreeView.SelectedNode.Tag;
if(o is NodeType1) menu1.Show();
else if(o is NodeType2) menu2.Show();
else if(o is NodeType3) menu3.Show();
...

And each menu, because there were some options common to all nodes, needed to contain some duplicate logic. This was, in short, a mess and extending this system to add new node types (and therefore new menus) was a real pain. What I really wanted to do was something like this, and leave the logic of menu building to the classes themselves:

WirelessSensorNode n = (WirelessSensorNode)myTreeView.SelectedNode.Tag;
ContextMenuStrip menu = n.GetContextMenu();
if(menu != null) menu.Show();

So I decided instead to fix this system up yesterday to do the right thing in a better and more encapsulated way. The node classes themselves know what menu items they are capable of showing, my GUI should not be in charge of figuring that information out. So, I added this code to create a new attribute type, ContextMenuHandler for methods in a class, and a routine to read all methods with this attribute and add them to a menu:
[AttributeUsage(AttributeTargets.Method, AllowMultiple=true)]
public class ContextMenuHandler : Attribute
{
public string name;
public ContextMenuHandler(string name)
{
this.name = name;
}
}

public static void AddContextMenuHandlers(System.Type c, object parent, ContextMenuStrip menu)
{
BindingFlags flags = BindingFlags.NonPublic | BindingFlags.DeclaredOnly |
BindingFlags.Instance;
foreach (MethodInfo method in c.GetMethods(flags)) {
foreach(object attribute in method.GetCustomAttributes(
typeof(ContextMenuHandler), false)) {
string name = ((ContextMenuHandler)attribute).name;
menu.Items.Add(new ToolStripMenuItem(name, null, new EventHandler(
delegate(object o, EventArgs e) {
method.Invoke(parent, null);
}
)));
}
}
}


And I added this code into the abstract parent class:

public virtual ContextMenuStrip GetContextMenu()
{
ContextMenuStrip menu = new ContextMenuStrip();
Helpers.AddContextMenuHandlers(typeof(WirelessSensorNode), this, menu);
Helpers.AddContextMenuHandlers(this.GetType(), this, menu);
return menu;
}


Not a whole lot of code to write for the flexibility that the system gives me. For people who aren't familiar with attributes, they are metadata items that can be added to methods (or other things) and can be examined at runtime using reflection. With this system, to add a new item to the menu of a particular class, I only need to create a new private method in that class with the ContextMenuHandler attribute:

[ContextMenuHandler("Menu Item 1")]
private void Menu_Item_1_ContextMenuHandler()
{
MessageBox.Show("You clicked 'Menu Item 1'");
}


No need to "install" the new menu item anywhere, the simple existance of this method in the class will enable the item to be shown in that menu. This is great for encapsulation because I don't want to be having to modify all sorts of existing code, especially not unrelated existing code, every time I want to add an option to my right-click menu. Plus, it gives me the ability to inherit menu items from the parent class into the menus of the child types, without having to write code in each child class to duplicate them!

There are some limitations to this method, obviously my class hierarchy is only 2-levels deep so this method as-is doesn't extend to arbitrarily deep class hierarchies. I'm sure it could be extended to do that with a little bit more System.Reflection magic, but I don't need to do it so I'm not going to spend the time. Despite the limitations my goals were met: context menus are inherited between classes, and I can edit/expand menus without having to modify all sorts of existing, working code.

Wednesday, May 6, 2009

Switching Gears: GC

I talked briefly with Allison today via email, and decided that the best idea for me is to switch gears and not focus on the Asynchronous IO system just yet. Though I've been trying to keep it out of my mind for a little while the GC really is the most pressing need we have right now, so I'm going to start working on that instead of the AIO system, for now. Given several projects that I am both willing and able to work on, I will tend to work on the one that's the most needed by the project at large. I say "tend" because this is far from a hard-and-fast rule, but it does explain why I am willing to change focus in this case so readily.

My loyal followers (the null set) will remember back to last summer when I was working on a new GC system for Parrot as part of the Google Summer of Code project. People should also remember that my project was ultimately unsuccessful: I was not able to produce a GC that ran reliably. Part of it was my fault, the GC turns out to have been a bigger problem then I was capable of building successfully at that time. However, we've also learned the lesson that Parrots GC API is particularly messy and needs to be cleaned significantly before we can make another honest attempt at an improved GC core.

My task, should I choose to accept it, is to clean up the GC API so we can eventually have pluggable GC cores. This is going to be a bigger task then most people realize, for a variety of reasons. The current GC is intimately intertwined through the whole codebase. There isn't clear encapsulation between the GC and other parts of the system, and as a consequence it's almost impossible to create a new GC core because we don't even know what all the old core is doing (and where it's doing it at).

What we need to define is:
  1. What interface functions (and macros) the GC should provide to do it's work.
  2. What functions from the rest of Parrot the GC is permitted to call. This should be a very small subset of all functions Parrot provides.
  3. What data structures the GC provides for access by the rest of the system.
  4. What data structures the GC is allowed access to.
Not a small task at all but potentially a very rewarding one if it's done right.

Yesterday I created the "gc_api" branch to start the work, and my first task is to rename of the functions from "foo" to "Parrot_gc_foo" following the naming convention used by the rest of the Parrot subsystems. This isn't going to be a simple prefixing operation, some functions are going to be completely renamed to be more honest about what they do.

Next task is to work out what functions the GC needs to provide and export to the rest of the system. These functions will be located in src/gc/api.c only. Any function not in that file will not be intended for use by the rest of Parrot. Here is a partial list off the top of my head of functions that I think the GC needs to provide:
  1. Initialize and Deinitialize the system
  2. Allocate new STRING and PMC structures from the proper pools
  3. Allocate new pmc_ext and sync structures (or, given a PMC, append these structures to it)
  4. Allocate new raw data items from the fixed-size pools (or from the system, or whatever)
  5. Mark an object as being "alive"
  6. Mark an object as being "dead"
  7. Create a new pool
  8. Perform a mark phase
  9. Perform a sweep phase
  10. Perform a combined mark/sweep collection run.
There are probably a few more basic operations that I am forgetting right now, and there are definitely some "wishlist" items that I'm not mentioning here too for brevity. This does seem like a reasonably complete yet concise interface for the GC to implement. I'll post updates as my work progresses.

Tuesday, May 5, 2009

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.