Vidar Hokstad V2.0

Hypno trip down the fractal rug - animated sierpinski in javascript

Thu, 19 Jun 2008 21:23:39 -0000

It's rare I see javascripts that makes me go wow!. I've been experimenting with the canvas element myself, and there are some cool demos of it, but I loved this both because it looks good and because the resulting code is so simple..

Writing a compiler in Ruby bottom up - step 9

Thu, 19 Jun 2008 17:08:12 -0000

This is the ninth in a series. Please start on part 1 first if you haven't already to get the background, or see here for the full series so far Ok, so I know it's been far too long. Lots going on at the moment... This is a very short part, but I'll try to get the next part cleaned up in the next few days (teaser at the end...)

Implementing 'while' as a primitive

I like small language cores, and it really appeals to me to implement control structures as methods rather than hardcoding them into the language. As we've seen, 'while' can be implemented fairly easily in terms of a quite basic language. We could streamline it even more by reducing the verbiage needed to pass anonymous functions or by adding a Lisp style macro facility. There's an added complication: Using lambda's that are not proper closures, which is the case for us so far, means there's no way for the body to access external variables. That makes the while loop pretty useless. The "proper" way of fixing that would be to actually implement proper closures, and I promise we'll get there, but not right now - there are other pieces to get in place first. So I'm biting the bullet and adding a built in "while" construct for now. It also serves the purpose of showing how it's usually done - it's quite simple really. As usual we start with a simple C test to see how to do this:

int main() {
  while (foo()) {
    bar();
  }
}

gcc -S, and this is the relevant part:

   jmp .L2
.L3:
    call    bar
.L2:
    call    foo
    testl   %eax, %eax
    jne .L3

Notice how the condition is placed at the end, and we start by jumping to the end? The alternative is to place the conditional check at the start, reversing the test and making it jump to after the end of the loop, and then placing an unconditional jump after the body, like the example below, but that results in one extra branch instruction per iteration of the loop:

.L3:
    call    foo
    testl   %eax, %eax
    je .L2
    call    bar
    jmp .L3
.L2:

This is not a big deal since performance isn't a concern right now, but the distinction here doesn't add any complexity to speak of. So here's what we do:

  def compile_while(scope, cond, body)
    start_while_seq = @seq
    cond_seq = @seq + 1
    @seq += 2
    puts "\\\\\\\\\\\\\\\\tjmp\\\\\\\\\\\\\\\\t.L#{cond_seq}"
    puts ".L#{start_while_seq}:"
    compile_exp(scope,body)
    var = compile_eval_arg(scope,cond)
    puts ".L#{cond_seq}:"
    puts "\\\\\\\\\\\\\\\\ttestl\\\\\\\\\\\\\\\\t#{var}, #{var}"
    puts "\\\\\\\\\\\\\\\\tjne\\\\\\\\\\\\\\\\t.L#{start_while_seq}"
    return [:subexpr]
  end

Then we add it to #compile_exp:

   return compile_while(scope,*exp[1..-1]) if (exp[0] == :while)

And a test:

prog = [:do,
  [:call, [:lambda, [:i],
      [:while,
        :i,
        [:do,
          [:printf, "Countdown: %ld\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n", :i],
          [:assign, :i, [:sub, :i, 1]]
        ]
      ]
    ], [10] ]
  ]

Wrapping it up

Like last time, I've tar'ed up the files for step 9 together with a Makefile here. If you have Ruby, make and gcc installed you should be able to just untar it and run make to get the "step9" test binary:

[vidarh@dev step9]$ make
ruby step9.rb >step9.s
as   -o step9.o step9.s
cc    -c -o runtime.o runtime.c
cc   step9.o runtime.o   -o step9
[vidarh@dev step9]$ ./step9 
Countdown: 10
Countdown: 9
Countdown: 8
Countdown: 7
Countdown: 6
Countdown: 5
Countdown: 4
Countdown: 3
Countdown: 2
Countdown: 1
[vidarh@dev step9]$

Next time

Next time we'll start putting together and going through a simple "text mangler" that'll let us "parse" a lisp like syntax and generate a Ruby script that runs the compiler on the equivalent program... It will turn this (not the complete program):

(defun parse () (let (c sep expr) 
  (assign sep 0)
  (assign expr 0)
  (while (and (ne (assign c (getchar)) -1) (ne c 41))
        (if (eq c 40)
          (do (copy_expr) (assign sep 1))
          (if (eq c 59)
                (parse_comment)
                (if (eq c 34) 
                  (do (parse_quoted c) (assign sep 1))
                  (do
                   (if (and (isspace c) sep) (do (printf ",") (assign sep 0)))
                   (if (and (isalnum c) (not sep)) 
                           (do (assign sep 1) (if (not (isdigit c)) (printf ":")))
                         )
                   (putchar c)
                   )
                  )
                )
          )
        )
  ))

into this plus driver code to run the compiler:

[:defun, :parse, [], [:let, [:c, :sep, :expr], 
  [:assign, :sep, 0],                             
  [:assign, :expr, 0],
  [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 41]],
        [:if, [:eq, :c, 40],
          [:do, [:copy_expr], [:assign, :sep, 1]],
          [:if, [:eq, :c, 59],
                [:parse_comment],
                [:if, [:eq, :c, 34], 
                  [:do, [:parse_quoted, :c], [:assign, :sep, 1]],
                  [:do,
                   [:if, [:and, [:isspace, :c], :sep], [:do, [:printf, ","], [:assign, :sep, 0]]],
                   [:if, [:and, [:isalnum, :c], [:not, :sep]], 
                           [:do, [:assign, :sep, 1], [:if, [:not, [:isdigit, :c]], [:printf, ":"]]],
                         ],
                   [:putchar, :c],
                   ],
                  ],
                ],
          ],
        ],
  ]],

