QINSB is not a Software Blog

Stack crawling in DrMemory without frame pointers or debug info

2011-12-12T16:28:00.000-08:00

I work on DrMemory, a dynamic instrumentation tool for finding memory bugs in native apps similar to memcheck, more widely known as just Valgrind. We have to be able to generate stack traces in a wide variety of interesting situations, and we want to do it quickly and without depending on slow, non-portable, and hard to integrate libraries.

If you remember your early computer systems classes, you'll recall those exam questions about unwinding the stack by chasing the base pointer. The reality is that for years we've been stuck with x86_32, which has a measly 8 general purpose registers, and compilers have been itching to grab that tender little %ebp register. So, they took it, and now the world is much more complicated because walking the stack is a whole lot harder.

To unwind the stack, we need to answer the question: given the stack pointer (SP) and program counter (PC), what is the offset from the SP to the next return address? With that, we can repeat the question until we hit main (or NULL or whatever).

Maintaining a huge table mapping any arbitrary module offset to a stack offset would waste a lot of space, so most systems use some form of state machine encoding that can compute the value on the fly, should you need to walk the stack. (Win64 SEH uses an interesting mechanism involving carefully constructed prologues which I'd like to learn more about.) If stack walking is rare, such as for an "exceptional" exception or when in the debugger, then the state machine (DWARF CFI) works great. But if you need to do it all the time and you need to do it on multiple platforms, it will be slow, you will need platform-specific code, or you will need to depend on some other library. Pulling arbitrary code into a tool that runs in the same as the address space as the application can often break isolation between the tool and the app, so we don't like to do it very often.

However, we're in dynamic binary instrumentation land, so we get to see every instruction as it's executed. The next most obvious solution for unwinding is what we call the "shadow stack" solution. Every time you see a call or ret instruction, you just push or pop the PC on to or off of the current thread's shadow stack. If you need to record lots of stack traces, then this may be your best bet, especially since you can imagine logging these updates and then recording a trace is as easy as logging a timestamp. I believe that this is what ThreadSanitizer does, because they need to produce a stack trace not just for the current memory access, but for the other memory access that races with the current thread.

For a tool like DrMemory, we only need to store stack traces for every heap routine invocation, which is not nearly quite as often. We also don't want to unnecessarily slow down an app that performs many calls in a loop without calling any heap routines or creating any memory bug reports. You also have to worry about a lot of corner cases, such as an app which clobbers the return addr to go somewhere else, or longjmp, or exception handling.

The solution we use is I think quite elegant. First, if there are frame pointers, we use them, because it's fast (like iterating a linked list that's in cache :). While the compiler may get a 10% perf boost from an extra register, we get a bigger boost by not doing a "scan", which is what I am about to describe.

If we don't have frame pointers, we start with the stack pointer, and scan each pointer-aligned cell for a value that looks like a pointer into executable memory. This part is obvious, and you can get Windbg to do the same thing and symbolize it to boot (anyone know how to do this in gdb?).

The problem is that most code rarely initializes its entire stack frame. In any given frame, there is a lot of spill space for temporaries in unexecuted code, or arrays that are not filled. This means that stale return addresses from prior frames are still on the stack. The clever bit is realizing that we're already shadowing every memory write to track definedness information to find uninitialized reads, so we actually *know* which bytes are initialized and which are not. That means we can tell what is a probable return address and what is stale.

Still, what if the app stores a function pointer to the stack? That will look like a code pointer and show up as an extra frame. The next bit of cleverness is where we take the candidate return address and look backwards in the code for likely encodings of a call instruction. This is pretty straightforward, as there are only a handful of encodings for direct and indirect calls, and we can just enumerate the opcodes along with their offsets. If it's a function pointer, this test should fail, unless we're really unlucky.

And with that, we have our (mostly) reliable, (reasonably) performant, and (mostly) portable stack crawler! :) To my knowledge, Memcheck doesn't attempt any of this craziness, and encourages you to recompile with FPs if it gets a weird looking stack.

Edit: Comments on G+ are preferred, since I'll actually respond.

Early injection of DBI frameworks on Linux

2011-08-11T09:57:00.000-07:00

I just had an interesting discussion with Qin Zhao about how the various instrumentation frameworks out there achieve early injection. I haven't actually cross-checked this all at all, so it may not be 100% accurate, but I thought it was interesting enough to write down.

Early injection is the ability of a binary instrumentation framework to interpret an application from the very first instruction. On Linux, applications do not start life in userspace at main. They start life at _start, and that usually hops into the dynamic loader to bring in the shared libraries such as libc. Usually this code is very similar for every application, and you don't need to instrument it to find uses of uninitialized memory in your application. However, its possible you have an app that doesn't use the dynamic loader, or there really are bugs there you want to see. A related problem is how to load your own dynamic libraries without conflicting with the loader being used by the application. Typically the DBI framework will load two copies of libc: one for the application, and one for the framework and its libraries. DynamoRIO, Valgrind, and Pin all have different ways of loading and injecting with different tradeoffs.

DynamoRIO is the easiest, because we don't support early injection on Linux. (Windows is a different story which I can't speak to.) We simply set LD_LIBRARY_PATH and LD_PRELOAD in a shell script that wraps the application invocation. This way, the loader will pull in one of our shared libraries, and call _init, at which point we take control. Instead of returning back to the loader, we start interpreting from where we would have returned. For DynamoRIO's dynamic libraries, the most important of which is the actual tool that you want to run, ie your race detector or memory debugger, we have our own private loader which keeps its own libraries on the side and does all the memory mapping and relocations itself. This is a pain, since it practically reimplements all of the system loader, but we do have the ability to place restrictions on the kinds of libraries we load to make things easier.

