Isn’t the whole system just a database? – libdrm

Do enough programming, and everything looks like a database of one form or another. Case in point, when you want to get keyboard and mouse input, you first have to query the system to see which of the /dev/input/eventxxx devices you want to open for your particular needs. Yes, there are convenient shortcuts, but that’s beside the point.

Same goes with other devices in the system. This time around, I want to find the drm device which represents the graphics card in my system (from the libdrm perspective).

In LJIT2libudev there are already objects that make it convenient to enumerate all the devices in the system using a simple iterator:

local ctxt, err = require("UDVContext")()
for _, dev in ctxt:devices() do
    print(dev)
end

Well, that’s find and all, but let’s get specific. To use the libdrm library, I very specifically need one of the active devices in the ‘drm’ subsystem. I could write this:

local ctxt, err = require("UDVContext")()

local function getActiveDrm()
  local function isActiveDrm(dev)
    if dev.IsInitialized and dev:getProperty("subsystem") == "drm" then
      return true;
    end

    return false;
  end

  for _, dev in ctxt:devices() do
    if isActiveDrm(dev) then
      return dev;
    end
  end

  return nil;
end

local device = getActiveDrm()

Yah, that would work. Then of course, when I want to change the criteria for finding the device I’m looking for, I would change up this code a bit. The core iterator is the key starting point at least. The ‘isActiveDrm()’ is a function which acts as a predicate to filter through the results, and only return the ones I want.

Since this is Lua though, and since there is a well throught out functional programming library already (luafun), this could be made even easier:

local function isActiveDrm(dev)
  if dev.IsInitialized and dev:getProperty("subsystem") == "drm" then
    return true;
  end

  return false;
end

local device = head(filter(isActiveDrm, ctxt:devices()))
assert(device, "could not find active drm device")

In this case, we let the luafun ‘filter’ and ‘head’ functions do their job of dealing with the predicate, and taking the first one off the iterator that matches and returning it. Now, changing my criteria is fairly straight forward. Just change out the predicate, and done. This is kind of nice, particularly with Lua, because that predicate is just some code, it could be generated at runtime because we’re in script right?

So, how about this version:

-- File: IsActiveDrmDevice.lua
-- predicate to determine if a device is a DRM device and it's active
return function(dev)
  if dev.IsInitialized and dev:getProperty("subsystem") == "drm" then
    return true;
  end

  return false;
end

-- File: devices_where.lua
#!/usr/bin/env luajit

-- devices_where.lua
-- print devices in the system, filtered by a supplied predicate
-- generates output which is a valid lua table
package.path = package.path..";../?.lua"

local fun = require("fun")()
local utils = require("utils")

local ctxt, err = require("UDVContext")()
assert(ctxt ~= nil, "Error creating context")

if #arg < 1 then
  error("you must specify a predicate")
end

local predicate = require(arg[1])

print("{")
	
each(utils.printDevice, filter(predicate, ctxt:devices()))

print("}")


-- Actual usage from the command line
./devices_where.lua isActiveDrmDevice

In this case, the ‘query’ has been generalized enough such that you can pass a predicate as a filename (minus the ‘.lua’). The code for the predicate will be compiled in, and used as the predicate for the filter() function. Well, that’s pretty nifty I think. And since the query itself again is just a bit of code, that can be changed on the fly as well. I can easily see a system where lua is the query language, and the entire machine is the database.

The tarantool database is written in Lua, and I believe the luafun code is used there. Tarantool is not a system database, but the fact that it’s written in Lua itself is interesting, and just proves the case that Lua is a good language for doing some database work.

I have found that tackling the lowest level enumeration by putting a Lua iterator on top of it makes life a whole lot easier. With many of the libraries that you run across, they spend a fair amount of resources/code on trying to make things look like a database. In the case of libudev, there are functions for iterating their internal hash table of values, routines for creating ‘enumerators’ which are essentially queries, routines for getting properties, routines for turning properties into more accessible strings, routines for turning the ‘FLAGS’ property into individual values, and the like, and then there’s the memory management routines (ref, unref). A lot of that stuff either goes away, or is handled much more succinctly when you’re using a language such as Lua, or JavaScript, or Python, Ruby, whatever, as long as it’s modern, dynamic, and has decent enough higher level memory managed libraries.

And thus, the whole system, from log files, to perf counters, to device lists, is a database, waiting to be harvested, and made readily available.


Functional Programming with libevdev

Previously, I wrote about the LuaJIT binding to libevdev: LJIT2libevdev – input device tracking on Linux

In that case, I went over the basics, and it all works out well, and you get get at keyboard and mouse events from Lua, with very little overhead.  Feels natural, light weight iterators, life is good.

Recently, I wanted to go one step further though.  Once you go down the path of using iterators, you begin to think about functional programming.  At least that’s how I’m wired.  So, I’ve pushed it a bit further, and incorporated the fun.lua module to make things a bit more interesting.  fun.lua provides things like each, any, all, map, filter, and other stuff which makes dealing with streams of data really brainlessly simple.

Here’s an example of spewing out the stream of events for a device:

 

package.path = package.path..";../?.lua"

local EVEvent = require("EVEvent")
local dev = require("EVDevice")(arg[1])
assert(dev)

local utils = require("utils")
local fun = require("fun")

-- print out the device particulars before 
-- printing out the stream of events
utils.printDevice(dev);
print("===== ===== =====")

-- perform the actual printing of the event
local function printEvent(ev)
    print(string.format("{'%s', '%s', %d};",ev:typeName(),ev:codeName(),ev:value()));
end

-- decide whether an event is interesting enough to 
-- print or not
local function isInteresting(ev)
	return ev:typeName() ~= "EV_SYN" and ev:typeName() ~= "EV_MSC"
end

-- convert from a raw 'struct input_event' to the EVEvent object
local function toEVEvent(rawev)
    return EVEvent(rawev)
end


fun.each(printEvent, 
    fun.filter(isInteresting, 
        fun.map(toEVEvent,
            dev:rawEvents())));

 
The last line there, where it starts with “fun.each”, can be read from the inside out.

dev:rawEvents() – is an iterator, it returns a steady stream of events coming off of the specified device.

fun.map(toEVEvent,…) – the map function will take some input, run it through the provided function, and send that as the output. In functional programming, this would be transformation.

fun.filter(isInteresting, …) – filter takes an input, allplies the specified predicate, and allows that item to pass through or not based on the predicate returning true or false.

fun.each(printEvent, …) – the ‘each’ function takes each of the items coming from the stream of items, and applies the specified function, in this case the printEvent function.

This is a typical pull chain. The events are pulled out of the lowest level iterator as they are needed by subsequent operations in the chain. If the chain stops, then nothing further is pulled.

This is a great way to program because doing different things with the stream of events is simply a matter of replacing items in the chain. For example, if we just want the first 100 items, we could write

each(printEvent, 
    take_n(100, 
      filter(isInteresting, 
        map(toEVEvent, dev:rawEvents()))));

You can create tees, send data elsewhere, construct new streams by combining streams. There are a few key operators, and with them you can do a ton of stuff.

At the very heart, the EVDevice:rawEvents() iterator looks like this:

function EVDevice.rawEvents(self)
	local function iter_gen(params, flags)
		local flags = flags or ffi.C.LIBEVDEV_READ_FLAG_NORMAL;
		local ev = ffi.new("struct input_event");
		--local event = EVEvent(ev);
		local rc = 0;


		repeat
			rc = evdev.libevdev_next_event(params.Handle, flags, ev);
		until rc ~= -libc.EAGAIN
		
		if (rc == ffi.C.LIBEVDEV_READ_STATUS_SUCCESS) or (rc == ffi.C.LIBEVDEV_READ_STATUS_SYNC) then
			return flags, ev;
		end

		return nil, rc;
	end

	return iter_gen, {Handle = self.Handle}, state 
end

This is better than the previous version where we could pass in a predicate. In this case, we don’t even convert to the EVEvent object at this early low level stage, because we’re not sure what subsequent links in the chain will want to do, so we leave it out. This simplifies the code at the lowest levels, and makes it more composable, which is a desirable effect.

And so it goes. This binding started out as a simple ffi.cdef hack job, then objects were added to encapsulate some stuff, and now the iterators are being used in a functional programming style, which makes the whole thing that much more useful and integratable.


LJIT2libevdev – input device tracking on Linux

