Trivial Non-Blocking Echo Server (Scala+Akka)

Akka is a framework for asynchronous messaging and IO in Scala. A colleague of mine gave it a good recommendation so I thought I’d check it out. It looks very promising although its low-level IO API is not as intuitive as I’d hoped. But, it was very easy to build a simple echo server, the “Hello, World!” of network programming.

Of course, it’s pretty easy to build a blocking socket server in pretty much any language. What I love about Scala+Akka is how easy it is to hide the fact that all of this IO is non-blocking.

Could not embed GitHub Gist 2219531: Not Found

To run:

scala -cp .:/home/rweeks/projects/akka-2.0/lib/akka/akka-actor-2.0.jar TCPServer

To test:

rweeks@foxbat:~/projects/scala-test$ telnet localhost 8080
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
You go first.
You go first.
No, You go first!
No, You go first!
Bye
Bye
^]
telnet> close
Connection closed.

libmicrohttpd mingw gotcha

Let’s say you want to build a nice tiny cross-platform web server using libmicrohttpd and mingw.  So for static content you’ll probably convert the URI to a path (safely! watch out for nasty clients playing tricks with “../”) and call open(3) on the path, and call MHD_create_response_from_fd with the file descriptor.

Sounds good, except on Windows you’ll see some very crazy errors whereby you actually read past the end of the file.  This is because Windows may decide to open the file as a text document, which will convert all your newlines to newlines + carriage returns.

The fix is to add the “O_BINARY” option to the open(3) call.  So,

Could not embed GitHub Gist 2030342: Not Found

Slow iTunes Downloads on TELUS Optik

If you’re experiencing really slow downloads from the iTunes store on TELUS Optik, it could be a problem with your DNS servers.  I think by default the DHCP server on the Optik router configures the clients to use the router as their DNS server.  The router is configured to use the servers:

  • 75.153.176.1  (ns1.dns.telus.com)
  • 75.153.176.9 (ns2.dns.telus.com)

I think that either the Optik router or the TELUS DNS servers are a bottleneck here.  I guess  that for some reason, iTunes needs to do a lot of DNS lookups when it transfers data?

Anyways I changed my clients to use the following DNS servers:

  • 8.8.8.8
  • 8.8.4.4
  • 208.67.222.222
  • 208.67.220.220

The first two are provided by Google, the last two are provided by OpenDNS.  iTunes download speed went from ~200KB/sec to ~1.5MB/sec.  On Mac OS X, change the setting in System Preferences → Network → (Select your Network Connection) → Advanced → DNS.

Corporate (Mis?)Management

Via Gruber, an article about the business anti-pattern of maximizing shareholder value.  I don’t disagree in principle with the idea that CEOs should have better things to do than negotiate expectations with market analysts.  But I think that the article’s central analogy, that of a CEO to a football coach and a business to a football match, is fundamentally invalid.

A football match is time-bound.  This rightly requires that a football coach focus on winning the game in the required timeframe, not on beating the spread.  I can’t think of any type of business that’s similarly time-bound (in fact, I think a competent economist could argue that in an efficient market, all corporations are growth-bound).  In an environment that isn’t time-bound, it makes sense that the best metric of a corporation’s value is not its position or “score”, but the first and second derivatives of its position (that is, velocity and acceleration).  And isn’t this what market analysts are really getting at when they try to define expectations for a corporation?

Bonus amateur economist theorizing: there’s been a lot of talk lately about executive pay and the perverse incentives it creates.  For what it’s worth, I think the best rationalization of executive pay comes from tournament theory applied to the workplace.  This is probably best explained by Tim Harford in various places, including this YouTube video from the Logic of Life.  To summarize: lavish CEO pay is not only a reward for the CEO’s labour, it’s an incentive for his underlings to aspire to the top position.  This creates its own set of perverse incentives, prioritizing individual success over the success of the corporation.

Hacking the Touchpad, Part 1

I just picked up a discounted HP TouchPad from my man Greg Chan (via a real stand-up guy who would probably prefer to remain anonymous).   Haven’t even played around with WebOS; it doesn’t interest me in the slightest.  We need to get Android on this contraption!  Here are my modest contributions to the effort. First: an attempt to get an SSH client and server running.