Valgrind is the next easiest, since it's basically the inverse of the above strategy. The command "valgrind" is a proper binary, so the system loader kicks in and loads all of Valgrind's libraries for it. It can use dlopen to bring in the tools it wants. To load libraries for the application, Valgrind has a private loader similar to our own, except that it loads the application's libraries instead of Valgrind's.

Finally, Pin has the most interesting strategy. Pin does not have it's own loader. Pin is also a proper binary. They start by loading all the libraries they ever want, including the tool you want to run, using the system loader (dlopen, etc). Then they fork a child process. The *parent*, not the child, sets up a call to exec to match the invocation of the application. Somehow, probably using ptrace or some other API, the child is able to pause the parent application before the first instruction and attach. The child then copies its memory map into the parent. If there are conflicts, it errors out. The child then redirects execution to Pin's entry point, which eventually starts interpreting the application from _start.

Pin's approach allows early injection without the maintenance burden of a private loader. However, it can cause conflicts with the application binary and requires heuristics to set preferred addresses which won't conflict. It also slows down startup, due to the extra forking and memory mapping and copying. Personally, I think this is pretty cool, even if it has some transparency issues.

FLAGS dependencies on x86

2011-05-05T12:39:00.000-07:00

One big annoyance I have with x86 in my work on DynamoRIO is the special FLAGS register. You can't read or write to it like a normal register, and 2/3 of the bits are reserved or always 0 or 1. The only easy way to get flags in or out is to use pushf and popf, but in DynamoRIO we can't use those without switching off the application stack, since it could be doing things like using the x86_64 Linux red zone. So, we try to avoid clobbering FLAGS in inserted code whenever possible. For example:

You wanted to subtract a constant? Instead of "sub $-1, %rax" try "lea -1(%rax), %rax". Works for add, too.

With the more complex base, displacement, index, scale, and offset form of the x86 memory operand, you can get even more fancy, accomplishing small shifts and multiplies and register to register adds using the LEA instruction. You can even get a 3-operand add like so:

lea 0(%rax, %rbx, 1), %rcx

Which adds %rax and %rbx and stores the result in %rcx. Another old trick is multiplication by 5, which works like so:

lea 0(%rax, %rax, 4), %rax

This is powerful enough to perform register to register adds and simple arithmetic with constants, but we can't yet subtract a register from another. Unfortunately, SUB and NEG both touch FLAGS. However, the NOT instruction does not. This means, assuming %rax is dead, we can rewrite "sub %rax, %rbx" like so:

not %rax

lea 1(%rax, %rbx, 1), %rbx

Remembering how two's complement works, negation is equivalent to a complement and add one. Addition is commutative, so we can fold the increment into the displacement field of the LEA.

Finally, you can also use JRCXZ (JECXZ in 32-bit land) to perform a jump if RCX is zero, without looking at flags. Putting it all together, you can implement equality checks without changing flags like so (assuming one of %rdi or %rsi and %rcx are dead or have been saved):

Flags code:

cmp %rdi, %rsi

je .Llabel

No flags code:

not %rsi

lea 1(%rdi, %rsi, 1), %rcx

jrcxz .Llabel

I haven't checked, but I imagine the compare is faster. However, in DynamoRIO, we have to save the flags for the cmp, which requires three instructions to save and to restore. With that factored in, I have a feeling the no flags version may be preferable. I will have to implement the no-flags transformation and see if it performs better.

Unfortunately, the toy client I am developing with has code like this:

lea -1(%rdx), %eax

test %rax, %rdi

jz .Llabel

Which performs an alignment check (assuming rdx is a power of two). I'm not sure how to implement an arithmetic AND (which is what TEST does) without touching flags.

HipHop talk

2011-04-06T15:39:00.000-07:00

I just went to a talk by Facebook HipHop engineer Haiping Zhao about various systems issues FB has had. There was a discussion of language issues with data movement in distributed systems and how to get that right, but I'm going to focus on HipHop, Facebook's open source PHP to C++ translator, since that's more up my alley.

Thinking carefully about HipHop, it seems to make better tradeoffs for large web deployments than the (at this point) traditional JIT approach. HipHop essentially trades compilation time, code size, and maximum performance for performance predictability and immediate startup performance. Furthermore, static compilation is probably perceived as being less likely to have bugs than a JIT compilation to someone in charge of deploying the system, although I would argue against that perception.

The main argument against static compilation of dynamic languages is that you don't have enough information to generate efficient code, and that you need to be able to run it before compiling it. To address that, HipHop is uses feedback directed (aka profile guided) optimization, even though PGO has never caught on in the C/C++ world. Essentially, they translate all their PHP to instrumented C++ to get types of variables, and then run that on an instance with a model workload. The compile takes about 15 minutes to make a 1 GB binary (the gold linker helps), and the profiling takes about another 15 minutes. Then they re-do the compilation with the profile information. This allows optimizations like speculating the target of a call, and speculating the type of a variable as being int or string, the easy to optimize types.

I would argue that this approach won't have as good peak performance as a JIT, which only has to generate the specialized version of the code, and can do some more clever optimizations. Also, a JIT can always fallback to the interpreter for the general case. If your profiling ends up being wrong (unlikely), a JIT can respond appropriately.