Once you start going down into the rabbit hole that is UI on Linux, there seems to be no end. I was wanting to get to the bottom of the stack as it were, because I just want to get raw keyboard and mouse events, and do stuff with them. There is a library that helps you do that call libevdev. Here is the luajit binding to it:

LJIT2libevdev

As it turns out, getting keyboard and mouse activity is highly dependent on what environment you’re in of course. Are you sitting at a Terminal, in which cases ncurses or similar might be your best choice. If you’re looking at a graphics display, then something related to X, or the desktop manager might be appropriate. At the very bottom of it all though is the kernel, and it’s ability to read the keyboard and mouse, and report what it finds up the chain to interested parties. Down there at the very bottom is a userspace library libevdev, which takes care of making the ioctl calls into the kernel to get the raw values. Great! Only caveat is that you need to be setup with the proper permissions to do it because you’re getting ALL of the keyboard and mouse events on the system. Great for key loggers…

Alright, so what does this mean in the context of Lua? Well, libevdev is a straight up C interface to which is a very thin veneer atop the ioctl calls. It would not be that hard to actually replace the ioctl calls with ioctl calls from luajit directly, but the maintainers of libevdev seem to have it covered quite nicely, so ffi calls to the library are sufficient. The library provides some conveniences like tables of strings to convert from the integer values of things to their string name equivalents. These could probably be replaced with the same within lua land, and save the round trips and string conversions. As a low level interface, it does not provide managedment of the various input devices. You can not ask it “give me the logitech mouse”. You have to know which device is the mouse in the first place before you can start asking for input. Similarly, it’s giving you a ton of raw data that you may not be interested in. Things like the sync signals, indicating the end of an event train. Or the skipped data events, so you can catch up if you prefer not to lose any. How to manage it all?

Let’s start at the beginning.

I have found it challenging to find appropriate discussions relating to UI on Linux. Linux has such a long history, and for most of it, the UI subsystems have been evolving and changing in fundamental ways. So, as soon as you find that juicy article dated from 2002, it’s been replaced by something in 2006, and then again in 2012. It also depends on whether you’re talking about X11, Wayland, Qt, Gnome, SDL, terminal, or some other context.

Recently, I was trying to track down the following scenario: I want to start reading input from the attached logitech mouse on my laptop. Not the track pad under my thumbs, and not the little red nubby stick in the middle of the keyboard, but that mouse specifically. How do I do that?

libevdev is the right library to use, but in order to use it, you need a file descriptor for the specific device. The interwebs tell me you simply open up the appropriate /dev/input/eventxxx file and start reading from it? Right. And how do I know which is the correct ‘eventxxx’ file I should be reading from? You can simply do:

$ cat /proc/bus/input

Look at the output, find the device you’re interested in, look at which event it indicates it’s attached to, then go open up that event…

And how do I do that programatically, and consistently such that it will be the same when I move the mouse to a different system? Ah yes, there’s a library for that, and why don’t you just use Python, and…

Or, how about this:

local EVContext = require("EVContext")

local function isLogitech(dev)
    return dev:name():lower():find("logitech") ~= nil
end

local dev = EVContext:getMouse(isLogitech);

assert(dev, "no mouse found")

print(string.format("Input device name: \"%s\"", dev:name()));
print(string.format("Input device ID: bus %#x vendor %#x product %#x\n",
        dev:busType(),
        dev:vendorId(),
        dev:productId()));

-- print out a constant stream of events
for _, ev in dev:events() do
    print(string.format("Event: %s %s %d",
        ev:typeName(),
        ev:codeName(),
        ev:value()));
end

How can I get to this state? First, how about that EVContext thing, and the ‘getMouse()’ call?

EVContext is a convenience class which wraps up all the things in libevdev which aren’t related to a specific instance of a device. So, doing things like iterating over devices, setting the logging level, getting a specific device, etc. Device iteration is a core piece of the puzzle. So, here it is.

function EVContext.devices(self)
    local function dev_iter(param, idx)
        local devname = "/dev/input/event"..tostring(idx);
        local dev, err = EVDevice(devname)

        if not dev then
            return nil; 
        end

	return idx+1, dev
    end

    return dev_iter, self, 0
end

That’s a quick and dirty iterator that will get the job done. Basically, just construct a string of the form ‘/dev/input/eventxxx’, and vary the ‘xxx’ with numbers until you can no longer open up devices. For each one, create a EVDevice object from that name. A bit wasteful, but highly beneficial. Once we can iterate all the input devices, we can leverage this for greater mischief.

Looking back at our code, there was this bit to get the keyboard:

local function isLogitech(dev)
    return dev:name():lower():find("logitech") ~= nil
end

local dev = EVContext:getMouse(isLogitech);

It looks like we could just call the ‘EVContext:getMouse()’ function and be done with it. What’s with the extra ‘isLogitech()’ part? Well, on its own, getMouse() will simply return the first device which reportedly is like a mouse. That code looks like this:

function EVDevice.isLikeMouse(self)
	if (self:hasEventType(EV_REL) and
    	self:hasEventCode(EV_REL, REL_X) and
    	self:hasEventCode(EV_REL, REL_Y) and
    	self:hasEventCode(EV_KEY, BTN_LEFT)) then
    	
    	return true;
    end

    return false;
end

It’s basically saying, a ‘mouse’ is something that has relative movements, at least an x and y axis, and a ‘left’ button. On my laptop, the little mouse nub on the keyboard qualifies, and since it has a lower /dev/input/event number (3), it will be reported before any other mouse on my laptop. So, I need a way to filter on anything that reports to be a mouse, as well as having “logitech” in its name. The code for that is the following from EVContext:

function EVContext.getDevice(self, predicate)
	for _, dev in self:devices() do
		if predicate then
			if predicate(dev) then
				return dev
			end
		else
			return dev
		end
	end

	return nil;
end

function EVContext.getMouse(self, predicate)
	local function isMouse(dev)
		if dev:isLikeMouse() then
			if predicate then
				return predicate(dev);
			end
			
			return true;
		end

		return false;
	end

	return self:getDevice(isMouse);
end

As you can see, ‘EVContext:getDevice()’ takes a predicate (a function that returns true or false). It will iterate through all the devices, applying the predicate to each device in turn. When it finds a device matching the predicate, it will return that device. Of course, you could easily change this to return ALL the devices that match the predicate, but that’s a different story.

The ‘predicate’ in this case is the internal ‘isMouse’ function within ‘getMouse()’, which in turn applies two filters. The first is calling the ‘isLikeMouse()’ function on the device. If that’s satisfied, then it will call the predicate that was passed in, which in this case would be our ‘isLogitech()’ function. If that is satisfied, then the device is returned.

In the end, here’s some output:

Input device name: "Logitech USB Optical Mouse"
Input device ID: bus 0x3 vendor 0x46d product 0xc018

Event: EV_REL REL_Y -1
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_Y -1
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_X -1
Event: EV_REL REL_Y -2
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_Y -1
Event: EV_SYN SYN_REPORT 0
Event: EV_MSC MSC_SCAN 589827
Event: EV_KEY BTN_MIDDLE 1
Event: EV_SYN SYN_REPORT 0
Event: EV_MSC MSC_SCAN 589827
Event: EV_KEY BTN_MIDDLE 0
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_Y -2
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_X 1
Event: EV_SYN SYN_REPORT 0
Event: EV_REL REL_Y -1

Some relative movements, a middle button press/release, some more movement.

The libevdev library represents some pretty low level stuff, and for the moment it seems to be the ‘correct’ way to deal with system level input device event handling. The LJIT2libevdev binding provide both the fundamental access to the library as well as the higher level device access which is sorely needed in this environment. I’m sure over time it will be beneficial to pull some of the conveniences that libevdev provides directly into the binding, further shrinking the required size of the library. For now though, I am simply happy that I can get my keyboard and mouse events into my application without too much fuss.


LJIT2libc – LuaJIT IS “batteries included”

I would say one of the most common complaints about any platform, framework, product is a paucity of available stuff to fiddle about with.  I’ve heard this criticism a few times leveled at the lua world in general.  Fatter frameworks are usually “batteries included”.  That’s great, when you get a whole ton of stuff that makes writing all sorts of apps relatively easy to do right off the bat.  The challenge of “batteries included” is that you get a whole ton of stuff, most of which you will never use, and some of which doesn’t have the best implementation.

Recently, I’ve been doing quite a lot off luajit bindings on the Linux platform:

If you were into anything from ASCII art graphics drivers to raw frame buffer management in a Linux system, these might start to look like batteries.  They’re not included with the luajit compiler, but they’re relatively easy to add.