Preparing for the Worst

First, establish a backup plan!  Once you register the device, you’ll have access to the HP WebOS site.  From there you can download WebOS Doctor, a Java app that will let you restore your TouchPad should something untoward happen to it.

I haven’t used WebOS Doctor yet and I hope I never have to.  But as a backup-backup plan, let’s make a copy of the filesystem.  Follow the instructions here to get terminal (root) access to the TouchPad. After logging in, I ran this command:

tar cvfz /media/internal/downloads/backup.tar.gz / --exclude '/media/internal/downloads/*

to backup the filesystem.  It’s far from a perfect backup, and it may never be useful, but I like having it around just in case.  Let me know if you need a copy, it’s about 300MB.

Setting up a Cross-Compiler

Wow, setting up a cross compiler has gotten a lot easier since the last time I checked.  All I had to do was download the ARM cross-compiler from here and install it.

The cross-compiler build tools are set up with weird names like “arm-none-linux-gnueabi-ar”.  There’s got to be an easier way to configure this but I just ran this command to set up shortened symlinks:

rweeks@faithless:/bitsafe/CodeSourcery/Sourcery_G++_Lite/bin$ for CMD in *; do CMD_TRIM=`echo $CMD | sed -e 's/arm-none-linux-gnueabi-//'`; ln -s $CMD $CMD_TRIM; done

Then you can control whether you’re using your native buildtools or the cross-compiler buildtools just by setting your $PATH.

Building OpenSSH

I figure a good first-day milestone is to get OpenSSH running on the TouchPad.  I’ll try to work my way up to a full-on Android distro :).  I pretty much followed the instructions here with some minor changes for the cross-compiler.

First I defined a directory where I want to put all the build output:

mkdir /bitsafe/arm-openssh-server/output

The commands I used to build zLib:

./configure --prefix=/bitsafe/arm-openssh-server/output
make && make install

The commands I used to build openSSL (this will take a while):

./Configure --prefix=/bitsafe/arm-openssh-server/output linux-armv4
make && make install

The commands I used to build openSSH:

./configure --host=arm-none-linux-gnueabi --prefix=/bitsafe/arm-openssh-server/output --with-zlib=$PWD/../zlib-1.2.5 --with-ssl-dir=../openssl-1.0.0d
make && make install

The OpenSSH build will fail to install due to the cross-compiler (it can’t strip the output files).  But that should be OK.

Deploying OpenSSH to the TouchPad

OK, everything should be built at this point.  You can double-check that you’re using the cross-compiler by, eg.

find . -type f -print0 | xargs -0 file

Where you see executable files, it should indicate that they have been built for the ARM architecture.  I wrapped up everything in a tarball:

tar cvfz openssh-server.tar.gz arm-openssh-server/

This grabbed my “output” directory, as well as the source directories for zLib, openSSL and openSSH (in case any files failed to install correctly into output/)

I had a vastly complicated procedure in mind to copy the tarball to my TouchPad, but it turns out that the TouchPad just mounts as a vfat file system which was mounted automatically by my build machine.  The whole thing was just a drag-and-drop, which was nice.

Extract the tar file like so:

tar xvfz openssh-server.tar.gz --no-same-owner

You’ll get a bunch of errors on the extraction because it can’t create symbolic links: I think this is because you’re extracting to a filesystem that doesn’t support symlinks.  No big deal.

Test that the cross-compiler worked!

cd /media/internal/downloads/arm-openssh-server/zlib-1.2.5
./example
zlib version 1.2.5 = 0x1250, compile flags = 0x55
uncompress(): hello, hello!
gzread(): hello, hello!
gzgets() after gzseek:  hello!
inflate(): hello, hello!
large_inflate(): OK
after inflateSync(): hello, hello!
inflate with dictionary: hello, hello!

Starting OpenSSH Server

Harder than it sounds!  The root filesystem is mounted read-only by default, but you can hack your way around that with:

mount -w -o remount /