The drawback of the JIT is that you don't know when or if your code is going to get compiled, and you have to wait for that to happen. Debugging performance problems with JITed code is tricky. On the other hand, there are many solid tools for profiling C++, and mapping that back to PHP doesn't sound too hard.

It's probably possible to do a little better in the static model by avoiding generating or loading code for slow paths that you feel will never actually be loaded. I imagine right now the generated code looks like:

if (is_int(v)) { /* large int code */ }
else { /* massive general code */ }

The else branch is probably never taken. It seems like there should be techniques to either move the else branch far away from the hot code so that the cold code is never even faulted in from disk, or you could try to rig up a fallback to the interpreter, which I think would be much harder and not help your code size. On the other hand, branch predictors these days are good and moving code around is really only going to show up as instruction cache effects, which are pretty hard to predict. HipHop probably already uses __builtin_expect to tell g++ which branch it expects to take as well.

One other major thing I remembered during the talk is that optimizing PHP turns out to be much easier than Python. In Python, functions, classes, and globals in a module all share the same namespace. In PHP, variables start with a $ and functions do not. Short of eval, which HipHop forbids, there is no way to shadow a function without the compiler noticing that it might be shadowed. For example, this works:

if ($a) {
  function foo() { return true; }
} else {
  function foo() { return false; }
}

But this is not possible:

function foo() { return true; }
function bar() { return false; }
foo = bar;  // No can do.

You can also invoke functions through variables, like so:

function foo() { return true; }
$func = "foo";
$bar = $func();

That will set $bar to true. This is generally rare and easy to implement by falling back to the standard dynamic lookup.

OTOH, local variable lookup seems like it sucks because PHP supports something like the following:

$which = $a ? "foo" : "bar";
$$which = "string";

Which will assign "string" to the variable $foo or $bar depending on whether $a is true or false. Hopefully the scoping rules restrict this to the scope of the local function, so you only need to worry about this feature in functions that use it.

Another feature of HipHop is that, once you forbid certain features like eval or using include to pull in generated or uploaded source from the filesystem, you get to do whole program compilation. One of the major optimization blockers even for C and C++ is that the compiler only gets to see a translation unit (TU) at a time. HipHop gets to see the whole program, so it makes it possible to do the checks I mentioned earlier, like making sure that there is only a single definition of a function 'foo' at top-level which is always present, so you can statically bind it at the call-site even if it's in a different source file.

Finally, Haiping mentioned that the massive binary produced is deployed to servers using BitTorrent, which surprisingly seems like exactly the right tool for the job. You could try to be more clever if you knew something about the network topology, or you could just use a general, well-tested tool and call it a day. =D

P.S. Hopefully none of this is considered FB confidential and Haiping doesn't get in any trouble. It was a very interesting talk!

Building spec benchmarks with newer libstdc++

2011-03-30T18:32:00.000-07:00

This post is mostly for the sake of others searching with the same problem.

I was having issues building the 483.xalancbmk benchmark with a not-so-new libstdc++ (4.3.4). There's a particular source file (FormatterToHTML.cpp) that uses memset without including string.h or cstring. This was the error message:

FormatterToHTML.cpp:139: error: 'memset' was not declared in this scope

It depended on an include of 'vector' to pull in 'cstring' as a transitive dep. That seems to have changed. Since the SPEC benchmarks go so far as to checksum the benchmark sources before letting you run them, it was easier to add '#include <cstring>' to /usr/include/c++/4.3.4/vector than fix the application. =(

Unladen Swallow Retrospective

2011-03-26T10:57:00.000-07:00

I wrote this while I was at PyCon, but I kept revising it. Anyway, here goes. :)

As is apparent by now, no one has really been doing any work directly on Unladen Swallow or in porting it to py3k. Why not?

Lack of Personal Interest

Most of this was decided around Q1 of 2010. We still could have chosen to pursue it in our spare time, but at that point things looked a little different.

First of all, it's a lot less fun to work on a project by yourself than with other people, especially if it's unclear if you'll even have users.

Secondly, a large part of the motiviation for the project was that we felt like PyPy would never try to support CPython C extension modules or SWIG wrapped code. We were very surprised to see PyPy take steps in that direction. That somewhat obviated the need to build a bolt-on JIT for CPython. Also, when the project was launched, PyPy didn't have x86_64 support, but in the meantime they have added it.

Finally, the signals we were getting from python-dev were not good. There was an assumption that if Unladen Swallow were landed in py3k, Google would be there to maintain it, which was no longer the case. If the merge were to have gone through, it is likely that it would have been disabled by default and ripped out a year later after bitrot. Only a few developers seemed excited about the new JIT. We never finished the merge, but our hope was that if we had, we could entice CPython developers do hack on the JIT.

So, with all that said for why none of us are working on Unladen anymore, what have we learned?

Lessons About LLVM

First of all, we explored a lot of pros and cons of using LLVM for the JIT code generator. The initial choice to use LLVM was made because at the time none of us had significant experience with x86 assmebly, and we really wanted to support x86 and x86_64 and potentially ARM down the road. There were also some investigations of beefing up psyco, which I beleive were frusturated by the need for a good understanding of x86.

Unfortunately, LLVM in its current state is really designed as a static compiler optimizer and back end. LLVM code generation and optimization is good but expensive. The optimizations are all designed to work on IR generated by static C-like languages. Most of the important optimizations for optimizing Python require high-level knowledge of how the program executed on previous iterations, and LLVM didn't help us do that.