But, there’s another one that I’ve been playing with recently which I think is even better:

Luajit is typically built and compiled against the libc and libm libraries.  As such, being able to access routines within those libraries comes for ‘free’ from within luajit, courtesy of the ffi capabilities.  This is very interesting because it means these routines, which are already on your system, are in fact just a stones throw away from being available within your app.
Let’s imagine you wanted to write some script like this, using the libc provided ‘puts()’ function:
puts("Hello, World!");

Well, the lua language has its own print routine, so this is a bit contrived, but let’s say you wanted to do it anyway. Well, to make this work, you need access to the function signature for the ‘puts’ routine and you need that to be accessible in the global namespace. So, it would actually look like this:

local ffi = require("ffi")

ffi.cdef("int puts(const char *);");
puts = ffi.C.puts;

puts("Hello, World!")

Great. A bit of work, and now I can program as wrecklessly as I could in C with all the batteries included in the libc and libm libraries. But, it gets tedious having to write that ffi stuff all over the place, so this is where the LJIT2libc thing comes in. It basically goes and implements a ton of the required ffi.cdef statements to make all those functions readily available to your script. An easy way to pull it into any script is to do the following:

local init = require("test_setup")()

puts("Hello, World!");

That first line ‘init = …’ in this case pulls in all of the definitions, and puts them into the global namespace, so that you can simply write your program without having to know anything about the ffi, or where functions come from or anything like that. Just start writing your code knowing that the batteries are already included.

Now, this example might seem too trivial for words, but just think about what’s in a typical libc library. It’s all the file system, sockets, system calls, math, random numbers, everything you’re likely to need to create higher level application stuff. It’s a lot of stuff that other systems end up creating from scratch, as part of their ‘batteries’.

Of course this is trivializing what’s happening in those batteries, because what you’re getting here is the raw C implementations of things, with all the headaches and dangers that are typically associated with writing code at that level. But, for those who want to have access to that level of code, and apply the safety net of lua where they see fit, this is quite a useful tool I think.

In short, batteries ARE included with every luajit. Those batteries might be just anode, cathode, and electrolyte, without the shell, but there are the raw ingredients. Having these wrappers available just makes it that much easier to think about and deal with a lot of low level stuff where I might previously had to resort to some sort of ‘package’ to achieve something as simple as traverse the file system.

So there you have it. luajit is a ‘batteries included’ system.


Dyanmic Programming in C

Certainly there must be a picture?
test_keyboard

This is a simple test app using the graphicc drawproc library.  The app is pretty simple.  It displays a background image, and as you drag the mouse over the image, the location and size of that semi-translucent square is displayed at the bottom of the window on that status line.
Here is the entirety of the program

/*
test_keyboard

Do some simple mouse and keyboard tracking

*/
#include "drawproc.h"
#include "guistyle.h"
#include &lt;stdio.h&gt;

static GUIStyle styler;
static const int gMaxMode = 3;
static int gMode = 0;

pb_rgba fb;
pb_rect keyRect = { 0, 0, 34, 34 };

void  mousePressed()
{
	gMode++;
	if (gMode &gt;= gMaxMode) {
		gMode = 0;
	}
}

void  mouseMoved()
{
	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;
}

void  keyReleased()
{
	switch (keyCode)
	{
	case VK_SPACE:
		write_PPM_binary("test_keyboard.ppm", gpb);
		break;

	case VK_RIGHT: // increase width of keyRect
		keyRect.width += 1;
		break;

	case VK_LEFT:
		keyRect.width -= 1;
		if (keyRect.width &lt; 4) keyRect.width = 4;
		break;
	case VK_UP:
		keyRect.height += 1;
		break;
	case VK_DOWN:
		keyRect.height -= 1;
		if (keyRect.height &lt; 4) keyRect.height = 4;
		break;
	}

	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;

}

// Draw information about the mouse
// location, buttons pressed, etc
void drawMouseInfo()
{
	// draw a white banner across the bottom
	noStroke();
	fill(pWhite);
	rect(0, fb.frame.height + 2, width, 24);


	// draw the key rectangle
	fill(RGBA(255, 238, 200, 180));
	stroke(pDarkGray);
	rect(keyRect.x, keyRect.y, keyRect.width, keyRect.height);

	// select verdana font
	setFont(verdana17);
	char infobuff[256];
	sprintf_s(infobuff, "Mouse X: %3d Y: %3d    Key: (%3f, %3f)(%3.0f, %3.0f)", mouseX, mouseY, keyRect.x, 
		keyRect.y, keyRect.width, keyRect.height);
	fill(pBlack);
	textAlign(TX_LEFT, TX_TOP);
	text(infobuff, 0, fb.frame.height + 2);

}

void draw()
{
	background(pLightGray);
	backgroundImage(&fb);

	drawMouseInfo();
}

void setup()
{
	int ret = PPM_read_binary("c:/repos/graphicc/Test/windows-keyboard-60-keys.ppm", &fb);

	size(fb.frame.width+4, fb.frame.height+4+30);
	background(pLightGray);
}



Of particular note, and what this article is about, are the routines to track the mouse and keyboard actions. Let’s take the mouse movement first of all.

void  mousePressed()
{
	gMode++;
	if (gMode &gt;= gMaxMode) {
		gMode = 0;
	}
}

void  mouseMoved()
{
	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;
}

Basically, every time the mouse moves, the location of the ‘keyRect’ is updated, to reflect the new mouse position. In this case, we have the reported mouse position at the center of that translucent square.

Alright, but who’s calling these routines in the first place? For that we look at the mouse handling within drawproc.cpp


LRESULT CALLBACK mouseHandler(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	switch (message)
	{
		case WM_MOUSEWHEEL:
			if (gmouseOnWheelHandler != nullptr) {
				gmouseOnWheelHandler(); // hWnd, message, wParam, lParam);
			}
		break;


		case WM_MOUSEMOVE:
			mouseX = GET_X_LPARAM(lParam);
			mouseY = GET_Y_LPARAM(lParam);

			if (isMousePressed) {
				if (gmouseOnDraggedHandler != nullptr) {
					gmouseOnDraggedHandler();
				}
			} else if (gmouseOnMovedHandler != nullptr) {
				gmouseOnMovedHandler();
			}
		break;

		case WM_LBUTTONDOWN:
		case WM_MBUTTONDOWN:
		case WM_RBUTTONDOWN:
			isMousePressed = true;
			mouseButton = wParam;

			if (gOnMousePressedHandler != nullptr) {
				gOnMousePressedHandler();
			}
		break;

		case WM_LBUTTONUP:
		case WM_MBUTTONUP:
		case WM_RBUTTONUP:
			isMousePressed = false;

			if (gmouseReleasedHandler != nullptr) {
				gmouseReleasedHandler();
			}
		break;

		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
	}

	return 0;
}

Good good, looks like a typical “Windows” mouse handling routine. But, what of these various global variables?

		case WM_MOUSEMOVE:
			mouseX = GET_X_LPARAM(lParam);
			mouseY = GET_Y_LPARAM(lParam);

			if (isMousePressed) {
				if (gmouseOnDraggedHandler != nullptr) {
					gmouseOnDraggedHandler();
				}
			} else if (gmouseOnMovedHandler != nullptr) {
				gmouseOnMovedHandler();
			}
		break;

In this case, we have mouseX, mouseY, isMousePressed, gmouseOnDraggedHandler , and gmouseOnMovedHandler. That’s a lot of global state. Of particular interest are the two that point to functions, which are gmouseOnDraggedHandler, and gmouseOnMovedHandler. These routines are called whenever there is mouse movement. The one for dragging is called if the additional global variable ‘isMousePressed’ is true.

This is nice because we’re already getting a chance at being ‘dynamic’ because the function calls are not hard coded, which means, those pointers, although they may have started with some value at compile time, can changed dynamically any time during runtime. So, let’s see how they might get set.

Before any actions occur, as part of the initialization for the drawproc routines, there is this series of calls:

void init()
{
	// Setup text
	font_t_init(&gfont, verdana12);
	gTextSize = 10;
	gTextAlignX = TX_LEFT;
	gTextAlignY = TX_TOP;


	
	HMODULE modH = GetModuleHandle(NULL);

	// Keyboard handling routines
	setOnKeyPressedHandler((EventObserverHandler)GetProcAddress(modH, "keyPressed"));
	setOnKeyReleasedHandler((EventObserverHandler)GetProcAddress(modH, "keyReleased"));
	setOnKeyTypedHandler((EventObserverHandler)GetProcAddress(modH, "keyTyped"));

	setKeyboardHandler(keyHandler);


	// Mouse Handling Routines
	setOnMousePressedHandler((EventObserverHandler)GetProcAddress(modH, "mousePressed"));
	setOnMouseReleasedHandler((EventObserverHandler)GetProcAddress(modH, "mouseReleased"));
	setOnMouseMovedHandler((EventObserverHandler)GetProcAddress(modH, "mouseMoved"));
	setOnMouseDraggedHandler((EventObserverHandler)GetProcAddress(modH, "mouseDragged"));

	setMouseHandler(mouseHandler);
}

First of all, ‘GetModuleHandle’ is the way within Windows to get a handle on one of the libraries (.dll file) which may have been loaded into the program. If you pass “NULL” as the parameter, it will get the handle for the currently running program (the .exe file) itself. This is valuable to have because with this handle, you can make the ‘GetProcAddress’ call, with the name of a function, and get a pointer to that function. Once we have that pointer, we can set it on the global variable, and the rest we’ve already seen.

So that’s it, that’s the trick. The typical way of compiling with the drawproc library is to statically link your code with it. The drawproc library comes with a ‘main’, so all you have to do is implement various bits and pieces that might not already be there.

As we saw from the test_keyboard code, mousePressed, and mouseMoved are the only two of the 4 mouse routines that were implemented. How is that possible? Well, the others will be NULL, as they won’t be found in the library, and since they’re NULL, they simply won’t be called.

There is one trick though to making this work. The GetProcAddress will only work if the routines were marked for export when compiled. This is achieved using the following in the drawproc.h header:

#define DPROC_API		__declspec(dllexport)

// IO Event Handlers
DPROC_API void keyPressed();
DPROC_API void keyReleased();
DPROC_API void keyTyped();


DPROC_API void mousePressed();
DPROC_API void mouseMoved();
DPROC_API void mouseDragged();
DPROC_API void mouseReleased();

This will essentially create function declarations for the functions we intend to implement. If your test code includes ‘drawproc.h’, and then you implement any of these routines, they will automatically be ‘exported’ when the whole is compiled. This will make it possible for them to be picked up during the ‘init()’ process, and thereby setting those global variables. This is also true of the ‘setup()’ and ‘draw()’ routines.

This is a great little trick, when you’re linking statically against the library. Another way to do it would be to put your code into a separate .dll, and run a drawproc.exe host program, giving the name of your .dll as a parameter. Then the library could be dynamically loaded, and the same hookup of routines could occur. The advantage of that setup is that you don’t need to create an entirely new .exe file for each of your test programs. Just produce the .dll. The disadvantage is you get stuck in a state when the runtime changes, and your .dll files no longer match.

So, there you have it, some amount of ‘dynamic’ programming in the little graphics engine that could, using ‘C’, which is certainly capable of supporting this pattern of dynamic programming.


Accessing Open vSwitch using LuaJIT – The LJIT2ovs project

I’ve recently had the need to learn Open vSwitch to do some virtualized networking stuff. As part of my learning experience, I’ve created the LJIT2ovs project on GitHub.

Open vSwitch (OVS) is a pretty decent bit of kit.  It’s use is to act as that bit of bridge code on a machine that supports some software defined networking.  Essentially, a network hub/switch/bridge on your machine.  My particular use case is to support interesting networking topologies with VMs, virtual lans and the like in the context of a data center.  Having OVS allows you to do some fairly fancy things in terms of managing VM movements, and virtual lans.

I have certainly done tons of integration with libraries of various types on platforms from the Raspberry pi, to Windows, and Linux in general.  Some code is easier to interop with and some code is harder.  I wrote a series a couple years back on the benefits and pitfalls of different styles of API development.

The OVS code is fairly easy to interop with using LuaJIT.  The publicly exposed stuff is all C99, and not particularly fancy.  There are a few cases where the usage of macros had me scratching my head, but a quick pass with a C compiler typically helps flesh those out.

One example will help illustrate the ease and pitfalls of doing some forms of interop.  I’ll use the UUID features in the library as an example.

First there’s data structures:

ffi.cdef[[
struct uuid {
uint32_t parts[4];
};
]]

The LuaJIT ffi makes pretty short work of that. Now the various routines that need a struct uuid will have access to what they need. The various functions are thus:

ffi.cdef[[
void uuid_init(void);
void uuid_generate(struct uuid *);
void uuid_zero(struct uuid *);
bool uuid_is_zero(const struct uuid *);
int uuid_compare_3way(const struct uuid *, const struct uuid *);
bool uuid_from_string(struct uuid *, const char *);
bool uuid_from_string_prefix(struct uuid *, const char *);
]]

Again, fairly simple. The use of ‘bool’ instead of ‘int’ as a return type from functions makes life a lot easier as the ffi will translate that to lua’s native boolean type. If it were an int, then instead of simpling doing

if not uuid_from_string(someuuidstring) then
  print("FAIL")
end

You’d have to write

if uuid_from_string(someuuidstring) ~= 0 then
  print("FAIL")
end

It seems like such a minor difference, but it’s actually a pretty huge pain in the backside. When the return value is an int, there are myriad things it can mean. One of them is ‘0 == success’, another is ‘0 == failure’, and there can by various others of course, including checking errno to find out what really went wrong or right. the bool is much more straight forward, success is usually indicated with ‘true’ and failure ‘false’.

Where things get a little more tricky and you have to pay special attention, is when you’re doing interop between different parts of the system and you flow through lua along the way.

Part of OVS has this dynamic string thing, which is one of those stretchy buffers, which will grow as necessary as you add stuff to it. One of the things it has is a ‘printf’ style formating thing.

ffi.cdef[[
void ds_put_format(struct ds *, const char *, ...) ;
]]

Yes, the LuaJIT ffi can deal with variadic functions, but you have to take extra care when feeding it the variable arguments. In particular, you’re responsible for dealing with the types of those arguments. This is where the care comes in. With normal functions (non-variadic), the ffi marshaling will just take care of things, and you don’t even realize a “number” is being turned into an ‘int32_t’, or whatever it needs to be. The ffi just figures it out based on the signature, and does the right thing. Not so with variadics. It can’t know what you need to pass.

So, here’s more from the UUID routines, some macros.

#define UUID_LEN 36
#define UUID_FMT "%08x-%04x-%04x-%04x-%04x%08x"
#define UUID_ARGS(UUID)                             \
    ((unsigned int) ((UUID)->parts[0])),            \
    ((unsigned int) ((UUID)->parts[1] >> 16)),      \
    ((unsigned int) ((UUID)->parts[1] & 0xffff)),   \
    ((unsigned int) ((UUID)->parts[2] >> 16)),      \
    ((unsigned int) ((UUID)->parts[2] & 0xffff)),   \
    ((unsigned int) ((UUID)->parts[3]))

In general, macros are of two types. First are the simple #defines which can turn into local variables. In this particular case, the UUID_LEN and UUID_FMT fit the bill. The UUID_LEN is just a numeric constant, so it can just become a regular number. The UUID_FMT doesn’t use any particularly fancy format routines (luckly lua string.format is similar enough in most cases), so that can become a simple string.

local UUID_LEN = 36
local UUID_FMT = "%08x-%04x-%04x-%04x-%04x%08x"

But what about that macro? Can we just turn it into a function, strip out the naughty bits, and call it a day?

local function UUID_ARGS(UUID)                             
    return ( ((UUID).parts[0])),            
    ( rshift((UUID).parts[1], 16)),      
    ( band((UUID).parts[1], 0xffff)),   
    ( rshift((UUID).parts[2], 16)),      
    ( band((UUID).parts[2], 0xffff)),   
    ( ((UUID).parts[3]))
end

Well, I want to write the following:

local success = uuid.uuid_from_string_prefix(id1, "12345678-1234-5678-1234-5678123456781234")
local output = ds.dynamic_string();
ds.ds_put_format(output, uuid.UUID_FMT, uuid.UUID_ARGS(id1))

print("OUTPUT: ", ds.ds_cstr(output));

Basically just round trip a string into a UUID and back out into a stretchy buffer, and print it as a lua string. Does it work? Nope, not quite. In this case, the output would be:

00000000-0000-0000-0000-45e4de9000000000