By the end of it it will process itself and spit out the equivalent parse-tree encoded in Ruby. Note how I've put "parse" in quotes etc.. It hardly deserves to be described as a parser - we'll get to a real parser a few steps further out. Note that I am not going to go down towards writing a Lisp, but I figured since I've used a Lisp like syntax so far for examples, it would be a good test to see whether we're far enough along to do something remotely useful yet. It did need a couple of helper functions beyond what's present so far to get a decent result, but not much. The "real" parser will be for a much more Ruby-ish syntax.

5 simple ways to troubleshoot using Strace

Tue, 10 Jun 2008 20:09:23 -0000

I keep being surprised how few people are aware of all the things they can use strace for. It's always one of the first debug tools I pull out, because it's usually available on the Linux systems I run, and it can be used to troubleshoot such a wide variety of problems.

What is strace?

Strace is quite simply a tool that traces the execution of system calls. In its simplest form it can trace the execution of a binary from start to end, and output a line of text with the name of the system call, the arguments and the return value for every system call over the lifetime of the process. But it can do a lot more:

It can filter based on the specific system call or groups of system calls
It can profile the use of system calls by tallying up the number of times a specific system call is used, and the time taken, and the number of successes and errors.
It traces signals sent to the process.
It can attach to any running process by pid.

If you've used other Unix systems, this is similar to "truss". Another (much more comprehensive) is Sun's Dtrace.

How to use it

This is just scratching the surface, and in no particular order of importance:

1) Find out which config files a program reads on startup

Ever tried figuring out why some program doesn't read the config file you thought it should? Had to wrestle with custom compiled or distro-specific binaries that read their config from what you consider the "wrong" location? The naive approach:

$ strace php 2>&1 | grep php.ini
open("/usr/local/bin/php.ini", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/local/lib/php.ini", O_RDONLY) = 4
lstat64("/usr/local/lib/php.ini", {st_mode=S_IFLNK|0777, st_size=27, ...}) = 0
readlink("/usr/local/lib/php.ini", "/usr/local/Zend/etc/php.ini", 4096) = 27
lstat64("/usr/local/Zend/etc/php.ini", {st_mode=S_IFREG|0664, st_size=40971, ...}) = 0

So this version of PHP reads php.ini from /usr/local/lib/php.ini (but it tries /usr/local/bin first). The more sophisticated approach if I only care about a specific syscall:

$ strace -e open php 2>&1 | grep php.ini
open("/usr/local/bin/php.ini", O_RDONLY) = -1 ENOENT (No such file or directory)
open("/usr/local/lib/php.ini", O_RDONLY) = 4

The same approach work for a lot of other things. Have multiple versions of a library installed at different paths and wonder exactly which actually gets loaded? etc.

2) Why does this program not open my file?

Ever run into a program that silently refuse to read a file it doesn't have read access to, but you only figured out after swearing for ages because you thought it didn't actually find the file? Well, you already know what to do:

$ strace -e open,access 2>&1 | grep your-filename

Look for an open() or access() syscall that fails

3) What is that process doing RIGHT NOW?

Ever had a process suddenly hog lots of CPU? Or had a process seem to be hanging? Then you find the pid, and do this:

root@dev:~# strace -p 15427
Process 15427 attached - interrupt to quit
futex(0x402f4900, FUTEX_WAIT, 2, NULL 
Process 15427 detached

Ah. So in this case it's hanging in a call to futex(). Incidentally in this case it doesn't tell us all that much - hanging on a futex can be caused by a lot of things (a futex is a locking mechanism in the Linux kernel). The above is from a normally working but idle Apache child process that's just waiting to be handed a request. But "strace -p" is highly useful because it removes a lot of guesswork, and often removes the need for restarting an app with more extensive logging (or even recompile it).

4) What is taking time?

You can always recompile an app with profiling turned on, and for accurate information, especially about what parts of your own code that is taking time that is what you should do. But often it is tremendously useful to be able to just quickly attach strace to a process to see what it's currently spending time on, especially to diagnose problems. Is that 90% CPU use because it's actually doing real work, or is something spinning out of control. Here's what you do:

root@dev:~# strace -c -p 11084
Process 11084 attached - interrupt to quit
Process 11084 detached
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 94.59    0.001014          48        21           select
  2.89    0.000031           1        21           getppid
  2.52    0.000027           1        21           time
------ ----------- ----------- --------- --------- ----------------
100.00    0.001072                    63           total
root@dev:~#

After you've started strace with -c -p you just wait for as long as you care to, and then exit with ctrl-c. Strace will spit out profiling data as above. In this case, it's an idle Postgres "postmaster" process that's spending most of it's time quietly waiting in select(). In this case it's calling getppid() and time() in between each select() call, which is a fairly standard event loop. You can also run this "start to finish", here with "ls":