An example of needing to apply high-level knowledge to code generation is optimizing the Python stack access. LLVM will not fold loads from the Python stack across calls to external functions (ie the CPython runtime, so all the time). We eventually wrote an alias analysis to solve this problem, but it's an example of what you have to do if you don't roll your own code generator.

LLVM also comes with other constraints. For example, LLVM doesn't really support back-patching, which PyPy uses for fixing up their guard side exits. It's a fairly large dependency with high memory usage, but I would argue that based on the work Steven Noonan did for his GSOC that it could be reduced, especially considering that PyPy's memory usage had been higher.

I also spent the summer adding an interface between LLVM's JIT and gdb. This wasn't necessary, but it was a nice tool. I'm not sure what the state of debugging PyPy is, but we may be able to take some of the lessons from that experience and apply it to PyPy.

Take Aways

Personally, before working on this project, I had taken a compiler class and OS class, but this experience really brought together a lot of systems programming skills for me. I'm now quite experienced using gdb, having hacked on it and run it under itself. I also know a lot more about x86, compiler optimization techniques, and JIT tricks, which I'm using extensively in my Master's thesis work.

I'm also proud of our macro-benchmark suite of real world Python applications which lives on and PyPy uses it for speed.pypy.org. In all the performance work I've done before and after Unladen, I have to say that our macro benchmark suite was the most useful. Every performance change was easy to check with a before and after text snippet.

We also did a fair amount of good work contributing to LLVM, which other LLVM JIT projects, such as Parrot and Rubinius, can benefit from. For example, there used to be a 16 MB limitation on JITed code size, which I helped to fix. LLVM's JIT also has a gdb interface. Jeff also did a lot of work towards being able to inline C runtime functions into the JITed code, as well as fixing memory leaks and adding the TypeBuilder template for building C types in LLVM.

So, while I wish there were more resources and the project could live on, it was a great experience for me, and we did make some material contributions to LLVM and the benchmark suite that live on.

Working remotely over a high-latency connection

2011-03-26T09:32:00.000-07:00

Does anyone have any tips for working remotely with high network latency? My project is Linux/Windows only, so I work remotely on a beastly machine at CSAIL. It works great when I'm at CSAIL, but terribly from Palo Alto. My two solutions thus far have been:

Use vi over ssh. This sucks because vi then occupies my terminal, and all my keystrokes are buffered over ssh so typing is slow.

Use MacVim and OpenAFS (or any other network filesystem here, including sshfs). This works better for me, but when switching files it takes *forever* (> 15 seconds) to tab-complete filenames or open or save a file. I have to believe this is due to inefficiencies in AFS, because I can scp files faster than MacVim can write to AFS.

I think the ideal solution might look something like Dropbox, where I have a full copy of my source code on both machines, and I only wait for the network when I want to go run the tests. However, I'm doing the initial sync now, and it's taking forever, so I'm not sure this is a real solution.

I haven't tried using bcvi or vim's scp:// file protocol. I'm not enthusiastic about them because I tend to use vim like people use emacs, meaning I keep lots of buffers open and open new files from the same vim instance. I want to be able to use tab completion to open new files, and I don't think vim's scp protocol will let me do that, and if it does, it would suffer from the same latency issues.

Ideas?

x86 register save performance

2011-03-17T13:04:00.001-07:00

Most people who deal with machine code already know that out-of-order CISC chips like most x86 variants are extremely complicated. Optimizing for them has always been a bit of a black art. In my work on DynamoRIO, I'm trying to optimize instrumentation calls to straight C functions. If it's a leaf function, we can try to inline it. For now, I'm just switching stacks and saving used registers inline. There are two ways you can do this. Most C compilers, when they have to spill locals to the stack, will subtract the size of the frame from the stack pointer on entry and address the locals relative to the SP. So, for register saves, I could do the same. However, I could also use the builtin push and pop opcodes. To decide, I did a microbenchmark, and the push and pop opcodes won. Let's look at the assembly:

/* Compile with -DPUSH to get pushes/pops
* and without for movs. */
.globl main
main:
push %rbp
mov %rsp, %rbp
mov $500000000, %rax
.Lloop:
#ifdef PUSH
  push %rax
  push %rbx
  /* etc... */
  push %r15
  /* Mid */
  pop %r15
  /* etc... */
  pop %rbx
  pop %rax
#else
  lea -120(%rsp), %rsp /* Update rsp. */
  mov %rax, 0x70(%rsp)
  mov %rbx, 0x68(%rsp)
  /* etc... */
  mov %r15, 0x00(%rsp)
  /* Mid */
  mov 0x00(%rsp), %r15
  /* etc... */
  mov 0x68(%rsp), %rbx
  mov 0x70(%rsp), %rax
  lea 120(%rsp), %rsp /* Update rsp. */
#endif
  dec %rax
  test %rax, %rax
  jnz .Lloop
leave
ret

So, we have a loop here that saves all registers (I only need to save some for my purposes, this is just a micro-benchmark) in the two ways described. Here are the results for running both on a Core i7 I have access to:

Command:

gcc microbench_push_mov.S -DPUSH -o microbench_push_mov && time ./microbench_push_mov

User time:

trial 1 0m3.400s

trial 2 0m3.404s

trial 3 0m3.404s

Command:

gcc microbench_push_mov.S -o microbench_push_mov && time ./microbench_push_mov

User time:

trial 1 0m3.444s

trial 2 0m3.444s

trial 3 0m3.444s