Not quite what I was expecting. Head scratch. OK, well, obviously I was a bit simplistic in my conversion of that UUID_ARGS macro. Maybe I should have preserved that casting stuff.

local uint32_t = ffi.typeof("uint32_t")

local function UUID_ARGS(UUID)                             
    local p1 = uint32_t(UUID.parts[0])
    local p2 = uint32_t(rshift(UUID.parts[1], 16))
    local p3 = uint32_t(band(UUID.parts[1], 0xffff))
    local p4 = uint32_t(rshift(UUID.parts[2], 16))
    local p5 = uint32_t(band(UUID.parts[2], 0xffff))
    local p6 = uint32_t(UUID.parts[3])

    return p1, p2, p3, p4, p5, p6
end

In addition to the temporary variables (used for debugging), I stripped out a number of parenthesis, because lua lives better with fewer parens. Basically, I used the ‘uint32_t’ type in a way that is similar to a typecast. Of course, it’s actually worse the way I’ve used it here because it creates a temporary number, which needs to be garbage collected, but the result is now:

OUTPUT: 12345678-1234-5678-1234-567812345678

Which is what I was expecting. So, maybe one last pass to clean it up…

local function UUID_ARGS(UUID)                             
    return ffi.cast("unsigned int", (UUID.parts[0])),
        ffi.cast("unsigned int", rshift(UUID.parts[1], 16)),
        ffi.cast("unsigned int", band(UUID.parts[1], 0xffff)),
        ffi.cast("unsigned int", rshift(UUID.parts[2], 16)),
        ffi.cast("unsigned int", band(UUID.parts[2], 0xffff)),
        ffi.cast("unsigned int", UUID.parts[3])
end

So, essentially, a more faithful representation of the original. Note though, although this will work with the UUID_FMT, when using a ‘C’ based ‘printf’ statements, it will NOT work with the lua string.format routine. It will complain that it was expecting a number, but received a ‘cdata’ instead. So, you have to think fairly clearly about how those APIs and macros are going to be used, and therefore how they should be translated.

Here’s that uuid.lua file in its entirety:

local ffi = require("ffi")
local bit = require("bit")

local rshift, band = bit.rshift, bit.band

local function BUILD_ASSERT_DECL(...)
    assert(...);
end

local UUID_BIT = 128;            -- Number of bits in a UUID. */
local UUID_OCTET = (UUID_BIT / 8); -- Number of bytes in a UUID. */

ffi.cdef[[
/* A Universally Unique IDentifier (UUID) compliant with RFC 4122.
 *
 * Each of the parts is stored in host byte order, but the parts themselves are
 * ordered from left to right.  That is, (parts[0] >> 24) is the first 8 bits
 * of the UUID when output in the standard form, and (parts[3] & 0xff) is the
 * final 8 bits. */
struct uuid {
    uint32_t parts[4];
};
]]

BUILD_ASSERT_DECL(ffi.sizeof("struct uuid") == UUID_OCTET);


local UUID_LEN = 36;
local UUID_FMT = "%08x-%04x-%04x-%04x-%04x%08x";

local function UUID_ARGS(UUID)                             
    return ffi.cast("unsigned int", (UUID.parts[0])),
        ffi.cast("unsigned int", rshift(UUID.parts[1], 16)),
        ffi.cast("unsigned int", band(UUID.parts[1], 0xffff)),
        ffi.cast("unsigned int", rshift(UUID.parts[2], 16)),
        ffi.cast("unsigned int", band(UUID.parts[2], 0xffff)),
        ffi.cast("unsigned int", UUID.parts[3])
end


--[[
/* Returns a hash value for 'uuid'.  This hash value is the same regardless of
 * whether we are running on a 32-bit or 64-bit or big-endian or little-endian
 * architecture. */
--]]
local function uuid_hash(uuid)
    return uuid.parts[0];
end

-- Returns true if 'a == b', false otherwise. */
local function uuid_equals(a, b)

    return (a.parts[0] == b.parts[0]
            and a.parts[1] == b.parts[1]
            and a.parts[2] == b.parts[2]
            and a.parts[3] == b.parts[3]);
end


  
ffi.cdef[[
void uuid_init(void);
void uuid_generate(struct uuid *);
void uuid_zero(struct uuid *);
bool uuid_is_zero(const struct uuid *);
int uuid_compare_3way(const struct uuid *, const struct uuid *);
bool uuid_from_string(struct uuid *, const char *);
bool uuid_from_string_prefix(struct uuid *, const char *);
]]

local Lib_uuid = ffi.load("openvswitch")

-- initialize uuid routines
Lib_uuid.uuid_init();

local exports = {
    Lib_uuid = Lib_uuid;

    UUID_BIT = UUID_BIT;
    UUID_OCTET = UUID_OCTET;
    UUID_FMT = UUID_FMT;
    UUID_ARGS = UUID_ARGS;

    -- types
    uuid = ffi.typeof("struct uuid");

    -- inline routines
    uuid_hash = uuid_hash;
    uuid_equals = uuid_equals;

    -- library functions
    uuid_init = Lib_uuid.uuid_init;
    uuid_generate = Lib_uuid.uuid_generate;
    uuid_zero = Lib_uuid.uuid_zero;
    uuid_is_zero = Lib_uuid.uuid_is_zero;
    uuid_compare_3way = Lib_uuid.uuid_compare_3way;
    uuid_from_string = Lib_uuid.uuid_from_string;
    uuid_from_string_prefix = Lib_uuid.uuid_from_string_prefix;
}

return exports

Just a couple more notes on style. When I’m using such a binding, I’ll typically do the following:

local uuid = require("uuid")

From there, I will want to utilize a simple notation to get at things.

local id = uuid.uuid(); 
uuid.uuid_generate(id);

local output = ds.dynamic_string();
ds.ds_put_format(output, uuid.UUID_FMT, uuid.UUID_ARGS(id))

 

I want to minimize the amount of times I have to use the ffi routines directly because they’re fairly low level, and can lead to some very subtle errors if you’re not careful. So, a properly constructed module will wrap up as much as possible.

In some cases I’ll create a ‘class’, which is a table to encapsulate the various bits and related bytes. In this case I did not, but I might still do it later if I find it useful.

I will typically do the ffi.load to get a handle on the library from which the routines are called, and stick that reference into a table, so the library reference won’t be garbage collected, and therefore possibly unloaded from the running system. And lastly, the function names have this construct:

    uuid_generate = Lib_uuid.uuid_generate;

It’s a simple aliasing so that I don’t have to remember which library the function is located in, I can just call uuid.uuid_generate, and the right thing will happen. This isn’t the most performant way to do it as the compiler can’t optimize the function call as much, so it will be slower. These routines are not typically called in a performant loop, so it’s an ok thing. If you were being really hard core, and needed the extra cycles, you’d make the library call directly instead of going through the table indirections.

The last trick you can do is to import that exports table into the global namespace:

for k,v in pairs(uuid) do
    _G[k] = v;
end

If you do this, then your code can drop the table indirection and become simply:

local id = uuid(); 
uuid_generate(id);

local output = dynamic_string();
ds_put_format(output, UUID_FMT, UUID_ARGS(id))

This is looking pretty close to the original ‘C’ code. Fewer pointers to deal with, no memory allocation problems, no funky difference between ‘.’ and ‘->’ indirection. In this way, Lua is just a nicer version of ‘C’ 🙂 My coworkers will get a kick out of that sentiment.

And so, there you have it. A fairly small example of beginning to interop with OVS. Open vSwitch is a fairly large codebase. It’s split between simple base library routines, reporting, core packet handling, and higher level apps, daemons and utilities. Starting from the top, the utilities are fairly easy to replace, once the interop at the lowest levels is dealt with. In LJIT2ovs, the lower levels are fairly well covered, and coverage increases as needs dictate. At the higher level, I am beginning with replacing simple routines, such as querying the database. At the end of the day, these higher level utilities are much easier to write, maintain, expand, and incorporate when they are written in script, rather than C.

Next time around I’ll examine some of these routines, and how they can be rewritten, and what benefits might acrue from that exercise.


schedlua – async io

And so, finally we come to the point. Thus far, we looked at the simple scheduler, the core signaling, and the predicate and alarm functions built atop that. That’s all great stuff for fairly straight forward apps that need some amount of concurrency. The best part though is when you can do concurrent networking stuff.

Here’s the setup; I want to issue 20 concurrent GET requests to 20 different sites, and get results back. I want the program to halt once all the tasks have been completed.