root@dev:~# strace -c >/dev/null ls
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 23.62    0.000205         103         2           getdents64
 18.78    0.000163          15        11         1 open
 15.09    0.000131          19         7           read
 12.79    0.000111           7        16           old_mmap
  7.03    0.000061           6        11           close
  4.84    0.000042          11         4           munmap
  4.84    0.000042          11         4           mmap2
  4.03    0.000035           6         6         6 access
  3.80    0.000033           3        11           fstat64
  1.38    0.000012           3         4           brk
  0.92    0.000008           3         3         3 ioctl
  0.69    0.000006           6         1           uname
  0.58    0.000005           5         1           set_thread_area
  0.35    0.000003           3         1           write
  0.35    0.000003           3         1           rt_sigaction
  0.35    0.000003           3         1           fcntl64
  0.23    0.000002           2         1           getrlimit
  0.23    0.000002           2         1           set_tid_address
  0.12    0.000001           1         1           rt_sigprocmask
------ ----------- ----------- --------- --------- ----------------
100.00    0.000868                    87        10 total

Pretty much what you'd expect, it spents most of it's time in two calls to read the directory entries (only two since it was run on a small directory).

5) Why the **** can't I connect to that server?

Debugging why some process isn't connecting to a remote server can be exceedingly frustrating. DNS can fail, connect can hang, the server might send something unexpected back etc. You can use tcpdump to analyze a lot of that, and that too is a very nice tool, but a lot of the time strace will give you less chatter, simply because it will only ever return data related to the syscalls generated by "your" process. If you're trying to figure out what one of hundreds of running processes connecting to the same database server does for example (where picking out the right connection with tcpdump is a nightmare), strace makes life a lot easier. This is an example of a trace of "nc" connecting to www.news.com on port 80 without any problems:

$ strace -e poll,select,connect,recvfrom,sendto nc www.news.com 80
sendto(3, "\\24\\0\\0\\0\\26\\0\\1\\3\\255\\373NH\\0\\0\\0\\0\\0\\0\\0\\0", 20, 0, {sa_family=AF_NETLINK, pid=0, groups=00000000}, 12) = 20
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_FILE, path="/var/run/nscd/socket"}, 110) = -1 ENOENT (No such file or directory)
connect(3, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, 28) = 0
poll([{fd=3, events=POLLOUT, revents=POLLOUT}], 1, 0) = 1
sendto(3, "\\213\\321\\1\\0\\0\\1\\0\\0\\0\\0\\0\\0\\3www\\4news\\3com\\0\\0\\34\\0\\1", 30, MSG_NOSIGNAL, NULL, 0) = 30
poll([{fd=3, events=POLLIN, revents=POLLIN}], 1, 5000) = 1
recvfrom(3, "\\213\\321\\201\\200\\0\\1\\0\\1\\0\\1\\0\\0\\3www\\4news\\3com\\0\\0\\34\\0\\1\\300\\f"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, [16]) = 153
connect(3, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, 28) = 0
poll([{fd=3, events=POLLOUT, revents=POLLOUT}], 1, 0) = 1
sendto(3, "k\\374\\1\\0\\0\\1\\0\\0\\0\\0\\0\\0\\3www\\4news\\3com\\0\\0\\1\\0\\1", 30, MSG_NOSIGNAL, NULL, 0) = 30
poll([{fd=3, events=POLLIN, revents=POLLIN}], 1, 5000) = 1
recvfrom(3, "k\\374\\201\\200\\0\\1\\0\\2\\0\\0\\0\\0\\3www\\4news\\3com\\0\\0\\1\\0\\1\\300\\f"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, [16]) = 106
connect(3, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, 28) = 0
poll([{fd=3, events=POLLOUT, revents=POLLOUT}], 1, 0) = 1
sendto(3, "\\\\\\2\\1\\0\\0\\1\\0\\0\\0\\0\\0\\0\\3www\\4news\\3com\\0\\0\\1\\0\\1", 30, MSG_NOSIGNAL, NULL, 0) = 30
poll([{fd=3, events=POLLIN, revents=POLLIN}], 1, 5000) = 1
recvfrom(3, "\\\\\\2\\201\\200\\0\\1\\0\\2\\0\\0\\0\\0\\3www\\4news\\3com\\0\\0\\1\\0\\1\\300\\f"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("62.30.112.39")}, [16]) = 106
connect(3, {sa_family=AF_INET, sin_port=htons(80), sin_addr=inet_addr("216.239.122.102")}, 16) = -1 EINPROGRESS (Operation now in progress)
select(4, NULL, [3], NULL, NULL)        = 1 (out [3])