So, the push/pop version is 1% faster, which depending on how you look at it is unintuitive. At first, one would think that push and pop have to do more work by updating the rsp register for each instruction. Looking at the encoding, I can say that the code size of the moves is much larger, because an offset needs to be encoded for every instruction. "push %rax" is just 50, while "mov %rax, 0x70(%rsp)" is 48 89 44 24 70. I suppose doing the indirect addressing every cycle is also work, but it doesn't need to be managed as a write dependency like the stack pointer updates.

With that in mind, it now makes better sense why most compilers generate pushes for saving caller saved registers on entry, but use stack offset addressing for locals. The encoding for pushes and pops is much smaller, and the execution is marginally faster. Locals are accessed unpredictably, so push and pop aren't really an option.

Dazed and confused in the age of new media

2010-04-15T12:59:00.000-07:00

We've all been talking for a long time about how the old media establishment of a few astronomically popular bands will crumble and give way to a plethora of smaller acts. That's all well and good, and you can see evidence of it in the declining record sales and the rise of music blogs like discodust.blogspot.com and discoworkout.com. The trend is more and more people are spending more time listening to music and searching for talented artists and sharing them with their friends.

However, my experience is that I discover an artist I like, and I'm unable to purchase their music through the large channels I'm familiar with. Let's take Kill the Noise, for example, who is a DJ somewhere in California who happens to have made a remix I like. I go to his site, and it's all about booking information for getting him to come and perform for you. He has several of his tracks in a Flash music player at the top of the page. I'm listening to it as I write this post, and it's good. There are even links to a handful of downloads, some for free and others for pay. But I can't find a single link to an album for purchase.

It makes sense: the album isn't a format that fits the model of new media. Why should an artist release 8 or so tracks all at once in a seemingly arbitrary collection? Why not publish as soon as each track is finished to keep the buzz alive, rather than waiting two years for new music? However, here I am with my wallet, trying to figure out how to purchase roughly $10 worth of music without spending too much time looking for it. I guess there's no place for this in the new media regime. In order to find all the new hip stuff, you've got to have boatloads of time to comb the music blogs and download hit singles.

How to configure smartmontools on an Ubuntu system

2010-04-06T14:43:00.000-07:00

So I'm having some hard drive troubles, and I'm not sure what the cause is. I've had two incidents so far, each of which is precipitated by my music hanging and the Amarok UI freezing and then unfreezing up to 30 seconds later. The first time was quite catastrophic, and I had to restore from my previous night's backup. However, I took the opportunity to do a complete system reinstall, which blew away my cron backup script configuration. So unfortunately, this time around, I didn't have a backup to restore from.

When I noticed the symptoms, I immediately made an incremental backup and rebooted to run fsck. Predictably, fsck reported a few nasty filesystem errors, but it mostly had to do with some unmodified files checked into version control and some system fonts.

Anyway, this experience prompted me to finally setup smartmontools so I can keep track of drive errors and identify if the failure is a controller problem, a connection problem, or a drive problem.

There are many ways to configure smartmontools/smartd, and you can read about them in the man page and across the Internet. These instructions are, in my opinion, the ones that require the least modifications to what Ubuntu sets up for you by default.

So first, do the usual sudo apt-get install smartmontools .

This installs postfix, which I configured as an Internet Site, and left with most of the defaults filled in.

The package comes with an init script that lives at /etc/init.d/smartmontools and is set to run at the defaults runlevel when installed. However, if you try running it manually via sudo /etc/init.d/smartmontools , you will notice that it prints nothing and fails to start a smartd background process. It turns out that you need to edit /etc/default/smartmontools and uncomment the lines they have there, as shown below:

# Defaults for smartmontools initscript (/etc/init.d/smartmontools)
# This is a POSIX shell fragment

# List of devices you want to explicitly enable S.M.A.R.T. for
# Not needed (and not recommended) if the device is monitored by smartd
#enable_smart="/dev/hda /dev/hdb"

# uncomment to start smartd on system startup
start_smartd=yes

# uncomment to pass additional options to smartd on startup
smartd_opts="--interval=1800"

Especially without start_smartd=yes, nothing will work!

Now, before we're off to the races, we want to go check out /etc/smartd.conf, where most of the real configuration we care about happens. Here is the relevant section of my configuration, with comments about each option.

# DEVICESCAN: Scan for ATA and SCSI devices.  All lines after this one are
#   ignored.
# -o on: Enable online data collection.
# -S on: Enable automatic attribute autosave.
# -s (S/../.././02|L/../../6/03): Do a short self-test every night between
#   2-3am and a long self-test every Sunday between 3-4am.
# -H: If the device says it's not healthy, send mail.  This occurs if any
#   prefail attributs are past their thresholds.
# -l selftest: Send mail if, since the last check, a self test has found
#   additional errors.
# -l error: Send mail if the error log has new errors.
# -f: Send mail if the disk has "failed", ie it's total usage is above the
#   threshold set by the manufacturer.  Indication of age, not check failures.
# -m: Address to which to send email.
# -M...: Script to run to send mail and do other things.

# This line is broken up for posting, but I would remove it from the actual
# config file.
DEVICESCAN -o on -S on -s (S/../.././02|L/../../6/03) -H -l selftest -l error -f \
  -m reid.kleckner@gmail.com -M exec /usr/share/smartmontools/smartd-runner

The idea behind this configuration is to be a little bit less verbose than the default of -a, which monitors changes in various parameters, but still generate an email when things go wrong. The results of the self-tests are stored on the hard drive, so if you're having trouble with a drive later, you can check out its bill of health and test record with smartctl -a.