--test_linux_net.lua
package.path = package.path..";../?.lua"

local ffi = require("ffi")

local Kernel = require("kernel"){exportglobal = true}
local predicate = require("predicate")(Kernel, true)
local AsyncSocket = require("AsyncSocket")

local sites = require("sites");

-- list of tasks
local taskList = {}


local function httpRequest(s, sitename)
	local request = string.format("GET / HTTP/1.1\r\nUser-Agent: schedlua (linux-gnu)\r\nAccept: */*\r\nHost: %s\r\nConnection: close\r\n\r\n", sitename);
	return s:write(request, #request);
end

local function httpResponse(s)
	local BUFSIZ = 512;
	local buffer = ffi.new("char[512+1]");
	local bytesRead = 0
	local err = nil;
	local cumulative = 0

	repeat
		bytesRead, err = s:read(buffer, BUFSIZ);

		if bytesRead then
			cumulative = cumulative + bytesRead;
		else
			print("read, error: ", err)
			break;
		end
	until bytesRead < 1

	return cumulative;
end


local function siteGET(sitename)
	print("siteGET, BEGIN: ", sitename);

	local s = AsyncSocket();

	local success, err = s:connect(sitename, 80);  

	if success then
		httpRequest(s, sitename);
		httpResponse(s);
	else
		print("connect, error: ", err, sitename);
	end

	s:close();

	print("siteGET, FINISHED: ", sitename)
end


local function allProbesFinished()
	for idx, t in ipairs(taskList) do
		if t:getStatus() ~= "dead" then
			return false;
		end
	end

	return true;
end

local function main()
	for count=1,20 do
		table.insert(taskList, Kernel:spawn(siteGET, sites[math.random(#sites)]))
		Kernel:yield();
	end

	when(allProbesFinished, halt);
end

run(main)

Step by step. The httpRequest() function takes a socket, and does the most bare mimimal HTTP GET request, assuming the socket is already connected to the site.

Similarly, the httpResponse() function gets a response back from the server, and reads as much as it can until the socket is closed (because the Connection: close header was sent).

That’s about the most basic of HTTP request/response pairs you can have, ignoring doing any parsing of the returned data.

Alright, so let’s wrap those two up into a function called siteGET(). siteGET(sitename) takes the name of a site, creates a socket, connects it to the site, and then issues the httpRequest(), and then the httpResponse(). Very simple. What I like about this is that the httpRequest(); httpResponse() sequence is executed in serial as far as I’m concerned. I don’t have to be worried about the httpResponse() being issued before the request completes. Furthermore, if I didn’t use a spawn(), I could simply execute the code directly and be none the wiser.

I want to execute these siteGET()s concurrently though, so within main(), I start up 20 of these tasks, and let them go. Then comes the waiting part:

local function allProbesFinished()
	for idx, t in ipairs(taskList) do
		if t:getStatus() ~= "dead" then
			return false;
		end
	end

	return true;
end

	when(allProbesFinished, halt);

Going back to our knowledge of predicates, we know that the ‘when’ function takes a predicate (function that returns true/false), and will execute the second function when the predicate returns true.

OK, so we just need to come up with a predicate which tells us that all the tasks have completed. Easy enough as a list of the tasks is generated when they are spawned. So, we just go through that list and see if any of them are still running. If there is a single one that is still running, the predicate will return false, and ‘halt()’ will not be called. As soon as the last task finished, the predicate will return true, and the halt() function will be called.

Of course, most things in schedlua are convenient compositions of deeper things (with signals being at the core).

Instead of using the ‘when’ function, you could write the code more directly like this:

	while true
		if allProbesFinished() then
			halt();
			break;
		end
		yield();
	end

That doesn’t quite look as nice as just using the when() function I think. Also, you’re sitting in the main() function, which is no big deal as there’s nothing else trying to execute after this, but it just doesn’t seem as clean. Furthermore, the ‘when’ function might have some magic in its implementation, such as a better understanding of the state of tasks, or special knowledge of the scheduler, or who knows what. At any rate, either way essentially implements a barrier, and the technique can be used anywhere you want to perform an action after some set of tasks has completed. The allProbesFinished() function can be generalized to wait on any list of tasks, maybe call it “waitForTasks()” or some such thing.

At any rate, that completes the primitives that are baked into the core schedlua package. Everything from signals, to predicates, alarms, and finally async io. Of course this is Linux, so async io works with any file descriptor, not just network sockets, so file management or device communications in general can be thrown into the mix.

Now that the basics work, it’s a matter of cleaning up, writing more test cases, fixing bugs, reorganizing, and optimizing resource usage a bit. In general though, the constructs are there, and it’s ready to be used for real applications.


schedlua – predicates and alarms

A few years back, during the creation of Language Integrated Query (LINQ), I had this idea. If we could add database semantics to the language, what would adding async semantics look like. These days we’ve gone the route of async/await and various other constructs, but still, I always just wanted a primitives. such as “when”, “whenever”, and “waitUntil”. The predicates in schedlua are just that:

  • signalOnPredicate(predicate, signalName)
  • waitForPredicate(predicate)
  • when(predicate, func)
  • whenever(predicate, func)

Of courese, this is all based at the very core on the signaling mechanism that’s in the kernel of schedlua, but these primitives are not in the kernel proper.  They don’t need to be, which is nice because it means you can easily add such functions without having to alter the core.

What do they look like in practice?  Well, first of all, a ‘predicate’ is nothing more than a fancy name for a function that returns a bool value.  It will either return ‘true’ or ‘false’.  Based on this, various things can occur.  For example, ‘signalOnPredicate’, when the predicate returns ‘true’, emit the signal specified by signalName.  Similarly, for ‘waitForPredicate’, the currently running task will be put into a suspended state until such time as the predicate returns ‘true’.  ‘when’ and ‘whenever’ are similar, but they spawn new tasks, rather than suspending the existing task.  And here’s some code:

 

--test_scheduler.lua
package.path = package.path..";../?.lua"

local Functor = require("functor")
local Kernel = require("kernel"){exportglobal = true}
local Predicate = require("predicate")(Kernel, true)

local idx = 0;
local maxidx = 100;

local function numbers(ending)
	local function closure()
		idx = idx + 1;
		if idx > ending then
			return nil;
		end
		return idx;
	end
	
	return closure;
end



local function counter(name, nCount)
	for num in numbers(nCount) do
		print(num)
		local eventName = name..tostring(num);
		--print(eventName)
		signalOne(eventName);

		yield();
	end

	signalAll(name..'-finished')
end


local function predCount(num)
	waitForPredicate(function() return idx > num end)
	print(string.format("PASSED: %d!!", num))
end



local function every5()
	while idx <= maxidx do
		waitForPredicate(function() return (idx % 5) == 0 end)
		print("!! matched 5 !!")
		yield();
	end
end

local function test_whenever()
	local t1 = whenever(
		function() 
			if idx >maxidx then return nil end; 
			return (idx % 2) == 0 end,
		function() print("== EVERY 2 ==") end)
end

local function main()
	local t1 = spawn(counter, "counter", maxidx)

	local t6 = spawn(test_whenever);

	local t2 = spawn(predCount, 12)
	local t3 = spawn(every5)
	local t4 = spawn(predCount, 50)
	local t5 = when(
		function() return idx == 75 end, 
		function() print("WHEN IDX == 75!!") end)
	local t6 = when(function() return idx >= maxidx end,
		function() halt(); end);


end

run(main)



It’s a test case, so it’s doing some contrived things.  Basically, there is one task that is running a counter that throws a signal for every new number (up to maxid).  Then you can see the various tests which use predicates.

local function every5()
	while idx <= maxidx do
		waitForPredicate(function() return (idx % 5) == 0 end)
		print("!! matched 5 !!")
		yield();
	end
end

Here, we’re just running a continuous loop which will print it’s message every time the predicate is true. It seems kind of wasteful doesn’t it? Under normal circumstances, this would be a very hot spin loop, but when you call ‘waitForPredicate’, you task will alctually be thrown into a ‘suspended’ state, which means if there are other tasks to execute, they’ll go ahead, and you’ll get back in the queue to be tested later. So, it’s really, “test this predicate, if it’s not true, then throw the task at the back of the ready list, and test it again later. If it’s true, then continue on with whatever is next in this task”. The ‘yield()’ here is redundant.

In this particular case, we’ve essentially created a ‘whenever’ construct. This construct happens enough that it’s worth creating a convenience function for it.

local function test_whenever()
	local t1 = whenever(
		function() 
			if idx >maxidx then return nil end; 
			return (idx % 2) == 0 end,
		function() print("== EVERY 2 ==") end)
end

In this particular case, we let the ‘whenever’ construct do the work for us. Every other count, we’ll print our message. Of course, I’m using in place functions (lambda expressions?) in these test cases. They don’t have to be that way, you can set the functions however you want.

t6 is interesting because it says, ‘when the count reaches maxidx, halt the program’, which will in fact break us out of the main even loop and stop the program. Very convenient. This construct is useful because there may be myriad reasons why you’d want to stop the program. You can simply setup a predicate to do that. It could be a ‘when’ or perhaps you’d rather it be based on a signal, in that case use a signalOnPredicate/waitForSignal sort of thing. It’s composable, so use whatever set of constructs makes the most sense. It’s kind of a sane form of exception handling.

So there you have it, yet another construct tackled. Predicates are a simple construct that kind of extend the if/then flow control into the async realm. ‘when’ is almost a direct replacement for ‘if’ in this context. The waitOnPredicate is kind of a new construct I think. It’s like an if/spinlock, except you’re not spinning, you’re suspended with periodic checks on the predicate. And then of course the ‘signalOnPredicate’ is like a hail Mary pass. You don’t know who/what is going to respond, but you’re going to send up the signal. That’s like programming with interrupts, except, unless the scheduler allows for high priority interrupts/signals, these will be handled in the normal flow of cooperative processing.

Predicates are great, they’re a slightly different construct than I’ve typically used in my every day programming. They make some tasks a lot easier, and they make thinking about async programming more manageable.

And then there’s time…

Time is a lot easier construct to think about, because it’s well represented in most language frameworks already. Here are the time primitives:
 

  • waitUntilTime
  • sleep
  • delay
  • periodic

 
‘waitUntilTime’ is the lynch pin in this case. It will suspend the current task until the specified time. Time, in this case is a relative thing. The alarm module keeps its own clock, so everything is expressed relative to that clock.

sleep(seconds), will simply suspend the current task for a specified number of seconds. You can specify fractions of seconds, and the clock has nanosecond precision, but we’re not using a realtime scheduler, so you’ll get some amount of delay. Of course you could simply swap in a new scheduler and deal with any realtime requirements you might have.

delay, will spawn a task which will then execute the specified function after the specified amount of time has passed. This is kind of like a ‘when’ predicate, with a specialization for time. You could in fact reconstruct this primitive using the when predicate, but the alarm, knowing about time as it does, will do it more efficiently.

local Kernel = require("kernel"){exportglobal = true};
local Alarm = require("alarm")(Kernel)
local Clock = require("clock")

local c1 = Clock();

local function twoSeconds()
	print("TWO SECONDS: ", c1:secondsElapsed());
	Kernel:halt();
end

local function test_alarm_delay()
	print("delay(twoSeconds, 2000");
	Alarm:delay(twoSeconds, 2000);
end

run(test_alarm_delay)

periodic is similar, in that it well execute a function, but whereas ‘delay’ is a oneshot event, ‘periodic’ will repeat. In this way it is like the ‘whenever’ construct.

And there you have it. Between the predicates and the alarms, you have some new basic constructs for doing async programming. They are supported by the signaling construct that’s already a part of the kernel. They are simple add-ons, which means you can easily create your own constructs and replace these, or create completely new constructs which are similar. They can leverage the signaling mechanism, or maybe they want to do something else altogether.

So far, the constructs have been of the if/then variety, only in async fashion. I think there’s another set of constructs, which have to do with barriers and completions of tasks. That will clean up the other part of async, which is the ‘await’. We’ll see. In the meanwhile, next time, async io, which is pretty exciting.


graphicc – presenting a graph

The latest graphicc library is shaping up to be an almost useful thing.

The only way I know how to ensure a library actually serves a purpose is to build applications upon it.  This installment is about that sort of thing.  But first, a look at some more text.  This is basically text alignment working in graphicc.

test_text

The little bit of code that’s doing this looks like this.

void draw()
{
	background(pLightGray);

	// Draw some lines
	stroke(pBlack);
	line(width / 2, 0, width / 2, height - 1);
	line(0, height / 2, width - 1, height / 2);

	// draw some text
	int midx = width / 2;
	int midy = height / 2;
	fill(pBlack);
	textAlign(TX_LEFT);
	text("LEFT", midx, 20);
	
	textAlign(TX_CENTER);
	text("CENTER", midx, 40);
	
	textAlign(TX_RIGHT);
	text("RIGHT", midx, 60);

	// Around the center
	textAlign(TX_LEFT, TX_TOP);
	text("LEFT TOP", 0, 0);

	textAlign(TX_RIGHT, TX_TOP);
	text("RIGHT TOP",width,0);

	textAlign(TX_RIGHT, TX_BOTTOM);
	text("RIGHT BOTTOM", width,height);

	textAlign(TX_LEFT, TX_BOTTOM);
	text("LEFT BOTTOM",0,height);

	stroke(pRed);
	line(midx - 6, midy, midx + 6, midy);
	line(midx, midy - 6, midx, midy + 6);

	fill(pWhite);
	textAlign(TX_CENTER, TX_CENTER);
	text("CENTER CENTER", midx, midy);
}

But wait, this is high level stateful graphics sort of stuff, not the low level raw graphicc API. Yep, that’s right. Along the way of creating the lower level stuff, I’ve been nursing along what I call ‘drawproc’. This is essentially an interface that looks and feels very similar to the popular Processing.org environment, but it’s for C/C++ instead of Java. I also have a skin for PHIGS, but this one is a lot further along, and used constantly for test cases.

In order to work the drawproc API, and thus the low level graphicc routines, I’m going through a book on Processing: Visualizing Data which shows a lot of techniques for visualizing data sets using Processing. And here are the fruits of following one particular chapter:

timeseries

Nice usage of text, alignment, lines, rectangles, tiny circles, different sized  text, and all that.  If you were doing the interactive app, you could flip between Milk, Tea, and Coffee graphs.  The drawproc along with a shim for win32, give you keyboard and mouse control as well, so doing some interactive hover effects and the like is possible.

It’s a kind of funny thing.  In these days of HTML rendering, how could there possibly be any other way to do UI?  Well, HTML is the answer in many cases, but not all.  Having a small tight graphics library that can allow you to build interactive apps quickly and easily is still a useful thing.  Besides, it’s just plain fun.

Now that I’ve got a reasonable set of core graphics routines, I contemplated what it would be like to write a remote UI sort of thing for cloud based VMs.  Basically, just put some little engine on the VM which receives drawing commands, and allow that to be connected to via some port, which also sends/receives key and mouse stuff.  Well, isn’t that what ‘X’ does?  Yah, and a whole lot more!  Well then, surely VNC has got it covered?  Yes, as long as you’re already running X.  But, it’s a challenge.  Can I write such a small service in less than 1Mb of code?  Maybe 2Mb just to be safe?  Of course you’d have to write apps on the server side that talk to the graphics server, but that shouldn’t be too hard.  Just pick an API skin, like Processing, or GDI, or whatever, and send all the commands to the service, which will render into a buffer to be served up to whomever is looking.

One can dream…


schedlua – the kernel

Previously, I talked about the scheduler within the new scedlua.  A scheduler is a fairly simple thing, it just decides which of the many ready tasks will run next.  The default scheduler follows a fairly simple FIFO strategy, so there are no priorities, favorites, or the like.  Of course this wouldn’t be any fun if you were stuck with just one scheduler, so naturally enough this is an easily pluggable part of the system.  But what does this plugging?

In steps the Kernel.  In general, the schedlua project is about creating a set of tools by which highly performant services can be constructed.  schedlua largely supports the concept that a single processor can be highly leveraged if programmed correctly.  It does not try to gain performance through the usage of multiple threads, but rather it just takes on the task of suspending various tasks which are blocked on IO or otherwise idle, and letting tasks which are ready to run do their thing.  The concurrency model is cooperative, not preemptive, so if any one task misbehaves, the process can become stuck.

So, let’s take a look at this code:

--kernel.lua
-- kernel is a singleton, so return
-- single instance if we've already been
-- through this code
print("== KERNEL INCLUDED ==")

local Scheduler = require("scheduler")
local Task = require("task")
local Queue = require("queue")
local Functor = require("functor")

local Kernel = {
	ContinueRunning = true;
	TaskID = 0;
	Scheduler = Scheduler();
	TasksSuspendedForSignal = {};
}

setmetatable(Kernel, {
    __call = function(self, params)
    	params = params or {}
    	params.Scheduler = params.Scheduler or self.Scheduler
    	
    	if params.exportglobal then
    		self:globalize();
    	end

    	self.Scheduler = params.Scheduler;

    	return self;
    end,
})

function Kernel.getNewTaskID(self)
	self.TaskID = self.TaskID + 1;
	return self.TaskID;
end

function Kernel.getCurrentTaskID(self)
	return self:getCurrentTask().TaskID;
end

function Kernel.getCurrentTask(self)
	return self.Scheduler:getCurrentTask();
end

function Kernel.spawn(self, func, ...)
	local task = Task(func, ...)
	task.TaskID = self:getNewTaskID();
	self.Scheduler:scheduleTask(task, {...});
	
	return task;
end

function Kernel.suspend(self, ...)
	self.Scheduler:suspendCurrentFiber();
	return self:yield(...)
end

function Kernel.yield(self, ...)
	return self.Scheduler:yield();
end


function Kernel.signalOne(self, eventName, ...)
	if not self.TasksSuspendedForSignal[eventName] then
		return false, "event not registered", eventName
	end

	local nTasks = #self.TasksSuspendedForSignal[eventName]
	if nTasks < 1 then
		return false, "no tasks waiting for event"
	end

	local suspended = self.TasksSuspendedForSignal[eventName][1];

	self.Scheduler:scheduleTask(suspended,{...});
	table.remove(self.TasksSuspendedForSignal[eventName], 1);

	return true;
end

function Kernel.signalAll(self, eventName, ...)
	if not self.TasksSuspendedForSignal[eventName] then
		return false, "event not registered"
	end

	local nTasks = #self.TasksSuspendedForSignal[eventName]
	if nTasks < 1 then
		return false, "no tasks waiting for event"
	end

	for i=1,nTasks do
		self.Scheduler:scheduleTask(self.TasksSuspendedForSignal[eventName][1],{...});
		table.remove(self.TasksSuspendedForSignal[eventName], 1);
	end

	return true;
end

function Kernel.waitForSignal(self, eventName)
	local currentFiber = self.Scheduler:getCurrentTask();

	if currentFiber == nil then
		return false, "not currently in a running task"
	end

	if not self.TasksSuspendedForSignal[eventName] then
		self.TasksSuspendedForSignal[eventName] = {}
	end

	table.insert(self.TasksSuspendedForSignal[eventName], currentFiber);

	return self:suspend()
end

function Kernel.onSignal(self, func, eventName)
	local function closure()
		self:waitForSignal(eventName)
		func();
	end

	return self:spawn(closure)
end



function Kernel.run(self, func, ...)

	if func ~= nil then
		self:spawn(func, ...)
	end

	while (self.ContinueRunning) do
		self.Scheduler:step();		
	end
end

function Kernel.halt(self)
	self.ContinueRunning = false;
end

function Kernel.globalize()
	halt = Functor(Kernel.halt, Kernel);
    onSignal = Functor(Kernel.onSignal, Kernel);

    run = Functor(Kernel.run, Kernel);

    signalAll = Functor(Kernel.signalAll, Kernel);
    signalOne = Functor(Kernel.signalOne, Kernel);

    spawn = Functor(Kernel.spawn, Kernel);
    suspend = Functor(Kernel.suspend, Kernel);

    waitForSignal = Functor(Kernel.waitForSignal, Kernel);

    yield = Functor(Kernel.yield, Kernel);
end

return Kernel;

 

From the top, you can see the Kernel requires the scheduler, task and functor. The scheduler has already been explained. The Kernel serves a couple of purposes. First of all, it manages the scheduler. The ‘run’ function at the bottom is the ‘loop’ of the application. It will run until ‘halt’ is called. Each time through the loop it’s telling the scheduler to take a step.

Also at the bottom, you can see usage of the Functor. A functor is just a simple convenience wrapper that helps you call a function on a table at a later point. Those functors are used to make the keywords global.

There are two primary things the kernel does. One is to spawn new tasks, the other is to provide a central point for signal handling.

First, let’s look at the ‘spawn’.

function Kernel.spawn(self, func, ...)
	local task = Task(func, ...)
	task.TaskID = self:getNewTaskID();
	self.Scheduler:scheduleTask(task, {...});
	
	return task;
end

This is actually the coolest part of the system in terms of how the programming model is expressed. Here’s an example of it in use.

local Kernel = require("kernel"){exportglobal = true}


local function numbers(ending)
	local idx = 0;
	local function closure()
		idx = idx + 1;
		if idx > ending then
			return nil;
		end
		return idx;
	end
	
	return closure;
end

local function task1()
	print("first task, first line")
	yield();
	print("first task, second line")
end

local function task2()
	print("second task, only line")
end

local function counter(name, nCount)
	for num in numbers(nCount) do
		print(name, num);
		yield();
	end
	halt();
end

local function main()
	local t0 = spawn(counter, "counter1", 5)
	local t1 = spawn(task1)
	local t2 = spawn(task2)
	local t3 = spawn(counter, "counter2", 7)
end

run(main)

Basically, any time you want something to happen concurrently, you just say ‘spawn(func, params) and that’s that.

What happens is a Task object is created which holds onto the function object as well as the initial set of parameters. This task is then sent to the scheduler to be run. From then on out you can forget about it. Of course, you’re handed the task when you say ‘spawn’, so you do have a chance of suspending and killing it off in the future if you like. Similarly, you can wait for a task to complete as well.

So, that’s spawning.

The other major feature in the kernel is signal handling.

function Kernel.waitForSignal(self, eventName)
	local currentFiber = self.Scheduler:getCurrentTask();

	if currentFiber == nil then
		return false, "not currently in a running task"
	end

	if not self.TasksSuspendedForSignal[eventName] then
		self.TasksSuspendedForSignal[eventName] = {}
	end

	table.insert(self.TasksSuspendedForSignal[eventName], currentFiber);

	return self:suspend()
end

This is probably THE most important routine in the whole system. Basically, take the current task, and put it onto the suspension list, connected with the signal name (signals are just a string value). Later on, when you want the task to resume, you would signal it using either signalOne(), or signalAll().

A little bit of code demonstrating this:

local Kernel = require("kernel"){exportglobal = true}
local Functor = require("functor")

local function numbers(ending)
	local idx = 0;
	local function closure()
		idx = idx + 1;
		if idx > ending then
			return nil;
		end
		return idx;
	end
	
	return closure;
end

local function waitingOnCount(name, ending)
	local eventName = name..tostring(ending)
	waitForSignal(eventName)

	print("REACHED COUNT: ", ending)
end

local function onCountFinished(name)
	print("Counter Finished: ", name)
end

local function counter(name, nCount)
	for num in numbers(nCount) do
		print(num)
		local eventName = name..tostring(num);
		--print(eventName)
		signalOne(eventName);

		yield();
	end

	signalAll(name..'-finished')
end

local function main()
	local t1 = spawn(counter, "counter", 50)
	local t2 = spawn(waitingOnCount, "counter", 20)
	local t3 = spawn(function() print("LAMDA"); waitForSignal("counter15") print("reached 15!!") end)
	
	-- test signalAll().  All three of these should trigger when
	-- counter finishes
	local t13 = onSignal(Functor(onCountFinished, "counter-1"), "counter-finished")
	local t14 = onSignal(Functor(onCountFinished, "counter-2"), "counter-finished")
	local t15 = onSignal(Functor(onCountFinished, "counter-3"), "counter-finished")
end

run(main)

Here, there is a counter(), which is just counting, and firing off a signal for each number. The various waitingOnCount(), and LAMBDA routines are going to respond to the appropriate signals.

Finally, the t13, t14, and t15 tasks are waiting for the “counter-finished” signal, and they will all fire off and print their little message.

Of course, at this point you could have something that would call ‘halt()’ so you don’t have to press Ctl-C to stop the process, but you get the idea.

And that’s pretty much it for the kernel. Absent from here are the async io, predicates, alarms and the like. They are available in schedlua, but they’re not a part of the kernel. Instead of being part of the kernel proper, these are essentially modules. They utilize the signal and spawn features built into the kernel, and they’re free to do their own thing.

I’ll get into the details of alarms and predicates next time around to demonstrate the concept of easy add-on modules.