So what happens here? Notice the connection attempts to /var/run/nscd/socket? They mean nc first tries to connect to NSCD - the Name Service Cache Daemon - which is usually used in setups that rely on NIS, YP, LDAP or similar directory protocols for name lookups. In this case the connects fails. It then moves on to DNS (DNS is port 53, hence the "sin_port=htons(53)" in the following connect. You can see it then does a "sendto()" call, sending a DNS packet that contains www.news.com. It then reads back a packet. For whatever reason it tries three times, the last with a slightly different request. My best guess why in this case is that www.news.com is a CNAME (an "alias"), and the multiple requests may just be an artifact of how nc deals with that. Then in the end, it finally issues a connect() to the IP it found. Notice it returns EINPROGRESS. That means the connect was non-blocking - nc wants to go on processing. It then calls select(), which succeeds when the connection was successful. Try adding "read" and "write" to the list of syscalls given to strace and enter a string when connected, and you'll get something like this:

read(0, "test\\n", 1024)                 = 5
write(3, "test\\n", 5)                   = 5
poll([{fd=3, events=POLLIN, revents=POLLIN}, {fd=0, events=POLLIN}], 2, -1) = 1
read(3, "

This shows it reading "test" + linefeed from standard in, and writing it back out to the network connection, then calling poll() to wait for a reply, reading the reply from the network connection and writing it to standard out. Everything seems to be working right.


Other ideas?

I'd love to hear from you if you use strace in particularly creative ways. E-mail me (vidar@hokstad.com) or post comments.

Writing a compiler in Ruby bottom up - step 8

Sun, 01 Jun 2008 08:07:28 -0000

This is the eight in a series. Please start on part 1 first if you haven't already to get the background, or see here for the full series so far Last time we looked at an improved way of handling loops etc. using anonymous functions. But most of that is relatively limited if there's no way of modifying variables. Sure, you can get away with recursion and not allow mutation or even other side effects at all. It might satisfy some functional programming purists, but it would not satisfy me and it would also require some fairly sophisticated optimizations to get decent performance. I like the principle of reducing side effects as much as possible, and pushing side effects up, so much so that it's one of the factors I pointed out in my post about reducing coupling through unit tests. But I don't like sacrificing simplicity and/or performance for the sake of a "purer" approach. So lets introduce assignment, and at the same time add in basic arithmetic and comparisons.

Assignment

We'll cheat and keep what we introduce into the actual compiler as minimal as possible. That means assignments go into the compiler, and arithmetic and comparisons are confined to a new C runtime for simplicity for now. It is temporary, I promise. Just another shortcut. Why don't we give assignment the same treatment? Well, we could, if we introduced a transparent way of passing the address of a variable as an argument to a function, but it would still mean compiler changes, would be slower and it seems it wouldn't actually bring any benefits. Another reason for not taking that route is that it opens up a can of worns: If we allow taking the address of stack variables, it gets easy to shoot yourself in the foot by accessing it after the stack frame is dead. We could accept that risk (it's not like this compiler is a bastion of safety at the moment, with mostly no typing and no error checking to speak of), or we can introduce "environments" and guarantee that any variable you take the address of will live on the heap and stay alive until you lose the reference... But that's more complicated than I'd like right now. Environments is one of the approaches to keeping local variables "alive" in the heap that would let us do proper closures instead of mere lowly anonymous functions, though, so we might eventually bite the bullet. Adding assignment to the compiler is trivial anyway. Here's the first try:

  def compile_assign scope, left, right 
    source = compile_eval_arg(scope, right) 
    atype, aparam = get_arg(scope,left) 
    raise "Expected a variable on left hand side of assignment" if atype != :arg 
    puts "\tmovl\t#{source},#{PTR_SIZE*(aparam+2)}(%ebp)" 
    return [:subexpr] 
  end

Notice our first error message... We'll eventually need to bite the bullet and add lots more of those, as well as handling them a bit better than just letting the compiler fail with an exception message and a stack trace, but it's a start. What this function does is quite straightforward: It compiles the right hand expression, then copies the result into the variable. Can you spot the problem? It's not a bug, it's a feature! Right... It only allows assignment to a local variable. Whether that is indeed a bug or a feature is open for discussion - many languages does allow for assignment to function/method arguments as well as local (and sometimes global) arguments. I promise we'll look at this closer later, but for now it's simply not important. We then update #compile_exp by adding this:

   return compile_assign(scope,*exp[1..-1]) if (exp[0] == :assign)

And test it with this (the output needs to be linked with the arithmetic functions in the next step, or rather it at least needs :sub):

prog = [:call, [:lambda, [:i],
    [:do,
      [:printf, "Testing sub and assign (before): %ld\\n", :i],
      [:assign, :i, [:sub, :i, 1]],
      [:printf, "Testing sub and assign (after): %ld\\n", :i],
    ]
  ], [10] ]

Arithmetic and comparisons

Here's our new C runtime:

signed int add(signed int a, signed int b)
{
  return a + b;
}

signed int sub(signed int a, signed int b)
{
  return a - b;
}

signed int div(signed int a, signed int b)
{
  return a / b;
}

signed int mul(signed int a, signed int b)
{
  return a * b;
}

signed int ne(signed int a, signed int b)
{
  return a != b;
}

signed int eq(signed int a, signed int b)
{
  return a == b;
}

signed int not(signed int a)
{
  return !a;
}

// Note that our "and" won't shortcircuit, as the
// evaluation happens before this function is called.
signed int and(signed int a, signed int b)
{
  return a && b;
}

signed int gt(signed int a, signed int b)
{
  return a > b;
}

signed int lt(signed int a, signed int b)
{
  return a < b;
}

Not very exciting is it? I'm not going to try to make it very exciting, but it's worth considering what would be involved in adding compilation of it, though I won't complete that now. Lets look at a single example, "lt", and show the process, though you should be used to it by now. gcc -S on just the "lt" function gives:

lt:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %eax
    cmpl    12(%ebp), %eax
    setl    %al
    movzbl  %al, %eax
    popl    %ebp
    ret

(Uh-oh, what's that setl / movzbl stuff? This is an optimization - cmpl compares the two operands and set a number of condition codes. "set[something]" sets a value in a single byte register %al based on the condition codes - in this case "l" for less. "movzbl" then takes that byte, extends the value up to 32 bits by filling the remaining bits with 0 and puts it into %eax - don't worry about it) To add this to the compiler we'd do compile_eval_arg on the left and right arguments. After doing it to the left, we'd need to store the result somewhere temporarily, in case we try to use %eax again. We'd then need to issue the cmpl/setl/movzbl instructions, and we'd be done. The function could look something like this:

def compile_lt scope,left,right
    l = compile_eval_arg(scope, left)
    puts "\tmovl\t#{l},%ecx"
    r = compile_eval_arg(scope, right)
    puts "\tcmpl\t%ecx, %eax"
    puts "\tsetl\t%al"
    puts "\tmovzbl %al,%eax"
    return [:subexpr] 
end

Note that this is completely untested - I haven't even checked that I got the operands to cmpl in the right order. More importantly, this illustrates one reason for not jumping into this and spending time on doing the same thing for all of these functions right away: Notice that we needed a temporary register? Notice how that was wasteful, because we could have just put things into %ecx right away? Notice how this is a recipe for a lot of pain, because we might have even more complex situations where it is handy (though not strictly necessary) to have even more temporary registers? Register allocation is a huge subject in itself. It boils down to figuring out the most efficient way of stuffing a large number of temporary and long lived variables into a very scarce (on the x86 in particular) resource, namely registers. You want to make the most of them, because access to registers is generally far faster than memory accesses, and because many architectures have instructions that requires the use of specific registers for specific purposes. It gets complicated fast, because while using a register when you can is good, "spilling" - that is the process of storing a variable back to memory and loading another variable it it's place - when you have more variables in use than registers can get even more expensive than accessing things straight from memory in the first place. Figuring out what combination of variables is most efficient to keep in registers or move in and out of registers is something that can make grown men cry, and many simple compilers just ignore this problem and pick a very simple and inefficient approach. At least reading the wikipedia article linked to above is worthwhile if you want to know more about this, though a few searches should turn up a lot of papers. I don't intend to add any advanced register allocation to this compiler until it's far closer to being functionally complete. But we will need to deal with some of it, but it's something I'd rather defer doing a proper implementation of until more functionality is in place for the simple reason that doing it well is a hell of a lot of work, and doing a half assed job at it will at least make things work, even though performance will suffer.

Wrapping it up

Since there's now a separate file for the C runtime support, I've tar'ed up the files for step8 together with a Makefile here. If you have Ruby, make and gcc installed you should be able to just untar it and run make to get the "step8" test binary:

$ make
ruby step8.rb >step8.s
as   -o step8.o step8.s
cc    -c -o runtime.o runtime.c
cc   step8.o runtime.o   -o step8
$ ./step8 
Testing sub and assign (before): 10
Testing sub and assign (after): 9
$

TraceViz: Visualizing traceroute output with graphivz

Thu, 29 May 2008 10:32:25 -0000

At Edgeio we had a fairly complicated network setup, and at one point I quickly hacked together a Ruby script to merge the paths generated by multiple traceroute runs together into directed graphs, showing the routing from a few selected host in our environment to all our other hosts. I generated dot-files suitable for Graphviz from it. It was a helpful way of looking for weird inconsistencies in routing, in particular between our two locations. Unfortunately, when Edgeio closed down I think the script was lost, and in any case if it isn't I wouldn't be able to get permission to release it without more hassle than it'd take me to recreate it from scratch. So recreate it from scratch is exactly what I did. Here's an example of a traceroute from www.hokstad.com to www.gmail.com, docs.google.com and www.google.com (scaled down): (Gradients and shadows courtesy of my XSL transform to make graphviz output prettier) There's a couple of caveats: I just strip out failed probes, and I don't try to reconcile the names of the endpoints (which I preferred to include for readability) with the IP addresses of the trace, so the first/last grey nodes before the named/blue nodes may be redundant. This script by default runs traceroute 3 times for each target, and that's the reason why there are more possible paths than endpoints, and it illustrates failover and/or load balancing mostly, but can also be affected by fluctuations in dynamic routing. It's usually fairly stable, and in fact at Edgeio I found several network problems by re-running the script when something was up and looking at how the routing had changed. 3 runs seemed sufficient for my use, but for large networks adding more may give a better picture of the routing.

The Ruby script

You can find the full script here, but here are the guts: First I defined a convenience method to run traceroute and capture the output. This is intended for a POSIX OS (Linux / Unix / BSD's), but mainly requires a working traceroute where the output is a number of lines starting with a hop count and then the ip address. TRACEROUTE must be set to a valid traceroute command.

TRACEROUTE=`which traceroute`.chomp

def traceroute host
  `#{TRACEROUTE} -n #{host}`
end

The TraceViz class does the gruntwork. @edges contains the edges of the graph, in other words which pairs of ip addresses represent a hop further in the network. @nodes contains a set of the ip addresses found. @targets contains the hostnames of the start and end-points - it's used only to style them differently:

class TraceViz
  def initialize(times,timeout)
    @times,@timeout = times,timeout
    @edges = Set.new
    @nodes = Set.new
    @targets = Set.new
    @this_host = Socket.gethostname
    @targets << @this_host
  end

The #trace method executes the traceroutes, and enforces a timeout:

  def trace host
    @times.times do |i|
      STDERR.puts "Trace ##{i+1} for #{host}"
      Timeout::timeout(@timeout) do
        process_trace(host,traceroute(host))
      end rescue nil
    end
  end

#process_trace handles the parsing of the trace, by splitting the output into lines, extracting the IP addresses, and then adding each of them to @nodes, and adding each pair to @edges. I don't care if we've seen them before, since I use Set's so the previous (identical) nodes/edges will just overwrite the same values:

  def process_trace host,trace
    @targets << host
    trace = [@this_host] + trace.collect do |line|
      line=line.split
      line[0].to_i > 0 && line[1] != "*" ? line[1] : nil
    end.compact
    trace << host
    trace.each {|h| @nodes << h }
    trace.each_cons(2) {|h1,h2| @edges << [h1,h2] }
  end

Finally #to_dot generates a graphviz compatible directed graph:

 def to_dot
    res = "digraph G {"
    @edges.each { |h1,h2| res << "   \"#{h1}\"->\"#{h2}\"\n" }
    @nodes.each do |n|
      color = @targets.member?(n) ? "lightblue" : "lightgrey"
      res << "  \"#{n}\" [style=filled fillcolor=#{color}]\n"
    end
    res << "}"
  end
end

Running it and generating the image

First run the script to generate the dot-files, and then generate an SVG file from it:

ruby traceviz.rb www.google.com www.gmail.com docs.google.com >trace.dot
dot -Tsvg trace.dot >trace.svg

Optionally, process the script with my XSL transform to make it prettier (adding the gradients from above etc) - I'm using xsltproc from libxslt:

xsltproc notugly.xsl trace.svg >trace-notugly.svg

Then I used "rsvg" from librsvg2 to turn it into a PNG:

rsvg trace-notugly.svg traceviz.png

Of course these steps are easily enough wrapped into a script.

Inversions (Iain M. Banks)

Wed, 28 May 2008 17:55:13 -0000

I just finished reading Inversions. It's a novel set in Iain Banks massive Culture setting, but at the same time not. If you haven't read any Culture novels before, don't start with this. If you have, you may either love or hate this depending on whether you read Banks books for their "space opera" qualities or for the twists and turns and explorations of culture and alien societies. On the surface it's not even clear to a casual reader that it is science fiction. It reads like fantasy: The setting is clearly alien, with two suns and multiple moons, and it's set in a roughly medieval setting, perhaps sort of an early renaissance equivalent. But if you've read the other Culture novels, the book is littered with hints that the two main characters whose respective stories are intertwined, forming the "inversions" are clearly Culture. We don't know who they are - they could be agents of Contact or Special Circumstances, or they could be individuals with their own agendas, or perhaps just shipwrecked aliens waiting for their ride home? Sometime before the story starts the world it is set on is hit by a devastating catastrophe of "burning rocks" falling from the heavens, yet we don't know if it's a meteorite, an intentional interference, or perhaps a massive Culture ship crashing into the atmosphere? From other books, it's clear that Culture citizens have artificially expanded life spans, so the protagonists in Inversions could have been there much longer than you'd expect. The story is at once intensely annoying it it's lack of answers (at a level only beaten for me by The Alien Years by Robert Silverberg, where the extremely infuriatingly annoying ending is at the same time genius) while at the same time on the surface the stories that are "complete" - the main protagonists, the Doctor and the bodyguard, each serving their respective rulers, conclude their "missions" with varying results. There is resolution. We just don't get to read the why's how's. But we "see" knife missiles and possibly other Culture tech at work without getting any firsthand descriptions of any of it. There's technology or magic, or the characters are just better than we give them credit for, but the "technology" explanation is by far the easiest to accept. The book can be read with no thought of the Culture, and it's meaning is intact - a story told by DeWar the bodyguard to the son of the ruler he serves hints strongly at the role of DeWar and his counterpoint - the doctor Vossil - and their opposite viewpoints on whether it is right to "be cruel to be kind", or in other words whether it is acceptable to interfere with someone in ways that "teaches a lesson" or if you should leave other civilizations to develop at their own pace. I've seen many reviews claim that Banks takes a clear stand for one of them, but while he seems to favor one it's not that clear cut. One country prospers, and the other falls into disarray, but towards the end it is also clearly hinted that things have since improved again, and the book cuts off too early to see the longer term impact. While one character is also clearly interfering far more, it is also not black and white - why did both characters choose to serve the ruler of their respective countries? Both of them have put themselves in situations where their success or failure directly interferes with the political stability of their respective countries - even the character who supposedly favors non-interference ends up saving a life that ultimately affects the line of succession in that country. But is that interference different because it is "personal" and apolitical? An act carried out because of duty in a job, not because of ulterior motives? Inversions is Banks' most obvious work of social science fiction taken to the extreme, reminiscent in some ways of Ursula K. Leguin's scifi, which often is close to fantasy on the surface despite obviously alien settings, though the motives that are hidden in Inversions are very much in plain sight in novels such as The Left Hand of Darkness. Both are about the people and at the same time about culture-clashes and explore interactions between highly developed cultures (The Culture and the Ekumen) vs. relatively primitive societies, but in both cases societies that are describe with a certain level of sensitivity. The "natives" may be primitive, but they are not bad as people, just products of their environment; and both sides learn - it's not a one way street. But all of Banks' scifi fit in this category - it is just often easy to ignore behind all the glitzy space opera and the vast vistas spanning planets and systems and involving billions of beings. Indeed, Banks' other novels are so good at combining both that you can read them for one or the other and be quite happy, while Inversions will seem to fall flat on it's face for you if you don't enjoy social scifi. I'd say you're likely to enjoy it if you like Ursula K. LeGuin, or the social aspects of books like Brian Aldiss' Non-Stop, Kim Stanley Robinson's Three California's trilogy (i.e. if you enjoy all three and the way they juxtapose different societies rather than enjoy them just for the technological aspects), than if you mostly prefer "hard SF" or pure space opera and demand visible techonology to accept something as SF. Inversions is perhaps the "hardest read" of Banks' science fiction books exactly because it's so much on the fringes of sci-fi and hides so much of the "real story" from the readers, forcing you to pay more attention than most sci-fi, which has a tendency to shove it's ideas in your face even when those ideas are deep and profound. But that serves as a reminder that there is a lot of subtlety in Banks' other Culture books, and the casual reader that read them just as space opera will miss a lot.

OpenVZ and Apache troubleshooting: PRNG still contains insufficient entropy!

Sat, 24 May 2008 11:33:55 -0000

I was setting up Apache on OpenVZ earlier today, and ran into a problem with enabling SSL. Apache would refuse to start, and I'd see this in the error log:

[Sat May 24 07:48:10 2008] [warn] Init: PRNG still contains insufficient entropy!
[Sat May 24 07:48:10 2008] [error] Init: Failed to generate temporary 512 bit RSA private keyConfiguration Failed

The solution is quite simple, though not very intuitive. On the host do this (replace "100" with the name or id of your OpenVZ container):

vzctl set 100 --devices c:1:8:rw --save
vzctl exec 100 mknod /dev/random c 1 8
vzctl set 100 --devices c:1:9:rw --save
vzctl exec 100 mknod /dev/urandom c 1 9

Apache's SSL support requires /dev/random and /dev/urandom to seed the PRNG. Note that if only /dev/urandom is missing, Apache may seem to start, but eat all CPU. If you attach "strace" to it, you may see it spin over attempting to open /dev/urandom over and over.

Reducing coupling through unit tests

Thu, 22 May 2008 14:13:08 -0000

After my previous post on the subject of coupling and cohesion, a lot of the feedback I've gotten has been from people who want examples of lowering coupling, or want to know how they can see if their code is loosely coupled. The easiest way I know of doing that also has other benefits: Whether you prefer Behavior Driven Development or test driven development, or you call it something completely different, writing unit tests provide you with one or two essential things:

If you write the tests up front, you will instinctively be guided to writing loosely coupled code
If you add tests "after the fact", you will clearly see whether your code is loosely coupled.

How unit testing help reduce and/or measure coupling

The Wikipedia article on coupling provides this definition:

Low coupling refers to a relationship in which one module interacts with another module through a stable interface and does not need to be concerned with the other module's internal implementation.

The thing is, when you write unit tests, you are putting the unit being tested into a harness. You need it to interact with your test code, and still carry out its functions. If you write the tests upfront, you have two alternatives: Either you create a hugely complex harness with lots of mock objects, or you write your code in a way that makes it easy to call in isolation. That is another way of formulating low coupling: A module exhibits low coupling if it is easy to call in isolation. Unit testing under any name is a good test of the ability to call your code in isolation Testing after the fact gives you a measure of how well you have done: If you have written code with low coupling, it should be easy to unit test. If you have written code with high degrees of coupling, you're likely to be in for a world of pain as you try to shoehorn the code into your test harness. If you haven't bought into TDD/BDD for other reasons, consider it for this reason. Try it. The structure of your code will change if it wasn't previously loosely coupled, as you'll quickly tire of writing horrendously complicated tests.

Some indicators of the level of coupling

Can you test the code with trivial unit tests? (I.e. no or few mock objects, no huge amounts of setup or teardown code.) If you can, your code is likely loosely coupled.
Do you find yourself struggling to test modules independently of eachother? Almost certainly high coupling.
Does the code have lots of side-effects in low level code? This is a warning sign - it very often lead to code that is harder to test, for example because it might mutate state on lots of unrelated objects. It's not always avoidable, though, and if well managed, it doesn't need to lead to high coupling - the trick is to isolate the calls that cause the side effects from the external environment through the use of the adapter pattern or similar.
Is the code "controlled from the top"? In other words, does the code pass results indicating actions up the call chain instead of having side effects? Code that consistently does this tend to be looser coupled (and easier to unit test) than code that have side effects, as long as the actions passed up are as generic as possible (in other words, it doesn't help if the action passed back for example is an object that when called will invoke a specific method on an object of a specific class - in that case you're just delaying execution of a side effect rather than decoupling anything).
Is the code highly cohesive? That is, does each module carry a single, reasonably simple responsibility, and is all the code with the same responsibility combined in a single module? If code implementing a single feature of your application is littered all over the place, or if your methods and classes try to do many different things, you almost invariable end up with a lot of coupling between them, so code with low cohesion is a big red flag alerting you to the likelihood of high coupling as well.

The last point highlight that looking just at coupling in isolation isn't all that helpful. But thankfully, if you strive to reduce coupling, one of the key things you end up doing a lot of the time is write more cohesive code. If you're constantly focused on ensuring code can be tested in isolation, there are few ways around that without making each module cohesive.

Would you like to live in the Culture?

Wed, 21 May 2008 09:39:24 -0000

If you haven't read Iain Banks' books about The Culture you should be ashamed. I've seen it referred to as dystopic some places, though I never found it that way, and this is what Iain Banks had to say about it himself in a reasonably interesting recent CNN interview:

Iain M. Banks: Good grief yes, heck, yeah, oh it's my secular heaven ... Yes, I would, absolutely. Again it comes down to wish fulfillment. I haven't done a study and taken lots of replies across a cross-section of humanity to find out what would be their personal utopia. It's mine, I thought of it, and I'm going home with it -- absolutely, it's great. CNN: What's it like, being a humanoid as part of the Culture? Iain M. Banks: It's pretty great being a human in the Culture, with the drug glands and enormously long orgasms. You can change sex if you want to, and you have total control over pain, and blister-free callusing. That wasn't one of mine, that was Ken MacLeod, my chum and fellow SF scribbler -- "I've just thought of a good improvement for the human body: Blister-free callusing!" -- so I made a particular point of putting that in ...

Blister free callusing is something I'd welcome after gym this morning...

Confessions of a Commodore 64 remix addict

Tue, 20 May 2008 18:50:59 -0000

I admit it, I'm impossibly geeky at times. Sometime last summer I re-discovered Commodore 64 music. Slay Radio, which primarily plays remixes of old Commodore 64 music, as well as some original tracks inspired by the era of 8-bit home computers became what I listened to while sitting in front of our open garden doors and working on Edgeio throughout most of the summer. My wife don't really consider it music, but to me it's the music that I listened the most to from '83-'84 and until at least '91. Many of the tracks are truly iconic, and feature artists that provided the soundtrack for the lives of millions of people who where kids in the 80's, yet who are virtually unknown outside a group of mostly 30-something hardcore geeks who grew up spending more of our childhood in front of our computers than chasing girls. Personally, I didn't listen to much mainstream music until the early 90's, and even since then it's mostly been incidental. But I listened to hours and hours worth of computer game music and demo music every day, and later to hours of electronic music like Jean-Michel Jarre who was perhaps the major inspiration for a large part of this sub-culture. (You can see this inspiration even now, with remixes such as Rolands Rat Race - The Quest for Jarre by Traxer, which mixes an early Martin Galway tune with a lot of Jarre influences) Before I finally left the Commodore 64 behind for the Amiga, I'd learned to love the SID music dearly. It has a special combination of minimalism (being limited to 3 voices, and with very limited space as well as having to synthesize the "instruments" from basic waveforms combined with some extremely limited sampling capabilities) and the heavy influence of Jarre and other electronic music pioneers such as Kraftwerk (who I just discovered has a wonderfully bizarre website including things such as a musical calculator) and a certain 80's flair. Most of my favorites are "obvious" - classics that in some cases made their games. Many of them are also amongst the easiest accessible for people who haven't heard the originals. Here are some of them (I didn't realize before I started putting the list together how many of these tracks are based on Rob Hubbard originals... What can I say, the man is a genius):

Commando (Instant Remedy, based on Rob Hubbards C64 version) - the music from Commando is one of the all time greats in my opinion; the original is fantastic, and this remix manages to capture the feel very well. This is the type of music that would get me to turn up the volume until our parents were shouting from downstairs - proper remixes of Command hits you like a wall, and give just the right feel for the game
I-Ball (The St. Albans Rob Hubbard Fan Club, based on Rob Hubbards tune) - Never had much of a relationship to I-Ball when I was a kid, but I love this remix.
Delta (Chris Abbott, from yet another Rob Hubbard track) -- Delta is a tricky one. The original is near perfect, and most of the remixes start far too slowly or go all soft with pianos etc.. The Chris Abbott version also start to slowly, but It's the best I've found. To show the span in the remixes, here's an orchestral version by Matti Paalanen. It's a beautiful piece, but to me the Delta theme should be fast paced and electronic like I remember it...
Lightforce (Allister Brimble, based on Rob Hubbards track) -- Definitively one of the games that was "saved" by an absolutely iconic soundtrack. When I first started downloading remixes this was one of the first ones - I remembered the soundtrack only vaguely remembered the game, and decided to play it on an emulator and was bitterly disappointed. For another great take on this tune, here's Rob Steptoe's "Unstable Asteroids" remix. Much less faithful to the original than Allister's, but a lot more polished.
Cobra (Jazzed up remix) (Cytex, based on a tune by Ben Daglish -- Cobra was another game largely saved by the music. The game was fairly good, but the music is one of the most iconic game tunes of the 80's. This remix is a lot "softer" than the original, but I love it.
The Human Race (Melodie Eine) (Das Karl Werk Project, based on, you guessed it, Rob Hubbard's original) -- I loved this tune, though I never got into the game. Most remixes are of melody 4, but this version of the first tune is very faithful and is a great "upgrade" while it probably doesn't bring that much new (but that's not needed with an original as good as this tune).
Human Race, subtune 4 (Visa Roster / Rob Hubbard) -- This is something unusual. Visa Roster is a Swedish group that mainly does a capella music, and this is no exception - a fantastic version of Human Race melody 4 done completely a capella.
IK Hamburg Extravaganza (J Krafft, based on International Karate by Rob Hubbard) -- This isn't faithful to the original at all, but it manages to incorporate enough elements of it while still being great as an original work in itself.
Monty On The Run (video, C64 Orchestra live, tune by Rob Hubbard) -- Monty on the Run was considered a breakthrough for the realistic sounding (by 8 bit standards) orchestral instruments, and it's fitting that it's one of the very well done orchestral arrangements that's being played live by the C64 orchestra.
Warhawk (Press Play on Tape / Rob Hubbard) -- Warhawk is another fast paced track, and this is another live rendition by the C64 tribute band Press Play on Tape.
Outrun (Instant Remedy, tune by Jason C. Brooke) -- Outrun is another icon. The arcade version was one of the first truly "immersive" driving games and left us in awe when it arrived. The C64 version was primitive by comparison, but the music was fantastic, and the Instant Remedy version captures it perfectly with a mix of the original c64 soundtrack mixed in with a modernized dance beat.

There are many, many more (and many non-Rob Hubbard tracks too, I promise...). The hardest is to sort the many craptastic remixes from the truly great ones. Remix64.com is a fantastic resource. Now to go looking for Amiga tracks...