Portable Native Client

2010-03-17T16:58:00.000-07:00

Hey, this is cool:

http://blog.chromium.org/2010/03/native-client-and-web-portability.html
http://nativeclient.googlecode.com/svn/data/site/pnacl.pdf

This is the first I've seen it disclosed publicly, but the summary is that Google plans to make Native Client (NaCl) portable with some kind of verifier on LLVM bitcode. Now, if you're familiar with LLVM, then you may have heard the claim that LLVM bitcode from a C compiler is not platform neutral. The argument is that you always have things like #ifdefs that check for the target architecture and that most C compilers (maybe including Clang? I'm not sure) lower things like sizeof(int) in the frontend. Therefore, they claim, it is essentially impossible to compile C and C++ down to a portable representation.

However, it seems doable for NaCl, because you're not dealing with arbitrary programs. In their writeup, they explicitly say you should eliminate things like architectural #ifdefs. They also state up front that sizeof(int) == sizeof(long) == sizeof(void*) == 4. I'm not sure how that fits in with x86_64. They also state that the data model assumes that integers are little endian, which isn't exactly portable either.

Still, it's a cool project.

"Blocks," or "lambdas in a non-sexp language"

2009-03-11T12:09:00.001-07:00

Last week there was a lot of discussion around tav's proposal to add Ruby blocks to Python. Eventually, the proposal went to python-ideas, and got ground into the dust by all of the objections. The idea has been proposed before, and has always met with strong resistance. The argument against anonymous pseudo-expression functions relies on the idea that Python already has powerful syntax for doing 90% of the things that Ruby and Scheme use blocks and lambdas for, and Guido seems to prefer it that way. In the end, I think Guido's right about blocks in Python, but in another language with different scoping rules, blocks might be a great idea.

Consider the Ruby blocks examples on the c2 wiki. The first three examples, which are iteration, callback registration, and resource management, all have distinct syntaxes in Python, while in Ruby they all use blocks:

Iteration:

# Ruby:
collection.each do |element|
   ...
end

# Python:
for x in collection:
   ...

# Ruby:
numbers = [1,2,3,4]
squares = numbers.map {|n| n*n }

# Python:
numbers = [1, 2, 3, 4]
squares = [n * n for n in numbers]

Callback registration:

# Ruby:
button.on_click do |event|
   ...callback code...
end

# Python:
# (decorators are more general, but this is a common use case
# exemplified by Django filters and tags.)
@button.on_click
def raise_dialog(event):
   ...callback code...

Resource management:

# Ruby:
File.open(filename) do |file|
   ...read from file...
end

# Python:
with open(filename) as file:
   ...read from file...

The consensus on the python-ideas list was that the dedicated for-loop and context-manager syntax is more readable, because no matter what object you're iterating, you have a big fat keyword on the line start telling you how the next code block is going to be executed, instead of one syntax stretching to try and cover multiple unrelated use cases. The verdict could also be interpreted as another instance of the "there should be only one way to do it" philosophy of Python. Currently, def is the only way to create a function that can contain statements, and decorators cover many of the higher-order function use cases. Introducing another syntax for those tasks goes against the grain.

So if blocks aren't good for Python, where do they work?

First of all, I think blocks in Ruby are kind of broken. I've seen many people talk about the elegance of the Ruby block syntax, and I just don't buy it. Why all the puncuation and magic ampersand-arguments? What the hell is up with optional parentheses on function calls? That's friggin' crazy when you're working with function values. It's almost as bad as Common Lisp having separate namespaces for functions and values. The scoping rules are also crazy. Because there's no variable declarations, you can modify names in enclosing scopes by accident. Python deals with this via the new 'nonlocal' statement. Also, the whole DSL craze and the role of blocks in that is just kind of strange to me. So forget that stuff. What I like about Ruby blocks is that they are an innovative way to do non-neutered lambdas in statement-oriented languages without dangling parenthesis.

Blocks occupy this weird middle zone between functional programming and stateful languages, because in functional languages or Lisps statements are either not allowed or are parentheses-wrapped expressions that you can stick anywhere you want anyway. Blocks are especially relevant in whitespace sensitive languages like Python and Ruby, where jamming a statement into an expression is awkward grammatically. Reia is a good case study for what happens if you try to force statements into expressions. So blocks are a little innovation to move the statements out of the expression and into a following block of code. In Lisp, the trailing parenthesis would be no big deal, but in statement-oriented languages it really messes up your grammar.

So what's the point of this stupid syntax hack so you can write multi-statement lambdas in stateful langauges? I think the reason that new Ruby programmers are so much in awe of blocks is because they haven't been properly exposed to first class functions before. A lot of them are web developers, and aren't interested in those high falutin' ideas about functional programming. I think that the key to teaching someone functional programming is lambda. Without the ability to embed executable code into an expression and pass it off to another function, you're left gesticulating wildly about how functions are values like numbers, strings, and lists. Lambda can really demonstrate that, as they say in 6.001, "the value of a lambda is a procedure." Once you've internalized that idea, you're ready for higher-order functions and the rest.

So while I think that in the existing Python ecosystem it makes sense to not have blocks, it makes it harder to teach and use higher-order functions. There's something to be said for the Ruby way of doing all of those examples above. They all use the same mechanism, and that's another kind of "there should be one obvious way to do it" in action.

In conclusion, if you're designing a new non-functional or whitespace sensitive language and you like the power of lambdas, blocks are probably a good way to express them. Patching them into Python now, however, would probably take away from the simplicity of the language.