Then, add the sshd user and group to /etc/passwd and /etc/group

Setup an ssh key using ssh-keygen and set the “HostKey” property in sshd_config to point to the private key.

If you didn’t remount the root FS as read-write, you need to set UsePrivilegeSeparation to true.

Start sshd like so:

root@RussHPTouchPad:/media/internal/downloads/arm-openssh-server/openssh-5.8p2# $PWD/sshd -f sshd_config -ddd

(This is required because by setting up the “prefix” properties during the SSH build, all the commands will now be looking for their config in /bitsafe/…)

Last thing is to undo all the custom iptables config:

iptables -F
iptables -P INPUT ACCEPT
iptables -X ALLOWED_PACKETS
iptables -X ICMPFLOOD
iptables -X INVALID_PACKETS

OpenSSH 5.8 Running on TouchPad:

backfire:bin rweeks$ ssh -p 2222 root@192.168.10.128
The authenticity of host '[192.168.10.128]:2222 ([192.168.10.128]:2222)' can't be established.
RSA key fingerprint is de:c2:1f:6a:30:e9:33:cc:85:f6:28:07:62:f9:8b:9b.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '[192.168.10.128]:2222' (RSA) to the list of known hosts.
root@192.168.10.128's password:
lastlog_openseek: Couldn't stat /var/log/lastlog: No such file or directory
lastlog_openseek: Couldn't stat /var/log/lastlog: No such file or directory
debug1: permanently_set_uid: 0/0
Environment:
  USER=root
  LOGNAME=root
  HOME=/home/root
  PATH=/usr/bin:/bin:/usr/sbin:/sbin:/bitsafe/arm-openssh-server/output/bin
  MAIL=/var/mail/root
  SHELL=/bin/sh
  TZ=:/var/luna/preferences/localtime
  SSH_CLIENT=192.168.10.107 52206 2222
  SSH_CONNECTION=192.168.10.107 52206 192.168.10.128 2222
  SSH_TTY=/dev/pts/1
  TERM=xterm-color
root@RussHPTouchPad:/var/home/root#

RTree implementation in Java

An RTree is a data structure for spatial indexing.  If you have a bunch of objects with associated coordinates (or associated rectangles, or hyperrectangles, etc.) you can use an RTree for queries like, “find all objects overlapping with this search rectangle” or “find the N closest objects to this object”.

This is the original paper describing the RTree and its implementation.  I’ve built a Java implementation based on it, here.

I used this RTree implementation to generate the simulated network topologies shown here.

Simulated Network Topologies

I’ve been doing a lot of work in the network management space recently (on account of that’s my job) and I’ve found it really helpful to use a few randomly-generated network topologies.  So I wrote a little tool which takes as input a slightly-massaged version of the cities database from geonames.org and produces as output a graph where cities are vertices and edges are defined in a pseudo-realistic fashion.  The graph is defined in XML.  I’ll probably get around to open-sourcing the tool, eventually.

By “pseudo-realistic” I mean that cities are much more likely to be adjacent to nearby cities, and the edges are weighted such that a shortest-path algorithm will prefer many short hops over a few long hops.  Specifically, the weight of an edge is n*log(n) where n is the great-circle distance between the two incident cities.

This algorithm tends to produce disconnected graphs.  It often doesn’t define any edges between the Americas and Africa or Europe.  Usually I just go and insert those edges manually.

Comments are extremely welcome re. how to make this simulated topology more realistic.  One thing I’m thinking of is defining a set of vertices as “aggregation nodes” and then auto-generating a certain number of devices adjacent to each aggregation node, where the number of aggregated devices per aggregation node is proportional to the population of the aggregation node city.

network-16384

network-8192

network-4096

network-2048

network-1024

network-512

network-256

network-128

network-64

network-32

Java brute-force Knight's Tour

Wikipedia today featured an animated picture of a Knight’s Tour, which got me thinking about algorithms to find Knights Tours.  I put this together really quickly, it’s just a brute-force approach and its running time varies (depending on the start square) from “wow that was fast” to “time to ctrl-c this thing”.