Automatic repr and eq for Data Structure Classes

2009-03-08T20:58:00.000-07:00

For the compilers class project that I'm working on, I recently wrote a couple of classes that do simple structural equality and automatic __repr__ generation. We have a lot of simple data structure IR classes in our project, and they all need __eq__ and __repr__ for testing and debugging. Structural equality is easy; all you have to do is introspect on __dict__ and see that the attributes match recursively. Automatic __repr__ is more difficult, though, because to produce valid Python source, you have to know the order of the arguments to the instance's __init__ method. Fortunately, with the inspect module, you can call inspect.getargspec(self.__init__) and get that information. We use the simple convention for our IR nodes that the arguments to __init__ all become attributes of the same name, so you can then use the argument names and getattr to generate the reprs of the subnodes. Good times!

Alternatives to django-media-bundler

2009-02-20T10:35:00.000-08:00

Apparently I didn't do a good enough job Googling for other projects when I wrote django-media-bundler. If you Google for django concatenate javsacript or django minify javascript there are a number of other projects that do similar things, each with different tradeoffs:

django-mediacat: To use this tool, you descibe your JS packages in Django models using the django-admin interface. You then configure a URL to point at the mediacat.views.cat view function, and pass it the package names you want as GET arguments. mediacat then caches the resulting file in the database model, and sends the appropriate ETags and Last-Modified tags to make the browser cache the request contents. Last updated: 2008-11-02
django-compress: This tool can be configured to automatically regenerate its bundles by checking the file modification times of the original source files. Obviously, if you're using a content distribution network or a cookieless static domain, this feature might not work out of the box, but if you're a small-time operation, this is nice. It also allows versioning the filenames of the bundles so that when you have new bundles they will bust the browser cache. You can also use the YUI compression tools if available, and finally django-compress has a templatetag that will source the compressed script if compression is enabled, or the individual source files if disabled. Finally, I'd like to point out that this project looks the most mature, as it was started on 2008-04-28, and it has a well-written wiki and not just a README. Last updated: 2008-12-05
django-compact: Looks like it's not quite finished yet, but so far it looks like its main feature is the templatetags that will link to individual script sources or the bundle. Last updated: 2009-01-30
django-assets: Has Jinja 2 templatetags, and supports automatic regeneration of bundles based on file mtime. Bundles are defined inline in the templates instead of in a central configuration. This seems less good to me, because you want to keep the number of different bundles small, so that the user only has to download one script bundle. Sometimes you want more than one because a particular page has a lot of JS, but usually you want all JS to be cached after the first page load. Last updated: 2009-02-08
django-assetpackager: This tool supports cache busting by putting the bundle generation timestamp in the bundle filename. It also has a templatetag that will source individual scripts in debug mode and just the bundle in production mode. Last updated: 2008-06-21
Finally, django-media-bundler: While somewhat unrelated to concatenating and minifying JavaScript and CSS, my project supports image spriting, which is a pain to do by hand. It also employs an interesting little heuristic 2-D bin packing algorithm to try and arrange the images into a square-ish rectangle of minimal area. It has templatetags like a couple of the others, but it doesn't have cache busting. That's an important feature I'd like to add. The auto-regeneration I'm not convinced about, because it breaks down when you're not using a simple single-server setup. Also, it means that your templatetag has to do a bunch of file system calls while its rendering the template, which isn't a terrible idea, but it feels less than perfect. Last updated: 2009-02-15

Having browsed the source trees of each of these projects, in my (biased, of course) opinion the best tools here are django-compress and django-media-bundler. django-compress is mature and has the most JS & CSS bundling features, while the media-bundler is simpler (which can be good) and has image spriting.

django-media-bundler now supports sprites!

2009-02-14T21:14:00.000-08:00

Over the last week I've been working on adding image spriting support to django-media-bundler. For the uninitiated, image spriting is a technique that Google, Yahoo, and other fast web sites use to speed up page load times. What these web sites do is to combine all of their small icon images into one medium size image, and then use CSS background image offsets to display each icon individually from the master. For small icon graphics, the overhead of the HTTP requests dwarfs the size of the actual image, so this speeds things up drastically.

With the help of the Python Imaging Library, I was able to read the images, measure their dimensions, and paste them together into the master image. However, given icons of arbitrary size, it's not clear what is the best way to lay out the master image. Having just taken an advanced algorithms course, this problem seemed like a variation of the bin-packing problem. The bin-packing problem is NP-hard, but once you have a name for something, it's a lot easier to Google up some simple heuristic algorithms to solve the problem.

Finally, I had to figure out how to get the sprites into the page. I found that in audio-enclave we use images in all sorts of interesting ways that make it difficult to abstract away the spriting behind a template tag. In the end I generated a set of CSS rules with the background image and offsets and decided to let the user figure out how to display the images. Working in the sprites was, for our project, more pain than it was worth, and I had to break a couple of nice CSS abstractions to force a DIV node into an element which had none before.

Anyway, implementation details aside, now audio-enclave has excellent front-end performance! Check out these Firebug net tab screenshots:

Before spriting:

After spriting:

Why CPython Will Live On

2009-02-01T08:08:00.000-08:00

Recently there has been a lot of interest on proggit and Hacker News in creating new language implementations on top of existing VMs like the JVM, the CLR, and the Erlang VM Beam. The list of language implementations targeting existing VMs that I can name off the top of my head is long: Clojure, Scala, Jython, JRuby, IronRuby, IronPython, Reia, Ioke, Boo, Fan, F#, and Fortress. I was even working on a small language side-project that had the eventually had the goal of targetting the JVM. This should all be old news to you if you've been paying attention to PL news, and I think it's a pretty good idea. When languages share runtimes, you end up being able to communicate between them nicely, and everyone can collaborate on writing one high-performance garbage collector and one solid JIT.

However, you can only stretch this principle so far. Reia is implemented on top of Beam because it wants capabilities that the JVM doesn't have built-in, like lightweight processes and good fault-tolerant message passing. So what I want to talk about is that while I think Jython and IronPython are a worthwhile ways to get pure Python to play nice with languages on those respective VMx, I still think CPython has a very bright future.

I realized while reading Guido's History of Python blog that one of Python's very early design decisions was to integrate well with existing systems, meaning things written in C. As Guido explains, this was a reaction on his part to his work with the ABC group, which wanted to hide all those scary systems problems away from the programmer and isolate them on some higher-level plane. While this may be good for a learning language, this limits your ability to do interesting things with code that already exists. Python solved that problem by having a relatively simple C API, especially when compared to things like JNI. Going further, the choices to use the GIL and reference counting are decisions that clearly make the life of the C extension module writer easier.

Writing C extension modules isn't exactly peaches and cream, so Greg Ewing came up with Pyrex which was forked into Cython. Cython is a "medium"-level Python-like language which gives you access to C primitives and allows you to call out into both Python and C with ease. The Sage Project, a project to repackage and combine Python math software, uses it extensively.

To give you an idea of what this lets you do, let's say you're writing a C++ plugin for an existing crummy Windows application and you want to make your life better by embedding Python. All you have to do is call PyInitialize() from your plugin, and then you can start interacting with Python code. Cython makes this even easier, because you can write your DLL stubs in Cython as cdef's and you can just wrap it up as a DLL. Doing this kind of thing is technically possible with the JVM. However, while Cython is easy, the JNI is a pain, and the JVM has a massive startup time penalty as compared to CPython. I'd like to link to a more in depth explanation of this technique, but the person I know who is using it hasn't written it up online yet. If and when it does go up I'll link it.

In conclusion, until the day that C's star sets, CPython will continue to be an incredibly useful tool.

Announcing django-media-bundler

2009-01-29T20:00:00.000-08:00

Just a couple of days ago, I looked at the Net tab in Firebug while doing a full refresh of an audio-enclave page. Here's what I saw on our (needlessly) most javascript heavy page:

As you can see, with all those external files, we were flagrantly violating three of the Yahoo best practices: minimize HTTP requests, put scripts at the bottom, and minify JavaScript and CSS. Obviously, what we wanted was to keep developing our JavaScript just as we had in separate modules, and add a build step to our deploy to concatenate and minify our JavaScript and CSS. We had heard of Rails' Asset Packager plugin, so we looked for a Django plugin that did basically the same thing. We were unable to find one, so we wrote our own, dubbing it django-media-bundler, and threw it up on GitHub. Here are the Firebug results of enabling bundling, minification, and deferred JavaScript on that page:

Using django-media-bundler

The media-bundler is a reusable app, so to install it all you have to do is download the source and add it to INSTALLED_APPS. Describe the JavaScript and CSS bundles you would like to create in settings.py as explained in the media_bundle.default_settings module. By default, deferring is enabled, and bundling is disabled when settings.DEBUG is True to assist debugging. You can override those values in your settings module.

To source your scripts, instead of writing
<script type="text/javascript" src="/url/myscript.js"></script>
<link rel="stylesheet" type="text/css" href="/url/mystyle.css"/>
you put {% load bundler_tags %} at the top of your template and write
{% javascript "js_bundle_name" "myscript.js" %}
{% css "css_bundle_name" "mystyle.css" %}

At the bottom of your page in your base template you should put
{% deferred_content %}
where-ever you want to load the scripts in production. We recommend putting a second section after your body.

And that's it! As a future goal, we'd like to help automate the horizontal spriting of PNG icons. We would have a {% sprite "sprite_bundle" "icon_name.png" %} tag that automatically generates a div with a background and offset. Alternatively, it might be nice to run the script and CSS files through the template preprocessor to allow them to access the urlresolver so we don't have anymore hardcoded URLs or janky inline template JavaScript. Happy hacking!

Announcing Audio-Enclave

2009-01-29T19:31:00.000-08:00

This January during MIT's Independent Activities Period I've been working hard on my dormitory floor's music server software. We operate a rack-mount server that plays music in our showers and in our lounges. The server, dubbed "nice-rack", is a hub where all of us come together and share our tastes in music. Using the web interface we wrote, anyone can upload and play music on the server, and anyone can dequeue anyone else's music. Naturally, the server is a flashpoint for arguments about what constitutes good or even tolerable music.

Recently, the entire web interface was rewritten to use Django, and the backend was rewritten using Gstreamer. The project has reached the point in its life where we, the contributing residents of East Campus Second West, think that other people might find the code useful, so we've put the code under a BSD license and moved it to Google Code:

http://code.google.com/p/media-enclave/

Audio-enclave should be useful to anyone who wants to share a communal sound system. Personally, I have vague notions of using audio-enclave as an input to my family's living room stereo, so that we can play music from our collection on the stereo without CDs or laptops that have to be on, open, and plugged in.

Eventually, we intend to support some kind of remote API so that we can write little mobile phone apps to control the playback.